Chapter 08

놀라움을 재는 법

"정보"는 뜻이 모호한 일상어처럼 보이지만, 1948년 클로드 섀넌은 그것을 전압이나 길이처럼 잴 수 있는 양으로 바꿔 놓았습니다. 잣대는 놀라움입니다. 뻔한 소식은 정보가 적고, 드문 소식은 정보가 많습니다. 이 한 가지 생각에서 압축 파일이 얼마나 작아질 수 있는지, 잡음 많은 전선으로 초당 몇 비트까지 보낼 수 있는지, 찢긴 QR 코드가 어떻게 원래 내용을 되살리는지가 차례로 따라 나옵니다.

사건의 정보량 $-\log_2 p$와 평균 정보량인 엔트로피를 계산하고, 스무고개·이진 탐색과 연결할 수 있다.
허프만 부호를 직접 만들고, 무손실 압축이 엔트로피 아래로 내려갈 수 없는 이유를 설명할 수 있다.
이진 대칭 채널, 반복 부호, 해밍(7,4) 부호의 신드롬 복호를 손으로 해 볼 수 있다.
섀넌–하틀리 채널 용량 $C = B\log_2(1+\mathrm{SNR})$으로 통신 링크의 한계를 어림할 수 있다.
리드–솔로몬 부호를 "다항식 보간"으로 이해하고, QR 코드의 오류 정정 레벨이 무엇을 뜻하는지 안다.

이 수식이 없었다면찢겨도 읽히는 QR 코드

QR 코드는 귀퉁이가 찢기거나, 가운데에 회사 로고를 덮어 씌워도 읽힙니다. 그림의 일부가 사라졌는데 어떻게 원래 내용이 남아 있을까요? 비결은 데이터 뒤에 덧붙인 리드–솔로몬 오류 정정 부호입니다. 오류 정정 레벨 L·M·Q·H에 따라 전체 부호어의 약 7·15·25·30%가 망가져도 복원됩니다.

그런데 "얼마나 덧붙이면 얼마나 견디는가"를 따지려면 먼저 정보 자체를 잴 수 있어야 합니다. 섀넌은 1948년 논문 「통신의 수학적 이론」에서 정보를 확률의 로그로 재고, 잡음 있는 채널에도 넘을 수 없는 속도 한계와 그 한계까지는 오류를 얼마든지 줄일 수 있다는 사실을 보였습니다. 오류 정정 부호 이론은 거기서 출발했습니다.

찢긴 그림→사라진 비트→정보량 · 엔트로피 · 다항식 보간→원래 내용 복원

정보 = 놀라움

사막의 일기예보를 전송하라

사막 관측소가 매일 날씨를 전신으로 본사에 보냅니다. 1년 중 360일은 "맑음"입니다. 매일 "맑음"이라는 글자를 꼬박꼬박 보내는 것은 낭비처럼 느껴지고, 어쩌다 오는 "비"는 반드시 전해야 할 큰 소식입니다. 회선 용량을 설계하려면 메시지의 뜻과 무관하게 "얼마나 많은 정보가 오가는가"를 숫자로 재야 합니다. 글자 수로 재면 "맑음"과 "비"는 거의 같은 길이라 이 차이를 놓칩니다.

직관을 정리하면 정보량 $I$이 가져야 할 성질은 셋입니다. (1) 확률 $p$가 작을수록, 즉 놀라울수록 크다. (2) 반드시 일어나는 일($p=1$)은 정보가 0이다. (3) 서로 독립인 두 사건을 함께 들으면 정보가 더해진다. 그런데 독립 사건의 확률은 곱해집니다: $p(A\cap B) = p(A)\,p(B)$. 곱을 합으로 바꾸는 함수는 로그뿐이므로 답이 정해집니다.

$$I(x) = -\log_2 p(x) = \log_2\frac{1}{p(x)} \quad[\text{bit}]$$

밑이 2이면 단위는 비트(bit), 자연로그면 nat(1 nat ≈ 1.443 bit). 확률 1/2인 사건(공정한 동전의 앞면)이 정확히 1비트다. 1928년 하틀리(R. Hartley)가 "가능한 경우의 수 $N$의 로그"로 정보를 재자고 제안했고, 섀넌은 이를 경우마다 확률이 다른 일반적인 상황으로 넓혔다.

사건	확률 p	정보량 −log₂p
공정한 동전이 앞면	1/2	1 bit
주사위가 6	1/6	2.585 bit
1~1,048,576 중 특정한 수	2⁻²⁰	20 bit
로또 6/45 1등 번호 조합	1/8,145,060	22.96 bit
사막에서 "맑음"(360/365)	0.986	0.020 bit
사막에서 "비"(5/365)	0.0137	6.19 bit

스무고개는 20비트다

"예/아니오" 질문 한 번의 답은 최대 1비트입니다. 후보를 정확히 반으로 가르는 질문을 던지면 어느 답이 나와도 확률이 1/2이므로 매번 1비트를 얻습니다. 20번이면 $2^{20} = 1{,}048{,}576$개, 대략 100만 개 중 하나를 맞힐 수 있습니다. 거꾸로, $N$개 중 하나를 확실히 맞히려면 최소 $\lceil\log_2 N\rceil$번은 물어야 합니다. 이진 탐색이 $O(\log N)$인 이유도, 8비트 ADC가 256단계를 구별하는 이유도 같은 계산입니다.

그림 8-1. 1~8 중 하나를 맞히는 스무고개. 매 질문이 후보를 반으로 가르면 3번(= log₂8)이면 끝난다. 답을 예=0, 아니오=1로 적으면 각 수는 3비트 부호가 된다. 질문의 답이 곧 비트다.

SIMULATOR

