조금은 느리게 살자: 엔트로피로 불리는 평균 정보량(Entropy as Mean Information Content)

[경고] 아래 글을 읽지 않고 "엔트로피로 불리는 평균 정보량"을 보면 바보로 느껴질 수 있습니다.

[그림 1] 동전 던지기의 확률 변수 $X$에 대한 엔트로피 $H(X)$: 이진 엔트로피 함수 $H_b(p)$(출처: wikipedia.org)

사건 확률을 정의한 다음에 평균(mean)을 써서 특정 사건 $E$의 특성을 정량화하는 방식처럼, 정보량 $I(X)$를 가지고 평균을 구하고 이를 정보의 엔트로피(entropy) $H(X)$로 이름 붙인다. 섀넌Claude Elwood Shannon(1916–2001)의 제안을 명확히 하기 위해 섀넌 엔트로피(Shannon entropy)로 부르기도 한다.

(1a)

여기서 $X$는 사건 $E$의 이산 확률 변수(discrete random variable)이며 그 확률은 $p_i$ = $p(x_i)$ = $\operatorname{Pr}[X=x_i]$, $h(p)$ = $p I(p)$는 확률 $p$에 대한 엔트로피 성분(entropy component), $I(p)$는 $p$의 정보량이다. 엔트로피에 $H$를 쓴 이유는 에타(eta) $\eta$의 대문자가 H이기 때문이다. 특히 경우의 수가 0과 1로 2가지인 이진 사건(binary event)의 엔트로피는 이진 엔트로피 함수(binary entropy function) $H_b(p)$로 표현한다.

(1b)

(1c)

여기서 $p$는 이진 사건중 하나가 발생할 확률이다.

우리가 통신을 하는 목적은 정보원(information source)에서 많은 정보를 얻기 위함이다. 정보량은 확률과 로그 함수로 쉽게 정의하지만, 정보량만으로 최대 정보를 얻는 방법을 고안하기는 어려워서 식 (1)로 만든 엔트로피를 사용한다. 예를 들면, 정보원이 가진 원천 알파벳(source alphabet) $S$의 기호(symbol) $s_i$의 발생 확률(probability of occurrence) 혹은 발생 빈도수(frequency of occurrence)를 고려해서 엔트로피 $H(S)$가 최대가 되도록 부호화를 하면, 수신원에서 최대의 정보를 획득할 수 있다. 여기서 원천 알파벳은 $S$ = $\{s_1, s_2, \cdots \}$처럼 정보원이 쓰는 기호를 모두 모은 집합이다. 식 (1)처럼 엔트로피는 평균 정보량(mean information content)이기 때문에, 평균 정보량이 최대가 되도록 원천 알파벳을 구성하면 수신원은 평균적으로 많은 정보를 정보원으로부터 얻을 수 있다.

[그림 2] 엔트로피 성분 $h(p)$의 변화

평균 정보량의 최대값으로부터 평균 정보량을 물리학의 엔트로피로 부르는 이유를 파악할 수 있다. 먼저 엔트로피를 구성하는 엔트로피 성분 $h(p)$의 성질부터 분석한다. 극단적인 $p$ = $0$과 $1$에서 $h(p)$ = $0$이다. 계산이 잘 안되는 $p$ = $0$인 경우는 로피탈의 규칙(L'Hopital's rule)을 써서 $\lim_{p \to 0} h(p)$ = $-1/\log 2 \cdot \lim_{p \to 0} \log p \mathbin{/} (1/p)$ = $1/\log 2 \cdot \lim_{p \to 0} (1/p) \mathbin{/} (1 /p^2)$ = $0$을 얻는다. 또한 $h(p)$의 변화 특성은 $dh(p)/dp$로 확인한다.

(2)

그러면 기울기에 따라 $h(p)$는 ↗↘로 변하며 $p$ = $1/e$ = 0.367879$\cdots$에서 $h(p)$는 최대값 $\log_2 e \mathbin{/} e$ = 0.5307378$\cdots$을 가진다. 이로 인해 $p$ = $0, 1$을 제외한 확률에서는 항상 0보다 크다.

