제 7 장

소스코딩의 한계

7-1  Entropy와 평균 코드길이

이 장에서는 제6장에서 정의한 Entropy Hr(S)와 임의의 소스코딩에 의하여 주어지는 평균 코드길이 L 사이에 성립하는 기본적인 관계식들을 유도하고자 한다.

	정보공학

제 7 장 Entropy와 Shannon의 기본정리

우리는 이미 제6장에서 실질적으로 사용되는 여러 가지 코드체계들이 아무리 효율적으로 구성되더라도 그 평균 코드길이가 Entropy 보다는 작아지지 않음을 확인한 바 있다. 그러나 이것은 지금까지 논의되었던 방법을 적용하였을 경우에 나타나는 결과일 뿐, 그러한 사실을 일반적인 특성으로 규명한 것이라고 말할 수는 없다. 따라서 지금까지의 결과만 가지고는, 앞으로 어떤 새로운 소스코딩의 방법이 개발되었을 때, 그 평균 코드길이가 Entropy 보다 작아질 수 있는지 혹은 그렇지 않은지 확신할 수 없다. 더구나 주어진 소스알파벳을 확장한 상태로 인코딩하는 경우나 심볼 간의 상관관계를 고려한 Markov 과정이 적용될 경우에는 더욱 그러하다.

이 장의 목적은 바로 소스코딩에 대한 한계를 수학적으로 규명하고자 하는 것이다. 결론부터 말하면, 임의의 방법으로 구성된 모든 소스코드 체계의 평균 코드길이는 그 소스알파벳이 갖는 Entropy 보다 작아질 수 없다. 여기서 말하는 소스코드 체계에는 독립적인 발생확률 만 사용하는 방법을 비롯하여 확장된 코드체계 및 Markov 과정을 적용한 체계 등 가능한 모든 방법에 의한 것들을 전부 포함한다.

우리는 먼저 임의의 동시코드(instantaneous code)에 대하여 이 사실을 규명할 것이다. 이어서 확장된 코드(extended code)를 고려하고자 하는데, 이를 용이하게 취급하기 위하여 새로운 코드체계를 한 가지 소개하게 된다. 이것이 Shannon-Fano 코드이다. 뒤에서 상세히 설명하겠지만, Shannon-Fano 코드는 제4장에서 논의된 Huffman 코드에 비하여 효율성이 떨어지므로 실질적인 소스코드 체계로 사용하기는 어렵다. 그러나 그 특성 상 정보이론의 개념을 설명하기에는 매우 적합하여 이론적인 접근에 널리 쓰인다. 우리는 이 체계를 이용하여 소위 □무잡음 코딩정리(noiseless coding theorem)□를 확립하게 된다. 마지막으로 우리는 이른바 Markov 과정으로 이루어 지는 시스템의 Entropy를 정의하고, 이를 적용한 소스코드의 효율성도 Entropy 라는 한계를 벗어나지 못함을 설명하고자 한다.

결국 Entropy는 그 시스템이 갖는 근본적인 정보의 양으로서, 최소한 이를 함유하고 있는 코드체계 만이 주어진 정보를 모두 포함한다고 말할 수 있는 것이다. 우리는 이 장의 결론으로 Entropy의 강력성을 논의하고자 한다.

7-2  동시코드에 대한 고찰

우리는 제4-2절에서 유일디코딩과 동시디코딩의 원리를 소개하면서 임의의 소스코드 체계가 동시코드(instantaneous code)로 되지 못하면 실질적인 코드로 사용될 수 없음을 설명한 바 있다. 따라서 정보의 전송이나 저장에 사용되는 모든 코드체계는 동시코드로 구성되어야 한다. 또한 제4-3절에서는 임의의 소스알파벳에 대하여 인코딩된 코드체계가 동시코드로 되기 위하여 만족해야 하는 Kraft 부등식(4-5)을 소개하였다. 이것은 단지 구성된 각 코드의 길이에 관한 조건을 제시하고 있으나, 실질적인 모든 소스코드가 만족해야 하는 동시디코딩 특성을 한정하고 있기 때문에 우리의 고찰에서 매우 유용하게 쓰인다.

이러한 성질을 기반으로, 임의의 동시코드 체계의 평균 코드길이와 그 Entropy 사이에 다음과 같은 정리를 세울 수 있다.

정리 1  □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

소스알파벳과 각 심볼의 발생확률이 다음과 같이 주어진다고 가정하자.

[eqn: S ``= \{`s_1 ,` s_2 ,` cdots,` s_q `\} `, ~ p_i `=Pr \{` s_i ~ \occurs \}, `i`=`1,`2,` cdots,` q]	(7-1)

이를 인코딩한 임의의 이진 동시코드의 평균 코드길이

[eqn: L_\av ~=` sum_i=1^q ``p_i ``l_i]	(7-2)

와 시스템의 Entropy

[eqn: H_2 `(S) ~=` sum_i=1^q ``p_i ```log_2 `1 over p_i]	(7-3)

사이에는 다음과 같은 관계식이 성립한다.

[eqn: L_\av ~>=~ H_2 `(S)]	(7-4)

♠ 증명

주어진 코드체계의 코드길이가 각각 li(iＡ1, 2, …, q)로 표시되며, 이진(radix-2)코드로 인코딩된 동시코드라 하면, 제4-3절의 Kraft 부등식(4-5)을 만족하여야 함으로

[eqn: K ~Ａ`` sum_i=1^q ``1 over 2^l_i``□``1]	(7-5)

이라 표시할 수 있다.

이 식을 이용하여 하나의 가상 확률분포(pseudo probability distribution)를 다음과 같이 정의한다.

[eqn: Q_i ~Ａ 1 over {K cdot 2^l_i } `, ~ i``Ａ`` 1,` 2,` cdots, `q]	(7-6)

이 확률분포는 실제로 어떤 심볼들이 발생되는 확률을 표시하는 것이 아니고, 단지 이 정리를 입증하기 위하여 도입된 것이므로 가상 확률분포라 하였다. 그러한 이것이 확률분포로서의 자격을 갖추기 위해서는 식(1-37)에 주어진 기본적인 조건을 만족하여야 할 것이므로 다음과 같이 검토되어야 한다.

[eqn: sum_i=1^q`` Q_i ~Ａ` sum_i=1^q 1 over {K cdot 2^l_i} ~Ａ` 1 over K ` sum_i=1^q`` 1 over 2^l_i ~=~ 1 over K cdot K ~=~ 1]	(7-7)

검토 결과 이 가상분포는 하나의 확률분포로 취급될 수 있음을 알 수 있다.

따라서 주어진 발생확률의 분포 pi와 식(7-6)의 가상 확률분포 Qi에 대하여 제6장의 정리 2에서 증명된 Gibbs 부등식(6-55)을 적용하면

[eqn: sum_iＡ1^q `` p_i ``log_2 ``Q_i over p_i ~<= ~ 0]	(7-8)

와 같은 부등식을 얻는다.

이 식의 좌변을 로그함수의 규칙에 따라 정리하면

[eqn: H_2 `(S) ~=` sum_i=1^q `` p_i ``log_2 `` 1 over p_i ~<=~ sum_i=1^q ``p_i ``log_2 ``1 over Q_i]	(7-9)

와 같이 나타난다.

이 식의 우변에 가상 확률분포의 정의 식(7-6)을 대입하여 정리하면

[eqn: sum_i=1^q ``p_i ``log_2 ``1 over Q_i &=` sum_i=1^q `` p_i ``log_2 ``(K cdot 2^l_i ) ## &=` sum_i=1^q `` p_i ``log_2 ``K ``+`` sum_i=1^q ``p_i ``l_i]	(7-10)

를 얻는다.

식(4-5)에 주어진 Kraff 부등식으로부터 K □ 1이므로 식(7-10)의 우변의 첫 번째 항은 0 보다 작은 값이다. 따라서 식(7-9)에 식(7-10)의 결과를 적용하면, 다음과 같은 관계식을 얻을 수 있다.

[eqn: H_2 `(S) ~=` sum_i=1^q ``p_i ``log_2 ``1 over p_i ~<=~ sum_i=1^q `` p_i ``l_i ~=~ L_\av]	(7-11)

따라서 정리의 식(7-4)는 임의의 이진 동시코드에 대하여 성립한다.

또한 이 정리에서는 이진코드 만을 다루었으나, 그 증명 과정은 Radix-r에 대해서도 동일하게 진행할 수 있으며, 이 정리가 모든 Radix에 대하여 만족한다는 사실을 쉽게 입증할 수 있다.

결론적으로 시스템의 Entropy는 그 소스알파벳을 인코딩하는 모든 동시코드의 평균 코드길이의 하한(the lower bound)이 된다.	■

제4-3절에서 언급했던 바, 정상적인 이진코드는 Kraft 부등식의 등식부분 즉 KＡ1을 만족하며 디코딩트리의 모든 결정상태를 사용하게 된다. 또한 효율적인 이진코드를 구성하기 위해서는 최소한 이와 같은 조건을 만족해야 한다는 사실도 밝힌 바 있다. 이 때 식(7-6)에 주어진 가상 확률분포는

[eqn: Q_i ~=` 1 over 2^l_i `,~ 1`=`1,`2,`cdots,` q]	(7-12)

와 같이 표현된다.

그러므로 만일 각 심볼의 확률분포 [eqn: p_i ``(i`=`1,`2,`cdots,`q)]가

[eqn: p_i ~=~ Q_i ~=~ 1 over 2^l_i `,~i``Ａ``1,`2,` cdots,`q]	(7-13)

을 만족한다면, 식(7-11)의 등식부분을 만족하게 되어 정리의 식(7-4)는

[eqn: L_\av ~=`` H_2 `(S)]	(7-14)

와 같이 표현된다. 또한 식(7-14)가 성립하는 것은 오직 이러한 경우 뿐이다.

따라서 실질적인 소스코드 체계에 있어서, 심볼들의 발생빈도수에 의하여 추정된 발생확률들은 일반적으로 식(7-13)을 만족할 수 없을 것이므로 정리식의 부등식부분 즉

[eqn: L_\av ~> `` H_2 `(S)]	(7-15)