숫자 맞히기: 질문 하나는 몇 비트인가

후보 수 N

아래쪽 막대(현재 후보 구간)를 클릭하면 그 위치의 수 x에 대해 "비밀 수 ≤ x?"라고 묻습니다. 마우스를 올리면 답마다 얻을 정보량이 미리 보입니다.

질문 수0

남은 후보—

마지막 답의 정보량—

얻은 정보 / 필요한 정보—

비밀 수를 정했습니다. 질문을 시작하세요.

해볼 것: ① N = 2²⁰(약 100만)으로 놓고 "반으로 묻기"만 눌러 정확히 20번에 끝나는지 확인. ② 구간의 맨 왼쪽 근처를 클릭해 한쪽으로 치우친 질문을 던지기: 보통 "아니오"가 나와 0.0몇 비트밖에 못 얻지만, 가끔 "예"가 나오면 큰 정보(놀라움)를 얻는다. ③ 치우친 질문을 계속하면 평균 질문 수가 log₂N보다 늘어나는지 보기. · 모델: 비밀 수는 1..N에서 균등하게 뽑는다. 각 답의 정보량은 "현재 후보 중 그 답과 맞는 비율" p에 대해 −log₂p이고, 정보량을 모두 더하면 정확히 log₂(N / 남은 후보)가 된다.

엔트로피 = 평균 놀라움

설비 상태 신호에 몇 비트를 배정할까

공장 장비가 1초마다 상태를 보냅니다. 상태는 4가지(정상·주의·경고·정지)이고, 고정 길이로 보내면 2비트입니다. 그런데 99%가 "정상"이라면 평균 2비트는 지나치게 많아 보입니다. 기호 하나당 평균적으로 몇 비트면 충분할까요? 사건 하나의 놀라움이 아니라 "정보원"의 평균 놀라움을 재야 합니다.

확률 $p_i$인 기호 $i$가 나올 때마다 $-\log_2 p_i$비트의 놀라움을 얻으므로, 기대값을 취하면 정보원의 엔트로피(Entropy)가 됩니다.

$$H(X) = \sum_i p_i \log_2\frac{1}{p_i} = -\sum_i p_i\log_2 p_i, \qquad 0 \le H \le \log_2 K$$

$K$는 기호의 개수. $0\log 0 = 0$으로 둔다(극한값). 한 기호가 확실하면($p=1$) $H=0$, 모든 기호가 균등하면($p_i = 1/K$) 최대값 $\log_2 K$. 통계역학의 볼츠만–깁스 엔트로피와 같은 꼴이라 폰 노이만이 섀넌에게 이 이름을 권했다는 일화가 전해진다.

위 문제의 상태 신호가 (0.99, 0.006, 0.003, 0.001)이라면 $H \approx 0.093$비트입니다. 기호당 2비트를 쓰는 고정 길이 방식보다 이론적으로 20배 이상 줄일 여지가 있다는 뜻입니다. 두 기호(동전)의 경우는 따로 이름이 있는 이진 엔트로피 함수입니다.

$$H_2(p) = -p\log_2 p - (1-p)\log_2(1-p)$$

$p=0.5$에서 최대 1비트, $p=0.11$이면 약 0.5비트, $p=0.01$이면 0.081비트. 4절에서 잡음 채널의 용량 $1-H_2(p)$로 다시 등장한다.

SIMULATOR

확률 막대를 끌어 엔트로피 바꾸기

기호 확률 (끌어서 조정, 합 = 1)

동전 하나: H₂(p)

기호 수 K

프리셋

엔트로피 H—

최대 log₂K—

잉여도 1 − H/log₂K—

동전 H₂(p)—

해볼 것: ① 아무 막대나 위아래로 끌어 보고, 어떤 모양일 때 H가 최대(막대가 모두 점선 1/K 높이)인지 확인. ② "1/2, 1/4, 1/8 …" 프리셋에서 각 막대 위 −log₂p가 정수(1, 2, 3 …)인 것을 보기: 이런 분포는 다음 절의 허프만 부호가 엔트로피에 정확히 도달한다. ③ 오른쪽 점을 끌어 동전이 조금만 치우쳐도(p = 0.4) H₂가 0.97비트로 거의 줄지 않는 것 확인: 곡선이 꼭대기에서 평평하다. · 모델: 한 막대를 바꾸면 나머지는 서로의 비율을 유지한 채 함께 늘거나 줄어 합 1을 유지한다. 막대 위 숫자는 확률과 그 기호의 놀라움 −log₂p.

영어 한 글자는 몇 비트인가 26글자가 균등하면 log₂26 ≈ 4.70비트지만, 실제 글자 빈도(e가 약 12%, z는 0.1% 미만)로 계산하면 약 4.1~4.2비트로 줄어든다. 섀넌은 1951년 사람에게 다음 글자를 맞히게 하는 실험으로, 앞 문맥을 모두 고려하면 영어가 글자당 대략 0.6~1.3비트 수준이라고 추정했다. "글자 빈도만 아는 모델"과 "문맥을 아는 모델"의 엔트로피 차이가 곧 압축 프로그램과 언어 모델이 뽑아낼 수 있는 여유다.

압축의 한계: 허프만 부호

같은 텍스트를 더 적은 비트로

로그 파일이 매일 수 GB씩 쌓입니다. 글자마다 고정된 8비트(ASCII) 또는 한글 한 글자 24비트(UTF-8)를 쓰는 대신, 자주 나오는 글자에 짧은 부호를, 드문 글자에 긴 부호를 주면 줄어들 것입니다. 모스 부호가 가장 흔한 글자 E에 점 하나를 준 것과 같은 생각입니다. 그런데 (1) 구분자 없이 이어 붙여도 해독이 되도록 하려면 어떻게 부호를 정하고, (2) 어디까지 줄일 수 있을까요?

