8.4 소스 부호화(Source Coding)의 기본 원리

1. 소스 부호화의 정의

소스 부호화(source coding)는 정보원(source)이 생성하는 메시지를 가능한 한 적은 비트 수로 표현하는 과정이다. 채널 부호화(channel coding)가 잡음에 대한 오류 내성을 부여하기 위해 의도적으로 잉여성을 추가하는 것과 대조적으로, 소스 부호화는 정보원에 내재하는 잉여성을 제거하여 비트 수를 줄이는 것을 목적으로 한다.

섀넌의 통신 시스템 모형에서 소스 부호화는 정보원과 채널 사이에 위치하며, 정보원-채널 분리 정리에 의해 채널 부호화와 독립적으로 설계할 수 있다.

2. 부호의 형식적 정의

2.1 부호 함수

정보원 알파벳 $\mathcal{X} = \{x_1, x_2, \ldots, x_q\}$ 에 대한 부호 알파벳 $\mathcal{D} = \{0, 1\}$ (이진 부호의 경우)로의 부호(code) $C$ 는 다음과 같이 정의된다:

$C: \mathcal{X} \to \mathcal{D}^+ = \{0, 1\}^+ = \bigcup_{l=1}^{\infty} \{0, 1\}^l$

각 정보원 기호 $x_i$ 에 유한 길이의 이진 수열(부호어, codeword) $C(x_i)$ 를 할당하며, 부호어의 길이를 $l_i = \lvert C(x_i) \rvert$ 로 표기한다.

2.2 비특이 부호

부호가 비특이(non-singular)하다 함은 서로 다른 정보원 기호에 서로 다른 부호어가 할당됨을 의미한다: $x_i \neq x_j$ 이면 $C(x_i) \neq C(x_j)$ 이다. 비특이성은 개별 기호의 복호를 보장하나, 기호 수열의 복호를 보장하지는 않는다.

2.3 확장 부호

부호 $C$ 의 확장(extension) $C^*$ 는 정보원 기호 수열 $x_{i_1} x_{i_2} \cdots x_{i_n}$ 에 대해 부호어를 연결(concatenation)하여 정의한다:

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

확장 부호 $C^*$ 가 비특이이면, 원래 부호 $C$ 를 유일 복호 가능(uniquely decodable)하다고 한다. 이는 부호어의 연결로부터 원래 기호 수열을 유일하게 복원할 수 있음을 의미한다.

3. 부호의 유형 계층

부호의 유형은 복호 가능성의 강도에 따라 다음의 계층을 형성한다:

특이 부호(singular code): 서로 다른 기호에 동일한 부호어가 할당될 수 있다. 복호 불가능.
비특이 부호(non-singular code): 개별 기호의 부호어는 유일하나, 수열의 복호가 보장되지 않을 수 있다.
유일 복호 가능 부호(uniquely decodable code): 확장 부호가 비특이이다. 수열 전체를 본 후 유일한 복호가 가능하다.
접두어 부호(prefix code / instantaneous code): 어떠한 부호어도 다른 부호어의 접두어가 아니다. 각 부호어를 수신하는 즉시 복호가 가능하다.

이 계층에서 접두어 부호가 가장 강한 조건을 만족하며, 크래프트-맥밀런 부등식에 의해 유일 복호 가능 부호의 부호어 길이로 달성 가능한 평균 부호 길이는 접두어 부호로도 동일하게 달성 가능하다.

4. 소스 부호화의 최적화 원리

4.1 가변 길이 부호화의 원리

소스 부호화의 핵심 원리는 빈번한 기호에 짧은 부호어를, 드문 기호에 긴 부호어를 할당하는 것이다. 이 원리는 정보 이론적으로 정당화된다: 기호 $x_i$ 의 이상적 부호어 길이는 $l_i^* = -\log_2 p_i$ 이며, 이는 해당 기호의 자기 정보량에 정확히 일치한다.

평균 부호 길이의 최소화는 다음의 최적화 문제이다:

$\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}$

크래프트 부등식이 제약 조건이며, 허프만 알고리즘이 이 문제의 최적해를 구성한다.

4.2 모형 기반 부호화

소스 부호화의 효율은 정보원의 확률 모형의 정확도에 직접적으로 의존한다. 부호화 과정은 두 단계로 분리된다:

모형화(modeling): 정보원의 확률 분포를 추정한다.
부호화(coding): 추정된 분포에 기반하여 최적 또는 근최적 부호를 구성한다.

산술 부호화는 임의의 확률 모형과 결합하여 해당 모형의 교차 엔트로피에 근접하는 부호 길이를 달성할 수 있으므로, 부호화 단계의 비효율을 사실상 제거한다. 따라서 현대적 소스 부호화에서 성능의 차이는 주로 모형화 단계의 정확도에서 발생한다.

5. 결론

소스 부호화는 정보원의 잉여성을 제거하여 데이터를 효율적으로 표현하는 과정이다. 부호의 유형은 복호 가능성의 강도에 따라 계층을 형성하며, 접두어 부호가 실용적으로 가장 유용한 유형이다. 최적 부호어 길이는 자기 정보량에 의해 결정되며, 평균 부호 길이의 하한은 엔트로피이다. 모형화와 부호화의 분리는 현대적 소스 부호화의 핵심 설계 원칙이며, 모형의 정확도가 압축 성능을 결정하는 주요 요인이다.