잡음 너머로

대서양 바닥의 케이블은 왜 신호를 뭉갰을까? 잡음이 있어도 오류 없이 보낼 수 있다는 섀넌의 정리와, 그 한계를 50년 동안 쫓은 부호들.

이 글의 처럼 점선이 그어진 숫자는 좌우로 끌 수 있고(키보드 ←/→도 됩니다), 색이 칠해진 같은 말은 눌러서 바꿀 수 있습니다. 밑줄 친 말에 마우스를 올리면 그림에서 그 부분이 빛납니다. 마지막 그림의 비트는 눌러서 뒤집을 수 있습니다. 휴대폰에서는 마우스를 올리는 대신 누르면 됩니다.

1858년 8월 16일, 영국의 빅토리아 여왕이 미국의 뷰캐넌 대통령에게 축하 전보를 보냈습니다. 아일랜드 서쪽 끝 발렌시아섬에서 뉴펀들랜드의 트리니티만까지 대서양 바닥에 깔린 첫 전신 케이블을 타고 간 전보였습니다. 배로 열흘 넘게 걸리던 소식이 하루 안에 바다를 건넜으니 두 대륙은 들떴습니다. 그런데 98낱말짜리 이 전보를 보내는 데 16시간이 걸렸습니다. 케이블은 그 뒤로도 느리고 불안정하게 732통의 전보를 실어 나르다가, 9월에 절연이 무너지며 완전히 끊어졌습니다. 개통한 지 한 달이 되지 않아서였습니다.

무엇이 문제였을까요? 케이블 끝에서 받은 신호는 보낸 신호와 모양이 달랐습니다. 또렷한 펄스를 보내도 반대편에는 흐릿하게 부풀어 서로 겹친 전류가 도착했습니다. 빨리 보낼수록 더 심하게 뭉개졌고, 받는 쪽의 계기는 바다 밑의 약한 전류와 땅에 흐르는 떠돌이 전류 사이에서 흔들렸습니다. 이 글의 질문은 이것입니다. 뭉개지고 잡음이 섞이는 통로로, 얼마나 빨리, 얼마나 믿을 만하게 보낼 수 있을까? 여기서 통로란 케이블이든 전화선이든 전파든, 신호가 보내는 쪽에서 받는 쪽으로 지나가는 길을 통틀어 부르는 말입니다.

「짧게 보내기」는 메시지에서 여분을 짜내는 이야기였습니다. 이 글은 그 반대편, 여분을 더해 메시지를 지키는 이야기입니다. 케이블의 물리에서 시작해 벨 연구소의 공학자들이 '정보'를 세기 시작한 과정을 따라가면, 1948년 클로드 섀넌의 결론에 닿습니다. 잡음이 있어도, 어떤 속도⁠(velocity)⁠보다 느리게만 보내면 메시지를 길게 묶어 부호화해서 오류를 얼마든지 줄일 수 있다는 것입니다. 마지막으로 그 약속을 실제로 지키는 부호를 찾아 반세기를 보낸 사람들의 이야기를 봅니다.

1 · 바다 밑의 케이블톰슨의 제곱 법칙⁠(law of squares)⁠과 뭉개지는 펄스

이 절의 물음은 이것입니다. 케이블은 왜 빨리 보낸 신호를 뭉갤까? 그리고 전압을 높이면 이것이 고쳐질까?

해저 케이블은 구리선을 구타페르카라는 나무 수지로 감싸고, 그 바깥을 쇠줄로 감은 것입니다. 바깥은 바닷물입니다. 1854년 글래스고 대학의 서른 살 교수 윌리엄 톰슨은 이 구조가 거대한 축전기⁠(capacitor)⁠라는 데 주목했습니다. 축전기는 전기가 통하지 않는 층을 사이에 둔 두 도체에 전하를 담아 두는 장치입니다. 구리 속심과 바닷물이 두 극판이고 구타페르카가 그 사이의 절연체입니다. 한쪽 끝에 전지를 대면 전류는 곧바로 반대편에 닿지 못하고, 먼저 가까운 곳부터 케이블을 '충전'하며 조금씩 스며 나갑니다.

톰슨은 이 스며듦이 막대를 따라 열이 퍼지는 것과 같은 방정식을 따른다는 것을 알아냈습니다. 반세기 전 푸리에가 풀어 둔 열방정식⁠(heat equation)⁠입니다. 쇠막대 한쪽 끝을 불에 대면 열은 곧장 반대편에 가지 않고, 가까운 곳부터 데우며 천천히 번져 갑니다. 한 점은 이웃보다 차가우면 데워지고 뜨거우면 식습니다. 케이블 속 전압도 똑같이 가까운 곳부터 '데우며' 번집니다.

톰슨은 그 풀이에서 공학자들을 당황하게 한 결론을 끌어냈습니다. 신호가 도착하는 데 걸리는 시간은 케이블의 저항(전류가 흐르기 어려운 정도)과 전기 용량(전하를 담는 능력)의 곱에 비례하는데, 둘 다 길이에 비례하니 늦어짐은 길이의 제곱에 비례한다는 것입니다. 케이블이 두 배 길어지면 저항도 두 배, 채워야 할 전하도 두 배이니, 같은 신호를 받는 데 2 × 2 = 4배의 시간이 듭니다. 흔히 신호가 늦는 것은 길이만큼 먼 길을 가기 때문이라고 생각하지만, 이 케이블에서는 길이에 비례해 늦는 것이 아니라 길이의 제곱에 비례해 늦습니다. 이 '제곱 법칙'은 1855년 왕립학회 회보에 실렸습니다.

대서양 전신 회사의 전기 기사 와일드먼 화이트하우스는 이 결론을 받아들이지 않았습니다. 외과 의사 출신인 그는 1856년 영국 과학진흥협회 모임에서, 제곱 법칙이 맞다면 대서양 전신은 가망이 없다며 자기 실험이 그 법칙을 뒤집는다고 주장했습니다. 톰슨은 화이트하우스의 측정값이 오히려 제곱 법칙과 잘 맞는다고 반박했고, 성공의 열쇠는 충분히 굵은 구리 속심에 있다고 답했습니다.

아래 그림은 톰슨의 모형으로 계산한 것입니다. 저항과 전기 용량⁠(capacity)⁠만 있는 케이블의 한쪽 끝에 +와 −의 펄스를 번갈아 보내고, 반대쪽 끝에서 받은 전류를 그렸습니다. 점선은 펄스 하나만 보냈을 때의 모양으로, 톰슨이 '도착 곡선⁠(arrival curve)⁠'이라 부른 것에서 나옵니다. 받는 쪽은 펄스마다 전류가 +인지 −인지를 읽습니다. 읽는 순간은 가장 잘 맞는 때로 골랐습니다(초록 점은 맞게, 빨간 점은 틀리게 읽은 곳). 케이블: , 신호 속도: 단위 시간에 펄스 개, 전압: 배. 볼 것은 두 가지입니다. 속도를 올릴 때 아래의 파란 선이 위의 +, − 모양을 얼마나 잃는지, 그리고 전압을 올리면 그것이 되돌아오는지입니다.

펄스 하나의 길이는 단위이고, 24개 가운데 개를 잘못 읽었습니다.

정리하면, 케이블은 펄스마다 긴 꼬리를 남겨서 빨리 보낼수록 꼬리들이 뒤의 펄스를 덮습니다. 이 뭉개짐은 신호의 모양 문제라서 전압을 키워도 사라지지 않고, 케이블이 길수록 길이의 제곱으로 심해집니다.

1858년 여름 케이블이 이어졌을 때 받는 신호는 몹시 약했습니다. 화이트하우스는 거대한 유도 코일로 수천 볼트의 전압을 걸어 신호를 밀어붙였습니다. 위 그림이 보여 주듯 전압은 뭉개짐을 고치지 못했고, 높은 전압은 이미 약해져 있던 절연을 더 망가뜨렸습니다. 화이트하우스는 해임되었습니다. 실패는 대서양에서만 일어나지 않았습니다. 1859–60년 수에즈에서 홍해를 따라 아덴을 거쳐 인도의 카라치까지 놓은 케이블도 한 줄로 제대로 이어져 작동한 적이 없이 끊겼습니다. 런던과 인도 사이에 편지 한 통이 오가는 데 몇 주씩 걸리던 때, 제국의 두 끝을 전신으로 잇겠다던 계획이 무너진 것입니다. 1859년 12월부터 영국 상무부와 대서양 전신 회사가 함께 꾸린 조사 위원회는 두 실패를 함께 따졌고, 1861년 대서양 케이블 실패의 책임 대부분이 화이트하우스에게 있다고 결론지었습니다. 위원회의 셈으로는 1851년부터 바다 밑에 놓인 케이블 1만 1천 해리 남짓 가운데 실제로 작동하는 것은 3천 해리가 되지 않았습니다.