첫째 문제: a=0, b=01, c=1로 정하면 "01"이 "ab"인지 "ac"…가 아니라 "b"인지 "a c"인지 구별되지 않습니다. 해결책은 어떤 부호도 다른 부호의 앞부분(접두어)이 되지 않게 하는 접두어 부호(Prefix-free Code)입니다. 이진 트리의 잎에만 기호를 두고 왼쪽=0, 오른쪽=1로 경로를 읽으면 자동으로 접두어 부호가 됩니다. 비트를 읽으며 트리를 내려가다 잎에 닿으면 한 기호가 끝난 것입니다.

둘째 문제의 답이 섀넌의 원천 부호화 정리(Source Coding Theorem)입니다. 길이 $\ell_i$인 접두어 부호는 크래프트 부등식 $\sum_i 2^{-\ell_i} \le 1$을 만족해야 하고, 이 제약 아래 평균 길이를 최소화하면 $\ell_i = -\log_2 p_i$가 이상적인 길이입니다. 부호 길이는 정수여야 하므로 정확히 그렇게는 못 하지만 1비트 이내로 다가갈 수 있습니다.

$$H(X) \;\le\; \bar L = \sum_i p_i\,\ell_i \;<\; H(X) + 1$$

왼쪽 부등식: 어떤 무손실 부호도 평균 길이가 엔트로피보다 짧을 수 없다. 오른쪽: 허프만 부호는 그 아래 1비트 이내를 보장한다. 기호 여러 개를 묶어 한 덩어리로 부호화하면 덩어리당 +1비트의 손해가 기호당 +1/n으로 줄어 엔트로피에 얼마든지 가까워진다.

1952년 MIT 대학원생이던 데이비드 허프만은 이 최적 부호를 만드는 놀랍도록 단순한 방법을 학기 과제로 제출했습니다. 가장 드문 두 기호를 묶어 하나로 만들고, 기호가 하나 남을 때까지 반복한다. 묶을 때마다 두 가지에 0과 1을 붙이면 트리가 아래에서 위로 완성됩니다. 같은 길이 조건에서 이보다 평균이 짧은 접두어 부호는 없다는 것이 증명되어 있습니다.

SIMULATOR

허프만 트리 만들기

텍스트 (직접 입력 가능) 예시

기호 종류 K / 글자 수—

엔트로피 H (글자당)—

허프만 평균 길이—

고정 길이 ⌈log₂K⌉—

총 비트: 허프만 / 고정 / UTF-8—

해볼 것: ① "aaaabbcd"에서 평균 길이가 엔트로피와 정확히 같아지는 것(1.75비트) 확인. ② "aaaaaaaaaaaaaaab"에서는 엔트로피가 0.34비트인데 허프만은 1비트 아래로 못 내려가는 것 보기: 기호 하나에 최소 1비트가 필요하기 때문이다. ③ 한글 예시에서 UTF-8(글자당 24비트) 대비 몇 배 줄어드는지 보기. · 모델: 텍스트 자체의 글자 빈도를 확률로 쓴다(트리 정보를 함께 보내는 비용은 무시). 빈도가 같으면 먼저 등장한 기호를 먼저 묶으므로, 부호는 달라도 평균 길이는 같은 다른 허프만 트리도 존재한다. 아래 비트열은 앞부분을 기호마다 색을 번갈아 표시한 것.

압축은 엔트로피를 이길 수 없다 "어떤 파일이든 1비트라도 줄이는" 무손실 압축기는 존재할 수 없다. n비트 파일은 $2^n$가지인데 그보다 짧은 파일은 모두 합쳐 $2^n - 1$가지뿐이라, 비둘기집 원리로 어떤 두 파일은 같은 결과로 압축되어 되돌릴 수 없다. 그래서 이미 압축된 ZIP·JPEG 파일을 다시 압축해도 거의 줄지 않는다. 그 파일의 비트는 이미 동전 던지기처럼 예측 불가능(엔트로피 ≈ 1비트/비트)하기 때문이다. ZIP 등이 쓰는 DEFLATE는 반복 구간을 찾는 LZ77 뒤에 허프만 부호를 붙인 구성이다.

잡음 채널: 비트가 뒤집힌다

1%의 비트가 뒤집히는 선로

압축으로 잉여를 다 짜낸 데이터를 이제 잡음 있는 선로로 보냅니다. 무선 링크든, 플래시 메모리 셀이든, 우주 탐사선 신호든 일정 확률로 0이 1로, 1이 0으로 바뀝니다. 압축된 데이터는 잉여가 없어서 한 비트만 틀려도 뒤가 통째로 망가집니다. 그렇다면 일부러 잉여를 다시 넣어야 합니다. 얼마나, 어떻게?

가장 단순한 잡음 모델은 이진 대칭 채널(Binary Symmetric Channel, BSC)입니다. 각 비트가 독립적으로 확률 $p$로 뒤집힙니다. 가장 단순한 대책은 같은 비트를 여러 번 보내고 다수결로 정하는 반복 부호(Repetition Code)입니다. 3번 반복하면 2번 이상 뒤집혀야 틀리므로

$$P_e^{(3)} = 3p^2(1-p) + p^3 = 3p^2 - 2p^3 \;\approx\; 2.98\times10^{-4}\quad (p=0.01)$$

오류율이 1%에서 0.03%로 33배 줄었지만, 대가로 전송률 $R = 1/3$: 같은 데이터를 보내는 데 시간이 3배 든다. $10^{-9}$ 이하로 내리려면 11번 반복($P_e \approx 4.4\times10^{-10}$), 전송률 1/11이 필요하다. 오류를 0으로 보내려면 전송률도 0으로 가야 할 것처럼 보인다.

