Prefix Property

예전 블로그 포스트에서 섀넌의 엔트로피를 한번 정리한 적이 있다. 그때 글에서 다루지 못한 몇 가지를 곁가지로 다뤄보려 한다.

섀넌 엔트로피와 볼츠만 엔트로피

임의의 확률 분포 $P = (p_{1}, p_{2}, \dots, p_{W})$ 에 대해 정의된 섀넌 엔트로피는 다음과 같다 (비례 상수를 고려해 로그의 밑을 일반화한 형태).

$H (P) = - \sum_{i = 1}^{W} p_{i} ln p_{i}$

여기서 통계역학의 근본 가정인 ‘등확률의 원리(Principle of Equal A Priori Probabilities)‘를 적용한다. 즉, 고립계에서 에너지가 같은 $W$ 개의 미시 상태가 존재할 때, 각 상태가 발생할 확률이 모두 균일하다고 가정하는 것이다.

$p_{i} = \frac{1}{W} (모든 i = 1, 2, \dots, W)$

이 조건을 섀넌의 엔트로피 식에 대입하면 다음과 같이 정리된다.

$H (P) = - \sum_{i = 1}^{W} (\frac{1}{W} ln \frac{1}{W})$

$= - \sum_{i = 1}^{W} (- \frac{1}{W} ln W) = ln W \sum_{i = 1}^{W} \frac{1}{W}$

$∴ H (P) = ln W$

여기에 열역학적 차원(J/K)을 부여하는 물리 상수인 볼츠만 상수 $k_{B}$ 를 곱하면 볼츠만의 엔트로피 공식이 정확히 유도된다.

$S = k_{B} H = k_{B} ln W$

즉, 볼츠만 공식은 ‘각 상태의 확률이 모두 동일한 특수한 경우( $p_{i} = 1/ W$ )‘에만 성립하는 섀넌 엔트로피의 특수해에 해당한다.

접두사 성질

섀넌의 엔트로피가 지닌 함의는 엔트로피가 낮은 정보 상태일 경우 이를 전달하는 신호 체계를 더 효율적으로 만들수 있다는 것이다. 그런데 문득 이런 의문이 들었다. 신호와 신호 사이를 어떻게 구별하지? 만일 이 구별을 위해 별도의 구분자가 필요하다면 낮은 엔트로피를 활용해 얻은 정보 전달의 효율성이 사라지지 않을까?

이때 활용하는 성질의 접두사 성질이다. 가변 길이 부호(Variable-length code)에서 비트 간 경계를 구분하기 위해 별도의 구분 기호(공백이나 쉼표)를 전송하지 않는다. 대신 ‘접두사 성질(Prefix Property)‘을 만족하는 부호 체계를 설계하여 비트 스트림 자체에서 모호성 없이 경계를 스스로 식별하도록 처리한다.

1. 접두사 부호 (Prefix Code) 원리

접두사 조건: 어떤 부호어도 다른 부호어의 앞부분(접두어, Prefix)이 되지 않아야 한다.
앞선 날씨 예시의 부호 체계:
- 맑음( $A$ ): 0
- 흐림( $B$ ): 10
- 비( $C$ ): 110
- 눈( $D$ ): 111
확인:
- 0으로 시작하는 다른 부호어는 없다 (10, 110, 111은 모두 1로 시작).
- 10으로 시작하는 다른 부호어는 없다 (110, 111은 11로 시작).
- 110과 111은 서로의 접두사가 아니다.

이 조건을 만족하면 비트열을 앞에서부터 1비트씩 순차적으로 읽어나가다가, 기존에 정의된 코드워드와 일치하는 순간이 오면 그 자리에서 즉시 단어를 끊어낼 수 있다(유일 디코딩 가능, Instantaneous Decodability).

2. 복호화(디코딩) 동작 과정 예시

전송된 비트열이 0101100111이라고 가정한다. 별도의 띄어쓰기가 없어도 수신 측은 다음과 같이 비트를 순차적으로 소비하며 해석한다.

첫 번째 비트 0 수신 $\to$ 0은 $A$ (맑음) 부호와 일치하므로 즉시 확정.
- 남은 비트: 101100111
다음 비트 1 수신 $\to$ 일치하는 부호 없음, 계속 읽음.
다음 비트 0 수신 $\to$ 10은 $B$ (흐림) 부호와 일치하므로 확정.
- 남은 비트: 1100111
다음 비트 1, 1 수신 $\to$ 일치 없음.
다음 비트 0 수신 $\to$ 110은 $C$ (비) 부호와 일치하므로 확정.
- 남은 비트: 0111
다음 비트 0 수신 $\to$ 0은 $A$ (맑음) 확정.
- 남은 비트: 111
다음 비트 1, 1, 1 수신 $\to$ 111은 $D$ (눈) 확정.

결과: 0 / 10 / 110 / 0 / 111 $\to$ $A$ (맑음), $B$ (흐림), $C$ (비), $A$ (맑음), $D$ (눈)으로 단 하나의 해석만 도출된다.

3. 이진 트리(Binary Tree) 구조를 통한 이해

접두사 코드는 이진 트리에서 모든 데이터(기호)를 리프 노드(Leaf Node, 잎 노드)에만 배치하는 방식과 동일하다.

Plaintext

       Root
      /    \
   (0)      (1)
   /          \
 [A]          Node
             /    \
          (0)      (1)
          /          \
        [B]          Node
                    /    \
                 (0)      (1)
                 /          \
               [C]          [D]

루트(Root)에서 출발하여 비트가 0이면 왼쪽, 1이면 오른쪽으로 이동한다.
리프 노드( $A, B, C, D$ )에 도달하면 해당 문자를 출력하고, 다시 루트로 돌아가 다음 비트를 읽는다.
어떤 기호도 다른 기호로 가는 경로의 중간에 존재하지 않으므로 구분을 위한 추가 메타데이터가 필요하지 않다.

lost-in-economics

Explorer