7.24 잡음 채널 부호화 정리(Noisy Channel Coding Theorem)의 개요

1. 정리의 역사적 의의

잡음 채널 부호화 정리(noisy channel coding theorem)는 섀넌의 제2정리(Shannon’s second theorem)로, 클로드 섀넌(Claude Shannon)이 1948년 “A Mathematical Theory of Communication“에서 증명하였다. 이 정리는 잡음이 존재하는 통신 채널에서 신뢰성 있는 통신이 가능한 조건과 그 한계를 정확히 규정한 것으로, 정보 이론의 가장 심원한 결과로 평가된다.

이 정리가 혁명적인 이유는, 잡음의 존재가 정확한 통신을 원리적으로 불가능하게 만드는 것이 아니라 단지 전송 속도의 상한을 설정할 뿐임을 밝혔기 때문이다. 이 상한, 즉 채널 용량(channel capacity) 이하의 전송률에서는 오류 확률을 임의로 작게 만드는 것이 가능하다.

2. 기본 설정

2.1 이산 무기억 채널

이산 무기억 채널(discrete memoryless channel, DMC)은 입력 알파벳 $\mathcal{X}$ , 출력 알파벳 $\mathcal{Y}$ , 전이 확률 $p(y \vert x)$ 의 삼중쌍으로 정의된다. ’무기억’은 각 시점의 채널 출력이 해당 시점의 채널 입력에만 의존하고 과거에는 의존하지 않음을 의미한다.

2.2 채널 부호의 정의

$(M, n)$ 채널 부호(channel code)는 다음으로 구성된다:

메시지 집합: $\mathcal{W} = \{1, 2, \ldots, M\}$
부호화 함수: $f: \mathcal{W} \to \mathcal{X}^n$ . 각 메시지 $w$ 를 길이 $n$ 의 채널 입력 수열 $\mathbf{x}(w) = (x_1, x_2, \ldots, x_n)$ 으로 매핑한다.
복호화 함수: $g: \mathcal{Y}^n \to \mathcal{W}$ . 채널 출력 수열 $\mathbf{y}$ 를 메시지 추정값 $\hat{w}$ 로 매핑한다.

부호율(code rate)은 $R = (\log_2 M) / n$ (bits per channel use)로 정의된다.

2.3 오류 확률

메시지 $w$ 가 전송되었을 때의 조건부 오류 확률은:

$\lambda_w = P(g(\mathbf{Y}) \neq w \vert W = w)$

최대 오류 확률은 $\lambda^{(n)} = \max_{w \in \mathcal{W}} \lambda_w$ 이고, 평균 오류 확률은 $P_e^{(n)} = (1/M) \sum_{w=1}^{M} \lambda_w$ 이다.

3. 채널 용량의 정의

채널 용량(channel capacity) $C$ 는 입력 분포 $p(x)$ 에 대한 상호 정보량의 최댓값이다:

$C = \max_{p(x)} I(X; Y)$

여기서 $I(X; Y) = H(Y) - H(Y \vert X) = H(X) - H(X \vert Y)$ 이다. 채널 용량은 채널의 고유한 특성으로, 입력 분포의 최적 선택에 의해 달성되는 단일 채널 사용당 최대 정보 전달량을 나타낸다.

4. 정리의 진술

4.1 달성 가능성 (정정리)

정리 (달성 가능성): 부호율 $R < C$ 인 모든 $R$ 에 대해, 충분히 큰 블록 길이 $n$ 에서 최대 오류 확률 $\lambda^{(n)}$ 을 임의로 작게 만드는 $(2^{nR}, n)$ 부호가 존재한다.

보다 정밀하게, $R < C$ 이면 다음을 만족하는 부호열 $\{(2^{nR}, n)\}_{n=1}^{\infty}$ 이 존재한다:

$\lambda^{(n)} \leq 2^{-nE(R)}$

여기서 $E(R) > 0$ 은 오류 지수(error exponent) 또는 신뢰도 함수(reliability function)이다. 오류 확률은 $n$ 에 대해 지수적으로 감소한다.

4.2 역정리 (불가능성)

정리 (역정리): 부호율 $R > C$ 이면, 블록 길이 $n$ 이 아무리 커도 오류 확률을 0으로 수렴시키는 부호열은 존재하지 않는다.

보다 정밀하게, $R > C$ 인 모든 $(2^{nR}, n)$ 부호에 대해:

$P_e^{(n)} \geq 1 - \frac{C}{R} - \frac{1}{nR}$