약한 신호를 읽은 것은 톰슨의 발명품이었습니다. 거울 검류계⁠(mirror galvanometer)⁠는 작은 자석에 가벼운 거울을 붙여 실에 매단 것입니다. 전류가 조금만 흘러도 자석이 살짝 돌고, 거울에 반사된 빛줄기가 멀리 떨어진 눈금 위에서 크게 움직입니다. 받는 사람은 빛 점이 왼쪽으로 가는지 오른쪽으로 가는지를 읽었습니다. 위 그림의 +와 −가 바로 그것입니다. 구리 속심을 훨씬 굵게 하고 절연을 개선한 새 케이블은 1866년 거대한 증기선 그레이트이스턴호가 놓았고, 이번에는 제대로 작동했습니다. 톰슨은 그해 기사 작위를 받았고, 1892년 켈빈 남작이 되었습니다. 온도의 단위 켈빈이 이 이름에서 왔습니다.

이야기는 여기서 끝나지 않았습니다. 1880년대 영국의 독학한 전기공학자 올리버 헤비사이드는 톰슨의 모형에 코일처럼 전류의 변화에 저항하는 성질, 곧 인덕턴스⁠(inductance)⁠를 더했습니다. 그러면 방정식에 파동방정식⁠(wave equation)⁠의 성질이 섞입니다. 헤비사이드는 저항과 인덕턴스, 전기 용량, 그리고 절연체를 통해 새는 전류가 알맞은 비율을 이루면(저항 ÷ 인덕턴스 = 새는 정도 ÷ 전기 용량) 신호가 약해질 뿐 모양은 그대로 전해진다는 것을 보였습니다. 그는 이 조건을 1887년 무렵 발표했지만 특허를 내지 않았습니다. 20세기 초 장거리 전화선에 일정한 간격으로 코일을 단 것은 이 생각에서 나왔습니다. 1899–1900년 미국 컬럼비아 대학의 마이클 푸핀과 AT&T의 조지 캠벨이 코일을 몇 킬로미터마다 달아야 하는지 따로 계산해 같은 방법에 이르렀습니다. 특허는 푸핀에게 돌아갔고, AT&T는 소송 대신 그 권리를 사들였습니다. 이 '장하 코일⁠(loading coil)⁠'로 전화가 닿는 거리가 크게 늘었고, 선로를 수학으로 설계하는 공학자들이 전화 회사 안에 자리를 잡았습니다. 2절의 사람들이 그 자리에서 나옵니다. 그래도 한 가지는 변하지 않습니다. 어떤 선로든 너무 빨리 바뀌는 신호는 뭉개서 전합니다.

이것을 재는 말이 대역폭입니다. 어떤 신호든 여러 빠르기로 오르내리는 매끈한 물결(사인파⁠, sinusoid⁠)의 합으로 쪼갤 수 있고, 1초에 몇 번 오르내리는지를 진동수라 합니다. 모서리가 날카로운 펄스일수록 빠른 물결이 많이 들어 있습니다. 선로는 어느 빠르기까지의 물결만 제대로 통과시키고 그보다 빠른 물결은 깎아 버리는데, 그 통과시키는 진동수⁠(frequency)⁠의 폭이 대역폭입니다. 대역폭⁠(bandwidth)⁠에는 늘 한계가 있고, 빠른 물결이 깎인 펄스는 모서리가 무뎌진 채, 곧 뭉개진 채 도착합니다.

구타페르카는 말레이반도의 나무에서 얻는 수지로, 1840년대에 유럽에 알려졌습니다. 데우면 주물러 모양을 잡을 수 있고 식으면 단단해지며 바닷물 속에서도 삭지 않았습니다. 덕분에 처음으로 물 밑에 전선을 깔 수 있게 되었습니다. 1851년 도버와 칼레 사이의 해협 케이블이 제대로 작동하자 더 긴 케이블들이 뒤따랐고, 그와 함께 이상한 현상이 보고되었습니다. 구타페르카 회사를 위해 실험하던 기술자 래티머 클라크는 물에 잠긴 전선이 물 밖의 전선보다 신호를 눈에 띄게 늦게 전한다는 것을 보았습니다. 1854년 1월 마이클 패러데이는 왕립연구소 강연에서, 물에 잠긴 전선이 전하를 담는 병처럼 먼저 충전되어야 하기 때문이라고 설명했습니다. 톰슨은 그해 케임브리지의 수학자 조지 가브리엘 스토크스와 편지를 주고받으며 이 설명을 식으로 옮겼습니다.

케이블이 하필 아일랜드 서쪽 끝과 뉴펀들랜드 사이로 간 데에는 바다 밑의 지형도 한몫했습니다. 미국 해군의 해양학자 매슈 모리는 여러 배가 줄에 추를 달아 내려 잰 바다의 깊이 기록을 모아 해저 지도를 그렸고, 두 땅 사이의 바닥이 케이블을 놓기에 알맞게 고르다며 그곳을 '전신 고원'이라 불렀습니다. 그의 지도로는 미국 본토로 곧장 가는 길은 바닥이 험하고 훨씬 길었습니다. 케이블은 먼 숲⁠(forest)⁠에도 흔적을 남겼습니다. 구타페르카는 35년 넘게 자란 나무라야 수지를 얻을 만했고, 줄기에 구멍을 내기보다 나무를 통째로 베어야 수지가 많이 나왔습니다. 케이블 수요가 늘자 이런 채취가 이어져 19세기 동안 공급이 무너질 만큼 나무가 줄었습니다.

케이블과 전화의 시대. 글래스고의 이론이 발렌시아와 트리니티만 사이의 바다 밑으로 가는 길(주황)과, 20세기의 뉴욕에서 벨 시스템의 공학자들이 전신과 전화의 속도를 수로 따지기 시작한 것을 보세요.

2 · 몇 단계를 알아볼까나이퀴스트, 하틀리, 그리고 열잡음⁠(thermal noise)⁠

이 절의 물음은 이것입니다. 대역폭이 정해진 선로로 1초에 몇 비트를 보낼 수 있을까? 펄스의 수와 펄스 하나에 싣는 양, 두 가지로 나누어 봅니다.

20세기 초 미국의 전화망은 AT&T와 그 연구 조직, 1925년부터는 뉴욕의 벨 전화 연구소가 이끌었습니다. 1924년 AT&T의 해리 나이퀴스트는 『벨 시스템 기술 저널』에 「전신 속도에 영향을 주는 몇 가지 요인」을 실었습니다. 그가 따진 것은 모스 부호처럼 전류를 켜고 끄는 신호를 한 선으로 얼마나 빨리 보낼 수 있는지, 그리고 전류의 세기를 몇 단계로 나누면 무엇이 나아지는지였습니다. 스웨덴에서 태어나 열여덟 살에 미국으로 건너온 그는 1928년의 논문에서 이것을 정확한 문장으로 만들었습니다. 대역폭이 $B$헤르츠인 통로로는 1초에 서로 독립⁠(independence)⁠인 펄스를 $2B$개까지만 보낼 수 있다. 헤르츠는 1초에 몇 번 진동하는지를 세는 단위입니다. 그보다 빨리 보내면 1절의 그림처럼 펄스들이 서로를 덮습니다. 예를 들어 대역폭이 3,000헤르츠인 전화선이면 1초에 6,000개까지입니다. 대략의 까닭은 이렇습니다. 이 선로를 지난 신호는 1초에 3,000번보다 빨리 오르내리지 못하는데, 한 번 오르내릴 때마다 마루 하나와 골 하나, 곧 서로 다른 값 두 개를 실을 수 있습니다.

그렇다면 1초에 보낼 수 있는 정보는 펄스의 수만으로 정해질까요? 같은 1928년, 같은 저널에 벨 연구소의 공학자 랠프 하틀리가 「정보의 전송」을 실었습니다. 1927년 9월 이탈리아 코모 호숫가에서 열린 국제 전신·전화 학회에서 먼저 발표한 글입니다. 하틀리는 우선 '정보'에서 뜻이나 심리적인 요소를 걷어 내자고 했습니다. 받는 사람에게 중요한 것은 보낸 사람이 가능한 여러 메시지 가운데 어느 것을 골랐는가입니다. 기호가 $s$가지이고 $n$개를 보낸다면 가능한 메시지는 $s^n$가지($s$를 $n$번 곱한 수)입니다. 기호가 +와 − 두 가지이고 세 개를 보내면 +++, ++−, …, −−−의 2 × 2 × 2 = 8가지입니다.

하틀리는 정보를 이 수의 로그, 곧 $n \log s$로 재자고 했습니다. 로그는 곱셈을 덧셈으로 바꾸는 함수입니다. 밑이 2인 로그 $\log_2 x$는 '2를 몇 번 곱해야 $x$가 되는가'이고, 그래서 $\log_2 8 = 3$입니다. 위의 여덟 가지 메시지는 3비트, 곧 예/아니요 물음 세 개로 가려낼 수 있는 양입니다. 로그를 쓰면 메시지 길이가 두 배일 때 정보도 두 배가 됩니다. 여섯 개를 보내면 메시지는 $8 \times 8 = 64$가지이고 $\log_2 64 = 6$비트이니까요.

이제 두 사람의 결과를 합치면 이렇습니다. 펄스마다 $M$가지 전압 수준 가운데 하나를 고를 수 있다면 펄스 하나가 $\log_2 M$비트를 싣고, 1초에 펄스가 $2B$개이니 1초에 $2B \log_2 M$비트를 보낼 수 있습니다. 수준을 두 가지(+와 −)가 아니라 16가지로 나누면 펄스 하나가 $\log_2 16 = 4$비트를 싣습니다. 3,000헤르츠 전화선이라면 1초에 6,000 × 4 = 24,000비트입니다. 그러면 수준을 한없이 잘게 나누면 한없이 많이 보낼 수 있을까요? 하틀리는 그렇지 않다고 보았습니다. 받는 쪽이 알아볼 수 있는 수준의 수는 신호의 세기와 수신기의 정밀도⁠(precision)⁠로 정해진다는 것입니다.

