제 6 장

정보의 특성과 ENTROPY

6-1  정보이론과 코딩의 관계

지금까지 우리는 소스코딩과 채널코딩으로 대별되는 코딩이론(coding theory)에 대하여 논의하여 왔다. 이제 코딩이론의 제반 개념을 바탕으로 하여 정보이론(information theory)을 유도하고, 양대 이론의 상호 관계를 취급하여 보기로 하자.

	정보공학

제 7 장 Entropy와 Shannon의 기본정리

제3장으로부터 제5장에 걸쳐서 다루어 졌던 코딩이론을 간단히 정리하여 언급한다면,  정보의 전송 및 저장에 있어서 발생하는 다음의 두 가지 문제에 대하여 그 해결책을 제시한 것이라고 할 수 있다.

(1) Redundancy 를 인가하여 채널 상의 각종 잡음에 대하여 적응할 수 있는 코드체계를 설계하는 문제 (채널코딩).

(2) 소스알파벳의 확률구조에 따라 처리할 자료를 압축하는 문제 (소스코딩).

그러나 이와 같은 코딩이론의 체계를 가지고는 우리가 도달할 수 있는 신뢰성 혹은효율성의 한계를 직접 측정할 수 없다. 다시 말해서 임의로 주어진 채널을 통하여 오류의 발생 없이 성취할 수 있는 최대의 전송속도(신뢰성)와 임의의 확률구조로 주어진 정보 소스를 표현할 수 있는 코드체계의 최소 평균 코드길이(효율성) 등은 코딩이론의 체계로 설명될 수 없는 부분이라는 것이다. 이러한 문제에 대한 해답을 얻기 위해서는 우리가 사용하는 채널과 소스의 구조를 수학적 모델로 설정하여 면밀하게 분석하여야 한다. 이것이 정보이론의 시작이다.

제2장의 그림 2-2를 통하여 설명한 바와 같이, 정보이론의 체계는 코딩이론의 기본적 개념으로부터 유도된다. 이것이 이 책의 차례가 먼저 코딩이론에 대하여 논하고 이를 바탕으로 정보이론의 체계를 취급하는 순서로 편성된 이유가 되거니와, 이렇게 하여 유도된 정보이론의 체계는 다시 코딩이론이 성취할 수 있는 한계를 제공하게 됨으로 이론의 아이러니라 아니 할 수 없다.

이 장에서 우리는 소스의 구조(the structure of source)를 평가하는 일반적인 방법으로 Entropy의 개념을 소개한다. 사실 □Entropy□라는 용어는 단지 정보이론에만 등장하는 것이 아니고, 물리학이나 화학 등에서 에너지의 상태를 표시하기 위하여 오래 전부터 사용되어 왔다. 그러나 정보이론의 체계에서 정의되는 Entropy의 개념은 이러한 자연과학적 의미에서 벗어나 정보의 양(amount of information)을 평가하는 기준으로서 정보공학적 의미를 갖는다.

따라서 Entropy는 우리가 제4장 및 제5장에서 취급하였던 소스코딩의 한계를 규정하며, 그 세부적 내용은 제7장에서 다루기로 한다. 소스코딩은 전송이나 저장 과정 이전에 정보 소스를 표현하는 선행적 과정이므로 채널 상의 잡음을 고려하지 않는 상태에서 다루어 진다. 그 결과로 우리는 이른바 Entropy와 평균 코드길이 사이에 성립하는 중요한 관계식을 유도하게 되는데, 이를 무잡음 코딩정리(noiseless coding theorem)라 한다.

정보이론은 Entropy에 의하여 소스의 특성을 규명할 뿐 아니라 잡음의 방지와 채널의 효율적 이용이라는 또 다른 관점에 대해서도 취급한다. 이를 위하여 우리는 채널의 특성을 규명하는 상호정보(제8장)와 채널용량(제9장)을 정의한다.

이 장에서 시작되는 정보이론의 체계를 통하여 우리가 추구하는 궁극적인 목표는 제10장에서 유도하게 되는 Shannon의 정리이다. 이는 제9장에서 정의되는 채널용량과 그 채널을 통하여 성취할 수 최대의 전송속도 사이에 성립하는 관계를 명시하여 준다. 우리는 이 탁월한 정리를 통하여, 무한히 적은 오류을 발생시키면서 최대의 전송속도에 무한히 접근하는 시스템을 구성할 수 있다는 사실을 증명하게 된다.

어떤 의미에서 Shannon의 정리는 제4장에서 설명한 Huffman 방식의 자료압축과 제3장에서 취급하였던 Hamming 방식의 잡음제어 특성을 하나의 코드체계 내에 실현한 상태를 규명하는 것이라고 볼 수 있다. 그러나 불행하게도 이 정리를 위하여 설정된 시스템의 모델은 극히 이상적인 것으로서 단지 우리가 실현할 수 있는 시스템의 한계 만을 제시할 뿐, 그 시스템을 구현하는 구체적 방법은 제시해 주지 못한다. 그럼에도 불구하고 이는 정보공학의 가장 핵심적인 정리로서, 디지탈 정보를 취급하는 다양한 이론적 체계를 세우는 데 필수적으로 도입될 만큼 매우 유용한 이론이다.

6-2  정보의 개념

정보이론에 있어서 □정보의 의미□는 정의하지 아니한다. 단지 유한한 원소를 갖는 소스알파벳이 존재하고, 그 알파벳 내의 심볼들이 연결되어 메시지를 형성한다면 그 메시지는 일정량의 정보를 갖게 된다고 평가하는 것이다. 따라서 정보이론은 □정보의 의미□를 규정하고자 하는 것이 아니고, □정보의 양□을 체계적으로 평가하고자 하는 것이다.

그렇다면 정보의 양은 어떠한 방법으로 측정되고 그 단위는 어떻게 설정되는가? 또한 측정된 정보의 양은 코딩과 어떠한 상관관계를 갖는가? 이들이 우리가 이 장을 통하여 해결하고자 하는 문제이다.

위에서 밝힌 것처럼 일정량의 정보를 갖는 메시지가 형성되기 위해서는 그 기반이 되는 소스알파벳과 그 내부의 심볼들에 대한 확률구조가 주어져야 한다. 우선 정보를 형성하고자 하는 소스알파벳이 다음과 같이 주어진다고 가정하자.

[eqn: S ~=`` \{`s_1 ,` s_2 , `cdots, `s_q ` \}]	(6-1)

이는 제4장에서 취급하였던 소스코딩의 시작과 동일하다. 그러나 여기서는 심볼의 수 q 를 확정하지 않으며, 각 심볼에 대하여 특별한 의미를 부여하지 않는다. 이렇게 함으로써 소위 정보를 형성하고자 하는 모든 알파벳을 우리의 논의에 포함시켜 포괄적이고 강력한 이론으로 전개할 수 있는 것이다.

식(6-1)에 주어진 소스알파벳의 각 심볼들은 다음과 같은 발생확률을 갖는다고 가정하자.

[eqn: p_i ``=` Pr` \{ s_i ````\occurs \}`, ~ for~ i ``=`` 1, `2, `cdots,` q]	(6-2)

여기서는 우선 소스알파벳의 확률구조를 각 심볼들의 독립적인 발생확률로 정의하였으나, 이는 다음 장에서 심볼 간의 상관관계까지 고려하는 Markov 과정으로 확장될 예정이다.

만일 식(6-1)에 주어진 소스알파벳 내의 심볼 중 어느 하나를 수신하였다면 수신측에서 얻은 정보의 양은 얼마일까? 더 나아가서 주어진 소스알파벳에 의하여 형성된 메시지를 다량 수신한 경우 수신측이 얻은 평균 정보의 양은 얼마일까?

문제의 개념을 좀 더 구체화하기 위하여 다음과 같은 두 가지 메시지를 수신하였다고 가정하여 보자.

<메시지 1> : □내일 아침에 태양이 뜬다.□

<메시지 2> : □금주 정보공학 휴강□

수신된 <메시지 1>은 거의 아무런 정보도 제공하지 못한다고 말할 수 있다. 왜냐하면 내일 아침에 태양이 뜰 것이라는 사실은 그 메시지를 받지 않더라도 알 수 있는 것이기 때문이다. 다시 말해서 그러한 사건이 발생될 확률은 거의 1 에 가깝기 때문에 □정보의 양□의 거의 0 에 가깝다는 것이다. 반면에 수신된 <메시지 2>는 매우 큰 정보를 제공한다. 왜냐하면 금주의 정보공학 강의가 모두 휴강되는 일은 좀처럼 있을 수 없는 일대 사건이기 때문이다. (물론 교수님에 따라 다르겠지만 …)  바꾸어 말하면, <메시지 2>는 발생확률이 거의 0 에 가까운 사건이므로 그 □정보의 양□은 매우 크다는 것이다.

또한 □정보의 양□은 □놀라움의 양□ 혹은 □불확실성의 양□이라고 표현할 수도 있을 것이다. <메시지 1>은 거의 아무런 □놀라움□이나 □불확실성□을 제공하지 못하는 반면, <메시지 2>는 매우 큰 □놀라움□과 □불확실성□을 제공한다. 이들은 사건의 발생 전후에 따라 구별하여 정의되기도 한다. 즉, 사건의 발생 이전에는 □불확실성의 양□이, 사건이 발생하는 동안에는 □놀라움의 양□이 각각 존재하며, 사건이 종료된 후에는 그 사건이 남긴 □정보의 양□이 존재한다고 말할 수 있으며, 이들의 양은 명백히 서로 같다.

이러한 상황은 각각의 발생확률을 갖는 심볼에 대해서도 그대로 적용될 수 있으며, 소위 □정보의 양□은 각 심볼의 발생확률에 대하여 모종의 역비례 관계를 가진다고 확신할 수 있다.

정보에 대한 이와 같은 논의를 기반으로, 각 심볼에 대한 정보의 양은 명백히 발생확률의 함수이므로 이를 I(p)로 표시하고, 이에 대하여 다음과 같은 세 가지 공리(axiom)를 부여한다.

(1) [eqn: I`(p) ~≥~ 0], 발생확률 p 를 갖는 모든 사건에 대하여	(6-3)

(2) [eqn: I` (p_1 `p_2 ) ~=`` I`(p_1 ) ``+`` I`(p_2 )], 두 개의 독립사건에 대하여	(6-4)

