8.10 최적 부호어 길이의 존재 증명과 엔트로피와의 관계

1. 최적 부호 설계 문제의 정식화

이산 무기억 정보원 X가 알파벳 \mathcal{X} = \{x_1, x_2, \dots, x_M\} 위에서 확률 분포 \{p_1, p_2, \dots, p_M\}, p_i > 0으로 정의되어 있다고 하자. 최적 부호 설계 문제는 다음의 정수 계획 문제(integer programming problem)로 정식화된다:

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

여기서 제약 조건은 크래프트 부등식이며, 이 조건을 만족하는 양의 정수 길이 집합에 대하여 접두사 부호가 존재함이 보장된다.

2. 최적 부호어 길이의 존재 증명

정리. 위 최적화 문제의 해, 즉 평균 부호어 길이를 최소화하는 부호어 길이 벡터 (l_1^*, l_2^*, \dots, l_M^*)가 존재한다.

증명. 크래프트 부등식 \sum_{i=1}^{M} 2^{-l_i} \leq 1을 만족하는 양의 정수 벡터 (l_1, l_2, \dots, l_M)의 집합을 \mathcal{L}이라 하자. \mathcal{L}은 공집합이 아니다. 예를 들어 모든 l_i = \lceil \log_2 M \rceil로 설정하면 크래프트 부등식이 만족되므로 \mathcal{L} \neq \emptyset이다.

각 l_i에 대하여 유효한 범위의 상한이 존재함을 보이자. 크래프트 부등식에서 2^{-l_i} \leq 1이므로 l_i \geq 1이다. 한편, 최적 부호에서는 l_i \leq l_i^{\text{ub}}인 유한한 상한이 존재한다. 구체적으로, l_i = \lceil -\log_2 p_i \rceil로 설정한 섀넌 부호(Shannon code)의 평균 길이가 L_{\text{Shannon}} < H(X) + 1이므로, 최적 부호의 평균 길이는 L^* \leq L_{\text{Shannon}}이다. 따라서 각 l_i^*는 다음을 만족한다:

p_i \, l_i^* \leq L^* \leq L_{\text{Shannon}} < H(X) + 1

이로부터 l_i^* < (H(X) + 1) / p_i를 얻는다. 따라서 탐색 영역 \mathcal{L}은 유한 집합이며, 유한 집합 위에서의 최소화 문제는 반드시 최솟값을 달성하는 점이 존재한다. \blacksquare

3. 연속 완화와 라그랑주 승수법

최적 부호어 길이의 특성을 분석하기 위하여, 정수 제약을 완화하여 l_i \in \mathbb{R}^+로 놓는 연속 완화(continuous relaxation) 문제를 고려한다:

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

라그랑주 승수법(method of Lagrange multipliers)을 적용한다. 라그랑주 함수는

\mathcal{L}(l_1, \dots, l_M, \lambda) = \sum_{i=1}^{M} p_i \, l_i + \lambda \left( \sum_{i=1}^{M} 2^{-l_i} - 1 \right)

이다. 최적성의 필요조건으로서 각 l_i에 대한 편미분을 0으로 놓으면,

\frac{\partial \mathcal{L}}{\partial l_i} = p_i - \lambda \, 2^{-l_i} \ln 2 = 0

이로부터

2^{-l_i} = \frac{p_i}{\lambda \ln 2}

를 얻는다. 제약 조건 \sum_{i=1}^{M} 2^{-l_i} = 1(등호가 성립함은 별도로 확인할 수 있다)에 대입하면,

\sum_{i=1}^{M} \frac{p_i}{\lambda \ln 2} = 1 \implies \lambda = \frac{1}{\ln 2}

따라서 2^{-l_i^*} = p_i, 즉

l_i^* = -\log_2 p_i

를 얻는다. 이것이 연속 완화 문제의 최적해이며, 이상적 부호어 길이(ideal codeword length) 또는 **섀넌 정보 내용(Shannon information content)**이라 불린다.

4. 이상적 부호어 길이와 엔트로피의 관계

이상적 부호어 길이 l_i^* = -\log_2 p_i를 대입하면, 연속 완화 문제의 최적 평균 부호어 길이는

L^* = \sum_{i=1}^{M} p_i \, l_i^* = \sum_{i=1}^{M} p_i \, (-\log_2 p_i) = H(X)

이다. 즉, 엔트로피는 연속 완화 문제의 최적 평균 부호어 길이와 정확히 일치한다. 이 결과는 엔트로피의 조작적 의미(operational meaning)를 부여한다: 엔트로피는 정보원의 기호를 이진수로 표현할 때 필요한 평균 비트 수의 이론적 최소값이다.

5. 정수 최적 부호어 길이의 범위

실제로는 부호어 길이가 정수여야 하므로, l_i^* = -\log_2 p_i가 정수가 아닌 경우 이상적 부호어 길이를 정확히 달성할 수 없다. 정수 제약 하에서의 최적 부호어 길이 l_i^{\text{opt}}는 다음의 범위에 위치한다.

정리. 정수 최적 부호의 평균 부호어 길이 L^{\text{opt}}는

H(X) \leq L^{\text{opt}} < H(X) + 1

을 만족한다.

하한은 앞서 증명한 섀넌의 하한이며, 상한은 섀넌 부호 l_i = \lceil -\log_2 p_i \rceil의 평균 길이로 달성된다. 등호 L^{\text{opt}} = H(X)는 모든 p_i가 2의 음의 거듭제곱일 때, 즉 p_i = 2^{-n_i}(n_i는 양의 정수)일 때에만 성립한다. 이러한 분포를 **이진 분수 분포(dyadic distribution)**라 한다.

6. 엔트로피와의 관계: 요약

최적 부호어 길이와 엔트로피의 관계를 정리하면 다음과 같다.

블록 길이 n을 증가시키면 기호 당 평균 비트 수가 엔트로피에 임의로 가까워진다는 사실은, 엔트로피가 무손실 압축의 궁극적이고 달성 가능한 한계임을 확인시켜 준다. 이 결과는 정보 이론의 가장 근본적인 정리 중 하나로서, 이후의 모든 부호 설계 알고리즘의 이론적 성능 기준(benchmark)을 제공한다.