[그림 2]를 참고하면 엔트로피의 하한은 분명 $H(X) \ge 0$이다. 그러나 엔트로피의 상한은 쉽게 구해지지 않으므로, [그림 1]과 같은 베르누이 시행(Bernoulli trial)의 엔트로피 $H(X)$는 식 (1b)에 도입한 이진 엔트로피 함수 $H(X)$ = $H_b(p)$로 상한을 유추한다. 여기서 $p$는 베르누이 시행이 성공하는 확률이다. 식 (1b)의 미분 $dH(X)/dp$ = $dH_b(p)/dp$는 식 (2)로 쉽게 구한다.

(3)

따라서 $h(p)$처럼 $H(X)$도 ↗↘ 모양으로 변화한다. [그림 1]의 그래프가 명확히 보여주듯이 $H(X)$의 최대값은 $p$ = $1/2$에서 $\log_2 2$ = $1$로 나온다. 이상의 관찰을 바탕으로 엔트로피의 최대값과 최소값을 증명한다.

[엔트로피의 최대와 최소(maximum and minimum of entropy)]

(4)

여기서 $n$은 사건 개수, 엔트로피의 최대값은 균등 분포(uniform distribution)인 $p_i$ = $1/n$에서 발생한다.

[증명]
엔트로피 성분 $h(p)$는 항상 0보다 크거나 같아서 엔트로피의 최소값이 0임은 명백하다. 엔트로피의 최대값을 증명하기 위해 기브스의 부등식(Gibbs's inequality)을 활용한다. 이를 위해 $f(X)$ = $H(X) - \log_2 n$을 정의해서 기브스의 부등식 형태로 만든다.

(5)

따라서 엔트로피는 $\log_2 n$을 넘어설 수 없다.

______________________________

[그림 3] 입자가 무작위로 퍼져서 엔트로피가 증가한 모습(출처: wikipedia.org)

함수 $H(X)$가 최대가 되는 순간은 모든 사건 원소가 같은 확률인 $1/n$으로 구성되는 경우이다. 열 역학(thermodynamics)의 엔트로피는 경향성을 가지지 않고 무작위로 흩어질 때 최대가 된다는 성질과 식 (5)의 결과가 동일하기 때문에 $H(X)$를 정보의 엔트로피로 개념화한다.

엔트로피는 원천 부호화(source coding)의 한계를 나타내는 유용한 지표이다. 원천 부호화는 정보원이 만들어내는 기호(symbol)를 특정한 진법을 가진 부호(code)로 바꾸는 과정이다. 기호 원소 $s_i$를 담은 집합은 원천 알파벳(source alphabet) $S$ = $\{s_1, s_2, \cdots \}$가 되고, 부호 $c_i$를 원소로 하는 집합은 부호 알파벳(code alphabet) $C$ = $\{c_1, c_2, \cdots \}$로 부른다. 예를 들어, 이진 부호(binary code) 혹은 간단히 이진수(binary number)의 부호 알파벳은 $C$ = $\{c_1, c_2 \}$ = $\{0, 1 \}$이다.

[표 1] 4가지 기호(symbol)를 표현하는 부호어(codeword)의 구성 체계

기호 $s_i$ (Symbol)	발생 확률 $p_i$	고정 길이 부호 $W_1$ (유일 부호)	부호어 길이 $l_i$	가변 길이 부호 $W_2$ (유일 부호, 순시 부호)	가변 길이 부호 $W_3$ (유일 부호)
$s_1$	1/2	00	1	0	0
$s_2$	1/4	01	2	10	01
$s_3$	1/5	10	3	110	011
$s_4$	1/20	11	3	111	111

원천 부호화를 이해하기 위해 [표 1]처럼 4가지 기호를 가진 원천 알파벳 $S$ = $\{s_1, s_2, s_3, s_4 \}$를 이진 부호 $C$ = $\{0, 1 \}$로 나타내본다. 기호가 4개라서 이진수로 4가지를 표현하는 2비트 부호를 $s_1$ = $00$, $s_2$ = $01$, $s_3$ = $10$, $s_4$ = $11$처럼 선택할 수 있다. 이는 각 기호의 발생 확률이 동일하다고 가정하는 고정 길이 부호(fixed-length code)가 되기 때문에, 엔트로피는 최대값인 $H(S)$ = $\log_2 4$ = $2$비트로 나온다. 고정 길이 부호는 각 기호에 배정된 기호 개수가 변하지 않아서 붙여진 이름이며, 부호 모임이 동일한 크기의 블록 혹은 사각괴를 이루어서 블록 부호(block code)라 할 수도 있다. 각 기호에 대응하는 부호 모임은 부호어(codeword)라 이름 붙인다. [표 1]에 보인 예시로서 부호어 구성 체계 $W_1$의 기호인 $s_2$의 부호어는 $01$이다. 다른 관점으로 $s_i$의 발생 확률이 다르면 기호마다 부호 길이를 다르게 주는 가변 길이 부호(variable-length code)를 써서 평균 부호어 길이(average codeword length) $L$을 고정 길이 부호보다 더 짧게 만들 수 있다. 예를 들어, $s_i$의 발생 확률 $p_i$를 $p_1$ = $1/2$, $p_2$ = $1/4$, $p_3$ = $1/5$, $p_4$ = $1/20$으로 가정한다. 그러면 각 $s_i$에 부호어 길이(codeword length) $l_i$를 [표 1]의 $W_2$나 $W_3$처럼 배정할 수 있다. 여기서 부호어 길이는 정보량(information content)에 가깝게 선택한다. 따라서 [표 1]의 $W_2, W_3$ 부호어 구성 체계에 대한 평균 부호어 길이는 $L$ = 1.75비트, 엔트로피는 $H(S)$ = 1.68비트로 나온다.

(6)

다만 부호화(encoding)를 할 때는 복호화(decoding)를 반드시 고려해야 한다. 이를테면 [표 1]과 같이 가변 길이 부호를 구성하지 않고 $s_1$ = $0$, $s_2$ = $1$, $s_3$ = $10$, $s_4$ = $11$으로 해도 부호화가 가능하다. 평균 부호어 길이도 $L$ = 1.25비트로 [표 1]보다 훨씬 짧아진다. 하지만 이런 부호어 체계는 복호화에 문제가 생긴다. 가령 부호어가 $11$로 들어온 경우에 2개의 $s_2$인지 혹은 하나의 $s_4$인지 구별되지 않는다. 그래서 부호화를 할 때는 복호화가 유일하게 되도록 유일 복호화(unique decoding)를 지향해야 한다. 유일 복호화가 되는 부호는 유일 부호(unique code or uniquely decodable code)가 된다.

유일 복호화의 성질을 더 명확히 파악하기 위해, 정보원에서 수신원으로 정보가 전달되는 과정을 수학적으로 표현한다. 이진 부호화의 경우에 수신원에 들어오는 이진 수열은 0, 1로만 구성된다. 이 이진 수열을 복호화한다는 의미는 이진수로부터 기호를 찾아내서 $s_i s_j s_k s_l \cdots$처럼 나열한다는 뜻이다. 이런 기호의 나열에는 부호의 $n$차 확장($n$th extension of code)이란 명칭이 붙어있다. 부호의 $n$차 확장은 수신된 원천 부호(source code)를 적당히 병합(concatenation)하여 부호어를 만든 후 대응되는 원천 알파벳의 기호 $n$개를 일렬로 배치한 형태를 이른다. 원천 알파벳 $S$ = $\{s_1, s_2, \cdots, s_q \}$의 원소 개수가 $q$라면 $n$차 확장에 대한 경우의 수는 $q^n$이 된다. 따라서 부호어 체계가 유일 복호화 가능이라는 말은 임의로 선택한 원천 부호와 그 $n$차 확장이 항상 일대일 대응(one-to-one mapping)함으로 바꾸어 쓸 수 있다. 가령 [표 1]의 고정 길이 부호 혹은 블록 부호 $W_1$을 가정하면 수신열 $0110110011$의 $n$차 확장은 5차인 $s_2 s_3 s_4 s_1 s_4$만 가능해서 이 부호어 체계는 유일 복호화 성질이 있다. 이처럼 정상적으로 배정된 고정 길이 부호는 모두 유일 부호에 속한다. 반면에 $s_1$ = $0$, $s_2$ = $1$, $s_3$ = $10$, $s_4$ = $11$인 부호어 체계에서는 $n$차 확장이 7차인 $s_1 s_2 s_3 s_4 s_1 s_1 s_4$, 9차인 $s_1 s_2 s_2 s_1 s_4 s_1 s_1 s_2 s_2$ 등으로 다양하게 생길 수 있어서 유일 복호화가 되지 않는다.

(a) 유일 부호(unique code)이며 순시 부호(instantaneous code): [표 1]의 $W_2$ 부호어 구성 체계

(b) 유일 부호이지만 비순시 부호(non-instantaneous code)

[그림 4] 복호화 트리로 그린 순시와 비순시 부호의 예시: [표 1]의 $W_3$ 부호어 구성 체계

나열된 부호를 확장할 때, 각 부호어가 그 뒤에 나오는 부호와 관계없이 복호되는 부호를 순시 부호(instantaneous code)라 한다. [표 1]에서 부호어 체계 $W_2$는 순시 부호이지만 $W_3$는 순시 부호가 되지 않는다. 이를 판단하기에 좋은 도구는 [그림 4]에 보인 복호화 트리(decoding tree)이다. 복호화 트리에서 그 다음에 나오는 분기(branch)에 상관없이 원천 알파벳의 기호가 결정되어야 [그림 4(a)]와 같은 순시 부호가 된다. 순시 부호를 정의하는 복호화 트리로 인해 순시 부호는 자동적으로 유일 부호가 된다. 부호어 체계 $W_3$는 기호를 지정할 때 그뒤의 분기까지 고려해야 유일하게 기호가 정해지기 때문에, [그림 4(b)]처럼 순시가 아닌 비순시 부호(non-instantaneous code)로 판정된다. 복호화 트리를 쓰지 않고 순시와 비순시 부호를 구분하려면 부호어의 접두사(prefix)도 유용하다. 부호어 체계 $W_2$는 어떤 부호어의 접두사든지 다른 부호어의 접두사가 되지 않는다. 그러나 $W_3$는 반복되는 접두사가 $0$, $01$이 있어서 현재 분기까지만 봐서는 복호화가 되지 않는다. 예컨대 $s_1, s_2, s_3$는 접두사가 $0$으로 같고, $s_2, s_3$는 동일한 $01$ 접두사가 있다. 이러한 이유로 접두사로 구별되는 순시 부호를 강조해서 접두사 부호(prefix code)로 명하기도 한다. 주어진 부호어 길이 선택에 대해 순시 부호가 존재하는지를 알려주는 관계식으로 크래프트 부등식(Kraft inequality) 혹은 크래프트–맥밀런 부등식(Kraft–McMillan inequality)이 있다[2].

[크래프트 부등식(Kraft inequality)]

원천 알파벳 $S$ = $\{s_1, s_2, \cdots, s_q \}$의 각 기호 $s_i$를 부호 알파벳 $C$ = $\{c_1, c_2, \cdots, c_r \}$로 부호화해서 얻은 부호어 길이 $l_i$를 $l_1 \le$ $l_2 \le$ $\cdots$ $\le l_q$로 둔다. 그러면 이 부호어 구성 체계가 순시 부호를 가질 필요 충분 조건은 다음과 같다.

(7)

여기서 $l_i$는 $s_i$의 부호어 길이, $K$ = $1$은 복호화 트리의 분기를 기호 $s_i$가 빠짐없이 채울 때 발생한다.

[증명]
먼저 부호 알파벳을 $r$ = $2$인 이진수로 선택해서 유도의 첫발을 내딛는다. 부호어의 최대 길이가 1이라면, 원천 알파벳 $S$ = $\{s_1, s_2 \}$를 표현할 수 있다. 그러면 [그림 4(a)]와 같은 복호화 트리를 만들 수 있어서 순시 부호가 얻어지며, $l_i$ = $1$, $K$ = $1/2 + 1/2$ = $1$이 되므로 식 (1)이 성립한다.

[그림 5] 부호어 길이 $n$인 순시 부호로 $n+1$인 순시 부호를 구성

이 지점을 발판으로 수학적 귀납법(mathematical induction)을 적용한다. 식 (7)에 따라 최대 부호어 길이(maximum codeword length)가 $L_m$ = $n$일 때, 어떤 부호어 체계든지 $K \le 1$을 만족한다. 예를 들어, [그림 5]처럼 두 개의 부호어 체계에 대해 $K_1 \le 1$, $K_2 \le 1$이 각각 나온다. 그러면 최대 부호어 길이를 [그림 5]와 같이 $L_m$ = $n+1$로 확장한 경우, $K'$ = $1/2 \cdot K_1 + 1/2 \cdot K_2$ $\le 1$이 성립해서 증명이 완성된다. 여기서 앞 부분에 생긴 복호화 트리의 분기로 인해 $1/2$이 곱해지며 최대 부호어 길이도 $K_1, K_2$보다 1만큼 증가한다.

이번에는 부호 알파벳의 크기를 $r$로 둔다. 이럴 경우 복호화 트리의 분기가 만드는 곱은 $1/r$이다. 따라서 $K''$ = $1/r \cdot K_1$ $+$ $1/r \cdot K_2$ $+ \cdots +$ $1/r \cdot K_r$ $\le 1$을 만족하기 때문에, 부호 알파벳이 $r$진수가 되어도 식 (7)은 잘 들어맞는다.

______________________________

크래프트 부등식으로 순시 부호의 존재성을 판단할 수 있지만, 어떤 부호어 체계가 가장 최적의 순시 부호인지는 알 수 없다. 그래서 원천 알파벳 기호 $s_i$의 발생 확률 $p_i$로 최적 순시 부호를 만드는 방식을 고안한다. 즉, $p_1 \ge p_2 \ge \cdots \ge p_q$인 조건에서는 반드시 $l_1 \le l_2 \le$ $\cdots \le l_q$로 부호어 길이를 배정하는 방식이 효과적이다. 또한 최대 부호어 길이 $L_m$을 가진 기호는 하나일 수 없다. 한 예로서 [그림 4(a)]와 같은 이진 순시 부호(binary instantaneous code)는 $L_m$을 가진 기호가 항상 2개이다. 왜냐하면 순시 부호는 접두사 부호이기 때문이다. 다시 말해 $L_m$을 가진 기호가 하나라면 마지막 비트를 제외한 앞 부분 접두사는 다른 기호의 접두사와 다르다. 그러면 마지막 비트를 없애도 다른 기호와 구별되는 부호어가 만들어지므로, 실제 최대 부호어 길이는 $L_m - 1$이 되며 이 부호어는 $L_m-1$인 다른 부호어와 쌍을 이룬다.

[그림 6] 허프먼 부호화의 예시(출처: wikipedia.org)

최적 순시 부호를 만드는 방식을 알고리즘 형태로 정형화한 결과물이 허프먼 부호(Huffman code)이다[3]. 허프먼 부호를 생성하는 [그림 6]과 같은 허프먼 부호화(Huffman coding)는 높은 발생 확률의 기호에는 적은 부호어 길이, 낮은 발생 확률의 기호는 많은 부호어 길이를 배정하기 위해 다음처럼 축소와 확장 과정(reduction and expansion processes)을 따른다. 우선 축소 과정을 이진 순시 부호(binary instantaneous code) 기준으로 소개한다.

원천 알파벳 $S$ = $\{s_1, s_2, \cdots, s_q \}$의 발생 확률에 따라 내림차 순서로 기호를 정렬[오름차 순서와 발생 빈도도 가능]
발생 확률이 가장 낮은 기호, $s_{q-1}, s_q$를 선택해 하나로 합치며 $s_{q-1}'$로 표기함으로써 원천 알파벳을 축소
합쳐진 기호 $s_{q-1}'$의 발생 확률은 $p_{q-1}'$ = $p_{q-1} + p_q$로 설정
새로운 원천 알파벳 $S'$ = $\{s_1, s_2, \cdots, s_{q-2}, s_{q-1}' \}$에 대해 축소 절차를 반복
최종적으로 두 개의 기호가 남을 때까지 재귀적으로 진행