그림 8-2. 왼쪽: 이진 대칭 채널. 각 비트가 독립적으로 확률 p로 뒤집힌다. 오른쪽: 섀넌의 통신 시스템 모델. 원천 부호기는 잉여를 빼고(압축), 채널 부호기는 잡음에 맞서도록 계획된 잉여를 넣는다. 섀넌의 분리 정리에 따르면 두 단계를 따로 최적화해도 (충분히 긴 블록에서) 전체 최적을 잃지 않는다.

SIMULATOR

잡음 채널로 그림 보내기: 반복 부호의 비용

뒤집힘 확률 p 반복 횟수 n 틀린 비트를 색으로 표시

부호 없음 측정 오류율—

반복 부호 측정 / 이론—

전송률 R = 1/n—

채널 용량 C = 1 − H₂(p)—

해볼 것: ① p = 0.05에서 n을 1→3→5로 올리며 그림이 깨끗해지는 대신 R이 1/5까지 떨어지는 것 보기. ② 아래 그래프에서 반복 부호의 점들이 "오류율을 낮추려면 R → 0"이라는 왼쪽 아래 방향으로만 가는 것, 반면 섀넌의 용량선 C 왼쪽(색칠한 영역)이라면 원리적으로 오류율을 얼마든지 낮추는 부호가 존재한다는 것 비교. ③ 해밍(7,4) 점(R = 4/7)이 같은 오류율의 반복 부호보다 훨씬 오른쪽(효율적)에 있는 것 확인. · 모델: 64×64 흑백 그림의 각 비트를 n번 보내고 각 사본이 독립적으로 확률 p로 뒤집힌 뒤 다수결. 그래프의 오류율은 정확한 이항 분포 계산(해밍은 128가지 오류 패턴을 모두 세어 복호 후 데이터 비트 오류율을 구함). 세로축 아래 끝(10⁻¹⁰)보다 작은 값은 그리지 않는다.

여기서 섀넌의 결론은 거의 믿기 어렵습니다. 이진 대칭 채널에는 용량(Capacity) $C = 1 - H_2(p)$가 있고, 전송률이 $R \lt C$이기만 하면 블록 길이를 늘려 오류 확률을 원하는 만큼 0에 가깝게 만드는 부호가 존재합니다. $p = 0.01$이면 $C \approx 0.919$: 보낸 비트의 91.9%까지를 데이터로 쓰고도 오류를 사실상 없앨 수 있다는 뜻입니다. 반복 부호(R = 1/11에서 $10^{-10}$ 수준)와는 비교가 안 됩니다. 섀넌의 증명은 "무작위로 고른 긴 부호가 평균적으로 잘 된다"는 존재 증명이어서, 실제로 그런 부호를 만드는 데 그 뒤 수십 년이 걸렸습니다. 첫 걸음이 다음 절의 해밍 부호입니다.

해밍(7,4) 부호: 오류의 주소를 알려 주는 패리티

주말 내내 멈춰 있던 계산기

1940년대 말 벨 연구소의 해밍은 주말에 계전기식 컴퓨터로 긴 계산을 돌리곤 했습니다. 기계는 패리티 검사로 오류를 찾을 수는 있었지만, 오류가 나면 작업을 버리고 다음 작업으로 넘어갔다고 합니다. 월요일에 와서 결과가 없는 것을 본 해밍은 "기계가 오류를 찾을 수 있다면, 왜 그 위치까지 알아내 고치지 못하는가"라고 물었다고 전해집니다. 그 답이 1950년에 발표된 해밍 부호입니다.

패리티 비트 하나는 "1의 개수가 짝수인가"만 알려 줍니다. 오류가 있다는 것은 알지만 어디인지는 모릅니다. 해밍의 착상은 패리티 여러 개가 데이터의 서로 다른 부분집합을 겹치게 감시하도록 하는 것입니다. 7개 위치를 1~7로 번호 매기고, 위치 1·2·4(2의 거듭제곱)에 패리티, 나머지 3·5·6·7에 데이터 4비트를 둡니다. 패리티 $p_1$은 번호의 이진수 첫 자리가 1인 위치(1,3,5,7), $p_2$는 둘째 자리가 1인 위치(2,3,6,7), $p_4$는 셋째 자리가 1인 위치(4,5,6,7)의 짝수 패리티를 맞춥니다.

$$\begin{aligned} s_1 &= r_1\oplus r_3\oplus r_5\oplus r_7\\ s_2 &= r_2\oplus r_3\oplus r_6\oplus r_7\\ s_4 &= r_4\oplus r_5\oplus r_6\oplus r_7 \end{aligned}\qquad \text{오류 위치} = (s_4 s_2 s_1)_2$$

$r_i$는 받은 비트, $\oplus$는 XOR. 오류가 없으면 세 검사가 모두 0이다. 위치 $j$의 비트 하나가 뒤집히면, $j$를 이진수로 쓸 때 1인 자리의 검사만 1이 되므로 $(s_4s_2s_1)$이 그대로 $j$의 이진수다. 이 세 비트를 신드롬(Syndrome)이라 한다. 행렬로 쓰면 $\mathbf s = H\mathbf r$(GF(2) 위), $H$의 $j$번째 열이 $j$의 이진수다(3장의 행렬 곱이 비트 위에서 그대로 쓰인다).

SIMULATOR

해밍(7,4): 비트를 뒤집으면 신드롬이 위치를 가리킨다

보낼 데이터 d₁d₂d₃d₄ (눌러서 토글)

채널 오류 넣기 (그림의 비트나 아래 칸을 직접 눌러도 된다)

보낸 부호어—