무엇이 정밀도를 막는지는 같은 해에 밝혀졌습니다. 벨 연구소의 물리학자 존 B. 존슨은 나이퀴스트처럼 스웨덴에서 태어나 미국으로 건너온 사람입니다. 그는 아무것도 연결하지 않은 저항기에서도 요동 전압이 나오고, 그 세기가 온도에 따라 커진다는 것을 측정했습니다. 이론은 나이퀴스트가 세웠습니다. 저항기 속 전자들이 열 때문에 쉬지 않고 흔들리니, 이 열잡음은 온도가 절대 영도(섭씨 −273.15도, 더 내려갈 수 없는 가장 낮은 온도)가 아닌 한 피할 수 없습니다. 그 세기는 온도와 대역폭에 비례합니다. 수많은 전자의 작은 떨림이 더해진 것이므로, 중심극한정리⁠(central limit theorem)⁠대로 정규분포⁠(normal distribution)⁠를 따릅니다.

그림에서 직접 세어 봅시다. −1과 +1 사이에 전압 수준 가지를 고르게 놓고, 펄스마다 그 가운데 하나를 무작위로 골라 보냅니다. 받은 전압에는 표준편차⁠(standard deviation)⁠가 인 정규분포 잡음이 섞입니다. 표준편차는 값이 평균⁠(mean)⁠에서 얼마나 흩어지는지를 재는 수로, 정규분포에서는 값의 약 68%가 평균에서 표준편차 하나 안쪽에 떨어집니다. 받는 쪽은 수준 사이의 한가운데를 경계로 가장 가까운 수준으로 읽습니다. 볼 것은 오른쪽 그림에서 수준마다 생긴 봉우리의 폭이 수준 사이의 간격과 견주어 얼마나 넓은가입니다.

펄스 하나는 비트를 실으려 하지만, 잘못 읽을 확률⁠(probability)⁠이 입니다(그림의 140개 가운데 개). 틀린 것까지 감안해서 받는 쪽이 실제로 알게 되는 정보를 4절에서 만들 자로 재면 펄스 하나에 비트입니다.

정리하면, 1초에 보낼 수 있는 비트는 (1초의 펄스 수 $2B$) × (펄스 하나에 싣는 비트)이고, 뒤의 것은 잡음이 허락하는 만큼만, 그것도 신호 세기의 로그로만 늘어납니다.

하틀리의 셈에는 빈틈이 있었습니다. '알아볼 수 있는 수준'은 딱 떨어지는 수가 아닙니다. 봉우리들은 조금씩 겹치고, 오류는 드물어질 뿐 0이 되지 않습니다. 오류가 조금 있는 통로는 얼마만큼의 정보를 나르는 걸까요? 이 질문에 답하려면 오류 자체를 정보로 재야 했고, 그것이 20년 뒤 섀넌이 한 일입니다.

3 · 파동을 수로표본화 정리⁠(sampling theorem)⁠와 되살아나는 펄스

이 절의 물음은 이것입니다. 소리처럼 끊김 없이 이어지는 파동을, 띄엄띄엄 잰 수 몇 개로 남김없이 담을 수 있을까? 담을 수 있다면 모든 신호를 비트로 바꿔 보낼 수 있습니다.

나이퀴스트의 $2B$를 거꾸로 읽으면 또 하나의 사실이 나옵니다. 진동수가 $B$헤르츠보다 높은 성분이 없는 신호는 1초에 $2B$번보다 자주 잰 값만으로 완전히 정해진다. 점과 점 사이를 어떻게 이어야 하는지가 이미 정해져 있다는 것입니다. 점들 사이로 다른 곡선을 그으려면 어딘가에서 더 빨리 오르내려야 하는데, 그런 빠른 성분은 없다고 했으니까요. 다만 이렇게 되살리려면 과거와 미래의 모든 잰 값이 필요해서, 실제 장비는 유한한 개수로 어림합니다. 이 표본화 정리는 여러 사람이 따로 찾았습니다. 1915년 에든버러의 수학자 E. T. 휘태커가 점들 사이의 값을 채워 넣는 보간 공식⁠(interpolation formula)⁠을 연구했고, 1933년 소련의 공학자 블라디미르 코텔니코프가 통신 공학의 언어로 증명했습니다. 섀넌은 1949년 논문에서 이것을 통신 이론의 출발점으로 삼았습니다.

조건을 어기면 어떻게 되는지 봅시다. 1초에 10번 재는데, 파동의 진동수는 헤르츠입니다. 노란 점이 잰 값이고, 파란 선이 원래 파동입니다. 1초에 10번 재니 나이퀴스트의 말대로라면 5헤르츠보다 낮으면 괜찮아야 합니다. 진동수를 5 위아래로 끌며 분홍 점선이 나타나는지 보세요.

진동수를 10헤르츠로 맞추면 점들이 모두 같은 높이에 찍혀 파동이 멈춘 것처럼 보이고, 9헤르츠면 1헤르츠로 느리게 도는 가짜 파동이 됩니다. 두 번 잰 사이의 0.1초 동안 9헤르츠 파동은 0.9바퀴를 돕니다. 한 바퀴에서 0.1바퀴 모자란 만큼이니, 점만 보면 거꾸로 0.1바퀴씩, 곧 1초에 1바퀴씩 도는 파동과 구별되지 않습니다. 영화 속 마차 바퀴가 거꾸로 도는 것처럼 보이는 것도 같은 현상입니다. 그래서 음악 CD는 1초에 44,100번 소리를 잽니다. 사람이 듣는 가장 높은 소리(약 20,000헤르츠)의 두 배가 넘는 횟수입니다. 그리고 재기 전에 그보다 높은 성분을 걸러 냅니다. 파동을 사인파들의 합으로 보는 눈은 「원에서 파동으로」의 푸리에 급수⁠(Fourier series)⁠에서 옵니다.

잰 값을 다시 몇 단계의 수로 반올림하면, 소리는 수의 목록이 되고 그림은 수를 가로세로로 늘어놓은 표(행렬⁠, matrix⁠)가 되니, 결국 모두 비트가 됩니다. 1937년 파리의 ITT 연구소에 있던 영국 공학자 앨릭 리브스는 소리를 이렇게 표본으로 뜨고 반올림해서 펄스의 줄로 보내는 펄스 부호 변조(PCM)를 고안했습니다. 왜 굳이 그렇게 할까요? 아날로그 신호는 먼 길을 가며 여러 번 증폭해야 하는데, 증폭기는 신호와 함께 잡음도 키우니 잡음이 중계소마다 쌓입니다. 펄스는 다릅니다. 중계소는 "이것이 +인가 −인가"만 판단해 깨끗한 새 펄스를 만들어 보내면 됩니다. 판단이 틀리지 않는 한 잡음은 중계소에서 매번 지워집니다. 전기 신호로 여닫는 작은 전자 스위치인 트랜지스터⁠(transistor)⁠가 이 판단을 싸게 만들어 주었고, 1962년 벨 시스템은 전화 통화를 펄스로 나르는 T1 전송 방식을 쓰기 시작했습니다.

목소리를 수로 바꾸어 보낸 첫 실제 체계는 전쟁이 만들었습니다. 벨 연구소가 만든 비화 전화(엿들어도 알아들을 수 없게 만든 전화) SIGSALY는 1943년부터 워싱턴과 런던 사이의 최고위급 통화를 날랐습니다. 목소리를 잘게 나눈 대역마다 세기를 몇 단계의 수로 반올림했습니다. 그리고 똑같은 무작위 잡음을 새긴 레코드판 두 장을 양쪽 끝에 두고, 보내는 쪽은 그 잡음을 더하고 받는 쪽은 뺐습니다. 한 번만 쓰는 무작위 열쇠, 곧 일회용 난수표⁠(one-time pad)⁠를 목소리에 쓴 셈입니다. 1943년 1월 영국의 앨런 튜링이 이 체계를 점검하러 뉴욕의 벨 연구소에 와서 두어 달을 머물렀습니다. 섀넌의 회고에 따르면 두 사람은 구내식당에서 자주 만났지만, 암호 일은 서로 말할 수 없어서 생각하는 기계를 두고 이야기했다고 합니다. 일회용 난수표가 왜 완전히 안전한지는 섀넌이 전쟁 뒤에 증명했습니다(8절). 1917년 버냄이 만든 전신 암호 기계가 일회용 난수표로 자란 이야기와 그 증명의 요지는 「나머지로 지키는 비밀」 7절에 있습니다.

이제 문제는 하나로 모였습니다. 모든 것을 비트로 바꿀 수 있다면, 남는 질문은 잡음이 비트를 뒤집는 통로로 비트를 얼마나 빨리, 얼마나 믿을 만하게 보낼 수 있는가입니다.

4 · 잡음의 값섀넌의 통로와 상호 정보량⁠(mutual information)⁠

