Shannon 채널 코딩 정리 — 존재 증명이 60년을 이끌었다

1948년 Shannon은 놀라운 주장을 했다. 잡음 있는 채널에서도 오류 확률을 임의로 작게 만들 수 있다 — 전송률이 채널 용량 $C$를 넘지 않는 한. 더 놀라운 것은 증명 방식이었다. 구체적인 부호 구성 없이, 순수하게 “랜덤하게 뽑은 부호가 평균적으로 잘 된다”는 확률적 논증이었다. 이 존재 증명이 이후 60년의 공학을 이끌었는데, 왜 그것이 가능했는가?

채널 용량 — $\max_{p(x)} I(X;Y)$

이산 메모리리스 채널(DMC)은 전이 확률 $p(y|x)$로 완전히 정의된다. 채널의 “성능”은 공학적 세부사항이 아니라 단 하나의 수 $C$로 결정된다는 것이 Shannon의 핵심 통찰이다.

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

최대화는 입력 분포 $p(x)$ 위에서 이루어진다. 채널 $p(y|x)$는 자연이 준 것이고, 우리가 선택할 수 있는 것은 어떤 심볼을 어떤 빈도로 보낼 것인가뿐이다. $I(X;Y)$는 $p(x)$에 대해 concave이므로 최대값은 유일하게 존재한다.

세 채널의 용량을 닫힌 형태로 구할 수 있다.

• BSC$(p)$: 비트를 확률 $p$로 뒤집는 대칭 채널. $H(Y|X) = H(p)$는 입력 분포와 무관하므로, $H(Y)$를 최대화하는 균등 입력이 최적이다.

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

• BEC$(\varepsilon)$: 확률 $\varepsilon$로 소거(erasure) 발생. 소거된 심볼에서 정보 0, 수신된 심볼에서 완전 복원.

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

• AWGN (Shannon–Hartley): $Y = X + N$, $N \sim \mathcal{N}(0, \sigma^2)$, 입력 파워 제약 $P$. 분산 조건 하에서 미분 엔트로피를 최대화하는 것은 가우시안 분포(MaxEnt 정리)이므로 $X \sim \mathcal{N}(0,P)$가 최적이다.

$$C_\text{AWGN} = \frac{1}{2}\log_2\!\left(1 + \frac{P}{\sigma^2}\right)$$

SNR = 10 dB일 때 $C \approx 1.73$ bits/use. 5G와 Wi-Fi의 이론 상한이 이 공식으로 결정된다.

Achievability — 랜덤 부호의 역설

Shannon 정리의 한 방향: $R < C$이면 오류 확률을 0으로 만드는 부호가 존재한다.

이 증명의 핵심은 “특수한 구조의 부호를 구성하지 않았다”는 것이다. 랜덤하게 뽑은 부호가 평균적으로 최적이라는 것 — 이것이 확률적 방법(probabilistic method)의 전형적 논증이며, 이후 ML 이론(PAC learning, Rademacher complexity)의 하한 증명에도 같은 구조가 반복된다.

Converse — 용량은 진짜 경계다

Wolfowitz(1957)의 Strong Converse는 더 강하게: $R > C$이면 $P_e^{(n)} \to 1$이다. 단순히 “오류가 줄지 않는다”가 아니라 “반드시 1로 발산한다”는 것이 실용적으로 중요하다 — $R > C$에서의 시도는 완전히 의미 없다.

60년의 공학 — Hamming에서 Polar까지

Shannon의 존재 증명 이후 목표는 단순했다: $R$에 가까우면서 복잡도가 낮은 부호를 실제로 구성하라.

Hamming(7,4) (1950): Generator matrix $G$와 parity check matrix $H$를 이용해 단일 비트 오류를 정정한다. d_\min = 3, Rate $= 4/7$. Syndrome $s = Hy^\top$으로 오류 위치를 직접 읽어낸다. 간단하지만 Shannon 한계와는 큰 gap이 있다.

LDPC (Gallager 1962, MacKay 1996): Parity check matrix $H$가 sparse인 선형 부호. Tanner graph — variable node와 check node의 이분 그래프 — 위에서 Belief Propagation(BP)을 돌린다.

Variable → Check:  m_{v→c} = LLR_v + Σ_{c'≠c} m_{c'→v}
Check → Variable:  m_{c→v} = 2 arctanh( Π_{v'≠v} tanh(m_{v'→c}/2) )

Density evolution 분석으로 decoder threshold가 $C$에 거의 근접함을 보인다. 5G 데이터 채널의 표준이다.

Polar Code (Arıkan 2008): 채널 두 개를 조합하면 하나는 더 좋은 채널 $W^+$, 하나는 더 나쁜 채널 $W^-$로 “극단화”된다. $N = 2^n$회 재귀 적용하면 sub-channel들이 용량 1(“완벽”) 또는 0(“쓸모없음”)으로 수렴한다. 완벽한 채널 $N \cdot C$개에는 정보를, 나머지에는 frozen bit을 배정한다.

이것이 Shannon 정리 이후 처음으로 용량 달성을 수학적으로 증명한 부호다. 5G 제어 채널의 표준이 되었다.

정리

• 채널 용량 $C = \max_{p(x)} I(X;Y)$는 “채널 1회 사용당 신뢰 전송 가능한 최대 비트 수”다.
• Achievability는 random codebook의 확률 논증으로만 증명된다 — 존재성이지 구성이 아니다.
• Converse는 Fano 부등식 + DPI 조합으로 $R > C$에서 $P_e \to 1$을 확정한다.
• Hamming → Turbo → LDPC → Polar의 60년 여정은 이 존재 증명이 실제 구현 가능한 경계임을 공학적으로 확인해 온 과정이다.

존재 증명 하나가 수십 년의 방향을 결정할 수 있다 — Shannon 정리는 그 가장 강력한 사례다.