받은 비트—

신드롬 s₄s₂s₁—

복원한 데이터—

—

해볼 것: ① 7개 비트 중 아무거나 하나를 눌러 뒤집으면, 패리티가 깨진 원(빨강)들의 교집합이 정확히 그 비트이고 신드롬이 그 위치 번호를 가리키는 것 확인. ② 패리티 비트(위치 1·2·4)가 뒤집혀도 원 하나만 빨개져 그 패리티 자신을 고치는 것 보기. ③ 두 비트를 뒤집으면 신드롬이 0이 아닌 엉뚱한 세 번째 위치를 가리켜 "고친" 결과가 3비트 오류가 되는 것: 해밍(7,4)은 1비트만 고칠 수 있다. · 모델: 짝수 패리티, 위치 1~7 배치(1·2·4가 패리티). 원 안의 비트는 그 원의 패리티 검사에 포함된다. 복호기는 신드롬이 가리키는 비트 하나를 뒤집는 최소 거리 복호기다.

그림 8-3. 해밍(7,4)의 16개 부호어는 서로 최소 3비트씩 다르다(최소 해밍 거리 $d_{\min}=3$). 1비트 오류는 원래 부호어의 "반경 1 공" 안에 남아 가장 가까운 부호어로 되돌릴 수 있지만, 2비트 오류는 다른 부호어 쪽에 더 가까워져 엉뚱하게 고쳐진다. 일반적으로 $d_{\min} = 2t+1$이면 $t$비트까지 정정한다.

비용을 비교해 봅시다. 3회 반복은 1비트 정정에 데이터 1비트당 2비트를 덧붙여 전송률 1/3이지만, 해밍(7,4)은 같은 1비트 정정을 4비트당 3비트로 해 전송률 4/7 ≈ 0.571입니다. 일반적으로 패리티 $m$개로 $2^m - 1$비트 블록을 감시하는 해밍$(2^m-1,\,2^m-1-m)$ 부호를 만들 수 있고, $m=7$이면 (127,120)으로 전송률 0.945입니다. 여기에 전체 패리티 1비트를 더한 확장 해밍 부호는 1비트 정정과 2비트 검출(SECDED)을 함께 합니다.

메모리 칩 안의 해밍 부호 서버용 ECC DRAM 모듈은 64비트 데이터마다 8비트 검사 비트를 붙인 (72,64) SECDED 부호를 쓰는 것이 전통적인 구성이다(64비트에는 해밍 패리티 7개면 충분하고, 1개는 2비트 검출용 전체 패리티). DDR5는 칩 내부에도 별도의 온다이 ECC를 둔다. NAND 플래시는 셀당 비트 수가 늘수록 원시 오류율이 높아져 BCH, 나아가 LDPC처럼 훨씬 강한 부호를 쓴다. 자세한 구조는 MemoryBook에서 다룬다.

섀넌 채널 용량: 넘을 수 없는 속도 제한

전화선 모뎀은 어디까지 빨라질 수 있나

음성 전화선은 대략 300~3400 Hz 대역만 통과시키고 잡음도 있습니다. 1990년대 모뎀은 2400, 9600, 14400, 28800 bps로 해마다 빨라졌습니다. 이 경쟁은 끝이 있을까요? 더 영리한 변조 방식을 쓰면 무한히 빨라질 수 있을까요? 대역폭과 잡음만 알면 답이 나오는 공식이 있습니다.

대역폭 $B$ [Hz]인 채널은 초당 약 $2B$개의 독립적인 표본을 실어 나를 수 있고(6장 나이퀴스트), 표본 하나가 구별할 수 있는 레벨 수는 잡음이 정합니다. 가우스 잡음이 더해지는 채널에서 이를 정확히 계산한 결과가 섀넌–하틀리 정리(Shannon–Hartley Theorem)입니다.

$$C = B\log_2\!\left(1+\frac{S}{N}\right)\quad[\text{bit/s}]$$

$S/N$은 신호 전력 대 잡음 전력비(SNR, 선형값). dB로 주어지면 $S/N = 10^{\mathrm{SNR_{dB}}/10}$. 높은 SNR에서는 $\log_2(1+S/N) \approx \mathrm{SNR_{dB}}/3.01$: SNR이 3 dB 좋아질 때마다 헤르츠당 1비트/초씩 늘어난다. 낮은 SNR에서는 $C \approx 1.44\,B\cdot S/N$으로 신호 전력에 비례한다.

이 공식은 두 방향의 놀라움을 담고 있습니다. 하나는 한계입니다. 어떤 변조·부호를 쓰더라도 $C$보다 빠르게 오류 없이 보낼 수는 없습니다. 다른 하나는 가능성입니다. $C$보다 느리기만 하면 오류율을 원하는 만큼 낮출 수 있습니다. 잡음은 속도를 제한할 뿐 신뢰성을 제한하지 않습니다.

SIMULATOR

대역폭과 SNR로 채널 용량 재기

예시 채널 대역폭 B SNR

용량 C—

스펙트럼 효율 C/B—

S/N (선형)—

1 GB를 보내는 최소 시간—

해볼 것: ① 전화선 프리셋: C ≈ 36 kbps. 아날로그 전화 구간을 그대로 지나는 V.34 모뎀의 최고 속도 33.6 kbps가 이 한계 바로 아래였다. ② SNR을 고정하고 B를 10배 늘리면 C도 10배, B를 고정하고 SNR을 10 dB 올리면 C/B가 약 3.3 bit/s/Hz만 늘어나는 것 비교: 대역폭은 비례, 전력은 로그로만 효과가 있다. ③ SNR을 0 dB 아래로 내려도 C가 0이 되지 않는 것 보기: 잡음보다 약한 신호로도 (느리게) 통신할 수 있다(GPS가 그렇다). · 모델: 대역 제한 가산 백색 가우스 잡음(AWGN) 채널. 가로선은 이상적 나이퀴스트 신호(심볼률 = B)에서 각 QAM 차수가 실어 나르는 bit/s/Hz로, 실제 시스템은 오류 정정 부호·보호 대역 등 때문에 그보다 낮다. 예시 채널의 SNR은 설명용 가정값이다.

