통로 용량(Channel capacity)

1948년 클로드 섀넌은 「통신의 수학적 이론」에서 통신을 이렇게 추상화했습니다. 보내는 쪽이 기호 x를 넣으면 받는 쪽에는 y가 나오는데, 잡음 때문에 y는 x 하나로 정해지지 않고 조건부 확률⁠(conditional probability)⁠ $p(y \mid x)$를 따릅니다. 전선이든 전파든 긁힌 디스크든, 통로는 이 확률표 하나로 요약됩니다. 섀넌이 물은 것은 이 통로를 여러 번 쓰며 긴 메시지를 보낼 때 한 번 쓸 때마다 평균⁠(mean)⁠ 몇 비트를 믿을 만하게 보낼 수 있느냐였고, 답은 통로 용량이라는 수 하나였습니다. 여기서는 통로를 쓸 때마다 잡음이 앞의 일과 상관없이 새로 생기는 통로(이산 무기억 통로)를 다룹니다.

받은 y가 보낸 x에 대해 알려 주는 양은 상호 정보량 $I(X;Y) = H(Y) - H(Y \mid X)$입니다. $H(Y)$는 받는 쪽이 느끼는 불확실성 전체이고(엔트로피⁠, entropy⁠), $H(Y \mid X)$는 x를 알아도 남는 몫, 곧 잡음이 만든 불확실성입니다(조건부 엔트로피⁠, conditional entropy⁠). 통로는 바꿀 수 없지만 보내는 쪽은 0과 1을 어떤 비율로 쓸지 고를 수 있습니다. 그 비율을 가장 잘 골랐을 때의 상호 정보량이 용량⁠(capacity)⁠ C입니다. 이렇게 정의한 수가 정말 '믿을 만하게 보낼 수 있는 속도⁠(velocity)⁠의 한계'와 같다는 것이 아래에서 볼 섀넌의 정리입니다.

통로: , 잡음 세기 , 1을 보낼 확률 $P(X{=}1) =$ .

왼쪽은 통로 그림입니다. 화살표의 굵기가 전이 확률⁠(transition probability)⁠ $p(y \mid x)$이고, 원의 크기가 보내는 기호와 받는 기호의 확률입니다. 오른쪽의 청록 곡선이 $I(X;Y)$, 파란 곡선이 $H(Y)$, 빨간 점선이 $H(Y \mid X)$이고, 파란 곡선에서 빨간 점선을 뺀 것이 청록 곡선입니다. 지금 입력에서 상호 정보량은 비트입니다. 최댓값으로

이진 대칭 통로⁠(binary symmetric channel)⁠는 비트를 확률 q로 뒤집습니다. 0과 1이 대칭이니 반반 보낼 때가 가장 좋고, 그때 $H(Y) = 1$이므로 $C = 1 - H(q)$입니다. 여기서 H(q)는 앞면 확률이 q인 동전의 엔트로피 $-q\log_2 q - (1-q)\log_2(1-q)$로, 비트마다 잡음이 보태는 불확실성입니다. q = 1/2이면 받은 비트가 동전 던지기와 다를 바 없어 용량이 0이고, q가 1/2을 넘으면 용량이 다시 커집니다. 거의 언제나 뒤집는 통로는 받은 비트를 모두 뒤집어 읽으면 되니, 거의 뒤집지 않는 통로만큼 좋습니다. 이진 소거 통로⁠(binary erasure channel)⁠는 비트를 틀리게 전하는 대신 확률 ε로 지워서 '?'로 전합니다. 용량은 지워지지 않고 도착하는 비율 그대로인 $C = 1 - \varepsilon$입니다. 보내는 쪽은 어느 비트가 지워질지 모르는데도, 긴 부호를 쓰면 미리 알고 그 자리를 피해 보내는 것만큼 보낼 수 있습니다.