(3) [eqn: I`(p)]는 p에 대한 연속함수	(6-5)

제 (1)항의 공리는 □정보의 양□이 음수로 될 수 없음을 뜻한다. 발생확률이 1 인 사건에 대한 □정보의 양□을 0 으로 하여, 그 밖의 모든 사건에 대한 □정보의 양□은 양수로 주어진다.

제 (2)항의 공리는 특별히 Cauchy의 함수방정식(Cauchy functional equation)이라 부르며, 이는 정보량 함수 I(p)를 정의하는 실마리를 제공한다. 이 방정식의 의미는 명백하다. 두 개의 사건이 서로 독립적으로 발생하였다면, 그 두 사건에 의하여 제공되는 □정보의 양□은 합으로 주어질 것이라는 사실이다. 이 때, 만일 두 사건이 동일한 발생확률을 갖는다고 가정하여 보면

[eqn: I`(p`p) ~=`` I`(p^2 ) ~=`` I`(p) ``+`` I`(p) ~=`` 2`I`(p)]	(6-6)

와 같은 등식이 성립한다. 여기서 두 사건이 같은 발생확률을 가진다고 하여 두 사건이 동일한 사건일 필요는 없다. 오히려 두 사건은 서로 독립적으로 발생하는 별개의 사건으로 취급하는 것이 타당할 것이다.

식(6-6)을 n 개의 동일한 발생확률을 갖는 독립사건에 대하여 일반화하면

[eqn: I`(p^n ) ~=`` n` I`(p)]	(6-7)

를 얻는다. 이 식으로부터 우리는 함수 I(p)에 적용되는 □확률의 지수에 관한 규칙□을 인식할 수 있다. 또한 이 식에서는 지수 n 을 정수라고 가정하였으나, 이를 유리수로 확장하더라도 이러한 규칙은 그대로 성립한다.

따라서 파라미터의 지수에 관하여 식(6-7)의 규칙을 만족시키는 것은 로그함수(log function)임을 쉽게 이해할 수 있을 것이다.

마지막으로 제 (3)항의 공리는 발생확률(0□p□1)의 모든 값에 대하여 □정보의 양□이 존재하며 연속적으로 변화함을 설명하고 있다. 다시 말해서 사건의 발생확률이 주어지면 그에 대한 □정보의 양□은 언제나 유일한 값으로 결정된다는 것이다.

우리는 제 (2)항의 공리인 함수방정식으로부터 실마리를 찾고, 제 (1)항과 제 (3)항의 공리를 만족하도록 정보량 함수를 다음과 같이 정의한다.

[eqn: I`(p) ~==````k``` log_r ```p]	(6-8)

여기서 k는 상수이고, 로그함수의 밑수(base)는 소스코드가 사용하는 Radix에 따라 결정된다.

.  정보량 함수 I(p)를 정의할 때 사용되는 로그함수의 밑수를 비교할 소스코드의 Radix로 결정하면, 정보량은 그 코드길이와 동일한 단위를 갖게 된다. 다음 장에서 □Entropy와 소스코드와의 관계□를 다룰 때 이를 입증하게 된다.

제 (1)항의 공리로부터 상수 k 는 음수가 되어야 함을 알 수 있으며, 뒤에서의 계산을 간단하게 하기 위하여 k = １1 을 취한다. 결국 식(6-8)의 정보량 함수는 다음과 같이 표시된다.

[eqn: I`( p ) ~==~ - log_r ```p ~Ａ~ log_r ``` 1 over p]	(6-9)

우리는 이 식을 사용하여 여러 가지 사건에 대한 □정보의 양□을 측정하게 된다. 이제 지금까지의 과정으로부터 얻은 최종 정의 식(6-9)가 식(6-3), (6-4) 및 (6-5)로 주어진 공리를 만족하는지 살펴 보기로 하자.

첫째로 발생확률은 모든 사건에 대하여 0 □ p □ 1 을 만족하는 값이므로 식(6-9)의 정보량 함수는 언제나 0 보다 크거나 같다. 따라서 제 (1)항의 공리는 만족한다.

다음으로 서로 독립인 두 사건에 대하여 식(6-9)는 다음과 같이 표현된다.

[eqn: I`(p_1 `p_2 ) &=`` log_r ``` 1 over {p_1 `p_2 } ~=`` log_r ```1 over p_1 ``+`` log_r ```1 over p_2 ## &=`` I`(p_1 ) ``+`` I`(p_2 )]	(6-10)

따라서 제 (2)항의 공리도 만족한다.

마지막으로 제 (3)항의 공리는 로그함수가 주어진 구간 내에서 근본적으로 연속함수이므로 당연히 만족한다. 또한 이러한 사실은 식(6-9)의 그래프를 그려서 확인할 수 있다. 다음의 그림 6-1은 발생확률(0 □ p □ 1)에 대하여 식(6-9)의 변화를 도시한 것이다. □정보의 양□은 발생확률의 변화에 따라 0 부터 ∞ 까지 연속적으로 변화함을 알 수 있으며, 이로부터 제 (1)항의 공리도 다시 한 번 확인된다.

그림 6-1  정보량 함수 I (p)의 그래프

이제 정보량 함수 I(p)에서 사용하는 로그함수의 밑수(base)와 그에 따른 정보량의 단위에 대하여 생각하여 보자. 사실 이 문제는 뒤에서 소스코드의 길이와 관련지어 논의해야만 명확한 결론에 도달할 수 있다. 따라서 여기서는 가장 흔히 사용되는 몇 가지 밑수에 대하여 정보량의 단위를 정의하고, 그 타당성에 관해서는 다음 장에서 입증하기로 하겠다. 로그함수의 밑수에 따른 정보량의 단위는 다음과 같이 정해진다.

.  앞의 각주 1)을 보라.

[eqn: I`(p) ~=`` log_2 ```1 over p ````(bits)]	(6-11)

[eqn: I`(p) ~=`` log_e ```1 over p ````(nats)]	(6-12)

[eqn: I`(p) ~=`` log_10 ```1 over p ```(hartley)]	(6-13)

식(6-11)과 같이 밑수를 □2□로 하면 이진코드를 다룰 때 대단히 편리하다. 왜냐하면 이렇게 계산된 정보량은 이진코드의 길이와 동일한 단위인 □bit□로 주어지기 때문이다. 만일 식(6-12)와 같이 밑수를 □e□로 취하면 정보량에 대한 미분 및 적분에 편리하게 이용될 수 있을 것이다. 이 때 정해지는 정보량의 단위 □nat□는 자연대수(natural logarithm)를 사용하기 때문에 붙여진 이름이다. 또한 로그함수의 밑수를 □10□으로 취하면 정보량의 단위는 □hartley□가 되는데, 이는 정보의 양을 로그함수로 측정하는 방법을 최초로 제안한 R.V.L.Hartley의 이름에서 따온 것이다.

[예제 1]  52 장의 카드가 들어있는 완전한 카드함으로부터 한 장의 카드를 꺼내는 시행에 있어서, 다음 사건들에 대한 정보량을 □bit□, □nat□, □hartley□의 단위로 각각 구하라.

(a) 사건 A : □Ace 일 사건□

(b) 사건 B : □♥ 일 사건□

(c) 사건 C : □♣-Ace 일 사건□

[풀이]  먼저 각 사건의 발생확률을 구하면

[eqn: p(A) `=`4/52 `=` 1/13`, ```p(B) `=`13/52 `=` 1/4`, ```p(C) `=`1/52]

이 되고, 이들의 정보량은 식(6-11), (6-12), (6-13)에 의하여 다음과 같이 계산된다.

(a)

[eqn: I_A `(p) &=`` log_2 ``1/p ~=`` log_2 ``13 ~=`` {log` 13}``/` {log` 2} ~simeq~ 3.7004 ~(bits) # I_A `(p) &=`` log_e ``1/p ~=`` log_e ``13 ~simeq~ 2.5649 ~(nats) # I_A `(p) &=`` log_10 ``1/p ~=`` log_10 ``13 ~simeq~ 1.1139 ~(hartley)]

(b)

[eqn: I_B `(p) &=`` log_2 ``1/p ~=`` log_2 ``4 ~=~2.0000 ~(bits) # I_B `(p) &=`` log_e ``1/p ~=`` log_e ``4 ~simeq~ 1.3863 ~(nats) # I_B `(p) &=`` log_10 ``1/p ~=`` log_10 ``4 ~simeq~ 0.6021 ~(hartley)]

(c)

[eqn: I_C `(p) &=`` log_2 ``1/p ~=`` log_2 ``52 ~=`` {log` 52}``/` {log` 2} ~simeq~ 5.7004 ~(bits) # I_C `(p) &=`` log_e ``1/p ~=`` log_e ``52 ~simeq~ 3.9512 ~(nats) # I_C `(p) &=`` log_10 ``1/p ~=`` log_10 ``52 ~simeq~ 1.7160 ~(hartley)]

지금부터 우리는 □bit□ 라는 용어를 두 가지 용도로 사용하게 되었다. 그 하나는 이진수 한 개(□0□ 혹은 □1□)를 나타내는 단위로서의 용도이며, 또 하나는 정보량의 단위로서의 용도이다. 뒤에서 우리는 이들이 같은 차원(dimension)을 갖는다는 사실을 입증할 것이지만, 이들은 정확히 동일한 의미를 갖는다고 말할 수는 없다. 따라서 이진수의 단위인지 혹은 정보량의 단위인지 혼동의 우려가 있을 경우에는 정보량의 단위를 □bits of information□ 으로 표현하기도 한다.

앞에서 우리는 식(6-7)로 주어진 함수방정식의 특수해로서 식(6-11), (6-12), (6-13) 등을 찾아내었다. 만일 이들이 로그함수의 밑수를 하나로 설정하여도 유일한 해를 갖지 않는다면, 이것을 이용하여 일률적으로 모든 심볼의 정보량을 평가할 수는 없을 것이다. 따라서 우리는 이 절의 마지막 과제로서 로그함수의 밑수를 □2□로 설정하여 함수방정식 (6-7)이 유일한 해(unique solution)를 가짐을 입증하기로 한다. 증명은 모순법으로 진행된다.

함수방정식 (6-7)이 식(6-11)로 주어진 해 I(p) 외에 또 다른 해 J(p)를 갖는다고 가정하여 보자. 그러면 J(p)도 식(6-7)의 해이므로

[eqn: J`(p^n ) ~=`` n`` J`(p)]	(6-14)

가 성립한다. 비례상수를 K 라 하고 두 해의 차를 구해보면

[eqn: J`(p^n ) ``-`` I`(p^n ) ~=~ n`J`(p) ``-`` n`I`(p) ~=~ n ``left{ J`(p) ``-`` K ``log_2 ``1 over p right}]	(6-15)

와 같이 쓸 수 있다. 만일 비례상수 K 를

[eqn: K ~=~ {J`(p_0 )} over {log_2 ``(1/p_0 )}]	(6-16)

로 택한다면,  p = p0 에서 식(6-15)의 우변은 0 이 된다. 여기서 식(6-16)의 가정으로 볼 때 p0의 값은 0 혹은 1이 될 수 없다.

따라서 0, 1 을 제외한 모든 p에 대하여

[eqn: J`(p) ~=~ K`` log_2 ``1 over p]	(6-17)

이 성립한다. 이는 원래의 해와 일치하며, 따라서 함수방정식 (6-7)은 유일해를 갖는다.  또한 위 증명에서 제외된 값 p = 0, 1 에 대해서도 공리 식(6-5)에 의한 연속함수 조건과 식(6-16)의 극한에서 역시 유일해가 됨을 입증할 수 있다.

6-3  ENTROPY

발생확률을 갖는 하나의 심볼이나 사건에 대하여 식(6-9)로 표시되는 □정보의 양□이 존재함으로 이러한 심볼들의 집합인 소스알파벳에 대해서는 평균 정보의 양(expected amount of information)이 주어진다.

식(6-1)로 표현된 소스알파벳의 각 심볼들이 식(6-2)와 같은 발생확률을 갖는다고 가정할 때, 이 소스알파벳에 대한 평균 정보의 양은 식(1-94)와 위에서 정의한 식(6-9)를 이용하여 다음과 같이 표시할 수 있다.

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

이것을 주어진 소스알파벳으로 성립되는 신호시스템 S 의 Radix-r Entropy라 정의한다.

따라서 이진코드(radix-2)에 대해서는

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

와 같이 표현되는 Radix-2 Entropy를 정의할 수 있다.

이들 두 Entropy 사이의 변환관계는 단지 로그함수의 밑수에 관한 성질에 의하여 다음과 규정된다.

[eqn: H_r `(S) &=` sum_i=1^q`` p_i ```log_r ``1 over p_i ~=`sum_i=1^q`` {p_i `` log_2 ``(1/p_i ) } over {log_2 ``r } ## &=`` H_2 `(S) ``log_r ``2]	(6-20)

와 같이 성립함을 알 수 있다.

일반적으로 임의의 소스알파벳과 그 안에 존재하는 각 심볼들의 확률구조가 주어지면 Entropy는 유일하게 결정된다. 이는 앞 절의 마지막 부분에서 입증하였던 정보량 함수의 유일성과 맥을 같이 하는 것이며, 일반적인 확률분포에 대한 평균값이 유일하게 결정된다는 사실에 근거를 두고 있다. 어떤 의미에서 소스의 Entropy는 그 확률분포를 요약하여 표현하는 대표값으로도 볼 수 있다.

또한 식(6-18) 및 식(6-19)에서 알 수 있는 바와 같이, Entropy는 주어진 확률분포의 각 확률값에 역수를 취하고, 이들을 파라미터로 하는 로그함수의 가중평균(weighted average)을 계산한 것이다. 이러한 사실은 소스알파벳의 Entropy를 결정함에 있어 각 심볼의 정보량이 미치는 영향을 개별적으로 계산하여, 각각의 발생확률을 가중치로 하는 가중합(weighted sum)을 이루어 궁극적으로 시스템의 평균 정보량을 형성한다는 것을 말해 준다.

제4-5절에서 Huffman 코드를 설계할 때, 소스알파벳의 각 심볼에 대한 발생확률을 추정하기 위하여 각 심볼의 발생빈도수(frequency of occurrence)를 조사한 바 있다. 더구나 발생빈도수로부터 실제로 발생확률을 추정하지 않고 단지 이들에 비례하는 정수를 이용하여도 동일한 Huffman 코드를 구성할 수 있음을 설명하였다. 그러나 임의의 소스알파벳에 대한 Entropy를 산출하고자 할 때에는 그것의 확률구조가 완전히 알려져 있지 않은 상태에서 단지 각 심볼의 발생빈도수에 의존하여 Entropy를 구하는 것은 무의미하다.

예를 들어서 가상난수 발생기(pseudo-random number generator)를 생각하여 보자. 일반적으로 가상난수 발생기는 각 종류마다 특수하게 설정된 공식에 근거하여 차례로 숫자들을 발생시킨다. 만일 우리가 그 숫자들이 가상난수라는 사실을 인식하지 못하고 있다면, 아마도 각 숫자가 발생하는 빈도수에 의하여 발생확률을 추정하고 그것을 이용하여 Entropy를 계산하게 될 것이다. 성능이 우수한 가상난수 발생기는 실제적인 난수(random number)에 대한 시뮬레이션(simulation)을 매우 근사하게 수행할 것이므로, 발생기로부터 얻어지는 각 숫자들은 마치 완전히 무작위로 발생하는 것처럼 보일 것이다. 따라서 빈도수에 의하여 추정된 확률로 계산된 Entropy는 상당히 큰 값으로 나타나게 될 것이다. 그러나 만일 우리가 가상난수 발생기의 동작을 규정하고 있는 공식을 알고 있다면, 몇 개의 숫자가 발생한 후 그 다음에 발생할 숫자를 완벽하게 예측할 수 있다. 따라서 이 때에는 가상난수 발생기로부터 아무런 정보도 얻지 못하게 되며, 가상난수가 갖는 Entropy의 값은 0 이 된다.

이와 같은 상황으로 볼 때, 소스알파벳에 대한 Entropy는 단지 각 심볼의 발생빈도수 만 가지고는 계산될 수 없으며, 전적으로 그 심볼들의 확률구조(probability structure)에 의하여 결정된다고 하겠다.

식(6-18) 및 식(6-19)에 정의된 Entropy 함수는 오직 각 심볼의 발생확률에 관련되는 함수이다. 따라서 일반적인 함수의 표시방법을 사용한다면 H(p)로 나타내어야 마땅할 것이다. 그러나 Entropy는 임의의 소스알파벳에 관련된 체계의 정보량을 표현하는 함수임을 강조하기 위하여 관습적으로 소스알파벳 S 를 파라미터로 하여 H(S)로 표시한다. 여기에는 한 가지 예외가 있는데, 이론적인 접근에 흔히 등장하는 2-심볼 소스(two-symbol source : 소스알파벳 내에 오직 두 개의 심볼 만이 존재하는 소스)에 대한 Entropy는 H(p)로 표시하고 있다. 이는 각 심볼의 발생확률이 p 혹은 (1１p)로 표시됨을 강조하기 위한 것이라고 볼 수 있다.

[예제 2] 소스알파벳과 각 심볼의 발생확률이 다음과 같이 주어지는 신호시스템의 Entropy를 구하라. 단, radix-2를 사용한다.

(1) [eqn: S_1 ``=` \{ s_1 , ` s_2 \}, ~ p_1 `=` 1/2 , ~ p_2 `=` 1/2]

(2) [eqn: S_2 ``=` \{s_1 ,` s_2 , `s_3 , ` s_4 , `s_5 , `s_6 \}, ~~ p_i `=` 1/6 , ~for ~\all ~i]

