7.23 산술 부호화(Arithmetic Coding)의 원리와 엔트로피 근접성

1. 산술 부호화의 기본 원리

1.1 허프만 부호화의 한계와 동기

허프만 부호화는 각 정보원 기호에 정수 길이의 부호어를 할당한다. 이상적 부호어 길이 $-\log_2 p_i$ 가 정수가 아닌 경우 올림이 필요하며, 이로 인해 기호 당 최대 1비트의 잉여성이 발생한다. 특히 정보원의 확률 분포가 매우 편향된 경우(예: $p_1 = 0.99$ , $p_2 = 0.01$ ), 이상적 부호어 길이는 약 0.014비트이나 최소 1비트의 부호어를 할당해야 하므로 잉여성이 크다.

산술 부호화(arithmetic coding)는 이 정수 길이 제약을 극복하는 부호화 기법이다. 개별 기호에 부호어를 할당하는 대신, 전체 메시지 수열에 하나의 실수 구간을 대응시키고, 그 구간을 식별하는 이진 분수(binary fraction)를 부호어로 사용한다.

1.2 구간 축소 과정

정보원 알파벳 $\mathcal{X} = \{x_1, x_2, \ldots, x_q\}$ 의 확률이 $p_1, p_2, \ldots, p_q$ 이고, 누적 확률을 $F_0 = 0$ , $F_k = \sum_{j=1}^{k} p_j$ 로 정의한다. 기호 $x_k$ 에는 구간 $[F_{k-1}, F_k)$ 가 대응된다.

길이 $n$ 의 메시지 $s = s_1 s_2 \cdots s_n$ 에 대한 산술 부호화는 다음의 구간 축소(interval narrowing) 과정으로 진행된다:

초기 구간을 $[0, 1)$ 로 설정한다.
각 기호 $s_t$ 를 처리할 때, 현재 구간 $[L, H)$ 를 기호 $s_t$ 에 대응하는 부분 구간으로 축소한다:

$L_{\text{new}} = L + (H - L) \cdot F_{k-1}$
$H_{\text{new}} = L + (H - L) \cdot F_k$

여기서 $s_t = x_k$ 이다.

모든 기호를 처리한 후의 최종 구간 $[L_n, H_n)$ 내의 임의의 점을 선택하고, 이를 이진 분수로 표현하여 부호어로 사용한다.

1.3 부호어의 길이

최종 구간의 길이는 메시지의 확률에 정확히 일치한다:

$H_n - L_n = \prod_{t=1}^{n} p(s_t) = p(s_1, s_2, \ldots, s_n)$

이 구간을 유일하게 식별하는 데 필요한 이진 자릿수는 약 $\lceil -\log_2(H_n - L_n) \rceil + 1$ 비트이다. 따라서 메시지 전체에 대한 부호 길이는:

$l(s) = \lceil -\log_2 p(s) \rceil + 1$

2. 엔트로피 근접성

2.1 기호 당 평균 부호 길이

i.i.d. 정보원에서 길이 $n$ 의 메시지에 대한 산술 부호의 총 비트 수는:

$l(s) = \lceil -\log_2 p(s_1, s_2, \ldots, s_n) \rceil + 1 \leq -\log_2 p(s) + 2$

기댓값을 취하면:

$E[l(S)] \leq E[-\log_2 p(S)] + 2 = H(S_1, \ldots, S_n) + 2 = nH(X) + 2$

기호 당 평균 부호 길이:

$\frac{E[l(S)]}{n} \leq H(X) + \frac{2}{n}$

하한은 무잡음 부호화 정리에 의해 $H(X)$ 이므로:

$H(X) \leq \frac{E[l(S)]}{n} \leq H(X) + \frac{2}{n}$

$n \to \infty$ 에서 기호 당 평균 부호 길이는 $H(X)$ 에 수렴한다. 간극 $2/n$ 은 허프만의 블록 부호화에서의 $1/n$ 과 동일한 차수이지만, 산술 부호화는 명시적 블록 구성 없이 이를 달성한다.

2.2 허프만 부호화와의 비교

산술 부호화의 핵심적 이점은 비정수 비트 할당의 실질적 구현이다. 허프만 부호화에서 확률 $p = 0.99$ 의 기호에 최소 1비트를 할당해야 하는 반면, 산술 부호화에서는 이 기호가 구간의 99%를 차지하므로 실질적으로 약 0.014비트에 해당하는 구간 축소만 발생한다. 이 차이는 확률이 매우 편향된 정보원에서 특히 크다.

