채널 용량 $C$는 입력과 출력의 최대 상호정보량이다. 이번 강의는 왜 이 숫자가 신뢰할 수 있는 통신률의 경계인지 보여준다. 핵심 그림은 각 부호어 주변에 잡음이 만들 수 있는 전형적인 출력들의 구름을 그리고, 그 구름들이 겹치지 않게 메시지를 배치하는 것이다.

교재: 10장 The Noisy-Channel Coding Theorem.

메시지, 부호어, 전송률

$K$비트 메시지를 길이 $N$인 부호어로 바꾼다. 가능한 메시지는 $2^K$, 전체 이진 문자열은 $2^N$개다. 전송률은

$$ R=\frac KN $$

이다. 부호는 $2^N$개 공간 가운데 $2^K$개 점을 고르는 일이다. 점들을 듬성듬성 놓을수록 잡음 뒤에도 구별하기 쉽지만 전송률은 낮아진다.

잡음이 만드는 전형적인 구름

오류율 $f$인 이진 대칭 채널에서 길이 $N$인 부호어를 보내면 보통 약 $fN$자리가 뒤집힌다. 특정 부호어 주변에서 전형적으로 나오는 출력의 수는 대략

$$ 2^{NH_2(f)} $$

개다. 전체 출력 공간은 $2^N$개이므로 전형적인 잡음 구름 하나가 차지하는 비율은 약

$$ 2^{-N(1-H_2(f))}=2^{-NC} $$

이다.

부호어가 $2^{NR}$개라면 모든 구름이 차지하는 부피는 대략

$$ 2^{NR}2^{NH_2(f)}=2^{N(R+H_2(f))} $$

이다. 이것이 전체 공간 $2^N$보다 작으려면

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

여야 한다. 용량 공식이 공간 채우기 문제에서 다시 나온다.

무작위 부호가 존재를 증명한다

섀넌의 증명은 놀랍게도 정교한 부호를 직접 만들지 않는다. 입력분포에 따라 부호어를 무작위로 많이 뽑는다. 메시지를 보내고 출력이 오면, 입력과 출력이 함께 전형적인 유일한 부호어를 찾는다.

오류는 두 경우에 난다.

  1. 실제 보낸 부호어와 출력이 전형적이지 않다.
  2. 다른 부호어가 우연히 그 출력과도 함께 전형적이다.

첫 사건의 확률은 블록 길이가 커지면 큰 수의 법칙에 따라 0으로 간다. 관계없는 다른 부호어 하나가 출력과 함께 전형적일 확률은 약 $2^{-NI(X;Y)}$다. 후보가 $2^{NR}$개 있으므로 합친 혼동 확률은 대략

$$ 2^{NR}2^{-NI(X;Y)}=2^{-N(I(X;Y)-R)} $$

이다. $R

평균적으로 무작위 부호가 잘 작동한다면 그 가운데 적어도 하나는 평균보다 나쁘지 않다. 이것이 존재 증명의 논리다.

용량 위에서는 왜 안 되는가

채널을 $N$번 쓴 출력이 입력에 대해 줄 수 있는 정보는 최대 $NC$비트다. 그런데 $NR$비트짜리 메시지를 구별하려면 그만큼의 정보가 필요하다. $R>C$이면 출력이 제공할 수 있는 정보보다 메시지 불확실성이 크다.

이를 엄밀하게 잇는 도구가 파노 부등식이다. 복호 오류 확률을 $P_e$라 할 때 메시지 $M$에 남은 조건부 엔트로피는 오류와 연결된다.

$$ H(M\mid Y)\le H_2(P_e)+P_e\log_2(|\mathcal M|-1) $$

오류가 0으로 가려면 출력이 메시지의 거의 모든 엔트로피를 전달해야 한다. 용량보다 높은 비율에서는 그것이 불가능하다.

정리가 보장하지 않는 것

부호화 정리는 좋은 부호가 존재한다고 말하지만 세 가지를 공짜로 주지는 않는다.

  • 짧은 블록에서 좋은 부호를 만드는 법
  • 빠르게 부호화하고 복호하는 법
  • 현실 채널의 모형이 정확하지 않을 때의 견고함

무작위 부호표는 크기가 지수적이라 저장도 검색도 할 수 없다. 실제 통신에는 선형 부호, 저밀도 패리티 검사 부호, 터보 부호처럼 구조가 있으면서 용량에 가까운 부호가 필요하다.

압축 정리와 거울 관계

정보원 부호화에서는 약 $2^{NH(X)}$개의 전형적인 메시지에 짧은 번호를 붙였다. 채널 부호화에서는 각 메시지 주변에 약 $2^{NH(Y\mid X)}$개의 잡음 출력을 허용하면서 전체 출력 공간에 부호어를 배치한다.

압축은 가능한 공간에서 실제로 필요한 부분만 남기고, 오류 정정은 메시지 사이에 빈 공간을 만든다. 두 정리 모두 전형 집합을 세는 같은 논리에서 나온다.

다음 강의에서는 이 존재 정리를 실제로 놀라울 만큼 잘 구현하는 희소 그래프 부호를 보고, 이어서 베이즈 추론의 기본 문제로 넘어간다.