이 절의 물음은 이것입니다. 비트가 가끔 뒤집히는 통로는 비트 하나당 정보를 정확히 얼마나 나를까? '100개 중 1개가 틀리니 99%'라는 답은 왜 틀릴까?

클로드 섀넌은 1941년 벨 연구소에 들어와, 전쟁 동안 대공포의 조준 장치와 암호를 연구했습니다. 1945년 그가 쓴 기밀 보고서 「암호의 수학적 이론」은 전쟁이 끝난 뒤 다듬어져 1949년 「비밀 체계의 통신 이론」으로 나왔습니다. 이 논문이 보인 '완전한 비밀'의 조건은 「나머지로 지키는 비밀」 7절에서 볼 수 있습니다. 그 사이 1948년 7월과 10월, 『벨 시스템 기술 저널』에 「통신의 수학적 이론」이 실렸습니다. 논문의 첫 문장은 이렇게 시작합니다. "통신의 근본 문제는 한 지점에서 고른 메시지를 다른 지점에서 정확히, 또는 비슷하게 재현하는 것이다."

섀넌은 모든 통신을 한 장의 그림으로 그렸습니다. 정보원이 메시지를 고르고, 송신기가 그것을 신호로 바꿉니다. 신호는 통로를 지나며 잡음원이 섞는 잡음을 만나고, 수신기는 받은 신호에서 메시지를 되살려 목적지에 건넵니다. 전신이든 라디오든 사람의 말이든 이 틀에 들어갑니다. 메시지에 든 정보의 양, 곧 엔트로피⁠(entropy)⁠와 압축의 한계는 「짧게 보내기」에서 보았습니다. 이 글은 그림의 가운데, 잡음이 있는 통로를 봅니다.

가장 단순한 통로를 생각합시다. 0이나 1을 보내면, 비트마다 확률 $q$로 뒤집혀 도착하고 $1-q$로 그대로 도착합니다. 0과 1이 똑같이 당하니 이진 대칭 통로⁠(binary symmetric channel)⁠라고 부릅니다. 섀넌 논문의 첫 문장을 32가지 기호(글자 26개, 공백, 문장 부호 5개)마다 5비트로 적어, 뒤집힐 확률이 $q =$ 인 통로로 보냅니다. 볼 것은 받은 글이 얼마나 망가지는지, 그리고 오른쪽 그림에서 $q$에 따라 두 곡선이 어떻게 갈리는지입니다. ↻ 다시 보내기

글자 몇 개가 틀려도 사람은 문맥으로 읽어 냅니다. 영어 글에는 여분이 많기 때문입니다. 하지만 압축해서 여분을 짜낸 메시지라면 비트 하나하나가 소중합니다. 그렇다면 이 통로는 비트 하나당 정보를 얼마나 나를까요?

섀넌은 논문에서 이런 예를 들었습니다. 1초에 1,000비트를 보내는데 평균 100개 중 1개가 틀린다면, 초당 990비트의 정보가 전해진다고 말하고 싶어집니다. 섀넌은 그렇지 않다고 했습니다. 받는 쪽은 어느 비트가 틀렸는지 모르기 때문입니다. 받은 비트 하나를 보고도 남는 불확실성은 확률 0.01로 뒤집혔는가 하는 물음의 엔트로피입니다.

엔트로피는 결과를 알기 전의 불확실성을 비트로 잰 양입니다. 확률 $p$인 일이 일어났다는 소식은 $-\log_2 p$비트의 '놀람'을 줍니다. 확률 1/2이면 1비트, 1/4이면 2비트, 드문 일일수록 큽니다. 엔트로피는 이 놀람을 확률로 평균한 것입니다. 확률 $q$로 일어나고 $1-q$로 일어나지 않는 일의 엔트로피를 $H(q) = -q\log_2 q - (1-q)\log_2(1-q)$로 적습니다. 동전 던지기($q = 1/2$)면 정확히 1비트입니다.

$q = 0.01$이면 뒤집혔다는 소식의 놀람은 $-\log_2 0.01 \approx 6.64$비트, 그대로라는 소식은 $-\log_2 0.99 \approx 0.0145$비트이니, 평균은 0.01 × 6.64 + 0.99 × 0.0145 ≈ 0.066 + 0.014 = 0.081비트입니다. 곧 $H(0.01) \approx 0.081$비트입니다. 그러니 1초에 81비트어치는 모르는 채로 남고, 실제로 전해지는 정보는 초당 1,000 − 81 = 919비트입니다. 틀린 비트 10개만 빼는 것보다 훨씬 많이 잃습니다. 받는 쪽은 틀린 10개를 잃을 뿐 아니라, 맞은 990개도 '맞았는지' 확신할 수 없기 때문입니다.

일반적으로, 받은 것 $Y$를 보고도 보낸 것 $X$에 관해 여전히 모르는 양이 조건부 엔트로피⁠(conditional entropy)⁠ $H(X \mid Y)$('$Y$를 알 때 $X$의 엔트로피')이고, 전해진 정보는 보내기 전의 불확실성 $H(X)$에서 그것을 뺀 것입니다. 위의 예에 대면 보내기 전 1비트, 받은 뒤에도 남는 0.081비트, 전해진 것은 그 차 0.919비트입니다.

이 양을 상호 정보량이라고 합니다. $Y$를 알게 되어 $X$에 관한 불확실성이 줄어든 만큼이고, 거꾸로 $H(Y) - H(Y \mid X)$로 셈해도 같습니다. 이진 대칭 통로에 0과 1을 반반씩 넣으면 $H(X) = 1$, $H(X \mid Y) = H(q)$이니, 지금 잃는 정보는 비트당 비트이고 남는 정보는 비트입니다. 초당 1,000비트를 보내면 비트어치가 전해집니다. 넣는 비트의 비율을 어떻게 바꿔도 이보다 커지지 않으니, 이것이 이 통로의 통로 용량⁠(channel capacity)⁠입니다. 아래 식의 $\max_{p(x)}$는 '보내는 기호의 확률 분포 $p(x)$를 가장 좋게 골랐을 때'라는 뜻입니다.

상호 정보량은 두 확률변수(보낸 비트, 받은 비트처럼 확률에 따라 값이 정해지는 양)가 서로에 대해 얼마나 알려 주는지를 재는 일반적인 자입니다. 두 변수의 값이 함께 나올 확률 전체(결합 분포⁠, joint distribution⁠)가, 두 변수가 서로 독립이었다면 나왔을 분포와 얼마나 다른지를 재는 쿨백–라이블러 발산⁠(Kullback–Leibler divergence)⁠으로 쓸 수도 있습니다. 2절의 전압 수준 그림에서 '실제로 전해지는 정보'도 이 자로 잰 것입니다.

정리하면, 잡음 있는 통로가 비트 하나당 나르는 정보는 '보내기 전의 불확실성 − 받은 뒤에도 남는 불확실성'이고, 이진 대칭 통로에서는 $1 - H(q)$입니다. $q$가 작을 때는 틀린 비트의 비율 $q$보다 잃는 양 $H(q)$가 훨씬 큽니다(0.01과 0.081).

같은 1948년, MIT의 노버트 위너는 『사이버네틱스⁠(cybernetics)⁠』를 냈습니다. 위너는 전쟁 중 대공포 조준 장치를 위해, 잡음 섞인 레이더 신호에서 비행기가 몇 초 뒤 어디에 있을지 예측하는 필터⁠(filter)⁠를 연구했습니다. 그 역시 정보를 확률과 엔트로피로 재고 있었습니다. 섀넌은 논문에서 통신 이론의 기본 철학과 이론의 많은 부분을 위너에게 빚졌다고 적었습니다. 두 사람의 차이는 초점에 있었습니다. 위너는 이미 섞인 잡음을 걸러 내 신호를 가장 잘 짐작하는 쪽을, 섀넌은 보내기 전에 메시지를 부호로 바꾸어 잡음을 이기는 쪽을 보았습니다. 섀넌의 논문은 이듬해 록펠러 재단의 수학자 워런 위버가 쓴 쉬운 해설과 함께 『통신의 수학적 이론』이라는 책으로 다시 나왔습니다.

섀넌의 정보에는 뜻이 들어 있지 않습니다. 섀넌은 1948년 논문 첫머리에서, 메시지에는 흔히 뜻이 있지만 통신의 이런 의미의 측면은 공학의 문제와 상관이 없다고 못 박았습니다. 받는 쪽에 중요한 것은 가능한 메시지 가운데 어느 것이 골라졌는가뿐이라는 2절 하틀리의 생각을 이은 것입니다. 위버는 책의 해설에서 통신의 문제를 세 층으로 나누었습니다. 기호를 정확히 옮기는 기술의 문제, 기호가 뜻을 정확히 전하는가 하는 의미의 문제, 전해진 뜻이 받는 사람의 행동을 바라는 대로 바꾸는가 하는 효과의 문제입니다. 섀넌의 이론은 첫째 층의 이론입니다. 둘째 층을 재 보려는 시도도 있었습니다. 1952년 철학자 루돌프 카르나프와 예호슈아 바르힐렐은 한 문장이 일어날 수 있는 세계들 가운데 얼마나 많은 것을 배제하는지로 '의미 정보'를 쟀습니다. 그런데 이 자로 재면 모든 세계를 배제하는 모순된 문장이 가장 많은 정보를 품게 됩니다. 두 사람은 이런 문장이 참이기에는 너무 많은 것을 말한다고 적었습니다. 섀넌 자신은 정보 이론이 생물학, 심리학, 경제학으로 너무 쉽게 번지는 것을 경계했습니다. 1956년의 짧은 사설 「밴드왜건」에서 그는 정보 이론이 과학계의 유행이 되었다고 꼬집고, 철저하게 과학적인 태도를 지킬 때에만 진전이 있다고 적었습니다.