섀넌 한계와 그 추격 비트당 에너지로 다시 쓰면, 대역폭을 무한히 써도 $E_b/N_0 \ge \ln 2$, 즉 −1.59 dB 아래로는 신뢰성 있는 통신이 불가능하다. 1993년 베루(C. Berrou) 등이 발표한 터보 부호가 이 한계에 1 dB 안쪽으로 다가가 학계를 놀라게 했고, 1960년대 갤러거(R. Gallager)가 제안했다가 잊혔던 LDPC 부호가 재발견되었다. 오늘날 5G NR은 데이터 채널에 LDPC, 제어 채널에 폴라 부호를 쓰고, Wi-Fi·DVB-S2·이더넷 일부·SSD 컨트롤러도 LDPC를 쓴다. 섀넌이 존재만 증명한 "용량에 다가가는 부호"를 실제 칩으로 만드는 데 약 반세기가 걸린 셈이다.

리드–솔로몬과 QR 코드: 점 몇 개로 곡선을 되살린다

비트가 아니라 덩어리로 사라진다

QR 코드가 찢기거나 얼룩이 지면 비트 하나가 아니라 근처 수십 개가 한꺼번에 사라집니다. CD의 긁힘, 무선의 순간 페이딩도 마찬가지인 버스트 오류(Burst Error)입니다. 해밍(7,4)처럼 블록당 1비트를 고치는 부호는 이런 오류에 속수무책입니다. 바이트 단위로 통째로 사라진 것을 되살리려면 다른 발상이 필요합니다.

1960년 리드(I. Reed)와 솔로몬(G. Solomon)의 아이디어는 고등학교 수학 하나에 기댑니다. 서로 다른 $k$개의 점을 지나는 $k-1$차 이하 다항식은 단 하나뿐이다. 두 점이 직선을, 세 점이 포물선을 정하는 것과 같습니다. 그러니 데이터 $k$개로 $k-1$차 다항식을 정하고, 그 곡선 위의 점을 $k$개보다 많은 $n$개 보내면 됩니다. 받는 쪽은 아무 점이든 $k$개만 살아 있으면 곡선을 되살리고 사라진 값을 모두 복원합니다.

$$f(x) = \sum_{i=1}^{k} y_i \prod_{j\ne i}\frac{x - x_j}{x_i - x_j}\qquad(\text{라그랑주 보간})$$

살아남은 점 $(x_i, y_i)$ $k$개만으로 다항식 전체를 다시 쓴다. 각 항의 곱은 $x_i$에서 1, 다른 $x_j$에서 0인 "선택 다항식"이다. 어디가 사라졌는지 아는 경우(소실, erasure)는 $n-k$개까지, 어디가 틀렸는지 모르는 경우(오류)는 $\lfloor (n-k)/2\rfloor$개까지 고칠 수 있다. 섞이면 $2e + s \le n-k$. 덧붙인 $n-k$개 기호를 이보다 효율적으로 쓰는 부호는 없다(싱글턴 한계를 등호로 만족).

SIMULATOR

다항식 부호: 점을 지우고 곡선 되살리기

데이터 점을 위아래로 끌기

클릭 동작

데이터 수 k (다항식 차수 k−1) 보내는 점 수 n 원래 곡선 보기(수신자는 모름)

살아남은 점 / 필요한 점—

소실 s, 오류 e—

보장 조건 2e + s ≤ n − k—

복호 결과—

—

해볼 것: ① k = 3, n = 7에서 "지우기"로 점을 하나씩 지워 4개(n − k)까지는 곡선이 그대로 복원되고, 5개째에 후보 곡선이 무수히 많아지는(흐린 곡선들) 것 확인. ② "오염"으로 점 하나를 틀린 값으로 바꾸면, 어디가 틀렸는지 모르는데도 나머지 점들이 다수결처럼 동의하는 곡선을 찾아 고치는 것 보기. 오염 2개(2e = 4 ≤ 4)까지는 보장된다. 점 3개를 지운 뒤 하나를 오염시키면(2·1 + 3 = 5 > 4) 똑같이 많은 점의 지지를 받는 곡선이 여럿 생겨 하나로 정할 수 없다. ③ "데이터 끌기"로 데이터 점을 움직여 덧붙인 점(주황)이 함께 움직이는 것: 덧붙인 값은 데이터가 정한 곡선의 연장이다. · 모델: 실수 위의 다항식으로 개념만 보인다. 데이터 k개를 x축의 고르게 흩어진 위치에 두는 체계적(systematic) 부호이고, 오류 복호는 살아남은 점에서 k개씩 고른 모든 조합을 보간해 가장 많은 점과 일치하는 다항식을 고른다(실제 칩은 벌레캄프–매시 알고리즘 등으로 훨씬 효율적으로 한다).

실제 리드–솔로몬은 실수가 아니라 유한체 위에서 동작한다 실수 다항식은 값이 커지고 반올림 오차가 생기며, 한 점의 값을 바이트 하나에 담을 수도 없다. 실제 RS 부호는 원소가 정확히 256개인 유한체 GF(2⁸)에서 계산한다. 각 원소가 바이트 하나이고, 덧셈은 XOR, 곱셈은 기약 다항식(QR 코드는 $x^8+x^4+x^3+x^2+1$)을 법으로 하는 다항식 곱셈이다. 이 체에서도 "$k$개 점이 $k-1$차 다항식을 유일하게 정한다"는 성질이 그대로 성립하므로 위 그림의 논리가 오차 없이 그대로 쓰인다. 기호가 바이트이므로 한 바이트 안의 8비트가 모두 틀려도 "오류 1개"로 센다. 버스트 오류에 강한 이유다.

