섀넌의 잡음 채널 부호화 정리, 채널 용량까지는 오류를 0에 가깝게 줄일 수 있다

핵심 메시지

• 비트가 일정 확률로 뒤집히는 통신로에서 같은 비트를 세 번씩 반복해 보내면 오류는 줄지만 전송 속도가 3분의 1로 떨어진다는 것이 문제의 출발점이다.
• 오류 확률을 0에 가깝게 만들려면 속도도 0에 수렴해야 한다는 것이 오랜 상식이었지만, 클로드 섀넌은 1948년 논문에서 이 경계가 원점을 지나지 않는다는 사실을 증명했다.
• 채널마다 정해진 '용량'이 있어서 그 값보다 느리기만 하면, 원하는 만큼 작은 오류 확률을 달성하는 부호가 존재한다는 것이 정리의 핵심이다.
• 섀넌은 그런 부호가 존재한다는 사실만 보였을 뿐 구체적인 방법은 제시하지 않았고, 이는 이후 오류 정정 부호 연구가 폭발한 계기가 됐다.
• 마법처럼 보이는 결과에는 조건이 있다. 메시지를 아주 긴 덩어리로 묶어 보낼 때만 성립하므로, 20비트짜리 짧은 메시지에는 이 보장이 적용되지 않는다.

쉽게 이해하기

설명은 아주 구체적인 문제에서 시작한다. 이진 메시지를 보내야 하는데 통신로가 각 비트를 일정 확률로 뒤집는다고 하자. 뒤집힐 확률이 0.1이면 받는 쪽 메시지의 약 10%가 원래와 달라진다. 보내는 쪽과 받는 쪽이 미리 약속을 정해 메시지를 특별한 방식으로 부호화하고 복호화하면 이 오류를 줄일 수 있다.

가장 소박한 방법은 각 비트를 세 번씩 반복하고, 받는 쪽이 세 개 묶음마다 더 많이 나온 값을 채택하는 것이다. 이렇게 하면 오류는 확실히 줄지만 사라지지는 않는다. 한 묶음에서 두 개 이상이 뒤집히면 그대로 오류가 된다. 열 번씩 반복하면 오류는 더 줄지만 전송 속도가 10분의 1이 된다. 결국 우리는 오류 확률과 속도라는 두 가지를 동시에 신경 쓰게 된다.

그래서 가로축을 원본 길이 대비 부호화된 길이의 비율인 전송률로, 세로축을 비트 오류 확률로 두고 생각해보자. 아무 부호화도 하지 않으면 전송률은 1이고 오류 확률은 채널의 뒤집힘 확률과 같다. 세 번 반복은 전송률 3분의 1에 더 낮은 오류 확률에 놓인다. 여기서 자연스러운 질문이 생긴다. 가능한 모든 부호화 전략을 통틀어, 이 평면에서 도달할 수 있는 영역은 어디까지인가?

대부분은 그 경계가 원점을 지나는 선이라고 짐작한다. 오류를 극단적으로 줄이고 싶으면 속도를 극단적으로 포기해야 한다는 뜻이다. 클로드 섀넌은 1948년 논문 '통신의 수학적 이론'에서 이 짐작이 틀렸음을 보였다. 경계는 원점이 아니라 가로축의 특정 지점에서 꺾이며, 그 지점이 바로 채널 용량이다. 뒤집힘 확률이 0.1인 예에서 용량은 약 0.53이다.

이 결과의 힘은 예를 들어보면 분명해진다. 비트 오류 확률을 10의 마이너스 25제곱까지 낮추라는 무리한 요구를 해도, 섀넌의 답은 전송률 0.53까지는 그런 부호가 존재한다는 것이다. 다만 그 부호가 무엇인지는 알려주지 않는다. 발표자는 그 마법을 걷어내는 조건도 함께 짚는다. 부호화는 메시지를 크기 k의 덩어리로 잘라 크기 n으로 늘리는 방식이고, 전송률이 용량에 가까워지려면 n이 아주 커야 한다. 짧은 메시지에는 이 보장이 적용되지 않지만, 현실의 통신은 대개 긴 메시지를 다루기 때문에 문제가 되지 않는다.

주요 인사이트

• 이 정리가 특별한 이유는 '무엇이 가능한가'를 구성이 아니라 존재로 답했다는 데 있다. 방법을 몰라도 한계를 알 수 있다는 발상은 이후 공학이 목표를 설정하는 방식 자체를 바꿔놓았다.
• 직관과 정면으로 충돌한다는 점도 중요하다. 오류를 줄이려면 반복을 늘리고 그만큼 느려져야 한다는 경험은 반복 부호에서는 맞지만, 가능한 모든 부호를 놓고 보면 전혀 다른 그림이 나온다.
• 발표자가 강조하듯 이 결과는 특정 채널의 특수 사례가 아니다. 같은 논리가 여러 형태의 통신에 일반화되기 때문에, 오늘 우리가 내려받는 파일과 듣는 목소리가 망가진 물리 계층을 통과하고도 온전히 도착한다.
• 동시에 조건을 무시하면 오해하기 쉽다. 아주 긴 블록을 전제로 한 점근적 결과이므로, 짧고 지연에 민감한 통신에서는 그대로 기대할 수 없다는 단서가 함께 따라붙는다.
• 더 깊이 보고 싶은 사람을 위해 발표자는 고 데이비드 매케이의 교재와 공개 강의를 출처로 밝힌다. 영상 자체가 그 책 1장과 9·10장의 설명을 바탕으로 구성됐다.

자주 묻는 질문

관련 AI 소식