제 4 장

가변길이 코드

4-1  소스코딩(Source Coding)

이 장에서는 논의의 촛점을 소스코딩(source coding)에 맞추어 보기로 한다. 제2-1절에서 언급한 바와 같이 소스코딩은 정보원(source)으로부터 생성되는 심볼을 이진코드로 변환하는 과정으로서 평균 코드길이(average code-length)의 최소화를 지향한다. 따라서 소스코딩에 있어서의 효율성(efficiency)은 평균 코드길이가 짧을수록 효율적이라고 평가되는 것이다.

	정보이론

제 4 장 가변길이 코드

우리가 지금까지 취급하였던 코드들은 주로 메시지를 일정한 길이로 분할하여 동일한 갯수의 패리티를 부여함으로써 블록을 형성하는 고정길이 코드(fixed-length code or block code)였다. 패리티를 부여하지 않더라도 원래의 정보코드 자체가 일정한 길이를 갖는 코드체계를 주로 다루었다. 하나의 예외는 제2-4절의 말미에 소개하였던 Morse 코드로서, 이는 인코딩하고자 하는 심볼에 따라 코드의 길이가 변하는 가변길이 코드(variable-length code)의 일 예이다.

우리는 이 장을 통하여 가변길이 코드의 원리 및 설계방법에 관하여 상세히 설명하기로 한다. 가변길이 코드의 장점은 소스알파벳의 각 심볼들을 빈도수에 따라 서로 다른 길이로 인코딩함으로써 같은 양의 정보를 표현하는 데 필요한 이진수의 갯수가 고정길이 코드에 비하여 평균적으로 적어진다는 것이다. 이러한 가변길이 코드의 적절한 체계를 얻기 위해서는 무엇보다도 먼저 전송될 메시지 심볼의 통계적 구조를 알아야 한다. 만일 소스알파벳의 모든 심볼들이 거의 같은 빈도로 나타난다면 고정길이 코드를 사용하더라도 정밀하게 설계된 가변길이 코드의 효율성을 거의 성취할 수 있을 것이다. 그러나 만일 소스알파벳 내의 일부 심볼들이 다른 심볼들보다 높은 확률로 나타난다면, 빈번히 나타나는 심볼들은 짧은 코드로, 드물게 나타나는 심볼들은 긴 코드로 인코딩함으로써 시스템의 효율을 증가시킬 수 있는 것이다.

Morse 코드는 바로 이러한 관점이 적용된 가변길이 코드이다. 예를 들어서 영문자 □E□는 다른 문자보다 매우 빈번히 나타난다. 다시 말해서 영문자 □E□는 발생확률이 높은 심볼로서 Morse 코드는 이를 1-요소의 코드로 표현하고 있다. 반면에 영문자 □X□는 다른 심볼들에 비하여 발생확률이 낮으므로 이를 4-요소의 코드로 표현하고 있다. 이렇게 하면 모든 심볼을 동일한 길이의 코드로 표현하는 고정길이 코드에 비하여 평균코드 길이를 감소시킬 수 있다는 것이다.

그러나 가변길이 코드는 그 자체로서 다음과 같은 근본적인 문제점을 가지고 있다. 가변길이 코드에 의하여 인코딩된 메시지를 검파하기 위하여 수신측은 일정한 길이의 블록으로 구분하여 처리할 수는 없을 것이다. 따라서 수신측은 연속되는 이진열(binary stream) 내에서 한 심볼의 마지막 bit와 그 다음 심볼의 첫번째 bit를 구별할 수 있는 동기 알고리듬(word-sync. algorithm)을 가지고 있어야만 한다.

이러한 근본적인 문제점에도 불구하고, 처리하고자 하는 각 심볼들이 충분히 다른 빈도수(혹은 발생확률)를 갖는다면 가변길이 코드는 고정길이 코드에 비하여 매우 효율적인 코드체계를 도출할 수 있으므로 자료압축(data compression)을 위한 방법으로 널리 사용되고 있다.

이 장에서는 소스알파벳 내의 각 심볼들에 대한 독립적인 발생확률만을 이용하여 평균코드 길이를 최소화하는 코드체계를 다루고, 심볼 상호간의 상관관계(correlation)에 의한 더 복잡한 통계적 구조는 무시하기로 한다.

그러나 실질적인 정보를 취급하다 보면 심볼 상호간의 상관관계가 매우 밀접하여 이를 무시할 수 없는 경우가 많다. 예를 들어서 영어 문장 중 영문자 □Q□가 나오면 그 다음에는 대부분 □U□가 나타난다는 사실은 이들 두 심볼 사이에 매우 큰 상관관계가 존재함을 말해준다. 또한 흑백 영상정보를 취급함에 있어서 □0□ 혹은 □1□이 상당량 계속되다가 교환되는 양상을 자주 나타내게 되는데 이는 이웃한 심볼들 사이에 밀접한 상관관계가 있음을 말해주는 또 하나의 예이다. 이러한 경우 이들 상관관계를 소스코딩에 적용하면 더욱 효율적인 코드체계를 설계할 수 있음이 틀림없다. 우리는 제5장에서 이와 같은 심볼 간의 상관관계를 이용한 소스코딩을 다루게 될 것이다.

4-2  유일디코딩과 동시디코딩

일반적으로 소스코드가 필요로 하는 가장 기본적인 성질은 유일디코딩(unique decodability)이다. 다시 말해서 수신된 메시지는 유일하게 결정될 수 있어야 한다는 것이다. 고정길이 코드의 경우, 수신측은 메시지를 일정한 길이로 분할하여 단순히 각 블록을 해당되는 심볼에 대응시키면 됨으로 이 문제가 그리 심각하지 않다. 단지 표 3-4에 표시된 것처럼 각 블록(코드점)이 최소거리 1을 유지하기만 하면 메시지는 유일하게 결정된다고 할 수 있다. 그러나 가변길이 코드에 있어서는 이 문제가 그리 간단하게 해결되지 않는다.

예를 들어서 소스알파벳 [eqn: S``=`\{s_1 ,`s_2 ,`s_3 ,` s_4 \}], 코드알파벳 [eqn: C``=`\{`0,`1 \}]인 코드체계가 다음과 같이 인코딩되었다고 가정하여 보자.

[eqn: &s_1 ``=``0 ## &s_2 ``=``0``1 ## &s_3 ``=``1``1 ## &s_4 ``=``0``0]	(4-1)

이 코드체계에 의한 메시지는 전송 중 오류가 발생되지 않는다고 하더라도 수신측에서 유일하게 결정될 수 없다. 만일 수신된 메시지가 □0011010011□이었다고 가정하면, 이는 □[eqn: s_1 `s_1 `s_3 `s_2 `s_4 `s_3]□, □[eqn: s_4 `s_3 `s_2 `s_1 `s_1 `s_3]□, □[eqn: s_1 `s_1 `s_3 `s_2 `s_1 `s_1 `s_3]□ 등 여러가지로 결정될 수 있다. 따라서 이러한 코드체계는 유일디코딩 특성을 만족하지 않는다.

이러한 우리의 생각을 좀 더 명백하게 하기 위하여 다음의 정의를 이용하여 개념을 정립하기로 한다.

<정의 : 코드의 n-차 확장>

코드의 n-차 확장(n-th extension)은 원래의 소스알파벳으로부터 임의로 n 개의 심볼을 택하여 일렬로 나열한 상태를 말한다. 원래의 소스알파벳이 q 개의 심볼을 포함하고 있었다면, n-차 확장은 모두 qn 개의 심볼열을 포함하게 된다.

송신측에서 소스알파벳 내의 필요한 심볼들을 택하여 이들을 인코딩하여 전송하였다면, 수신측에서는 코드의 확장을 받게 되며 그로부터 송신측의 메시지를 유일하게 결정해 내어야 한다. 따라서 유일디코딩을 위해서는 소스심볼의 모든 확장이 서로 달라야 한다. 다시 말해서 인코딩된 소스심볼의 모든 나열(binary sequence)은 소스알파벳 내의 심볼열(symbol sequence)로써 유일하게 표현될 수 있어야만 그 체계의 유일디코딩이 가능하다는 것이다. 이것은 유일디코딩을 위한 필요충분조건이다.

<유일 디코딩을 위한 필요충분조건>

코드체계는 유일하게 디코딩된다.  □  임의의 확장이 서로 다르다.

그러나 소스알파벳에 여러 개의 심볼들이 존재하고 이들을 확장하여 전송 메시지가 형성된다면 이러한 조건의 진위여부(true or false)를 가려내는 것은 사실상 불가능하다.따라서 설계된 가변길이 코드의 유일디코딩 여부를 가려내는 기준으로 위에 제시한 필요충분조건이 사용되기는 매우 어렵다.

다음에 주어진 두 가지 코드체계를 고찰하여 보자.

<코드체계Ⅰ>	<코드체계Ⅱ>

[eqn: &s_1 ``=``0 ## &s_2 ``=``0``1 ## &s_3 ``=``0``1``1 ## &s_4 ``=``1``1``1]	[eqn: &s_1 ``=``0 ## &s_2 ``=``1``0 ## &s_3 ``=``1``1``0 ## &s_4 ``=``1``1``1]	(4-2)

임의의 몇 가지 이진열(binary sequence)에 대하여 이들 코드체계로 디코딩하여 보면 위에서 제시하였던 식(4-1)의 코드체계와는 달리 유일한 심볼열로 결정됨을 알 수 있다. 그러나 이들이 모든 이진열 즉 코드의 모든 확장에 대하여 유일한 심볼열로 결정될 것인지에 대해서는 확신할 수 없다. 또한 코드체계Ⅰ과 코드체계Ⅱ는 디코딩되는 과정이 서로 현저하게 다르다는 사실을 알 수 있을 것이다. 즉 코드체계Ⅱ는 수신된 이진열의 차례대로 심볼들이 결정되는 반면, 코드체계Ⅰ은 현재의 심볼을 결정하기 위하여 차후에 수신될 이진열들을 참조하지 않으면 안된다.

일반적으로 가변길이 코드에 의하여 인코딩된 메시지를 수신측에서 디코딩하는 방법으로 가장 편리하고 널리 사용되는 것은 코드체계에 대한 디코딩트리(decoding or decision tree)를 형성시켜 이를 이용한 알고리듬을 구현하는 방법일 것이다. 그림 4-1은 식(4-2)에 제시된 두 가지 코드체계의 디코딩트리를 그린 것이다. 이 그림에서 볼 수 있는 바와 같이, 코드체계Ⅱ는 정상적인 디코딩트리를 형성시키는 반면 코드체계Ⅰ은 그렇지 못하다. 다시 말해서 디코딩트리의 정상적인 구성은 하나의 초기상태(initial state)와 심볼 수 만큼의 결정상태(terminal state)를 갖는 이진트리(binary tree)로서 임의의 결정상태는 더 이상의 분기(branch)를 만들지 않아야 한다. 그러나 코드체계Ⅰ은 이러한 기본적 특성을 만족하는 디코딩트리를 형성시키지 못한다는 것이다.

그림 4-1  디코딩트리 (예)

(a) 코드체계 Ⅰ	(b) 코드체계 Ⅱ

이제 정상적인 디코딩트리 그림 4-1(b)를 이용하여 코드체계Ⅱ의 디코딩 과정을 살펴보기로 하자. 초기상태로부터 시작하여 최초의 bit가 수신되면 분기를 형성한다. 즉 최초의 bit가 □0□이면 결정상태 s1에 도달하게 되고, □1□이면 다음 유보상태(intermediate state)에 이르게 된다. 유보상태에서는 결정을 유보하고 다음 bit가 수신되며, 같은 방법으로 □0□이면 결정상태 s2에, □1□이면 그 다음 유보상태로 가게 된다. 이 유보상태에서도 마찬가지로 그 다음 bit를 수신하여 □0□이면 결정상태 s3로, □1□이면 결정상태 s4에 각각 도달하게 된다. 물론 각 결정상태에 도달하면 초기상태로부터 그 결정상태에 이르기까지 수신된 이진열을 대응되는 심볼로 결정하고 초기상태로 되돌아 간다.

이와 같이 정상적인 디코딩트리를 갖는 코드체계의 경우, 수신되는 이진열의 각 bit는 오직 한번씩 검사되고, 차후에 수신되는 bit를 참조할 필요없이 수신되는 차례대로 디코딩이 진행된다. 이러한 디코딩 과정을 동시디코딩(instantaneous decoding)이라 하며, 동시디코딩이 가능한 코드체계를 동시코드(instantaneous code)라 한다.

그러나 정상적인 디코딩트리를 갖지 못하는 코드체계Ⅰ의 경우에는 이러한 동시디코딩이 불가능하다. 다시 말해서 현재 수신된 bit에 대응하는 심볼을 결정하기 위해서는 차후에 수신될 bit들을 참조해야 하므로 모든 bit가 1 회 이상 검사되어야 한다는 것이다. 더욱이 소스알파벳 내에 많은 종류의 심볼들이 존재하는 경우에는 차후에 수신될 bit들을 참조하여 현재의 심볼을 결정하는 것도 매우 복잡한 알고리듬을 필요로 하게 된다. 그러나 이 코드체계도 유일디코딩 특성을 가지고 있음에 유의하여야 한다.

일반적으로 동시디코딩 특성을 갖는 코드체계는 유일하게 디코딩된다. 그러나 유일디코딩 특성을 가졌다고 하여 반드시 동시코드가 되는 것은 아니다. 코드체계Ⅰ은 유일디코딩 특성을 가지면서 비동시코드인 하나의 예이다.

유일디코딩이나 동시디코딩은 가변길이를 갖는 소스코드가 갖추어야 할 필수적인 성질이다. 만일 어떤 코드체계가 동시디코딩 특성을 갖지 않는다고 가정하면 소스알파벳 내의 심볼 수와 그 통계적인 구조에 따라 디코딩 알고리듬은 매우 복잡해지고, 경우에 따라서는 메시지 전체를 수신한 다음 이를 뒤로부터 차례로 결정해 나가는 것이 오히려 편리할 때도 있다. 이는 잠정적으로 무한한 기억장치를 요구하게 되어 실질적인 전송시스템의 특성으로는 수용할 수 없는 것이다.

동시코드는 기본적으로 유일디코딩 특성을 가지고 있을 뿐 아니라, 메시지를 디코딩하는 데 있어서 디코딩트리의 알고리듬에 따라 수신되는 이진열을 오직 한번씩 대응시키는 이외에 어떠한 과정도 필요로 하지 않으므로 전송시스템의 적용에 매우 유리하다. 따라서 이제부터는 이러한 동시코드에 대해서만 집중적으로 논의하기로 한다.

위에서 논의된 바와 같이, 어떤 코드체계가 정상적인 디코딩트리를 형성하면 동시코드가 된다는 사실을 알 수 있다. 이는 필요충분조건이다. 또한 디코딩트리가 존재하는 코드체계를 자세히 살펴보면, 체계 내의 어떤 코드도 다른 코드를 접두(Prefix : 한 코드의 앞 부분이 다른 코드의 전체로 표시됨)로 갖지 않는다는 사실을 알 수 있다.

디코딩트리의 구조로 볼 때, 정상적인 디코딩트리가 존재하기 위해서는 코드체계 내에 □Prefix□가 없어야 함은 명백하다. 왜냐하면 하나라도 Prifix가 존재하는 코드체계는 하나의 코드가 끝나는 점(결정상태)에서 다시 다른 코드의 뒷부분을 형성하기 위한 분기가 계속되어야 하므로 정상적인 디코딩트리를 형성할 수 없기 때문이다. 또한 그러한 구조를 디코딩트리로 인정한다 하더라도 □하나의 결정상태에 도달하면 해당되는 심볼을 결정하고 초기상태로 되돌아가는 알고리듬□도 근본적으로 수정되어야 할 것이다.

엄밀한 수학적 증명은 아니지만, 지금까지의 논의과정으로부터 하나의 코드체계가 동시코드이기 위한 필요충분조건은 명백하며 이를 다음과 같이 정리해 두기로 한다.

<동시코드의 조건>

코드체계는 동시코드이다.

□ 코드체계에 대한 디코딩트리가 존재한다.

□ 코드체계의 모든 코드는 다른 코드의 Prefix가 되지 않는다.

이제 주어진 소스알파벳에 대하여 적절한 동시코드를 구성하는 방법을 생각하여 보자. 일반적으로 고정길이 코드(블록코드)는 특별한 언급이 없는 한 동시코드이다. 제3-9절의 표 3-4에 나타낸 바와 같이 코드점 사이에 최소거리 1 이상을 유지하고 있는 블록코드는 그 길이가 일정하며 서로 1 bit 이상 다르므로 □Prefix□는 존재할 수 없다. 따라서 유일하게 디코딩되는 블록코드는 동시코드인 것이다. 소스알파벳의 각 심볼들이 서로 근사한 발생확률을 가지고 있다면 이를 위한 소스코드로서 블록코드가 사용되어도 무방할 것이다.

그러나 일반적인 소스알파벳은 그 내부의 심볼들이 서로 다른 발생확률을 나타내는 것이 보통이며, 이에 대하여 우리는 가변길이 코드에 의한 동시코드를 구성하여 평균 코드길이를 최소화하고자 한다. 앞에서도 언급하였지만 평균 코드길이를 최소화하는 것은 일정한 양의 정보를 표현함에 있어서 사용되는 코드심볼(code symbols)의 수를 평균적으로 감소시키는 효과를 주게 되어 궁극적으로 전송 혹은 저장시스템의 효율을 향상시킨다.

소스알파벳 S와 코드알파벳 C가 다음과 같이 주어졌다고 가정하자.

[eqn: & S ~=`` \{`s_1 ,` s_2 ,` s_3 ,`s_4 ,`s_5 `\} ## & C ~=`` \{`0 ,`1 `\}]	(4-3)