확장 과정은 축소 과정에 부호를 배정하면서 순차적으로 진행한다.

축소 과정을 시작한 $s_{q-1}, s_q$에 $0$과 $1$을 각각 부호로 배정
이전 축소 과정을 동일하게 따라가면서 축소가 일어난 기호에는 $0$과 $1$을 계속 추가함
이 과정을 원천 알파벳이 2개로 될 때까지 반복
확장 과정으로 인해 발생 확률이 낮은 기호는 많은 부호를 가지게 됨

[그림 6]은 알파벳과 공백을 가진 문장을 허프먼 부호로 바꾸는 방법을 보여준다. 발생 빈도를 헤아려서 오름차 순서로 늘어세운다. 첫번째로 C와 B의 빈도가 낮아서, 이 둘을 합한 기호를 CB로 두고 발생 빈도는 $2+6$ = $8$로 설정한다. 이를 다시 정렬하고 마지막 두 기호가 남을 때까지 되풀이한다. 확장 과정에서는 C와 B에 $0$과 $1$을 각각 배정한다. 다음 단계로 E와 CB에 $0$과 $1$을 배치하면, E는 $0$, C는 $10$, B는 $11$로 부호화된다. 이 과정을 끝까지 반복하면 [그림 6]에 나오는 7번처럼 각 알파벳과 공백이 이진수로 허프먼 부호화된다. 이상의 논의를 바탕으로 이진 순시 부호를 엔트로피와 연결한다.

