통로 부호화 정리(Noisy-channel coding theorem)

1948년 이전의 공학자들에게 잡음은 속도⁠(velocity)⁠와 맞바꾸는 것이었습니다. 오류를 줄이려면 같은 것을 여러 번 보내야 하고, 오류를 0에 가깝게 하려면 전송률도 0에 가까워진다고 여겼습니다. 클로드 섀넌은 「통신의 수학적 이론」에서 이 생각이 틀렸음을 보였습니다. 통로마다 통로 용량 C가 있어서, 전송률 R이 C보다 작기만 하면 부호를 충분히 길게 하여 오류 확률을 원하는 만큼 작게 만들 수 있고, R이 C보다 크면 어떤 부호로도 그럴 수 없습니다. 속도와 신뢰도의 맞바꿈에는 문턱⁠(threshold)⁠이 있었던 것입니다.

비트를 확률 $q =$ 로 뒤집는 이진 대칭 통로⁠(binary symmetric channel)⁠에서, 이름난 부호들의 자리를 전송률–오류 평면에 찍어 봅시다.

반복 부호는 오류가 줄어드는 만큼 전송률도 1/n로 줄어 왼쪽 벽에 붙습니다. 해밍 부호⁠(Hamming code)⁠는 길수록 전송률이 1에 다가가지만 오류도 커집니다. 1949년 스위스 태생 미국 물리학자 마르셀 골레이가 찾은 (23,12) 부호는 12비트를 23비트에 실어 세 개까지의 오류를 고칩니다. q = 0.01이면 묶음이 세 배 큰데도, 전송률이 비슷한 해밍 (7,4)보다 오류가 스물일곱 배쯤 적습니다(7.6×10⁻⁵ 대 2.0×10⁻³). 그러나 q가 커지면(0.077쯤부터) 네 개 이상의 오류가 흔해져 순서가 뒤집힙니다. 섀넌의 정리는 청록 선 왼쪽이면 어디든, 아무리 아래라도 충분히 긴 부호로 닿을 수 있다고 말합니다. 오른쪽에서도 짧은 부호로 어느 정도 낮은 오류를 낼 수는 있습니다('부호 없음' 점이 그 예입니다). 그러나 오류를 원하는 만큼 낮출 수는 없고, 부호를 길게 할수록 오류는 오히려 1로 갑니다.