(※ (1)번은 완전한 동전을 던지는 시행, (2)번은 완전한 주사위를 던지는 시행의 소스알파벳과 동일하다.)

[풀이]

(1) 식(6-19)를 이용하여

[eqn: H`(p) ~=` sum_i=1^2 ``p_i~ log_2 ``1 over p_i ~=`` log_2~ 2 ~=~1 ~(bit)]

(2)     [eqn: H`(S) ~=`` sum_i=1^6 ``p_i~ log_2 ``1 over p_i ~=`` log_2~ 6 ~simeq~2.585 ~(bits)]

제4-6절에서 우리는 확장된 소스에 대한 Huffman 코드를 작성하고 확장의 차수에 따른 평균 코드길이를 계산한 바 있다. 확장의 차수가 증가할수록 평균 코드길이는 점차 감소하지만, 그 감소의 경향은 어떤 점근선(asymtote)에 무한히 접근하는 형태로 그림 4-9와 같이 주어짐을 보았다. 그 때의 점근선은 평균 코드길이의 하한으로서 바로 지금 논의하고 있는 Entropy 임을 알 수 있다. 소스알파벳과 각 심볼의 발생확률은

[eqn: S ~=`` \{s_1 ,`s_2 \} ``, ~~p_1 `=` 2/3 , ~ p_2 `=` 1/3]	(6-21)

와 같이 주어졌으므로 Entropy는 식(6-19)에 의하여

