섀넌–하틀리 정리(Shannon–Hartley theorem)

1920년대 벨 연구소의 기술자들은 전선 하나로 얼마나 빨리 보낼 수 있는지 묻고 있었습니다. 해리 나이퀴스트는 1924년과 1928년의 논문에서 전신의 속도⁠(velocity)⁠가 대역폭⁠(bandwidth)⁠에 달려 있음을 밝혔습니다. 대역폭은 통로가 통과시키는 진동수 범위의 폭으로, 300 Hz에서 3,400 Hz까지 통과시키는 전화선이라면 3,100 Hz입니다. 나이퀴스트는 대역폭이 B인 통로로 1초에 서로 섞이지 않게 보낼 수 있는 펄스가 많아야 2B개라는 것을 보였습니다. 같은 1928년 벨 연구소의 랠프 하틀리는 정보의 양을 '구별할 수 있는 선택지 수의 로그'로 정했습니다. 펄스마다 M가지 높이 가운데 하나를 고르면 펄스 하나가 $\log_2 M$비트를 싣고, 1초에 $2B\log_2 M$비트가 됩니다. 그렇다면 M을 한없이 늘리면 되지 않을까요? 그것을 막는 것이 잡음입니다.

신호의 높이를 단계로 나누고, 신호 대 잡음비(신호 전력 S와 잡음 전력 N의 비)를 로 둡시다. 데시벨⁠(decibel)⁠은 전력비의 상용로그에 10을 곱한 값이라, 10 dB는 10배, 30 dB는 1,000배입니다.

단계 사이가 잡음의 폭보다 좁아지면 종 모양들이 겹쳐 읽기가 틀리기 시작합니다. 어림하면, 받은 신호의 진폭⁠(amplitude)⁠은 $\sqrt{S+N}$, 잡음의 진폭은 $\sqrt N$ 정도이니 구별되는 단계는 $M \approx \sqrt{1 + S/N}$개입니다. 지금은 입니다. 이것을 하틀리의 식에 넣으면 $2B \log_2 \sqrt{1+S/N} = B\log_2(1+S/N)$가 됩니다. 1948년 섀넌은 이 어림으로 얻은 식이 정확한 용량⁠(capacity)⁠이라는 것을 증명했고, 1949년 논문 「잡음이 있을 때의 통신」에서 기하학으로 다시 설명했습니다. 단계를 이 어림대로 나누면 기호가 아직 몇 %씩 틀립니다. 섀넌 정리의 힘은 긴 부호를 쓰면 바로 이 속도에서 오류를 얼마든지 줄일 수 있다는 데 있습니다(통로 부호화 정리⁠, noisy-channel coding theorem⁠).

잡음이 정규분포를 따르는 것은 우연이 아닙니다. 열잡음⁠(thermal noise)⁠은 수많은 전자의 작은 떨림이 더해진 것이라 중심극한정리⁠(central limit theorem)⁠에 따라 종 모양이 됩니다. 또 전력이 정해져 있을 때 엔트로피⁠(entropy)⁠가 가장 큰 분포가 정규분포입니다(최대 엔트로피 원리⁠(principle of maximum entropy)⁠). 그래서 상호 정보량⁠(mutual information)⁠ $I(X;Y) = h(Y) - h(N)$(h는 연속분포의 엔트로피)은 입력도 정규분포일 때 가장 크고, 같은 전력의 잡음 가운데 가우스 잡음⁠(Gaussian noise)⁠이 가장 해롭습니다. 계산하면 표본⁠(sample)⁠ 하나에 $\tfrac12\log_2(1+S/N)$비트이고, 여기에 1초의 표본 수 2B(표본화 정리⁠, sampling theorem⁠)를 곱하면 섀넌–하틀리 정리가 나옵니다.

대역폭 1 Hz당 용량 $C/B = \log_2(1+S/N)$을 그린 것이 아래 왼쪽 그림입니다. 지금 신호 대 잡음비⁠(signal-to-noise ratio)⁠에서는 옛 아날로그 전화선은 대략 300–3,400 Hz, 곧 약 3.1 kHz를 통과시키고 신호 대 잡음비는 30–35 dB 정도였습니다. 그러면 C는 초당 31–36킬로비트입니다. 1990년대의 V.34 모뎀이 초당 33.6킬로비트까지 냈으니 거의 한계에 닿았던 셈입니다.

