출처 → 채널: 2단계 부호화
해밍의 10장은 정보를 이동시키는 모든 시스템에 적용되는 섀넌의 통신 모델로 시작합니다: 전화 통화, 라디오, 하드 드라이브, DNA 복제, 컴퓨터 메모리.
2단계 아키텍처
1단계: 소스 부호화(압축). 소스 메시지를 압축된 표현으로 변환합니다. 목표: 소스에 내재된 중복성을 제거합니다. 모스 부호가 이를 수행합니다: 일반적인 문자는 짧은 코드를 얻고, 드문 문자는 긴 코드를 얻습니다.
2단계: 채널 부호화(오류 보호). 채널의 잡음 특성에 맞춘 제어된 중복성을 추가합니다. 잡음이 있는 전화선은 광섬유 케이블보다 더 많은 중복성이 필요합니다. 2단계는 분리됩니다: 각각을 고유한 작업에 대해 독립적으로 최적화합니다.
2단계 간의 공통 인터페이스 — 표준화된 비트 스트림 — 은 모든 소스가 모든 채널과 쌍을 이룰 수 있음을 의미합니다. 이 모듈화는 섀넌의 핵심 건축 통찰입니다.
저장소를 통신으로. 해밍은 공간을 통해 메시지를 보내는 것(전송)과 시간을 통해 보내는 것(저장)이 같은 모델을 사용한다고 지적합니다. 백업 드라이브는 시간의 잡음이 있는 채널입니다.
잡음의 역할
섀넌의 모델은 급진적인 가정을 합니다: 잡음은 불가피합니다. 모든 채널, 모든 저장 매체, 모든 스위칭 회로는 어느 정도의 오류 확률을 도입합니다. 문제는 '잡음을 어떻게 제거할 것인가?'가 아니라 '잡음에도 불구하고 원래 메시지를 어떻게 복구할 것인가?'입니다.
이는 잡음이 사후 사항으로 들어오는 고전 물리학과 대조됩니다(불확실성 원리). 섀넌은 잡음을 기초 조건으로 취급합니다 — 모든 이론이 이것으로부터 구축됩니다.
지금은 10장이 무잡음 경우에 초점을 맞춥니다: 오류 없는 소스 부호화. 채널 부호화 문제(오류 정정)는 나중 장에서 기다립니다.
언제 고유하게 디코딩할 수 있습니까?
가변 길이 부호가 유용하려면, 수신자는 비트 스트림을 명확하게 디코딩해야 합니다. 해밍은 이 테스트를 실패하는 4-기호 부호로 설명한 후, 수정을 소개합니다: 접두사 없는 부호.
접두사 없는 조건
코드는 접두사 없는(또는 즉시) 경우 어떤 코드워드도 다른 코드워드의 접두사가 아닙니다. 수신된 비트 스트림이 주어지면, 디코딩 트리에서 리프에 도달하는 순간 기호가 끝났음을 알 수 있습니다 — 선제 필요 없습니다.
예 {s1, s2, s3, s4}의 접두사 없는 부호: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
확인: 0은 10, 110 또는 111의 접두사가 아닙니다. 10은 110 또는 111의 접두사가 아닙니다(10 다음에 더 많은 비트가 있으면 100... 또는 101...이 되고, 둘 다 110 또는 111로 시작하지 않습니다). 부호가 규정을 만족합니다.
디코딩 절차: 트리를 따르고, 각 들어오는 비트에서 분기하고, 리프에 도달할 때 기호를 내보내고, 루트로 돌아갑니다.
크래프트 부등식
길이 l_1, l_2, ..., l_n의 접두사 없는 이진 부호의 경우:
Σ 2^(−l_i) ≤ 1
코드가 완전할 때(리프가 중복 없이 전체 이진 트리를 채울 때) 동등성이 성립합니다. 이는 필요한 조건입니다: 접두사 없는 부호는 이를 위반할 수 없습니다. 역으로, 크래프트 부등식을 만족하는 모든 길이 집합에 대해 접두사 없는 부호가 존재합니다.
크래프트 부등식 적용
코드 길이가 주어지면, 크래프트를 확인하십시오: Σ 2^(−l_i) ≤ 1.
{s1=0, s2=10, s3=110, s4=111}의 경우: 길이는 1, 2, 3, 3입니다.
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓
섀넌 엔트로피
가변 길이 부호의 평균 코드 길이: L = Σ p_i · l_i, 여기서 p_i는 기호 s_i의 확률이고 l_i는 코드 길이입니다.
L이 얼마나 짧을 수 있습니까? 섀넌의 답: 소스 엔트로피 이하가 아닙니다.
섀넌 엔트로피: H = −Σ p_i · log₂(p_i) (단위: 비트/기호)
엔트로피는 기호당 평균 정보를 측정합니다. 높은 엔트로피는 기호가 대략 동일할 가능성을 의미합니다(최대 예측 불가능). 낮은 엔트로피는 일부 기호가 지배함을 의미합니다(높은 예측 가능성, 더 압축 가능).
무잡음 부호화 정리
접두사 없는 부호의 경우, H(소스) ≤ L ≤ H(소스) + 1.
부호는 엔트로피를 이길 수 없습니다. 허프만 부호화(다음 장)는 상한을 달성합니다: L < H + 1. 블록 부호의 경우 n개 기호에 대해 경계가 조여집니다: H ≤ L/n < H + 1/n.
엔트로피는 또한 이론적 압축 한계입니다: 정보를 잃지 않고 소스를 기호당 H 비트 이하로 압축할 수 없습니다.
엔트로피 계산
예: 확률 p = [1/2, 1/4, 1/8, 1/8]인 4개 기호.
H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)
= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3
= 0.5 + 0.5 + 0.375 + 0.375 = 1.75 비트/기호
그리고 허프만 부호 {0, 10, 110, 111}은 L = 1.75 = H를 정확히 달성합니다.
엔트로피가 하한인 이유
무잡음 부호화 정리의 하한은 단순한 공식이 아닙니다 — 정보에 대해 깊은 무언가를 반영합니다: 이미 최대 예측 불가능한 것을 압축할 수 없습니다.
모든 기호가 동일할 가능성이 있을 때(균등 분포), 엔트로피 H = log₂(n)은 n개 기호입니다. log₂(n) 비트 길이의 블록 부호가 정확히 H를 달성합니다. 어떤 부호도 더 잘할 수 없습니다.
한 기호가 지배할 때(예, p(A) = 0.99, p(B) = 0.01), H는 작습니다 — 0에 가깝습니다. 가변 길이 부호는 A에 매우 짧은 부호를 할당할 수 있고, 스트림을 매우 효율적으로 인코딩할 수 있습니다.
실질적인 요점: 큰 압축 이득은 기호 확률이 상당히 다를 때만 존재합니다. 소스가 이미 '균등'(무작위처럼 보임)이면, 허프만 부호화는 이득이 없습니다.