을 만족하게 되는 것이다.

제6장에 제시한 표 6-1은 Zipf 확률분포에 대한 Huffman 코딩의 결과와 시스템의 Entropy를 비교한 것인데, 이 분포는 식(7-13)을 만족하지 않으므로 모든 심볼 수에 대하여 정리식의 부등식 부분, 즉 식(7-15)가 성립되고 있음을 볼 수 있다.

[예제 1] 소스알파벳과 각 심볼의 발생확률이 다음과 같이 주어질 때

[eqn: S &=` \{`s_1 , ` s_2 ,` s_3 , ` s_4 , `s_5 \} # & p_1 `=`1/2 , ~ p_2 `=` 1/4 , ~ p_3 `=` 1/8 , ~p_4 `=` 1/16 , ~p_5 `=` 1/16]

(1) Huffman 코드의 평균 코드길이 [eqn: L_H]를 구하라.

(2) 시스템의 Entropy[eqn: H_2 `(S)]를 구하여, 위에서 구한 평균 코드길이와 비교하라.

[풀이]

(1) 최소분산 Huffman 코드로 인코딩하면 다음과 같은 결과를 얻는다.

[eqn: &s_1 ~=~ 1 ~~~~&p_1 ``=`` 1/2 ~~~~&l_1 ``=`` 1 # &s_2 ~=~ 0~1 ~~~~&p_2 ``=`` 1/4 ~~~~&l_2 ``=`` 2 # &s_3 ~=~ 0~0~1 ~~~~&p_3 ``=`` 1/8 ~~~~&l_3 ``=`` 3 # &s_4 ~=~ 0~0~0~0 ~~~~&p_4 ``=`` 1/16 ~~~~&l_4 ``=`` 4 # &s_5 ~=~ 0~0~0~1 ~~~~&p_5 ``=`` 1/16 ~~~~&l_5 ``=`` 4]

따라서 평균 코드길이는

[eqn: L_H ~=` sum_i=1^5 `p_i ``l_i ~=`` 15 over 8 ~~(bits)]

와 같이 계산된다.

(2) 한편 시스템의 Entropy는

[eqn: H_2 `(S) ~=` sum_i=1^5 ``p_i `` log_2 `` 1 over p_i ~=~ 15 over 8 ~~(bits)]

와 같이 계산되어, [eqn: L_H `=` H_2 `(S)]를 만족한다. 이는 주어진 각 심볼의 발생확률이 식(7-13)을 만족하기 때문이다.

7-3  코드의 확장에 대한 고찰

이 절에서는 확장된 소스알파벳에 대하여 코드체계를 구성하였을 때, 그 평균 코드길이가 시스템의 Entropy 함수와 어떤 관계를 갖게 되는가를 분석하고자 한다. 우리는 이미 제4-6절에서 하나의 간단한 소스알파벳을 도입하여 코드의 확장에 따른 평균 코드길이의 변화를 분석하였고, 그 결과로 그림 4-9를 제시한 바 있다. 코드확장의 차수가 증가함에 따라 평균 코드길이는 점차로 작아지지만, 그 변화의 경향은 어떤 점근선에 무한히 접근하는 양상임을 확인하였고, 그 점근선이 바로 시스템의 Entropy라는 사실도 식(4-44)를 통하여 밝힌 바 있다. 그러나 이는 하나의 간단한 소스알파벳에 대한 예에 지나지 않으므로 일반적인 특성을 확인한 것이라고 볼 수는 없다.

이 절의 목적은 바로 이러한 코드의 확장에 있어서도 그 평균 코드길이는 시스템의 Entropy 보다 작아질 수 없음을 수학적으로 입증하고자 하는 것이다.

이를 위하여 먼저 하나의 새로운 코드체계를 소개하기로 한다. 지금까지 시스템의 Entropy 함수를 결정할 때나 Huffman 코드를 구성하고자 할 때에는 소스알파벳 내의 각 심볼들에 대한 발생확률 pi (i = 1, 2, …, q) 가 모두 주어져 있다고 가정하였다. 또한 구성된 코드체계의 평균 코드길이를 계산하기 위해서는 각 심볼에 대한 코드의 길이 li (i = 1, 2, …, q) 가 모두 결정되어 있어야만 가능하였다. 다시 말해서 제4-5절에서 소개하였던 Huffman 코딩 과정은 전체적인 확률분포가 주어진 상태에서만 진행될 수 있으며, 개별적인 심볼의 발생확률 만 가지고는 그 심볼의 코드를 결정할 수 없다는 것이다. 따라서 하나의 심볼에 대한 코드길이를 산출하기 위해서도 그 심볼의 발생확률은 물론 소스알파벳 전체의 확률분포를 적용해야만 가능하였다.

여기서 새로이 소개하고자 하는 Shannon-Fano 코드는 그 인코딩 과정이 전술된 Huffman 코드와는 반대로 이루어 진다고 볼 수 있다. 풀어서 말하면, Huffman 코드의 인코딩은 먼저 각 심볼의 코드들이 결정되고 그것으로부터 코드길이가 산출된다고 할 수 있으며, Shannon-Fano 코드의 인코딩은 먼저 코드길이가 산출되고 그것을 기준으로 각 심볼의 코드들을 결정해 나가는 순서로 이루어 진다. 또한 Huffman 코딩에 있어서는 하나의 심볼에 대한 코드길이를 결정하기 위하여 소스알파벳 전체의 확률분포를 필요로 하지만, Shannon-Fano 코딩에 있어서는 각 심볼에 대한 코드길이가 그 심볼의 발생확률로부터 개별적으로 산출된다. 따라서 각각 심볼이 평균 코드길이나 Entropy에 미치는 영향을 개별적으로 분석하기 위해서는 Shannon-Fano 코드가 매우 편리하게 사용될 수 있는 것이다. 다음과 같이 Shannon-Fano 코드를 정의한다.

<정의 : Shannon-Fano 코드>

소스알파벳과 각 심볼의 발생확률이 다음과 같이 주어진다고 가정하자.

[eqn: S ``= \{`s_1 ,` s_2 ,` cdots,` s_q `\} `, ~ p_i `=Pr \{` s_i ~ \occurs \}, `i`=`1,`2,` cdots,` q]	(7-16)

임의의 심볼에 대한 발생확률 pi 에 대하여 하나의 정수 li 가 존재하여 다음과 같은 관계식을 만족하게 되는데,

[eqn: log_2 ``1 over p_i ``<=~ l_i ~＠`` log_2 ``1 over p_i `／```1]	(7-17)

각 심볼의 코드길이가 li (i = 1, 2, …, q)로 주어지는 동시코드를 Shannon-Fano 코드라 한다.

먼저, 식(7-17)을 만족하는 정수의 존재성(existence)과 유일성(uniqueness)에 대하여 검토하여 보자. 하나의 발생확률 pi (0 ≤ pi ≤ 1)가 주어지면, 식(7-17)의 좌변은 하나의 실수 □R□로 결정된다. 이 때 식(7-17)의 우변은 □R + 1□이 될 것이다. 만일 □R□이 정수이면 □R + 1□도 정수로 되지만, 식(7-17)의 관계식은 한 쪽에만 등식을 포함하고 있으므로 li = R 로 결정된다. 만일 □R□이 정수가 아니라면, □R□과 □R + 1□ 사이에는 유일한 정수가 존재하게 되고, li 는 바로 그 값을 취하게 된다. 따라서 식(7-17)을 만족하는 정수는 유일하게 존재한다.

다음으로, 식(7-17)에 의하여 결정되는 코드길이를 갖는 동시코드의 존재성을 확인하기 위하여 아래와 같은 정리를 마련하기로 한다.

정리 2  <Shannon-Fano 코드의 존재성>  □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

임의 심볼의 발생확률 pi (i = 1, 2, …, q)에 대하여

[eqn: log_2 ``1 over p_i ``<=~ l_i ~＠`` log_2 ``1 over p_i `／```1 `, ~ i`=`1,`2,` cdots,` q]	(7-18)

로 결정되는 코드길이 li (i = 1, 2, …, q)를 갖는 동시코드 체계는 존재한다.

♠ 증명

각 심볼의 코드길이가 주어진 경우, 그것을 만족하는 동시코드 체계의 존재성을 입증하기 위해서는 제4-3절의 식(4-5)로 주어진 Kraft 부등식을 이용하는 것이 가장 편리한 방법일 것이다. 따라서 식(7-18)을 다음과 같이 변형한다.

우선 주어진 식의 모든 항을 로그함수로 표현하면

[eqn: log_2 ``1 over p_i ~<=~ log_2 ```2^l_i ~＠~log_2 ``2 over p_i]	(7-19)

와 같다. 로그함수는 단조증가함수이므로 이 식의 각 항에서 □log□를 제거하여도 부등호의 방향은 변치 않는다. 따라서 식(7-19)는

[eqn: 1 over p_i ~<=~ 2^l_i ~＠~ 2 over p_i]	(7-20)

와 같이 변형할 수 있다.

이제 이 식의 각 항을 역수 취하면 부등호의 방향은 반대로 되어

[eqn: p_i ~>=~ 1 over 2^l_i ~Ｂ~ p_i over 2]	(7-21)

로 표시된다.

식(7-18)에 제시된 바와 같이, 식(7-21)은 모든 i (1, 2, …, q)에 대하여 성립하므로 이들 각각에 대하여 부등식을 구하고, 각 항별로 모두 합하면 다음과 같은 관계식을 얻게 된다.

[eqn: 1 ~>=~ K `= sum_i=1^q `` 1 over 2^l_i ~Ｂ~ 1 over 2]	(7-22)

Kraft 정리로부터, 이 결과식은 주어진 코드길이를 갖는 동시코드 체계가 존재함을 입증한다. 따라서 Shannon-Fano 코드는 존재한다.	■

