8.9 섀넌의 무잡음 부호화 정리와 평균 부호어 길이의 하한

1. 무잡음 부호화 문제의 정식화

이산 무기억 정보원(Discrete Memoryless Source) $X$ 가 알파벳 $\mathcal{X} = \{x_1, x_2, \dots, x_M\}$ 위에서 확률 분포 $p_i = P(X = x_i)$ , $i = 1, 2, \dots, M$ 으로 정의되어 있다고 하자. 이 정보원의 엔트로피는

$H(X) = -\sum_{i=1}^{M} p_i \log_2 p_i$

이다. 무잡음 부호화(noiseless coding) 또는 무손실 부호화(lossless coding) 문제란, 고유 복호 가능(uniquely decodable) 이진 부호 $C$ 의 평균 부호어 길이

$L(C) = \sum_{i=1}^{M} p_i \, l_i$

를 최소화하는 부호를 설계하는 것이다.

2. 평균 부호어 길이의 하한

정리 (섀넌의 하한). 이산 무기억 정보원 $X$ 에 대한 임의의 고유 복호 가능 이진 부호 $C$ 의 평균 부호어 길이는 엔트로피 이상이다:

$L(C) \geq H(X)$

등호는 모든 $i$ 에 대하여 $p_i = 2^{-l_i}$ , 즉 모든 확률이 $2$ 의 음의 거듭제곱 형태일 때에만 성립한다.

증명. 크래프트-맥밀런 정리에 의하여, 고유 복호 가능 부호의 부호어 길이 $l_1, l_2, \dots, l_M$ 은 크래프트 부등식 $\sum_{i=1}^{M} 2^{-l_i} \leq 1$ 을 만족한다. $r_i = 2^{-l_i} / \sum_{j=1}^{M} 2^{-l_j}$ 로 정의하면, $\{r_i\}$ 는 확률 분포를 이룬다.

$L(C) - H(X)$ 를 분석한다:

$L(C) - H(X) = \sum_{i=1}^{M} p_i \, l_i + \sum_{i=1}^{M} p_i \log_2 p_i = -\sum_{i=1}^{M} p_i \log_2 2^{-l_i} + \sum_{i=1}^{M} p_i \log_2 p_i$

$= \sum_{i=1}^{M} p_i \log_2 \frac{p_i}{2^{-l_i}} = D_{\text{KL}}(p \| q) + \sum_{i=1}^{M} p_i \log_2 \frac{1}{\sum_j 2^{-l_j}} + D_{\text{KL}}(p \| r) \cdot 0$

보다 직접적으로, $q_i = 2^{-l_i}$ 로 놓으면 $\sum_i q_i \leq 1$ 이며,

$L(C) - H(X) = \sum_{i=1}^{M} p_i \log_2 \frac{p_i}{q_i}$

이다. 깁스 부등식(Gibbs’ Inequality)에 의하여, 임의의 확률 분포 $\{p_i\}$ 와 $\sum_i q_i \leq 1$ 인 양의 수열 $\{q_i\}$ 에 대하여

$\sum_{i=1}^{M} p_i \log_2 \frac{p_i}{q_i} \geq \sum_{i=1}^{M} p_i \log_2 \frac{1}{\sum_j q_j} \geq 0$

이 성립한다. 첫째 부등식은 쿨백-라이블러 발산(Kullback–Leibler Divergence)의 비음성에서 유도되며, 둘째 부등식은 $\sum_j q_j \leq 1$ 에서 따른다. 따라서 $L(C) \geq H(X)$ 이다.

등호 조건은 $q_i = p_i$ , 즉 $2^{-l_i} = p_i$ 이고 $\sum_i q_i = 1$ 일 때 성립한다. 이는 $l_i = -\log_2 p_i$ 가 모든 $i$ 에 대하여 정수일 것을 요구한다. $\blacksquare$

3. 섀넌의 무잡음 부호화 정리

하한의 달성 가능성에 관하여 섀넌은 다음의 정리를 증명하였다.