QR 코드 안의 리드–솔로몬

QR 코드는 1994년 일본 덴소 웨이브가 공장 부품 추적용으로 개발했습니다. 내용은 8비트 부호어(codeword) 단위로 나뉘어 데이터 부호어 뒤에 RS 오류 정정 부호어가 붙고, 그림 전체에 흩어져 배치됩니다. 큰 심볼은 여러 RS 블록으로 나눈 뒤 부호어를 블록끼리 번갈아 섞어(인터리빙) 배치하므로, 한 귀퉁이가 찢겨도 손상이 여러 블록에 분산되어 각 블록의 정정 능력 안에 들어가기 쉽습니다.

그림 8-4. QR 코드 버전 1(21×21 모듈)의 구조 모식도. 세 귀퉁이의 파인더 패턴(위치 찾기), 타이밍 패턴(모듈 간격 측정), 형식 정보(오류 정정 레벨과 마스크 번호를 담으며 그 자체도 BCH 부호로 보호됨) 외의 영역에 데이터와 RS 부호어가 놓인다. 데이터 영역의 무늬는 임의로 채운 것으로 실제로 읽히는 코드가 아니다. 점선 부분처럼 일부가 가려져도 레벨에 따라 복원된다.

오류 정정 레벨	복원 가능한 부호어 비율(약)	버전 1의 데이터 / RS 부호어	주 용도
L (Low)	7%	19 / 7	깨끗한 인쇄, 최대 용량
M (Medium)	15%	16 / 10	일반 용도
Q (Quartile)	25%	13 / 13	공장·물류 환경
H (High)	30%	9 / 17	로고 삽입, 훼손 위험

버전 1은 총 26개 부호어를 담습니다. H 레벨에서는 26개 중 17개가 RS 검사 부호어라 데이터는 9바이트뿐이지만, 위치를 모르는 오류도 8개까지 고칠 수 있습니다. 가운데에 로고를 덮는 "디자인 QR"은 이 정정 능력을 일부러 소모하는 셈이라, 보통 H 레벨로 만들고 로고 면적을 정정 한도보다 넉넉히 작게 잡습니다. CD 역시 두 단계의 RS 부호를 인터리빙으로 엮은 CIRC를 써서 긁힘으로 인한 수천 비트의 연속 손실을 복원합니다.

교차 엔트로피: AI가 줄이는 바로 그 숫자

틀린 분포로 압축하면 얼마나 손해인가

허프만 부호를 영어 글자 빈도로 만들어 놓고 한국어 로마자 텍스트를 압축하면 어떻게 될까요? 실제 분포 $p$인 데이터를 다른 분포 $q$에 맞춘 부호(길이 $-\log_2 q_i$)로 보내면 평균 길이가 늘어납니다.

$$H(p, q) = -\sum_i p_i \log q_i = H(p) + D_{\mathrm{KL}}(p\,\|\,q), \qquad D_{\mathrm{KL}} \ge 0$$

$H(p,q)$를 교차 엔트로피(Cross-Entropy), 그 초과분 $D_{\mathrm{KL}}(p\|q) = \sum_i p_i\log(p_i/q_i)$를 쿨백–라이블러 발산이라 한다. 두 분포가 같을 때만 0이다. "틀린 모델로 세상을 볼 때 치르는 평균 놀라움의 추가분"이다.

분류 신경망의 학습이 정확히 이 숫자를 줄이는 일입니다. 정답이 "고양이"인 사진에서 실제 분포 $p$는 고양이에 1, 나머지에 0이므로 교차 엔트로피는 $-\log q_{\text{고양이}}$, 즉 모델이 정답에 준 확률의 놀라움 하나만 남습니다. 모델이 정답에 0.7을 주면 $-\ln 0.7 \approx 0.357$ nat(0.515 bit), 0.01을 주면 4.6 nat입니다. 확신하며 틀릴수록 손실이 폭발적으로 커집니다. 딥러닝 프레임워크는 보통 자연로그(nat)를 씁니다. 대형 언어 모델의 학습 손실도 "다음 토큰에 대한 교차 엔트로피"이고, 흔히 보고하는 퍼플렉서티(perplexity)는 그 지수 $e^{H}$입니다. 손실을 낮추는 것은 곧 데이터를 더 짧게 압축할 수 있는 모델을 만드는 것과 같습니다. 이 손실을 경사 하강법으로 줄이는 과정은 9장에서, 실제 모델 구조는 AIBook에서 이어집니다.

모델이 정답에 준 확률 q	0.99	0.9	0.7	0.5	0.1	0.01
교차 엔트로피 손실 −ln q [nat]	0.010	0.105	0.357	0.693	2.303	4.605

이 도구가 쓰이는 곳

정보 이론은 "데이터를 다루는 모든 기계"의 바닥에 깔려 있습니다. 시리즈의 다른 책에서 이 장의 도구를 만나는 곳들입니다.

