8.8 맥밀런 부등식(McMillan Inequality)과 고유 복호 가능성

1. 맥밀런 부등식의 정식화

크래프트 부등식은 접두사 부호의 존재 조건을 규정한다. 맥밀런 부등식(McMillan Inequality)은 이 결과를 고유 복호 가능 부호(uniquely decodable code) 전체로 확장한 것으로, 1956년 Brockway McMillan이 증명하였다.

정리 (맥밀런 부등식). D-진 알파벳 위에서 부호어 길이가 l_1, l_2, \dots, l_M인 고유 복호 가능 부호가 존재하면, 다음 부등식이 성립한다:

\sum_{i=1}^{M} D^{-l_i} \leq 1

이 정리의 핵심적 함의는 다음과 같다. 접두사 부호는 고유 복호 가능 부호의 특수한 경우이므로, 크래프트 부등식에 의하여 접두사 부호의 부호어 길이가 위 부등식을 만족함은 이미 알고 있다. 맥밀런 부등식은 접두사 조건을 만족하지 않는 고유 복호 가능 부호까지 포함하여 동일한 부등식이 성립함을 보인 것이다.

2. 맥밀런 부등식의 증명

이진 부호(D = 2)에 대하여 증명한다. 부호어 길이가 l_1, l_2, \dots, l_M인 고유 복호 가능 부호가 주어져 있다고 하자. 최대 부호어 길이를 l_{\max} = \max_i l_i로 놓는다.

크래프트 합(Kraft sum)을 K = \sum_{i=1}^{M} 2^{-l_i}로 정의하자. K \leq 1임을 보이기 위하여, K의 n-제곱을 분석한다.

K^n = \left( \sum_{i=1}^{M} 2^{-l_i} \right)^n = \sum_{i_1=1}^{M} \sum_{i_2=1}^{M} \cdots \sum_{i_n=1}^{M} 2^{-(l_{i_1} + l_{i_2} + \cdots + l_{i_n})}

다중 합의 각 항 (i_1, i_2, \dots, i_n)은 길이 n의 정보원 기호열 x_{i_1} x_{i_2} \cdots x_{i_n}에 대응하며, 지수 l_{i_1} + l_{i_2} + \cdots + l_{i_n}은 해당 기호열의 연접 부호어의 총 길이이다. 이 총 길이를 s라 하면, n \cdot l_{\min} \leq s \leq n \cdot l_{\max}이다. 여기서 l_{\min} = \min_i l_i이다.

총 길이가 s인 기호열의 수를 A_s로 놓으면,

K^n = \sum_{s = n \cdot l_{\min}}^{n \cdot l_{\max}} A_s \cdot 2^{-s}

로 쓸 수 있다. 이제 A_s의 상한을 구한다. 총 길이가 s인 연접 부호열은 길이 s의 이진 문자열이다. 부호가 고유 복호 가능하므로, 서로 다른 기호열은 서로 다른 이진 문자열에 대응한다. 따라서 A_s는 길이 s인 이진 문자열의 총 수를 초과할 수 없다:

A_s \leq 2^s

이를 대입하면,

K^n = \sum_{s = n \cdot l_{\min}}^{n \cdot l_{\max}} A_s \cdot 2^{-s} \leq \sum_{s = n \cdot l_{\min}}^{n \cdot l_{\max}} 2^s \cdot 2^{-s} = \sum_{s = n \cdot l_{\min}}^{n \cdot l_{\max}} 1 = n(l_{\max} - l_{\min}) + 1

따라서 모든 양의 정수 n에 대하여,

K^n \leq n(l_{\max} - l_{\min}) + 1

이 성립한다. 만약 K > 1이면 좌변 K^n은 n \to \infty일 때 지수적으로 증가하지만, 우변은 n에 대하여 선형적으로만 증가한다. 이는 충분히 큰 n에서 모순을 야기한다. 따라서 K \leq 1이다. \blacksquare

3. 맥밀런 부등식의 역과 크래프트 부등식의 통합

맥밀런 부등식의 역, 즉 크래프트 부등식을 만족하는 부호어 길이에 대하여 고유 복호 가능 부호가 존재한다는 명제 역시 성립한다. 크래프트 부등식의 충분조건 증명에서 이미 보인 바와 같이, 해당 길이를 갖는 접두사 부호가 존재하며, 접두사 부호는 고유 복호 가능하다.

이로써 크래프트 부등식과 맥밀런 부등식을 통합하면 다음의 정리를 얻는다.

정리 (크래프트-맥밀런 정리). 다음 세 조건은 동치이다:

(a) 부호어 길이가 l_1, l_2, \dots, l_M인 접두사 부호가 존재한다.

(b) 부호어 길이가 l_1, l_2, \dots, l_M인 고유 복호 가능 부호가 존재한다.

(c) \sum_{i=1}^{M} 2^{-l_i} \leq 1이 성립한다.

이 동치 관계의 핵심적 의미는, 부호어 길이의 관점에서 접두사 부호와 고유 복호 가능 부호가 정확히 동일한 능력을 갖는다는 것이다. 고유 복호 가능이지만 접두사 부호가 아닌 부호가 존재할 수 있으나, 그 부호어 길이와 동일한 길이를 갖는 접두사 부호가 반드시 존재한다.

4. 평균 부호어 길이에 대한 함의

크래프트-맥밀런 정리는 최적 부호 설계 이론에 근본적인 영향을 미친다. 정보원 기호 x_i의 확률이 p_i일 때, 고유 복호 가능 부호의 평균 부호어 길이는

L = \sum_{i=1}^{M} p_i \, l_i

이다. L을 최소화하는 최적 고유 복호 가능 부호를 구하는 문제는, 크래프트-맥밀런 정리에 의하여, 크래프트 부등식 \sum_{i=1}^{M} 2^{-l_i} \leq 1을 제약 조건으로 하는 최적화 문제로 환원된다:

\min_{l_1, l_2, \dots, l_M} \sum_{i=1}^{M} p_i \, l_i \quad \text{subject to} \quad \sum_{i=1}^{M} 2^{-l_i} \leq 1

더 나아가, 이 최적화 문제의 해를 접두사 부호로 실현할 수 있으므로, 실제 부호 설계에서는 접두사 부호만을 고려하면 충분하다. 이 결론은 허프만 부호화, 섀넌-파노 부호화 등 실용적 부호 설계 알고리즘이 접두사 부호의 범위 내에서 동작하는 이론적 정당성을 부여한다.

5. 맥밀런 부등식 증명의 기법적 의의

맥밀런의 증명에서 사용된 “크래프트 합의 n-제곱” 기법은 정보 이론의 여러 정리 증명에서 반복적으로 활용되는 중요한 방법론이다. 이 기법의 핵심은 단일 부호어 수준의 성질을 분석하기 어려울 때, 길이 n의 기호열 전체에 대한 부호화를 고려함으로써 조합론적 상한을 도출하는 것이다. n을 무한대로 보내면 지수적 증가율과 다항식적 증가율의 비교를 통해 원하는 결론을 이끌어낸다. 이러한 **블로킹 기법(blocking technique)**은 섀넌의 부호화 정리 증명에서도 핵심적인 역할을 담당한다.