7.21 최적 부호의 존재 증명과 섀넌 한계(Shannon Limit)

1. 최적 부호의 정의

1.1 최적성 기준

유일 복호 가능 부호(uniquely decodable code) 중에서 평균 부호 길이 \bar{L} = \sum_i p_i l_i를 최소화하는 부호를 최적 부호(optimal code)라 한다. 크래프트-맥밀런 부등식에 의해, 접두어 부호(prefix code)의 범위 내에서만 최적화하여도 일반적 유일 복호 가능 부호에 대한 최적과 동일한 평균 부호 길이를 달성할 수 있다.

따라서 최적 부호 문제는 다음으로 정식화된다:

\min_{l_1, \ldots, l_q} \sum_{i=1}^{q} p_i l_i \quad \text{subject to} \quad \sum_{i=1}^{q} 2^{-l_i} \leq 1, \quad l_i \in \mathbb{Z}_{\geq 1}

2. 섀넌 한계의 유도

2.1 실수 이완 문제

정수 제약 l_i \in \mathbb{Z}_{\geq 1}을 실수로 이완(relaxation)한다: l_i \in \mathbb{R}_{> 0}. 크래프트 부등식을 등식으로 놓고 라그랑주 승수법을 적용한다:

\mathcal{L} = \sum_i p_i l_i + \lambda \left(\sum_i 2^{-l_i} - 1\right)

l_i에 대한 편미분:

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

이로부터:

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

크래프트 등식 \sum_i 2^{-l_i} = 1에 대입하면:

\frac{1}{\lambda \ln 2} \sum_i p_i = 1 \implies \lambda = \frac{1}{\ln 2}

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

l_i^* = -\log_2 p_i

이상적 부호어 길이 l_i^* = -\log_2 p_i에서의 평균 부호 길이는:

\bar{L}^* = \sum_i p_i (-\log_2 p_i) = H(X)

이것이 섀넌 한계(Shannon limit)이다: 어떠한 유일 복호 가능 부호도 평균 부호 길이를 엔트로피 H(X) 미만으로 줄일 수 없다.

2.2 정수 제약의 영향

이상적 부호어 길이 l_i^* = -\log_2 p_i는 일반적으로 정수가 아니다. 정수 부호어 길이가 요구되므로, 실현 가능한 최적 부호어 길이는 l_i = \lceil -\log_2 p_i \rceil이다. 이때:

-\log_2 p_i \leq l_i < -\log_2 p_i + 1

평균 부호 길이에 대해:

H(X) \leq \bar{L} < H(X) + 1

따라서 기호 단위(symbol-by-symbol) 최적 부호의 평균 부호 길이는 엔트로피보다 최대 1비트 길다.

3. 최적 접두어 부호의 존재 증명

3.1 존재성

유한 알파벳 \mathcal{X}에 대해, 크래프트 부등식을 만족하는 정수 부호어 길이 (l_1, \ldots, l_q)의 집합은 유한하지 않으나, 평균 부호 길이의 최솟값이 존재함을 보일 수 있다.

l_i \leq -\log_2 p_{\min} + 1로 상한이 설정된다 (여기서 p_{\min} = \min_i p_i > 0). 각 l_i가 유한한 범위의 양의 정수이므로, 가능한 부호어 길이 벡터의 수는 유한하다. 유한 집합에서의 최솟값은 반드시 존재한다. 따라서 평균 부호 길이를 최소화하는 정수 부호어 길이 벡터가 존재하며, 크래프트 부등식에 의해 대응하는 접두어 부호가 존재한다.

3.2 최적 부호의 성질

최적 접두어 부호는 다음의 성질을 만족한다:

성질 1: 확률이 높은 기호에 짧은 부호어가 할당된다. p_i > p_j이면 l_i \leq l_j이다.

증명: l_i > l_j라 가정하면, l_i와 l_j를 교환한 부호는 평균 부호 길이를 \Delta\bar{L} = (p_j - p_i)(l_i - l_j) < 0만큼 감소시키므로, 원래 부호가 최적이 아닌 것에 모순이다.

성질 2: 가장 긴 부호어의 길이를 가지는 기호가 최소 두 개 존재한다.

증명: 가장 긴 부호어가 하나뿐이면, 그 부호어의 마지막 비트를 제거해도 접두어 부호의 성질이 유지되며 평균 부호 길이가 줄어든다. 이는 최적성에 모순이다.