$n \to \infty$ 에서 $P_e^{(n)} \geq 1 - C/R > 0$ 이므로, 오류 확률은 양의 값 이하로 내려갈 수 없다.

4.3 강한 역정리

울프로위츠(Jacob Wolfowitz)가 증명한 강한 역정리(strong converse)에 의하면, $R > C$ 일 때 $P_e^{(n)} \to 1$ as $n \to \infty$ 이다. 즉, 채널 용량을 초과하는 전송률에서는 오류 확률이 단순히 0으로 수렴하지 않는 것을 넘어, 1로 수렴한다.

5. 증명의 핵심 아이디어

5.1 임의 부호화 논증

달성 가능성 증명에서 섀넌이 사용한 핵심 기법은 임의 부호화(random coding)이다. 부호어를 입력 분포 $p^*(x)$ (용량을 달성하는 최적 입력 분포)에 따라 독립적으로 무작위 생성한다. 이러한 임의 부호의 평균 오류 확률이 $n$ 이 충분히 크면 임의로 작아짐을 보인다.

임의 부호화 논증의 핵심은 결합 전형성(joint typicality)의 개념이다. 전송된 부호어 $\mathbf{x}(w)$ 와 채널 출력 $\mathbf{y}$ 가 결합적으로 전형적(jointly typical)인 경우에만 올바른 복호가 이루어진다. $R < C$ 일 때, 잘못된 메시지의 부호어가 채널 출력과 결합적으로 전형적일 확률은 $n$ 에 대해 지수적으로 감소한다.

5.2 존재 증명의 성격

임의 부호화 논증은 좋은 부호가 “존재한다“는 것을 증명하지만, 그러한 부호를 구체적으로 “구성하는” 방법을 제시하지는 않는다. 이 존재 증명과 구성적 증명의 간극을 메우는 것이 이후 부호화 이론 연구의 핵심 과제가 되었다.

6. 채널 용량의 사례

6.1 이진 대칭 채널 (BSC)

교차 확률 $p$ 인 BSC의 채널 용량:

$C_{\text{BSC}} = 1 - H_b(p)$

$p = 0$ 이면 $C = 1$ bit, $p = 1/2$ 이면 $C = 0$ 이다.

6.2 이진 소거 채널 (BEC)

소거 확률 $\epsilon$ 인 BEC의 채널 용량:

$C_{\text{BEC}} = 1 - \epsilon$

6.3 가산 백색 가우시안 잡음 채널 (AWGN)

대역폭 $W$ , 신호 전력 $S$ , 잡음 전력 스펙트럼 밀도 $N_0/2$ 인 AWGN 채널의 용량:

$C = W \log_2\left(1 + \frac{S}{N_0 W}\right)$

이 식은 섀넌-하틀리 공식(Shannon-Hartley formula)으로 알려져 있다.

7. 정리의 영향

7.1 부호화 이론의 발전

잡음 채널 부호화 정리는 채널 용량에 접근하는 실용적 부호의 구성이라는 연구 과제를 설정하였다. 이 과제는 수십 년에 걸쳐 추구되었으며, 해밍 부호(1950), BCH 부호(1959/1960), 리드-솔로몬 부호(1960), 컨볼루션 부호(1955), 비터비 복호(1967), 터보 부호(1993), LDPC 부호(1960/1996) 등의 발전을 거쳐, 섀넌 한계에 사실상 도달하는 부호가 실현되었다.

7.2 현대 통신 시스템에의 적용

현대의 4G/5G 이동 통신, 위성 통신, 심우주 통신 등에서 사용되는 부호화 기법은 모두 섀넌의 채널 부호화 정리가 제시한 이론적 한계를 목표로 설계된다. 극 부호(polar code)는 어클란(Erdal Arıkan)이 2009년에 제안한 것으로, 구성적으로 채널 용량을 달성하는 최초의 부호 범주이며, 5G NR의 제어 채널 부호화에 채택되었다.

8. 결론

잡음 채널 부호화 정리는 잡음 존재 하에서 신뢰성 있는 통신의 근본적 가능성과 한계를 규정한다. 채널 용량 이하의 전송률에서 오류 확률을 임의로 줄일 수 있다는 달성 가능성 결과와, 채널 용량 초과 전송률에서 이것이 불가능하다는 역정리는, 채널 용량이 통신의 근본적 한계에 대한 정확한 특성화임을 확립한다. 이 정리는 정보 이론의 학문적 정당성을 확립한 핵심 결과이자, 현대 통신 기술의 이론적 토대이다.