Z 통로⁠(Z-channel)⁠에서는 0은 언제나 제대로 가고 1만 확률 p로 0이 됩니다. 빛 펄스가 사라질 수는 있어도 없던 펄스가 생기지는 않는 광통신이 이런 모양입니다. 여기서는 반반이 최선이 아닙니다. 잡음이 1에만 붙으니 $H(Y \mid X) = P(X{=}1)\,H(p)$는 1을 많이 보낼수록 곧게 커지고(빨간 직선), 그래서 꼭대기가 왼쪽으로 밀립니다. p = 0.5이면 1을 40%만 보낼 때 C ≈ 0.322비트로 가장 좋고, 반반이면 0.311비트입니다. p가 1에 가까워지면 가장 좋은 비율은 $1/e \approx 0.368$에 다가갑니다. 닫힌 식은 $C = \log_2\bigl(1 + (1-p)\,p^{p/(1-p)}\bigr)$입니다.

상호 정보량은 입력 분포에 대해 오목한 함수⁠(function)⁠, 곧 그래프가 위로 볼록한 함수입니다. 그래서 동네에서 가장 높은 곳이 곧 전체에서 가장 높은 곳이고, 언덕을 오르기만 하면 꼭대기에 닿습니다(볼록 최적화⁠(optimization)⁠). 입력과 출력의 가짓수가 많은 일반적인 통로에는 닫힌 식이 없는 경우가 많습니다. 이때는 1972년 일본의 아리모토 스구루와 미국의 리처드 블라후트가 각각 발표한 반복 알고리즘⁠(algorithm)⁠을 씁니다. 입력 분포를 고정한 채 '받은 y로 x를 거꾸로 짐작하는 분포'를 구하고, 다시 그것을 고정한 채 입력 분포를 고치는 일을 번갈아 되풀이하면 용량으로 수렴⁠(convergence)⁠합니다.

용량이 '최대 상호 정보량'이라는 정의보다 중요한 것은 그 뜻입니다. 통로 부호화 정리⁠(noisy-channel coding theorem)⁠에 따르면 전송률⁠(code rate)⁠이 C보다 작으면 긴 부호로 오류를 얼마든지 줄일 수 있고, C보다 크면 어떤 부호로도 안 됩니다. 무기억 통로를 n번 쓰면 한계는 nC비트입니다. q = 0.1인 이진 대칭 통로는 C ≈ 0.531이라, 통로를 1,000번 써서 믿을 만하게 실을 수 있는 정보는 대략 531비트가 한계입니다. 다만 한계에 바짝 붙어 실으면서 오류를 거의 없애려면 부호가 훨씬 길어야 합니다. 1,000비트 길이에서 오류를 1,000분의 1쯤으로 낮추려면, 어림으로 440비트 안팎까지 덜 실어야 합니다.

이어지는 곳. 대역폭⁠(bandwidth)⁠이 B로 제한된 연속적인 신호에 가우스 잡음(정규분포⁠(normal distribution)⁠를 따르는 잡음)이 더해지는 통로의 용량은 섀넌–하틀리 정리⁠(Shannon–Hartley theorem)⁠ $C = B\log_2(1 + S/N)$비트/초입니다. 용량을 실제로 끌어내는 방법이 오류 정정 부호⁠(error-correcting code)⁠이고, 부호어끼리 서로 다른 비트의 개수인 해밍 거리⁠(Hamming distance)⁠가 설계의 잣대입니다. 상호 정보량을 입력에 대해 최대화하면 용량이 되고, 허용 왜곡 아래에서 최소화하면 율–왜곡 함수⁠(rate–distortion function)⁠가 되어 두 문제가 짝을 이룹니다. 상호 정보량은 결합 분포⁠(joint distribution)⁠가 독립⁠(independence)⁠인 분포에서 얼마나 먼지를 재는 쿨백–라이블러 발산⁠(Kullback–Leibler divergence)⁠이기도 합니다. 용량이 전송의 한계라는 통로 부호화 정리는, 압축의 한계가 엔트로피라는 원천 부호화 정리⁠(source coding theorem)⁠와 함께 섀넌 이론의 두 기둥입니다.