맥케이 정보이론 7강: 잡음 채널 부호화 (2): 잡음 채널의 용량

6강에서 채널 입력 $X$와 출력 $Y$가 공유하는 정보량을 $I(X;Y)$로 썼다. 하지만 같은 채널도 어떤 입력을 얼마나 자주 보내느냐에 따라 전달하는 정보가 달라진다. 채널 용량은 송신자가 입력분포를 가장 잘 골랐을 때 얻는 최대 상호정보량이다.

용량의 정의

전이확률 $P(y\mid x)$가 정해진 이산 기억 없는 채널의 용량은

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

이다. 단위는 채널 한 번당 비트다. 채널은 고정되어도 입력분포 $P(x)$는 설계할 수 있다. 한 기호만 계속 보내면 출력이 아무리 정확해도 새 정보는 0이다. 가능한 입력을 적절히 섞어야 한다.

비트가 확률 $f$로 뒤집히는 이진 대칭 채널에서는 균등 입력이 최적이다. 출력도 균등하므로 $H(Y)=1$, 입력을 알 때 출력에 남는 불확실성은 $H(Y\mid X)=H_2(f)$다.

$$ C=1-H_2(f) $$

오류율이 10퍼센트라면 용량은 약 $0.531$비트다. 채널을 1000번 쓸 때 대략 531비트보다 조금 적은 정보를 보내면 긴 부호를 통해 오류를 거의 없앨 수 있다는 뜻이다. 단순 반복 부호의 $1/3$보다 높다.

용량은 “받은 비트 가운데 맞은 비율"이 아니다. 오류율 10퍼센트라고 용량이 0.9가 되지 않는다. 어느 자리가 틀렸는지 모른다는 불확실성까지 고려하면 잃는 양은 $H_2(0.1)\simeq0.469$비트다.

지움 채널은 비트를 잘못된 값으로 바꾸지 않고, 확률 $e$로 ?를 내보낸다. 수신자는 어느 자리가 사라졌는지 안다. 균등 입력에서 지워지지 않은 비트는 1비트를 온전히 전달하고 지워진 비트는 아무 정보도 주지 않는다.

$$ C=1-e $$

뒤집힘과 지움의 차이가 중요하다. 지움은 오류 위치를 알려주므로 복구하기 쉽다. 같은 비율의 손상이 있어도 채널의 확률 구조에 따라 용량이 달라진다.

어떤 채널은 한 입력 기호를 다른 기호보다 더 잘 전달한다. 이때 균등 입력이 최적이라는 보장은 없다. 너무 불안정한 기호를 덜 쓰면 출력의 구별 가능성이 커질 수 있다.

용량 계산은 $P(x)$를 바꾸며

$$ I(X;Y)=\sum_{x,y}P(x)P(y\mid x)\log_2\frac{P(y\mid x)}{P(y)} $$

를 최대화하는 문제다. 입력 기호 $x$를 보냈을 때의 출력분포가 평균 출력분포 $P(y)$와 얼마나 구별되는지를 평균낸 것으로 볼 수 있다.

상호정보량은 출력으로 입력을 얼마나 알아냈는지 잰다. 데이터 처리 부등식은 관측을 더 가공한다고 입력에 대한 정보가 늘지 않는다고 말한다. $X\to Y\to Z$가 마르코프 연쇄라면

$$ I(X;Z)\le I(X;Y) $$

이다. 손실된 정보는 계산만으로 되살릴 수 없다. 복호기가 하는 일은 정보를 창조하는 것이 아니라, 송신자가 부호어에 심어 둔 구조를 이용해 $Y$에 남은 정보를 최대한 꺼내는 것이다.

$C$를 계산했다고 실제 부호를 얻은 것은 아니다. 용량은 한 번의 채널 사용에서 얻는 최대 상호정보량이고, 부호화 정리는 긴 블록에서 이 값이 신뢰 가능한 통신률의 정확한 경계임을 보인다.

다음 강의에서는 전형적인 잡음 결과를 세고, 무작위로 고른 부호어들조차 용량 아래에서 잘 작동함을 보여 이 약속을 증명한다.