세 기호 A, B, C 확률은 1−2ε, ε, ε이며 0<ε<1/3입니다. 각 기호에 하나의 비어 있지 않은 이진 부호어를 고정해 이어 붙이는 prefix 부호만 허용해요. 즉 어떤 부호어도 다른 부호어의 앞부분이 아니에요. 이 조건에서 최소 평균 길이는 얼마인가? 아래 엔트로피가 ε→0일 때 0으로 가므로 기호별 부호의 최소 평균 길이도 0으로 가나요?
세 기호가 모두 양수 확률이므로 각 부호어를 실제로 써야 해요. 한 비트인 부호어 0과 1을 둘 다 쓰면 다른 어느 부호어도 그 둘 중 하나로 시작해 prefix 조건을 어겨요. 따라서 길이 1 부호는 많아야 하나이며 나머지 둘은 최소 2입니다. 길이 1이 없으면 평균은 2 이상이에요. 있다면 그 자리에 가장 큰 확률 1−2ε인 A를 두는 것이 최소예요. 그러므로 다음 하한을 얻고 0, 10, 11 부호로 실제로 달성해요.
반면 −εlog₂ε→0이고 −(1−2ε)log₂(1−2ε)→0라 H→0입니다. ε=1/16에서는 최소 평균 9/8 bit이고 H=1/2+(7/8)log₂(8/7)<1입니다. entropy라는 하한이 존재하는 것과 기호별 정수 길이 부호가 그 하한을 달성하는 것은 달라요. 기호 여러 개를 묶어 하나의 부호어를 만드는 block 부호는 지금 허용한 기호별 부호와 다른 설계 범위예요.
실제 강의는 entropy와 부호 평균 길이 및 기호별 정수 길이의 차이를 설명해요. 현재는 원문의 이진 .99/.01 예를 바꾸지 않고 세 기호 ε 가족에서 모든 prefix 부호의 구조적 하한과 달성 부호를 직접 증명했어요. bit는 본문 부호의 길이이며 전체 파일 헤더나 실제 압축 소프트웨어의 측정값이 아니에요.
최소라는 결론을 쓰려면 모든 허용 부호에 적용되는 하한과 그 값을 달성하는 실제 부호를 둘 다 확인해 봐요. 어느 단위의 블록을 부호화하는지 바꾸지 않은 채 entropy 하한만으로 실제 1회 부호 길이를 확정하지 않아요.
착안 원문: Stanford EE376A, Lecture6: Kraft-McMillan Inequality and Huffman Coding (25 January2018). 세 기호의 확률 ε 가족과 기호별 부호 길이의 하한·달성 증명은 자체 작성했으며, 원문의 엔트로피 정의와 구별해 사용했어요.