[eqn: H_2 `(p) ~= `sum_i=1^2 ``p_i ```log_2 ``1 over p_i ~simeq~0.918296 ~(bits)]	(6-22)

로 계산된다. 확장의 차수가 아무리 증가하더라도 코드체계의 평균 코드길이는 식(6-22)에 주어진 값보다 작아질 수 없는 것이다. 이러한 사실은 단지 Huffman 코드에 대해서만 성립되는 것이 아니라, 우리가 사용할 수 있는 모든 소스코드에 대하여 성립한다. 우리는 이를 다음 장에서 입증하게 될 것이다.

이제 두 가지 특별한 경우에 대하여 Entropy의 식을 세워 보기로 하자. 그 하나는 이른바 2-심볼 소스(two-symbol source)에 관한 것이고, 다른 하나는 임의 갯수의 심볼을 포함하고 있으나 각 심볼의 발생확률이 모두 같은 경우, 즉 동확률 소스(equi- probable source)에 관한 것이다.

소스알파벳 내에 오직 두 개의 심볼 만 존재한다면, 그 중 하나의 발생확률이 p인 경우 나머지 하나의 발생확률은 당연히 (1１p)로 나타날 것이다. 따라서 이 소스에 대한 Entropy는 다음과 같이 주어진다.

[eqn: H_2 `(p) ~=`` p``log_2 ``1 OVER p ``／``` (1`-`p) ``log_2 ``1 OVER {1`-`p} ~(bits)]	(6-23)

위의 [예제 2](1)이나 식(6-21)에 주어진 소스알파벳은 바로 이와 같은 형태이다.

소스알파벳 내에 q 개의 심볼이 존재하고 각 심볼의 발생확률이 동일하다면, 그 발생확률은 모든 심볼에 대하여

[eqn: p_i ~=~ 1 over q `, ~ for ~i `=` 1, `2, `cdots, ` q]	(6-24)

로 주어지게 된다. 따라서 이러한 소스알파벳에 대한 Entropy는

[eqn: H_2`(S)~=` sum_i=1^q`` 1 over q `log_2 ``q ~=~ log_2 ``q ~(bits)]	(6-25)

와 같이 계산되며, 이는 하나의 심볼이 갖는 □정보의 양□과 일치하는 값이다. 위 [예제 2]의 (1), (2)는 모두 여기에 속한다.

제4-6절에서 우리는 일반적인 언어에 의하여 표현된 문자정보의 발생확률을 근사화하는 Zipf 분포(Zipf□s distribution)를 소개하고, 이에 대한 Huffman 코드를 작성한 바 있다. 식(4-33)에 표현된 바와 같이, Zipf 분포에서는 소스알파벳 내의 k 번째 심볼이 1/k에 비례하는 발생확률을 가지게 된다. 즉, 전체 N 개의 심볼에 대하여

[eqn: p_k ~=`` 1/k over S_N , ~~k``Ａ``1, `2, cdots, ``N]	(6-26)

로 표시되는 발생확률을 가지며, 여기서

[eqn: S_N ~=` sum_kＡ1^N `` 1 OVER k]	(6-27)

이다. 따라서 Zipf 분포의 Entropy는 다음과 같이 나타난다.