이제 우리가 정의하였던 Shannon-Fano 코드가 동시코드 체계로서 존재함을 확인하였으므로, 그 체계의 평균 코드길이와 시스템의 Entropy 사이에는 어떠한 관계가 성립하는지 규명하여 보자. 이를 위하여 다음과 같은 정리를 세운다.

정리 3  <Shannon-Fano 코드와 Entropy의 관계>  □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

Shannon-Fano 코드의 평균 코드길이를 [eqn: L_\SF]라 하고, 시스템의 Entropy를[eqn: H_2 `(S)] 라 할 때, 이들 사이에는 다음과 같은 관계식이 성립한다.

[eqn: H_2 `(S) ~<=~ L_\SF ~＠~ H_2 `(S) ``+`` 1]	(7-23)

♠ 증명

식(7-18)의 각 항에 pi를 곱하고, 모든 i (1, 2, …, q)에 대하여 부등식을 구한 다음, 각 항별로 모두 합하면

[eqn: sum_i=1^q `` p_i ``log_2 ``1 over p_i ~<=~ sum_i=1^q `` p_i ``l_i ~＠~ sum_i=1^q ``p_i ``log_2 `` 1 over p_i ``+`` sum_i=1^q ``p_i]	(7-24)

와 같은 관계식이 주어진다. 이 식의 좌변은 시스템의 Entropy를 표시하며, 중변은 Shannon-Fano 코드의 평균 코드길이를 나타내고, 우변은 Entropy에 1을 더한 값이다. 따라서 정리의 식(7-23)은 성립한다.	■

예상한 바와 같이, Shannon-Fano 코드에 있어서도 그 평균 코드길이의 하한(lower bound)은 시스템의 Entropy로 주어진다. 또한 특별히 Shannon-Fano 코드는 평균 코드길이의 상한(upper bound)도 제공하며, 그 값은 식(7-23)에 표시된 바와 같이 시스템의 Entropy에 1을 더한 것과 같다.

제4장에서 취급하였던 Huffman 코드도 그 평균 코드길이의 하한은 시스템의 Entropy로 주어짐을 확인한 바 있다. 그러나 평균 코드길이의 상한은 소스의 조건에 따라 달라짐으로 그 일반화된 값을 얻기는 매우 어렵다.

뒤에서 자세히 다루겠지만, 일반적으로 Shannon-Fano 코드의 효율성은 Huffman 코드에 비하여 다소 떨어진다. 사실, 우리는 제4장을 통하여 Huffman 코드가 주어진 조건에서 구성될 수 있는 최적의 동시코드임을 밝힌 바 있다. 그러므로 모든 경우에 대하여 Huffman 코드는 최소한 Shannon-Fano 코드 만큼은 효율적일 것이다. 이러한 이유 때문에 식(7-23)은 Huffman 코드에 대해서도 성립한다.

이제, 실제로 다음과 같이 주어진 소스알파벳과 각 심볼의 확률분포를 사용하여 Shannon-Fano 코드를 구성하는 방법을 논의하여 보자.

[eqn: S&=` \{`s_1 ,` s_2 ,` s_3 ,`s_4 ,`s_5 ,` s_6 \} # &~p_1 `=`p_2 `=`1 over 4 , ~~p_3 `=` p_4 `=` p_5 `=` p_6 `=` 1 over 8]	(7-25)

앞에서 설명한 바와 같이, Shannon-Fano 코딩에 있어서는 각 심볼에 대한 코드가 결정되기에 앞 서 그 코드길이가 먼저 산출된다. 각 코드의 길이는 식(7-25)에 주어진 발생확률들에 대하여 식(7-18)을 차례로 적용함으로써 쉽게 얻어진다.

[eqn: l_1 ``Ａ`` l_2 ``Ａ`` 2 ,~~ l_3 ``Ａ`` l_4 ``Ａ`` l_5 ``Ａ`` l_6 ``Ａ`` 3]	(7-26)

이와 같이 각각의 코드길이가 구해지면, 정리 2에 의하여 이러한 코드길이를 갖는 동시코드 체계가 존재함을 확신할 수 있다. 그러나 이러한 코드길이를 갖는다고 하여 모두 동시코드가 되는 것은 아니다(Kraft 정리의 개념이 바로 그러함으로). 따라서 우리는 식(7-26)에 표시된 코드길이를 가지면서 동시코드를 구성하는 방법을 모색하여야 한다.

제4-2절에서 언급한 바, 코드체계 내의 어떤 코드도 다른 코드의 Prefix가 되지 않는다면 그 코드체계는 동시코드를 형성한다. 따라서 식(7-26)에 주어진 코드길이에 따라 각 심볼에 코드를 부여하되 체계 내에 Prefix가 나타나지 않도록 이진코드를 할당해 나가면 될 것이다.

이 예에 대하여 Shannon-Fano 코드를 구성하면 다음과 같다.

(그림 들어갈 자리임)	[eqn: & s_1 ``Ａ`` 0``0 ## & s_2 ``Ａ`` 0``1 ## & s_3 ``Ａ`` 1``0``0 ## & s_4 ``Ａ`` 1``0``1 ## & s_5 ``Ａ`` 1``1``0 ## & s_6 ``Ａ`` 1``1``1]	(7-27)

이 코드체계는 식(7-22)에 따라 Kraft 부등식을 만족하며, 체계 내에 Prefix가 존재하지 않고 위 그림과 같은 디코딩트리가 존재함으로 동시코드이다.

또한 이 코드체계를 구성하는 과정에서 인식할 수 있는 바와 같이 Shannon-Fano 코드는 유일하지 않다. 다시 말해서 식(7-27)의 코드체계는 주어진 소스알파벳 식(7-25)에 대하여 구성할 수 있는 여러 가지 Shannon-Fano 코드 중의 하나라는 것이다. 만일 식(7-27)에 구성된 각 코드의 보수를 취한다면 근소한 차이를 갖는 또 하나의 코드체계를 만들 수 있을 것이다. 또한 식(7-26)에 주어진 코드길이에 따라 □s1=10□ 으로 할당하기 시작한다면 다음과 같이 전혀 새로운 코드체계를 구성할 수 있을 것이다.

(그림 들어갈 자리임)	[eqn: & s_1 ``Ａ`` 1``0 ## & s_2 ``Ａ`` 1``1 ## & s_3 ``Ａ`` 0``1``0 ## & s_4 ``Ａ`` 0``1``1 ## & s_5 ``Ａ`` 0``0``0 ## & s_6 ``Ａ`` 0``0``1]	(7-28)

이러한 사실로 볼 때, Shannon-Fano 코드의 코드길이가 주어진 상태에서 동시코드 체계를 구성하기 위하여 할당할 수 있는 코드들은 언제나 충분히 존재한다는 것을 알 수 있다.

식(7-25)에 주어진 소스알파벳의 Entropy와 구성된 코드체계의 평균 코드길이를 계산해 보면 다음과 같다.

[eqn: H_2` (S) ~=` sum_i=1^6 ``p_i ``log_2 ``1 over p_i ~=~ 2.5 ~~(bits)]	(7-29)

[eqn: L_\SF ~=` sum_i=1^6 ``p_i ``l_i ~=~ 2.5 ~~(bits)]	(7-30)

이것은 주어진 소스알파벳의 확률분포가 식(7-13)을 만족한다는 사실에 기인하는 것이며, 이러한 경우 Shannon-Fano 코드는 최대의 효율성을 나타내게 되고, 그 평균 코드길이가 Entropy 및 Huffman 코드의 평균 코드길이와 일치하게 된다. 즉 소스의 확률분포가 식(7-13)을 만족하는 경우에는

[eqn: L_\SF ~=~ L_\H ~=~ H_2` (S)]	(7-31)

와 같은 관계식이 성립한다.

그러나 확률분포가 식(7-13)을 만족하지 않는 일반적인 경우에는 다음과 같은 관계식을 만족한다.

[eqn: L_\SF ~Ｂ~ L_\H ~Ｂ~ H_2` (S)]	(7-32)

[예제 2] 소스알파벳과 각 심볼의 발생확률이 다음과 같이 주어질 때

[eqn: S ``=`` \{`s_1 ,`s_2 , `s_3 , ` s_4 \}, ~~ p_1 `=` 1/2 , ~ p_2 `=` 1/4 , ~ p_3 `=` p_4 `=` 1/8]

(1) 시스템의 Entropy [eqn: H_2 `(S)]를 구하라.

(2) Shannon-Fano 방법으로 인코딩하고 평균 코드길이 [eqn: L_\SF]를 구하라.

(3) Huffman 방법으로 인코딩하고 평균 코드길이 [eqn: L_\H]를 구하라.

[풀이]

(1)     [eqn: H_2` (S) ~=` sum_i=1^4 ``p_i ``log_2 `` 1 over p_i ~=~ 7 over 4 ~~(bits)]

(2) 부등식 (7-18)을 이용하여 각각의 코드길이를 구하면 다음과 같다.

[eqn: & log_2~ 2 ~<=~ l_1 ~＠~ log_2~ 2 ``+``1 ~~~ &Rarrow ~~~ l_1 ``=``1 # & log_2~ 4 ~<=~ l_2 ~＠~ log_2~ 4 ``+`` 1 & Rarrow ~~~ l_2 ``=`` 2 # & log_2~ 8 ~<=~ l_3 , l_4 ~＠~ log_2~ 8 ``+`` 1 & Rarrow ~~~ l_3 ``=`` l_4 ``=`` 3]

Prefix가 나타나지 않도록 코드를 부여하면 다음과 같다.

[eqn: & s_1 ~=~ 0 # & s_2 ~=~ 1~0 # & s_3 ~=~ 1~1~0 # & s_4 ~=~ 1~1~1]

따라서 평균 코드길이는 다음과 같다.

[eqn: L_\SF ~=` sum_i=1^4 `p_i ``l_i ~=~ 7 over 4 ~~ (bits)]

(3) 최소분산 Huffman 코드를 구성하면 다음과 같다.

[eqn: & s_1 ~=`` 1 & p_1 ~=`` 1/2 & ~~~Rarrow~~~ l_1 ``=`` 1 # & s_2 ~=`` 0~1 & p_2 ~=`` 1/4 & ~~~Rarrow~~~l_2 ``=`` 2 # & s_3 ~=`` 0~0~0 & p_3 ~=`` 1/8 & ~~~Rarrow~~~l_3 ``=`` 3 # & s_4 ~=`` 0~0~1 ~~ & p_4 ~=`` 1/8 & ~~~Rarrow~~~l_4 ``=`` 3]

따라서 평균 코드길이는 위 (2)에서와 마찬가지로

[eqn: L_\H ~=~ 7 over 4 ~~ (bits)]

로 주어진다. 이 예제는 [eqn: H_2`(S) ``=`` L_\SF ``=`` L_\H]을 만족하는 경우이며, 이러한 결과는 각 심볼의 발생확률들이 식(7-13)을 만족한다는 사실에 기인한다.

[예제 3] 소스알파벳과 각 심볼의 발생확률이 다음과 같이 주어질 때

[eqn: S ``=`` \{`s_1 ,`s_2 , `s_3 , ` s_4 \}, ~~ p_1 `=` 0.4 , ~ p_2 `=` 0.3 , ~ p_3 `=` 0.2, ~ p_4 `=` 0.1]

(1) 시스템의 Entropy [eqn: H_2 `(S)]를 구하라.

(2) Shannon-Fano 방법으로 인코딩하고 평균 코드길이 [eqn: L_\SF]를 구하라.

(3) Huffman 방법으로 인코딩하고 평균 코드길이 [eqn: L_\H]를 구하라.

[풀이]

(1)     [eqn: H_2` (S) ~=` sum_i=1^4 ``p_i ``log_2 `` 1 over p_i ~simeq~ 1.8464 ~~(bits)]

(2) 부등식 (7-18)을 이용하여 각 코드의 길이를 구하면 다음과 같다.

[eqn: & log_2~ 1 over 0.4 ~<=~ l_1 ~＠~ log_2~ 1 over 0.4 ``+``1 ~~~ &Rarrow ~~~ l_1 ``=``2 # & log_2~ 1 over 0.3 ~<=~ l_2 ~＠~ log_2~ 1 over 0.3 ``+`` 1 & Rarrow ~~~ l_2 ``=`` 2 # & log_2~ 1 over 0.2 ~<=~ l_3 ~＠~ log_2~ 1 over 0.2 ``+`` 1 & Rarrow ~~~ l_3 ``=`` 3 # & log_2~ 1 over 0.1 ~<=~ l_3 ~＠~ log_2~ 1 over 0.1 ``+`` 1 & Rarrow ~~~ l_4 ``=`` 4]

Prefix가 나타나지 않도록 코드를 부여하면 다음과 같다.

[eqn: & s_1 ~=~ 0~0 # & s_2 ~=~ 0~1 # & s_3 ~=~ 1~0~0 # & s_4 ~=~ 1~1~1~1]

따라서 평균 코드길이는 다음과 같이 계산된다.

[eqn: L_\SF ~=` sum_i=1^4 `p_i ``l_i ~=~ 2.4 ~~ (bits)]

(3) 주어진 소스알파벳에 대하여 최소분산 Huffman 코드를 구성하면 다음과 같다.

[eqn: & s_1 ~=`` 1 & p_1 ~=`` 0.4 & ~~~Rarrow~~~ l_1 ``=`` 1 # & s_2 ~=`` 0~1 & p_2 ~=`` 0.3 & ~~~Rarrow~~~l_2 ``=`` 2 # & s_3 ~=`` 0~0~0 & p_3 ~=`` 0.2 & ~~~Rarrow~~~l_3 ``=`` 3 # & s_4 ~=`` 0~0~1 ~~ & p_4 ~=``0.1 & ~~~Rarrow~~~l_4 ``=`` 3]

따라서 평균 코드길이는

[eqn: L_\H ~=~ sum_i=1^4 ``p_i ``l_i ~ =~ 1.9 ~~ (bits)]

로 주어진다. 이 예제는 [eqn: H_2`(S) ``＠`` L_\H ``＠`` L_\SF]를 만족하는 경우이며, 이러한 결과는 각 심볼의 발생확률들이 식(7-13)을 만족하지 않기 때문에 나타난 것이다.

위의 두 가지 예제를 통하여 살펴본 바와 같이, 소스알파벳의 확률분포가 식(7-13)을 만족하지 않으면, Shannon-Fano 코드는 Huffman 코드에 비하여 효율성이 떨어진다. 그렇다면 이들의 효율성 차이는 어느 정도인지 검토하여 보는 것도 매우 유용할 것이다. 이를 위하여 다음과 같은 간단한 예를 조사해 보기로 하자.

소스알파벳과 각 심볼의 발생확률이

[eqn: S``=` \{`s_1 ,` s_2 \} ``, ~~ p_1 ``Ａ`` 1 `-`1 over 2^k `,~ p_2 `Ａ` 1 over 2^k ~~(k``□``2)]	(7-33)

와 같이 주어진다. 이에 대하여 Shannon-Fano 방법을 사용하여 각 코드의 길이를 구하면 다음과 같다.

[eqn: & log_2 ``1 over p_1 ~<=~ l_1 ~＠~ log_2 `` 1 over p_1 ``+`` 1 ## & log_2 ``1 over p_2 ~<=~ l_2 ~＠~ log_2 `` 1 over p_2 ``+`` 1]	(7-34)

여기서 두 식의 좌변은 각각

[eqn: & log_2``1 over p_1 ``=`` log_2 ``2^k over {2^k `-` 1 } ``＠`` log_2 `2 ``Ａ``1 ## & log_2``1 over p_2 ``=`` log_2 `` 2^k ``=`` k]	(7-35)

와 같이 계산됨으로 각 코드의 길이는 다음과 같이 주어진다.

[eqn: l_1 ``=`` 1 ``, ~~l_2 ``=` k]	(7-36)

따라서 Shannon-Fano 코드의 평균 코드길이는

[eqn: L_\SF ~= ``` 1 ``／`` {k`-`1} over 2^k ~~(bits)]	(7-37)

로 계산된다.

한편, 이 소스알파벳에 대하여 Huffman 방법을 적용하면 각 코드의 길이는 명백히 1 이며, 따라서 평균 코드길이는

[eqn: L_ \H ~=~ 1 ~~(bits)]	(7-38)

로 주어진다.

식(7-37)과 식(7-38)을 비교하여 보면, (k □ 2)에 대하여 Shannon-Fano 코드가 Huffman 코드에 비하여 덜 효율적이라는 것은 사실이다. 그러나 그 비효율성에 대하여 걱정하기 전에 이들이 k 의 변화에 따라 어떠한 양상을 나타내는지 조사하여 보자.

먼저 k = 2 로서 가장 작은 값을 갖는 경우, 식(7-37)은 LSF = 1.25 (bits) 가 됨으로 Huffman 코드에 비하여 약 25(%) 정도의 효율 저하를 나타낸다. 그러나 k 가 무한히 커지면 식(7-37)은 1 에 접근함으로써 Huffman 코드와 동일한 효율성을 나타내게 된다. 식(7-33)에 주어진 발생확률의 식으로 볼 때, 파라미터 k 가 증가한다는 것은 두 심볼의 확률 차가 커짐을 나타내므로, Shannon-Fano 코드의 효율성은 각 심볼의 발생확률 차가 클수록 점차 증가하여 Huffman 코드의 효율성에 도달한다고 말할 수 있다.

요컨대, Shannon-Fano 코드는 일반적인 소스코드의 특성을 그대로 가지고 있으면서, 효율성에 있어서는 최적의 Huffman 코드 보다 다소 떨어지지만 평균 코드길이와 Entropy의 산출에 사용되는 각 요소별 정보량을 산출하기 용이하며, 구성된 각 코드가 개별적인 발생확률에 의하여 직접 계산됨으로 정보이론의 접근에 유용하다. 이제 이러한 Shannon-Fano 코드의 특성을 이용하여, 제4-6절에서 소개하였던 코드의 확장(extension of a code)에 대하여 고찰해 보기로 한다.

제4-6절에 예시하였던 식(4-35)의 소스알파벳은 확장의 차수가 증가할수록 식(4-38), (4-41)과 같이 심볼들의 발생확률이 점차로 큰 차이를 나타내게 된다. 따라서 고차의 확장에 대해서는 Shannon-Fano 코드의 효율이 증가하여 Huffman 코드의 효율에 접근할 것이라는 사실을 쉽게 예상할 수 있다. 이는 우리가 코드의 확장에 대한 정리들을 유도함에 있어서, 취급이 용이한 Shannon-Fano 코드를 사용하더라도 Huffman 코드를 사용하는 것과 동일한 효과를 나타낼 것이라는 사실을 말해준다.

먼저, 제4-2절에서 정의하였던 □코드의 n-차 확장□에 근거하여, 앞으로의 논의에서 필요한 □소스알파벳의 n-차 확장□을 다음과 같이 정의한다.

<소스알파벳의 n-차 확장>

시스템이 가지는 원래의 소스알파벳을 다음과 같이 정의하자.

[eqn: S``=` \{`s_1 ,`s_2 ,` cdots, `s_q \} ~:~ q```\elements]	(7-39)

이 알파벳으로부터 얻어지는 심볼의 n-차 확장은 제4장의 정의에 의하여 다음과 같이 주어진다.

[eqn: t_i ~=`` s_i_1```s_i_2```cdots```s_i_n ``, ~ s_i_k `` in `` S , ~for~ k`=`1,`2,`cdots,`n.]	(7-40)

이 때, 원래의 알파벳 S 의 각 심볼은 독립적인 발생확률을 갖는다고 가정하면, 식(7-40)에 주어진 심볼의 n-차 확장은

[eqn: Q_i ~=`` Pr \{` t_i ~\occurs \} ~=`` p_i_1 ``p_i_2 `` cdots``p_i_n]	(7-41)

와 같은 발생확률을 갖는다.

이와 같은 심볼의 n-차 확장을 원소로 하는 집합

[eqn: T ``=` S^n ``=` \{` t_i `vert t_i `Ａ` s_i_1` s_i_2 ` cdots `s_i_n `, ~ i`Ａ`1,`2,` cdots,`q^n \}``:`` q^n ~\elements] (7-42)

를 소스알파벳 S 의 n-차 확장이라 한다.

이와 같이 □소스알파벳의 n-차 확장□은 제4-2절에서 정의된 □코드의 n-차 확장□에 의하여 자연스럽게 유도되는 개념으로서 전혀 새로운 것이 아니며, 단지 앞에서의 정의를 집합으로 표시하여 구체화하였을 뿐이다.

이렇게 확장된 소스알파벳의 개념과 앞에서 논의된 Shannon-Fano 코드의 특성을 기반으로 하여, 다음과 같은 중요한 정리를 마련하기로 한다.

정리 4  <Shannon의 소스코딩 정리>  □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

소스알파벳의 n-차 확장에 대하여 임의의 소스코드를 구성하였을 때, 그 평균 코드길이를 [eqn: L_n]이라 하고, 원래의 소스알파벳에 대한 시스템의 Entropy를[eqn: H_2 `(S)] 라 할 때, 확장의 차수 n을 무한히 증가시키는 극한에서 다음과 같은 관계식이 성립한다.

[eqn: lim_n->inf L_n over n ~=~ H_2 `(S)]	(7-43)

♠ 증명

먼저, 소스알파벳의 n-차 확장에 대한 Entropy는 다음과 같이 주어진다.

[eqn: H_2`(T`) ~=``` H_2 `(S^n`) ~=`` sum_i=1^{q^n} `Q_i ```log_2 ``1 over Q_i]	(7-44)

여기에 식(7-41)을 대입하고, 로그함수의 규칙을 적용하여 다시 쓰면

[eqn: H_2 (S^n ) &=` sum_i=1^{q^n} ``p_i_1 ``p_i_2 ``cdots ``p_i_n ``log_2 ``1 over {p_i_1 ``p_i_2 ``cdots`` p_i_n } ## &=`sum_i=1^{q^n}``p_i_1 ``p_i_2 ``cdots ``p_i_n ``sum_k=1^n ``log_2 `1 over p_i_k ## &=`sum_k=1^n sum_i=1^{q^n} ````p_i_1 ``p_i_2 ``cdots ``p_i_n ```log_2 1 over p_i_k]	(7-45)

와 같이 나타난다. 이 식의 우변은 두 변수 k와 i에 관한 합으로 구성되어 있는데, 변수 k에 대한 하나의 항 만을 먼저 살펴보면

[eqn: sum_i=1^{q^n}&p_i_1 ``p_i_2 ``cdots`` p_i_n `` log_2 ``1 over p_i_k ## &=`` sum_{i_1 =1}^q`` p_i_1 ```sum_{i_2 =1}^q`` p_i_2 ```cdots ``` sum_{i_k =1}^q`` p_i_k ``log_2 ``1 over p_i_k sum_{i_k+1 =1}^q ``p_i_k+1 ``` cdots ```sum_{i_n =1}^q ``p_i_n ## &=`` sum_{i_k =1}^q ``p_i_k ``log_2 `` 1 over p_i_k ~=~ H_2` (S)]	(7-46)

로 계산된다. 변수 k에 대한 모든 항은 k에 관계없이 H2(S)로 표현되고, 식(7-45)에는 이러한 항이 모두 n 개 존재함으로 확장된 소스알파벳의 Entropy는 다음과 같이 계산된다.

[eqn: H_2 `(S^n ) ~=~ n`` H_2 `(S)]	(7-47)

이 식을 Shannon-Fano 코드의 Entropy 관계식 (7-23)에 적용하면

[eqn: & H_2 `(S^n ) ~<=~ L_n ~＠~ H_2 `(S^n ) ``+`` 1 ## Rarrow~~ & n ``H_2 `(S) ~<=~ L_n ~＠~ n`` H_2 `(S) ``+`` 1]	(7-48)

와 같은 관계식을 얻을 수 있다. 여기서 [eqn: L_n]은 확장된 소스알파벳에 대한 소스코드의 평균 코드길이를 나타낸다. 그러므로 이를 bits 단위로 표시하기 위해서는 식(7-48)을 확장의 차수 n으로 나누어야 한다. 결국 우리는 다음과 같은 관계식을 얻는다.

[eqn: H_2 `(S`) ~<= ~ L_n over n ~＠~ H_2 `(S`) ``／`` 1 over n]	(7-49)

확장의 차수 n이 무한히 커지면, 식(7-49)의 우변은 Entropy에 접근함으로 좌변과 무한히 근접하게 된다. 따라서 좌변과 우변의 사이에 존재하는 값은 결국 Entropy에 접근하게 될 것이다. 즉, 정리식 (7-43)은 성립한다.	■

우리는 제4장에서 간단한 소스알파벳에 대하여 코드를 확장하여 Huffman 코드를 구성함으로써 그 평균 코드길이가 Entropy에 접근함을 보았다. 이제 이러한 사실은 단지 Huffman 코드에 대해서만 성립하는 것이 아니라 Shannon-Fano 코드에 의하여 일반화되는 모든 소스코드에 대하여 성립하는 정리가 되었다. 이를 Shannon의 소스코딩 정리 혹은 무잡음 코딩 정리(noiseless coding theorem)라 한다.

7-4  Markov 과정에 대한 고찰

제5-2절에서 우리는 심볼 간의 상관관계를 소스코딩의 과정에 도입하기 위하여 Markov 과정의 개념을 소개한 바 있다.  Markov 과정은 심볼 간의 상관관계를 조건확률에 의하여 취급함으로써 유한한 기억장치를 갖는 시스템의 코딩에 편리하게 적용될 수 있다. 이 절에서는 이러한 Markov 과정이 적용된 코드체계의 평균 코드길이와 시스템의 Entropy 사이에 성립되는 관계를 검토하고자 한다.

일반적인 j-차 Markov 과정(j-th order Markov process)을 고려하자. 시스템은 기지의 심볼 j 개를 저장할 수 있는 기억장치를 소유함으로, 임의의 심볼이 발생되기 전에 그 이전의 심볼

[eqn: s_i_1 , `` s_i_2 ,`` □, ``s_i_j]	(7-50)

를 미리 알고 있다고 가정할 수 있다. 이러한 상태에서 임의의 심볼[eqn: s_i]가 발생될 확률, 즉 발생된 심볼열(symbol sequence)이

[eqn: s_i_1 , `` s_i_2 ,`` □, ``s_i_j ,``s_i]	(7-51)

와 같이 구성될 확률은 다음과 같은 조건확률로 표시된다.

[eqn: P``(s_i vert s_i_1 , `s_i_2 , `□,` s_i_j `)]	(7-52)

제6장에서 정의된 □정보의 양(amount of information)□(식6-11)의 개념을 적용하여 이 심볼의 발생에 의한 정보량을 표시하면 다음과 같다.

[eqn: I``(s_i vert s_i_1 ,` s_i_2 ,`□,` s_i_j `) ~=`` log_2 ``1 over { P` (s_i vert s_i_1 ,` s_i_2 ,`□,` s_i_j `) }]	(7-53)

따라서 이러한 심볼의 집합인 소스알파벳 S에 대한 조건(conditional) Entropy는 다음과 같이 정의된다.

[eqn: H_2`(S vert s_i_1 ,` s_i_2 ,` □,` s_i_j `) &==`` sum_S`` P`(s_i vert s_i_1 ,` s_i_2 ,`□,` s_i_j `)`` I`(s_i vert s_i_1 ,` s_i_2 ,` □,` s_i_j `) ## &= `sum_S`` P`(s_i vert s_i_1 ,` s_i_2 ,` □,` s_i_j `) ``log_2 ``1 over {P`(s_i vert s_i_1 ,` s_i_2 ,` □,` s_i_j `)}]

(7-54)

이것은 식(7-50)에 주어진 심볼열이 발생하였다는 조건 하에서 측정된 소스알파벳의 Entropy이므로, j-기억 시스템의 모든 상태를 고려한 Markov 과정의 Entropy를 얻어내기 위해서는 이 조건 Entropy의 평균값을 계산하여야 할 것이다.

식(7-50)의 상태가 발생될 확률은

[eqn: P`(s_i_1 ,` s_i_2 ,` □,` s_i_j`)]	(7-55)

와 같은 결합확률로 표시된다. 만일 원래의 소스알파벳 내에 q 개의 심볼이 존재한다면, 이러한 결합확률은 qj 가지 존재하게 될 것이다. 따라서 주어진 j-차 Markov 과정의 Entropy는

[eqn: H_M`(S) ~==`` sum_{s^j} ``P`(s_i_1 ,` s_i_2 ,` □,` s_i_j` ) ~H_2`(s_i vert s_i_1 ,` s_i_2 ,` □,` s_i_j `)]	(7-56)

와 같이 정의된다. 이 식에 앞에서 정의하였던 조건 Entropy 식(7-54)를 대입하면

[eqn: H_M`(S) &= `sum_{S^j}``P`(s_i_1 ,` s_i_2 ,` □,` s_i_j` )## &~~×``sum_S``P`(s_i vert s_i_1 ,` s_i_2 ,` □, `s_i_j `)`` log_2 `` 1 over { P`(s_i vert s_i_1 ,` s_i_2 ,` □, `s_i_j `) }]	(7-57)

로 표현된다. 합([eqn: sum] )의 차례를 교환하고, 제1장의 식(1-15)를 적용하면 다음과 같이 계산된다.

[eqn: H_M`(S) ~=` sum_{S^j+1} ``P`(s_i_1 ,` s_i_2 ,` □, `s_i_j ,`s_i` ) ``log_2 ``1 over {P`(s_i vert s_i_1 ,` s_i_2 ,` □,` s_i_j `) }]	(7-58)

여기서 결합확률 [eqn: P`(s_i_1 ,` s_i_2 ,` cdots, s_i_j ,` s_i `)]는 모두 qj+1 가지 존재하며, 이에 따라 합([eqn: sum _{S^j+1}] )도 1 부터 qj+1 까지의 합을 의미하게 된다. 식(7-58)을 j-차 Markov 과정의 Entropy라 한다.

Markov 과정의 Entropy에 대한 개념을 좀 더 깊이 이해하기 위하여 다음과 같은 간단한 예제를 해결하여 보자.

[예제 4]  다음 천이그래프로 표시되는 2-차 Markov 과정을 생각하자.

각 상태(vertex)는 이진수로 인코딩되어 있고, 각 가지(edge)에 표시되어 있는 숫자들은 상태천이를 위한 조건확률을 나타낸다. 또한 각 상태를 표시하고 있는 두 개의 이진수는 발생된 심볼의 순서에 따라 쓰여진 것이라고 가정한다. 즉, 새로이 발생되는 심볼은 상태의 두 번째 이진수로 설정된다.

(그림 들어갈 자리임)

(1) 주어진 Markov 과정을 조건확률로 표시하라.

(2) 평형조건에서 각 상태에 대한 확률을 구하라.

(3) Markov 과정의 Entropy HM(S)를 구하라.

[풀이]

(1) 그림으로부터 각 상태천이를 위한 조건확률은 다음과 같다.

[eqn: & P` (0 vert 0``0) ``=``P` (1 vert 1``1) ``=`` 0.8 # & P` (1 vert 0``0) ``=``P` (0 vert 1``1) ``=`` 0.2 # & P` (0 vert 0``1) ``=``P` (1 vert 1``0) ``=`` 0.5 # & P` (1 vert 0``1) ``=``P` (0 vert 1``0) ``=`` 0.5]

(2) 그림과 위 (1)의 결과로부터 알 수 있는 명백한 대칭성에 의하여

[eqn: P `( 0``0 ) ``=`` P`(1``1) ``, ~ ``P`(0``1 ) ``=`` P`(1``0)]  … □

을 얻을 수 있으며, 그림의 상태천이 관계로부터 다음의 방정식을 얻는다.

[eqn: & P`(0``0) ``=`` 0.5` P`(1``0) ``+`` 0.8` P`(0``0) # & P`(0``1) ``=`` 0.2` P`(0``0) ``+`` 0.5` P`(1``0)]

여기에 식 □을 대입하여 풀면 이 두 개의 방정식은 모두 다음과 같은 한 개의 방정식으로 나타나게 된다.

[eqn: 0.2` P`(0``0) ``=`` 0.5` P`(1``0)]               … □

한편 모든 확률분포에 대하여 성립하는 방정식

[eqn: P`(0``0) ``+``P(0``1) ``+`` P`(1``0) ``+`` P`(1``1) ``=`` 1]

에 다시 식 □을 대입하면

[eqn: 2`P(0``0) ``+`` 2`P`(1``0) ``=`` 1]	… □

을 얻는다.

이제 식 □와 □을 연립하여 풀면, 평형조건에서 각 상태에 대한 확률은 다음과 같이 주어진다.

[eqn: & P`(0``0) ``=`` P`(1``1) ``=`` 5 /14 # & P`(1``0) ``=`` P`(0``1) ``=`` 2 / 14]

(3) 따라서 주어진 Markov 과정의 Entropy는 식(7-58)에 의하여 다음과 같이 계산된다.

[eqn: H_M`(S`) &=` sum_{S^3} ``P`(`s_i_1 ,` s_i_2 , `s_i `) ``log_2 ``1 over {P`(s_i vert s_i_1 ,` s_i_2 `) } ## &=`` 2 TIMES .8 times 5 over 14 log_2 ``1 over .8 ``／``2 TIMES .2 times 5 over 14 log_2`` 1 over .2 ``／`` 4 times. 5 times 2 over 14 ``log_2 ``1 over .5 ## &simeq ``0.8014 ~~(bits)]

이 예제에서 보는 바와 같이, Markov 과정의 Entropy를 구하기 위해서는 주어진 소스의 각 상태에 대한 평형상태 확률(equilibrium state probabilities)을 필요로 한다. 그러나 실질적인 시스템에 있어서 이러한 평형상태 확률을 구하는 것은 일반적으로 매우 어렵다. 이 예제에 주어진 Markov 과정은 그 구성이 비교적 간단하며 매우 강한 대칭성을 가지고 있으므로 평형상태 분포를 구해내는 데 아무런 어려움이 없었으나, 일반적인 형태로 주어지는 Markov 과정의 구성에 있어서는 그것이 그리 용이하지 않다는 것이다.

그러므로 우리는 직접 Entropy를 구하는 대신, 그 한계(bound)를 발견하여 그로부터 시스템의 특성을 추정하는 방법을 필요로 한다. 여기서 제시하고자 하는 방법은 소위 인접시스템(adjoint system)의 개념에 그 근거를 두고 있다.

이론의 전개를 간단하게 하기 위하여 우선 1-차 Markov 과정을 고려하여 보자. 일반적인 n-차 Markov 과정을 위해서는 지금 전개하고자 하는 1-차 Markov 과정에 대한 결과를 자연스럽게 확장함으로써 얻을 수 있다.

다음과 같은 세 가지 확률분포를 고려하여 보자.

[eqn: & sum_i ``p(s_i ) ``=``1 `, ~~ sum_j ``p(s_j ) ``=``1 ## & sum_i sum_j ``P`(s_i ,``s_j `) ``=`` 1]	(7-59)

제6장의 식(6-55)로 주어진 Gibbs 부등식을 이용하면 이들 세 가지 확률분포에 대하여 다음과 같은 관계식을 얻을 수 있다.

[eqn: sum_i sum_j ``P`(s_i ,``s_j `) ``log_2 `` {p(s_i ) `p(s_j )} over {P`(s_i ,``s_j `)} ~<=~ 0]	(7-60)

여기서 우리는 Gibbs 부등식에 참여하는 두 분포를 각각 두 가지 변수에 대한 확률분포, 즉 [eqn: P`(s_i ,`s_j ) right]_{i, j}] 와 [eqn: p(s_i )`p(s_j ) right]_{i, j}] 로 적용하여 이중합([eqn: sum_i sum_j] )이 나타나게 되었으며, 그 등식은

[eqn: P`(s_i ,``s_j `) ``=`` p(s_i ) `p(s_j ) `, ~ for ~\all ~ i,``j]	(7-61)

일 때 성립한다.

식(7-60)에 제1장의 식(1-15)를 적용하여 정리하면

[eqn: sum_i sum_j ``P`(s_i , ` s_j` ) ``log_2`` {p(s_i )} over {P`(s_i vert s_j )} ~ <= ~0]	(7-62)

로 쓸 수 있으며, 여기에 로그함수의 규칙을 적용하면

[eqn: sum_i sum_j``P`(s_i ,` s_j` ) `` log_2`` 1 over {P`(s_i vert s_j )} ~<=~ sum_i sum_j ``P`(s_i ,`s_j `) ``log_2` 1 over {p(s_i`)}]	(7-63)

을 얻는다. 이 식의 좌변에는 다시 식(1-15)를 적용하고, 우변에는 식(1-27)로 주어진 전체확률의 정리를 이용하여

[eqn: sum_j ``P`(s_i ,`s_j `) ``=`` sum_j ``p(s_j ) `P`(`s_i vert s_j `) ``=``p(s_i )]	(7-64)

을 적용하면

[eqn: sum_j `p(s_j )``sum_i `P`(s_i vert s_j`) ``log_2` 1 over {P`(s_i vert s_j`)} &<=~sum_i ` p(s_i )`` log_2` 1 over {p(s_i )}## &=~ H_2 `(BAR S `)]	(7-65)

와 같이 나타난다. 이 식의 좌변은 1-차 Markov 과정의 Entropy를 나타내며, 우변은 원래의 소스알파벳에 대한 Entropy를 나타낸다. 결국 1-차 Markov 과정의 Entropy는 독립적인 발생확률 만을 사용하는 0-기억 시스템(zero-memory system)의 Entropy에 의하여 한정된다.

여기서 우리는 원래의 소스알파벳에 대한 Entropy를 [eqn: H_2`(BAR S`)]로 표시하였으며, 이 소스를 주어진 Markov 과정의 인접시스템(adjoint system)이라 한다.

식(7-65)를 정리하여 나타내면

[eqn: H_M (S) ``=``sum_j `p(s_j`)``H_2`(S vert s_j`) ~<=~ H_2 `(BAR S`)]	(7-66)

와 같이 표시되며, 이 식으로부터 Markov 과정의 Entropy는 인접시스템의 Entropy에 의하여 한정됨을 알 수 있다.

또한 식(7-66)의 등식 부분도 식(7-61)을 만족할 경우에 성립하며, 이는 연속된 두 심볼이 서로 독립인 경우, 즉 0-기억 시스템(인접시스템)에 해당하므로 당연한 결과라 할 것이다.

이와 같은 결과로부터, 심볼 간의 상관관계는 그것이 어떠한 형태로 주어지든 원래의 Entropy를 감소시키게 된다는 사실을 알 수 있다. 따라서 심볼 간의 상관관계까지 고려한 소스코드, 즉 Markov 과정에 의한 코드체계는 그 평균 코드길이가 더욱 작은 Entropy에 의하여 한정될 것이라는 사실을 추정할 수 있는 것이다.

Markov 과정의 n-차 확장에 대한 Entropy는 앞에서 식(7-47)로 유도되었던 일반적인 n-차 확장의 개념과 인접시스템의 개념을 이용하여 쉽게 유도할 수 있다. 여기에서도 표현의 단순화를 위하여 1-차 Markov 과정을 사용하기로 한다.

Markov 과정에 대한 n-차 확장의 Entropy는

[eqn: H_M (S^n ) &=` sum_{s^n} sum_{s^n} ``P`(t_i ,`t_j`) ``log_2 ` 1 over {P`(t_i vert t_j`)}## &=`sum_{s^2n} ``P`(t_i ,`t_j`) ``log_2 ` 1 over {P`(t_i vert t_j`)}]	(7-67)

로 표시되며, 여기서 1-차 Markov 과정의 결합확률은

[eqn: P`(t_i ,` t_j`) ~=`` P`(s_i_i ,`s_i_2 ,`□,` s_i_n , `s_j`)]	(7-68)

로 쓸 수 있다.

여기서 식(1-15)를 이용하여 체인규칙(chain rule)을 만들어 보자. 우선 세 개의 사건에 대한 결합확률은

[eqn: P`(A,B, C) &=`` P`(A,B)` P`(C vert A,B) ## &=``p(A)` P`(B vert A)`P`(C vert A,B)]	(7-69)

와 같이 표현할 수 있으며, 이를 n 개의 사건에 대하여 자연스럽게 확장하면

[eqn: P`(A_1 , A_2 , cdots, A_n ) ~=& p(A_1 )`` P`(A_2 vert A_1 )`` P`(A_3 vert A_1 , A_2 ) ``cdots ## &P`(A_n vert A_1 , A_2 , cdots, A_n-1 )]	(7-70)

와 같은 체인규칙을 얻을 수 있다. 이제 이 체인규칙을 이용하여 식(7-68)을 다시 쓰면

[eqn: P`(t_i ,`t_j ) &=``P`(s_j ,` s_i_1 , `s_i_2 , ` cdots,` s_i_n `) ## &=`` p(s_j )` P`(s_i_1 vert s_j )` P`(s_i_2 vert s_j ,`s_i_1 )` P`(s_i_3 vert s_j ,`s_i_1 ,` s_i_2 ) ``cdots # & ~~~~~~~ P`(s_i_n vert s_j ,` s_i_1 ,` s_i_2 ,` cdots,` s_i_n-1 `)]	(7-71)

로 표현된다. 그러나 1-차 Markov 과정은 바로 이전의 심볼에만 종속됨으로

[eqn: P`(t_i ,`t_j ) ~=`` p(s_j )` P`(s_i_1 vert s_j )` P`(s_i_2 vert s_i_1 )` P`(s_i_3 vert s_i_2 ) ``cdots `` P`(s_i_n vert s_i_n-1 `)]	(7-72)

와 같이 각각 하나의 심볼에 대한 조건확률들의 곱으로 나타낼 수 있다. 또한 이 Markov 과정의 조건확률은 다음과 같이 계산된다.

[eqn: P`(t_i vert t_j ) &=`` {P`(t_i, t_j )} over {p(t_j )}~=``{P`(t_i, t_j )} over {p(s_j )} ## &=`` P`(s_i_1 vert s_j )` P`(s_i_2 vert s_i_1 )` P`(s_i_3 vert s_i_2 ) ``cdots `` P`(s_i_n vert s_i_n-1 `)]	(7-73)

따라서 식(7-67)에 주어진 Entropy 함수는

[eqn: H_M `(S^n ) &=` sum_{S^2n}` P(t_i ,` t_j )`` log_2 `` 1 over {P(s_i_1 vert s_j ) `P(s_i_2 vert s_i_1 )`` cdots`` P(s_i_n vert s_i_n-1 ) } ## &=` sum_{S^2n}` P(t_i ,` t_j ) ``left{log_2 `1 over {P(s_i_1 vert s_j )} `+` log_2 `1 over {P(s_i_2 vert s_i_1 )} # &~~~~~~~~~~~~~~~+`` cdots ``+`` log_2 ``1 over {P(s_i_n vert s_i_n-1 )} right}]  (7-74)

와 같이 정리된다.

우리가 앞에서 식(7-45)를 계산할 때와 마찬가지로, 식(7-74)의 각 항은 모두 동일한 합을 갖게 되는데, 그들 중 하나를 계산하여 보면 다음과 같다.

[eqn: & sum_{S^2n}``P`(t_i ,t_j ) ``log_2 `1 over {P`(s_i_2 vert s_i_1`)} ## &~~~=` sum_{S^2n} P(t_1 , t_2 ) ``cdots sum_{S^2} `P`(s_i_1 , s_i_2 ) ``log_2 `` 1 over {P`(s_i_2 vert s_i_1`)} ``cdots`` sum_{S^2n} P(t_q , t_r ) ## &~~~=`` 1 cdot ``cdots sum_S p(s_i_1 )sum_S P(s_i_2 vert s_i_1 ) log_2 ``1 over {P`(s_i_2 vert s_i_1`)} ``cdots`` cdot 1 ## &~~~=`` sum_S `p(s_i_1 )`` H_2 (bar S vert s_i_1 ) ~=`` H_2 (BAR S `)]	(7-75)

그러므로 식(7-74)의 각 항은 인접시스템의 Entropy로 표현되고, 이들이 모두 n 개 존재함으로, 우리가 예상했던 바와 같이, Markov 과정의 n-차 확장에 대한 Entropy는

[eqn: H_M `(S^n`) ~=~ n``H_2 (bar S )]	(7-76)

로 계산된다. 여기서는 단지 1-차 Markov 과정의 확장을 논의하였으나, 임의의 차수를 적용하더라도 이러한 과정은 그대로 진행될 수 있으며 그 표시방법과 계산의 복잡성 만 증가될 뿐이다.

이제 우리는 심볼 간의 상관관계까지 고려하는 Markov 과정을 적용한 소스코딩의 한계를 규정할 수 있게 되었으며, 그 한계는 주어진 확률구조를 사용하는 모든 소스코드 체계에 대하여 적용할 수 있다.

7-5  Entropy 함수의 강력성

우리는 이 장을 통하여 소스코드의 한계를 설정하는 Entropy 함수의 역할에 대하여 체계적으로 다루어 왔다. 또한 그러한 과정을 통하여 우리가 사용하는 여러 가지 코드체계들이 기본적으로 만족해야 하는 정보공학적 관계식들을 유도하였다.

이제, 이 장의 마지막 과제로서, 주어진 시스템의 확률분포

[eqn: P`(S)~=`` \{` p_i vert \prob. ``\that ~ s_i ~ \occurs, ~ i`=` 1,`2,` cdots ,` q \}]	(7-77)

가 확률추정 상의 오류 등에 의하여 작은 변화를 나타낼 때, Entropy 함수는 얼마나 민감하게 반응하는 지 검토해 보고자 한다.

우리는 제4-7절에서 Huffman 코드의 평균 코드길이가 확률추정오류에 의하여 영향 받는 정도를 조사한 바 있다. 이 절에서 취급하고자 하는 문제도 그와 유사한 개념을 갖는 것으로, 이른바 Entropy 함수의 민감성(sensitivity) 혹은 강력성(robustness)에 대한 검토 과정이라 할 수 있다.

Entropy 함수의 강력성에 대한 검토는 가정되는 확률분포에 따라 상한(upper bound) 혹은 하한(lower bound)을 조사하여 수행되는 극값(extreme values)에 의한 검토와 일반적인 확률분포를 적용하여 수행되는 추정확률에 의한 검토 등 여러 가지 방법으로 진행될 수 있다. 또한 부여되는 오류확률의 형태에 따라서도 서로 다른 결과가 유도되어 Entropy 함수에 대한 또 다른 측면을 볼 수 있다.

그러나 여기에서는 덧셈형 오류(additive error)를 부여한 상한에 대한 검토 만을 수행해 보기로 한다. 우리는 이러한 검토의 결과를 바탕으로 Entropy 함수의 강력성을 일반적 특성으로 추정해 낼 것이다.

제6장의 말미에서 식(6-60)으로 설명된 Entropy의 최대값

[eqn: H_2 `(S) ~=~log_2 `` q ``,~ p_i ``=`` 1 over q `, ~for ~i`=`1,`2,`cdots,` q]	(7-78)

로부터 출발하기로 한다.

덧셈형 오류에 의하여 발생되는 확률분포의 변화는 다음과 같이 표현할 수 있다.

[eqn: bar p_i ~=`` 1 over q ``／`` Delta`p_i ``, ~ i`=` 1,`2,` cdots ,`q]	(7-79)

여기서 원래의 확률분포, 즉 오류가 없는 상태의 정확한 분포는

[eqn: P~=`` \{` p_i `=` 1 over q vert \prob. ``\that ~ s_i ~ \occurs, ~ i`=` 1,`2,` cdots ,` q \}]	(7-80)

와 같이 표현되었고, 오류를 포함하는 확률분포는

[eqn: barP ~=`` \{` bar p_i vert \prob. ``\that ~ s_i ~ \occurs ``\with ``\errors, ~ i`=` 1,`2,` cdots ,` q \}]	(7-81)

로 표현된 것이다. 또한 그 오류들은 각각의 확률에 더해지는 형태로서 식(7-79)를 만족한다고 가정한다.

확률분포의 기본적인 성질에 의하여 각 분포의 확률합은

[eqn: sum_i=1^q ``p_i ~=``sum_i=1^q `` bar p_i ~=`` 1 ```,~ sum_i=1^q ``Delta`p_i ~=~0]	(7-82)

와 같이 주어진다.

한편 오류를 포함하는 확률분포 식(7-81)에 의하여 주어지는 Entropy 함수는 다음과 같이 표현된다.

[eqn: H_2 (bar S ) ~= ` sum_i=1^q `` left( 1 over q `+` Delta `p_i right) ``log_2 `` 1 over {1/q `+` Delta` p_i }]	(7-83)

앞에서도 언급한 바와 같이, 이 Entropy 함수는 □[eqn: barS] □를 파라미터로 사용하고 있으나 실질적으로는 [eqn: Delta `p_i]의 함수이다.

식(7-83)을 독립변수 [eqn: Delta `p_i]에 대하여 Taylor 급수로 전개하면

[eqn: H_2 (barS `) &=`` H_2 (barS `) right]_{Delta p_i `=`0} ~+`` sum_i=1^q `{partial`H_2 (bar S )} over {partial` Delta p_i} right]_{Delta p_i `=`0} cdot (Delta` p_i ) # &~~／`` sum_i=1^q `{partial^2` H_2 (bar S )} over {partial` Delta `p_i^2} right]_{Delta p_i `=`0} cdot (Delta p_i`)^2 ~+``` cdots]	(7-84)

를 얻게 된다. 이 식의 각 항을 계산하면 다음과 같다.

[eqn: H_2 (bar S ) right]_{Delta p_i `=`0} ``=`` sum_i=1^q ``1 over q log_2 ``q ``=``log_2 ``q ~=`` H_2 (S)]	(7-85)

[eqn: sum_i=1^q `{partial`H_2 (bar S )} over {partial` Delta p_i} right]_{Delta p_i `=`0} cdot (Delta` p_i ) ~=`` (log_2 ``q ``-`` log_2 ``e )`` sum_i=1^q `Delta` p_i ~=~ 0]	(7-86)

[eqn: sum_i=1^q `{partial^2` H_2 (bar S )} over {partial` Delta `p_i^2} right]_{Delta p_i `=`0} cdot (Delta p_i`)^2 ~=~ -`q``log_2 ``e ``sum_i=1^q ``(Delta p_i )^2]	(7-87)

따라서 식(7-84)의 Taylor 급수는 다음과 같이 표현된다.

[eqn: H_2 (bar S ) ~=` H_2 (S) `-` q` log_2 `e `sum_i=1^q (Delta`p_i`)^2 `／` (higher`` order``terms) ~ cdots]    (7-88)

우리는 이 식으로부터 확률분포 상의 작은 오류가 최대의 Entropy에 얼마나 영향을 주게 되는지 짐작할 수 있다. 주지하는 바와 같이, 확률분포 상의 작은 변화는 Entropy에 대하여 그 제곱(second order) 혹은 고차(higher order) 항으로 영향을 주므로 실질적인 Entropy 함수의 변화는 매우 작은 양이다. 이러한 사실은 지금까지 우리가 소스코딩의 한계로 규정하였던 Entropy 함수가 확률분포의 변화에 민감하지 않은 안정된 함수임을 나타내며, 결국 Entropy 함수는 소스코드 체계의 효율성을 한정하는 강력한 도구임을 말해준다.

연 습 문 제

7.1	일반적으로 Kraft 부등식은 임의의 Radix-r 에 대하여 성립한다(식 4-5). 이러한 사실을 이용하여 다음과 같이 정의되는 Radix-r Entropy

[eqn: H_r (S) ~=`` sum_i=1^q ``p_i ``log_r ``1 over p_i]

와 임의의 Radix-r 동시코드 체계의 평균 코드길이 사이에 다음과 같은 관계가 성립함을 보여라.

[eqn: L_\av ~>=~ H_r (S)]

또한 소스알파벳의 각 심볼들이 다음과 같은 발생 확률분포를 가질 때,

[eqn: p_i ~=`` 1 over r^l_i ``,````i`=`1,`2,` cdots,` q]

위 부등식의 등식부분이 만족됨을 보여라. (※ 정리 1의 증명과정을 참고하라.)

7.2	소스알파벳과 각 심볼의 발생확률이 다음과 같이 주어진다.

[eqn: &S ``=` \{`s_1 ,` s_2 ,` s_3 ,` s_4 ,` s_5 ,` s_6 \} # &~~p_1`Ａ`1/2, ~p_2 `Ａ` 1/4, ~p_3 `Ａ` 1/8, ~p_4 `Ａ` 1/16, ~ p_5 `Ａ` 1/32, ~p_6 `Ａ` 1/32]

(a) 이 시스템의 Entropy [eqn: H_2 (S)]를 구하라.

(b) 최소분산 Huffman 코드로 인코딩하고, 그 평균 코드길이 [eqn: L_H]를 구하라.

(c)	Shannon-Fano 방법으로 인코딩하고, 그 평균 코드길이 [eqn: L_SF]를 구하라.

(d) 위에서 구한 Entropy와 각 코드체계의 평균 코드길이 사이에 성립하는 관계를 정리 1의 관점에서 설명하라.

7.3	소스알파벳과 코드알파벳이 다음과 같이 주어진다.

[eqn: S~=`` \{` a,`b,`c,`d,`e,`f, `g,`h, `i,`j \} ``, ~~ C~=`` \{`0,`1,`2,`3 \}]

또한 각 심볼의 발생확률은 다음과 같이 추정되었다.

[eqn: &p_a `=`0.23,~p_b `=`0.12,~p_c `=`0.10,~p_d `=`0.09,~p_e `=`0.15 # &p_f `=`0.01,~`p_g `=`0.07,~p_h `=`0.14,~p_i `=`0.04,~p_j `=`0.05]

(a) 이 시스템의 Entropy [eqn: H_4 (S)]를 구하라.

(b) Radix-4 Huffman 코드로 인코딩하고, 그 평균 코드길이 [eqn: L_H(4)]를 구하라.

(c)	Radix-4 Shannon-Fano 코드으로 인코딩하고, 그 평균 코드길이 [eqn: L_SF(4)]를 구하라. (※ [eqn: log_4 ``(1/p_i ) ```<=``` l_i ```＠```log_4 ``(1/p_i ) `+` 1])

(d) 위에서 구한 Entropy와 각 코드체계의 평균 코드길이 사이에 성립하는 관계를 정리 1의 관점에서 설명하라.

7.4	소스알파벳 내의 임의 심볼에 대한 발생확률이 [eqn: p_i ```( i`=`1,`2,` cdots,` q)]로 주어질 때, 각 코드의 길이가

[eqn: log_r ``1 over p_i ```<=``` l_i ```＠``log_r ``1 over p_i `+`` 1 ``, ~i`=`1,`2,` cdots,` q]

로 주어지는 Radix-r 동시코드가 존재함을 보여라.

또한 그 코드체계의 평균 코드길이와 Radix-r Entropy 사이에 다음과 같은 관계가 성립함을 증명하라.

[eqn: H_r (S) ~<=~ L_(r) ~＠~ H_r (S) ``+`` 1]

7.5	소스알파벳과 각 심볼의 발생확률이 다음과 같이 주어질 때, 각각에 대하여 이진 Huffman 코드 및 이진 Shannon-Fano 코드를 구성하고, 그들의 평균 코드길이를 구하라. 또한 각 시스템의 Entropy를 구하여 식(7-31)과 식(7-32) 중 어느 것이 성립되는가를 밝히고 그 이유를 간단히 설명하라.

(a) S Ａ {s1, s2, s3, s4, s5, s6}

[eqn: p_1`Ａ` 1 over 3 , ~p_2 `Ａ` 1 over 4 , ~p_3 `Ａ` 1 over 6 , ~p_4 `Ａ` 1 over 9 , ~ p_5 `Ａ` 1 over 12 , ~p_6 `Ａ` 1 over 18]

(b) S Ａ {s1, s2, s3, s4, s5}

[eqn: p_1 `Ａ` 1 over 3 , ~p_2 `Ａ` 1 over 3 , ~p_3 `Ａ` 1 over 9 , ~p_4 `Ａ` 1 over 9 , ~ p_5 `Ａ` 1 over 9]

(c) S Ａ {s1, s2, s3, s4, s5}

[eqn: p_1 `Ａ` 1 over 2 , ~p_2 `Ａ` 1 over 4 , ~p_3 `Ａ` 1 over 8 , ~p_4 `Ａ` 1 over 16 , ~ p_5 `Ａ` 1 over 16]

(d) S Ａ {s1, s2, s3, s4, s5, s6, s7}

[eqn: p_1 `Ａ` 1 over 2 , ``p_2 `Ａ` 1 over 4 , ``p_3 `Ａ` 1 over 8 , ``p_4 `Ａ` 1 over 16 , `` p_5 `Ａ` 1 over 32 , ``p_6 `Ａ` 1 over 64 , ``p_7 `Ａ` 1 over 64]

7.6	소스알파벳 [eqn: S``=` \{s_1 ,` s_2 \}]의 발생확률 분포가 [eqn: p_1``Ａ`` 1/ 4, ~p_2 ``Ａ`` 3/4] 로	주어진다. 이 소스에 대하여

(a) Huffman 코드와 Shannon-Fano 코드를 각각 구성하고, 그들의 평균 코드길이 LH 및 LSF를 구하라.

(b) Entropy H2(S)를 구하여, 위에서 구한 평균 코드길이들과 비교하라 .

(c) 주어진 소스알파벳의 2-차 확장에 대하여 위 (a), (b) 과정을 반복하라.

(d) 주어진 소스알파벳의 3-차 확장에 대하여 위 (a), (b) 과정을 반복하라.

(e) 위의 모든 과정에 대하여 식(7-49)가 성립함을 보여라.

7.7	식(7-49)는 임의의 Radix-r 에 대하여 성립함을 보여라. 즉, □Shannon의 코딩정리□는 모든 Radix에 대하여

[eqn: lim_n->inf `L_n(r) over n ~=~ H_r (S)` ,~ for ~\all ~r]

와 같이 표현될 수 있음을 증명하라. (※ 정리 4의 증명과정을 참고하라.)

7.8	식(7-54) 및 식(7-58)에 주어진 Entropy 함수를 이용하여

(a) 3-차, 4-차, 5-차 조건 Entropy를 각각 구하라.

(b) 3-차, 4-차, 5-차 Markov 과정의 Entropy를 각각 구하라.

7.9	식(7-83)을 이용하여 식(7-85), 식(7-86), 식(7-87)을 각각 확인하라.

7.10*	수학적 귀납법을 이용하여 식(7-70)으로 표현되는 체인규칙(chain rule)을 증명하라.	(※ 식(1-15)를 □Basis step□(n=2)으로 하고, n=k 일 때 성립함을 가정하여 n=k+1 일 때도 성립함을 보여라.)

7.11*	다음의 천이그래프로 표시되는 2-차 Markov 과정에 대하여

(a) 주어진 Markov 과정을 상태천이를 위한 조건확률들로 나타내어라.

(b) 평형조건에서 각 상태의 확률을 구하라.

(c) 조건 Entropy [eqn: H_2 (S vert s_i_1 ,` s_i_2 )]를 구하라.

(d) 주어진 Markov 과정의 Entropy [eqn: H_M (S)]를 구하라.