Source Coding Theorem

Summary

Source Coding Theorem은 메시지를 평균적으로 entropy보다 훨씬 짧게는 안정적으로 압축할 수 없다는 정리다.

핵심 insight

Entropy는 단순한 계산값이 아니라 압축의 바닥선이다. 평균 정보량이 3 bit라면, 아주 오래 많이 보낼 때 평균 3 bit보다 작게 줄이는 것은 불가능에 가깝다.

내용

source $X$의 entropy가 $H(X)$일 때:

• 평균 코드 길이를 $H(X)$에 아주 가깝게 만들 수 있다.
• 하지만 $H(X)$보다 작게 안정적으로 압축하면 정보가 손실되거나 복원이 실패한다.

즉:

$$\text{best average code length}\approx H(X)$$

예시

공정한 동전은 entropy가 1 bit다.

• 앞/뒤를 보내려면 평균적으로 1 bit가 필요하다.
• 앞=0, 뒤=1이면 딱 1 bit다.

반대로 거의 항상 앞면이 나오는 동전은 entropy가 1보다 작다. 이때는 여러 번의 결과를 묶어서 더 짧게 압축할 수 있다.

왜 중요한가

이 정리는 Shannon Code, Huffman coding, arithmetic coding 같은 압축 방법들의 목표를 정해준다.

관련 노트

• Entropy
• Shannon Code
• Channel Capacity