이에 대하여 가변길이 코드로 구성된 다음의 두 코드체계를 비교하여 보자.

<코드체계Ⅲ>	<코드체계Ⅳ>

[eqn: & s_1 ~=~ 0 ## & s_2 ~=~ 1``0 ## & s_3 ~=~ 1``1``0 ## & s_4 ~=~ 1``1``1``0 ## & s_5 ~=~ 1``1``1``1 ##]	[eqn: & s_1 ~=~ 0``0 ## & s_2 ~=~ 0``1 ## & s_3 ~=~ 1``0 ## & s_4 ~=~ 1``1``0 ## & s_5 ~=~ 1``1``1 ##]	(4-4)

코드체계Ⅲ은 첫번째 심볼을 1 bit로 코딩하고 심볼의 진행에 따라 1 bit 씩 증가시켰으며 마지막 두 개의 심볼은 동일한 길이로 설정하였다. 만일 이러한 코드체계를 q 개의 심볼을 갖는 소스알파벳에 적용한다면, 각 코드의 길이는

[eqn: 1, ``2, ``3, ``cdots, ``(q`-`1),`` (q`-`1)]

로 주어지게 될 것이다. 이러한 가변길이 코드를 Comma 코드라 부른다.

한편 코드체계Ⅳ는 처음 세 개의 심볼을 2 bits로, 나머지 두 개의 심볼을 3 bits로 각각 설정하였다.

이들 두 코드체계는 체계 내의 어떤 코드도 다른 코드를 Prefix로 갖지 아니하므로 동시코드임을 알 수 있다. 또한 그림 4-2와 같이 이들에 대한 디코딩트리가 존재하므로 이러한 사실이 확인된다.

식(4-3)에 주어진 소스알파벳에 대하여 작성할 수 있는 가변길이 동시코드는 이들 이외에도 무수히 많다. 다시 말해서 식(4-4)에 제시한 두 코드체계는 주어진 소스알파벳에 대한 코드체계 중 극히 일부에 지나지 않는다는 것이다. 그렇다면 □이들 중 가장 효율적인 코드체계는 어떤 것이며, 어떻게 그것을 설계할 것인가?□ 이것이 이 장에서 해결하고자 하는 문제의 핵심이다. 여기서 □효율적□이라는 말은 인코딩된 코드체계의 평균 코드길이(average code-length)가 짧다는 의미이다.

결국, 설계된 코드체계의 효율성은 각 심볼을 표현하고 있는 코드의 길이(bit 수)와 각 심볼의 발생확률에 의하여 주어진다. 식(4-4)에 제시된 두 코드체계 중 어느 것이 더 효율적이냐 하는 문제도 주어진 소스가 어떠한 확률분포를 갖느냐에 달려있다.

그림 4-2  디코딩트리 (예)

(a) 코드체계 Ⅲ	(b) 코드체계 Ⅳ

[예제 1]  다음과 같은 소스알파벳과 코드알파벳에 대하여

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

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

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

(1) [eqn: s_1 `=`0] 으로 시작되는 Comma 코드를 작성하고 그 디코딩트리를 그려라.

(2) [eqn: s_1 =00, `` s_2 =01, ``s_3 =10] 으로 하는 동시코드를 작성하고 그 디코딩트리를 그려라.

(3) 위 (1), (2)에서 작성된 두 가지 코드체계에 대한 평균 코드길이 [eqn: L_1 ,`` L_2] 를 각각 구하여 비교하라.

[풀이]

(1)

[eqn: s_1 &=~ 0 ## s_2 &=~ 1``0 ## s_3 &=~ 1``1``0 ## s_4 &=~ 1``1``1``0 ## s_5 &=~ 1``1``1``1``0 ## s_6 &=~ 1``1``1``1``1]                       ( 그림들어갈 자리 )

(2)

[eqn: s_1 &=~ 0``0 ## s_2 &=~ 0``1 ## s_3 &=~ 1``0 ## s_4 &=~ 1``1``0 ## s_5 &=~ 1``1``1``0 ## s_6 &=~ 1``1``1``1]                         ( 그림들어갈 자리 )

(3) 각 코드체계의 평균 코드길이는 식(2-3)을 이용하여 다음과 같이 구할 수 있다.

[eqn: L_1 ~=` sum_i=1^6 p_i ` l_i &=`` 1 over 2 □1 `+` 1 over 4 □ 2 `+` 1 over 8 □ 3 `+` 1 over 16 □ 4 `+` 1 over 32 □ 5 `+` 1 over 32 □ 5 # # &=`` 31 over 16]

[eqn: L_2 ~=` sum_i=1^6 p_i ` l_i &=`` 1 over 2 □2 `+` 1 over 4 □ 2 `+` 1 over 8 □ 2 `+` 1 over 16 □ 3 `+` 1 over 32 □ 4 `+` 1 over 32 □ 4 ## &=`` 35 over 16]

평균 코드길이의 관점에서, (1)에서 작성한 Comma 코드가 (2)에서 작성한 코드보다 더욱 효율적임을 알 수 있다. 이는 발생확률이 큰 심볼에 대하여 더 짧은 코드를 부여했다는 사실에 기인한다.

4-3  Kraft 부등식

Kraft는 코드의 길이에 따라 동시코드의 존재조건을 설명하는 부등식을 마련하였다. 즉, 소스알파벳의 각 심볼을 인코딩한 코드의 길이가 주어졌을 때, 그러한 길이를 갖는 동시코드의 존재 여부를 판단하는 다음과 같은 정리를 제시하였다.

<Kraft 정리>

소스알파벳 [eqn: S ``=`` \{s_1 ,`` s_2 , ``cdots,`` s_q \}]의 각 심볼을 인코딩한 코드의 길이가

[eqn: l_1 ``<=``l_2 ``<=`` cdots ``<=`` l_q ~, ~~~l_i ~:``s_i 의 ~코드길이]

와 같이 주어졌을 때, 이러한 길이를 갖는 동시코드가 존재할 필요충분조건은 다음과 같다.

[eqn: K ``Ａ`` sum_iＡ1^q 1 over r^{l_i} ```□```1]	(4-5)

여기서 r은 코드알파벳의 원소 수, 즉 Radix를 나타낸다.

이 정리는 동시코드를 구성하기 위한 각 코드의 길이 li (i Ａ 1, 2, □, q)가 모두 일률적으로 짧아질 수 없음을 말해준다. 다시 말해서 코드체계 내의 각 코드들은 적절하고 조화로운 길이로 작성되어 식(4-5)의 부등식을 만족하도록 정해져야 동시코드가 될 수 있음을 설명하고 있다.

앞에서 설명한 것처럼 어떤 코드체계에 대한 디코딩트리가 존재하면 그 코드체계는 동시코드이며, 동시코드에 대해서는 항상 디코딩트리가 존재한다. 이러한 디코딩트리의 성질을 이용하면 다음과 같이 Kraft 정리를 쉽게 증명할 수 있다.

<Kraft 정리의 증명> 증명의 과정은 코드체계 내에서 가장 긴 코드의 길이, 즉 코드의 최대길이(maximun code-length)에 대한 수학적 귀납법(mathematical induction)으로 이루어 진다.

.  수학적 귀납법은 정수(integer)에 관련된 정리를 증명하는데 주로 사용되는 증명방법으로 다음과 같은 두 단계에 의하여 완성된다.

1) 기본단계 (Basis step) : 정리의 초기관계식 P(1)이 성립함을 증명한다.

2) 귀납단계 (Induction step) : 관계식 P(n)이 성립함을 가정하여 관계식 P(n+1)이 성립함을 증명한다.

수학적 귀납법에 관한 상세한 내용을 공부하고자 하는 독자는 다음 서적을 참고하라.

B.Kolman and R.C.Busby, Discrete Mathematical Structures for Computer Science, 2nd. ed., pp.47-58, 1987, Prentice-Hall.

먼저 증명을 간단하게 하기 위하여 rＡ2인 경우, 즉 이진코드의 경우를 살펴보자.

[Basis Step] 코드의 최대길이가 1인 경우, 디코딩트리는 그림 4-3(a)와 같이 한 개 혹은 두 개의 분기(branch)를 갖게 된다. 한 개의 분기를 가질 때

[eqn: K ~=~ 1 over 2^1 ~=~ 1 over 2 ~<=~ 1]	(4-6)

와 같이 주어지고, 두 개의 분기를 가질 때

[eqn: K ~=~ 1 over 2^1 `+` 1 over 2^1 ~=~ 1 ~<=~ 1]	(4-7)

와 같이 주어지므로 식(4-5)의 부등식을 만족한다. 따라서 최대길이가 1인 경우 정리는 성립한다.

[Induction Step] 코드의 최대길이가 n 인 경우에 Kraft 부등식을 만족한다고 가정하자. 그리고 최대길이 n 인 두 코드체계에 대하여 각각 K'□1, K''□1 이라 두자. 그러면 코드의 최대길이가 (n+1) 인 코드체계 중에서 최대의 K 값을 갖는 디코딩트리는 그림 4-3(b)와 같이 그 초기상태를 선두로 최대길이 n 인 두 개의 부트리(subtree)를 갖는 형태가 될 것이다. 이 때, 부트리에 존재하는 모든 코드의 길이는 1 씩 증가하게 된다. 이것은 부트리의 K', K''에 각각 1/2을 곱한 것에 해당하므로 결국 전체 디코딩트리의 K 값은

[eqn: K~Ａ~ 1 OVER 2 K`' ``／``1 OVER 2 K`'' ~□~ 1]	(4-8)

그림 4-3  Kraft 부등식의 증명 (수학적 귀납법)

(a) Basis Step	(b) Induction Step

와 같이 계산되어 식(4-5)의 부등식을 만족한다. 따라서 정리는 최대길이가 (n+1) 인 코드체계에 대해서도 성립한다.

수학적 귀납법에 의하여, Kraft 정리는 모든 최대길이에 대하여 성립한다.	■

일반적인 Radix r로 확장해 보면, 디코딩트리는 각 유보상태로부터 최대 r 개의 분기를 가질 수 있으며, 위 증명 중에 나타나는 1/2 은 1/r로 대치되어 동일한 개념으로 설명될 수 있다. 최종 디코딩트리에 부착되는 부트리도 r 개로 확장되며 Kraft의 K 값은 다음과 같이 계산된다.

[eqn: K ~=~ 1 over r `K`'``+`` 1 over r `K`'' ``+``` cdots ```+``1 over r `K^(r) ~<=~1]	(4-9)

따라서 Kraft 정리는 모든 Radix에 대하여 성립함을 알 수 있다.	■

만일 어떤 코드체계가 디코딩트리의 모든 결정상태(terminal state)를 사용한다면 그 코드체계는 식(4-5)의 등식부분 KＡ1을 만족하며, 디코딩트리의 결정상태 중 일부를 사용하지 않는 코드체계는 부등식부분 K＠1을 만족한다.

어떤 이진코드(rＡ2)가 디코딩트리의 한 결정상태를 사용하지 않는다면, 디코딩 과정에서 그 결정상태에 선행하는 유보상태는 불필요하게 되며 그 분기점에 해당하는 bit는 아무런 손실없이 코드체계에서 제거될 수 있을 것이다. 따라서 식(4-5)의 부등식부분(K<1)을 만족하는 코드체계는 비효율적이라 할 수 있으며, 이러한 코드체계는 디코딩트리로부터 쉽게 수정될 수 있다. 그러므로 정상적인 이진코드 체계는 디코딩트리의 모든 결정상태를 사용하며 KＡ1을 만족한다.

Kraft 정리는 오직 코드의 길이에 대한 동시코드의 존재조건만을 취급하고 있다. 따라서 □주어진 코드길이를 갖는 동시코드가 존재할 것인가□를 결정할 뿐, □어떤 특별한 코드가 동시코드인가 아닌가□의 여부를 가려 주지는 못한다. 따라서 설계된 코드체계의 각 코드길이 li (i Ａ 1, 2, □, q)가 Kraft 부등식을 만족한다고 하더라도 그 코드체계를 동시코드라고 할 수는 없다. 단지 그러한 코드길이를 갖는 동시코드가 존재함을 확신할 뿐이다. 식(4-2)의 코드체계Ⅰ은 Kraft 부등식을 만족하지만 동시코드는 아니다.

다음의 두 가지 예에서 우리는 오직 각 코드의 길이만이 주어져 있다고 가정한다. 이것이 바로 Kraft 정리의 조건이며, 먼저 실질적인 코드체계를 예로 들지 않는 이유이다.

[예제 2] 코드알파벳이 [eqn: C `=` \{` 0, `1 \}]로 주어진 이진 코드체계에서 코드의 길이가 각각

[eqn: l_1 `=` 1, ~l_2 `=`3, ~l_3 `=` 3, ~l_4 `=`3]

으로 주어졌다면 이러한 길이를 갖는 동시코드는 존재하는가 ?

[풀이]

Kraft 정리로부터

[eqn: K ~=~ sum_i=1^4 `1 over {2^l_i } ~=~ 1 over 2 `+` 1 over 8 `+` 1 over 8 `+` 1 over 8 ~=~ 7 over 8 ~<=~ 1]

이므로 이러한 길이를 갖는 동시코드는 존재한다.

[예제 3] 위 예제 2의 코드길이 중 몇몇을 줄여

[eqn: l_1 `=` 1, ~l_2 `=`2, ~l_3 `=` 2, ~l_4 `=`3]

로 한다면, 이러한 길이를 갖는 동시코드는 존재하는가 ?

[풀이]

Kraft 정리로부터

[eqn: K ~=~ sum_i=1^4 `1 over {2^l_i } ~=~ 1 over 2 `+` 1 over 4 `+` 1 over 4 `+` 1 over 8 ~=~ 9 over 8 ~Ｂ~ 1]

와 같이 계산되므로 이러한 길이를 갖는 동시코드는 존재하지 않는다.

이제 이진코드 이외의 일반적인 Radix에 대한 개념을 이해하기 위하여 다음 예제에서는 r Ａ 3인 경우를 고려하여 보자.

[예제 4] 코드알파벳이 [eqn: C `=` \{` 0, `1,`2 \}]로 주어진 삼진 코드체계에서 코드의 길이가 각각

[eqn: l_1 = 1, `l_2 =2, `l_3 = 2, `l_4 =2, `l_5 = 2, `l_6 =2, `l_7 = 3, `l_8 =3, `l_9 = 3, `l_10 =3]

으로 주어졌다.

(a) 이러한 길이를 갖는 동시코드는 존재하는가 ?

(b) 마지막 코드 □l10 = 3□을 제거하면 그러한 길이의 동시코드는 존재하는가 ?

(c) 위 (a), (b)에서 동시코드가 존재하는 경우, 실제적으로 코드체계를 제시하고 그에 대한 디코딩트리를 그려라.

[풀이]

(a) Kraft 의 합은

[eqn: K ~=` sum_i=1^10 `1 over {3^l_i } `=`` 1 over 3 `+` 1 over 9 ×5 `+` 1 over 27 ×4 ~=~ 28 over 27 ~Ｂ~ 1]

와 같이 계산되므로 이러한 길이를 갖는 동시코드는 존재하지 않는다.

(b) Kraft 의 합은

[eqn: K ~=` sum_i=1^10 `1 over {3^l_i } `=`` 1 over 3 `+` 1 over 9 ×5 `+` 1 over 27 ×3 ~=~ 27 over 27 ~<=~ 1]

와 같이 계산되어 Kraft 정리를 만족하므로 이러한 길이를 갖는 동시코드는 존재한다.

(c) s1Ａ0으로부터 시작하여 각 코드의 길이를 맞추고 □Prefix□가 발생하지 않도록 체계적으로 진행하면 다음과 같은 코드체계를 얻을 수 있다. 또한 이 체계에 관한 디코딩트리는 코드체계의 우측에 제시하였다.

[eqn: &s_1 `=`0 ## &s_2 `=`1``0 ## &s_3 `=`1``1 ## &s_4 `=`1``2 ## &s_5 `=`2``0 ## &s_6 `=`2``1 ## &s_7 `=`2``2``0 ## &s_8 `=`2``2``1 ## &s_9 `=`2``2``2]                      (그림 들어갈 자리임)

위 예제에서 사용한 □0□, □1□, □2□ 등은 일반적인 숫자가 아니라 세 가지 서로다른 상태를 표시하는 코드심볼임을 명심해야 한다. 따라서 이들 세 가지 코드심볼은 서로 교환하더라도 궁극적으로 같은 코드체계를 형성하며 단지 디코딩트리 내의 분기(branch)들이 갈라지는 순서만을 변경하게 되는 것이다. 체계 내의 각 유보상태에서 분기의 순서 만을 변경하고 그 형태는 그대로 유지한다면 하나의 등가코드(equivalent code)를 얻게 된다.

앞에서 설명한 바와 같이, 설계된 하나의 코드체계가 식(4-5)로 주어진 Kraft 부등식을 만족한다고 하더라도 그것이 동시코드라고 확신할 수는 없다. 그러나 설계된 코드체계가 하나의 동시코드이면 반드시 Kraft 부등식을 만족한다.

[예제 5] 앞 절의 [예제 1]에서 구성하였던 두 가지 코드체계가 Kraft 부등식의 등식부분을 만족함을 보여라.

[풀이]

(1) [eqn: K ~=` sum_i=1^6 1 over {2^l_i } ``=~ 1 over 2 `+` 1 over 4 `+` 1 over 8 `+` 1 over 16 `+` 1 over 32 `+` 1 over 32 ~=~ 1]

(2) [eqn: K ~=` sum_i=1^6 1 over {2^l_i } ``=~ 1 over 4 `+` 1 over 4 `+` 1 over 4 `+` 1 over 8 `+` 1 over 16 `+` 1 over 16 ~=~ 1]

[예제 6] 소스알파벳과 코드알파벳이 각각

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

와 같이 주어지는 코드체계가 다음과 같이 작성되었다.

[eqn: s_1 = 1, ``s_2 = 2, ``s_3 =3, ``s_4 = 0`0, ``s_5 = 0`1, ``s_6 = 0`2, ``s_7 = 0`3`0, ``s_8 = 0`3`1]

(a) 디코딩트리를 그려서 이 체계가 동시코드임을 보여라.

(b) Kraft 부등식을 만족함을 보여라.

[풀이]

(a) 작성된 코드체계에 대한 디코딩트리는 다음과 같다.

따라서 작성된 코드체계는 동시코드이다.

(b) Kraft의 합은

[eqn: K ~=& sum_i=1^8 1 over {4^l_i } ~=~ 1 over 4 × 3 `+` 1 over 16 ×3 `+` 1 over 64 × 2 ~=~ 62 over 64 ~＠~ 1]

와 같이 계산되므로 Kraft 부등식을 만족한다. 이것이 등식부분을 만족하지 않는 것은 디코딩트리 내에 사용되지 않는 분기가 있음을 말해 준다.

4-4  축소형 블록코드

제4-2절에서 설명한 바와 같이, 일반적으로 최소길이 1 이상을 유지하고 있는 고정길이 코드(블록코드)는 코드체계 내에 □Prefix□가 존재하지 않으므로 동시코드이다. 이 절에서는 블록코드의 이와 같은 성질을 이용하여, 블록코드 체계 내의 일부 코드를 제거함으로써 가변길이 동시코드를 유도하는 방법을 설명하고자 한다.

블록코드에 있어서 정확히 2m 개의 소스심볼을 인코딩 한다면(Radix-r의 경우는 rm 개), 각각의 심볼은 m-bit (m-symbol)로 구성될 것이다. 그러나 소스알파벳이 정확히 Radix의 거듭제곱 만큼의 소스심볼을 가지고 있지 않은 경우에는 사용되지 않는 코드들이 존재하게 되고, 이들을 디코딩트리에서 살펴보면 불필요한 분기로 나타나게 된다. 코드체계의 평균 코드길이를 최소화하기 위해서는 불필요한 분기를 제거하여 일부 코드들을 축소시킴으로써 가변길이 동시코드로 변환할 수 있다.

예를 들어서 5 개의 심볼을 갖는 소스알파벳을 고려하여 보자. 이를 블록코드로 인코딩하기 위해서는 최소한 3-bit 코드를 사용해야 하며, 3-bit 블록코드의 디코딩트리는 다음 그림 4-4와 같이 구성된다.

그림 4-4  3-bit 블록코드의 디코딩트리

이들 8 개의 코드 중 우리가 필요로 하는 것은 5 개이므로 3 개는 제거되어야 한다. 만일 이들로부터 001, 011, 101 등 3 개의 코드를 제거한다고 하면, 디코딩트리에는 불필요한 분기가 발생하게 되고, 이들을 제거하여 해당되는 코드를 축소함으로써 그림 4-5와 같은 새로운 디코딩트리를 얻는다. 이는 우리가 구성하고자 하는 5 개의 심볼에 대한 가변길이 동시코드가 된다.

그림 4-5  축소형 블록코드 (예)

블록코드로부터 제거할 코드의 선택은 구성하고자 하는 코드체계의 소스알파벳이 가지고 있는 확률구조에 따라 달라질 수 있다. 만일 그림 4-4의 블록코드에서 제거할 코드를 001, 010, 011 등으로 선택한다면, 새로운 디코딩트리는 그림 4-6과 같이 달라지며 그 때의 코드체계도 새로운 가변길이 동시코드로 나타나게 된다.

이들 두 가지 코드체계는 모두 디코딩트리가 존재함으로 동시코드임이 명백하고, 각각의 디코딩트리에서 사용하지 않는 결정상태(terminal)가 없으므로 Kraft의 합은 KＡ1이 된다.

그림 4-6  축소형 블록코드 (예)

이와 같이 블록코드로부터 일부 코드를 제거하고 불필요한 분기를 축소함으로써 얻어지는 가변길이 동시코드를 축소형 블록코드(shortened block code)라 한다. 여기서 소스알파벳의 확률구조를 고려하여 형성된 동시코드를 각 심볼에 부여한다면 블록코드에 비하여 효율적인 체계를 얻을 수 있을 것이다. 그러나 축소형 블록코드는 코드체계의 구성 초기부터 소스알파벳의 확률구조를 고려하는 것이 아니므로 임의의 확률구조에 대한 최적의 동시코드를 설계하는 방법으로 사용하기에는 적당하지 않다.

4-5  최적 동시코드와 Huffman 코드

이 절에서는 실제적인 전송에 사용되는 심볼들의 발생확률(probability of occurrence)을 고려하여 최적의 동시코드를 구성하는 체계적이고 합리적인 방법을 마련하기로 한다. 이 장을 통하여 지금까지 구성된 코드체계들이 가변길이 동시코드인 것은 틀림없으나 평균 코드길이에 의한 효율성을 평가하기에는 적당하지 않은 것들이었다. 그 이유는 코드체계의 구성 초기부터 심볼들의 발생확률을 고려하여 각 코드의 길이를 결정한 것이 아니라 단순히 가변길이 동시코드를 만들어 각 심볼에 부여하였기 때문이다. 그러므로 이제부터는 소스알파벳의 각 심볼이 어떤 빈도수로 나타나는가를 먼저 평가하여 발생확률을 추정하고, 이를 기준으로 각 심볼에 부여할 코드의 길이와 실제적인 코드체계를 유도하는 체계적인 방법에 대하여 공부하기로 한다.

우리는 가장 빈번히 발생하는 심볼을 가장 짧은 코드로, 드물게 발생하는 코드를 긴 코드로 인코딩함으로써 평균 코드길이를 최소화하고자 한다. 소스알파벳

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

에 대하여 추정된 각 심볼의 발생확률이

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

와 같이 주어지고, 이들을 인코딩한 각 코드의 길이가

[eqn: l_i ~:~ \심볼~ s_i ~에 ~대한 ~코드의~ 길이 ~( \# ~of~ bits), ~i `=`1,`2,`cdots,`q]	(4-12)

와 같다면, 그 코드체계의 평균 코드길이는 식(2-3)에 나타낸 바와 같이

[eqn: L_av ~Ａ``` sum from iＡ1 to q ``p_i``l_i]	(4-13)

가 된다.

소스알파벳 내의 각 심볼들의 나열순서는 바뀌어도 무방하므로, 그들의 발생확률 pi (i Ａ 1, 2, □, q)를 다음과 같이 내림차순(decreasing order)으로 정리하여도 일반성은 상실되지 않는다.

[eqn: p_1``□`` p_2 ``□``□``□``p_q]	(4-14)

이 때, 만일 구성된 코드체계가 평균 코드길이의 관점에서 최적 동시코드(optimal instantaneous code)라면, 각 코드의 길이 li (i Ａ 1, 2, □, q)는 반드시 다음과 같이 발생확률의 역순으로 배열되어야 한다.

[eqn: l_1 ``□`` l_2 ``□``□``□``l_q]	(4-15)

다시 말해서 어떤 코드체계가 식(4-14)와 식(4-15)를 동시에 만족하지 않는다면, 평균 코드길이가 가장 짧은 코드라고 할 수는 없다는 것이다.

이러한 사실을 입증하기 위하여 m＠n 이라 두고 m과 n에 대하여 다음의 두 가지 조건이 성립한다고 가정하자. 이는 식(4-14)와 식(4-15)를 동시에 만족하지 않는 상태를 가정한 것이다.

[eqn: p_m``□`` p_n , ~~~l_m``□``l_n]	(4-16)

코드체계의 평균 코드길이는

[eqn: L_1 ``Ａ`` cdots ``+ ``p_m``l_m ``／`` p_n ``l_n ``+`` cdots]	(4-17)

이 된다. 이제 두 개의 심볼 sm과 sn에 대한 코드를 서로 교환하여 새로운 코드체계를 구성하고 평균 코드길이를 구하면

[eqn: L_2 ``Ａ``cdots ``+`` p_m``l_n ``／`` p_n ``l_m ``+`` cdots]	(4-18)

과 같이 나타난다. 새로운 코드의 평균 코드길이 L2로부터 원래의 평균 코드길이 L1을 빼면

[eqn: L_2``-`` L_1 ``Ａ`` (p_m``-`` p_n `)` (l_n ``-`` l_m`)]	(4-19)

이 된다. 최초의 가정인 식(4-16)으로부터 L2 - L1의 값은 음수이며, 이는 구성된 코드체계 보다 더 효율적인 코드체계가 존재함을 뜻한다. 또한 이러한 결과는 심볼 sm과 sn의 코드를 서로 교환함으로써 평균 코드길이를 감소시킬 수 있음을 보여주며, 원래의 코드체계가 식(4-14)와 식(4-15)를 동시에 만족하지 않기 때문에 최적의 코드체계가 되지 못한 것이다.

그러므로 평균 코드길이의 관점에서 가장 효율적인 코드체계는 반드시 식(4-14)와 식(4-15)를 동시에 만족하여야 한다. 결국 두 연속부등식(running inequalities)은 효율적인 코드체계가 갖추어야 하는 필수적인 특성이므로 앞으로 우리는 이 두 부등식을 동시에 만족하는 코드체계를 주로 취급하기로 한다.

이제부터, 이 절의 주된 관심사인 Huffman 코드에 대하여 논의하기로 하자. 무엇보다도 먼저 우리가 증명해 두어야 할 사실은 최적 동시코드에 있어서 발생확률이 가장 낮은 두 개의 심볼에 대한 코드는 동일한 길이를 가져야 한다는 것이다. 어떤 코드체계의 최대 코드길이(maximum code length)를 Lm이라 하고, 코드길이가 Lm인 심볼이 코드체계 내에 오직 하나만 존재한다고 가정하여 보자. 논의되고 있는 모든 코드는 동시코드이므로 최대길이코드 이외의 Lm１1 혹은 그 이하의 길이를 갖는 어떤 코드도 이 최대길이코드의 □Prefix□가 되지 않는다. 그러므로 최대길이코드의 마지막 부분은 디코딩에 있어서 아무런 정보손실 없이 제거할 수 있다. 따라서 최적 동시코드 체계 내에는 최대길이를 갖는 코드가 언제나 두 개 존재하며, 위의 연속부등식 식(4-14), (4-15)로부터 이들 두 심볼은 소스알파벳 내에서 가장 낮은 빈도수를 갖는 것들이 될 것이다.

Huffman 코드를 구성하는 알고리듬은 크게 두 개의 과정으로 구분된다. 그 첫번째 과정은 축소과정(reduction process)이고, 두번째 과정은 확장과정(splitting and expansion process)이다.

축소과정에서는 주어진 소스알파벳의 심볼이 오직 Radix 만큼(r 개) 남을 때까지 각 단계마다 (r - 1) 개씩 줄여 나간다. 가장 흔히 사용되는 이진코드(binary code : r = 2)에 대한 축소과정을 설명하면 다음과 같다.

1. 발생확률이 가장 낮은 두 개의 심볼을 결합하여 그 합의 확률을 가진 하나의 심볼을 만들어 소스심볼의 갯수를 한 개 축소시킨다.

[eqn: p_\new ~=~p_q ``+```p_q-1]	(4-20)

2. 새로이 형성된 심볼의 확률을 나머지 확률들과 비교하여 해당되는 위치로 천이시킨다.

[eqn: p_m ``<=``p_\new ``<=``p_n]	(4-21)

3. 위 1, 2의 과정을 오직 두 개의 심볼만이 남을 때까지 반복한다.

확장과정에서는 위의 축소과정과 반대로 남아있는 r 개의 심볼로부터 각 단계마다 심볼의 갯수를 (r - 1) 개씩 늘려 나가는 것이다. 이진코드(r = 2)에 대한 확장과정을 설명하면 다음과 같다.

1. 축소과정의 결과로 남아있는 두 개의 심볼에 각각 □0□과 □1□을 할당한다. (splitting)

2. 두 개의 심볼 중 축소과정의 전 단계에서 결합되었던 하나의 심볼에 대하여 다시 두 개로 확장하면서 각각 □0□과 □1□을 덧붙인다. (expansion)

3. 위 2의 과정을 원래 소스심볼의 갯수 q가 될 때까지 반복한다.

결국 Huffman 코딩은 두 개의 순환적(recursive) 과정으로 구성됨을 알 수 있으며, 이들은 구조적 프로그램(structured program)에 의하여 용이하게 구현될 수 있을 것이다. 먼저 Huffman 코딩과정을 좀 더 구체적으로 이해하기 위하여 간단한 소스알파벳을 인코딩하는 예를 들어보자.

[예제 7] 소스알파벳과 코드알파벳이 각각 다음과 같이 주어진다.

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

추정된 각 심볼의 발생확률이 다음과 같을 때

[eqn: p_1 `=` 0.4, ~p_2 `=` 0.2, ~p_3 `=`0.2, ~p_4 `=` 0.1, ``p_5 `=` 0.1]

(a) 축소과정의 각 단계에서 결합된 확률을 가능한 최상위에 위치시키는 방법으로 Huffman 코드를 구성하고 그 디코딩트리를 그려라.

(b) 축소과정의 각 단계에서 결합된 확률을 가능한 최하위에 위치시키는 방법으로 Huffman 코드를 구성하고 그 디코딩트리를 그려라.

(c) 위 (a), (b) 에서 구성된 코드체계에 대한 Kraft의 합을 구하여 식(4-5)를 만족함을 보여라.

[풀이]	(a)

(그림 들어갈 자리임)

(b)

(그림 들어갈 자리임)

(c) [eqn: &K_1 ~=`` sum_i=1^5 1 over {2^l_i } ~=`` 1 over 4 ×`3 `+` 1 over 8 ×`2 ~=~ 1 ## &K_2 ~=`` sum_i=1^5 1 over {2^l_i } ~=`` 1 over 2 `+` 1 over 4 `+` 1 over 8 `+`1 over 16 ×`2 ~=~ 1]

따라서 구성된 두 코드체계는 모두 식(4-5)를 만족하며 불필요한 분기는 없다.

위 예제 (a), (b)의 인코딩 과정 중, 좌로부터 우로 오직 두 개의 심볼이 남을 때까지 확률을 더해 나간 과정은 축소과정이며, 남아있는 두 개의 심볼에 각각 □0□과 □1□을 부여하고 이어서 우로부터 좌로 원래의 심볼들이 모두 형성될 때까지 □0□과 □1□을 덧붙여 나간 과정은 확장과정이다. 이러한 과정의 결과로 구성된 두 코드체계는 위에 도시된 바와 같이 디코딩트리가 존재하므로 동시코드이다. 또한 Kraft 의 합을 계산하면 모두 1이 됨으로 디코딩트리 내에 사용되지 않는 분기는 없다.

주지하는 바와 같이, Huffman 코드의 인코딩 과정은 동일한 확률구조를 갖는 소스알파벳에 대해서도 항상 유일한 코드체계로 귀결되지는 않는다. 첫째로 확장과정에서 두 개의 심볼에 할당하는 □0□과 □1□의 순서를 교환한다면, 원래의 코드에 모두 보수(complement)를 취한 또 다른 코드체계를 얻을 수 있을 것이다. 이 때, 두 코드체계의 차이는 하찮은 것이라 할 것이다. 둘째로 [예제 7]의 (a), (b)에서 보는 바와 같이, 축소과정의 각 단계에서 결합에 의하여 생성된 심볼의 확률이 다른 심볼들의 발생확률과 동일한 경우, 이를 어디에 위치시키느냐에 따라 완전히 다른 코드체계가 형성됨을 알 수 있다. 이들의 차이점은 무엇이며 서로 어떤 관계를 유지하고 있는가 ?

먼저 이들의 효율성을 비교해 보기 위하여 각 코드체계의 평균 코드길이를 구하면 다음과 같다.

[eqn: L_1 &=``sum_i=1^5 p_i `l_i ## &=`` 0.4 `(2) ``／`` 0.2 `(2) ``／``0.2 `(2) ``／``0.1`(3) ``／``0.1 `(3) ``=`` 2.2]	(4-22)

[eqn: L_2 &=``sum_i=1^5 p_i `l_i ## &=`` 0.4 `(1) ``／`` 0.2 `(2) ``／``0.2 `(3) ``／``0.1`(4) ``／``0.1 `(4) ``=`` 2.2]	(4-23)

평균 코드길이의 관점에서 두 코드체계의 효율성은 서로 같으며, 일반적으로 축소과정의 각 단계에서 결합된 확률을 가능한 임의 위치에 두더라도 이러한 관계는 그대로 성립된다.

이제, 우리는 동일한 효율성을 갖는 여러가지 코드체계 중에서 용도에 따라 가장 적합한 체계를 선택하여야 한다. 매우 합리적인 선택 중의 하나는 체계의 평균 코드길이에 대하여 각 심볼의 코드길이가 최소로 변하는 것, 즉 체계의 분산(variance)이 최소인 코드체계를 택하는 것이다.

[예제 7]의 두 가지 코드체계에 대하여 분산을 구해 보자. 여기서 분산이라 함은 코드체계 내에 존재하는 각 코드의 길이가 평균 코드길이를 중심으로 어느 정도 변화하는가의 척도를 말하며, 우리가 제1장에서 정의한 식(1-107) 및 식(1-108)을 이용하여 다음과 같이 계산된다.

[eqn: Var_1 (bold l `)``=& E \{(bold l `-`L_1 )^2 \} ``=`sum_i=1^5 (l_i `-` L_1 )^2 ``p_i## =& (2-2.2)^2 (0.4) `+`(2-2.2)^2 (0.2)(2)`+`(3-2.2)^2 (0.1)(2) ## =&0.16]

(4-24)

[eqn: Var_2 (bold l `)``=& E \{(bold l `-`L_2 )^2 \} ``=`sum_i=1^5 (l_i `-` L_2 )^2 ``p_i## =& (1-2.2)^2 (0.4) `+`(2-2.2)^2 (0.2)`+`(3-2.2)^2 (0.2) ## & +`(4-2.2)^2 (0.1)(2) ## =&1.36]

(4-25)

결국, 첫 번째 코드체계는 두 번째 코드체계에 비하여 각 심볼의 코드길이가 평균 코드길이를 중심으로 훨씬 작은 변화를 나타내고 있음을 알 수 있다. 가변길이 코드에 있어서 각 코드의 길이가 크게 변화하지 않는다는 사실은 수신측의 동기(synchronization) 획득에 매우 유리하다.

일반적으로 Huffman 코딩 축소과정의 각 단계에서 결합에 의하여 생성된 확률을 가능한 최상위에 두도록 하면 최소분산 Huffman 코드(minimum variance Huffman code)를 얻게 된다. 따라서 [예제 7]에 제시된 소스알파벳에 대하여 식(4-24)는 최소분산을, 식(4-25)는 최대분산을 표시한다.

[예제 8] 소스알파벳과 코드알파벳이 각각

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

이고, 각 심볼의 발생확률이

[eqn: &p_1 = 0.05, &p_2 = 0.15, &p_3 = 0.2, &p_4 =0.05 # &p_5 = 0.15, &p_6 =0.3, &p_7 = 0.1]

와 같이 주어질 때, 최소분산 Huffman 코드를 작성하고, 그 평균 코드길이 [eqn: L] 및 분산 [eqn: Var]을 구하라.

[풀이]

먼저 소스알파벳의 심볼들을 발생확률이 큰 것부터 내림차순으로 나열하고, 최소분산 코드가 되도록 축소과정과 확장과정을 진행하면 다음과 같다.

[eqn: s_1 &=`` 1``0``0``0 ## s_2 &=`` 0``0``0 ## s_3 &=`` 1``1 ## s_4 &=`` 1``0``0``1 ## s_5 &=`` 0``0``1 ## s_6 &=`` 0``1 ## s_7 &=`` 1``0``1]

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

[eqn: L ~=` sum_i=1^7 p_i`` l_i &=~ 0.05 cdot 4 ``+`` 0.15 cdot 3 ``+`` 0.2 cdot 2 ``+`` 0.05 cdot 4 # &~~~+`` 0.15 cdot 3 ``+`` 0.3 cdot 2 ``+`` 0.1 cdot 3 ## &=~ 2.6 ~(bits)]

[eqn: Var &=` sum_i=1^7 `p_i `` (l_i `-`L)^2 ## &=~ 0.05 (4-2.6)^2 ``+`` 0.15 (3-2.6)^2 ``+`` 0.2 (2-2.6)^2 ``+`` 0.05 (4-2.6)^2 # &~~~+`` 0.15 (3-2.6)^2 ``+`` 0.3 (2-2.6)^2 ``+`` 0.1 (3-2.6)^2 ## &=~ 0.44]

앞에서 언급한 바와 같이 최적 동시코드는 발생확률이 가장 작은 두 개의 심볼에 대하여 언제나 동일한 길이의 코드를 할당하여야 한다. 또한 Huffman 코딩의 축소과정과 확장과정의 결과로 얻어지는 이진코드는 마지막 두 개의 심볼에 대하여 항상 동일한 길이의 코드를 부여한다. 이러한 사실은 Huffman 이진코드가 주어진 소스알파벳의 확률구조에 대하여 가능한 최적의 동시코드임을 암시하고 있다.

엄밀한 수학적 증명은 아니지만, Huffman 이진코드가 평균 코드길이의 관점에서 가능한 최적의 코드임을 다음과 같이 설명할 수 있다.

주어진 소스알파벳의 확률구조에 대하여 Huffman 코드의 평균길이를 L(bits)라 하고, 이보다 더 짧은 평균 코드길이 L1을 갖는 동시코드가 존재한다고 가정하여 보자. 즉,

[eqn: L_1 ~＠~ L]	(4-26)

라 하면, 이진수로 인코딩된 최적 동시코드는 디코딩트리의 모든 결정상태(terminals)를 코드가 점유하게 되므로 디코딩트리 내에 무효분기(dead branch)를 포함하지 않는다. 여기서 무효분기라 함은 단 하나의 가지(edge)를 갖는 분기점(유보상태)을 말하며, 디코딩트리로부터 이를 제거함으로써 그것을 지나는 모든 결정상태에 대한 코드길이를 축소할 수 있다. 따라서 최적 동시코드는 무효분기가 없는 디코딩트리를 갖게 된다.

만일 디코딩트리 내에 최대길이를 갖는 코드가 오직 두 개만 존재한다면(Huffman 코드의 경우), 그들은 반드시 마지막 유보상태를 공유하며 최소 발생확률을 갖는 두 개의 심볼을 표시하고 있을 것이다. 그러므로 평균 코드길이 L인 Huffman 코드에 있어서 이들 두 심볼이 평균 코드길이에 미치는 영향은

[eqn: l_q `(p_q ``／``p_q-1`)]	(4-27)

이며, Huffamn 코드보다 더 짧은 평균 코드길이 L1을 갖는 코드체계를 구성하기 위하여 최대길이의 코드를 1 bit 축소하였다고 가정하면

[eqn: (l_q ``-``1`) `(p_q ``／``p_q-1`)]	(4-28)

와 같이 계산되어야 할 것이다.

따라서 새로운 코드체계는 Huffman 코드에 비하여 적어도

[eqn: p_q ``／``p_q-1`]	(4-29)

만큼 짧은 평균 코드길이를 가져야 한다.

만일 최대길이를 갖는 코드가 세 개 이상 존재한다고 가정하면(Huffman 코드가 아닌 경우), 같은 코드길이를 갖는 심볼들은 평균 코드길이에 변화를 주지 않고 서로 교환할 수 있으므로, 이들 중 최소의 발생확률을 갖는 두 심볼이 마지막 유보상태를 공유하도록 옮겨 놓을 수 있다. 이 때, Huffman 코드보다 더 짧은 평균 코드길이를 갖는 코드체계를 형성하기 위하여 최대길이의 코드를 짧게 한다면, 이것이 평균 코드길이에 미치는 영향은 식(4-28)과 동일하고, 두 체계의 차이도 식(4-29)와 같게 나타날 것이다.

이러한 과정을 각각 두 개의 심볼만 남을 때까지 계속 적용하면, 결국 Huffman 코드의 평균 코드길이는 1이 되며, 식(4-26)은 계속 유지될 것이므로 새로운 코드체계의 평균 코드길이는 1 보다 작게 된다. 1 보다 작은 코드길이는 존재할 수 없으므로, 이는 명백히 모순이다. 따라서 식(4-26)은 성립할 수 없으며, Huffman 코드는 이진 코드체계에 있어서 가능한 최소길이의 코드이다.

4-6  Huffman 코드의 응용

이 절에서는 앞 절에서 소개한 Huffman 코드의 몇 가지 특수한 경우에 대하여 살펴보고, 문자정보의 시뮬레이션에 실질적으로 응용되고 있는 Zipf 분포(Zipf distribution)에 대한 Huffman 코드를 유도한다. 또한 제4-2절에서 정의하였던 n-차 확장(n-th extension)에 대한 Huffman 코드길이를 비교하고, 코드알파벳을 확장하여 일반적인 Radix에 대한 Huffman 코드를 취급함으로써 뒤에서 Entropy를 비롯한 정보이론의 제반 개념을 설명하는 기반으로 삼고자 한다.

Huffman 코드는 소스알파벳의 구성과 각 심볼의 발생확률 분포에 따라 달라진다. 따라서 소스알파벳을 적절히 정의함으로써 몇 가지 흥미있는 Huffman 코드를 도출시킬 수 있다.

첫째로, 소스알파벳의 모든 심볼들이 동일한 발생확률을 가지며, 소스알파벳 내의 심볼 수가 정확히 q Ａ 2m 개이면, Huffman의 결과는 모든 심볼들이 동일한 코드길이 를 갖게 될 것이므로 m-bit 블록코드가 된다. 이 때, 만일 소스심볼의 수가 정확히 2m 로 주어지지 않으면 제4-4절에서 설명한 축소형 블록코드가 될 것이다.

둘째로, 최소의 발생확률을 가진 두 심볼의 결합이 최대의 발생확률을 언제나 초과하는 경우에는, 축소과정의 각 단계에서

[eqn: p_q ``+`` p_q-1 ``Ｂ`` p_1 `, ~~for~\all~\reductio\n~ \steps]	(4-30)

와 같은 부등식이 항상 성립하게 됨으로 그림 4-7과 같이 결합에 의하여 생성된 심볼은 언제나 최상위로 천이하게 된다. 이 때, 소스알파벳의 심볼 수가 q Ａ 2m이면, 축소과정에 의하여 각 심볼들은 같은 횟수 만큼 결합하게 되고, 확장과정에서 다시 같은 횟수 만큼 덧붙임을 받게 됨으로 결국 m-bit 블록코드를 얻게 된다. 만일 소스심볼의 수가 2m에 미치지 못하는 경우에는 앞에서와 같이 축소형 블록코드를 형성한다.

모든 심볼들이 동일한 발생확률을 갖는 위의 경우에도 최소분산 Huffman 코드를 적용한다면 그림 4-7과 같은 축소과정이 진행될 것이므로, 첫번째 경우는 두번째 경우의 특수한 예라고 볼 수 있다.

그림 4-7  (축소형) 블록코드가 되는 경우

위의 두 가지 경우는 심볼들의 발생확률이 크게 다르지 않은 소스알파벳에 대하여 예시하고 있다. 따라서 Huffman 코딩의 결과도 고정길이 코드(블록코드) 혹은 그와 유사한 코드체계를 형성하였다.

가변길이 코드의 진가는 소스알파벳의 심볼들이 서로 상당히 다른 발생확률을 가질 때 비로소 나타나게 된다. 그러므로 Huffman 코딩의 결과가 효율적인 가변길이 코드를 구성하기 위해서는 현저히 다른 발생확률을 가진 소스알파벳에 적용되어야 한다.

각 심볼들의 발생확률이 다음과 같은 조건을 만족한다고 가정하여 보자.

[eqn: p_j ~□~ 2 over 3 sum from kＡj／1 to q p_k ~, ~~for ~\all ~j]	(4-31)

이 식은 각 심볼의 발생확률이 그 하위의 모든 발생확률을 합한 것의 2/3 보다 작지 않음을 나타내고 있다.

예컨대, 최하위의 두 확률을 합한 값 [eqn: p_q `+`` p_q-1] 은 그 바로 위의 확률 [eqn: p_q-2] 보다는 클 수도 있으나 [eqn: p_q-3] 보다 클 수는 없다. 따라서 결합된 확률은 한 단계 위로 올라가거나 혹은 현 위치에 그대로 머물게 된다. 이에 따라 다음 단계에서 결합되는 확률은 [eqn: p_q ``／``p_q-1 ``／`` p_q-2] 가 된다.

결국 Huffman 코딩의 축소과정은 그림 4-8에 도시된 것과 같이 매 단계마다 최하위의 두 심볼만이 교환되거나 혹은 전혀 교환되지 않고 제자리를 지키게 된다. 그러므로 확장과정에서는 최상위의 심볼(1-bit)로부터 시작하여 차례로 1 bit 씩 추가되는 코드를 형성하며, 최하위의 두 심볼은 동일한 길이로 인코딩된다. 따라서 이와 같이 형성된 코드체계는 제4-2절에서 언급하였던 Comma 코드가 됨을 알 수 있다.

예를 들어서, 어떤 소스알파벳이 다음과 같은 확률분포를 갖는다고 가정하면,

[eqn: p_1 ``Ａ`` 1`/` 2],  [eqn: p_q ``Ａ`` 1 `/` 2^q-1]

[eqn: p_k ``Ａ`` 1 `/`2^k ~(1``＠``k``＠``q`)]	(4-32)

이는 식(4-31)을 만족하므로, 그 Huffman 코딩의 결과는 Comma 코드가 된다.

그림 4-8  Comma 코드가 되는 두 가지 경우

[예제 9] 소스알파벳과 코드알파벳이 각각

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

이고, 각 심볼의 발생확률이 식(4-32)를 만족한다.  최소분산 Huffman 코드를 작성하고 그 디코딩트리를 그려라.

[풀이]

먼저 식(4-32)를 이용하여 각 심볼들의 발생확률을 구하면

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

따라서 Huffman 과정의 진행과 구성된 코드체계 디코딩트리는 다음과 같다. 이는 하나의 Comma 코드이다.

(그림 들어갈 자리임)

Zipf 분포는 인간이 사용하는 언어(영어, 한국어 등)에 의하여 표현된 문자정보의 확률분포를 근사화하므로 각종 시뮬레이션(simulation)의 도구로 흔히 쓰인다. 이 확률분포에 있어서 k 번째 심볼의 발생확률은 1/k에 비례한다(k Ａ 1, 2, □, N). 즉, 문자정보의 소스알파벳에 대한 각 심볼의 확률분포는 다음과 같이 근사화된다.

[eqn: & p_k ~=~ 1/k over S_N ``, ~k `=` 1,`2,`3, `cdots, `N ## &~~~\where ~S_N ``=``sum_k=1^N ` 1 over k]	(4-33)

여기서 N은 소스알파벳 내에 존재하는 심볼의 갯수이다. 이 분포가 하나의 확률분포로서 모순없이 사용되기 위해서는 식(1-37)을 만족하여야 한다. 랜덤변수 X를 발생된 심볼이라고 가정하고 식(4-33)의 확률을 대입하면

[eqn: sum_k=1^N `P_boldX ` (x_k ) ~=` sum_k=1^N `p_k ~=` sum_k=1^N `1/k over S_N ~=~1]	(4-34)

와 같이 계산되므로 Zipf 분포는 확률분포로서의 자격을 갖추었다.

Zipf 분포는 실질적인 소스코딩의 문제에 대하여 Huffman 코드와 블록코드의 효율성을 비교하기 위한 좋은 본보기이다. 우선 전체적인 개념을 파악하기 위하여 간단한 예를 들어 보기로 하자.

[예제 10] 소스알파벳의 심볼 수가 N=4로 주어지고, 그 발생확률이 식(4-33)의 Zipf 분포를 따른다고 가정할 때

(a) 블록코드와 최소분산 Huffman 코드로 각각 인코딩하라.

(b) 위 (a)에서 작성된 두 코드체계의 평균 코드길이를 계산하라.

(c) Huffman 코드의 블록코드에 대한 이득(gain)을 구하라.

[풀이]

(a) 주어진 소스알파벳에 대한 블록코드는 명백히 다음과 같이 구성된다.

[eqn: s_1 `=` 0`0, ~s_2 `=` 0`1, ~s_3 `=` 1`0, ~s_4 `=` 1`1]

최소분산 Huffman 코드를 작성하기 위해서는 먼저 각 심볼의 발생확률을 구해야 한다. 식(4-33)에서

[eqn: S_4 ~=~ 1 ``+`` 1 over 2 ``+`` 1 over 3 ``+`` 1 over 4 ~=~ 25 over 12]

이므로 확률들은

[eqn: p_1 `=`12 over 25 ,~ p_2 `=`6 over 25 ,~ p_3 `=`4 over 25 ,~ p_4 `=`3 over 25]

와 같이 계산된다. 따라서 최소분산 Huffman 코드는 다음과 같이 구성된다.

[eqn: &s_1 ``=`` 1 ## &s_2 ``=`` 0``1 ## &s_1 ``=`` 0``0``0 ## &s_1 ``=`` 0``0``1]

(b) 두 코드체계의 평균 코드길이는 각각 다음과 같이 계산된다.

[eqn: & L_B ~=~ 2 ``(bits) # & L_H ~=`` sum_k=1^4 `p_k ``l_k ~=~1.8 ``(bits)]

(c) 따라서 Huffman 코드의 이득은 다음과 같다.

[eqn: G ~==~ {L_B ``-`` L_H} over L_B ~=~ 0.1 ~=``` 10 `(%)]

이 예제에서 보는 바와 같이, 심볼의 발생확률이 Zipf 분포를 따르는 경우 Huffman 코드는 블록코드에 비하여 다소 효율적인 코드체계를 제공한다.

이와 같은 과정은, 더욱 많은 심볼 수(large N)에 대하여 자연스럽게 확장할 수 있다. 또한, 심볼의 수가 증가할수록 Huffman 코드의 이득은 더욱 증가할 것이라는 사실도 쉽게 예측할 수 있다. 그러나 심볼의 수 N이 어느 정도만 증가하더라도 이 예제에서 진행된 과정은 매우 복잡하여 컴퓨터 프로그램에 의한 처리를 필요로 한다. 이 장의 말미에 제시된 연습문제를 통하여, Zipf 분포를 갖는 소스알파벳에 대하여 Huffman 코드를 설계하고, 블록코드의 효율과 비교하는 컴퓨터 프로그램을 작성하게 될 것이다.

다음에 제시한 표 4-1은 몇 가지 N에 대한 Zipf 분포를 두 코드체계로 인코딩하여, 그들의 평균 코드길이와 이득을 항목별로 정리한 것이다. 이 표도 앞에서 언급된 컴퓨터 프로그램에 의하여 마련된 것이다.

표 4-1  Zipf 분포에 대한 블록코드와 Huffman 코드의 비교

심볼의 수 N	블록코드의 길이 LB	Huffman 코드의 길이 LH	이득 (%) G
2 4 8 16 32 64 128 256 512 1024	1 2 3 4 5 6 7 8 9 10	1.0 1.8 2.68 3.43 4.17 4.89 5.60 6.26 6.90 7.54	0 10 10.7 14.3 16.6 18.5 20 21.8 23.3 24.6

사실 Zipf 분포는 심볼들 사이의 확률 변화가 그리 현저하지 않은 경우에 해당한다. 그러나 이러한 열약한 조건 하에서도 Huffman 코드는 심볼의 수 N이 증가할수록 상당히 큰 이득을 나타낸다는 사실을 알 수 있다.

Zipf 분포에 관해서는 이 장의 연습문제에서 프로그래밍 문제를 다룰 것이며, 제6장에서는 Entropy와 관련하여 다시 한 번 논의하게 될 것이다.

실질적으로 전송에 사용되는 소스알파벳에 대하여 Huffman 코딩 과정을 적용하다 보면, 추정된 발생확률에 의하여 진행된다기 보다는 오히려 그 발생확률에 비례하는 자연수들을 이용하여 인코딩된다는 사실을 인식할 수 있을 것이다. 앞에서도 언급한 바 있지만, 실제적인 Huffman 코딩은 발생확률의 추정이 선행된 후에야 이루어 질 수 있다. 일반적으로 발생확률은 각 심볼의 발생빈도수(frequency of occurrence)를 추정함으로써 근사적으로 계산되며, 이 때 발생빈도수는 발생확률에 비례하는 자연수들이라 할 수 있다.

요컨대 소수나 분수로 주어지는 발생확률을 사용하는 것과 여기에 전체 빈도수를 곱하여 자연수로 얻어지는 발생빈도수를 사용하는 것은 Huffman 과정 상에서 아무런 차이점도 없으며, 오히려 발생빈도수가 다루기 쉬운 자연수이므로 편리할 때가 많다는 것이다.

제4-2절의 초반에 우리는 코드의 확장(extension of a code)을 정의하였다. Huffman 코딩 과정에 있어서 이러한 코드의 확장은 구체적으로 어떠한 결과를 나타내는지 살펴 보기로 하자. 원래의 소스알파벳에 여러 개의 심볼이 존재하는 경우에는 그 n-차 확장은 너무 복잡하여 손으로 다루기는 불가능하다. 따라서 우리는 가장 간단한 소스알파벳에 대한 n-차 확장을 취급하여 그 결과를 일반화하는 방법을 택하기로 한다. 앞의 정의에서 보는 바와 같이 코드의 확장은 그 개념이 단순하고 명백한 결과를 예측할 수 있으므로 우리의 이와 같은 접근이 효과적일 것으로 예측된다.

예를 들어서 두 개의 심볼 {s1, s2}를 가지며, 이들 각각의 발생확률이 p1Ａ2/3, p2Ａ1/3인 소스알파벳을 고려하여 보자.

먼저 이들에 대하여 아무런 확장도 가하지 않고 원래의 소스알파벳 상태(이를 1-차 확장이라 한다)에서 Huffman 코딩을 진행하면, 오직 두 개의 심볼만 존재하므로 축소과정은 더 이상 진행할 필요가 없고, 확장과정은 단순히 두 개의 심볼에 □0□ 과 □1□을 할당하는 것으로 이루어 진다. 따라서

[eqn: & s_1 ~∑~ p_1 ``Ａ`` 2 `/` 3 ~~~s_1 ``→``0 ## & s_2 ~∑~ p_2 ``Ａ`` 1 `/` 3 ~~~s_2 ``→``1]	(4-35)

와 같은 코드체계를 얻게 되며, 그 평균 코드길이는

[eqn: L_Ⅰ ~=`` sum_i=1^2 `p_i ``l_i ~=~ 2 over 3 ×1 ``+`` 1 over 3 ×1 ~=~1]	(4-36)

와 같이 계산된다.

정의에 따라, 이 코드체계의 2-차 확장은 두 개의 심볼이 연결된 형태로 다음과 같이 구성된다.

[eqn: S_2 ~=~ \{`s_1 `s_1 ,``s_1 `s_2 ,``s_2 `s_1 ,``s_2 `s_2 ` \}]	(4-37)

또한 확장된 각 심볼의 발생확률은

[eqn: p_{1`1} ``=`` 4 over 9 , ~p_{1`2} ``=`` 2 over 9 , ~p_{2`1} ``=`` 2 over 9 , ~p_{2`2} ``=`` 1 over 9]	(4-38)

와 같이 주어진다. 따라서 2-차 확장에 대한 Huffman 코드는 다음과 같다.

[eqn: &s_1 `s_1 ~∑~ p_{1`1} ``Ａ`` 4 over 9 ~~~~s_1 `s_1 ``→``1## &s_1 `s_2 ~∑~ p_{1`2} ``Ａ`` 2 over 9 ~~~~s_1 `s_2 ``→``0``1## &s_2 `s_1 ~∑~ p_{2`1} ``Ａ`` 2 over 9 ~~~~s_2 `s_1 ``→``0``0``0## &s_2 `s_2 ~∑~ p_{2`2} ``Ａ`` 1 over 9 ~~~~s_2 `s_2 ``→``0``0``1]	(4-39)

이 때, 가장 큰 확률은 가장 작은 확률의 4 배에 해당한다. 따라서 확장되지 않은 경우에 비하여 Huffman 코딩의 결과는 더욱 효율적일 것이라는 사실을 짐작할 수 있다. 이 코드체계의 평균 코드길이는

[eqn: L_Ⅱ &=`` 1 over 2 sum_i=1^4 `p_i ``l_i## &=`` 1 over 2 `left( ` 4 over 9 ×1 ``+`` 2 over 9 ×2 ``+``2 over 9 ×3 ``+`` 1 over 9 ×3 `right) ~≒~ 0.944444]	(4-40)

와 같이 계산된다. 여기서 확장된 심볼은 두 개의 소스심볼이 연결된 상태이므로 평균 코드길이의 계산에 있어서 □2□로 나누었다.

같은 방법으로 3-차 확장은 세 개의 심볼들이 연결된 형태이며, 이들에 대한 발생확률을 계산하여 내림차순으로 나열하고, Huffman 코딩을 진행하면 다음과 같은 결과를 나타낸다.

[eqn: &s_1 `s_1 `s_1 ~∑~ p_{1`1`1} ``Ａ`` 8 `/` 27 ~~~~s_1 `s_1 `s_1 ``→``0``1## &s_1 `s_1 `s_2 ~∑~ p_{1`1`2} ``Ａ`` 4 `/` 27 ~~~~s_1 `s_1 `s_2 ``→``0``0``0## &s_1 `s_2 `s_1 ~∑~ p_{1`2`1} ``Ａ`` 4 `/` 27 ~~~~s_1 `s_2 `s_1 ``→``0``0``1## &s_2 `s_1 `s_1 ~∑~ p_{2`1`1} ``Ａ`` 4 `/` 27 ~~~~s_2 `s_1 `s_1 ``→``1``0``0]	(4-41)

[eqn: &s_1 `s_2 `s_2 ~∑~ p_{1`2`2} ``Ａ`` 2 `/` 27 ~~~~s_1 `s_2 `s_2 ``→``1``1``0## &s_2 `s_1 `s_2 ~∑~ p_{2`1`2} ``Ａ`` 2 `/` 27 ~~~~s_2 `s_1 `s_2 ``→``1``1``1## &s_2 `s_2 `s_1 ~∑~ p_{2`2`1} ``Ａ`` 2 `/` 27 ~~~~s_2 `s_2 `s_1 ``→``1``0``1``0## &s_2 `s_2 `s_2 ~∑~ p_{2`2`2} ``Ａ`` 1 `/` 27 ~~~~s_2 `s_2 `s_2 ``→``1``0``1``1]

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

[eqn: &L_Ⅲ ~=`` 1 over 3 sum_i=1^8 `p_i ``l_i ~simeq~ 0.938272]	(4-42)

진행되는 양상으로 볼 때, 이들보다 더 높은 차수의 확장에 대한 Huffman 코딩은 매우 복잡한 과정을 포함하게 될 것이다.

4-차 확장은 알파벳 내에 16 개의 심볼을 포함하며, 최대/최소 발생확률의 비도 16 배로 나타나게 될 것이다. 또한 이에 대한 Huffman 과정도 매우 복잡하게 진행될 것이 예상된다. 이 때의 평균 코드길이를 계산하면

[eqn: L_Ⅳ ~≒~ 0.938270]	(4-43)

로 주어진다.

식(4-36)으로부터 시작하여 식(4-40), 식(4-42) 및 식(4-43) 등의 경향을 살펴보면, 코드확장의 차수가 증가할수록 평균 코드길이가 축소되는 것은 명백하다. 그러나 그 축소되는 양은 차수의 증가에 따라 점차로 작아져서 평균 코드길이는 어떤 점근선(asymptote)을 향하여 무한히 접근하고 있음을 짐작할 수 있다. 그림 4-9는 코드확장의 차수에 따른 평균 코드길이의 변화 경향을 도시하고 있다.

그러므로 소스알파벳을 무한 차수까지 확장한다 하더라도 평균 코드길이는 무한히 작아지는 것이 아니라 어떤 하한(lower bound)에 접근한다는 것이다. 그림 4-9의 점근선은 바로 그 하한을 표시하고 있으며, 이것은 우리가 제6장에서 구체적으로 다루게 될 Entropy에 해당하는 값이다.

그림 4-9  코드확장의 차수에 따른 평균 코드길이의 변화

제2-1절에서 증명없이 제시하였던 식(2-1)을 이용하여, 이 예에 대한 평균 코드길이의 하한(Entropy)을 계산하면 다음과 같다.

[eqn: H_2`(S)&=`` sum_i=1^2 `p_i ```log_2 `{1 over p_i } ## &=`` 2 over 3 ``log_2 `3over2 ``+`` 1 over 3 ``log_2 `3 ~simeq~ 0.918296]	(4-44)

지금까지 우리는 Radix-2(binary) Huffman 코드를 주로 다루어 왔다. 현대의 통신시스템들이 흔히 이진 디지탈 신호를 사용하여 정보를 전송하고 있지만, 이동통신이나 위성통신에 채택되는 시스템 중에는 일반적인 Radix를 갖는 디지탈 신호를  사용하는 것들도 많다.

Huffman 코드에 대하여 일반적인 Radix-r의 적용은 앞에서 설명한 이진 Huffman 코딩의 규칙을 자연스럽게 확장함으로써 이루어 진다. 우선 Radix-r(rＢ2) Huffman 코드의 소스알파벳과 코드알파벳은 다음과 같이 정의할 수 있다.

[eqn: S ~=`` \{` s_1 ,``s_2 , ``cdots, ``s_q `\}~, ~~~C ~=`` \{`0, ``1, ``2,`` cdots,`` r-1 `\}]	(4-45)

일반적인 Radix-r Huffman 코드를 작성하는 알고리듬은 크게 세 가지 과정으로 구분된다. 그 첫번째 과정은 이진 Huffman 코딩에서는 필요하지 않았던 전처리과정(pre-process)이며, 나머지 두 과정은 축소과정(reduction process)과 확장과정(splitting and expansion process)이다.

전처리과정에서는 소스알파벳 내의 심볼 수가 정확히

[eqn: k ``(r``-``1`) ``／``r ~, ~~k```:``정수]	(4-46)

만큼 존재하는지를 검사한다.

만일, 이를 만족하면 다음의 축소과정으로 넘어가고, 만족하지 않으면 발생확률을 0으로 하는 추가심볼(dummy symbol)을 필요한 갯수 만큼 포함시켜 식(4-46)을 만족하도록 한 다음 축소과정으로 넘어가야 한다.

축소과정에서는 주어진 소스알파벳의 심볼이 오직 Radix 만큼(r 개) 남을 때까지 각 단계마다 (r - 1) 개씩 줄여 나간다.

1. 발생확률이 가장 낮은 r 개의 심볼을 결합하여 그 합의 확률을 가진 하나의 심볼을 만들어 소스심볼의 갯수를 (r - 1) 개 축소시킨다.

[eqn: p_\new ~=~p_q `+``p_q-1 `+``cdots `+``p_{q-r+1}]	(4-47)

2. 새로이 형성된 심볼의 확률을 나머지 확률들과 비교하여 해당되는 위치로 천이시킨다.

[eqn: p_m ``<=``p_\new ``<=``p_n]	(4-48)

3. 위 1, 2의 과정을 오직 r 개의 심볼 만이 남을 때까지 반복한다.

확장과정에서는 위의 축소과정과 반대로 남아있는 r 개의 심볼로부터 각 단계마다 심볼의 갯수를 (r - 1) 개씩 늘려 나간다.

1. 축소과정의 결과로 남아있는 r 개의 심볼에 각각 □0□, □1□, …, □r-1□을 할당한다. (splitting)

2. r 개의 심볼 중 축소과정의 전 단계에서 결합되었던 하나의 심볼에 대하여 다시 r 개로 확장하면서 각각 □0□, □1□, …, □r-1□ 등을 덧붙인다. (expansion)

3. 위 2의 과정을 원래 소스심볼의 갯수 q가 될 때까지 반복한다.

다음에 제시하는 두 가지 예제를 통하여 여기에 설명한 Radix-r Huffman 과정을 구체적으로 활용하여 보자.

[예제 11] (Radix-4 Huffman 코드)

소스알파벳과 코드알파벳이 각각 다음과 같다.

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

또한 추정된 각 심볼의 발생확률이

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

와 같이 주어졌을 때, 적당한 Radix의 Huffman 코드로 인코딩하고 그 디코딩트리를 그려라.

[풀이]

우선 식(4-46)을 이 경우에 적용하면

[eqn: k``(`4 ``-``1`) ``+``4 ~=~ 10 ``, ~~ for ~k``=``2]

와 같이 계산된다.

따라서 추가(dummy)심볼 s9, s10을 포함시켜 Radix-4 Huffman 코딩을 진행하면 다음과 같이 나타난다. Huffman 코딩이 진행되는 과정을 표시하는 그림의 우측에는 이 구성된 코드체계의 디코딩트리를 도시하였다.

특별히, 디코딩트리에 나타나는 추가심볼은 실제로 사용되지 않는 심볼이므로 점선으로 표시해 두었다.

(그림 들어갈 자리임)

[예제 12] (Radix-3 Huffman 코드)

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

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

와 같을 때, 적당한 Radix를 갖는 Huffman 코드를 작성하고 그 디코딩트리를 그려라. 또한, 위 [예제 11]에서와 같이 □dummy 심볼□을 표시하라.

[풀이]

식(4-46)을 적용하면

[eqn: k``(`3 ``-``1`) ``+``3 ~=~ 7 ``, ~~ for ~k``=``2]

이 되므로, 하나의 추가심볼 [eqn: s_7]을 포함시켜 Radix-3에 의한 축소과정과 확장과정을 수행하여야 한다.

그 결과와 디코딩트리는 다음과 같다.

(그림 들어갈 자리)

일반적으로 r Ｂ 2 인 경우에는 이른바 전처리과정에 의하여 추가심볼들이 포함될 수 있으며, 추가심볼이 포함되면 디코딩트리 상에는 반드시 사용되지 않는 결정상태(terminal)가 존재하게 된다. 그러나 이 때에는 이진 Huffman 코드에서와는 달리 불필요한 분기를 포함하지는 않는다. 다시 말해서 [예제 11]의 s9, s10과 [예제 12]의 s7은 실제로 사용되지 않는 심볼이지만, 이들이 공유하고 있는 분기(유보상태)는 제거할 수 없는 것임을 명심해야 한다.

4-7  확률추정오류의 영향

임의의 소스알파벳에 대하여 Huffman 코딩을 진행하기 위해서는 우선 각 심볼의 발생확률을 추정하여야 한다. 일반적으로 소스심볼의 발생확률은 각 심볼의 발생 빈도수를 조사함으로써 추정할 수 있다.

예를 들어서 어떤 소스알파벳에 의하여 작성된 □File□들을 입력으로 받아 그 안에 포함된 각 심볼의 갯수를 세는 프로그램이 작성되어 있다면, 우리는 이 프로그램에 많은 □File□들을 입력시켜 각 심볼의 빈도수를 조사할 수 있을 것이다. 이 때, 입력으로 수용되는 데이타의 양이 많을수록 더욱 정확한 빈도수가 조사될 것이고, 각 심볼에 대한 빈도수를 입력된 심볼의 총수(total number of symbols)로 나누어 발생확률을 추정할 수 있을 것이다.

극단적으로 말하면, 정확한 발생확률을 추정하기 위해서는 무한한 양의 데이타를 입력으로 수용해야만 한다. 이것은 실질적인 운용 상 불가능한 일이며, 따라서 이러한 과정에 의하여 추정된 발생확률은 정확하지 않을 수도 있다. 다시 말해서 추정된 발생확률에는 일반적으로 오류를 포함하게 되는데 이것을 확률추정오류(errors in estimation of probabilities)라 한다.

만일 추정된 확률분포 [eqn: p_i ^(e)](i Ａ 1, 2, □, q)가 확률추정오류를 포함한다고 가정하면, 이러한 오류가 Huffman 코드의 평균 코드길이에는 어떠한 영향을 미칠 것인가? 다시 말해서 확률추정 과정에서 발생한 작은 오류가 설계된 코드체계의 효율성에 미치는 악영향은 얼마나 되겠는가의 문제가 이 절의 핵심이다.

정확한 확률분포를 pi (i Ａ 1, 2, □, q)라 하면, 확률추정오류는

[eqn: e_i ~==~ p_i ^(e) ``-``` p_i ~, ~~i ``=`` 1, ``2, ``cdots , ``q]	(4-49)

와 같이 정의될 수 있다. 여기서 [eqn: p_i ^(e)]와  pi 는 모두 확률분포이므로 각각의 총합은 1이 된다. 따라서

[eqn: 1 over q sum from iＡ1 to q `e_i ~=~0]	(4-50)

임은 명백하다. 이는 확률추정오류의 산술평균(arithmetic mean)이다. 일반적으로 오류의 크기를 측정할 때에는 이와 같은 산술평균보다 제곱평균(mean-square)을 많이 사용한다. 확률추정오류의 제곱평균 혹은 [eqn: p_i ^(e)] 의 pi 에 대한 분산으로서 다음을 정의한다.

[eqn: sigma^2 ~==~ 1 over q sum from iＡ1 to q `e_i ^2]	(4-51)

식(4-49)로부터 추정된 확률분포는

[eqn: p_i ^(e) ~=~ p_i ```+``` e_i ~, ~~i ``=`` 1, ``2, ``cdots , ``q]	(4-52)

와 같이 표시되고, 여기에 설계된 각 코드의 길이 li (i Ａ 1, 2, □, q)를 곱하여 평균 코드길이를 구하면 다음 식으로 표현된다.

[eqn: L^(e) &=`` sum_i=1^q `` p_i ^(e) `l_i ~=`` sum_i=1^q ``p_i ``l_i ~+`` sum_i=1^q ``e_i `` l_i ## &=~ L ~+`` sum_i=1^q e_i ``l_i]	(4-53)

여기서 L은 정확한 확률분포 pi (i Ａ 1, 2, □, q)에 의하여 계산된 평균 코드길이를 표시한다. 따라서 확률추정오류에 의한 평균 코드길이의 변화량은 다음과 같이 정의할 수 있다.

[eqn: Delta `L ~==~ L^(e) `-``L ``=``sum_i=1^q ``e_i ``l_i]	(4-54)

우리는 확률추정오류 ei에 의하여 발생한 평균 코드길이의 변화량이 식(4-50)과 식(4-51)에 표현된 평균과 분산에 대하여 어떠한 양상을 나타내는지 조사하고자 한다. 특히 평균 코드길이의 최대 변화량을 구하여 확률추정오류가 미치는 악영향의 한계를 알아보고자 한다. 이를 위하여 다음과 같은 방정식을 세운다.

.  이와 같은 방법을 □Lagrange multiplier method□라 한다.

[eqn: □ ~Ａ`` sum_i=1^q e_i ``l_i ```-``` lambda` sum_i=1^q e_i ```-``` mu` `left(1 over q sum_i=1^q e_i ^2 ``-`` sigma^2 `right)]	(4-55)

이제 이 식을 확률추정오류 ei (i Ａ 1, 2, □, q)에 관해서 편미분하고, 그 최대값을 구하기 위하여 0 으로 두면

[eqn: {partial □} over {partial e_i} ~Ａ~ l_i ``-`` lambda``-``` {2 `mu} over q `e_i` ~Ａ~ 0~, ~~ i ``Ａ``1, ``2, ``□, ``q]	(4-56)

을 얻는다.

식(4-56)을 i Ａ 1, 2, □, q에 관하여 각각 작성하고, 이들을 모두 더한 후 식(4-50)을 적용하면

[eqn: lambda~Ａ~ 1 over q `sum_i=1^q `l_i]	(4-57)

와 같이 정리된다. 이 식은 평균 코드길이의 변화량을 최대로 하는 파라미터 □의 값을 결정한다.

다음으로 식(4-56)의 양변에 ei 를 곱하고 모든 i 에 관하여 식을 작성한 다음, 이들을 모두 더한 후 식(4-50)을 적용하면, 다음과 같이 또 하나의 파라미터 □의 식을 얻을 수 있다.

[eqn: mu ~=~ q over 2 ``{sum_i=1^q ` e_i``l_i } over { sum_i=1^q `e_i^2 }]	(4-58)

마찬가지 방법으로 식(4-56)의 양변에 li 를 곱하고 모든 i 에 관하여 식을 만들어 합하면, 다음과 같은 또 하나의 방정식이 나타난다.

[eqn: sum_i=1^q `l_i`^2 ``-`` lambda` sum_i=1^q `l_i ``-`` {2`mu} over q `sum_i=1^q `e_i ``l_i ~Ａ~ 0]	(4-59)

이제, 두 개의 파라미터에 관한 식(4-57)과 식(4-58)을 식(4-59)에 대입하여 정리하면

[eqn: sum_i=1^q ``l_i`^2 ``-``` 1 over q left( sum_i=1^q `l_i right)^2 ``-``` { left( sum_i=1^q ``e_i ``l_i right)^2 } over { sum_i=1^q ``e_i^2 } ~Ａ~ 0]	(4-60)

와 같이 나타난다. 이 방정식에 식(4-51) 및 식(4-54)를 대입하여 정리하면

[eqn: left( {Delta L} over q right)^2 ~Ａ~`` sigma ^2 ```left{ ` 1 over q `sum_i=1^q `l_i`^2 ~-~ left(` 1 over q sum_i=1^q `l_i `right)^2 `right}]	(4-61)

와 같은 식을 얻을 수 있다. 이 식 우변의 { } 내에 들어있는 두 개의 항은 코드길이의 제곱평균(mean-square)과 평균제곱(square of the mean)을 각각 나타낸다. 따라서 식(1-109)를 이용하면, { } 내의 식은 코드길이의 분산(variance)을 표시한다. 이러한 사실을 이용하면 식(4-61)은

[eqn: left( {Delta L} over q right)^2 ~=~`` sigma ^2 ```left{ E(bold l`^2 ) ~-~ [ E(bold l `) ]^2 `right} ~=~ Var``[bold e ] cdot Var``[bold l `]]	(4-62)

와 같이 표현할 수 있다. 이것은 확률추정오류에 의하여 발생되는 평균 코드길이의 최대 변화를 나타낸다.

일반적으로 확률의 추정이 크게 잘못되지 않는다면 Var[e]는 매우 작은 값이라 할 수 있다. 또한 Var[e]의 값이 고정되어 있는 경우, 평균 코드길이의 변화는 설계된 코드체계의 각 코드길이 li (i Ａ 1, 2, □, q)가 얼마나 심하게 변하느냐에 따라 달라진다.

그러므로 기본적으로 발생확률의 추정이 대체로 정확하고, 그 기반 위에서 최소분산 Huffman 코드를 사용하여 코드길이 li 의 변화를 최소화한다면, 평균 코드길이의 변화는 매우 작은 값으로 유지될 수 있다. 이와 같은 사실은 발생확률의 추정에 있어서 다소의 오류가 존재한다 하더라도 설계된 소스코드의 효율성은 크게 손상되지 않음을 말해주므로, 최소분산 Huffman 코드는 소스코딩에 있어서 대단히 강력한 도구라 하겠다. 그러나 발생확률의 추정이 근본적으로 크게 잘못되어 있으면, 최소분산을 유지한다 하더라도 설계의 결과로 나타난 코드체계의 효율성은 보장할 수 없다.

최소분산 Huffman 코드의 설계 과정은 근본적으로 순환과정(recursion)이다. 따라서 그 알고리듬을 컴퓨터 프로그램으로 작성하는 것은 매우 용이하다. 또한 제4-2절에서 소개한 디코딩트리는 전송된 Huffman 코드의 수신방법을 제공하게 된다.

앞에서 논의한 바와 같이, 임의의 소스알파벳에 대하여 Huffman 코드를 설계하기 위해서는 각 심볼의 발생확률을 추정하는 선행과정이 필요하다. 발생확률의 추정은 기본적으로 발생되는 심볼의 갯수를 세는 간단한 프로그램에 의하여 해결될 수 있으며, 이 때 추정된 확률의 정확성은 프로그램의 특성에 달려있는 것이 아니라 입력으로 수용된 데이타의 양에 달려있다고 할 수 있다.

발생확률을 추정하는 시스템과 Huffman 인코더/디코더가 설계되면, 우리는 이들을 결합하여 간단한 자료압축(data compression) 시스템을 구축할 수 있다. 제5장에서는 이보다 더욱 효율적인 자료압축 시스템에 대하여 구체적으로 설명할 예정이지만, 각 심볼의 독립적인 발생확률만을 고려하는 현재로서는 이러한 구조로 만족할 수 밖에 없다. 임의의 소스알파벳으로 작성된 충분한 양의 데이타를 입력시켜 발생확률을 추정하고, 추정된 발생확률을 사용하여 각 심볼을 Huffman 인코딩하면 블록코드에 비하여 압축된 자료를 얻을 수 있을 것이며, 이를 원래의 심볼로 환원하기 위해서는 디코딩트리를 이용한 디코더에 입력하면 될 것이다. 그림 4-10에는 □발생확률 추정 시스템□과 □Huffman 인코더 및 디코더□의 입출력 관계를 도시하고 있다.

그림 4-10  Huffman 코딩을 이용한 자료압축

(a) 발생확률 추정시스템      (b) Huffman 인코더/디코더

또 하나 흥미로운 것은, 소스심볼의 자료압축을 위한 Huffman 코딩시스템과 채널 상의 오류를 정정하기 위한 Hamming 코딩시스템을 결합시켜 효율성과 신뢰성을 동시에 고려한 전송시스템을 구축할 수 있다는 점이다. 소스심볼들은 먼저 Huffman 방식으로 소스인코딩되어 가변길이 동시코드가 되고, 그 출력을 일정한 길이의 블록으로 나누어 Hamming 방식으로 채널인코딩되어 전송된다. 한편 수신측에서는 먼저 Hamming 방식으로 디코딩하고 이어서 디코딩트리를 이용한 Huffman 방식으로 디코딩함으로써 원래의 심볼들을 얻어낼 수 있다. 그림 4-11에는 이와 같은 전송시스템의 구성도를 제시하였다.

그림 4-11  Huffman-Hamming 전송시스템

연 습 문 제

4.1	다음에 주어진 코드체계들은 유일디코딩이 가능한 체계인지 밝혀라.

(a)	[eqn: & s_1 ``=`` 0 # & s_2 ``=`` 0``1 # & s_3 ``=`` 0``0``1 # & s_4 ``=`` 0``0``1``0 # & s_5 ``=`` 0``0``1``1 #]	(b)	[eqn: & s_1 ``=`` 0 # & s_2 ``=`` 0``1 # & s_3 ``=`` 0``1``1 # & s_4 ``=`` 1``1``1]

(c)	[eqn: & s_1 ``=`` 0 # & s_2 ``=`` 1``0 # & s_3 ``=`` 1``1``0 # & s_4 ``=`` 1``1``1]	(d)	[eqn: & s_1 ``=`` 1 # & s_2 ``=`` 1``0 # & s_3 ``=`` 1``0``0 # & s_4 ``=`` 1``0``0``0 # & s_5 ``=`` 1``0``0``1]

4.2	소스알파벳의 심볼 수가 각각 6, 7, 8, 9 개인 경우에 대하여,  그림 4-2(a) 및 그림 4-2(b)와 같은 형태를 갖는 동시코드를 작성하라.

4.3	위 문제 4.2에서 작성된 코드체계들이 각각 Kraft 부등식을 만족하는지 검토하라.

4.4	(Infinite comma code)

각 코드의 길이가 [eqn: l_k ``=``k , ``k`=`1,`2,`cdots,`inf] 로 표시되는 무한 Comma 코드는 Kraft 부등식을 만족하는가 ?

(a) Radix-2 인 경우	(b) Radix-r 인 경우

에 대하여 각각 검토하라.

4.5	소스심볼의 수가 각각 10, 20, 30 개일 때, 여러가지 형태의 축소형 블록코드를 작상하라. 또한 구성된 각 코드체계에 대하여 디코딩트리를 그려라.

4.6	코드알파벳이 [eqn: C ``=` \{`0,``1 \}]로 주어지는 이진 코드체계의 코드길이가 각각 다음과 같을 때, 이러한 길이를 갖는 동시코드의 존재성을 밝혀라.

(a)	[eqn: l_1 `=`1, ~l_2 `=`2, ~l_3 `=`3, ~l_4 `=`4, ~l_5 `=`5, ~l_6 `=`5]

(b) [eqn: l_1 `=`2, ~l_2 `=`2, ~l_3 `=`2, ~l_4 `=`3, ~l_5 `=`4, ~l_6 `=`4 , ~l_7 `=`5]

(c) [eqn: l_1 `=`2, ~l_2 `=`2, ~l_3 `=`2, ~l_4 `=`3, ~l_5 `=`3, ~l_6 `=`4, ~l_7 `=`4]

(d) [eqn: l_1 `=`1, ~l_2 `=`1, ~l_3 `=`2, ~l_4 `=`2, ~l_5 `=`2, ~l_6 `=`3]

4.7	코드알파벳이 [eqn: C ``=` \{`0,``1, ``2, ``3 \}]으로 주어지는 Radix-4 코드에서 코드의 길이가 각각 다음과 같을 때, 이러한 길이를 갖는 동시코드는 존재하는가 ?

(a)	[eqn: l_1 `=`1, ``l_2 `=`1, ``l_3 `=`1, ``l_4 `=`2, ``l_5 `=`2, ``l_6 `=`2, ``l_7 `=`3, ``l_8 `=`3]

(b) [eqn: l_1 `=`1, ``l_2 `=`1, ``l_3 `=`1, ``l_4 `=`1, ``l_5 `=`2, ``l_6 `=`2 , ``l_7 `=`3, ``l_8 `=`3]

(c) [eqn: l_1 `=`2, ``l_2 `=`2, ``l_3 `=`2, ``l_4 `=`3, ``l_5 `=`3, ``l_6 `=`3, ``l_7 `=`3]

(d) [eqn: l_1 `=`1, ``l_2 `=`1, ``l_3 `=`2, ``l_4 `=`2, ``l_5 `=`2, ``l_6 `=`2]

4.8	소스알파벳과 각 심볼의 발생확률이 다음과 같이 주어졌을 때 최소분산을 갖는 이진 Huffman 코드를 작성하라.

(a) [eqn: S``Ａ`\{ `s_1 ,`s_2 , `s_3 `\} ~, ~~p_1 `=` 1 over 2 , ``p_2 `=` 1 over 3 ,``p_3 `=` 1 over 6]

(b) [eqn: S``Ａ`\{ `s_1 , `s_2 , `s_3 ,` s_4 , `s_5 `\} ,~p_1 = 1 over 3 , `p_2 = 1 over 4 ,`p_3 = 1 over 5 , `p_4 = 1 over 6 , `p_5 = 1 over 20]

(c) [eqn: S``Ａ`` \{ `s_1 ,`s_2 ,`s_3 ,` s_4 ,`s_5 `\}, ~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)[eqn: & SＡ \{ ` s_1 ,`s_2 ,`s_3 , `s_4 , `s_5 , `s_6 `\}~, # & ~~~~p_1 `Ａ` 1 over 3 , ``p_2 `Ａ` 1 over 4 , ``p_3 `Ａ` 1 over 6 , ``p_4 `Ａ` 1 over 8 , ``p_5 `Ａ` 1 over 12 , ``p_6 `Ａ` 1 over 24]

4.9	위 문제 4.8에서 작성된 각 코드체계의 디코딩트리를 그리고, 평균 코드길이와 분산을 구하라.

4.10 최소분산 Huffman 코드는 축소과정의 각 단계에서 결합에 의하여 생성된 확률을 가능한 최상위에 둠으로써 얻어진다. 이제 결합에 의하여 생성된 확률을 가능한 최하위에 두는 방법으로 문제 4.8의 소스알파벳 대한 Huffman 코드를 작성하라.

4.11	위 문제 4.10에서 작성된 각 코드체계의 평균 코드길이와 분산을 구하고, 이들을 문제 4.9에서 구한 값들과 비교하라.

4.12	소스알파벳, 코드알파벳 및 각 심볼의 발생확률이 다음과 같이 주어질 때, 최소분산 Huffman 코드를 작성하라.

(a) [eqn: & S``=`` \{`a,`b,`c,`d` \}, ~C``=`` \{`0,`1 \} # &~~~p_a `Ａ` 27 over 40 , ``p_b `Ａ` 9 over 40 ,``p_c `Ａ` 3 over 40 , ``p_d `Ａ` 1 over 40]

(b) [eqn: &S``Ａ`` \{ `a, `b,`c,`d,`e \}, ~C``=`` \{`0,`1,`2 \}# &~~~p_a `Ａ` 1 over 18 , ``p_b `Ａ` 2 over 18 ,``p_c `Ａ` 4 over 18 , ``p_d `Ａ` 5 over 18 , ``p_e `Ａ` 6 over 18]

(c) [eqn: & S``Ａ`` \{` a, `b,`c,`d,`e,`f \} , ~ C``=`` \{`0,`1,`2 \}# &~~~p_a `Ａ` 1 over 2 , ``p_b `Ａ` 1 over 4 ,``p_c `Ａ` 1 over 8 , ``p_d `Ａ` 1 over 16 , ``p_e `Ａ` 1 over 32 , ``p_f `Ａ` 1 over 32]

(d) [eqn: & S``Ａ`` \{` a, `b,`c,`d,`e,`f \} , ~ C``=`` \{` 0,`1,`2,`3 \}# &~~~p_a `Ａ` 1 over 80 , ``p_b `Ａ` 4 over 80 ,``p_c `Ａ` 8 over 80 , ``p_d `Ａ` 16 over 80 , ``p_e `Ａ` 24 over 80 ,``p_f `Ａ` 27 over 80]

4.13	위 문제 4.12에서 작성된 각 코드체계의 디코딩트리를 그려라. 이 때, 추가된 심볼도 디코딩트리에 표시하라.

4.14	위 문제 4.12의 각 경우에 대하여, 축소과정의 각 단계에서 결합된 확률을 가능한 최하위에 두는 방법으로 Huffman 코드를 작성하고, 그들의 디코딩트리를 그려 문제 4.13의 결과와 비교하라.

4.15	소스알파벳 [eqn: S`= \{` s_1 ,` s_2 ,`s_3 ,` s_4 ,`s_5 ,` s_6 \}]의 추정된 발생확률이

[eqn: p_1 `Ａ` 1 over 3 , ``p_2 `Ａ` 1 over 4 , ``p_3 `Ａ` 1 over 6 , ``p_4 `Ａ` 1 over 8 , ``p_5 `Ａ` 1 over 12 , ``p_6 `Ａ` 1 over 24]

와 같이 주어졌다. 이러한 소스알파벳에 의하여 구성된 File이 정확히 200,000 개의 심볼을 포함하고 있다고 가정하면

(a) 예상되는 각 심볼의 빈도수(frequency)는 얼마인가 ?

(b) 구해진 빈도수를 이용하여 최소분산 Huffman 코드를 작성하고, 문제 4.8(d)의 결과와 비교하라.

4.16	소스알파벳 [eqn: S`= \{` s_1 ,` s_2 ,`s_3 ,` s_4 ,`s_5 ,` s_6 ,`s_7 ,`s_8 ,` s_9 , `s_10 \}]로 형성된 여러개의 File을 조사하여 총 500,000 개의 심볼을 분류한 결과 다음과 같은 빈도수를 얻었다고 가정하자.

[eqn: & s_1 ~:~````35,400~~~~~ &s_2 ~:~ 82,650~~~~~ &s_3 ~:~````8,450 # & s_4 ~:~106,740~~~ &s_5 ~:~ 54,400~~~ &s_6 ~:~22,980 # & s_7 ~:~````43,540~~~ &s_8 ~:~ 25,960~~~ &s_9 ~:~65,890 # & s_10 ~:~``53,990]

(a) 각 심볼의 발생확률을 추정하라.

(b) 코드알파벳을 [eqn: C `= \{`0,`1 \}]로 할 때

① 최소분산 Huffman 코드를 작성하라.

② 작성된 코드체계의 디코딩트리를 그려라.

③ 평균 코드길이와 분산을 구하라.

(c) 코드알파벳을 [eqn: C `= \{`0,`1,`2,`3 \}]으로 하여 위 문제 (b)를 반복하라.

(d) 발생확률을 사용한 경우와 빈도수를 사용한 경우 Huffman 코딩 과정은 어떠한 차이점이 있는지 설명하라.

(e) 위 문제 (b)에서 결합된 확률을 가능한 최하위에 천이시키는 방법으로 코딩하고 그 결과를 비교하라. 최소분산 코드와 실질적인 차이점이 있는가 ?

4.17	(Zipf distribution)

식(4-33)으로 주어진 Zipf 확률분포에 있어서, 전체 심볼의 수 N Ａ 8 이라 가정하고 다음에 답하라.

(a) 블록코드로 인코딩하고 그 평균 코드길이 LB를 구하라.

(b) 식(4-33)에 정의된 합 SN을 구하고, 각 심볼의 발생확률 p1, p2, □, p8 을 계산하라.

(c) 위 (b)에서 계산된 발생확률을 이용하여 최소분산 Huffman 코드를 작성하라.

(d) 작성된 Huffman 코드의 평균 코드길이 LH를 구하라.

(e) 블록코드에 대한 Huffman 코드의 이득 G(%)를 구하라.

(f) 이상의 결과를 표 4-1의 해당되는 행과 비교하라.

4.18	위 문제 4.17에서 전체 심볼의 수를 N Ａ 16 으로 변경하여 반복하고, 표 4-1의 네 번째 행을 확인하라.

4.19	소스알파벳 S1 Ａ {a, b, c, d}에 대하여 추정된 발생확률이

[eqn: p_a ``Ａ`` 1 over 3 , ~p_b ``Ａ`` 1 over 3 ,~p_c ``Ａ`` 1 over 6 , ~p_d ``Ａ`` 1 over 6]

와 같이 주어졌다.

(a) 최소분산 Huffman 코드를 작성하고 그 평균 코드길이 L1 을 구하라.

(b) 소스알파벳의 2-차 확장 S2 를 구하고 각 심볼의 발생확률을 구하라.

(c) 위 (b)에서 유도한 2-차 확장에 대하여 최소분산 Huffman 코드를 작성하고, 그 평균 코드길이 L2 를 구하여 L1 과 비교하라.

(d) 주어진 소스알파벳을 무한히 확장한다면 평균 코드길이는 얼마까지 감소될 수 있는가 ?

4.20 [eqn: S ``Ａ`` "{"s_1, ~s-_2`"}"]에 대하여 두 심볼의 발생확률이 각각 [eqn: p_1 `Ａ`0.7 , ``p_2 `Ａ` 0.3]로 주어졌다.

(a) 소스알파벳에 대한 2-차 확장을 구하여 Huffman 방법으로 인코딩하고 그 평균 코드길이를 구하라.

(b) 3-차 및 4-차 확장에 대하여 위 (a)를 반복하고 각각의 평균 코드길이를 비교하라.

(c) 주어진 소스알파벳을 무한히 확장할 때 나타나는 최소의 평균 코드길이는 얼마인가 ?

4.21 [예제 11]에 주어진 소스알파벳과 발생확률을 이용하여 Radix-3 및 Radix-5 Huffman 코드를 작성하라. 또한 이들에 대한 디코딩트리를 그려라.

4.22	소스알파벳 S Ａ {a, b, c, d, e, f, g} 에 대하여 추정된 발생확률이

[eqn: p_a `Ａ` 1 over 20 , ``p_b `Ａ` 1 over 10 ,``p_c `Ａ` 1 over 15 , ``p_d `Ａ` 1 over 5 , ``p_e `Ａ` 1 over 12 , ``p_f `Ａ` 1 over 6 , ``p_g `Ａ` 1 over 3]

로 주어졌다.

(a) Radix-2 Huffman 코드를 작성하고 그 평균 코드길이를 구하라.

(b) Radix-3 Huffman 코드를 작성하고 그 평균 코드길이를 구하라.

(c) Radix-4 Huffman 코드를 작성하고 그 평균 코드길이를 구하라.

(d) 각 코드체계의 디코딩트리를 그려라.

4.23*	위 문제 4.22의 발생확률 값에 각각 자연수 □8,000□을 곱하여 등가빈도수를 구하고, 여기에 빈도수 □1□에 해당하는 □ESC(escape)□ 문자를 추가시켜 Radix-2 Huffman 코드로 코딩하라. 또한 코드체계에 대한 디코딩트리를 그려 문제 4.22의 결과와 비교하라.

4.24*	위 문제 4.23을 Radix-3 및 Radix-4에 대하여 반복하고 그 결과를 문제 4.22의 결과와 비교하라.

4.25*	(Huffman Encoder Programing)

소스알파벳의 원소 수 Q와 각 원소의 발생확률 {P(i)}i=1,2,□,Q를 입력으로 받아, 그에 대한 최소분산 이진 Huffman 코드를 출력하는 컴퓨터 프로그램을 작성하라. 또한 임의의 소스알파벳에 대한 입력자료들을 준비하여 결과를 산출하고, 그들 코드체계에 대한 디코딩트리를 그려라. 이 때, 컴퓨터 프로그램의 입출력 구조도(I/O diagram)는 다음과 같다.

	Binary Huffman Encoder
Q : # of symbols P[i], i=1,2,…,Q		S[1] : code (# of bits) S[2] : code (# of bits) □ S[Q] : code (# of bits)

4.26*	(ASCII 발생확률 추정 Programing)

(a) ASCII 코드로 작성된 Text-file들을 입력으로 받아 각 문자의 발생 빈도수를 누적시키고, 그 누적된 빈도수에 의하여 각 문자의 발생확률 {P(i)}i=1,2,□,Q를 계산하는 컴퓨터 프로그램을 작성하라. 이 때의 입출력 구조도는 다음과 같다.

	ASCII Symbol Probabilities Estimator
ASCII Text-files		P[i], i=1,2,…Q

(b) 위 (a)에서 계산된 확률을 문제 4.25의 프로그램에 입력시켜 ASCII 심볼에 대한 최소분산 Huffman 코드를 작성하고, 그 평균 코드길이를 구하라.

(c) 평균 코드길이와 디코딩 규칙의 측면에서 원래의 ASCII 코드체계와 비교하라.

4.27*	(Zipf 분포에 대한 Huffman 인코더)

다음 그림과 같은 입출력 구조도를 이용하여 Zipf 확률분포에 대한 Huffman 인코더를 컴퓨터 프로그램으로 구축하여 보자.

(a) 소스알파벳의 심볼 수 N 을 입력으로 받아 각 심볼의 발생확률 {P(i)}i=1,2,□,N를 계산하고,

(b) 이를 위 문제 4.25에서 작성된 프로그램의 입력으로 받아 최소분산 Huffman 코드를 작성하며,

(c) 작성된 Huffman 코드의 평균 코드길이를 계산하여 블록코드의 길이와 비교함으로써 이득을 계산하는 컴퓨터 프로그램을 작성하라.

입력	Zipf Probability Calculation	발생확률	Binary Huffman Encoder		Code Length and Gain Calculation
N : # of Symbols		P[i], i=1,2,…,N		최소분산 Huffman Code		LH LB G (%)

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

4.28*	(코드의 확장과 Huffman 인코더)

소스알파벳[eqn: S ``Ａ`` "{"s_1, ~s-_2`"}"]에 대하여 두 심볼의 발생확률이 각각 다음과 같이 주어졌다.

[eqn: p_1 `Ａ`2 over 3 , ~``p_2 `Ａ` 1 over 3]

(a) 코드확장의 차수 N 을 입력으로 받아 확장된 심볼의 발생확률을 계산하고, 이를 이용하여 Huffman 코드를 작성한 후 평균 코드길이를 산출하는 컴퓨터 프로그램을 작성하라. 이 때, 다음과 같은 입출력 구조도를 사용하라.

입력	Probability Calculation	발생확률	Binary Huffman Encoder		Code Length Calculation
N : Order of Extension		P[i], i=1,2,…,2N		최소분산 Huffman Code		LN

(b) 입력으로 N = 2, 3, 4 를 각각 적용하여 식(4-39),(4-40), 식(4-41),(4-42) 및 식(4-43)을 확인하라.

(c) 입력 N 을 점차로 증가시켜 출력 LN 이 식(4-44)에 접근함을 확인하라.