압축에서는 흔한 메시지를 짧게 표현했다. 이제 채널이 메시지를 훼손한다. 송신자는 여분을 넣어 부호화하고, 수신자는 관측된 신호에서 원래 메시지를 추론한다. 이번 강의는 통신을 확률 모형으로 쓰고, 입력과 출력이 얼마나 많은 정보를 공유하는지 재는 도구를 만든다.
교재: 8장 Dependent Random Variables, 9장 Communication over a Noisy Channel.
이진 대칭 채널
가장 단순한 잡음 채널은 비트를 확률 $f$로 뒤집는다.
$$ P(y\mid x)= \begin{cases} 1-f,&y=x\\ f,&y\ne x \end{cases} $$$x$는 보낸 비트, $y$는 받은 비트다. 여러 비트가 독립적으로 뒤집힌다면 전체 가능도는 각 자리 가능도의 곱이다. 수신자는 받은 벡터 $y$에 대해 가능한 부호어 $x$들의 사후확률을 비교한다.
$$ P(x\mid y)\propto P(y\mid x)P(x) $$모든 부호어가 같은 사전확률을 가지면 가장 가까운 부호어를 고르는 최대가능도 복호와 같다. 해밍 거리가 작을수록 적은 비트가 뒤집혔으므로 가능도가 크다.
반복 부호의 교훈
한 비트를 세 번 반복해 000 또는 111로 보내면 한 자리 오류를 다수결로 고칠 수 있다. 하지만 전송률은 $R=1/3$이다. 반복 횟수를 늘리면 오류는 줄어도 속도가 계속 떨어진다.
좋은 부호는 각 메시지에 긴 부호어를 주되 부호어들을 멀리 떨어뜨린다. 동시에 가능한 부호어를 충분히 많이 넣어 전송률을 높여야 한다. 거리와 개수 사이의 싸움이 채널 부호 설계의 핵심이다.
두 변수의 정보량
입력 $X$와 출력 $Y$의 결합 엔트로피는 둘을 함께 알려면 필요한 평균 정보량이다.
$$ H(X,Y)=-\sum_{x,y}P(x,y)\log_2P(x,y) $$$Y$를 안 뒤에도 $X$에 남은 불확실성은 조건부 엔트로피다.
$$ H(X\mid Y)=\sum_yP(y)H(X\mid Y=y) $$연쇄 규칙은 전체 불확실성을 먼저 $Y$를 아는 비용과, 그 뒤 $X$를 아는 비용으로 나눈다.
$$ H(X,Y)=H(Y)+H(X\mid Y) $$입력에 원래 있던 정보 $H(X)$ 가운데 출력을 보고 알아낸 양이 상호정보량이다.
$$ I(X;Y)=H(X)-H(X\mid Y) $$대칭적으로
$$ I(X;Y)=H(Y)-H(Y\mid X)=H(X)+H(Y)-H(X,Y) $$이다. 채널이 완벽하면 $H(X\mid Y)=0$이라 입력 정보를 모두 얻는다. 출력이 입력과 무관하면 $H(X\mid Y)=H(X)$이고 상호정보량은 0이다.
벤 그림보다 중요한 것
엔트로피 항등식은 집합의 넓이를 닮아 벤 그림으로 그릴 수 있다. 겹치는 부분이 $I(X;Y)$, $X$에만 남은 부분이 $H(X\mid Y)$다. 다만 그림은 기억 도구일 뿐이다. 세 변수 이상에서는 조건부 상호정보량과 상호작용이 단순한 넓이 직관을 벗어날 수 있다.
상호정보량은 두 변수가 공유한 의존성을 재며 항상 0 이상이다. 상대 엔트로피로도 쓸 수 있다.
$$ I(X;Y)=D_{\mathrm{KL}}\big(P(x,y)\|P(x)P(y)\big) $$결합분포가 독립분포의 곱에서 얼마나 벗어났는지를 재는 값이다.
이진 대칭 채널에서 사라지는 정보
입력을 0과 1에 똑같이 보내면 $H(X)=1$비트다. 오류율이 $f$인 채널에서 출력을 안 뒤 남는 불확실성은 $H_2(f)$다. 따라서 한 번 사용할 때 공유되는 정보는
$$ I(X;Y)=1-H_2(f) $$이다. $f=0$이면 1비트, $f=1/2$이면 0비트다. 흥미롭게도 $f>1/2$라고 통신이 끝난 것은 아니다. 출력 비트를 뒤집어 읽으면 오류율 $1-f$인 채널이 된다. 정확히 절반일 때만 입력과 출력이 완전히 무관하다.
다음 강의에서는 입력분포를 바꿀 수 있을 때 상호정보량의 최댓값을 구한다. 그것이 채널 용량이다.