8.7 크래프트 부등식(Kraft Inequality)의 정식화와 증명

1. 크래프트 부등식의 정식화

크래프트 부등식(Kraft Inequality)은 접두사 부호(prefix-free code)가 존재하기 위한 부호어 길이의 필요충분조건을 제시하는 정리이다. 1949년 Leon G. Kraft가 석사 학위 논문에서 처음 증명하였다.

정리 (크래프트 부등식). D-진 알파벳 위에서 부호어 길이가 l_1, l_2, \dots, l_M인 접두사 부호가 존재할 필요충분조건은 다음 부등식이 성립하는 것이다:

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

특히 이진 부호(D = 2)의 경우,

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

이 된다.

이 정리는 두 방향의 명제를 포함한다. (i) 접두사 부호가 존재하면 부호어 길이가 위 부등식을 만족한다(필요조건). (ii) 위 부등식을 만족하는 길이 집합이 주어지면 해당 길이를 갖는 접두사 부호를 구성할 수 있다(충분조건). 이하에서 이진 부호(D = 2)의 경우에 대하여 각 방향을 증명한다.

2. 필요조건의 증명: 접두사 부호이면 크래프트 부등식 성립

접두사 부호의 부호어 집합 \{c_1, c_2, \dots, c_M\}이 주어져 있다고 하자. 최대 부호어 길이를 l_{\max} = \max_i l_i라 하자. 깊이 l_{\max}의 완전 이진 트리(full binary tree)를 고려한다. 이 트리의 잎 노드의 총 수는 2^{l_{\max}}이다.

길이 l_i인 부호어 c_i는 이진 트리의 깊이 l_i에 위치하는 하나의 내부 노드(또는 l_i = l_{\max}이면 잎 노드)에 대응한다. 접두사 조건에 의하여, 부호어 c_i에 대응하는 노드의 모든 후손 잎 노드는 다른 어떤 부호어에도 대응하지 않는다. 깊이 l_i의 노드가 관할하는 잎 노드의 수는 2^{l_{\max} - l_i}개이다.

접두사 조건에 의하여 서로 다른 부호어가 관할하는 잎 노드 집합은 서로소(disjoint)이다. 따라서 이들의 합은 전체 잎 노드 수를 초과할 수 없다:

\sum_{i=1}^{M} 2^{l_{\max} - l_i} \leq 2^{l_{\max}}

양변을 2^{l_{\max}}로 나누면,

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

을 얻는다. \blacksquare

3. 충분조건의 증명: 크래프트 부등식이 성립하면 접두사 부호 존재

부호어 길이 l_1, l_2, \dots, l_M이 크래프트 부등식을 만족한다고 하자. 일반성을 잃지 않고 l_1 \leq l_2 \leq \cdots \leq l_M으로 정렬되어 있다고 가정한다.

부호어를 다음의 귀납적 절차에 의해 구성한다. 각 부호어 c_i를 길이 l_i의 이진수로 간주하고, 그 수치 값을 v_i라 하자.

v_1 = 0

v_k = (v_{k-1} + 1) \cdot 2^{l_k - l_{k-1}}, \quad k = 2, 3, \dots, M

여기서 v_{k-1} + 1은 이전 부호어의 수치 값에 1을 더한 것이고, 2^{l_k - l_{k-1}}을 곱하는 것은 길이 차이만큼 좌측 시프트하는 것에 해당한다.

이 구성이 접두사 조건을 만족함을 보이자. i < j인 두 부호어 c_i와 c_j에 대하여, c_i가 c_j의 접두사가 되려면 c_j의 상위 l_i비트가 c_i와 일치해야 한다. 이는 v_j를 2^{l_j - l_i}로 나눈 몫이 v_i와 같다는 것, 즉

\left\lfloor \frac{v_j}{2^{l_j - l_i}} \right\rfloor = v_i

를 뜻한다. 그런데 구성에 의하여,

\frac{v_j}{2^{l_j - l_i}} \geq \frac{(v_i + 1) \cdot 2^{l_j - l_i}}{2^{l_j - l_i}} = v_i + 1

이므로 \lfloor v_j / 2^{l_j - l_i} \rfloor \geq v_i + 1 > v_i이다. 따라서 c_i는 c_j의 접두사가 될 수 없으며, 접두사 조건이 성립한다.

남은 것은 v_M이 길이 l_M의 이진 표현 범위를 초과하지 않음, 즉 v_M < 2^{l_M}임을 보이는 것이다. 구성 과정에서 각 부호어가 이진 트리의 잎 노드 2^{l_{\max} - l_i}개를 점유하며, 크래프트 부등식에 의하여 점유된 잎 노드의 총 수가 2^{l_{\max}}을 초과하지 않으므로, 모든 부호어의 수치 값이 유효 범위 내에 있음이 보장된다. \blacksquare

4. 크래프트 부등식의 기하학적 해석

크래프트 부등식은 단위 구간 [0, 1)의 분할을 이용하여 기하학적으로 해석할 수 있다. 길이 l_i인 부호어 c_i를 이진 소수(binary fraction) 0.c_i로 해석하면, 이 부호어는 구간 [0.c_i,\; 0.c_i + 2^{-l_i})에 대응한다.

접두사 조건은 이 구간들이 서로 겹치지 않는다는 것과 동치이다. 서로소인 구간들의 길이의 합이 단위 구간의 길이를 초과할 수 없으므로,

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

이 자연스럽게 도출된다. 이 해석은 크래프트 부등식의 직관적 이해를 제공하며, 산술 부호화(arithmetic coding)의 이론적 기초와도 연결된다.

5. D-진 부호로의 일반화

이진 부호에 대한 크래프트 부등식은 D-진 알파벳으로 자연스럽게 일반화된다. D-진 완전 트리에서 깊이 l_i인 노드가 관할하는 잎 노드의 수는 D^{l_{\max} - l_i}이며, 동일한 논증에 의하여

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

을 얻는다. 충분조건의 증명도 이진 경우와 완전히 유사한 구성법에 의해 성립한다.

6. 등호 조건과 완전 부호

크래프트 부등식에서 등호

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

가 성립하는 접두사 부호를 **완전 부호(complete code)**라 한다. 이진 트리 표현에서 완전 부호는 모든 잎 노드가 빠짐없이 어떤 부호어에 의해 관할되는 경우에 해당한다. 완전 부호에서는 어떤 부호어도 더 이상 추가할 수 없으며, 이진 트리의 잎 노드 자원이 완전히 활용된 상태이다.

최적 부호 설계에서 크래프트 부등식의 등호 조건은 중요한 역할을 한다. 평균 부호어 길이를 최소화하는 최적 부호는 일반적으로 완전 부호이며, 이 성질은 허프만 부호화의 최적성 증명에서 핵심적으로 활용된다.