정리 (섀넌의 무잡음 부호화 정리, Shannon’s Noiseless Source Coding Theorem). 이산 무기억 정보원 $X$ 에 대하여, 고유 복호 가능 이진 부호 $C$ 의 평균 부호어 길이 $L(C)$ 는 다음을 만족하는 것이 존재한다:

$H(X) \leq L(C) < H(X) + 1$

증명. 각 기호에 대하여 부호어 길이를 $l_i = \lceil -\log_2 p_i \rceil$ 로 설정하자. 여기서 $\lceil \cdot \rceil$ 은 올림 함수(ceiling function)이다. 이 길이가 크래프트 부등식을 만족하는지 확인한다:

$\sum_{i=1}^{M} 2^{-l_i} = \sum_{i=1}^{M} 2^{-\lceil -\log_2 p_i \rceil} \leq \sum_{i=1}^{M} 2^{\log_2 p_i} = \sum_{i=1}^{M} p_i = 1$

따라서 이 길이를 갖는 접두사 부호가 존재한다. 평균 부호어 길이의 상한은 다음과 같이 얻어진다:

$L(C) = \sum_{i=1}^{M} p_i \, \lceil -\log_2 p_i \rceil < \sum_{i=1}^{M} p_i \, (-\log_2 p_i + 1) = H(X) + 1$

하한은 앞서 증명한 $L(C) \geq H(X)$ 에 의해 성립한다. $\blacksquare$

4. 블록 부호화에 의한 엔트로피 율 달성

단일 기호 부호화에서는 평균 부호어 길이와 엔트로피 사이에 최대 $1$ 비트의 간격이 존재한다. 그러나 $n$ 개의 기호를 블록(block)으로 묶어 부호화하면 이 간격을 줄일 수 있다.

정보원의 $n$ -차 확장(extension) $X^n = (X_1, X_2, \dots, X_n)$ 에 대하여, 무기억 가정에 의해 $H(X^n) = n H(X)$ 이다. $X^n$ 에 대한 최적 부호의 평균 부호어 길이를 $L_n$ 이라 하면,

$n H(X) \leq L_n < n H(X) + 1$

기호 당 평균 비트 수는

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

이므로, $n \to \infty$ 일 때 기호 당 평균 비트 수가 엔트로피 $H(X)$ 에 수렴한다. 이것이 섀넌의 무잡음 부호화 정리의 핵심적 결론이다: 엔트로피는 무손실 압축의 궁극적 한계이며, 블록 길이를 충분히 크게 하면 이 한계에 임의로 가까이 접근할 수 있다.

5. 정보량과 부호어 길이의 관계

섀넌의 정리는 정보량(information content)과 부호어 길이 사이의 근본적 관계를 드러낸다. 기호 $x_i$ 의 자기 정보량(self-information)은 $I(x_i) = -\log_2 p_i$ 이며, 최적 부호어 길이는 $l_i^* \approx I(x_i)$ 에 가깝다. 즉, 발생 확률이 낮은(놀라움이 큰) 기호에는 긴 부호어를, 발생 확률이 높은(놀라움이 작은) 기호에는 짧은 부호어를 할당하는 것이 최적이다.

이 원리는 데이터 압축의 기본 철학을 수학적으로 정당화한다. 자주 나타나는 패턴을 짧게 표현하고 드문 패턴을 길게 표현하는 전략이, 평균적으로 가장 효율적인 표현을 달성한다는 사실이 엄밀히 증명된 것이다.

6. $D$ -진 부호로의 일반화

$D$ -진 알파벳을 사용하는 경우, 엔트로피의 밑을 $D$ 로 변경하면 동일한 결과가 성립한다:

$H_D(X) \leq L(C) < H_D(X) + 1$

여기서 $H_D(X) = -\sum_{i=1}^{M} p_i \log_D p_i$ 는 $D$ -진 엔트로피이다. 이 일반화는 삼진, 사진 등 비이진 부호 체계에서도 엔트로피가 압축 한계를 결정한다는 사실을 보여준다.