[이진 순시 부호와 엔트로피]

이진 순시 부호에 대한 평균 부호어 길이 $L$의 하한은 원천 알파벳 $S$의 엔트로피 $H(S)$이다.

(8)

여기서 등호는 식 (7)에 유도한 $K$ = $1$일 때 나온다.

[증명]
식 (7)에 유도한 크래프트 부등식을 사용해서 가상의 확률 분포 $v_i$ = $1 \mathbin{/} (K \cdot 2^{l_i})$를 만든다. 이 확률 분포는 $\sum_{i=1}^q v_i$ = $1$이 되어서 확률의 공리를 만족한다. 새로운 확률 분포 $v_i$와 기호 $s_i$의 확률 분포 $p_i$에 대해 식 (5)처럼 기브스 부등식(Gibbs's inequality)을 적용한다.

(9a)

(9b)

______________________________

위 증명은 이진 부호를 다루고 있지만, 동일한 방식을 활용해서 $r$진수에 대해서도 성립함을 보일 수 있다. 또한 [그림 6]에 예로 든 허프먼 부호는 대부분의 경우에 엔트로피와 거의 비슷한 평균 부호어 길이가 나온다. 따라서 허프먼 부호는 매우 효율적인 이진 순시 부호이다.

허프먼 부호와 비슷하지만 살짝 다른 섀넌–파노 부호(Shannon–Fano code)도 있다. 이 부호는 허프먼 부호와 같이 순시 부호에 속한다. 파노Robert Fano(1917–2016)는 임피던스 정합(impedance matching)의 한계인 보디–파노 기준(Bode–Fano criterion)의 증명자로 유명하다. 허프먼 부호화는 각 기호의 부호를 정하고 부호어 길이를 결정하지만, 섀넌–파노 부호화(Shannon–Fano coding)는 다음처럼 정보량으로 먼저 부호어 길이 $l_i$를 선택한 후 각 기호의 부호를 선정한다.

(10)

여기서 $I(p_i)$ = $\log_2 (1/p_i)$는 발생 확률 $p_i$의 정보량이다. 섀넌–파노 부호의 존재성을 확인하기 위해 크래프트 부등식을 확인한다. 우선 식 (10)에 지수 함수 $2^x$를 적용해서 역수를 취한다.

(11a)

식 (7)과 같은 형태로 만들기 위해 모든 기호 $s_i$에 대해 식 (11a)의 오른쪽 식을 더한다.

(11b)

따라서 섀넌–파노 부호는 크래프트 부등식을 만족하므로, 식 (10)으로 구성되는 순시 부호가 존재한다. 다음 수순으로 섀넌–파노 부호의 평균 부호어 길이 $L_\text{SF}$와 엔트로피 $H(S)$에 대한 부등식을 유도한다.

[섀넌–파노 부호의 평균 부호어 길이 $L_\text{FS}$와 엔트로피의 관계]

(12)

[증명]
각 기호 $s_i$의 발생 확률 $p_i$를 식 (10)에 곱하고 더해서 평균 부호어 길이 $L_\text{SF}$를 만든다.

(13)

여기서 모든 기호의 발생 확률을 더하면 1이 된다.

______________________________

모든 이진 순시 부호의 평균 부호어 길이는 엔트로피보다 크기 때문에 식 (12)의 좌변은 당연한 결론이다. 하지만 식 (12)의 우변처럼 섀넌–파노 부호는 $L_\text{SF}$의 상한이 존재하는 지점이 재미있다. 식 (10)처럼 부호를 배당하는 경우, 평균 부호어 길이는 엔트로피보다 많아야 1비트 정도만 길어진다. 다만 섀넌–파노 부호의 경우보다 더 복잡한 알고리즘을 쓰는 허프먼 부호의 평균 부호어 길이 $L_{H}$가 통상적으로 더 짧다. 이를테면, $S$ = $\{ s_1, s_2\}$인 원천 알파벳의 $L_{H}$는 당연히 1비트이다. 그러나 $p_1$ = $1/2^k$, $p_2$ = $1- 1/2^k$인 경우에 $L_\text{SF}$ = $k/2^k$ $+$ $1 \cdot(1- 1/2^k)$ = $1 + (k-1)\mathbin{/}2^k$가 된다. 조건 $k \ge 2$에서 발생 확률이 차이나는 경우[$p_1 \ne p_2$]에 $L_\text{SF}$는 $L_{H}$보다 더 길어진다.

현실에서는 허프먼 부호가 많이 쓰이지만 섀넌–파노 부호를 중요하게 생각하는 이유는 식 (12) 때문이다. 식 (12)를 활용해서 원천 알파벳의 $n$차 확장이 가진 근원적 한계인 섀넌의 원천 부호화 정리(Shannon's source coding theorem)를 증명한다. 여기서 원천 알파벳의 $n$차 확장은 $s_{i_1}s_{i_2}\cdots s_{i_{n-1}}s_{i_n}$처럼 임의 기호 $s_i$를 연속적으로 보내고 받는 자료 통신(data communication)을 상징한다. 먼저 원천 알파벳의 $n$차 확장 $S^n$과 엔트로피 $H(S^n)$의 관계부터 파악한다. 각 기호의 나열이 생성하는 $n$차 확장은 서로 독립이기 때문에, 정보량의 성질에 의해 $n$차 확장의 정보량은 각 기호 정보량의 합이 된다. 따라서 다음 유도에 의해 $H(S^n)$ = $n H(S)$가 성립한다.

(14a)

(14b)

이 결과는 곧바로 모든 순시 부호에 대해 성립하는 기호당 평균 부호어 길이는 엔트로피에 근접한다는 섀넌의 원천 부호화 정리에 연결된다.

[섀넌의 원천 부호화 정리(Shannon's source coding theorem)]

임의 순시 부호의 $n$차 확장은 다음과 같은 성질을 가진다.

(a) $n$차 확장의 평균 부호어 길이 $L_n$은 $nH(S)$ 모양으로 발산한다.

(b) 차수 $n$이 커짐에 따라 손실 없이 압축하려면 최소 $nH(s)$ 비트를 할당해야 한다.

(c) 역으로 $nH(s)$ 비트 이하로 압축된 자료는 정보가 손실될 수 있다.

(15)

여기서 $L_n$은 원천 알파벳의 $n$차 확장 $S^n$이 가진 평균 부호어 길이, $H(S)$는 원천 알파벳 $S$의 엔트로피이다.

[증명]
일단 정보량 조건에 부합하는 순시 부호로 섀넌–파노 부호를 선택해서 식 (12)를 $n$차 확장에 적용한다.

(16)

여기서 $H(S^n)$ = $n H(S)$이다. 차수 $n$이 커질수록 부등식의 간격은 0으로 가기 때문에, 조임 정리(squeeze theorem)에 의해 $L_n/n$의 극한은 $H(S)$가 된다. 이때 부호어 길이를 정보량으로 선택할 때의 길이 상한은 식 (10)처럼 1비트일 필요는 없다. 어떤 값이든지 유한한 비트라면 식 (16)과 같은 극한에 의해 식 (15)가 나온다. 나아가 식 (15)로 인해 아무리 압축을 해도 기호당 평균 부호어 길이 $L_n/n$은 $H(S)$보다 작아질 수 없다. 따라서 정보를 잃지 않으면서 압축을 하려면 최소한 $H(S)$ 이상의 비트를 각 기호에 배분해야 한다.

______________________________

비슷한 예로 섀넌–파노 부호와 다르지만 정보량에 근접하게 부호어 길이를 정하는 허프먼 부호도 $n$차 확장을 하면, 식 (15)에 따라 그 평균 부호어 길이는 엔트로피에 정확히 수렴한다. 또한 원천 알파벳의 $n$차 확장은 원천 알파벳에서 무작위로 선택하는 기호의 나열이기 때문에 독립 항등 분포(independent and identical distribution, i.i.d.)인 $n$개의 확률 변수(random variable)라 정의해도 무방하다. 게다가 우리가 원하면 언제든 오류 없이 원천 부호화를 할 수 있어서 섀넌의 원천 부호화 정리의 조건을 잡음이 없는 상태로 가정할 수 있다. 그래서 섀넌의 원천 부호화 정리를 무잡음 부호화 정리(noiseless coding theorem)로 부르기도 한다.

현재까지 엔트로피에 대한 논의는 정보원이 기호를 이산 확률 변수(discrete random variable)에 따라 이산적으로 발송한다고 가정한다. 이산 신호(discrete signal) 혹은 디지털 신호(digital signal) 외에 연속적으로 변하는 연속 신호(continuous signal) 혹은 아날로그 신호(analog signal)도 존재한다. 이런 연속 신호에 쓰이는 연속 확률 변수(continuous random variable) $X$를 위한 연속 엔트로피(continuous entropy) $H_c(X)$는 리만 적분(Riemann integral)의 정의를 차용한다. 먼저 식 (1)의 기호 개수를 무한대로 보내는 극한으로 리만 적분을 생성한다.

(17a)

여기서 $x_i$ = $i \Delta x$, $\Delta x$ = $x_{i+1} - x_i$ = $a/N$, $2a$ = $x_\max - x_\min$; 연속 확률 변수 $X$가 발생하는 확률 밀도 함수(probability density function, PDF)는 $p_X(x)$, $p_X(x)$로 만드는 이산 확률 변수의 확률 질량 함수(probability mass function, PMF)는 $p(x_i)$ = $p_X(x_i)\Delta x$이다. 식 (17a)의 마지막 항은 정적분으로 바꾸더라도 피적분 함수가 무한대로 발산한다. 그러면 식 (17a) 전체가 발산해서 연속 엔트로피를 정상적으로 이끌어낼 수 없다. 결국 식 (17a)에서 발산하는 항을 버리고 상대 엔트로피(relative entropy)만 선택한다. 또한 연속 확률 변수의 범위 $2a$를 무한대로 바꿈으로써 연속 엔트로피 $H_c(X)$를 일반화시킨다.

(17b)

하지만 식 (17a)의 논증에 따라 연속 엔트로피는 절대성을 잃고 서로 크다 혹은 작다만 비교 가능하다. 이는 식 (1)에 도입한 엔트로피의 정의에 기인한다. 즉, 기호 개수가 무한대로 가기 때문에 평균 정보량도 계속 발산할 수밖에 없다.

라그랑주 승수(Lagrange multiplier)를 활용해서 연속 확률 변수 $X$가 가진 연속 엔트로피 $H_c(X)$의 특성을 다양하게 규정할 수 있다.

유한 범위의 $X$: 범위 $a \le x \le b$에서 변하는 $X$의 연속 엔트로피는 균일 분포(uniform distribution)인 $p_X(x)$ = $1 \mathbin{/} (b-a)$에서 최대가 되며 $\max[H_c(X)]$ = $\log_2 (b-a)$
분산이 고정된 $X$: 분산이 $\sigma^2$인 $X$는 정규 분포(normal distribution)인 $1 / (\sqrt{2 \pi} \sigma) \cdot e^{-x^2/(2 \sigma^2)}$에서 연속 엔트로피가 가장 크며, 최대값은 $\max[H_c(X)]$ = $\log_2 (\sqrt{2 \pi e} \sigma)$

이런 연속 엔트로피는 아날로그 신호의 채널 용량을 정의할 때도 적극적으로 쓰인다.

[참고문헌]

[1] C. E. Shannon, "A mathematical theory of communication", Bell System Tech. J., vol. 27, pp. 379–423, 623–656, Jul., Oct. 1948.

[2] L. G. Kraft, A Device for Quantizing, Grouping, and Coding Amplitude Modulated Pulses, M.S. Thesis, MIT, MA, USA, 1949.

[3] D. A. Huffman, "A method for the construction of minimum-redundancy codes," Proc. IRE, vol. 40, no. 9, pp. 1098–1101, Sep. 1952.

[4] R. W. Hamming, Coding and Information Theory, 2nd ed., Englewood Cliffs, NJ, USA: Prentice-Hall, 1986.

[다음 읽을거리]

1. 통신을 지배하는 상호 정보

2. 채널 용량과 정보 전송의 한계

3. 라그랑주 승수