5 · 더 여러 번 보내면반복 부호⁠(repetition code)⁠와 섀넌의 약속

이 절의 물음은 이것입니다. 오류를 한없이 줄이려면 속도도 한없이 느려져야 할까? 용량이 있다는 것은 알았습니다. 그런데 초당 919비트라는 말은 무슨 뜻일까요? 받은 글은 여전히 100개에 1개꼴로 틀려 있습니다. 틀리지 않게 하려면 무언가를 덧붙여야 합니다. 가장 먼저 떠오르는 방법은 같은 비트를 여러 번 보내고 받는 쪽에서 다수결로 읽는 것입니다. 세 번 보내면 셋 가운데 둘 이상이 뒤집혀야 틀립니다. $q = 0.1$일 때 정확히 둘이 뒤집히는 경우는 어느 둘인지 3가지이고 각각 확률이 0.1 × 0.1 × 0.9 = 0.009이니 합이 0.027, 셋 다 뒤집힐 확률이 0.001이어서, 오류가 10%에서 0.028, 곧 2.8%로 줄어듭니다. 대신 보낸 비트 가운데 진짜 정보의 비율, 곧 부호율⁠(code rate)⁠이 1/3로 떨어집니다. 부호율은 보통 $R$로 적습니다. 데이터 4비트에 검사 비트⁠(check bit)⁠ 3비트를 붙여 7비트를 보내면 $R = 4/7$입니다.

아래 왼쪽 그림의 가로축은 부호율, 세로축은 받는 쪽이 되살린 데이터 비트가 틀릴 확률입니다(세로축은 칸마다 10배씩 줄어듭니다). 볼 것은 점들이 부호율을 너무 많이 잃지 않고 아래로 내려갈 수 있는가입니다. 노란 점들이 1번, 3번, 5번, …, 61번 반복하는 반복 부호이고, 보라색 점이 오류 정정 부호⁠(error-correcting code)⁠의 고전인 해밍 부호⁠(Hamming code)⁠입니다. 통로의 $q =$ , 반복 횟수 번.

번 반복하면 부호율은 이고 오류율은 입니다. 해밍 (7,4) 부호는 부호율 4/7에서 입니다. 반복 부호로 . 반복 부호의 점들은 왼쪽 아래 구석, 부호율 0을 향해서만 내려갑니다. 1948년까지 공학자들은 이것을 자연스럽게 여겼습니다. 믿을 만하게 보내려면 느려질 수밖에 없고, 오류를 0으로 만들려면 속도도 0이 되어야 한다고 말입니다.

섀넌의 통로 부호화 정리⁠(noisy-channel coding theorem)⁠는 이 믿음을 뒤집었습니다.

화살표 ⟹는 '이면'으로 읽습니다. '부호율 $R$이 용량 $C$보다 작으면, 오류 확률을 원하는 만큼 작게 하는 부호가 있다'는 문장입니다.

부호율이 용량 $C =$ 보다 작기만 하면, 충분히 긴 부호를 써서 오류 확률을 100만분의 1이든 10억분의 1이든 원하는 만큼 낮출 수 있습니다. 거꾸로 부호율이 $C$보다 크면 어떤 부호도 오류를 초록 곡선 아래로 낮출 수 없습니다. 그래서 도달 가능한 영역은 $C$에서 수직 벽처럼 바닥까지 뚫려 있습니다. 반복 부호가 기어가는 구석과는 전혀 다른 모양입니다. 잡음은 속도의 상한⁠(upper bound)⁠을 정할 뿐, 신뢰도의 상한을 정하지 않습니다. 다만 정리가 약속하는 것은 '그런 부호가 있다'는 것과 '길이가 충분히 길면'이라는 조건이어서, 오류를 줄일수록 부호가 길어지고 한 덩어리를 다 받은 뒤에야 풀 수 있으니 기다리는 시간이 늘어납니다. 그 대가는 속도가 아니라 지연으로 치릅니다.

어떻게 이것이 가능할까요? 열쇠는 긴 덩어리에 있습니다. 비트 하나에서는 뒤집힐지 말지가 운에 달렸지만, 비트 $n =$ 개를 한 덩어리로 보내면 뒤집히는 개수는 이항분포($n$번 가운데 몇 번 일어나는지의 확률 분포)를 따르고, $n$이 커질수록 그 비율이 $q$ 근처에 몰립니다. 평균 개가 뒤집히고, 비율이 $q$에서 0.03 안쪽에 들 확률은 입니다. 큰 수의 법칙⁠(law of large numbers)⁠입니다. 잡음은 하나하나는 예측할 수 없어도, 모아 놓으면 거의 정확히 예측할 수 있습니다.

