7.20 무잡음 부호화 정리(Noiseless Coding Theorem)의 정식화

1. 정리의 역사적 맥락

무잡음 부호화 정리(noiseless coding theorem)는 섀넌의 제1정리(Shannon’s first theorem) 또는 정보원 부호화 정리(source coding theorem)로도 불리며, 클로드 섀넌(Claude Shannon)이 1948년 “A Mathematical Theory of Communication“에서 증명하였다. 이 정리는 데이터 압축의 이론적 한계를 엄밀하게 규정하는 것으로, 엔트로피가 정보원의 본질적 정보율(intrinsic information rate)에 대한 정확한 척도임을 확립한다.

2. 기본 정의

2.1 정보원 부호

이산 무기억 정보원(discrete memoryless source, DMS) $X$ 가 알파벳 $\mathcal{X} = \{x_1, \ldots, x_q\}$ 위에서 확률 질량 함수 $p(x_i)$ 를 가진다. 정보원 부호(source code) $C$ 는 각 정보원 기호 $x_i$ 에 유한 길이의 이진 수열(부호어, codeword) $c(x_i) \in \{0, 1\}^*$ 를 할당하는 함수이다. 부호어 $c(x_i)$ 의 길이를 $l_i = \lvert c(x_i) \rvert$ 로 표기한다.

2.2 평균 부호 길이

부호 $C$ 의 평균 부호 길이(average code length)는:

$\bar{L}(C) = \sum_{i=1}^{q} p(x_i) l_i = E[l(X)]$

데이터 압축의 목표는 $\bar{L}$ 을 최소화하는 부호를 설계하는 것이다.

2.3 유일 복호 가능 부호

부호가 유용하려면 부호어의 연결(concatenation)로부터 원래의 기호 수열을 유일하게 복원할 수 있어야 한다. 유일 복호 가능 부호(uniquely decodable code)는 임의 유한 길이의 정보원 기호 수열에 대해 부호화된 이진 수열이 유일하게 복호 가능한 부호이다.

접두어 부호(prefix code) 또는 순시 부호(instantaneous code)는 어떠한 부호어도 다른 부호어의 접두어가 아닌 부호이다. 접두어 부호는 유일 복호 가능하며, 부호어가 도착하는 즉시 복호가 가능하다.

3. 크래프트 부등식

3.1 진술

정리 (크래프트 부등식, Kraft inequality): 부호어 길이 $l_1, l_2, \ldots, l_q$ 를 가지는 접두어 부호가 존재할 필요충분조건은:

$\sum_{i=1}^{q} 2^{-l_i} \leq 1$

3.2 맥밀런 부등식

정리 (맥밀런 부등식, McMillan inequality): 유일 복호 가능 부호의 부호어 길이도 동일한 부등식을 만족한다:

$\sum_{i=1}^{q} 2^{-l_i} \leq 1$

크래프트-맥밀런 부등식에 의해, 유일 복호 가능 부호의 부호어 길이로 달성 가능한 평균 부호 길이의 범위는 접두어 부호로 달성 가능한 범위와 동일하다. 따라서 최적 부호 설계에서 접두어 부호만 고려하면 일반성을 잃지 않는다.

4. 무잡음 부호화 정리의 정식화

4.1 기호 단위 부호화

정리 (무잡음 부호화 정리, 기호 단위): 이산 무기억 정보원 $X$ 의 엔트로피를 $H(X)$ 라 하자. 유일 복호 가능 부호의 평균 부호 길이 $\bar{L}$ 에 대해:

$H(X) \leq \bar{L}$

더 나아가, 다음을 만족하는 접두어 부호가 존재한다:

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

하한의 증명: 크래프트 부등식 $\sum_i 2^{-l_i} \leq 1$ 이 성립한다. $r_i = 2^{-l_i} / \sum_j 2^{-l_j}$ 로 놓으면 $\{r_i\}$ 는 확률 분포이다. KL 발산의 비부정성에 의해:

$D_{\text{KL}}(P \| R) = \sum_i p_i \log_2 \frac{p_i}{r_i} \geq 0$

이를 전개하면:

$\sum_i p_i \log_2 p_i - \sum_i p_i \log_2 r_i \geq 0$

$-H(X) + \sum_i p_i l_i + \sum_i p_i \log_2 \left(\sum_j 2^{-l_j}\right) \geq 0$

$\sum_j 2^{-l_j} \leq 1$ 이므로 $\log_2(\sum_j 2^{-l_j}) \leq 0$ 이다. 따라서:

$\bar{L} - H(X) \geq -\log_2\left(\sum_j 2^{-l_j}\right) \geq 0$

즉, $\bar{L} \geq H(X)$ 이다.

상한의 달성: $l_i = \lceil -\log_2 p_i \rceil$ 로 부호어 길이를 설정한다. $-\log_2 p_i \leq l_i < -\log_2 p_i + 1$ 이므로 $2^{-l_i} \leq p_i$ 이고, $\sum_i 2^{-l_i} \leq \sum_i p_i = 1$ 이므로 크래프트 부등식이 만족된다. 접두어 부호가 존재하며:

$\bar{L} = \sum_i p_i l_i < \sum_i p_i(-\log_2 p_i + 1) = H(X) + 1$