구체적으로, 이진 정보원에서 $p(0) = 0.99$ , $p(1) = 0.01$ 인 경우 엔트로피는 $H \approx 0.081$ bits/symbol이다. 허프만 부호의 평균 부호 길이는 1 bit/symbol이며 잉여성이 약 0.919 bits이다. 산술 부호화는 $n$ 이 충분히 크면 기호 당 평균 부호 길이가 0.081에 근접하여 잉여성이 거의 0이다.

3. 복호화 과정

3.1 복호화 알고리즘

복호화기는 수신된 이진 분수 $v$ 로부터 메시지를 복원한다:

초기 구간을 $[0, 1)$ 로 설정한다.
$v$ 가 어떤 기호의 부분 구간에 속하는지 확인하여 해당 기호를 출력한다.
부호화 과정과 동일하게 구간을 축소한다.
메시지 길이 $n$ 이 알려져 있으면 $n$ 개의 기호를 복호한 후 종료한다.

메시지 길이가 사전에 알려져 있지 않은 경우, 특수 종료 기호(end-of-message symbol)를 알파벳에 추가하여 메시지의 끝을 표시한다.

4. 유한 정밀도 구현

4.1 정밀도 문제

무한 정밀도 실수 연산은 실제 컴퓨터에서 구현할 수 없다. 메시지가 길어질수록 구간이 좁아져 매우 높은 정밀도가 필요해진다.

4.2 점진적 출력과 재정규화

실용적 산술 부호화는 구간이 $[0, 0.5)$ 또는 $[0.5, 1)$ 의 한쪽에 완전히 포함되면 해당 비트를 즉시 출력하고, 구간을 두 배로 확장(재정규화, renormalization)하는 방식으로 구현된다. 이 방법에 의해 유한 비트(일반적으로 32비트 또는 64비트) 정수 연산만으로 산술 부호화를 수행할 수 있다.

위텐(Ian H. Witten), 닐(Radford M. Neal), 클리어리(John G. Cleary)가 1987년 “Arithmetic Coding for Data Compression“에서 제시한 실용적 구현은 정수 연산만을 사용하며, 이후 다수의 압축 표준에 채택되었다.

5. 적응적 산술 부호화

정보원의 확률 분포가 사전에 알려져 있지 않은 경우, 적응적(adaptive) 산술 부호화를 사용한다. 이 방법에서는 이미 처리된 기호들로부터 확률 분포를 점진적으로 추정하고, 추정된 분포를 사용하여 다음 기호를 부호화한다. 부호화기와 복호화기가 동일한 추정 규칙을 사용하므로 분포의 별도 전송이 필요 없다.

적응적 산술 부호화는 정보원의 통계적 구조가 시간에 따라 변하는 비정상(non-stationary) 정보원에도 적용 가능하며, 이는 허프만 부호화에 비한 주요 이점이다.

6. 응용

산술 부호화는 다양한 데이터 압축 표준에서 핵심 구성 요소로 사용된다. JPEG 2000 이미지 압축, H.264/AVC 및 H.265/HEVC 비디오 압축의 CABAC(Context-Adaptive Binary Arithmetic Coding), 그리고 범용 압축 라이브러리에서 산술 부호화가 채택되어 있다. 이 응용들에서 산술 부호화는 맥락 모형(context model)과 결합되어 정보원의 조건부 확률 분포를 활용하며, 이를 통해 엔트로피에 매우 가까운 압축 성능을 달성한다.

7. 결론

산술 부호화는 정수 길이 부호어의 제약을 극복하여, 메시지 전체에 대해 사실상 비정수 비트 할당을 실현하는 부호화 기법이다. 기호 당 평균 부호 길이가 $H(X) + 2/n$ 으로 상한이 설정되어 엔트로피에 임의로 가깝게 접근하며, 이는 허프만 부호화의 기호 단위 잉여성 한계를 실질적으로 제거한다. 유한 정밀도 정수 연산에 의한 효율적 구현이 가능하고, 적응적 모드에서 사전 분포 지식 없이도 운용 가능하다는 실용적 이점은, 산술 부호화를 현대 데이터 압축의 핵심 기술로 자리 잡게 하였다.