오른쪽 그림은 신호 전력을 고정하고 대역폭을 넓힐 때입니다. 잡음은 1 Hz마다 $N_0$씩 쌓이므로 대역을 넓히면 잡음도 함께 들어옵니다. $S/N_0 = 10{,}000$ Hz로 두고 대역폭을 kHz로 하면

두 영역이 있습니다. 신호 대 잡음비가 클 때는 전력을 두 배(+3 dB)로 늘려도 1 Hz당 초당 약 1비트가 늘 뿐이라, 대역폭을 넓히는 쪽이 이득입니다. 신호 대 잡음비가 작을 때는 용량이 전력에 거의 비례하고, 대역폭을 아무리 넓혀도 $S/(N_0 \ln 2)$를 넘지 못합니다. 이것을 비트 하나에 쓰는 에너지 $E_b = S/C$로 바꿔 쓰면 $E_b/N_0 \ge \ln 2 \approx 0.693$, 곧 −1.59 dB입니다. 대역을 무한히 써도 이보다 적은 에너지로는 1비트를 믿을 만하게 보낼 수 없습니다. 전력이 귀한 먼 우주 탐사선의 통신이 이 한계와 씨름합니다.

섀넌의 1949년 논문은 이것을 기하학으로 보였습니다. T초 동안의 신호는 표본 $n = 2BT$개, 곧 n차원 공간의 한 점입니다. 잡음 벡터⁠(vector)⁠ 길이의 제곱은 성분 n개의 제곱을 더한 것이라, 큰 수의 법칙⁠(law of large numbers)⁠에 따라 n으로 나눈 값이 N에 몰립니다. 그래서 잡음의 길이는 상대적으로 거의 정확히 $\sqrt{nN}$이고, 받은 점은 보낸 점을 중심으로 한 얇은 공 껍질 근처에 떨어집니다. 받은 점은 거의 모두 반지름 $\sqrt{n(S+N)}$인 공 안에 있으니, 서로 겹치지 않는 잡음 공은 대략 많아야 부피의 비 $\bigl(\sqrt{(S+N)/N}\bigr)^n$개 들어갑니다. 로그를 취하면 $\tfrac n2\log_2(1+S/N) = BT\log_2(1+S/N)$비트입니다. 고차원에서는 공의 부피가 거의 모두 껍질에 몰린다는 차원의 저주⁠(curse of dimensionality)⁠가 여기서는 축복이 됩니다. 이진 통로의 잡음 구름 세기(통로 부호화 정리)를 유클리드 거리⁠(Euclidean distance)⁠의 세계로 옮긴 그림입니다.

이어지는 곳. 이산 통로의 용량은 통로 용량⁠(channel capacity)⁠에서, 1초에 표본 2B개면 충분한 이유는 표본화 정리에서 봅니다. 가우스 잡음이 가장 해로운 이유는 최대 엔트로피 원리와 정규분포의 엔트로피로 이어지고, 신호를 여러 진동수의 사인파⁠(sinusoid)⁠로 나누는 푸리에 급수⁠(Fourier series)⁠가 '대역폭'이라는 말의 바탕입니다. 전력을 잡음이 다른 여러 대역에 나눠 쓸 때는 '물 채우기⁠(water-filling)⁠'가 최선입니다. 대역마다 잡음의 크기를 바닥 높이로 삼은 울퉁불퉁한 그릇에 전력이라는 물을 부으면 낮은 곳부터 차듯, 잡음이 작은 대역에 더 많은 전력을 주고 잡음이 너무 큰 대역은 아예 쓰지 않는 것입니다. 대역마다 섀넌–하틀리 식을 더한 총용량을 가장 크게 하는 답이 이 모양입니다. 받은 신호를 가장 가까운 단계로 읽는 일은 신호점들로 나눈 보로노이 영역⁠(Voronoi region)⁠ 가운데 어디에 떨어졌는지 보는 일입니다.