이제 셈을 해 봅시다. 길이 $n$인 부호어⁠(codeword)⁠ 하나를 보내면, 받은 말은 거의 틀림없이 약 $nq$비트가 다른 말들 가운데 하나입니다. 그런 말의 수는 $n$자리 가운데 뒤집힐 $nq$자리를 고르는 방법의 수, 곧 이항계수⁠(binomial coefficient)⁠ $\binom{n}{nq}$이고, 큰 수의 팩토리얼⁠(factorial)⁠을 어림하는 스털링 공식⁠(Stirling's formula)⁠으로 계산하면 대략 $2^{nH(q)}$개입니다. 여기서 '대략'은 2의 몇 제곱인지, 곧 지수가 비트당 $H(q)$에 가까워진다는 뜻입니다. $q = 0.1$이면 $H(0.1) \approx 0.469$이고, $\log_2 \binom{n}{nq}$를 $n$으로 나눈 값은 $n = 100$일 때 0.440, 1,000일 때 0.464, 10,000일 때 0.468로 다가갑니다. 부호어마다 자기 둘레에 이만큼의 '잡음 공'을 차지하는 셈입니다. 받는 쪽이 헷갈리지 않으려면 공들이 겹치지 않아야 하는데, 길이 $n$인 비트열은 모두 $2^n$개뿐입니다. 전체 개수를 공 하나의 크기로 나눈 만큼보다 많은 공을 겹치지 않게 넣을 수는 없으니, 부호어는 많아야

개입니다($2^a \div 2^b = 2^{a-b}$). 부호어가 이만큼 있으면 그 가운데 하나를 골라 보내는 것으로 $n(1-H(q))$비트, 곧 보내는 비트 하나당 $1 - H(q)$비트를 실을 수 있습니다. 이 셈은 넘을 수 없는 상한의 뼈대입니다. 공이 조금 겹쳐도 되는 경우까지 따지는 엄밀한 증명도 같은 결론을 줍니다. 그 상한에 실제로 다가갈 수 있음을 보인 것이 아래에서 볼 섀넌의 논증입니다. 받은 말을 가장 가까운 부호어로, 곧 해밍 거리(두 비트열에서 서로 다른 자리의 수)가 가장 작은 부호어로 읽는 것은, $q$가 1/2보다 작고 부호어들이 똑같은 확률로 쓰일 때 베이즈 정리⁠(Bayes' theorem)⁠로 보면 가장 그럴듯한 부호어를 고르는 일입니다.

남은 문제는 공들을 실제로 겹치지 않게 배치하는 것입니다. 섀넌의 해법은 대담했습니다. 부호어를 무작위로 고르는 것입니다. 무작위로 고른 부호들의 평균 오류 확률을 계산해 보니, 부호율이 용량보다 작으면 길이가 늘수록 평균이 0으로 갑니다. 평균이 작으면 오류 확률이 평균 이하인 부호가 적어도 하나는 있습니다. 모든 부호가 평균보다 나쁘다면 평균도 평균보다 나빠야 하니 말이 되지 않습니다. 좋은 부호를 직접 만들지 않고, 무작위로 고른 것이 평균적으로 좋다는 사실로 존재를 보이는 논법입니다. 한 해 앞서 1947년 에르되시가 램지 수⁠(Ramsey number)⁠에 쓴 확률적 방법⁠(probabilistic method)⁠과 같은 생각입니다(「완전한 무질서는 없다」).

그러나 이 증명은 약속일 뿐 설계도가 아니었습니다. 무작위 부호는 부호어의 목록을 통째로 적어 두어야 하고, 길이가 1,000이고 부호율이 1/2인 부호라면 목록에 부호어가 $2^{500}$개나 됩니다. 받는 쪽이 가장 가까운 부호어를 찾으려면 그 목록을 다 뒤져야 합니다. 쓸 수 있는 부호, 곧 규칙이 있어서 빨리 만들고 빨리 풀 수 있는 부호로 용량에 다가가는 일이 7절의 50년이 됩니다.

정리하면, 긴 덩어리에서는 뒤집히는 비율이 거의 정확히 $q$이므로 부호어마다 약 $2^{nH(q)}$개짜리 잡음 공이 생기고, 그 공들을 겹치지 않게 넣을 수 있는 한 비트당 $1 - H(q)$까지 오류 없이 보낼 수 있습니다.

수학자들이 이 정리를 처음부터 반긴 것은 아닙니다. 미국 확률론의 대표 격이던 조지프 둡은 1949년 『수학 리뷰』의 서평에서 이 논문의 논의가 "처음부터 끝까지 수학적이라기보다 암시적이며, 저자의 수학적 의도가 늘 떳떳한지도 분명하지 않다"고 적었습니다. 섀넌 자신도 논문에, 극한⁠(limit)⁠을 다루며 때때로 자유를 누렸지만 실제로 관심 있는 모든 경우에는 정당화될 수 있다고 적어 두었습니다. 빈틈은 몇 해 안에 메워졌습니다. 1954년 MIT의 아미엘 파인스타인이 통로 부호화 정리의 엄밀한 증명을 내놓았고, 1957년 코넬 대학의 제이컵 울포위츠는 부호율이 용량을 넘으면 오류 확률이 0으로 갈 수 없을 뿐 아니라 1로 간다는 더 강한 역정리⁠(strong converse)⁠를 증명했습니다. 모스크바에서는 알렉산드르 힌친과 콜모고로프가 1950년대에 섀넌의 이론을 엄밀한 확률론의 언어로 옮겼습니다.

6 · 잡음의 구름부호의 기하학과 섀넌–하틀리 정리⁠(Shannon–Hartley theorem)⁠

이 절의 물음은 이것입니다. 비트가 아니라 전압처럼 연속된 값을 보내고 잡음도 정규분포일 때, 용량은 대역폭과 신호 세기로 어떻게 적힐까? 답은 5절의 '공 세기'를 공간의 부피로 다시 하는 데서 나옵니다.

섀넌은 1949년 1월 무선 공학자들의 학술지에 실은 「잡음이 있을 때의 통신」에서 같은 생각을 그림으로 보였습니다. 3절의 표본화 정리에 따르면 대역폭 $B$, 길이 $T$초인 신호는 대략 수 $2BT$개로 정해집니다($T$가 길수록 이 어림이 정확해집니다). 대역폭 3,000헤르츠로 1초 보내는 신호라면 수 6,000개입니다. 평면의 점이 좌표 두 개로 정해지듯, 수 6,000개로 정해지는 것은 6,000차원 공간의 점 하나로 볼 수 있습니다. 그러니 신호 하나는 $2BT$차원 공간의 점 하나입니다. 보내는 쪽은 미리 정해 둔 점 가운데 하나를 보내고, 잡음은 그 점을 흐릿한 구름으로 흩어 놓습니다. 받는 쪽은 받은 점이 어느 부호어의 구름에 속하는지 가립니다.

두 차원이면 직접 볼 수 있습니다. 평면에 부호어 점 를 격자로 놓고(평균 세기는 늘 같게), 각 방향으로 정규분포 잡음을 더해 600번 보냅니다. 신호 세기를 잡음 세기로 나눈 신호 대 잡음비⁠(signal-to-noise ratio)⁠는 데시벨입니다(10데시벨⁠(decibel)⁠이 10배, 20데시벨이 100배). 받는 쪽은 받은 점에 가장 가까운 부호어로 읽습니다. 회색 격자는 그 경계, 곧 평면을 '어느 부호어가 가장 가까운가'로 나눈 보로노이 영역⁠(Voronoi region)⁠입니다. 볼 것은 받은 점들의 구름이 자기 칸을 얼마나 자주 넘어가는가입니다.

신호 대 잡음비는 배이고, 600개 가운데 개를 잘못 읽었습니다.

두 차원의 구름은 둥글게 퍼져 있어서 경계를 자주 넘습니다. 그런데 차원이 높아지면 이상한 일이 생깁니다. 잡음 벡터의 길이의 제곱은 피타고라스 정리⁠(Pythagorean theorem)⁠대로 성분들의 제곱을 모두 더한 것입니다. 성분 하나하나는 표준편차 $\sigma$('시그마')인 정규분포 잡음이라서, 제곱의 평균은 $\sigma^2$입니다. 그러니 큰 수의 법칙에 따라, 차원이 커질수록 제곱의 합을 $n$으로 나눈 값이 $\sigma^2$에 몰립니다. 곧 길이의 제곱이 상대적으로 거의 정확히 $n\sigma^2$이 됩니다. 예를 들어 $\sigma = 1$, $n = 100$이면 길이의 제곱은 거의 늘 100 근처, 길이는 10 근처입니다. 오른쪽 그림에서 차원($n =$ )을 올려 보세요. 길이가 평균의 ±10% 안에 들 확률이 입니다. 높은 차원의 잡음 구름은 속이 빈 얇은 껍질입니다. 받은 점은 보낸 점에서 거의 $\sqrt{n\sigma^2}$만큼 떨어진 구면 근처에 있습니다. 높은 차원에서는 부피가 거의 다 겉껍질에 몰린다는 차원의 저주⁠(curse of dimensionality)⁠가 여기서는 축복이 됩니다.

이제 5절의 셈을 부피로 할 수 있습니다. 신호의 평균 세기(성분 하나의 제곱의 평균)를 $S$, 잡음의 세기를 $N$이라 하면, 부호어 하나의 잡음 껍질은 방금 본 대로 반지름 $\sqrt{nN}$입니다. 받은 점은 신호에 잡음을 더한 것이고, 둘이 서로 독립이면 세기가 더해지므로, 받은 점들은 거의 모두 반지름 $\sqrt{n(S+N)}$인 큰 공 안에 있습니다. 평면에서 원의 넓이⁠(area)⁠가 반지름의 제곱에, 공간에서 공의 부피가 세제곱에 비례하듯, $n$차원 공의 부피는 반지름의 $n$제곱에 비례합니다. 큰 공의 부피를 작은 공의 부피로 나누면, 겹치지 않게 넣을 수 있는 잡음 공은 많아야

개입니다. 가운데 등호는 근호 안의 $n$을 약분하고 $\tfrac{S+N}{N} = 1 + \tfrac{S}{N}$로 쓴 뒤, 제곱근의 $n$제곱을 $n/2$제곱으로 적은 것입니다. 부호어가 이만큼이면 하나를 골라 보내는 것으로 $\log_2$를 취한 $\tfrac{n}{2} \log_2(1 + S/N)$비트를 싣습니다. 한 차원에 $\tfrac12 \log_2(1 + S/N)$비트이고, 1초에 $2B$차원이니 둘을 곱해 이렇게 됩니다.

이것이 섀넌–하틀리 정리입니다. 하틀리의 공식 $2B \log_2 M$에서 알아볼 수 있는 수준의 수를 $M = \sqrt{1 + S/N}$으로 놓은 것과 같으니, 하틀리의 직관이 옳았던 셈입니다. 다만 섀넌은 이 수를 '대략 알아볼 수 있는 수'가 아니라, 긴 부호로 오류를 얼마든지 작게 하며 다가갈 수 있는 정확한 한계로 바꾸어 놓았습니다. 섀넌은 또 같은 세기의 잡음 가운데 정규분포 잡음이 가장 해롭다는 것도 보였습니다. 세기가 같을 때 엔트로피가 가장 큰 분포가 정규분포이기 때문입니다(최대 엔트로피 원리⁠, principle of maximum entropy⁠). 식을 보면 대역폭은 용량을 곧장 늘리지만 신호 세기는 로그로만 늘립니다. 대역폭을 두 배로 하면 용량이 두 배가 되지만, 신호 세기를 두 배로 하면 신호 대 잡음비가 클 때 1초에 $B$비트쯤만 늡니다. 2절의 교훈 그대로입니다.

전화선에 대어 봅시다. 대역폭 3,000헤르츠, 신호 대 잡음비 30데시벨(1,000배)이면 $3000 \times \log_2 1001 \approx 29{,}900$비트, 곧 초당 약 3만 비트입니다. 1990년대 중반 양쪽 끝이 모두 아날로그 전화선인 모뎀의 속도가 초당 33.6킬로비트에서 더 오르지 못한 것은 이 벽 근처에 다다랐기 때문입니다. 그 뒤의 56킬로비트 모뎀은 전화국 쪽 구간이 이미 디지털이라는 점을 이용한 것입니다. 반대로 신호 대 잡음비가 1보다 훨씬 작아도 용량은 0이 아닙니다. 대역폭을 넓게 쓰고 느리게 보내면 잡음보다 약한 신호로도 믿을 만하게 통신할 수 있습니다. 7절의 우주 탐사선이 그렇게 합니다.

정리하면, 높은 차원에서 잡음은 얇은 껍질에 몰리므로 부호어마다 크기가 정해진 잡음 공을 차지하고, 그 공을 큰 공에 몇 개 넣을 수 있는가가 용량 $B \log_2(1 + S/N)$을 줍니다.

7 · 50년의 사냥해밍의 검사 비트에서 극 부호⁠(polar code)⁠까지

이 절의 물음은 이것입니다. 섀넌의 정리는 좋은 부호가 있다고만 말했습니다. 목록을 통째로 적지 않고도 빨리 만들고 빨리 풀 수 있는 부호로, 용량에 얼마나 다가갈 수 있을까?

섀넌의 1948년 논문에는 동료 리처드 해밍이 만든 부호가 예로 실렸습니다. 데이터 4비트에 검사 비트 3비트를 더해 한 비트의 오류를 스스로 찾아 고치는 해밍 (7,4) 부호입니다. 해밍의 논문은 1950년에야 나왔습니다. 그 사이 뉴저지주 포트먼머스 육군 통신 연구소의 스위스 출신 물리학자 마르셀 골레이가 섀넌의 논문을 읽고, 1949년 한 쪽짜리 메모에서 이 예를 일반화했습니다. 그가 내놓은 부호는 23비트 가운데 12비트가 데이터이면서 오류 셋까지 고칩니다. 골레이 부호⁠(Golay code)⁠는 잡음 공들이 빈틈없이 공간을 채우는 드문 '완전 부호⁠(perfect code)⁠'입니다. 해밍 부호가 틀린 비트를 찾는 원리는 「짧게 보내기」 7절에서 직접 해 볼 수 있고, 주말마다 오류로 멈추는 계전기⁠(relay)⁠ 계산기에 지친 해밍이 이 부호를 만든 이야기는 「까마귀와 택시」 5절에 있습니다.

우주 탐사가 이 부호들의 첫 무대가 되었습니다. 먼 곳에서 오는 신호는 거리의 제곱에 반비례해 약해집니다. 그런데 탐사선은 무게와 전력이 빠듯해 신호를 키울 수 없으니, 섀넌–하틀리 정리가 말하는 대로 느리게 보내며 부호로 지켜야 했습니다. 1971년 11월 다른 행성의 궤도⁠(orbit)⁠를 도는 첫 탐사선이 된 마리너 9호는 화성 사진의 화소마다 밝기 6비트를 32비트 부호어로 바꿔 보냈습니다. 1954년 수학자 데이비드 뮬러와 어빙 리드가 내놓은 리드–뮬러 부호⁠(Reed–Muller code)⁠로, 32비트 가운데 7비트까지 틀려도 고칩니다. 부호율은 6/32, 반복 부호만큼 낭비가 커 보이지만 훨씬 강합니다.

1955년 MIT의 피터 일라이어스는 덩어리마다 따로 부호화하는 대신, 비트를 흘려보내며 최근 몇 비트를 섞어 검사 비트를 만드는 합성곱 부호⁠(convolutional code)⁠를 내놓았습니다. 이 부호를 가장 그럴듯하게 푸는 방법은 1967년 UCLA의 앤드루 비터비가 찾았습니다. 부호기가 거칠 수 있는 상태들의 격자에서 받은 신호와 가장 잘 맞는 길을 찾는 것으로, 앞에서부터 상태마다 가장 좋은 길 하나만 남기는 동적 계획법⁠(dynamic programming)⁠입니다. 같은 알고리즘⁠(algorithm)⁠이, 겉으로 드러난 소리나 낱말 뒤에서 보이지 않는 상태가 확률적으로 옮겨 간다고 보는 은닉 마르코프 모델⁠(hidden Markov model)⁠에서 품사⁠(part of speech)⁠를 태깅하고 음성을 알아듣는 데 쓰입니다(「말을 세는 기계」). 비터비는 뒤에 이동통신 회사 퀄컴을 함께 세웠습니다. 가장 좋은 길 하나를 고르는 비터비 알고리즘⁠(Viterbi algorithm)⁠과 모든 길의 확률을 더하는 알고리즘은, '더하기'와 '곱하기' 자리에 무엇을 넣느냐만 다른 한 계산입니다(「같은 계산, 다른 덧셈」 6절).

한편 1960년 MIT 링컨 연구소의 어빙 리드와 구스타브 솔로몬은 데이터를 다항식⁠(polynomial)⁠의 계수로 보고 그 다항식의 값 여러 개를 보내는 리드–솔로몬 부호⁠(Reed–Solomon code)⁠를 발표했습니다. 다항식은 몇 점만 알면 되살릴 수 있으니, 값 몇 개가 통째로 망가져도 괜찮습니다. 가장 작은 예로, 데이터 두 수 $a$, $b$를 직선 $y = a + bx$의 계수로 삼고 $x = 1, 2, 3, 4$에서의 값 네 개를 보낸다고 합시다. 직선은 두 점으로 정해지므로, 넷 가운데 어느 둘이 지워져도 남은 두 값으로 직선을 다시 그어 $a$, $b$를 되찾습니다. 긁힌 자국처럼 연달아 몰려오는 오류에 강해서, 1982년에 나온 음악 CD와 1994년 일본 덴소 웨이브가 만든 QR 코드에 들어갔습니다. QR 코드는 가장 강한 설정에서 데이터 조각(부호어)의 30% 가까이가 망가져도 읽힙니다.

1977년에 떠난 보이저 탐사선들은 두 부호를 겹쳐 썼습니다. 탐사선은 합성곱 부호로 비트를 감싸 보내고 지상의 수신기가 비터비 알고리즘으로 풀었습니다. 목성과 토성에서는 그 안쪽에 골레이 부호를 한 겹 더 썼습니다. 그러나 해왕성은 목성보다 대략 여섯 배 멀어서, 거리의 제곱에 따라 신호 세기는 36분의 1이 됩니다. 1979년 목성에서 초당 115,200비트로 보내던 링크를 그대로 두면 1989년 해왕성에서는 초당 3,200비트쯤으로 떨어질 참이었습니다. 탐사를 맡은 NASA 제트 추진 연구소(JPL)는 천왕성에 다가가기 전부터, 먼 여정에 대비해 실어 둔 리드–솔로몬 부호기로 골레이 부호를 바꿨습니다. 덧붙이는 비트는 데이터만큼(100%)에서 약 14%(데이터 223바이트마다 32바이트)로 줄고, 되살린 데이터의 비트 오류율은 1,000분의 5에서 100만분의 1로 내려갔습니다. 지상 안테나를 키우고 여러 개를 묶은 것까지 더해, 보이저 2호는 해왕성에서 초당 21,600비트를 보냈습니다. 탐사선 송신기의 출력은 20와트 안팎이었습니다.

부호의 시대. 머리힐의 섀넌과 해밍에서 시작한 생각이 포트먼머스, MIT, 링컨 연구소, UCLA, 패서디나의 JPL을 거쳐 브레스트, 케임브리지, 앙카라로 가는 길을 보세요. 수학 줄(파랑)의 부호들이 과학 줄의 탐사선과 역사 줄의 CD, QR 코드, 이동통신이 됩니다.

이렇게 겹쳐 쓴 부호도 섀넌의 한계와는 여전히 몇 데시벨, 곧 신호 세기로 몇 배의 차이가 있었습니다(3데시벨이 약 2배입니다). 같은 오류율을 얻는 데 섀넌의 한계가 허락하는 것보다 신호를 몇 배 세게 보내야 했다는 뜻입니다. 1993년 5월 제네바에서 열린 국제 통신 학회에서, 프랑스 브레스트의 통신 학교에 있던 클로드 베루, 알랭 글라비외, 푼야 티티마즈시마가 「섀넌의 한계에 가까운 오류 정정 부호와 복호: 터보 부호⁠(turbo code)⁠」를 발표했습니다. 간단한 합성곱 부호 두 개를, 비트 순서를 뒤섞어 나란히 쓰고, 두 복호기⁠(decoder)⁠가 비트마다 '믿음'을 주고받으며 여러 번 되풀이해 고치는 방식이었습니다. 한계에서 1데시벨이 되지 않는 곳에서 비트 오류율 10만분의 1을 얻었다는 결과를, 처음에는 많은 전문가가 믿지 않았습니다. 곧 여러 곳에서 결과가 확인되었습니다.

그러자 잊혔던 부호가 다시 불려 나왔습니다. MIT의 로버트 갤러거가 1960년 박사 논문에서 내놓고 1963년 책으로 펴낸 저밀도 패리티 검사 부호⁠(low-density parity-check code)⁠, 곧 LDPC 부호입니다. 검사 하나가 비트 몇 개만 보고 비트 하나가 검사 몇 개에만 들어가는, 성긴 검사들로 된 부호입니다. 당시의 컴퓨터로는 긴 부호를 풀기 벅차서 30년 넘게 거의 잊혔습니다. 1990년대 중반 케임브리지의 물리학자 데이비드 매카이와 토론토의 통계학자 래드퍼드 닐이 이 부호를 다시 찾아내, 터보 부호만큼 좋다는 것을 보였습니다. 2001년에는 아주 긴 LDPC 부호가 모의실험에서 섀넌의 한계에서 0.0045데시벨 떨어진 곳까지 다가갔습니다.

LDPC 부호는 비트와 검사를 점으로 놓고 이은 이분 그래프(점이 두 무리로 나뉘고 선은 늘 다른 무리의 점끼리만 잇는 그래프)로 그립니다. 1981년 이 그림을 쓴 마이클 태너의 이름을 따서 태너 그래프⁠(Tanner graph)⁠라고 부릅니다. 아래는 비트 20개와 검사 12개로 된 작은 LDPC 부호입니다. 비트마다 검사 3개에 들고, 검사마다 비트 5개를 보며, 검사는 자기가 보는 비트들의 합이 짝수여야 만족합니다(2로 나눈 나머지⁠(remainder)⁠). 부호율은 , 곧 20비트 가운데 8비트가 데이터입니다. 비트를 눌러 잡음을 흉내 내거나, 무작위로 개를 뒤집어 보세요. 만족하지 않는 검사가 빨개지고, 비트 아래의 빨간 점은 그 비트를 의심하는 검사의 수입니다.

잡음 뿌리기 잡음 지우기 새 부호어

이것이 갤러거가 제안한 비트 뒤집기 복호⁠(bit-flipping decoding)⁠의 가장 단순한 형태입니다. 가장 많은 검사가 의심하는 비트를 뒤집고, 검사를 다시 보고, 되풀이합니다. 비트 하나의 오류는 언제나 고칩니다. 틀린 비트의 검사 셋이 모두 빨개지는데, 이 그래프에서는 어떤 두 비트도 검사를 둘 이상 함께 쓰지 않아서 다른 비트는 많아야 하나에게만 의심받기 때문입니다. 무작위 오류를 2,000번씩 뿌려 보면 되찾는 비율은 오류 입니다. 이 작은 부호에서는 가장 가까운 두 부호어도 4비트밖에 다르지 않으니 둘 이상의 오류에 약한 것이 당연합니다. 실제 LDPC 부호는 비트가 수천에서 수만 개이고, 이렇게 긴 부호에서 5절의 큰 수의 법칙이 힘을 냅니다. 실제 복호기(받은 말에서 원래 부호어를 되찾는 장치)는 0과 1을 딱 잘라 뒤집는 대신, 비트마다 '1일 확률'을 검사들과 주고받으며 베이즈 정리로 고쳐 가는 믿음 전파⁠(belief propagation)⁠를 씁니다. 터보 부호의 되풀이 복호도 같은 생각의 다른 모습이라는 것이 뒤에 밝혀졌습니다.

마지막 조각은 2009년 앙카라 빌켄트 대학의 에르달 아리칸이 맞췄습니다. 그는 1980년대 MIT에서 바로 갤러거의 지도를 받아 박사 학위를 받은 사람입니다. 같은 통로를 여러 번 쓰는 것을 교묘하게 짝지으면, 통로들이 거의 완벽한 것과 거의 쓸모없는 것으로 갈라집니다. 극 부호는 이 '통로 분극⁠(channel polarization)⁠'을 이용해 완벽한 쪽에만 데이터를 싣습니다. 대칭인 이진 통로에서 부호를 길게 할수록 용량에 다가간다는 것을 증명할 수 있으면서, 만들고 풀기도 쉬운 첫 부호로 꼽힙니다. 2016년 이동통신 표준을 정하는 3GPP는 5G에서 데이터에는 LDPC 부호를, 제어 정보에는 극 부호를 쓰기로 했습니다. 섀넌의 약속에서 주머니 속 전화기까지 68년이 걸렸습니다.

정리하면, 섀넌이 존재만 보인 좋은 부호에 다가간 열쇠는 두 가지였습니다. 단순한 규칙을 되풀이해(LDPC의 성긴 검사, 극 부호의 거듭된 짝짓기) 아주 긴 부호를 만드는 것, 그리고 받는 쪽이 0과 1을 딱 잘라 정하지 않고 비트마다 확률을 따지며 조금씩 풀어 가는 것입니다.

8 · 이어지는 길잡음과 함께 사는 수학

• 압축: 섀넌은 압축(원천 부호화)과 오류 정정(통로 부호화)을 따로 해도, 길게 묶어 보내는 극한에서는 손해가 없음을 보였습니다. 먼저 원천 부호화 정리⁠(source coding theorem)⁠가 허락하는 만큼 여분을 짜내고, 그다음 통로에 맞게 설계된 여분을 새로 더하면 됩니다. 조금 잃어도 되는 메시지를 얼마나 줄일 수 있는지는 율–왜곡 이론⁠(rate–distortion theory)⁠이 답합니다(「짧게 보내기」).
• 암호: 섀넌은 1949년 같은 도구로 비밀 통신을 분석해, 열쇠가 평문⁠(plaintext)⁠만큼 길고, 완전히 무작위로 골라졌으며, 한 번만 쓰일 때 엿듣는 사람이 얻는 상호 정보량이 정확히 0임을 보였습니다. 잡음 통로⁠(noisy channel)⁠ 부호화에서는 받는 쪽이 모르는 것을 줄이려 하고, 암호에서는 엿듣는 쪽이 모르는 것을 키우려 합니다(「나머지로 지키는 비밀」).
• 언어: 음성 인식과 기계 번역⁠(machine translation)⁠의 통계적 방법은 말을 '잡음 통로를 지나온 메시지'로 보고 가장 그럴듯한 원문을 찾는 문제로 바꾸었습니다. 비터비 알고리즘이 거기서도 쓰입니다(「말을 세는 기계」). 섀넌이 1951년 사람에게 다음 글자를 맞히게 해서 영어의 엔트로피를 잰 '추측 게임'은 오늘날 다음 낱말을 맞히도록 훈련하는 언어 모델⁠(language model)⁠의 먼 조상입니다(「다음 단어를 맞히는 기계」).
• 학습: 분류 모형을 훈련하는 교차 엔트로피 손실은 쿨백–라이블러 발산과 한 몸이고, 입력과 표현 사이의 상호 정보량은 신경망⁠(neural network)⁠이 무엇을 배우는지 설명하려는 여러 시도의 도구가 되었습니다(「배우는 기계」). 거꾸로 자료에 정규분포 잡음을 조금씩 더해 지우는 과정을 되돌리도록 신경망을 학습시키면, 순수한 잡음에서 새 그림을 만들어 내는 확산 모델⁠(diffusion model)⁠이 됩니다. 그 잡음이 퍼지는 방식이 1절에서 톰슨이 케이블에 쓴 열방정식과 같은 식이라는 이야기는 「라플라시안, 가장 많이 재사용된 식」 9절에 있습니다.
• 거꾸로 풀기: 받은 신호에서 보낸 것을 되찾는 일은 역문제⁠(inverse problem)⁠이기도 합니다. 1절의 케이블처럼 빠른 변화를 뭉개는 통로를 거꾸로 풀면, 뭉개진 성분에 섞인 잡음이 거꾸로 크게 부풀어 오릅니다. 흐린 사진을 되살릴 때 부딪히는 이 벽과 그것을 넘는 처방은 「거꾸로 푸는 문제는 왜 어려운가」에 있습니다.
• 세기로 긋는 한계: 용량보다 빠르게는 믿을 만하게 보낼 수 없다는 역정리의 뼈대는 5절의 잡음 공 세기, 곧 비둘기집 원리입니다. 모든 파일을 줄이는 압축이 없다는 것과 같은 종류의 불가능성 증명입니다(「불가능의 증명」).
• 뭉쳐 오는 오류: 섀넌의 이진 대칭 통로는 비트마다 서로 독립으로 뒤집힌다고 가정합니다. 실제 전화선의 오류는 몰려옵니다. 1963년 IBM의 제이 버거와 브누아 망델브로는 전화선의 오류 기록에서 오류 사이의 간격이 꼬리가 두꺼운 거듭제곱 분포를 따른다고 보고했습니다. 망델브로는 뒤에 이 오류들이 어느 시간 규모로 보아도 비슷하게 뭉쳐 있다는 점을 칸토어 집합⁠(Cantor set)⁠에 비겼습니다. 리드–솔로몬 부호와 CD의 엇갈림 배치(비트 순서를 섞어 몰려온 오류를 여러 부호어로 흩어 놓는 방법)가 몰려오는 오류를 따로 다루는 까닭입니다. 망델브로가 같은 무렵 해안선에서 본 자기 닮음⁠(self-similarity)⁠은 「재는 순간 바뀐다」 2절에서 이어집니다.
• 거리: 가장 가까운 부호어로 읽는 복호는 해밍 거리⁠(Hamming distance)⁠와 유클리드 거리⁠(Euclidean distance)⁠ 위의 최근접 이웃⁠(nearest neighbor)⁠ 찾기입니다. 좋은 부호를 찾는 일은 고차원 공간에 공을 빽빽이 채우는 문제와 닮았습니다(「까마귀와 택시」).
• 확률: 통로 부호화 정리의 속은 큰 수의 법칙이고, 무작위 부호의 논증은 몬테카를로처럼 '무작위가 평균적으로 좋다'는 생각입니다(「도박판에서 온 편지」).
• 물리: 정보를 지우는 데에는 열이 든다는 IBM의 물리학자 롤프 란다우어의 원리는 맥스웰의 악마⁠(Maxwell's demon)⁠의 역설을 푸는 열쇠가 되었습니다. 톰슨의 케이블 방정식은 열방정식의 사촌입니다. 2절의 열잡음도 온도의 얼굴입니다.
• 생명과 저장: DNA를 복제하는 효소는 잘못 붙인 염기를 되돌아가 고치고, 하드 디스크와 SSD, 메모리, 먼 우주의 탐사선, 바닥에 떨어진 QR 코드까지, 오늘날 비트가 머무는 거의 모든 곳에 오류 정정 부호가 들어 있습니다.