성질 3: 가장 긴 부호어 중 두 개는 마지막 비트만 다른 형제(sibling) 관계이다.

4. 섀넌 부호

4.1 섀넌 부호의 구성

섀넌 부호(Shannon code)는 부호어 길이를 l_i = \lceil -\log_2 p_i \rceil로 설정하는 부호이다. 이 길이가 크래프트 부등식을 만족함은 다음으로 확인된다:

\sum_i 2^{-l_i} \leq \sum_i 2^{-(-\log_2 p_i)} = \sum_i p_i = 1

따라서 이 길이를 가지는 접두어 부호가 존재한다.

4.2 섀넌-파노 부호화

구체적 부호어의 할당은 누적 분포 함수(cumulative distribution function)를 이용한다. 기호를 확률의 내림차순으로 정렬한 후, i번째 기호의 누적 확률 F_i = \sum_{j=1}^{i-1} p_j의 이진 전개(binary expansion)에서 처음 l_i 비트를 부호어로 할당한다.

이 부호의 평균 부호 길이는 H(X) \leq \bar{L} < H(X) + 1을 만족하므로, 섀넌 한계에 최대 1비트의 간극으로 접근한다.

5. 섀넌 한계에의 점근적 접근

5.1 블록 부호화에 의한 간극 축소

n개 기호의 블록 X^n = (X_1, \ldots, X_n)을 단일 슈퍼 기호로 부호화하면, 슈퍼 기호에 대한 섀넌 부호의 평균 부호 길이 L_n은:

H(X^n) \leq L_n < H(X^n) + 1 = nH(X) + 1

기호 당 평균 부호 길이:

H(X) \leq \frac{L_n}{n} < H(X) + \frac{1}{n}

n이 증가함에 따라 간극 1/n이 0으로 수렴하므로, 기호 당 평균 부호 길이는 섀넌 한계 H(X)에 임의로 가깝게 접근한다.

5.2 실용적 한계

블록 길이 n의 증가는 이론적으로 섀넌 한계에의 접근을 보장하지만, 실용적으로는 다음의 비용이 수반된다. 첫째, 슈퍼 기호의 알파벳 크기가 q^n으로 지수적으로 증가하여 부호의 저장과 탐색이 비현실적이 된다. 둘째, 부호화 및 복호화의 지연(delay)이 n에 비례하여 증가한다. 이러한 실용적 한계를 극복하면서 섀넌 한계에 접근하는 것이 실용적 부호화 알고리즘 연구의 핵심 과제이다.

6. 섀넌 한계의 의의

6.1 정보원의 본질적 특성

섀넌 한계는 정보원의 확률 구조에 내재한 본질적 압축 한계를 규정한다. 이 한계는 부호화 기법의 영리함에 무관하게 존재하며, 정보원의 엔트로피에 의해 완전히 결정된다. 어떠한 부호화 방법을 사용하더라도 엔트로피 이하의 평균 부호 길이는 달성할 수 없다.

6.2 부호화 기법의 평가 기준

섀넌 한계는 실용적 부호화 알고리즘의 성능을 평가하는 절대적 기준(benchmark)을 제공한다. 특정 부호화 기법의 평균 부호 길이와 엔트로피의 차이(잉여성, redundancy)가 작을수록 해당 기법이 섀넌 한계에 가까우며, 이는 곧 해당 기법의 우수성을 의미한다.

6.3 통신 시스템 설계의 지침

섀넌 한계는 통신 시스템 설계에서 정보원 부호화의 목표를 명확히 규정한다. 정보원의 엔트로피를 계산하면, 달성 가능한 최대 압축률이 결정되며, 이에 기초하여 전송에 필요한 채널 대역폭을 산정할 수 있다.

7. 결론

섀넌 한계는 무손실 데이터 압축의 근본적이고 넘을 수 없는 한계로, 엔트로피가 이 한계를 정확히 규정함을 무잡음 부호화 정리가 증명한다. 최적 부호의 존재는 유한 알파벳에 대해 보장되며, 블록 부호화에 의해 섀넌 한계에 임의로 가까운 접근이 가능하다. 이 정리는 엔트로피의 조작적 의미를 확립하고, 이후 개발된 모든 실용적 무손실 압축 알고리즘의 이론적 지평을 설정한다.