왜 문턱이 하필 $1 - H(q)$일까요? n비트 부호어⁠(codeword)⁠를 보내면 큰 수의 법칙⁠(law of large numbers)⁠에 따라 거의 언제나 nq개 안팎의 비트가 뒤집힙니다(이항분포⁠, binomial distribution⁠). 그렇게 받을 법한 비트열은 이항계수⁠(binomial coefficient)⁠ $\binom{n}{nq} \approx 2^{nH(q)}$개로(스털링 공식⁠, Stirling's formula⁠), 부호어를 둘러싼 '잡음 구름'을 이룹니다. 받는 쪽이 헷갈리지 않으려면 부호어들의 구름이 겹치지 않아야 하는데, n비트 문자열은 모두 $2^n$개뿐이니 부호어는 대략 많아야 $2^n / 2^{nH(q)} = 2^{n(1-H(q))}$개입니다. 부호어가 $2^{nR}$개이면 이것이 곧 $R \le 1 - H(q) = C$입니다. 이것은 셈의 뼈대이고, 구름이 조금 겹쳐도 되는 경우까지 따지는 엄밀한 증명(파노 부등식을 쓰는 증명)도 같은 결론을 줍니다. 지금 q에서 n = 100이면

거꾸로, C보다 조금 작은 전송률은 실제로 가능할까요? 섀넌의 증명은 대담했습니다. 부호어 $2^{nR}$개를 동전 던지기로 아무렇게나 뽑고, 받은 비트열은 가장 가까운 부호어로 읽습니다. 이렇게 뽑은 부호 전체에 대해 오류 확률을 평균⁠(mean)⁠하면 R이 C보다 작을 때 n이 커질수록 0으로 갑니다. 평균이 작으면 오류 확률이 평균 이하인 부호가 적어도 하나는 있으니 좋은 부호가 존재합니다. 어떤 부호인지는 말해 주지 않는 확률적 방법⁠(probabilistic method)⁠의 증명입니다. 1955년 미국의 정보 이론가 피터 일라이어스는 무작위로 고른 선형 부호⁠(linear code)⁠로도 충분하다는 것을 보였습니다. 선형 부호는 메시지에 행렬⁠(matrix)⁠을 곱해 만드는 부호로, 두 부호어를 자리마다 XOR로 더해도 다시 부호어가 됩니다.

직접 해 봅시다. 메시지 k비트에 무작위로 뽑은 행렬을 곱해 n비트 부호어를 만들고(k는 nR을 반올림한 값), 받은 비트열은 해밍 거리⁠(Hamming distance)⁠로 가장 가까운 부호어로 읽습니다. 메시지가 모두 같은 확률로 나온다면 이것이 이 통로에서 가장 좋은 해독, 곧 최대가능도 해독입니다. 받은 비트열이 나왔을 확률이 가장 큰 부호어를 고르는 해독인데, q가 1/2보다 작으면 뒤집힌 비트가 적을수록 그 확률이 크므로 가장 가까운 부호어가 바로 그것입니다. 전송률 $R =$ . 다른 부호 뽑기

R을 C보다 작게 두면 부호가 길어질수록 오류가 줄고, C보다 크게 두면 오류가 1을 향해 올라갑니다. C보다 큰 전송률에서 오류가 0에서 떨어져 있는 데 그치지 않고 1로 간다는 강한 역정리⁠(strong converse)⁠는 1957년 미국 통계학자 제이컵 울포위츠가 증명했습니다. 곡선이 들쭉날쭉한 것은 k를 반올림하여 실제 전송률 k/n이 조금씩 달라지기 때문이고, R이 C에 가까우면 24비트로는 오류가 거의 줄지 않습니다. 용량 바로 밑까지 가려면 수천 비트 길이의 부호가 필요합니다. 오류 확률을 정확히 셀 수 있는 것은 선형 부호이기 때문입니다. 잡음 패턴은 검사 행렬⁠(parity-check matrix)⁠을 곱한 값(신드롬⁠, syndrome⁠)에 따라 $2^{n-k}$개의 묶음으로 나뉘고, 해독기는 묶음마다 가장 가벼운 패턴, 곧 뒤집힌 비트가 가장 적은 패턴 하나만 바로잡습니다. 그 패턴들의 확률을 모두 더하면 제대로 읽을 확률이 됩니다.

섀넌의 무작위 부호는 해독할 때 부호어 $2^{nR}$개를 모두 비교해야 해서 실제로는 쓸 수 없습니다. 용량에 다가가면서도 빠르게 해독되는 부호를 찾는 데 반세기가 걸렸습니다. 1993년 프랑스의 클로드 베루 등이 발표한 터보 부호⁠(turbo code)⁠가 용량에 바짝 다가가 놀라움을 주었고, 1960년대 미국의 로버트 갤러거가 고안했다가 잊힌 LDPC 부호(검사 하나하나가 비트 몇 개만 보는, 성긴 검사 행렬을 쓰는 부호)가 1990년대에 재발견되었습니다. 2009년 터키의 에르달 아르칸이 내놓은 극 부호⁠(polar code)⁠는, 부호 길이 n에 대해 $n \log n$ 정도의 계산으로 만들고 풀면서 (이진 대칭 통로 같은 대칭 통로의) 용량에 닿는다는 것이 증명된 첫 부호로 꼽힙니다. 5G 이동통신은 데이터에 LDPC 부호⁠(low-density parity-check code)⁠를, 제어 신호에 극 부호를 씁니다(오류 정정 부호⁠(error-correcting code)⁠).

이어지는 곳. 섀넌은 같은 논문에서 압축(원천 부호화 정리⁠, source coding theorem⁠)과 이 정리를 합쳐, 원천을 먼저 엔트로피⁠(entropy)⁠까지 줄인 다음 통로에 맞게 여분을 덧붙여도, 길게 묶어 보내는 극한⁠(limit)⁠에서는 손해가 없다는 것도 보였습니다(분리 정리⁠, source–channel separation theorem⁠). 원천 기호 하나마다 통로를 한 번 쓴다면, 엔트로피가 H인 원천은 H가 C보다 작으면 믿을 만하게 보낼 수 있고 크면 보낼 수 없습니다. 연속 신호의 통로에서는 이 정리가 섀넌–하틀리 정리⁠(Shannon–Hartley theorem)⁠가 되고, 부호어의 잡음 구름을 고차원 공간에 겹치지 않게 채우는 그림은 보로노이 영역⁠(Voronoi region)⁠과 차원의 저주⁠(curse of dimensionality)⁠로 이어집니다. 약간의 왜곡을 허용할 때의 한계는 율–왜곡 이론⁠(rate–distortion theory)⁠이 다룹니다. 잡음 구름의 크기 $2^{nH}$는 압축에서 만나는 전형적 집합⁠(typical set)⁠, 곧 실제로 나올 법한 결과열들의 모임과 같은 것입니다. 압축은 이 모임에 번호를 매기는 데 드는 비트 수를, 통로 부호화는 이런 구름이 몇 개나 겹치지 않고 들어가는지를 세니, 두 정리는 같은 세기 논증의 앞뒷면입니다.