NETWORKBOOK채널 용량 · 오류 정정
이더넷·Wi-Fi·광통신의 변조 차수와 FEC, CRC 오류 검출, 압축 프로토콜. PHONEBOOK5G 모뎀의 LDPC · 폴라 부호
SNR에 따라 변조·부호율을 바꾸는 링크 적응은 섀넌 용량을 따라가는 일이다. MEMORYBOOKDRAM ECC · NAND LDPC
(72,64) SECDED, 온다이 ECC, 다치 셀 플래시의 연판정 복호. COMPUTERBOOK부호화 · 압축 · 저장
허프만·LZ 압축, RAID 6의 리드–솔로몬 패리티, 문자 인코딩. AIBOOK교차 엔트로피 손실
분류·언어 모델의 학습 목표, KL 발산, 퍼플렉서티. SOCBOOK오류 정정 하드웨어
칩 안의 ECC 엔진, 고속 직렬 링크의 FEC, 영상·음성 코덱 블록. SENSORBOOK이미지 데이터와 잡음
센서 잡음이 정하는 유효 비트 수, 원본(RAW) 데이터 압축. MUSICBOOK오디오 압축
MP3·AAC 같은 손실 압축과 그 마지막 단계의 엔트로피 부호화.

MathBook 안에서는 7장 확률이 이 장의 재료이고, 채널 용량의 $2B$ 표본은 6장 샘플링, 해밍 부호의 행렬 $H$는 3장 선형대수, 교차 엔트로피를 줄이는 학습은 9장 최적화와 이어집니다. 유한체 GF(256)의 구조는 12장 대칭의 대수의 군·체 이야기와 맞닿아 있습니다.

핵심 정리

사건의 정보량은 놀라움 $I = -\log_2 p$ [bit]. 독립 사건의 정보가 더해지도록 로그를 쓴다. 반으로 가르는 예/아니오 질문 하나가 1비트이고, $N$개 중 하나를 고르려면 $\log_2 N$비트가 필요하다.
엔트로피 $H = -\sum p_i\log_2 p_i$는 정보원의 평균 놀라움이다. 균등할 때 최대 $\log_2 K$, 확실할 때 0.
무손실 압축의 평균 길이는 엔트로피 아래로 내려갈 수 없고, 허프만 부호는 $H \le \bar L \lt H+1$을 달성한다.
잡음 채널에서는 계획된 잉여를 넣어야 한다. 반복 부호는 오류를 줄이려면 전송률이 0으로 가지만, 섀넌은 $R \lt C$면 오류를 얼마든지 줄이는 부호가 있음을 보였다(BSC의 $C = 1-H_2(p)$).
해밍(7,4)은 겹치는 패리티 3개로 1비트 오류의 위치를 신드롬 $(s_4s_2s_1)$으로 직접 알려 준다. 최소 거리 3이라 2비트 오류는 잘못 고친다.
가우스 잡음 채널의 용량은 $C = B\log_2(1+S/N)$. 대역폭에는 비례, 신호 전력에는 로그로만 늘어난다.
리드–솔로몬 부호는 데이터 $k$개로 정한 $k-1$차 다항식의 값 $n$개를 보내고, 아무 $k$개로 복원한다. 소실 $s$·오류 $e$는 $2e+s \le n-k$까지 고친다. 실제로는 GF(256) 위에서 바이트 단위로 계산하며, QR 코드의 L/M/Q/H 레벨이 그 정정 능력(약 7/15/25/30%)이다.
교차 엔트로피 $H(p,q) = H(p) + D_{\mathrm{KL}}(p\|q)$는 틀린 모델의 대가이며, 분류·언어 모델 학습의 손실 함수다.

확인 퀴즈

확률이 1/8인 사건이 일어났다는 소식의 정보량은?

$-\log_2(1/8) = 3$. 1~8 중 하나를 맞히는 데 반으로 가르는 질문 3번이 필요한 것과 같은 계산이다.

네 기호의 확률이 (1/2, 1/4, 1/8, 1/8)일 때 허프만 부호의 평균 길이는?

부호 길이 1, 2, 3, 3 → 평균 0.5·1 + 0.25·2 + 0.125·3·2 = 1.75. 확률이 모두 2의 거듭제곱 꼴이면 −log₂p가 정수라 허프만이 엔트로피 H = 1.75에 정확히 도달한다. 어떤 무손실 부호도 H보다 짧을 수는 없다.

비트가 1% 확률로 뒤집히는 채널(BSC, p = 0.01)에 대한 설명으로 옳은 것은?

C = 1 − H₂(0.01) ≈ 0.919이므로 R = 0.9 < C. 섀넌의 채널 부호화 정리에 따라 오류 확률을 얼마든지 줄이는 부호가 존재한다. 1/11은 반복 부호를 고집할 때의 이야기다. 용량은 1 − p가 아니라 1 − H₂(p)다.

해밍(7,4) 부호어에서 위치 3과 위치 5의 비트가 동시에 뒤집혔다. 복호기는?

신드롬은 뒤집힌 위치 번호들의 XOR이다: 011 ⊕ 101 = 110 = 6. 복호기는 1비트 오류라고 믿고 6번을 뒤집는다. 2비트 오류를 검출만이라도 하려면 전체 패리티를 하나 더한 확장 해밍(SECDED)이 필요하다.

대역폭 1 MHz, SNR 0 dB(신호 전력 = 잡음 전력)인 가우스 잡음 채널의 용량은?

S/N = 10⁰ = 1이므로 C = 10⁶ · log₂(1 + 1) = 10⁶ bit/s. 잡음과 같은 세기의 신호로도 헤르츠당 1 bit/s를 보낼 수 있다.

데이터 4개(k = 4)로 3차 다항식을 정하고 그 값 8개(n = 8)를 보내는 다항식(리드–솔로몬식) 부호가 견딜 수 있는 손상은?

n − k = 4. 소실은 남은 점 4개만 있으면 되므로 4개까지, 오류는 어디인지도 찾아야 해서 2e ≤ 4, 즉 2개까지다. 섞이면 2e + s ≤ 4.