8.5 고유 복호 가능 부호(Uniquely Decodable Code)의 조건

1. 고유 복호 가능 부호의 정의

이산 무기억 정보원(Discrete Memoryless Source)이 알파벳 $\mathcal{X} = \{x_1, x_2, \dots, x_M\}$ 위에서 정의되어 있다고 하자. 부호(code)란 각 정보원 기호 $x_i$ 에 부호어(codeword) $c_i \in \{0, 1\}^{l_i}$ 를 대응시키는 사상 $C: \mathcal{X} \to \{0, 1\}^*$ 이다. 여기서 $l_i$ 는 부호어 $c_i$ 의 길이를 나타낸다.

유한 기호열 $x_{i_1} x_{i_2} \cdots x_{i_n}$ 의 부호화 결과는 각 기호에 대응하는 부호어를 연접(concatenation)한 것으로서,

$C^n(x_{i_1} x_{i_2} \cdots x_{i_n}) = c_{i_1} c_{i_2} \cdots c_{i_n}$

로 정의된다. 이때 부호 $C$ 가 **고유 복호 가능(uniquely decodable)**하다 함은, 임의의 유한 길이 정보원 기호열에 대하여 그 연접 부호화 결과가 유일하게 원래의 기호열로 복호될 수 있음을 뜻한다. 형식적으로 표현하면, 모든 양의 정수 $n$ 에 대하여 확장 부호 사상 $C^n: \mathcal{X}^n \to \{0,1\}^*$ 이 단사(injective)임을 요구하는 것이다.

2. 비특이 부호와 고유 복호 가능 부호의 구별

부호의 복호 가능성에 관한 조건을 단계적으로 분류할 수 있다.

비특이 부호(Nonsingular Code): 부호 사상 $C$ 가 단사, 즉 $x_i \neq x_j$ 이면 $c_i \neq c_j$ 인 부호를 비특이 부호라 한다. 비특이성은 개별 기호의 복호를 보장하지만, 기호열의 연접 부호화에 대해서는 복호의 유일성을 보장하지 못한다.

예를 들어, $\mathcal{X} = \{a, b, c\}$ 이고 부호어가 각각 $C(a) = 0$ , $C(b) = 01$ , $C(c) = 011$ 인 경우를 고려하자. 이 부호는 비특이하지만, 연접 부호열 $011$ 은 $C(a)C(b) = 0 \cdot 01 = 001$ 과는 구별되나 $C(c) = 011$ 과 $C(a)C(a)C(b) = 0 \cdot 0 \cdot 11$ 은 아니므로, 이 예시에서는 비특이성만으로는 부족함을 확인할 수 있다.

고유 복호 가능 부호: 기호열의 길이에 관계없이 연접 부호화 결과로부터 원래 기호열을 유일하게 복원할 수 있는 부호이다. 이 조건은 비특이성보다 엄밀히 강한 조건이다.

3. 고유 복호 가능성의 필요충분조건

고유 복호 가능성을 판정하기 위한 체계적 방법으로 **사르디나스-패터슨 알고리즘(Sardinas–Patterson Algorithm)**이 있다. 부호 $C$ 의 부호어 집합을 $S = \{c_1, c_2, \dots, c_M\}$ 라 하자. 다음의 집합열을 재귀적으로 정의한다.

$S_1 = S^{-1} S \setminus \{\epsilon\}$

$S_{n+1} = S^{-1} S_n \cup S_n^{-1} S, \quad n \geq 1$

여기서 $A^{-1}B = \{y : \exists\, a \in A,\; ay \in B\}$ 는 집합 $A$ 에 대한 $B$ 의 좌몫(left quotient)이며, $\epsilon$ 은 빈 문자열이다. 사르디나스-패터슨 정리에 의하면, 부호 $C$ 가 고유 복호 가능할 필요충분조건은 어떤 $n \geq 1$ 에 대해서도 $\epsilon \notin S_n$ 인 것이다.

이 알고리즘은 유한 단계 안에 종료됨이 보장된다. 가능한 잉여 접미사(dangling suffix)의 집합이 유한하므로, 집합열 $\{S_n\}$ 이 궁극적으로 주기적이 되기 때문이다.

4. 고유 복호 가능 부호의 성질

고유 복호 가능 부호는 다음과 같은 중요한 성질을 갖는다.

성질 1. 모든 접두사 부호(prefix-free code)는 고유 복호 가능하다. 접두사 부호에서는 어떤 부호어도 다른 부호어의 접두사가 되지 않으므로, 부호열을 왼쪽에서 오른쪽으로 순차적으로 탐색하면 즉시 복호가 가능하다.

성질 2. 고유 복호 가능 부호의 부호어 길이 $l_1, l_2, \dots, l_M$ 은 크래프트 부등식(Kraft Inequality)을 만족한다:

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

이는 맥밀런 부등식(McMillan Inequality)으로 알려져 있으며, 고유 복호 가능 부호의 부호어 길이에 대한 근본적인 제약 조건을 제시한다.

성질 3. 크래프트 부등식을 만족하는 임의의 길이 집합 $\{l_1, l_2, \dots, l_M\}$ 에 대하여, 해당 길이를 갖는 접두사 부호가 존재한다. 따라서 고유 복호 가능 부호로 달성할 수 있는 평균 부호어 길이의 범위는 접두사 부호로도 동일하게 달성 가능하다.

5. 평균 부호어 길이와의 관계

정보원 기호 $x_i$ 의 확률이 $p_i = P(X = x_i)$ 일 때, 부호 $C$ 의 **평균 부호어 길이(expected codeword length)**는

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

로 정의된다. 고유 복호 가능 부호 중에서 $L(C)$ 를 최소화하는 문제가 최적 부호 설계의 핵심이며, 성질 2와 성질 3에 의하여 이 최적화 문제는 접두사 부호의 범위 내에서 탐색하여도 최적해를 잃지 않는다.

6. 고유 복호 가능성 판정의 예

구체적 예를 통하여 사르디나스-패터슨 알고리즘의 적용을 살펴보자. $\mathcal{X} = \{a, b, c, d\}$ 이고 부호어가 $C(a) = 0$ , $C(b) = 01$ , $C(c) = 011$ , $C(d) = 111$ 인 부호를 고려하자.

$S = \{0, 01, 011, 111\}$ 에 대하여 좌몫을 계산하면,

$S_1 = \{1, 11\}$

이다. $0$ 은 $01$ 과 $011$ 의 접두사이므로 잉여 접미사 $1$ 과 $11$ 이 발생한다. 다음으로,

$S_2 = S^{-1}S_1 \cup S_1^{-1}S = \{1\} \cup \{1, \epsilon\}$

에서 $\epsilon \in S_2$ 이므로, 이 부호는 고유 복호 가능하지 않다. 실제로, 부호열 $0111$ 은 $C(a)C(d) = 0 \cdot 111$ 로도, $C(c)C(a) = 011 \cdot ?$ 이 아닌 $C(b)C(a)C(a) = 01 \cdot ?$ … 등 여러 가지로 해석될 수 있어 모호성이 발생한다.

이와 같이 고유 복호 가능 부호의 조건은 효율적인 데이터 압축 부호의 설계에 있어 반드시 충족되어야 할 기본 요건이며, 이후 논의할 크래프트 부등식 및 최적 부호 설계 이론의 출발점이 된다.