[eqn: H_2 `(S) &=`` sum_k=1^N ``p_k``log_2`` 1 over p_k ~=` sum_k=1^N ``1/k over S_N `` log_2 ``S_N over 1/k ## &=`` 1 over S_N sum_k=1^N `` 1 over k `left( log_2 ``S_N ```／``` log_2`` k right) ## &=`` 1 over S_N left( log_2 ``S_N sum_k=1^N ``1 over k ``+``sum_k=1^N `` {log_2 ``k } over k right) ## &Ａ`` log_2 ``S_N ```+``` T_N over S_N]	(6-28)

여기서 SN은 식(6-27)에 주어져 있으며,

[eqn: T_N ~Ａ` sum from kＡ1 to N ``{log_2``k} OVER k]	(6-29)

이다. 구하고자 하는 Entropy는 SN과 TN에 의하여 결정되며, SN과 TN은 다음과 같은 순환식에 의하여 계산할 수 있다.

[eqn: S_1 ``=``1 `, ~S_N ~=`` S_N-1 ``／`` 1 OVER N `, ~for ~ N``>=``2]	(6-30)

[eqn: T_1 ``=`` 0 `, ~ T_N ~=`` T_N-1 ``／`` {log_2``N} OVER N `, ~for ~N``>=``2]	(6-31)

소스알파벳의 심볼 수 N에 대하여 이들 순환식을 이용하여 SN, TN 을 구하고, 그 결과를 식(6-28)에 대입함으로써 Zipf 분포의 Entropy를 계산할 수 있다.

제4-6절에서는 이러한 Zipf 분포에 대하여 Huffman 코드를 작성하여 그 평균 코드길이를 블록코드의 길이와 비교한 바 있다 (표 4-1).  심볼의 수 N이 증가할수록 블록코드에 대한 Huffman 코드의 효율성은 더욱 두드러져 그 이득이 점차로 향상됨을 확인하였다. 그러나 위에서도 언급한 바와 같이, 우리가 사용하는 어떤 소스코드도 그 평균 코드길이가 Entropy 보다 짧아질 수는 없다.

다음의 표 6-1은 제4장의 표 4-1에 주어진 소스코드의 길이와 식(6-28)에 주어진 Entropy의 값을 심볼의 수 N에 따라 비교하여 나타낸 것이다.

표 6-1  Zipf 분포의 Entropy와 소스코드의 평균 코드길이

심볼의 수 N	블록코드의 길이 LB	Huffman코드의 길이 LH	Entropy H2(S)
2 4 8 16 32 64 128 256 512 1024	1 2 3 4 5 6 7 8 9 10	1.00 1.80 2.68 3.43 4.17 4.89 5.60 6.26 6.90 7.54	0.918 1.792 2.618 3.403 4.149 4.864 5.553 6.222 6.873 7.511

앞에서도 확인된 바와 같이, 심볼의 수가 증가될수록 Huffman 코드의 효율성은 블록코드에 비하여 점차 향상되지만, 그 평균 코드길이는 언제나 Entropy 보다는 크다.

[예제 3] 심볼의 수가 [eqn: N`=`8] 로 주어지는 Zipf 분포에 대하여

(1) Entropy [eqn: H_2 `(S)]를 구하고,

(2) Huffman 방식으로 인코딩하여 그 평균 코드길이 [eqn: L_H] 를 구하여 표 6-1의 세 번째 줄을 확인하라.

[풀이]

(1) Zipf 분포의 Entropy는 식(6-28)에 의하여

[eqn: H_2 `(S) ~=`` log_2 `` S_8 ``+`` T_8 over S_8]

와 같이 표시되고, 여기서 [eqn: T_8 , `` S_8]은 식(6-30) 및 (6-31)을 이용하여 다음과 같이 계산된다.

[eqn: T_2 &=`T_1 `+` {log_2 2} over 2 ``=``0.5,~ & S_2 ``=`` S_1 `+` 1 over 2 ``=`` 1.5 # T_3 &=`T_2 `+` {log_2 3} over 3 ``simeq`` 1.02832, & S_3 ``=`` S_2 `+` 1 over 3 ``simeq`` 1.83333 # T_4 &=`T_3 `+` {log_2 4} over 4 ``simeq``1.52832, & S_4 ``=`` S_3 `+` 1 over 4 ``simeq`` 2.08333 # T_5 &=`T_4 `+` {log_2 5} over 5 ``simeq``1.99270, & S_5 ``=`` S_4 `+` 1 over 5 ``simeq`` 2.28333]

[eqn: T_6 &=`T_5 `+` {log_2 6} over 6 ``simeq``2.42352, & S_6 ``=`` S_5 `+` 1 over 6 ``simeq`` 2.45 # T_7 &=`T_6 `+` {log_2 7} over 7 ``simeq``2.82457, & S_7 ``=`` S_6 `+` 1 over 7 ``simeq`` 2.59286 # T_8 &=`T_7 `+` {log_2 8} over 8 ``simeq``3.19957, & S_8 ``=`` S_7 `+` 1 over 8 ``simeq`` 2.71786]

따라서 구하는 Entropy는 다음과 같이 계산된다.

[eqn: H_2`(S) ~simeq~ log_2~ 2.71786 ``+`` 3.19957 over 2.71786 ~simeq~ 2.618 ~(bits)]

(2) Huffman 코드를 작성하기 위해서는 우선 각 심볼의 발생확률을 계산해야 함으로 식(6-26)과 (6-27)을 이용하여 pi (i = 1, 2, …, 8)를 얻고, 최소분산 Huffman 코드로 인코딩하면 다음과 같은 코드체계를 얻는다.

[eqn: &s_1 ~=~ 0~0 ~~~~&p_1 ~=~ 0.368 ~~~~&l_1 ~=~ 2 # &s_2 ~=~ 1~1 ~~~~&p_2 ~=~ 0.184 ~~~~&l_2 ~=~ 2 # &s_3 ~=~ 0~1~1 ~~~~&p_3 ~=~ 0.123 ~~~~&l_3 ~=~ 3 # &s_4 ~=~ 1~0~1 ~~~~&p_4 ~=~ 0.092 ~~~~&l_4 ~=~ 3 # &s_5 ~=~ 0~1~0~0 ~~~~&p_5 ~=~ 0.073 ~~~~&l_5 ~=~ 4 # &s_6 ~=~ 0~1~0~1 ~~~~&p_6 ~=~ 0.061 ~~~~&l_6 ~=~ 4 # &s_7 ~=~ 1~0~0~0 ~~~~&p_7 ~=~ 0.053 ~~~~&l_7 ~=~ 4 # &s_8 ~=~ 1~0~0~1 ~~~~&p_8 ~=~ 0.046 ~~~~&l_8 ~=~ 4]

따라서 구하고자 하는 평균 코드길이는

[eqn: L_H ~=` sum_i=1^8 `p_i ``l_i &=`` 0.368 cdot 2 ``+`` 0.184 cdot 2 ``+`` cdots ``+`` 0.046 cdot 4 ## &simeq~ 2.68]

와 같이 계산된다.

이상에서 계산된 결과는 표 6-1의 세 번째 줄과 일치한다.

제4-6절의 후반부에서는 Radix-r Huffman 코드의 구성 방법을 공부하였다. 이진 소스코드가 오직 두 개의 수준(level)으로 구성되는 반면, Radix-r 코드는 r 개의 수준을 갖는다. 이들의 평균 코드길이와 Entropy와의 관계를 검토하기 위하여 다음과 같은 소스알파벳과 코드알파벳을 갖는 시스템을 고려하여 보자. 이는 제4장의 [예제 11]에 제시된 것을 다시 한 번 사용한 것이다.

[eqn: S ~= ``\{s_1 ,` s_2 , `s_3 ,` s_4 , ` s_5 ,` s_6 ,` s_7 ,` s_8 \} ``, ~ C ~=`` \{`0, `1,` 2, `3 \}]	(6-32)

주지하는 바와 같이 이러한 시스템은 Radix-4 에 해당되며, 인코딩된 각 심볼을 나타내는 숫자들은 4 개의 수준을 갖는다. 소스알파벳의 각 심볼에 대한 발생확률이

[eqn: & p_1 `=`0.22`, ~p_2 `=`0.20`, ~p_3 `=`0.18`, ~p_4 `=`0.15 ## & p_5 `=`0.10`, ~p_6 `=`0.08`, ~p_7 `=`0.05`, ~p_8 `=`0.02]	(6-33)

와 같이 주어진다고 할 때, 이에 대한 Huffamn 코딩의 결과는 다음과 같다.

[eqn: &s_1 ``=``1 ~~~~& p_1 ``=``0.22 ~~~~& l_1 ``=``1 # &s_2 ``=``2 ~~~~& p_2 ``=``0.20 ~~~~& l_2 ``=``1 # &s_3 ``=``3 ~~~~& p_3 ``=``0.18 ~~~~& l_3 ``=``1 # &s_4 ``=``0``0 ~~~~& p_4 ``=``0.15 ~~~~& l_4 ``=``2 # &s_5 ``=``0``1 ~~~~& p_5 ``=``0.10 ~~~~& l_5 ``=``2 # &s_6 ``=``0``2 ~~~~& p_6 ``=``0.08 ~~~~& l_6 ``=``2 # &s_7 ``=``0``3``0 ~~& p_7 ``=``0.05 ~~~~& l_7 ``=``3 # &s_8 ``=``0``3``1 ~~& p_8 ``=``0.02 ~~~~& l_8 ``=``3 # &s_9 ~``:~ \dummy # &s_10 ~:~ \dummy]	(6-34)

따라서 이 코드체계의 평균 코드길이는

[eqn: L_H(4) ``= sum_i=1^8 ``p_i ``l_i(4) &=`` 0.22 TIMES 1 ``+`` 0.20 TIMES 1 ``+`` cdots ``+`` 0.02 TIMES 3 ## &=``1.47 ~~( 4- \level ~symbols )]	(6-35)

와 같이 계산된다. 여기서 평균 코드길이의 단위는 (bits)가 아닌 (4-level symbols)임을 주의하여야 한다. 다시 말해서 이 코드체계의 신호심볼 한 개는 이진수 2 bits에 해당한다.

식(6-35)에 주어진 평균 코드길이와 비교될 수 있는 Entropy는 식(6-18)을 이용하여 (r = 4) 로 두고 계산되어야 할 것이다. 시스템의 Entropy는 다음과 같이 주어진다.

[eqn: H_4 `(S) &= sum_i=1^8 ``p_i ``log_4 ``1 over p_i ## &=`` .22`log_4 `1 over .22 `+` .20`log_4 `1 over .20 `+` cdots `+` .02` log_4 `1 over .02 ## &simeq~ 1.377 ~~(4- \level ~symbols )]	(6-36)

따라서 Radix-4의 경우에도 Huffman 코드의 평균 코드길이는 시스템의 Entropy 보다 크다. 이러한 성질은 Huffman 코드에 대해서만 성립하는 것이 아니고, 우리가 사용하는 임의의 소스코드에 대하여 만족한다. 또한 임의의 Radix에 대해서도 만족한다.

[예제 4] 소스알파벳과 코드알파벳이 각각 다음과 같이 주어지고,

[eqn: S ~=`` \{`s_1 ,` s_2 ,` s_3 ,` s_4 ,` s_5 , s_6 `\} ``, ~~ C ~=`` \{` 0, `1, `2 \}]

각 심볼의 발생확률이

[eqn: &p_1 `=` 0.30, ~~~p_2 `=` 0.25, ~~~p_3 `=` 0.15# &p_4 `=`0.12, ~~~p_5 `=` 0.10, ~~~p_6 `=`0.08]

와 같을 때

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

(2) Entropy [eqn: H_3 `(S)]를 구하고, 위 (1)의 결과와 비교하라.

[풀이]

(1) 주어진 소스알파벳은 제4장의 [예제 12]에 제시된 것과 동일하다. 따라서 그 때의 결과를 사용하면 Huffman 코드는 다음과 같다.

[eqn: & s_1 ``=`` 1 ~~~ & p_1 ``=`` 0.30 ~~~ & l_1 ``=``1 # & s_2 ``=`` 2 ~~~ & p_2 ``=`` 0.25 ~~~ & l_2 ``=``1 # & s_3 ``=`` 0``1 ~~~ & p_3 ``=`` 0.15 ~~~ & l_3 ``=``2 # & s_4 ``=`` 0``2 ~~~ & p_4 ``=`` 0.12 ~~~ & l_4 ``=``2 # & s_5 ``=`` 0``0``0 ~~ & p_5 ``=`` 0.10 ~~~ & l_5 ``=``3 # & s_6 ``=`` 0``0``1 ~~~ & p_6 ``=`` 0.08 ~~~ & l_6 ``=``3 # & s_7 `````:```` \dummy]

따라서 이에 대한 평균 코드길이는

[eqn: L_H(3) ~=`` sum_i=1^6 `p_i ``l_i(3) &=`` 0.30 TIMES 1 `+` 0.25 TIMES 1 `+` cdots `+` 0.08 TIMES 3 # &=`` 1.63 ~~(3- \level ~symbols )]

으로 계산된다.

(2) 이 시스템의 Entropy 는 식(6-18)을 이용하여 (r = 3)으로 두고 계산되어야 한다.

[eqn: H_3 `(S) &=` sum_i=1^6 `p_i ``log_3 ``1 over p_i ## &=`` .3 ``log_3 ``1 over .3 `+` .25 ``log_3 ``1 over .25 `+` cdots `+` .08 ``log_3 ``1 over .08 ## &simeq~ 1.5284 ~~(3- \level ~ symbols )]

여기서도 Huffman의 평균 코드길이는 Entropy 보다 길다.

6-4  ENTROPY 함수의 성질

이 절에서는 앞 절에서 정의되고 몇몇 소스코드와 비교해 보았던 Entropy 함수에 관한 몇가지 중요한 성질들을 검토하고자 한다. 여기에 제시되는 성질들은 주로 수학적 특성이며, 이들은 뒤에서 정보이론의 핵심적인 개념들을 유도하는 데 매우 유용하게 사용된다.

Entropy 함수는 메시지의 수신과 같은 랜덤시행(random experiment)의 결과로부터 우리가 얻을 수 있는 정보의 양을 평균적으로 측정하여 준다. 따라서 이는 랜덤신호의 전송, 여파 및 저장 등 디지탈정보를 취급하는 여러 시스템에 있어서 필수적으로 측정되어야 하는 중요한 함수라고 할 수 있다.

일반적으로 정보 소스는 그로부터 얻을 수 있는 정보의 양이 가능한 한 최대가 되도록 설계되어야 할 것이다. 이것은 결국 정보 소스의 Entropy를 최대로 하려는 시도이므로, 이를 위해서는 소스알파벳 내의 각 심볼에 대한 발생확률을 조정할 필요가 있다. 이와 같은 일을 □시행의 설계(design of trials)□라 하며, 그 목적은 Entropy 함수의 극대화로 요약될 수 있다. 오늘날 Entropy 함수는 그 자체에 대한 연구도 활발하게 진행되고 있지만, 특히 그 응용면에서 많은 연구가 이루어지고 있다.

따라서 정보이론의 제반 개념 속으로 더 깊이 들어가기 전에 이른바 Entropy 함수에 대한 수학적 성질들을 검토해 두는 것은 매우 유용하리라 사료된다.

식(6-19)에 정의된 Entropy 함수는

[eqn: h`(p) ~=~ p ``log_2 ``1 over p `, ~ 0 ``<=``p ``<=``1]	(6-37)

와 같은 형태를 갖는 요소함수(elementary function)들의 합으로 구성되어 있다. 그러므로 이 함수의 특성을 명확히 해 두는 것은 결국 Entropy 함수의 각 항을 개별적으로 파악하는 일이 될 것이다.

먼저, 이 함수의 양 끝 점은 각각 p Ａ 1 인 경우의 함수값과 p → 0 에서의 극한값으로 주어진다. 즉

[eqn: h`(1) ~=~ 1` log_2 ``1 ~=~ 0]	(6-38)

이고, p → 0 에서의 극한값은 다음과 같이 주어진다.

[eqn: lim from p->0 ``p``log_2 `1 over p &=`` lim from p->0 ` {log_2 `(1 / p) } over { (1 / p) } ## &=`` log_2 ``e ``` lim_p->0 `{p`` left( - 1 / p^2 right) } over {(- 1 / p^2 )} ~=~ 0]	(6-39)

여기서 우리는 l□Hopital의 정리를 활용하였다.

이제,  0 ＠ p ＠ 1 인 구간에서 함수의 변화 형태를 알아보기 위하여 식(6-37)을 p에 관하여 미분하면

[eqn: d over dp h`(p) ~=~ log_2 ``1 over p ``+`` p ``left{ p``left(- 1 over p^2 right) log_2 ``e ``right} ``=`` log_2 ``1 over p `-``log_2 ``e]	(6-40)

를 얻는다.

식(6-40)은 p Ａ 0 에서 무한히 커지므로 함수의 왼쪽 끝 점에서는 접선의 기울기가 무한대(□)가 된다. 또한 p Ａ 1 에서 -log2 e 가 됨으로 함수의 오른쪽 끝 점에서는 음의 기울기를 갖는다.

또한 이 함수의 최대값을 얻기 위하여 식(6-40)의 우변을 0 으로 두고 풀면

[eqn: h` (p) ]_max ``=`` 1 over e log_2 ``e ~simeq~ 0.53074 `, ~for~ p`=`1 over e]	(6-41)

와 같은 결과를 얻는다.

이상의 과정을 종합하여 식(6-37)의 그래프를 그리면 다음과 같이 나타난다.

그림 6-2   요소함수 [eqn: h`(p) `=` p`` log_2 `` (1 / p)]의 그래프

식(6-23)은 2-심볼 소스(two-symbol source)의 Entropy를 표현하고 있다. 이것은 단지 두 개의 심볼이 존재하는 소스알파벳에 대하여 측정된 평균 정보의 양으로서, 흔히 사용되는 소스알파벳을 대변하지는 못한다. 그러나 발생확률 p의 변화에 따른 이 함수의 변화를 조사함으로써, 우리는 일반적인 Entropy 함수의 특성을 유추할 수 있을 뿐 아니라 소위 □시행의 설계□에 관한 개념을 파악할 수 있게 된다. 그러므로 현 시점에서 이 함수에 대한 그래프를 그려 보는 것은 매우 유용한 일이라 하겠다.

먼저, 식(6-23)에 주어진 함수의 양 끝 점은 각각 p → 0 및 p → 1에서의 극한값으로 주어진다. 즉

[eqn: lim_p->0 ``H`(p) ~=~ lim_p->1 ``H`(p) ~=~0]	(6-42)

여기서 우리는 식(6-38)과 (6-39)를 이용하였다.

이제,  0 ＠ p ＠ 1 인 구간에서 함수의 변화를 조사하기 위하여 식(6-23)을 p에 관하여 미분하면

[eqn: d over dp H_2`(p`) &=`` d over dp left{` p``log_2 `1 over p `／``(1`-`p) ``log_2 `1 over {1`-`p} right} ## &=~ log_2 `1 over p ``+`` (p)`(p) left(- 1over p^2 right) ``log_2 ``e # &~~+`` LEFT{ - log_2 `` 1 over {1`-`p} ``+`` (1`-`p)`(1`-`p)` 1 over {(1`-`p)^2} ``log_2 ``e ``right} ## &=`` log_2``1 over p ``-`` log_2 ``1 over {1`-`p}]	(6-43)

을 얻는다.

식(6-43)은 p Ａ 0 및 p Ａ 1 에서 각각 다음과 같이 표현됨으로

[eqn: d over dp H_2`(0) ~=~ inf ``,~~ d over dp H_2`(1) ~=~ -inf]	(6-44)

함수의 양쪽 끝 점에서는 모두 수직접선(vertical tangent)을 가지며 그 기울기는 서로 반대의 부호를 나타낸다.

또한 함수의 최대치를 구하기 위하여 식(6-43)의 우변을  0 으로 두고 풀면

[eqn: H_2 `(p) ]_max ``=`` 1 `, ~for~ p`=`1 over 2]	(6-45)

을 얻는다.

이상의 내용을 종합하여, 2-심볼 소스의 Entropy H2(p)에 대한 그래프를 그리면 다음의 그림 6-3과 같다.

그림 6-3  [eqn: H_2`(p) `=` p` log_2 ` (1 / p) `+` (1-p) `log_2 `\{ 1/(1-p) \}]의 그래프

2-심볼 소스의 Entropy가 pＡ0.5 에서 최대값을 갖는다는 사실은 우리에게 시사해 주는 바 크다. 하나의 심볼에 대한 발생확률이 0.5 라는 것은 나머지 다른 심볼의 발생확률도 0.5 임을 말해주며, 결국 두 개의 심볼이 동일한 확률을 가질 때 소스는 최대의 Entropy를 갖게 됨을 알 수 있다. 이러한 사실은 2-심볼 소스알파벳에 대해서만 성립하는 것이 아니고, 일반적인 모든 소스알파벳에 대해서도 각 심볼이 동일한 발생확률을 가질 때 최대의 Entropy가 주어진다. 우리는 이를 이 절의 후반에서 수학적으로 증명할 것이다. 이른바 □시행의 설계□에 있어서도, 시스템이 최대의 정보량을 갖도록 설계하기 위해서는 바로 이 기준을 활용하여야 할 것이다.

다음으로, 앞에서 언급하였던 개념적 사실을 수학적으로 확인하기 위하여 Entropy 함수에 대한 몇 가지 정리를 마련하기로 한다.

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

[eqn: & ln `x ~<=~x``-``1 ``, ~~for ~\all ~ \real ~x``>=``0 ## & log_2 ``x ~<=~ (x ``-`` 1) `log_2 ``e ``, ~~for ~\all ~ \real ~x``>=``0]	(6-46)

여기서 등식은 [eqn: x ``=`` 1] 일 때 성립한다.

♠ 증명

이 정리는 다음과 같은 두 가지 방법으로 증명할 수 있다.

<방법 1>  함수 [eqn: y ``=`` ln``x] 그래프 위의 한 점 (1, 0)에서 접선의 방정식을 구해 보자. 우선 그 접선의 기울기는 도함수의 성질로부터

[eqn: dy over dx right | _{x`=`1} ~=~ {d```(ln `x)} over dx right| _{x`=`1} ~=~ 1]	(6-47)

로 얻어진다. 그러므로 구하고자 하는 접선의 방정식은

[eqn: y``-``0 ~=~ 1``(x``-``1)]	(6-48)

와 같이 나타나며, 이를 정리하면

[eqn: y ~=~ x``-``1]	(6-49)

을 얻을 수 있다.  이제 [eqn: y ``=`` ln``x] 의 그래프와 접선 식(6-49)의 그래프를 동일한 좌표 그려보면 다음의 그림 6-4와 같이 나타난다. 우리는 이 그래프로부터 직접

[eqn: ln``x ~ <=~ x``-``1]	(6-50)

이 성립함을 알 수 있으며, 여기에 로그함수의 규칙을 적용하면

[eqn: log_2 ``x ~<=~ (x``-``1) ``log_2 ``e]	(6-51)

을 얻게 된다. 또한 그래프로부터 식(6-50)과 (6-51)은 [eqn: x`>=`0] 인 모든 실수 [eqn: x] 에 대하여 만족하며, 등식은 [eqn: x``=`1] 일 때만 성립함을 알 수 있다.	■

그림 6-4  함수[eqn: y`=`x`-`1``과 ```y`=`ln`x] 의 그래프

<방법 2>  식(6-46)의 좌변에서 우변을 빼어 하나의 함수를 정의하자.

[eqn: f`(x) ~=`` ln``x ```-``x ``+``1]	(6-52)

이 함수를 [eqn: x] 에 관하여 미분하면

[eqn: d over dx `f(x) ~=`` 1 over x ``-``1]	(6-53)

을 얻는다. 따라서 식(6-52)의 함수는 [eqn: x`<`1] 인 영역에서 증가하고, [eqn: x`>`1] 인 영역에서 감소한다. 또한 함수의 최대값을 구하기 위하여 식(6-53)의 우변을 0 으로 놓고 풀면

[eqn: f`(x) ] _max ~=~ 0 ``, ~ \at ~ x``=``1]	(6-54)

을 얻는다. 그러므로 식(6-52)는 0 보다 작거나 같다. 따라서 정리는 성립하며, 등식은 [eqn: x`=`1] 에서만 만족한다.	■

정리 2 : Gibbs 부등식 □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

두 개의 확률분포 [eqn: x_i `, ```y_i ~(i`=`1,`2,`cdots,`q )]에 대하여 다음 부등식이 성립한다.	[eqn: sum_i=1^q ``x_i ``log_2 ``y_i over x_i ~<=~ ``0]	(6-55)

여기서 [eqn: x_i , ``y_i]는 확률분포이므로 [eqn: sum_i=1^q `x_i ```Ａ` sum_i=1^q`y_i ```Ａ``1] 을 만족하며, 등식은

[eqn: x_i ~=`` y_i ``, ~for ~\all ~ i`=`1,`2,`cdots,`q]	(6-56)

일 때 성립한다.

♠ 증명

로그함수의 성질에 의하여 식(6-55)의 좌변은

[eqn: sum_i=1^q``x_i ``log_2 ``y_i over x_i ~=~ log_2 ``e `sum_iＡ1^q ``x_i ``` ln`y_i over x_i]	(6-57)

와 같이 쓸 수 있으며, 여기에 앞에서 증명한 식(6-46)을 적용하면

[eqn: sum_iＡ1^q ``x_i ``log_2`y_i over x_i &<= ``log_2 ``e ``sum_iＡ1^q ``x_i ``left(y_i over x_i ``-``1 right) ## &Ａ``log_2 ``e `` sum_iＡ1^q `(y_i ``-`` x_i ) ## &Ａ`` log_2 ``e `` left(sum_iＡ1^q `y_i ``-`` sum_iＡ1^q `x_i `right) ~Ａ~0]	(6-58)

로 나타난다. 그러므로 정리는 성립하며, 등식은 식(6-56)을 만족하는 경우에만 성립한다. 다시 말해서 식(6-55)의 등식부분은 모든 i 에 대하여 xi Ａ yi 일 때, 즉 동일한 확률분포에 대하여 성립된다.	■

정리 3 : Entropy의 최대, 최소 □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

Radix-2 Entropy 함수

[eqn: H_2 `(S) ~=`` sum_iＡ1^q ``p_i ``log_2 ` 1 over p_i]	(6-59)

의 값은 다음과 같은 범위 내에 존재한다.

[eqn: 0 ~<=~ H_2`(S) ~<=~ log_2 `` q]	(6-60)

즉, Entropy의 최소값은 0 (하나의 발생확률이 1 이고, 나머지 모든 발생확률은 0 인 경우)이고, 최대값은 [eqn: log_2 ``q] (모든 발생확률이 1/q 로 동일한 경우)이다.

♠ 증명

소스알파벳 내의 심볼들 중에서 임의의 한 개가 발생확률 1 을 갖고, 다른 모든 심볼들은 발생확률 0 을 가진다고 가정하면, Entropy 함수는

[eqn: H_2 `(S) ~=` sum_i=1^q ``p_i ``log_2 ``1 over p_i ~=` 1`log_2``1 ~=~0]	(6-61)

으로 주어진다. 한편 모든 Entropy 함수는 0 보다 작을 수 없으므로 그 최소값은 0 이다. 그러므로 식(6-60)의 좌측 부등식은 성립한다.

다음으로 식(6-59)로 주어지는 Entropy 함수에서[eqn: log_2 ``q] 를 빼어 새로운 함수를 정의하자. 즉

[eqn: g`(p) ~==~H_2`(S) ``-`` log_2 ``q ~Ａ` sum_i=1^q ``p_i ``log_2 `1 over p_i ``-`` log_2 ``q]	(6-62)

라 두자.

이 식의 우변을 다음과 같이 조작하면, 다음과 같은 관계식을 얻을 수 있다.

[eqn: g`(p) &Ａ`` sum_i=1^q ``p_i ``log_2 `` 1 over p_i ``-`` log_2 ``q ``sum_i=1^q ``p_i ## &Ａ`` sum_i=1^q ``p_i ``log_2 ``1/q over p_i]	(6-63)

여기서 1/q (i = 1, 2, …, q) 과  pi (i = 1, 2, …, q) 는 모두 확률분포이므로 앞에서 증명한 Gibbs 부등식 (6-55)를 적용할 수 있다. 그러므로

[eqn: g`(p) ``=`` H_2`(S) ``-`` log_2 ``q ~<=~ 0]	(6-64)

은 성립한다.

따라서 Entropy 함수 [eqn: H_2`(S)]의 최대값은[eqn: log_2 ``q] 이며, 식(6-60)의 우측 부등식도 역시 성립한다. 우리는 이미 식(6-25)에서 이러한 Entropy 값은 모든 심볼이 동일한 발생확률을 가질 때 나타난다는 사실을 입증한 바 있다. 따라서 정리의 모든 부분이 성립한다.	■

이 중요한 부등식은 우리가 제4-7절에서 사용하였던 □Lagrange multiplier method□를 써서 증명할 수도 있다. 다음과 같은 함수를 생각하자.

[eqn: f`(p_1, ` p_2, ` cdots, ` p_q ) ~= ~log_2 ``e `` sum_i=1^q ``p_i ``ln ` 1 over p_i ``／`` lambda ``left( sum_i=1^q ` p_i ``-``1 right)]	(6-65)

여기서 [eqn: lambda]는 Lagrange 파라미터이다.

이를 각각의 pi (i = 1, 2, …, q)에 대하여 편미분하고, 최대값을 구하기 위하여 0 으로 두면

[eqn: partialf over {partial p_i} ``Ａ``log_2 ``e} ``left( ln `1 over p_i ``-`` 1 right) ``／`` lambda ~=`` 0 `, ~ i`=`1,`2,`cdots,`q]	(6-66)

와 같은 관계식을 얻는다. 이를 ln(1/pi)에 대하여 풀면

[eqn: ln`1 over p_i ~=~ 1 ``-`` lambda over {log_2 ``e}` , ~ i`=`1,`2,`cdots,`q]	(6-67)

로 나타난다. 이 식의 우변은 i 를 포함하지 않는 상수임을 알 수 있다. 따라서 좌변도 모든 i 에 대하여 상수이다. 발생확률 pi가 i에 관계없는 상수라면, 그 값은 명백히 1/q이다.

따라서 Entropy 함수의 최대값은[eqn: log_2 ``q] 이며 정리는 성립한다.	■

앞에서 몇 가지 예제를 통하여 증명 없이 언급하였던 사실이 확인되었다. 임의의 소스알파벳이 최소의 Entropy를 갖기 위한 조건은 각 심볼 중 하나가 발생확률 1로 나타나고 나머지 심볼들은 발생확률 0, 즉 전혀 나타나지 않는 경우이며, 이 때 소스알파벳의 Entropy는 0 이다. 또한 최대의 Entropy를 갖기 위한 조건은 소스알파벳 내의 모든 심볼들이 동일한 발생확률 1/q를 갖는 경우이며, 이 때 소스알파벳의 Entropy는 [eqn: log_2 ``q]이다.

이러한 Entropy 함수의 특성을 기반으로 하여 다음과 같은 의문을 제기하여 보자. □동일한 자형(font)과 동일한 문자 수를 포함하는 책들 중에서 최대의 정보량을 갖는 것은 어떤 책인가?□

만일 사회과학 혹은 인문과학적 개념으로 이 문제에 접근한다면, 아마도 □독자가 모르는 내용을 가장 많이 포함하고 있는 책□ 정도의 해답이 구해지지 않을까? 우리는 제2-3절에서 정보에 대한 공학적 의미는 그 사회과학적 의미와 판이하게 다르다는 사실을 언급한 바 있다. 이 문제의 해답도 그 관점을 □정보의 양□에 두느냐 혹은 □정보의 내용□에 두느냐에 따라 완전히 달라진다.

지금까지 논의된 정보공학적 개념으로 이 문제에 접근한다면, □동일한 발생확률을 갖는 무작위 추출 문자들로 구성된 책□이 최대의 정보량을 담고 있다고 할 수 있다. 이 책에 포함되어 있는 각 문자들은 전혀 예측할 수 없이 나타나며 그 내용도 전혀 파악할 수 없다. 단지 전체적으로 각 문자의 발생빈도수가 모두 같으며 이들이 무작위로 추출되어 나열되고 있을 뿐이다.

이러한 예로부터 우리는 정보에 관한 공학적 개념이 사회과학이나 인문과학 혹은 일반적으로 인식되고 있는 개념과는 매우 다르다는 사실을 다시 한 번 인식할 수 있다. 요컨대, C.E.Shannon에 의하여 제창된 정보공학에 있어서 정보의 개념은 컴퓨터, 전화, 기억장치, 통신시스템 등 전적으로 □정보의 양□에 의하여 파악되는 분야와는 잘 부합되지만, 일반적으로 □정보의 의미□ 혹은 □정보의 내용□을 중시하는 분야와는 잘 부합되지 않는다.

여기서 독자들은 □정보의 양□을 측정하고자 하는 이론의 제한성이 그 이론을 더욱 유용하게 만들기 위하여 엄격히 규정된 것이라는 사실을 인식해야 할 것이다. □정보의 의미□나 □정보의 내용□에 상관 없는 이론은 어떠한 의미나 내용의 정보도 취급할 수 있음을 암시하며, 이와 같이 엄격히 제한된 이론을 바탕으로 여러 가지 복잡한 상황에서 나타나는 혼동이나 막역함 등을 배제하여 □정보의 양□에 관한 유용한 결과들을 도출시킬 수 있는 것이다.

소스알파벳의 각 심볼들이 균일분포(uniform distribution)를 가질 때 최대의 정보량을 포함한다는 원리를 다음과 같은 간단한 예에 적용하여 보자.

□표준 학점체계(A, B, C, D, F)를 사용하는 □학부 성적표□, □석사과정 성적표□, □박사과정 성적표□ 중 가장 큰 정보량을 갖는 것은 어떤 것인가? 또한 일반적으로 최대의 정보량을 갖는 성적표는 어떻게 작성될 수 있는가?□

(물론 교수님에 따라 다르겠지만), 일반적으로 □학부 성적표□는 대학원 성적표에 비하여 표준 학점체계의 다섯 가지 학점이 고르게 분포한다. 특히 □박사과정 성적표□에서는 C, D 혹은 F 학점을 거의 찾아볼 수 없는 것이 보통이다. 그렇다면 위의 세 가지 성적표 중에서 가장 큰 정보를 포함하고 있는 것이 □학부 성적표□라고 할 수 있지 않을까?

한 학기 동안 어떤 과목을 수강하는 학생들이 모두 열심히 공부하여 매우 우수한 성적을 거두었기 때문에 모든 학생들에게 A 학점을 부여하기로 약속되었다면, 그 과목의 성적이 학생들에게 주는 정보는 전혀 없다. 반대로 모든 학생들에게 F 학점을 주기로 약속되었다고 하여도 역시 그 과목이 주는 정보는 없다. 이러한 경우 학생들은 성적표에 대하여 아무런 기대감(uncertainty)이나 놀라움(surprise)을 표시하지 않을 것이다. 또한 성적에 대하여 아무도 불평하지 않을 것이다(?).

한편, 성적표에 의하여 최대의 정보량을 주기 위해서는 각 학생의 시험성적에 관계없이 위의 다섯 가지 학점을 무작위로 고르게 부여하면 될 것이다. 이러한 경우 학생들은 자신의 한 학기 동안의 노력에 상관없이 무작위의 성적을 받게 될 것이므로 성적표를 받을 때 최대의 놀라움을 표시하게 될 것이다. (어불성설도 많고 항의도 많겠지만 …)

연 습 문 제

6.1	어떤 TV 화면이 300,000 개의 화소(pixel)로 구성된다고 한다. 이 화소들은 가로 방향으로 600 개, 세로 방향으로 500 개씩 격자형으로 배열되어 있다. 그리고 각각의 화소는 10 개의 grey-level을 가지며, 각 grey-level은 동일한 확률로 나타난다고 가정한다. 이러한 TV의 한 화면이 갖는 정보량은 얼마인가?

(a) bit 단위로 계산하라.

(b) nat 단위로 계산하라.

(c) hartley 단위로 계산하라.

(d) □bit □, □nat □, □hartley□ 사이에 성립하는 일반적 관계를 유도하라.

6.2*	어떤 아나운서가 하나의 TV 화면을 설명하는 데 1,000 개의 단어를 사용한다. 이 아나운서가 사용하는 총 어휘는 10,000 단어이고 각 단어는 동일한 확률로 나타난다고 가정한다.

(a) 이 아나운서가 하나의 TV 화면을 설명하는 데 있어서 주어지는 정보량은 얼마인가? bit, nat, hartley 를 단위로 각각 구하라.

(b) 만일 TV 화면이 문제 6.1에 제시된 것과 동일하다면, 이 아나운서는 그의 1,000 단어로 한 화면을 완벽하게 설명할 수 있다고 볼 수 있는가? 정보이론적 관점에서 그 여부를 말하라.

(c) 이 문제의 결과로 볼 때, □a picture is worth a thousand words□라는 격언은 □picture□에 대한 과대평가인가 혹은 과소평가인가? 정보이론적 관점에서 설명하라.

6.3	정보이론에서는 정보의 정의를 별도로 확정하지 아니한다. 그렇게 하는 이유를 간단히 설명하라.

6.4	정보량의 정의 식(6-8)이 세 가지 공리 식(6-3), (6-4), (6-5)를 모두 만족함을 증명하라.

6.5	다음과 같은 사건에 의하여 주어지는 정보의 양을 각각 bit, nat, hartley 를 단위로 계산하라.

(a) 52 장의 카드가 들어있는 완전한 카드함으로부터 한 장의 카드를 뽑았을 때 □♣□일 사건

(b) 완전한 두 개의 주사위를 동시에 던져 모두 □5□ 이상의 숫자가 나타나는 사건

(c) ASCII 코드(표 2-1)에 포함되어 있는 128 개의 심볼로부터 임의로 3 개의 심볼을 선택하였을 때, 모두 영문 소문자가 되는 사건

(d) 완전한 동전을 던져 □Head□가 나타나는 사건

6.6	소스알파벳 [eqn: S ``=`` \{`s_1 ,` s_2 ,` s_3 ,` s_4 ,` s_5 ,` s_6 \}]의 각 심볼들이

[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 32]

의 발생확률을 갖는다.

(a) 각 심볼이 갖는 정보량을 bit 단위로 구하라.

(b) 이 시스템의 Entropy H2(S) 를 구하라.

(c) 이를 Huffman 방법으로 코딩하고, 그 평균 코드길이 LH 를 구하라.

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

6.7	소스알파벳과 각 심볼의 발생확률이 다음과 같이 주어질 때, 위 문제 6.6의 과정을 반복하라.

(a) [eqn: S_1 &=`` \{` s_1 ,` s_2 ,` s_3 ,`s_4 ,`s_5 ,s_6 \} # &p_1 `=`1/3 ,~~p_2 `=`1/4 ,~~~p_3 `=`1/6 # &p_4 `=`1/9 ,~~p_5 `=`1/12 ,~~p_6 `=`1/18]

(b) [eqn: S_2 &=`` \{` s_1 ,` s_2 ,` s_3 ,`s_4 ,`s_5 \} # &p_1 `=` p_2 `=`1/3 ,~p_3 `=` p_4 `=`p_5 `=`1/9]

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

(d) [eqn: S_4 &=`` \{` s_1 ,` s_2 ,` s_3 ,`s_4 ,`s_5 ,`s_6 ,` s_7 \} # &p_1 `=`1/2 ,~~~p_2 `=`1/4 ,~~~p_3 `=`1/8 ,~~p_4 `=`1/16 # &p_5 `=`1/32 ,~~p_6 `=`1/64 ,~~p_7 `=`1/64]

6.8	식(6-7)에 표현된 Cauchy 함수방정식의 해는 식(6-8)에 정의된 정보량 함수로 유일하게 주어짐을 보여라.

6.9	Zipf 분포에 대한 Entropy 식(6-28)과 순환식 (6-30), (6-31)을 이용하여 표 6-1의 N Ａ 2, 4, 16에 대하여 확인하라. (※ N Ａ 8 인 경우는 [예제 3]에서 확인하였다.)

6.10*	(Zipf 분포에 대한 Huffman 코드의 평균 코드길이와 Entropy의 비교 :

Computer Programming)

(a)	다음 그림과 같은 입출력 구조도를 이용하여, 심볼의 수 N 을 입력으로 받아 식(6-26)으로 주어지는 Zipf 분포의 발생확률 P [ i ] 를 계산하고, 이어서 제4장에서 구현하였던 Huffman 인코더를 이용하여 평균 코드길이 L 을 계산하는 컴퓨터 프로그램을 작성하라.

입력	Zipf Probability Calculation	발생확률	Binary Huffman Encoder		Avg. Code Length Calculation	평균코드 길이
N : # of Symbols		P[i], i=1,2,…,N		Huffman Codes & P[i]		L

(b) 다음 그림과 같은 입출력 구조도를 이용하여, 심볼의 수 N 에 따르는 식(6-30) 및 식(6-31)의 순환식을 계산하고, 이어서 식(6-28)로 주어지는 Zipf 분포의 Entropy H2(S) 를 계산하는 컴퓨터 프로그램을 작성하라.

입력	Zipf Recursions	부분합	Zipf Entropy Calculation	Entorpy
N : # of Symbols		SN,TN		H2(S)

(c) 심볼의 수 N 을 여러 가지로 변화시켜 작성된 프로그램을 시험하고, 표 6-1을 확인하라.

6.11*	양의 영역에 한정되며(0＠x＠□), 그 평균이 A인 모든 연속적 랜덤변수들 중에서 최대의 Entropy를 갖는 분포는 다음과 같은 확률밀도함수로 나타낼 수 있음을 증명하라.

[eqn: p_boldX`(x) ~=~ 1 over A e^{-x/A}``u`(x)]

또한 이 때의 Entropy는 H(x) Ａ ln A 로 주어짐을 보여라.

6.12	소스알파벳과 코드알파벳이 각각 다음과 같이 주어지고,

[eqn: S~=`` \{`s_1 ,` s_2 , `s_3 ,` s_4 , `s_5 , ` s_6 , `s_7 , ` s_8 , `s_9 \} ``, ~C ~=`` \{0,`1,`2 \}]

각 심볼의 발생확률이

[eqn: & p_1 `=`0.31, &p_2 `=`0.18, & p_3 `=`0.14, &p_4 `=`0.10, &p_5 `=`0.10 # & p_6 `=`0.09, &p_7 `=`0.04, &p_8 `=`0.02, &p_9 `=`0.02]

로 추정되었다.

(a) Radix-3 Huffman 코드를 작성하고, 그 평균 코드길이 [eqn: L_H(3)]를 구하라.

(b) Entropy [eqn: H_3 `(S)]를 구하고, 위 (a)의 결과와 비교하라.

6.13	소스알파벳, 코드알파벳 및 각 심볼의 발생확률이 다음과 같이 주어질 때 위 문제 6.12의 과정을 반복하라.

(a) [eqn: S_1 &=`` \{` s_1 ,` s_2 ,` s_3 ,`s_4 ,`s_5 ,s_6 \}``, ~ C_1 ~=`` \{`0,`1,`2 \} # &p_1 `=`1/3 ,~~p_2 `=`1/4 ,~~~p_3 `=`1/6 # &p_4 `=`1/9 ,~~p_5 `=`1/12 ,~~p_6 `=`1/18]

(b) [eqn: S_2 &=`` \{` s_1 ,` s_2 ,` s_3 ,`s_4 ,`s_5 ,` s_6 , `s_7 ,` s_8 \}``, ~ C_2 ~=`` \{`0,`1,`2,`3 \} # &p_1 `=` p_2 `=`1/5 ,~p_3 `=` p_4 `=`p_5 `=`1/10 # &p_6 `=` 0.25 ,~ p_7 `=` p_8 `=` 0.025]

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

(d) [eqn: S_4 &=`` \{` s_1 ,` s_2 ,` s_3 ,`s_4 ,`s_5 ,`s_6 ,` s_7 ,`s_8 ,`s_9 ,` s_10 \}``, ~C ~=`` \{` 0,`1,`2,`3,`4 \} # &p_1 `=`1/2 , ~~p_2 `=`1/4 , ~~~p_3 `=`1/8 , ~~~p_4 `=`1/16 , ~~p_5 `=`1/32 # &p_6 `=`1/64 , ~p_7 `=`1/128 , ~p_8 `=` 1/256 , ~p_9 `=`1/512 , ~p_10 `=`1/512]

6.14	세 가지 심볼 A, B, C 를 발생시키는 소스를 생각하자. 각 심볼은 하나의 신호 간격(signal interval)을 차지하며, 각각 0.7, 0.2, 0.1 의 확률로 발생된다.

(a) 이 소스의 출력으로부터 심볼 A 혹은 B 혹은 C를 얻었다고 할 때, 취득된 정보의 양은 각각 얼마인가?

(b) 이 소스의 출력에서 얻어지는 평균 정보의 양은 얼마인가?

(c) 만일 이 소스가 1,000(symbols/sec)의 속도로 심볼들을 발생시킨다고 하면, 정보율(information rate)은 얼마인가?  bits/sec, nats/sec, hartley/sec 을 단위로 각각 구하라.

(d) 이 소스가 가질 수 있는 최대 정보량(bits) 및 최대 정보율(bits/sec)은 각각 얼마인가?

6.15	이진코드를 사용하는 시스템의 소스알파벳과 각 심볼의 발생확률이 다음과 같이 주어지고,

[eqn: S &=` \{`A,`B,`C,`D,`E,`F, `G,`H ``\} # &p(A)`=`0.01, ~p(B)`=`0.03, ~p(C)`=`0.35, ~p(D)`=`0.02 # &p(E)`=`0.15, ~p(F)`=`0.18, ~p(G)`=`0.19, ~p(H)`=`0.07]

시스템의 출력에서 심볼들은 1 (msec) 마다 한 개씩 발생한다.

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

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

(c) Huffman 코드에 의한 출력의 발생율(symbol rate)은 얼마인가? (bits/sec)

(d) 평균 정보율은 얼마인가? (bits/sec)

(e) 이 시스템이 가질 수 있는 최대의 평균 정보량은 얼마이며(bits), 이는 어떠한 경우에 나타나는가?

6.16*	제2장의 표 2-3에 주어진 □Morse 코드표(일부)□를 알파벳으로 하여 동작하는 문자정보 시스템을 고려하자. 각 문자는 그것을 표현하고 있는 Morse 기호(dot or dash)의 개수에 반비례하는 발생확률을 가지며, 초당 2,000 개의 Morse 기호를 발생시킨다고 가정한다.

(a) 시스템이 발생시키는 평균 문자율(character rate)은 얼마인가? (chars/sec)

(b) 각 문자의 발생확률을 구하고, 그 평균 정보량을 계산하라.

(c) 가능한 최대 문자율을 구하고, 이를 위 (a)의 결과와 비교하라.