4.2 블록 부호화에 의한 엔트로피 수렴

정리 (무잡음 부호화 정리, 블록 부호화): 정보원 기호를 $n$ 개씩 블록으로 묶어 부호화하면, 기호 당 평균 부호 길이를 엔트로피에 임의로 가깝게 만들 수 있다.

구체적으로, $X^n = (X_1, X_2, \ldots, X_n)$ 을 하나의 ’슈퍼 기호’로 간주하여 부호화하면, $X^n$ 의 엔트로피는 i.i.d. 가정 하에서 $H(X^n) = nH(X)$ 이다. 기호 단위 정리에 의해:

$nH(X) \leq L_n < nH(X) + 1$

여기서 $L_n$ 은 블록 당 평균 부호 길이이다. 기호 당 평균 부호 길이 $\bar{L}_n = L_n / n$ 에 대해:

$H(X) \leq \bar{L}_n < H(X) + \frac{1}{n}$

$n \to \infty$ 에서 $\bar{L}_n \to H(X)$ 이다. 따라서 충분히 긴 블록을 사용하면 기호 당 평균 부호 길이를 엔트로피에 임의로 가깝게 만들 수 있다.

5. 점근적 등분할 성질과의 관계

5.1 AEP의 진술

점근적 등분할 성질(Asymptotic Equipartition Property, AEP)은 무잡음 부호화 정리의 증명에서 핵심적 역할을 한다. i.i.d. 확률 변수 $X_1, X_2, \ldots, X_n$ 에 대해:

$-\frac{1}{n} \log_2 p(X_1, X_2, \ldots, X_n) \xrightarrow{P} H(X)$

즉, 긴 수열의 표본 엔트로피(sample entropy)가 참 엔트로피에 확률 수렴한다.

5.2 전형 수열 집합

$\epsilon > 0$ 에 대해 전형 수열 집합(typical set) $A_\epsilon^{(n)}$ 을 다음과 같이 정의한다:

$A_\epsilon^{(n)} = \left\{(x_1, \ldots, x_n) : \left\lvert -\frac{1}{n} \log_2 p(x_1, \ldots, x_n) - H(X) \right\rvert < \epsilon \right\}$

AEP에 의해 다음이 성립한다:

$P(A_\epsilon^{(n)}) > 1 - \epsilon$ for sufficiently large $n$
$\lvert A_\epsilon^{(n)} \rvert \leq 2^{n(H(X) + \epsilon)}$
$\lvert A_\epsilon^{(n)} \rvert \geq (1-\epsilon) 2^{n(H(X) - \epsilon)}$ for sufficiently large $n$

5.3 전형 수열에 기반한 부호화

전형 수열 집합의 원소 수가 약 $2^{nH(X)}$ 개이므로, 전형 수열을 색인하는 데 약 $nH(X)$ 비트가 필요하다. 비전형 수열은 확률이 무시할 만큼 작으므로, 전체 기호 당 평균 부호 길이는 약 $H(X)$ 비트에 수렴한다.

구체적으로, 전형 수열에는 $\lceil nH(X) + n\epsilon \rceil + 1$ 비트의 부호어를 할당하고 (선두 비트 0으로 시작), 비전형 수열에는 $\lceil n \log_2 \lvert\mathcal{X}\rvert \rceil + 1$ 비트의 부호어를 할당하면 (선두 비트 1으로 시작), 평균 부호 길이가 $n(H(X) + \epsilon) + 2$ 를 넘지 않는다. $n$ 이 충분히 크면 기호 당 평균 부호 길이가 $H(X) + \epsilon + 2/n$ 이므로, $H(X)$ 에 임의로 가깝게 접근한다.

6. 역정리: 엔트로피 이하의 압축 불가능성

6.1 진술

무잡음 부호화 정리의 역정리(converse)는, 기호 당 평균 부호 길이가 엔트로피 미만인 유일 복호 가능 부호가 존재하지 않음을 진술한다:

$\bar{L}_n \geq H(X) \quad \text{for all } n$

어떠한 블록 길이 $n$ 과 어떠한 유일 복호 가능 부호를 사용하더라도, 기호 당 평균 부호 길이는 엔트로피 미만이 될 수 없다.

6.2 의미

달성 가능성 정리와 역정리를 결합하면, 엔트로피는 무손실 데이터 압축의 근본적 한계를 정확히 규정한다:

엔트로피 이하의 압축률은 달성 불가능하다.
엔트로피에 임의로 가까운 압축률은 충분히 긴 블록 부호를 통해 달성 가능하다.

따라서 엔트로피는 정보원의 본질적 정보율에 대한 완전한 특성화이다.

7. 결론

무잡음 부호화 정리는 엔트로피가 데이터 압축의 정밀한 한계임을 수학적으로 확립한다. 기호 단위 부호화에서 평균 부호 길이는 $H(X)$ 이상 $H(X) + 1$ 미만이 달성 가능하며, 블록 부호화에 의해 이 간극은 $1/n$ 으로 축소된다. 이 정리는 엔트로피의 조작적 의미(operational meaning)를 제공하며, 후속적으로 개발된 허프만 부호, 산술 부호화, 렘펠-지브 부호 등 실용적 압축 알고리즘의 이론적 기초가 된다.