제 5 장

상관관계와 자료압축

5-1  심볼 간 상관관계와 소스코드

	정보공학

제 5 장 상관관계와 자료압축

현대의 정보통신시스템이나 저장시스템 등 디지탈 신호를 처리하고 있는 장비들은 실로 무수한 종류의 코드체계를 사용되고 있다. 이들은 시스템이 처한 잡음 환경과 사용되는 심볼 및 신호의 특성 등에 따라 적절하게 설계된 다양한 종류의 소스코드와 채널코드를 포함하고 있다. 따라서 현재 사용되고 있는 코드체계들을 포괄적으로 취급한다는 것은 불가능한 일이다. 우리는 이들 중에서 가장 보편적으로 사용되며 개념적으로 명백한 코드체계를 집중적으로 설명할 것이다. 독자들은 이러한 보편적인 코드체계의 학습을 통하여 기본 개념을 철저히 파악해 둠으로써, 필요에 따라 이들이 응용된 체계나 더 복잡한 체계의 해석은 물론 시스템에 따라 요구되는 코드체계를 스스로 설계할 수 있는 능력을 키워 나가야 한다.

제4장에서 상세히 논의하였던 Huffman 코딩은 소스알파벳의 각 심볼들에 대하여 추정된 독립적인 발생확률 만을 사용하는 방식이었다. 그러나 일반적으로 소스심볼들이 연결된 메시지를 자세히 검토해 보면 이웃한 심볼 사이에 상관관계(correlation)가 존재함을 알 수 있으며, 이러한 상관관계를 소스코딩에 적용하면 단지 독립적인 발생확률 만을 적용하는 것보다 더욱 효율적인 코드체계를 구축할 수 있다.

이 장의 첫부분에서는 소위 Markov 과정(Markov process)의 기본적인 개념을 설명한다. 이는 근본적으로 제1-4절에서 다루었던 조건확률(conditional probability)에 의한 확률구조이다. 일반적인 소스알파벳에 대하여 Markov 과정에 의한 확률구조가 알려지면, 우리는 독립적인 발생확률 뿐만 아니라 심볼 상호간의 상관관계까지 고려한 소스코딩을 수행할 수 있게 된다.

다음으로 우리는 예측형 Run-length 코드(predictive run-length code)를 다룬다. 이는 예측기(predictor)를 이용한 소스코드의 일종으로서 자료압축(date compression)의 가장 일반적인 방법이다. 이 시스템의 효율성은 주로 예측기의 성능에 의하여 지배되는데, 소스알파벳의 확률구조에 따라 다음 심볼(the next symbol)을 정확히 예측하는 능력이 우수할수록 자료의 양은 더욱 축소된다.

오늘날 반도체 기술의 발달로 값싸고 성능이 우수한 많은 예측기들이 생산되고 있으며, 이들을 이용한 소스코딩의 획기적인 방법들도 다양하게 제시되고 있다. 이 책에서는 예측기의 원리나 제작 방법 등에 대해서는 상세히 취급하지 않겠고, 단지 이를 소스코딩에 응용하는 Run-length 코드시스템의 일부로 채택하여 자료압축의 효과를 검토하기로 한다.

.  예측기는 고정형(fixed)/적응형(adaptive) 및 선형(linear)/비선형(non-linear) 등으로 구분되며, 이의 성능을 향상시키고자 하는 연구는 신호처리 분야의 중요한 과제가 되고 있다. 예측기의 원리와 구성에 대하여 좀 더 공부하고자 하는 독자는 다음 서적을 참고하라.

V.Cappellini, Data Compression and Error Control Techniques with Applications, Ch.3, 1985, Academic Press.

일반적으로 아날로그-디지탈 변환(A/D : analog-to-digital conversion)이나 디지탈-아날로그 변환(D/A : digital-to-analog conversion)에 있어서는 연속되는 심볼의 코드들이 거의 유사하게 작성될수록 오류발생의 가능성은 작아진다. 이러한 조건을 만족하는 코드체계로서 가장 널리 사용되고 있는 것이 Gray 코드이다.  Gray 코드는 논리회로 설계를 비롯한 컴퓨터 공학이나 전자공학 및 정보통신공학 등 디지탈 신호를 다루는 모든 분야에서 광범위하게 사용되고 있기 때문에 그 중요성에 대한 별도의 설명은 필요치 않을 것이다. 그러나 수(혹은 심볼)의 진행에 따라 오로지 1 bit 씩 변화해 가는 코드체계의 특성을 설명하기 위하여 이웃한 심볼 간의 상관관계로 취급되는 새로운 개념을 도입할 필요가 있는 것이다.

제2-3절에서 언급한 바와 같이, 일반적으로 자연발생적인 신호들은 연속신호(혹은 아날로그 신호)이다. 반면에 오늘날 사용되는 정보처리 시스템들은 거의 디지탈 방식이다. 따라서 A/D 혹은 D/A 변환은 필연적이며, 이것이 Gray 코드가 널리 사용되는 주된 이유이다.

Gray 코드가 형성되는 과정에 보수(complement)의 개념을 도입하면 Gray 코드와 정 반대의 특성을 가진 Anti-Gray 코드를 작성할 수 있다. Gray 코드가 이웃한 심볼 사이에 최소로 변화하는 체계라고 한다면, Anti-Gray 코드는 이웃한 심볼 사이에 최대로 변화하는 코드이다. 이는 기억장치의 주소(address)를 표시하는 데 사용되어, 그 억세스 상에서 발생할 수 있는 오류를 감소시킬 수 있음이 밝혀져 있다.

앞에서도 언급하였지만, 심볼 상호간의 상관관계를 이용하는 소스코드 체계는 매우 다양하여, 이 장에서 설명하고자 하는 몇가지 체계는 이들 중 극히 일부에 지나지 않는다. 그러나 여기서 논의되는 코드체계들의 개념을 완전히 이해하면, 더 복잡하고 다양한 코드체계에 대해서도 용이하게 접근할 수 있을 것으로 사료된다.

5-2  Morkov 과정과 Huffman 코드

지금까지 우리는 소스심볼의 독립적인 발생확률 만을 사용하여 소스코딩을 수행하여 왔다. 그러나 보통의 정보 소스에서 사용되는 심볼들의 특성을 조사해 보면 상당히 복잡한 확률적 구조를 가진다는 사실을 알 수 있다. 영문자 □Q□와 □U□의 상관관계는 단지 독립적인 발생확률 만을 가지고는 설명될 수 없는 확률구조의 일예라 할 것이다. 영문자 □U□는 독립적인 발생확률로 볼 때 매우 드물게 나타나는 심볼이지만, 바로 전에 영문자 □Q□가 발생했다는 조건 하에서는 거의 1에 가까운 확률을 갖는다.

확률론에 있어서 이러한 상황을 가장 잘 표현하고 있는 것은 제1-4절에서 소개한 조건확률(conditional probability)이다. 영문자 □Q□가 발생했다는 조건 하에서 영문자 □U□가 발생할 조건확률은

[eqn: P`(U vert Q`)]	(5-1)

와 같이 표시할 수 있다. 이를 일반화하여 표기하면

[eqn: P`(s_i vert s_i_1 ,`s_i_2 ,` cdots,`s_i_j `)]	(5-2)

와 같이 나타낼 수 있으며, 이는 심볼 [eqn: s_i_1 ,`s_i_2 ,` cdots, `s_i_j]가 차례로 발생했다는 조건 하에서 심볼 [eqn: s_i]가 발생할 조건확률을 말한다. 그러므로 이 때 발생한 심볼열(sequence of symbols)은 [eqn: s_i_1 , `s_i_2 , `cdots, `s_i_j , `s_i]가 된다.

식(5-2)에 표시된 조건확률은 하나의 심볼 이전에 발생된 j 개의 심볼을 그 조건으로 취하고 있으므로, 소스(source)는 j 개의 심볼을 저장할 수 있는 기억장치를 갖추어야만 이러한 조건확률을 완전히 정의할 수 있을 것이다. 이러한 조건을 만족하는 정보원천을 j-memory 소스라 하며, 이를 표현하는 조건확률의 모임을 j-차 Markov 과정(jth-order Markov process)라 한다.

일반적으로 문자정보 메시지의 앞 부분에 있는 문자들이 그 다음에 나타날 문자들의 발생확률에 큰 영향을 미치는 것은 실질적인 언어에 있어서 명백한 사실로 받아들여지고 있다. 컴퓨터 언어에 있어서도 이전에 발생한 심볼에 관계없이 독립적으로 사용되는 Zero-memory 소스는 매우 드물고, 어떠한 형태이든 심볼들 사이의 상관관계를 이용하는 경우가 대부분이다.

이제부터 모든 시스템들은 유한한 기억장치를 가지고, 이들에 의한 유한 개의 상태(finite states)를 소유한다고 가정한다.

예를 들어서 소스알파벳이

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

로 주어지는 1-memory 소스는 q 개의 상태를 가진다. 또한 동일한 소스알파벳을 이용하는 2-memory 소스는 한 쌍의 소스심볼로 이루이진 q2 개의 상태를 가진다.

어떤 예측기가 다음과 같은 차동방정식(difference equation)을 사용하여 차기 심볼을 예측하고 있다면,

[eqn: y_n／1 ~=~ 2` `y_n ``-`` y_n-1 , ~for ~\all ~ `n]	(5-4)

이는 2-memory 소스의 일종이다. 왜냐하면 이 식에서 차기값 yn／1은 두 개의 이전값 yn, yn-1 로부터 얻어지고 있기 때문이다.

만일 식(5-2)에 표시된 j-memory 소스가 식(5-3)의 소스알파벳을 사용하고 있다면, 그 상태의 수는 qj 개로 주어진다.

Markov 과정의 개념을 좀 더 구체적으로 설명하기 위하여, 다음과 같이 세 개의 심볼을 갖는 소스알파벳을 가정하여 보자.

[eqn: S~=`` \{ `a , ``b ,`` c `\}]	(5-5)

만일 하나의 심볼을 저장하는 1-memory 소스를 사용한다면, 상태의 갯수는 □3□이며, 이들 상태를 조건으로 하는 조건확률들이 각각의 심볼에 대하여 존재할 것이므로 식(5-2)에 표시된 형태의 조건확률들은 모두 9 개가 될 것이다.

이러한 1-차 Markov 과정을 표현하는 조건확률들이 각각 다음과 같이 추정되었다고 가정하자.

[eqn: & P`(a vert a`) ``Ａ`` 1 over 3 ~& P`(b vert a`) ``Ａ`` 1 over 3 ~& P`(c vert a`) ``Ａ`` 1 over 3## & P`(a vert b`) ``Ａ`` 1 over 4 ~& P`(b vert b`) ``Ａ`` 1 over 2 ~& P`(c vert b`) ``Ａ`` 1 over 4## & P`(a vert c`) ``Ａ`` 1 over 4 ~& P`(b vert c`) ``Ａ`` 1 over 4 ~& P`(c vert c`) ``Ａ`` 1 over 2]	(5-6)

이 식은 하나의 Markov 과정을 완벽하게 표현하고 있다. 다시 말해서 임의의 상태로부터 다른 상태로의 천이를 조건확률에 의하여 모두 규정하고 있기 때문에 주어진 1-memory 소스의 동작을 완전히 나타내 주고 있다는 것이다.

우리는 식(5-6)으로 표현된 Markov 과정을 다음과 같은 행렬(matrix)의 형태로 표현할 수도 있다.

[eqn: Gamma~=~ bmatrix { 1 over 3 &~~ 1 over 3 &~~ 1 over 3 ## 1 over 4 &~~ 1 over 2 &~~ 1 over 4 ## 1 over 4 &~~ 1 over 4 &~~ 1 over 2 }]	(5-7)

이 행렬을 주어진 Markov 과정의 천이행렬(transition matrix)이라 한다. 천이행렬의 각 원소는 식(5-6)의 조건확률들을 수정 없이 옮겨 놓은 것인데, 이들을 각 상태 사이의 천이확률(transition probability)이라고 한다.

Markov 과정을 표현하는 또 하나의 방법으로 천이그래프(transition graph)를 들 수 있다. 천이그래프는 하나의 방향성그래프(digraph or directional graph)로서, 그 정점(vertex or node)들은 해당되는 □상태□를 표시하고, 그 가지(edge or branch)들은 상태천이에 요구되는 □조건확률□을 표시하도록 그린 도표이다.  식(5-6) 혹은 식(5-7)로 표현된 Markov 과정에 대한 천이그래프는 그림 5-1과 같이 나타난다.

.  일반적으로 방향성그래프는 함수적 관계(functional relation)를 표현하기 위하여 그리는 일종의 도표로서 정점(node)과 가지(branch)로 구성된다. 특별히 각 정점과 가지에 레이블(label)을 붙인 방향성그래프를 □labeled digraph□라 한다. 천이그래프는 하나의 □labeled digraph□이다.

함수적 관계와 방향성 그래프에 관하여 구체적으로 공부하기를 원하는 독자는 다음 서적을 참고하라.

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

그림 5-1  천이그래프(예)

천이그래프에 있어서, 각 정점에는 상태 a, b, c 를 표기하고, 화살표는 상태천이의 방향 나타내며 그러한 상태천이가 일어날 확률들을 해당되는 화살표 옆에 표기함으로써 완성된다. 예를 들어서 조건확률 P(a | b)는 상태 b로부터 상태 a로 천이하는 확률을 나타내므로 해당되는 화살표 옆에 □1/4□로 표기되어 있다.

이 예에서 각 상태는 모두 3 개의 □나가는(Out)□ 화살표와 3 개의 □들어오는(In)□ 화살표를 가진다. 임의의 상태를 중심으로 입출(入出)되는 화살표의 갯수를 그 상태의 입력차수(In-degree) 및 출력차수(Out-degree)라고 부른다.

이제 현재의 상태가 결정되는 확률분포를 다음과 같은 행벡터(row vector)로 표시하여 보자.

[eqn: bmatrix {p_a ~~p_b ~~p_c ` }]	(5-8)

여기서 각 상태가 결정되는 확률들은 하나의 확률분포를 이루므로

[eqn: p_a ``+``` p_b ``+ ```p_c ~=~ 1]	(5-9)

이다. 만일 이들 세 가지 상태 중 어떤 상태가 결정될 확률이 1 로 주어지면, 나머지 두 가지 상태에 대한 확률은 명백히 0 이고, 이에 따라 하나의 확정상태를 얻게 된다.

현재의 상태를 표시하는 행벡터 식(5-8)을 천이행렬 식(5-7)에 곱하면, 차기상태(the next state)의 확률분포를 얻게 된다. 즉 차기상태의 확률분포는

[eqn: bmatrix {p_a ~p_b ~ p_c `} bmatrix { 1/3 & 1/3 & 1/3 ## 1/4 & 1 /2 & 1 / 4## 1 / 4 & 1/ 4 & 1 / 2 }]

[eqn: Ａ`` bmatrix { 1 over 3 p_a + 1 over 4 p_b + 1 over 4 p_c ~~ 1 over 3 p_a + 1 over 2 p_b + 1 over 4 p_c ~~1 over 3 p_a + 1 over 4 p_b + 1 over 2 p_c }]	(5-10)

와 같이 계산된다. 이는 천이행렬의 각 원소를 식(5-6)에 표시된 조건확률의 식으로 대치하고, 제1장의 식(1-27)로 표현된 전체확률의 정리를 적용함으로써 쉽게 입증된다.

만일 차차기상태(the state after the next state)의 확률분포를 얻고자 한다면, 식(5-10)의 결과를 다시 식(5-7)의 천이행렬에 곱하면 될 것이다.

벡터나 행렬의 곱셈에 있어서는 결합법칙이 성립하므로, 먼저 두 개의 천이행렬을 곱하면

[eqn: bmatrix { 1/3 & 1/3 & 1/3 ## 1/4 & 1 /2 & 1 / 4## 1 / 4 & 1/ 4 & 1 / 2 } bmatrix { 1/3 & 1/3 & 1/3 ## 1/4 & 1 /2 & 1 / 4## 1 / 4 & 1/ 4 & 1 / 2 } ~=~bmatrix { 10/36 &~ 13/36 &~ 13/36 ## 13/48 &~ 19 /48 &~ 16 / 48## 13 / 48 &~ 16/ 48 &~ 19 /48 }]	(5-11)

와 같이 계산되고, 이를 정리하여 다음과 같이 쓸 수 있다.

[eqn: Gamma``^2 ~=~ 1 over 144 bmatrix {` 40 &~ 52 &~ 52` ## `39 &~ 57 &~ 48` ## `39 &~ 48 &~ 57` }]	(5-12)

이제 식(5-8)의 벡터를 식(5-12)의 행렬에 곱하면 차차기상태의 확률분포를 얻을 수 있을 것이다.

그러나 여기서 차차기상태의 확률분포를 계산하는 것보다 더욱 중요한 일은 식(5-7)에 주어진 원래의 천이행렬 □와 이를 제곱하여 얻은 식(5-12)의 행렬 □2을 서로 비교하는 일이다.  행렬 □2을 자세히 살펴보면, 각 원소들의 변화가 원래의 천이행렬 □에 비하여 완만해졌음을 알 수 있다. 다시 말해서 원래의 천이행렬은 최소 원소에 대한 최대 원소의 비가 2 인 반면에, 제곱하여 얻은 행렬에서는 57/40 로 감소되었다는 것이다.

만일 그 이후의 상태에 대한 확률분포를 얻기 위하여 식(5-12)의 행렬에 다시 원래의 행렬을 곱한다면, 새로이 얻어지는 행렬의 원소들은 더욱 작은 변화를 갖게 될 것으로 예측할 수 있다.

원래의 천이행렬을 연속적으로 곱해 나가면

[eqn: Gamma `, ~ Gamma`^2 , ~Gamma`^3 , ~cdots , Gamma`^n , ~cdots]	(5-13)

와 같은 행렬의 수열(sequence of matrix)을 얻을 수 있다. 일반적으로 식(5-13)의 행렬들은 그 차수(powers)가 증가할수록 행렬 내의 각 원소들 사이의 변화량이 점차 감소하여 궁극적으로 하나의 한계행렬에 수렴하게 된다.

식(5-13)에 표시된 행렬들의 공통적인 성질을 다음과 같이 정리해 두고자 한다.

1. 만일 원래의 천이행렬 □ 가 (m × m) 행렬이면, 수열 내의 임의 행렬 □n 도 (m × m) 행렬이다.

2. 행렬의 차수 n 이 증가할수록, 각 원소의 변화량은 감소한다.

3. 행렬 □n 의 임의 행(row)을 더하면 정확히 1 이 된다.

처음 두 가지 성질은 지금까지의 진행 과정에서 이미 충분히 설명되었다고 본다. 세번째 성질은 다음과 같이 입증될 수 있다.

먼저 식(5-6)과 식(5-7)을 비교하여 보면, 원래의 천이행렬 □의 각 행은 동일한 조건을 가지는 모든 조건확률을 포함하고 있으므로 그 합은 명백히 1 이다. 이제 이와 같은 두 행렬의 곱으로 주어지는 새로운 행렬에 대하여 살펴보자. 각 행의 합이 1 인 두 행렬을 각각 □, □' 이라 하고, 이들의 곱으로 나타나는 행렬을 □'' 이라 하면,

[eqn: & Gamma ~=~ left[` t_{i`k} `right], ~ i`=`1,`2, `cdots,`q ,~k`=`1,`2,` cdots,` q # &~~~~~~~sum_k=1^q `t_{i`k} ``=``1 ``, ~for ~\all ~i ## & Gamma ``' ~=~ left[` t``'_kj `right], ~ k`=`1,`2, `cdots,`q ,~j`=`1,`2,` cdots,` q # &~~~~~~~sum_j=1^q `t``'_kj ```=``1 ``, ~for ~\all ~k ## \&~ &Gamma ``'' `=`` Gamma cdot Gamma ``' `=`` left[` t``''_ij `right], ~ i`=`1,`2, `cdots,`q ,~j`=`1,`2,` cdots,` q]	(5-14)

와 같이 쓸 수 있다. 행렬의 곱에 관한 규칙에 따라 □'' 의 각 원소는 다음과 같이 주어진다.

[eqn: t``''_ij ~=~sum_k=1^q `t_{i`k} `` t`'_kj ~,~ i`=`1,`2, `cdots,`q ,~j`=`1,`2,` cdots,` q]	(5-15)

그러므로 □'' 의 각 행의 합은

[eqn: sum_j=1^q `t``''_ij ~=` sum_j=1^q sum_k=1^q `t_{i`k} `` t`'_kj ~=` sum_k=1^q t_{i`k} ```sum_j=1^q ` t`'_kj ~=~ 1 ,~ for~ \all ~i]	(5-16)

로 계산된다. 따라서 식(5-13)의 모든 행렬은 임의의 행의 합이 1 이다.

위에서 밝혀진 바와 같이, 주어진 천이행렬을 연속적으로 곱해 나가면 한계행렬에 수렴하게 되며 원소들 사이의 변화는 점차 감소하여, 결국 한계행렬에 의하여 계산되는 차기상태는 현재상태와 일치하게 될 것이다.

이러한 관점에서, 현재상태의 확률분포와 차기상태의 확률분포가 일치하게 되는 확률분포를 평형조건(equilibrium condition) 혹은 평형분포(euqilibrium distribution)이라 한다. 예를 들어서 식(5-7)로 주어진 천이행렬에 대하여 평형조건을 구하기 위해서는

[eqn: bmatrix {p(a) ~``p(b) ~`` p(c) `} bmatrix { 1/3 & 1/3 & 1/3 ## 1/4 & 1 /2 & 1 / 4## 1 / 4 & 1/ 4 & 1 / 2 } ~=~ bmatrix {p(a) ~``p(b) ~ ``p(c) `}]	(5-17)

와 같은 행렬방정식을 세워야 할 것이다. 이 행렬방정식을 풀어서 선형 연립방정식의 형태로 쓰면

[eqn: & 1 over 3 `p(a) ``+`` 1 over 4 `p(b) ``+`` 1 over 4 `p(c) ~=~ p(a) ## & 1 over 3 `p(a) ``+`` 1 over 2 `p(b) ``+`` 1 over 4 `p(c) ~=~ p(b) ## & 1 over 3 `p(a) ``+`` 1 over 4 `p(b) ``+`` 1 over 2 `p(c) ~=~ p(c)]	(5-18)

로 된다. 일반적으로 이러한 3 원 선형 연립방정식이 유일한 해를 갖기 위해서는 세 개의 방정식이 모두 선형독립(linearly independent)이어야 한다. 그러나 식(5-18)의 선형 연립방정식은 이와 같은 선형독립 조건을 만족하지 않는다. 따라서 이들 만으로는 유일한 해를 구할 수 없다. 그러나 우리는 확률분포의 기본조건

[eqn: p(a) ```／``` p(b) ``` ／``` p(c) ~=~ 1]	(5-19)

을 알고 있으므로, 식(5-18)에서 임의로 두 개의 방정식을 택하고 식(5-19)의 방정식을 연립하여 풀면 다음과 같이 유일한 해를 얻을 수 있다.

[eqn: p(a) ~=`` 3 over 11 , ~p(b) ~ =`` p(c) ~=`` 4 over 11]	(5-20)

이 확률들은 식(5-7)로 주어진 천이행렬에 대한 평형분포이다.

일반적으로 유한한 상태를 갖는 Markov 과정에 대하여 평형분포는 유일하게 결정되며, 임의의 확률분포로부터 시작하여 식(5-7)로 주어진 천이행렬에 의하여 연속적으로 차기상태들을 구해 간다면 궁극적으로 식(5-20)의 확률분포에 도달하게 될 것이다. 이것이 평형분포의 의미이다.

Huffman 코딩에 있어서 Markov 과정을 적용하면, 각 심볼의 독립적인 발생확률 뿐만 아니라 심볼 상호간의 상관관계까지 고려할 수 있으므로 더욱 효율적인 코드체계를 구성할 수 있다. Markov 과정에 있어서 각 상태는 일정한 조건확률을 가지고 다른 상태로 천이하게 되므로, 각각의 상태로부터 천이되는 조건확률에 따라 Huffman 방법을 적용할 수 있다. 이 때, 각 상태에 대한 천이확률들이 서로 얼마나 다르냐에 따라 이득의 크기가 결정된다.

식(5-6)에 주어진 Markov 과정에 대하여 Huffman 방법을 적용하여 보자.

전상태(previous state)가 a 인 경우에 대하여, 현재상태(present state)의 Huffman 코드는 다음과 같이 구성된다.

[eqn: &a``Ａ``1 ~~&p_a ``Ａ`` 1 over 3## &b``Ａ``0`0 ~~&p_b ``Ａ`` 1 over 3## &c``Ａ``0`1 ~~&p_c ``Ａ`` 1 over 3 ~~~~L_a ``Ａ`` 5 over 3]	(5-21)

여기서 La 는 전상태가 a 인 경우에 대한 Huffamn 코드의 평균 코드길이를 계산한 것이다.

전상태가 b 인 경우, 현재상태의 Huffman 코드와 그 때의 평균 코드길이는 다음과 같다.

[eqn: &b``Ａ``1 ~~&p_b ``Ａ`` 1 over 2## &a``Ａ``0`0 ~~&p_a ``Ａ`` 1 over 4## &c``Ａ``0`1 ~~&p_c ``Ａ`` 1 over 4 ~~~~L_b ``Ａ`` 3 over 2]	(5-22)

마지막으로, 전상태가 c 인 경우, 현재상태의 Huffman 코드와 그 때의 평균코드길이는 다음과 같다.

[eqn: &c``Ａ``1 ~~&p_c ``Ａ`` 1 over 2 ## &a``Ａ``0`0 ~~&p_a ``Ａ`` 1 over 4 ## &b``Ａ``0`1 ~~&p_b ``Ａ`` 1 over 4 ~~~~L_c ``Ａ`` 3 over 2]	(5-23)

따라서 식(5-20)을 이용하여 평형상태에서의 평균 코드길이를 구하면

[eqn: L_M ~Ａ`` 3 OVER 11 `L_a ```／``` 4 over 11 `L_b ```／``` 4 over 11 `L_c ~Ａ~ 17 over 11]	(5-24)

을 얻는다.

다음으로 각 상태 a, b, c 에 대한 독립적인 발생확률 만을 사용하여 Huffman 코드를 작성하여 보자. 이 때, 위에서 유도하였던 Markov 과정을 이용한 코드체계와 비교하기 위해서는 각 심볼의 발생확률을 평형분포로부터 얻어 처리하는 것이 가장 합리적인 방법이다. 따라서 Huffman 코딩의 결과는

[eqn: &b``Ａ``1 ~~&p_b ``Ａ`` 4 over 11## &c``Ａ``0`0 ~~&p_c ``Ａ`` 4 over 11 ## &a``Ａ``0`1 ~~&p_a ``Ａ`` 3 over 11]	(5-25)

와 같이 나타난다. 이에 대한 평균 코드길이는

[eqn: L_H ~Ａ~ 3 OVER 11 ×` 2 ``／`` 4 over 11 ×` 2 ``／`` 4 over 11 ×` 1 ~Ａ~ 18 over 11]	(5-26)

로 계산된다.

따라서 Markov 과정을 이용하여 인코딩된 코드체계의 평균 코드길이 LM (5-24)은 독립적인 발생확률 만을 이용하여 얻은 코드체계의 평균 코드길이 LH (5-26)에 비하여 짧다. 다시 말해서 Markov 과정을 이용하면 독립적인 발생확률 만을 이용하는 것보다 효율적인 코드체계를 생산한다는 것이다. 이를 식으로 표현하면

[eqn: L_M ~Ａ~ 17 OVER 11 ~＠~ 18 over 11 ~Ａ~ L_H]	(5-27)

와 같이 나타난다.

예상했던 바와 같이, Huffman 코딩 과정에 있어서 Markov 과정을 적용하면 코드체계의 평균 코드길이가 감소한다. 그러나 이 예에서는 소스알파벳의 심볼 수가 매우 적고 이웃한 심볼 사이의 상관관계를 1-차 Markov 과정으로 적용하였으므로 효율성의 향상은 그리 두드러지지 않는다. 만일 소스알파벳의 심볼 수가 증가하고 그들의 천이확률이 크게 변화하며 여러 개의 이웃한 심볼 사이의 상관관계를 부여하는 고차 Markov 과정을 적용하면 코드체계의 효율성은 더욱 향상될 것이다.

[예제 1] 1-차 Markov 과정의 천이확률들이 다음과 같이 주어졌다.

[eqn: &P`(a vert a) ``=`` 3/ 4 ~~~~ &P`(b vert a) ``=`` 1/ 8 ~~~~ &P`(c vert a) ``=`` 1 / 8 ## &P`(a vert b) ``=`` 1 /4 ~~~~ &P`(b vert b) ``=`` 1 / 2 ~~~~ &P`(c vert b) ``=`` 1 / 4 ## &P`(a vert c) ``=`` 1 /4 ~~~~ &P`(b vert c) ``=`` 1 / 4 ~~~~ &P`(c vert c) ``=`` 1 / 2]

(1) 천이행렬을 구하고 천이그래프를 그려라.

(2) 평형분포를 구하라.

(3) Markov 과정을 이용하여 Huffman 방식으로 인코딩하고, 그 결과로 얻어진 코드체계의 평균 코드길이 LM 을 구하라.

(4) 평형상태에서 순수한 Huffman 방식으로 인코딩하고, 그 결과로 얻어진 코드체계의 평균 코드길이 LH 를 구하라.

(5) 위 (3)과 (4)에서 구해진 평균 코드길이를 식(5-27)과 비교하여 Markov 효과를 설명하라.

[풀이]

(1) [eqn: bmatrix { 3/4 ~~ 1/8 ~~ 1/8 ## 1/4 ~~ 1/2 ~~ 1/4 ## 1/4 ~~ 1/4 ~~ 1/2 }]                       (그림 들어갈 자리임)

(2) 평형상태에서 행렬방정식은

[eqn: bmatrix { p(a) & ~p(b) & p(c) } bmatrix { 3/4 &~ 1/8 &~ 1/8 # 1/4 &~ 1/2 &~ 1/4 # 1/4 &~ 1/4 &~ 1/2 } ~=~bmatrix { p(a) & ~p(b) & ~p(c) }]

와 같이 나타나고, 이를 선형 연립방정식으로 표현하면 다음과 같다.

[eqn: cases{ 3 over 4 p(a) ``+`` 1 over 4 p(b) ``+`` 1 over 4 p(c) ~=~ p(a) ~~cdots~~① ## 1 over 8 p(a) ``+`` 1 over 2 p(b) ``+`` 1 over 4 p(c) ~=~ p(b) ~~cdots~~② ## 1 over 8 p(a) ``+`` 1 over 4 p(b) ``+`` 1 over 2 p(c) ~=~ p(c) ~~cdots~~③ }]

이들 중 처음 두 방정식 ①, ②와 일반적인 확률분포의 조건

[eqn: p(a) ``+`` p(b) ``+`` p(c) ~ =~ 1]

을 연립하여 풀면, 다음과 같은 평형분포를 얻는다.

[eqn: p(a) ``=`` 1 over 2 , ~~ p(b) ``=`` p(c) ``=`` 1 over 4]

(3)   <전상태가 □a□ 인 경우>     <전상태가 □b□ 인 경우>    <전상태가 □c□ 인 경우>

[eqn: & a ``=`` 0 ~~ & p_a `=` 3/4 ~~~~&b ``=`` 1 ~~& p_b `=` 1/2 ~~~~&c ``=`` 1 ~~&p_c `=` 1/2 # &b ``=`` 1`0 ~~ &p_b `=` 1/8 &a ``=`` 0`0 &p_a `=` 1/4 &a ``=`` 0`0 &p_a `=` 1/4 # &c ``=`` 1`1 ~~ &p_c `=` 1/8 &c ``=`` 0`1 &p_c `=` 1/4 &b ``=`` 0`1 &p_b `=` 1/4 # &L_a ``=`` 5 over 4 & &L_b ``=`` 3 over 2 & &L_c ``=`` 3 over 2]

따라서 평형상태에서는 평균 코드길이는

[eqn: L_M ~=~ 1 over 2 `L_a ``+`` 1 over 4 `L_b ``+`` 1 over 4 `L_c ~=~ 11 over 8]

와 같이 계산된다.

(4) 평형상태에서 순수 Huffman 방식으로 코딩하면

[eqn: &a ``=`` 1 ~~~ &p_a ``=`` 1/2 # &b ``=`` 0`0 & p_b ``=``` 1/4 # &c ``=`` 0`1 &p_c ``=``` 1/4]

와 같이 나타나고, 이 때의 평균 코드길이는

[eqn: L_H ~=~ 1 over 2 cdot 1 ``+`` 1 over 4 cdot 2 ``+`` 1 over 4 cdot 2 ~=`` 12 over 8]

로 계산된다.

(5) 따라서 [eqn: L_M]과 [eqn: L_H]의 관계는

[eqn: L_M ~=~ 11 over 8 ~ ＠ ~ 12 over 8 ~=~ L_H]

와 같이 주어진다. 이는 식(5-27) 보다 Markov 과정에 의한 효율성의 향상이 더 크게 나타난 경우에 해당하며, 그 이유는 이 예제에 주어진 천이확률들이 식(5-6)으로 주어진 본문의 예보다 더 큰 확률차를 갖기 때문이다.

5-3  예측형 Run-length 코딩시스템

우리는 지금까지 소스알파벳의 확률구조가 코드체계의 평균 코드길이를 감소시키는  데 어떠한 역할을 하는 지에 대하여 조사하여 왔다. 심볼들의 독립적인 발생확률은 순수한 Huffman 과정에 의한 코드체계를 설계하는 데 사용될 수 있으며, 이보다 더 복잡한 확률구조인 Markov 과정은 심볼 사이의 상관관계를 고려하는 코드체계의 설계에 이용하였다.

그러나 인코딩된 데이타의 양을 축소시키는 소스코딩의 방법에는 단지 이들 두 가지만 존재하는 것이 아니고, 메시지의 확률구조에 따라 매우 다양한 방법들이 제시되어 있는 바, 이 한 권의 책에 이들 모두를 상세히 다루는 것은 불가능하다. 그 중에서도 특히 오늘날의 자료압축 방법으로 가장 널리 사용되고 있는 Run-length 코딩시스템은 압축 효과가 뛰어날 뿐 아니라 그 시스템의 구성도 비교적 간단하여 매우 다양한 응용 시스템들이 설계되어 있는 상태이다.

우리는 이들을 개별적으로 취급하는 대신, 가장 개념적이고 대표성 있는 형태를 택하여 상세히 검토함으로써 그 전반적인 원리를 설명하고자 하는 것이다.

먼저 우리가 사용하고자 하는 소스심볼들의 발생패턴(pattern of occurrence)을 인식하여 차기심볼(the next symbol)을 예측할 수 있는 예측기(predictor, S/W or H/W)가 설계되어 있다고 가정하자. 또한 이론을 간단하게 하기 위하여 이진 심볼(binary symbol)을 사용하기로 한다.

예측기를 이용하여 정보를 압축시켜 전송하는 예측형 Run-length 코딩시스템의 구성도를 그림 5-2에 제시하였다.

그림 5-2  예측형 Run-length 코딩시스템

이 시스템의 동작을 개괄적으로 설명하면 다음과 같다.

송신측의 입력으로 주어진 이진열 {Sn}은 □0□과 □1□이 고르게 섞여 있는 정보데이터이다. 앞에서 언급한 바와 같이, 예측기의 기능은 이미 진행된 이진열(binary sequence)의 발생패턴을 검토하여 다음에 발생할 이진수를 예측해 내는 것이다. 만일 그 예측이 맞으면(success) 예측형 인코더(predictive encoder)는 □0□을 출력하고, 예측이 틀리면(fail) 예측형 인코더는 □1□을 출력한다. 따라서 사용된 예측기가 수용할 만한 성능을 가지고 있다면, 예측형 인코더의 출력 {En}은 연속되는 □0□의 나열(zero run) 속에 가끔 □1□이 섞여 나타나는 새로운 이진열이 될 것으로 예상할 수 있다. 이 때, 예측기의 성능의 우수할수록 □0□-열의 길이(run-length)는 길어진다.

이진열 {Sn}과 {En}은 동일한 길이를 갖게 되지만 그 발생패턴은 완전히 달라진다. 만일 정보데이터 {Sn}이 100(bits) 입력되었다면, 예측형 인코더의 출력 {En}도 100(bits)발생한다. 그러나 {Sn}은 □0□과 □1□이 고르게 분포하는 랜덤이진열(random binary sequence)인 반면, {En}은 주로 □0□이 연속되고 그 사이에 드물게 □1□이 나타나는 새로운 패턴의 이진열이 됨을 알 수 있다. 물론 그 □0□과 □1□의 분포는 사용된 예측기의 성능에 따라 달라진다. 그림 5-3에는 설계된 예측형 인코더의 일 예를 제시하였다.

그림 5-3  예측형 인코더 (예)

그림에서 예측기는 그 내부의 설계를 상세히 제시하지 않았으나, 입력심볼을 대다수 정확히 예측하고 있다는 가정 하에서 이루어 진다. 예측기는 입력 이진열 {Sn}에 대하여 예측된 이진열 {Pn}을 발생시킨다. 따라서 예측형 인코더의 출력 이진열 {En}은 예측심볼 Pn이 입력심볼 Sn과 같을 경우(success) □0□으로, 다를 경우(fail) □1□로 나타나게 된다. 다시 말해서 예측기가 올바른 예측(good prediction)을 한 경우에는 EnＡ0, 잘못된 예측(wrong prediction)을 한 경우에는 EnＡ1이 되는 것이다. 또한 예측기는 오차 {En}을 취하여 메시지의 발생패턴을 파악하고, 이에 따라 자신을 수정함으로써 다음의 예측심볼을 결정하게 되는 것이다.

.  제5-1절의 각주 1을 참고하라.

그림 5-3으로부터 예측형 인코더의 출력은 다음과 같이 나타낼 수 있다.

[eqn: E_n ~=~ S_n ~□~ P_n ~,~~ n `=`1,`2,`3, cdots]	(5-28)

앞에서 설명한 것처럼 예측기의 성능이 우수하다면 □0□의 나열(zero run)은 길게 나타나고 □1□은 드물게 나타난다. 최악 예측기는 랜덤예측기(random predictor)라 할 수 있는데, 이는 소스심볼의 발생패턴에 관계없이 □0□과 □1□을 무작위로 발생시키는 예측기를 말한다. 일반적으로 랜덤예측기가 하나의 심볼을 올바로 예측할 확률은 1/2 보다 크거나 같다. 만일 이것이 1/2 보다 작다면, 예측형 인코더의 출력에 보수(complement)를 취함으로써 이를 수정할 수 있을 것이다. 따라서 성능이 매우 열악한 예측기가 사용된다 하더라도, 예측형 인코더의 출력에서는 □1□ 보다는 □0□이 많이 발생한다는 것이다.

한편 수신측의 예측형 디코더(predictive decoder)는 예측형 인코더의 출력 {En}으로부터 원래의 메시지 {Sn}을 복원하도록 설계된 장치이다. 그림 5-3과 같은 예측형 인코더에 대응하는 예측형 디코더의 형태를 그림 5-4에 제시하였다.

그림 5-4  예측형 디코더 (예)

여기서 사용된 예측기(predictor)는 그림 5-3의 예측형 인코더에서 사용된 것과 정확히 동일한 장치라고 가정한다. 만일 Run-length 인코더 및 Run-length 디코더가 정상적으로 동작하고 채널에서 오류가 발생하지 않았다고 가정한다면, 예측형 디코더의 입력[eqn: \{hat{ E}_n `\}]은 예측형 인코더의 출력[eqn: \{ E_n \}]과 동일한 이진열이 될 것이다. 이들 두 예측기가 동시에 동작하기 시작한다면, 이들은 동일한 입력을 갖는 동일한 장치이므로 그 출력도 동일한 예측심볼을 발생시키게 될 것이다. 따라서 예측기의 출력은

[eqn: hat P_n ~=`` P_n ,~ if ~ hat E_n ``=`` E_n ~for ~\all ~ n]	(5-29)

와 같은 관계를 만족한다. 이에 따라 예측형 디코더의 출력은 식(5-28)을 이용하여 다음과 같이 산출된다.

[eqn: hat S_n &Ａ~ hat P_n ~□~ hat E_n ~=~ P_n ~□~ E_n ## &Ａ~ P_n ~□~ (S_n ~□~ P_n`) ## &Ａ~ S_n ``, ~~~ for ~ \all ~ n]	(5-30)

그러므로 Run-length 인코더/디코더가 정상적으로 동작하고 채널 상에서 오류가 발생되지 않았다면, 예측형 디코더는 원래의 메시지를 정확히 복원함을 알 수 있다.

이제 남아있는 문제는 예측형 인코더의 출력 {En}을 압축하여 채널을 통하여 전송하는 Run-length 인코더와 채널을 통과한 신호를 받아 {En}을 재생하여 예측형 디코더에 공급하는 Run-length 디코더의 동작을 설명하는 일이다.

먼저 Run-length 인코더는 이진열 {En}의 □0□-열의 길이(run-length) 만을 블록코드(block code)로 인코딩한다. 이 때, 반드시 블록코드를 사용해야 하는 것은 아니지만 개념을 간단하게 하기 위하여 블록코드로 가정한 것이다. 그림 5-5는 k-bit 블록코드를 사용하는 Run-length 인코더의 개념도를 나타내고 있다.

그림 5-5  Run-length 인코더의 구성 (예)

앞에서 설명한 바와 같이, Run-length 인코더의 입력 {En}은 주로 □0□이 계속되다가 가끔 □1□이 나타나는 형태의 이진열이다. 따라서 Run-length 인코더는 먼저 연속되는 □0□의 길이를 측정하여 이른바 □run-length□를 구하여야 한다. 이는 하나의 □1□이 나타나기 바로 전까지 단순히 □0□의 수를 세는(counting) 동작이며, 생성된 □run-length□에 따라 k-bit 블록코드를 만들어 전송하면 되는 것이다. 입력 {En}의 □run-length□에 따른 블록의 수는 다음과 같다.

[eqn: & □ \run □ \length□ ~:~~~~~~0 ~~~ ``∼~```(2^k `-`1)`-`1 ~&□~~ \#~ \of ~\blocks ``=``1 # & □ \run □ \length□ ~:~```(2^k `-`1) ~ ∼~ 2(2^k `-`1)`-`1 ~&□~~ \#~ \of ~\blocks ``=``2 # & □ \run □ \length□ ~:```2(2^k `-`1) ~ ∼~` 3(2^k `-`1)`-`1 ~&□~~ \#~ \of ~\blocks ``=``3# &~~~``~~~~~~~~~~~~~~~~~~~~~□]

여기서 하나의 블록에 의하여 표현할 수 있는 □run-length□를 0 ∼ (2k - 1) - 1 로 설정한 것은 뒤에서 설명하게 될 Run-length 디코더의 알고리듬을 간단하게 하기 위함이다. 예를 들어서 4-bit 블록코드를 사용한다고 가정할 때, □run-length□ 14, 15, 16은 각각 1 블록, 2 블록, 2 블록을 사용하여 다음과 같이 인코딩된다.

[eqn: □ \run □ \length□ ``=``14 ~~ □]  1-블록

1	1	1	0

[eqn: □ \run □ \length□ ``=``15 ~~ □]  2-블록

1	1	1	1

0	0	0	0

[eqn: □ \run □ \length□ ``=``16 ~~ □]  2-블록

1	1	1	1

0	0	0	0

결국 Run-length 인코더는 블록코드의 형태로 채널 상에 정보를 전송하게 됨으로 여기에 Hamming 코드와 같은 오류제어코드를 적용하여도 무방하다. 또한 이와 같은 전략은 시스템의 특성 상 매우 필요한 조치라 할 수 있다. 이 시스템에 있어서 하나의 k-bit 블록코드는 실제로 최대 (2k - 1) 개의 bits를 표현하고 있으므로, 만일 전송 중에 블록 내의 1 bit에서 오류가 발생되면 수신측에서는 여러 bits의 정보를 한꺼번에 잃게 되거나 불필요한 정보가 추가될 가능성도 있는 것이다. 오류제어 체계를 이 시스템에 도입한다면, Run-length 인코더 다음에 오류제어 인코더를, Run-length 디코더 앞에 오류제어 디코더를 각각 설치하여야 한다.

한편, Run-length 디코더는 채널로부터 받은 블록코드에 의하여 이진열 {En}을 재생한다. 그림 5-6은 이러한 Run-length 디코더의 구성을 도시한 것으로서 그림 5-5에 주어진 인코더에 대응하는 장치이다.

그림 5-6  Run-length 디코더의 구성 (예)

위의 Run-length 인코더에서 정한 블록코드의 생성규칙에 따라, Run-length 디코더의 블록코드 해석기는 하나의 블록을 □0 인 경우□, □[1, 2k-2] 사이의 값인 경우□, □2k-1 인 경우□ 등 세 가지로 구분하여 이진수 발생기로 보내준다. 이에 대하여 이진수 발생기는 다음과 같은 알고리듬에 의하여 {En}을 재생하게 된다.

0 인 경우 : 하나의 □1□ 만 발생한다.

[1, 2k-2] 사이의 값인 경우 : 해당 갯수의 □0□을 발생하고 하나의 □1□을 발생한다.

2k-1 인 경우 : 2k-1 개의 □0□을 발생한다. (□1□은 발생하지 않는다.)

만일 채널 상의 오류가 없다고 가정하면, Run-length 디코더의 출력은

[eqn: hat E_n ~=`` E_n~ , ~for ~\all ~ n]	(5-31)

로 되어, 최종적으로 예측형 디코더는 식(5-30)에 따라 원래의 메시지를 완벽하게 재생할 수 있게 된다.

이제, 지금까지 설명한 Run-length 코딩시스템의 자료압축 효과를 검토하여 보자. 이 시스템의 자료압축 효과(혹은 효율성)를 정량적으로 분석하기 위해서는 예측기(predictor)의 확률모델(probabilistic model)을 필요로 한다. 실제적인 예측기 알고리듬의 확률구조는 매우 복잡한 것이 사실이나, 여기서는 개념의 단순화를 위하여 예측기의 예측능력 만을 고려하기로 한다.

예측기가 하나의 메시지 bit를 올바로 예측할 확률을 p 라 하고, 각 bit에 대한 예측은 다른 bit에 상관없이 독립적으로 수행된다고 가정하자. 그러면 하나의 메시지 bit에 대하여 잘못 예측할 확률은 명백히 qＡ1１p 가 된다. 이를 예측형 인코더의 출력 {En}과 관련지어 나타내면

[eqn: & p ~=`` Pr \{` \good ~prediction \} ~=`` P \{E_n `=`0 \} ## & q ~=`` Pr \{` \wrong ~prediction \} ~=`` P \{E_n `=`1 \} ~=~ 1 ``-`` p]	(5-32)

와 같이 쓸 수 있다. 또한 앞에서 설명한 바와 같이, 일반적인 예측기에 대하여 p □ 1/2 라고 가정할 수 있다.

여기서 한가지 주의해야 할 사항은 확률 p 혹은 q 를 채널 상에서 발생하는 오류확률과 혼동해서는 않된다는 점이다. 이들은 오로지 예측기의 성능에만 관계하는 것으로 채널과는 무관하다. 요컨대 확률 p 가 클수록 성능이 우수한 예측기이며, 확률 p 가 1/2 에 접근할수록 랜덤예측기에 비교되는 열악한 예측기이다.

위의 가정으로부터 Run-length가 정확히 n 이 될 확률은

[eqn: p`(n`) ~Ａ~ p^n `q , ~n ``Ａ``0, ``1, ``2, ``cdots]	(5-33)

와 같이 표시된다. 이진열 {En}에 있어서 모든 □0□의 나열은 하나의 □1□이 나타남으로써 끝나게 됨으로, 식(5-33)은 결국 n 개의 □0□이 나타나고 이어서 하나의 □1□이 나타날 확률과 같다.

식(5-33)을 모든 n(Run-length)에 대하여 합하면

[eqn: sum_n=0^inf `p(n)~=`` sum_n=0^inf `p^n `q ~=`` q sum_nＡ0^inf `p^n ~=~ q over {1``-``p} ~=~ 1]	(5-34)

와 같이 계산됨으로 p(n)은 하나의 확률분포라 할 수 있다.

이제 이진열 {En}은 그림 5-5에 주어진 Run-length 인코더에 의하여 의하여 k-bit 블록코드로 인코딩되어 전송된다. 앞에서 우리는 각각의 Run-length에 따른 블록의 수를 계산하였다. 각 블록은 k-bit를 표시함으로, Run-length에 따른 블록의 수와 전송되는 bit 수를 관련지어 나타내면 다음 표와 같다.

Run-length	전송되는 블록의 수	전송되는 bit 수
[eqn: 0 ~□~ n ~□ ~(2^k `-` 1`) ``-``1]	1	k
[eqn: (2^k `-`1`) ~□~ n ~□~ 2`(2^k `-` 1`) ``-``1]	2	2k
[eqn: 2`(2^k `-`1`) ~□ ~n~ □~ 3`(2^k `-` 1`) ``-``1]	3	3k
□	□	□

계산의 편의를 위하여

[eqn: 2^k ``-`` 1 ~=```m]	(5-35)

이라 두고, 전송되는 bit 수의 평균값을 구하면 다음과 같이 계산된다.

[eqn: L_RL &=`` sum_n=0^inf `p_n `l_n ## &=`` \{`p`(0) `／` p`(1) `／` cdots `／` p`(m`-`1) \}`` k ## &```／ \{`p`(m) `／` p`(m`／`1) `／` cdots `／` p`(2m`-`1) \}``2`k ## &```／ \{`p`(2m) `／` p`(2m`／`1) `／` cdots `／` p`(3m`-`1) \}``3`k ## &```／` cdot cdot cdot]	(5-36)

여기에  식(5-33)을 대입하여 정리하면

[eqn: L_RL ~=~ (1``-``p^m ) ` (1``／`` 2`p^m ``／`` 3`p^2m ``／`` cdots `)``k]	(5-37)

와 같이 나타난다. 여기서 두 번째 괄호 내에 들어있는 무한수열의 합은 다음과 같은 등식을 이용하여 계산할 수 있다.

[eqn: 1``／``2`x ``／`` 3`x^2 ``／`` cdots ~=~ 1 over {(1`-`x`)^2}]	(5-38)

그 계산의 결과는 다음과 같이 정리된다.

[eqn: L_RL ~=~ k over {1`-`p^m}]	(5-39)

여기에 다시 식(5-35)를 대입하면

[eqn: L_RL ~=~ k over {1``-``p^{ (2^k`-`1 )} }]	(5-40)

을 얻는다.

이 식은 우리가 그림 5-2에 도시된 것과 같은 Run-length 코딩시스템을 사용하였을 때 얻을 수 있는 전송 bit 수의 평균값이다. 그렇다면 이러한 Run-length 코딩시스템을 사용하지 않고 원래의 정보 {Sn}을 그대로 전송한다면 전송 bit 수의 평균값은 얼마로 계산되겠는가 ?  다시 말해서 Run-length 코딩시스템의 효율성을 검토하기 위하여 식(5-40)과 비교할 대상을 무엇이냐는 것이다.

앞에서 설명한 바와 같이, 원래의 정보 {Sn}과 예측형 인코더의 출력 {En}의 길이는 동일하며, 식(5-40)은 {En}의 Run-length／1(연속된 □0□과 하나의 □1□)에 대하여 계산된 전송 bit 수의 평균값이므로, 결국 이 식과 비교해야 할 대상은 (n ／ 1)의 평균값이 될 것이다. 이는 다음과 같이 쉽게 계산된다.

[eqn: L_P ~=&sum_n=0^inf `p(n)` (n`+`1) ~=~ sum_n=0^inf `p^n q`` (n `+` 1) ## =& q `sum_n=0^inf `p^n ``(n `+` 1) ~=~ 1 over {1`-`p} ~=~ 1 over q]	(5-41)

이제, 식(5-40)은 그림 5-2의 Run-length 코딩시스템을 사용한 경우에 전송해야 하는 bit 수의 평균값이며, 식(5-41)은 원래의 정보를 그대로 전송해야 하는 경우의 평균값이다. 따라서 우리는 이 두 식을 비교함으로써 이른바 Run-length 코딩시스템의 효율성을 판단할 수 있게 되었다. 식(5-40)은 블록코드의 길이 k와 예측확률 p에 따라서 변화하는 값이므로, 사용된 예측기의 성능에 따라 LRL 을 최소로 하는 k 값을 찾아 적용하여야 한다. 이 식으로부터 최적의 k를 구하기 위하여 p □ 0.5에 대한 값들을 구해보면 다음의 표 5-1을 얻을 수 있다.

표 5-1  Run-length 코딩시스템을 사용한 경우 [eqn: L_RL `=` k over {1`-`p^{(2^k `-`1)}}]

블록의 길이 k	예측기의 성능 p
	0.5	0.6	0.7	0.8	0.9	0.95	0.98	0.99
2 3 4 5 6 7 8 9 10	2.29 3.02 4.00	2.55 3.09 4.00	3.04 3.27 4.02 5.00	4.10 3.80 4.15 5.00 6.00	7.38 5.75 5.04 5.20 6.00	14.02 9.94 7.45 6.28 6.25 7.01 8.00	34.0 22.7 15.3 10.7 8.33 7.58 8.05 9.00	67.3 44.2 28.6 18.7 12.8 9.71 8.67 9.05 10.0

이 표에서 보는 바와 같이 식(5-40)은 k 값의 변화에 따라 처음엔 감소하다가 최소값에 도달하고 다시 증가하여 k 값에 접근하는 양상을 나타낸다. 따라서 우리는 식(5-40)이 최소값을 나타내는 블록코드의 길이 k 를 찾아 이를 그림 5-5의 Run-length 인코더에 적용하여야 할 것이다. 표 5-1에는 각각의 p에 대하여 식(5-40)의 값이 최소가 되는 경우에 밑줄을 그어 최적의 k를 쉽게 발견할 수 있도록 하였다.

이제 이들 k에 대한 식(5-40)의 값과 각 예측확률 p에 식(5-41)의 값을 비교하여 정리하면 다음의 표 5-2와 같이 나타난다. 여기서 압축율은 다음과 같은 식에 의하여 산출된 것이다.

[eqn: varupsilon ~=~ L_RL over L_P TIMES 100 ~(%)]	(5-42)

표 5-2  Run-length 코딩시스템의 효율성

예측기의 성능 p	최적 블록의 길이 k	전송 bit 수의 기대치 LRL	Run-length+1의 기대치 LP	압축율 □(%)
0.7 0.8 0.9 0.95 0.98 0.99	2 3 4 6 7 8	3.04 3.80 5.04 6.25 7.58 8.67	3.33 5.00 10.00 20.00 50.00 100.00	91.3 76.0 50.4 31.3 15.2 8.7

표 5-1 및 표 5-2 로부터 Run-length 코딩시스템의 효율성은 예측기의 성능을 나타내는 확률 p와 블록코드의 길이 k의 선택에 따라 크게 달라짐을 알 수 있다. 이들 중 블록코드의 길이 k는 최적으로 선택할 수 있는 값이므로 결국 시스템의 효율성은 예측기의 성능에 전적으로 의존하게 된다. 만일 성능이 우수한 예측기(p=0.98 혹은 p=0.99 등) 만 확보된다면, 우리는 그림 5-2와 같은 구성을 이용하여 데이터의 양을 거의 1/10 이하로 압축할 수 있는 자료압축 시스템(data compression system)을 구축할 수 있다.

[예제 2] 그림 5-2의 예측형 Run-length 코딩시스템에 있어서 예측기의 오류확률을 [eqn: q=0.15] 라 하고, 4-bit 블록코드를 사용하여 인코딩한다고 할 때

(1) 채널에 전송되는 bit 수의 기대값 [eqn: L_RL]을 구하라.

(2) (Run-length+1)의 기대값 [eqn: L_P]를 구하라.

(3) (Run-length+1)의 분산[eqn: Var(bold l_P )]을 구하라.

(4) 이 코딩시스템의 자료압축율 [eqn: varupsilon] 은 얼마인가 ?

[풀이]

(1) 식(5-40)을 이용하여

[eqn: L_RL ~=~ 4 over {1 ``-`` 0.85^{(16 `-` 1)}} ~simeq~ 4.383 ~~( \bits)]

(2) 식(5-41)을 이용하여

[eqn: L_P ~=~ 1 over 0.15 ~simeq~ 6.667 ~~( \bits )]

(3) 식(1-107) 및 식(1-108)을 이용하여

[eqn: Var `(bold l `) &=` sum_n=0^inf ` (n `+` 1 `-` L_P `)^2`` p(n) ~=` sum_n=0^inf ` (n`+`1`-`1 over q )^2 `` p^n `q ## &=``q `sum_n=0^inf `(n`+`1)^2 `p^n ``-`` 2 sum_n=0^inf `(n`+`1) `p^n ``+`` 1 over q^2 ## &=``q `{1`+`p} over { (1`-`p)^3} ``-`` 1 over q^2 ~=~ p over q^2 ~=~ 0.85 over 0.15^2 ~simeq~ 37.778]

(4) 위에서 구한 [eqn: L_RL] , [eqn: L_P] 및 식(5-42)를 이용하여

[eqn: varupsilon ~=~ L_RL over L_P `TIMES 100 ~=~ 4.383 over 6.667 ` TIMES 100 ~simeq~ 65.7``(%)]

로 각각 계산된다.

이 절에서 논의된 예측형 Run-length 코딩시스템은 자료압축을 위한 가장 기본적인 형태로서 이것이 모든 데이터에 대하여 적용된다고는 말할 수 없다. 또한 이 체계의 효율성(efficiency)은 사용되는 예측기(predictor)의 성능에 전적으로 의존하고 있으므로 압축율의 향상을 위해서는 오로지 우수한 예측기를 채택하는 방법 밖에 없다. 다시 말해서 그림 5-2에 제시된 시스템은 자료압축을 위한 개념적인 구성을 설명해 주기에는 충분하지만 융통성이 부족한 구조를 가지고 있다는 것이다. 실질적인 자료압축 시스템들은 이 보다 많은 융통성을 부여할 수 있도록 설계되어 있으며 그 구성도 매우 다양하게 제공되고 있다. 그러나 우리는 그림 5-2와 같은 시스템의 개념을 철저히 이해해 둠으로써 이들 실질적 시스템의 동작과 성능도 충분히 파악할 수 있다고 하겠다.

실질적인 자료압축 시스템에 있어서 우선적으로 고려되어야 할 사항은 압축하고자 하는 정보의 통계적 특성이다. 이에 따라 예측기의 선택도 달라지며 자료압축 시스템의 구성도 달라질 수 있는 것이다.

예측기가 수행해야 하는 기능은 오직 입력되는 심볼들의 흐름을 파악하여 차기심볼(the next symbol)을 예측하는 일이다. 따라서 예측기의 제작에 대한 이론적 제한성은 두지 않는다. 어떠한 방법으로 제작되더라도 차기심볼의 정확한 예측 만 가능하다면 이는 예측형 코딩시스템의 중요한 요소로 채택될 수 있는 것이다.

5-4  DPCM,ADPCM,DM,ADM

이웃한 심볼들 사이의 상관관계를 이용하여 실제로 전송되는 정보의 양을 축소하는 방법은 단지 문자정보와 같은 이산적 정보에만 적용될 수 있는 것이 아니라, 아날로그 신호로 구성된 정보를 이산신호 혹은 디지탈신호로 변환하여 전송하고자 하는 여러 가지 변조방식에 있어서도 널리 적용되고 있다. 이들 중 이 책의 주된 관심사인 정보공학과 깊은 관련성이 있는 변조방식으로는 DPCM(differential pulse code modulation), ADPCM(adaptive DPCM), DM(delta modulation) 및 ADM(adaptive DM) 등을 들 수 있다.

우리는 제2-3절에서 모든 신호를 연속신호, 이산신호, 디지탈신호로 분류하고, 자연 발생적인 연속신호를 표본화(sampling), 양자화(quantization) 및 코딩(coding) 과정을 거쳐 디지탈신호로 변환하는 과정을 설명한 바 있다(그림 2-4). 이것과 정확히 동일한 과정으로 연속신호를 디지탈신호로 변환하여 전송하는 변조방식을 PCM(pulse code modulation)이라 한다. 이는 오늘날의 디지탈통신이 이루어 지는 가장 기본적인 체계로서 제2-3절에서 설명한 표본화 정리(sampling theorem)의 지배를 받아, 연속신호를 디지탈신호로 변환하여 전송하고 이를 수신하여 다시 원래의 연속신호를 복원하는 방식으로 구성된다.

PCM에 있어서 각각의 표본(sample)은 독립적으로 양자화된다. 다시 말해서 인접한 표본들 사이의 상관관계는 고려하지 않고 단지 각 표본의 크기를 독립적으로 평가하여 가장 가까운 수준(level)으로 근사화하는 것이다. 만일 PCM의 양자화 과정에 예측기를 도입하여 인접한 표본 사이의 상관관계를 고려할 수 있도록 구성한다면 전송되는 코드의 효율성을 크게 향상시킬 수 있을 것이다.

PCM의 양자화기(quantizer)에 예측기를 도입하여 이웃한 표본들 사이의 상관관계를 고려함으로써 효율성을 개선한 변조방식을 DPCM이라 한다. 이는 그 효율성이 기존의 PCM 보다 월등하고 응용분야에 따른 융통성이 뛰어나므로 널리 사용되고 있는 변조방식이다. 그림 5-7은 하나의 선형 적응예측기(linear adaptive predictor)를 도입한 DPCM 방식의 양자화기를 예시하고 있다.

.  DPCM의 양자화기는 예측기의 구조에 따라 달라질 수 있다. 여기에 제시된 것은 가장 일반적으로 사용되는 형태로서 선형 적응예측기를 도입하여 구성한 것이다. 여기서 우리는 앞에서 논의된 Run-length 코딩시스템에서 사용된 것과는 다른 개념의 예측기를 볼 수 있는데, 전자의 예측기가 이진수 예측을 수행한다고 하면 후자는 표본의 크기를 예측한다고 볼 수 있다. 이러한 경우 일반적으로 사용되는 형태가 바로 선형 적응예측기이다. 제5-1절의 각주 1)을 보라.

그림 5-7  DPCM 방식의 양자화기

선형 적응예측기에 의한 예측표본 [eqn: \{hat x_n \}]은 M 개의 이전 입력표본으로부터 다음과 같은 관계식에 따라 산출된다.

[eqn: hat x_n ~=~ sum_i=1^M `a_i ```x_n-i `, ~n`=`1,`2,`3,` cdots]	(5-43)

여기서 ai 는 예측기의 특성을 나타내는 계수이다. 예측기는 자신의 특수한 알고리듬에 따라 계수 ai 를 조정함으로써 입력표본의 크기를 예측한다.

따라서 입력표본과 예측표본의 차[eqn: \{ e_n \}]은

[eqn: e_n ~=~ x_n ``-`` hat x_n `, ~ n``=``1,` 2,` 3,` cdots]	(5-44)

와 같이 산출되어 양자화기로 들어간다. 결국 양자화기는 입력표본들을 독립적으로 양자화하는 대신 입력표본과 예측표본의 차를 양자화하게 되는 것이다. 양자화된 출력표본[eqn: \{ y_n \}]은 여러 가지 방법으로 코딩되어 전송로에 보내진다.

만일 인접한 입력표본들의 상관관계가 크고 예측기의 계수가 적절히 선택된다면 DPCM은 PCM에 비하여 월등한 효율성을 갖게 될 것이다. 일반적으로 PCM에 대한 DPCM의 이득(gain)은 다음과 같이 주어진다.

.  일반적인 전력의 관점에서 우리는 이 식을 쉽게 이해할 수 있으나, 실질적으로 이 식의 산출은 매우 복잡한 과정에 의하여 이루어 진다. 신호대 양자화 잡음비(signal-to- quantization-noise ratio)의 관점에서 이 식을 산출하는 상세한 과정을 다음의 참고문헌에서 찾아 볼 수 있다.

R.W.Donaldson and D.Chan, □Analysis and Subjective Evaluation of Differential Pulse-Code Modulation in Voice Communication Systems□, IEEE Trans. Commun. Technol. COM-17, pp.10-19, 1969.

[eqn: G_DPCM ~=~ {E \{x_n^2 \}} over {E \{e_n^2 \} } ~=~ {E \{x_n^2 \}} over {E \{ (x_n `-` hat x_n )^2 \} }]	(5-45)

주지하는 바와 같이, 예측기의 성능이 아주 열악하지 않다면 보통의 연속신호에 대하여[eqn: \{ e_n \}]의 전력은[eqn: \{ x_n \}]의 전력에 비하여 매우 작게 주어질 것이며, 이에 따라 식(5-45)의 이득은 크게 증가한다.

일반적으로 DPCM은 천천히 변화하는 연속신호에 대하여 적용되었을 때 효율성의 향상을 기대할 수 있다. 만일 연속신호의 변화율이 시간에 따라 크게 달라지는 경우에 DPCM을 적용하게 되면, 복원된 신호에 피크오류(peak error)가 발생될 가능성이 많다. 이러한 피크오류를 극복하기 위해서는 그림 5-7에 주어진 시스템을 다소 수정해야 하는데, 여기에는 두 가지 방식이 알려져 있다. 그 하나는 양자화기의 양자화계단(quantization step)의 크기를 입력신호에 따라 적응적으로 변화시키는 방법이다. 즉, 입력신호가 천천히 변화하는 경우에는 양자화계단의 크기를 작게 하고, 입력신호가 급격히 변화하는 경우에는 양자화계단의 크기를 크게 하는 것이다. 사실 이와 같은 기술은 다음에 설명하게 될 ADM 변조에 있어서도 같은 개념으로 적용하게 된다.

피크오류를 극복하는 또 하나의 방법은 선형 적응예측기를 입력신호의 따라 적응적으로 변화시키는 것인데, 식(5-43)에 주어진 계수 ai 를 산출함에 있어서 예측표본의 변화를 최소화하도록 설정하는 방식 등이 주로 사용된다.

이와 같이 그림 5-7의 DPCM 방식을 수정하여 특수한 잡음에 대하여 적응하도록 설계된 것을 ADPCM(adaptive DPCM) 변조라 한다.

이 밖에도 DPCM을 근간으로 약간의 수정을 거쳐 설계되는 변조방식으로는 가변길이 DPCM(variable length DPCM)과 비동기 DPCM(asynchronous DPCM) 등을 들 수 있다. 가변길이 DPCM은 양자화된 출력표본을 Huffman 인코딩함으로써 평균 코드길이를 더욱 축소하고자 하는 방식이며, 비동기 DPCM은 식(5-43)의 예측에 적용되는 입력표본의 수 M 을 고정시키지 않고 {en}의 부호와 크기에 따라 비동기적으로 변화시킴으로써 예측의 정확성을 더욱 높이려는 방식이다. 이처럼 전송환경이나 자료의 특성에 따라 수정된 방식들이 다양하게 존재한다는 사실은 DPCM의 융통성이 매우 뛰어남을 말해 준다.

인접한 표본들 사이의 상관관계를 이용하는 또 하나의 변조방식으로 이른바 DM을 들 수 있다. 엄밀하게 말해서 DM은 1-bit 코드를 사용하는 DPCM의 특수한 경우라고 할 수 있으며, 여기에서는 입력표본을 그대로 전송하는 대신 현재의 표본과 바로 이전의 표본과의 차이 만을 1-bit로 인코딩하여 전송한다. 따라서 DM에 있어서는 예측기가 필요 없으며, 양자화 및 코딩 과정이 동시에 이루어 진다고 할 수 있다.

그림 5-8은 전형적인 DM 인코더의 구성도와 각 부분에서 나타나는 전형적인 신호 형태를 보여주고 있다.

입력신호 x(t)는 천천히 변화하는 연속신호이다. 이는 비교기(comparator)에 의하여 매 표본화순간(sampling instants) 마다 적분기(integrator)의 출력 [eqn: hat x(t)]와 비교된다. 따라서 B 점의 신호는 각 표본화순간에서

[eqn: x_B (t) ~=~ x(t) ``-`` hat x(t) `, ~ \at~ \sampling ~\points]	(5-46)

로 주어진다. 이는 극성 양자화기(polarity quantizer)에 의하여 그 부호(음양)에 따라 □1□ 혹은 □-1□의 값을 갖는 펄스열로 변환된다. 즉, 점 C에서의 신호는 다음과 같다.

그림 5-8  DM 변조방식

(a) 인코더의 구성도      (b) 각 부분의 신호 형태

[eqn: x_C (t) ~=~ {x(t) ``-`` hat x(t)} over {vert x(t)``-`` hat x(t) vert } ~=~ cases { ~~1 `, ~ & if ~x(t) `` >= `` hat x(t) ## -1`, ~& if ~x(t) `` <= `` hat x(t) }]	(5-47)

그림 5-8에 나타낸 바와 같이, C 점의 신호는 펄스발생기(pulse generator)의 신호와 곱해져서 출력신호 y(t) 를 형성하며, 이는 또한 적분기(integrator)의 입력이 된다. 적분기는 들어오는 펄스를 누적하고, 누적된 크기를 유지시켜 입력신호와 비교될 비교기의 입력을 형성시킨다. 이상의 내용을 종합하면 그림 5-8(b)에 도시된 신호형태를 이해할 수 있을 것이다.

한편 수신측의 디코더는 채널을 통하여 전송된 펄스를 받아 이를 누적시키고 저역통과여파기(low-pass filter)를 이용하여 신호를 □Smoothing□함으로써 원래의 연속신호를 재생한다. 그림 5-9는 전형적인 DM 디코더의 구성과 그 신호처리 과정을 도시한 것이다.

그림 5-9  DM 디코더의 구성도와 신호의 재생

이와 같이 DM은 비교적 간단한 구조로 각각의 입력표본을 오로지 1 bit로 인코딩하여 전송하므로 적당한 형태의 연속신호에 대해서는 탁월한 효율성을 나타낸다.

그림 5-8에 주어진 DM 인코더에 있어서 계단의 크기(step amplitude) □는 고정되어 있다. 이는 처리하고자 하는 연속신호의 평균변화율에 따라 정해진 값으로서 양자화잡음(quantization noise)의 크기를 결정하는 주요인이 되고 있다. 계단의 크기 □가 고정되어 있기 때문에 발생되는 DM의 양자화잡음은 다음과 같은 두 가지 형태로 나타나게 된다.

1) Granular noise : 부드러운 곡선으로 주어지는 연속신호를 계단형 신호로 근사화함으로써 나타나는 잡음

2) Overload noise : 고정된 계단의 크기에 비하여 연속신호의 변화가 너무 급격하여 신호를 추적할 수 없기 때문에 나타나는 잡음

그림 5-10은 이러한 DM의 양자화잡음을 개념적으로 도시한 것이다. □Granular noise□는 연속신호의 변화율이 정해진 계단의 크기에 비하여 너무 작은 경우에 주로 나타나는 잡음이며, 반대로 □Overload noise□는 연속신호의 변화율이 정해진 계단의 크기에 비하여 너무 큰 경우에 주로 발생하게 된다.

그림 5-10  DM 의 양자화잡음

(a) Granular noise    (b) Overload noise

이러한 두 가지 잡음은 조건에 따라 DM의 성능을 심각하게 저하시킬 뿐 아니라, 표본화속도(sampling rate)와 계단의 크기에 대한 시스템의 성능을 너무 민감하게 만든다.

이제 DM의 양자화잡음을 극복하여 그 성능과 효율성을 향상시키기 위한 방안은 명백해 졌다. 계단의 크기와 표본화속도를 고정시키지 않고 연속신호의 변화율에 따라 적응적으로 대응하는 시스템을 구성하면 될 것이다. 다시 말해서 최근에 발생된 펄스 값의 크기 및 그 변화율을 이용하여 각 표본에 적용하는 계단의 크기와 표본화속도를 변화시킴으로써 적응적으로 연속신호를 추적할 수 있도록 하는 것이다.

이 때, 연속신호의 변화율에 따라 계단의 크기를 적응시키는 방식을 ADM(adaptive DM)이라 하며, 표본화속도를 적응시키는 방식을 비동기 DM(asynchronous DM)이라 한다. 그림 5-11은 ADM에 의하여 연속신호를 추적하고 있는 예를 보여주고 있다.

.  ADM이나 비동기 DM에 있어서 계단의 크기 및 표본화속도를 적응시키는 알고리듬은 이 책의 범위를 넘는 부분이므로 다루지 않았다. 그러나 이에 대한 연구는 1970 년대부터 1980 년대 초반에 이르기까지 매우 활발하게 수행되었고, 현재 상당수의 우수한 알고리듬들이 제시되어 있는 상태이다. 이들에 대하여 상세히 공부하고자 하는 독자는 다음 서적을 참고하라.

R.Steele, Delta Modulation Systems, 1975, Pentech Press.

그림 5-11  ADM (연속신호의 추적)

5-5  Gray 코드와 Anti-Gray 코드

Gray 코드와 Anti-Gray 코드는 서로 상반된 성질을 갖는 코드체계로서 소스알파벳 내의 심볼들이 나열되는 순서에 따라 그들에 부여되는 코드들이 최소(gray) 혹은 최대(anti-gray)의 차이를 나타내도록 하는 특별한 목적으로 사용되고 있다. 일반적으로 Gray 코드는 이웃한 심볼들의 코드가 최소의 차이를 갖도록 할당되며, Anti-Gray 코드는 이웃한 심볼들의 코드가 최대의 차이를 갖도록 할당된다.

오늘날 Gray 코드는 여러 분야에서 서로 다른 목적으로 사용되고 있지만, 최초에는 자기디스크(magnetic disk)의 구역번호(sector number)를 할당하기 위하여 설계되었다. 보통 자기디스크 상의 주소(address)는 축을 중심으로 하는 동심원에 부여되는 트랙번호(track number)와 동일한 각도로 설정된 부채꼴에 부여되는 구역번호로 구분된다. 설명을 간단하게 하기 위하여, 그림 5-12와 같이 4 개의 트랙과 8 개의 구역을 갖는 자기디스크에 대하여 각각의 구역번호를 보통 사용되는 이진수의 순서에 따라 할당하였다고 가정하여 보자.

그림 5-12  자기디스크의 구역번호 할당 (이진코드)

만일 자기티스크를 억세스하기 위한 헤드(read/write head)가 그림에 표시된 것과 같이 구역번호 □011□과 □100□ 사이에 위치하고 있다면, 좌측 혹은 우측으로의 작은 이동에 의하여 구역번호의 3 bits가 모두 바뀌는 결과를 나타낸다. 이러한 사실은 헤드 혹은 축의 회전에 약간의 오동작이 발생하면 구역번호 상에는 곧바로 3-bit 오류가 발생할 수 있음을 말해 준다. 따라서 이 때 각 구역의 주소는 기계적인 작은 오동작에 대하여 매우 민감하게 반응하여 큰 오류를 발생시키는 결과를 초래하게 된다.

그렇다면 이러한 자기디스크의 구역번호를 설정함에 있어서 연속되는 구역 사이에 오직 1 bit 씩 변화하도록 코드체계를 변경한다면, 기계적 오동작에 의한 오류를 크게 감소시킬 수 있을 것이다. Gray 코드는 연속된 이진수 사이에 오직 1 bit 씩 변화하도록 설계된 코드체계이다. 따라서 그림 5-12와 같은 자기티스크의 구역번호를 Gray 코드로 할당하면, 구역의 경계에서 발생할 수 있는 구역번호의 오류는 최대 1 bit 로 감소된다. 이와 같이 Gray 코드는 A/D 변환에 있어서 인접 심볼 사이의 경계에서 나타날 수 있는 오동작에 의한 오류를 최소화하는 코드체계로 개발되었다.

이진수의 나열에 따라 오직 1 bit 씩 변화하는 기본적 특성만 가지고는 Gray 코드에 대한 유일한 표현을 얻어낼 수 없다. 또한 Gray 코드는 목적에 따라 여러 가지 형태로 정의되어 사용되고 있다. 따라서 여기서는 가장 일반적으로 사용되는 Gray 코드체계를 정의하고자 한다. 정의는 귀납적으로 이루어 진다.

즉 1-bit Gray 코드체계는 □0□과 □1□의 두 가지 상태를 차례로 정의한다. 2-bit Gray 코드체계는 앞에서 형성된 1-bit Gray 코드체계를 차례로 한 번 쓰고, 그 밑에 역순으로 다시 한 번 써서, 이들을 양분하여 윗부분에는 □0□을, 아랫부분에는 □1□을 각 코드 앞에 덧붙임으로써 얻는다. 이와 같은 과정은 bit 수가 증가하더라도 그대로 적용된다. 일반적으로 n-bit Gray 코드체계는 (n-1)-bit Gray 코드체계를 차례로 한 번 쓰고, 그 밑에 역순으로 다시 한 번 써서, 이들을 양분하여 윗부분에는 □0□을, 아랫부분에는 □1□을 각 코드 앞에 덧붙인다. 이렇게 하여 구성된 코드체계는 심볼의 진행에 따라 오직 1 bit 씩 변화하게 되고, 최종의 심볼로부터 최초의 심볼로의 천이도 1 bit 차이를 나타내게 된다.

다음은 1-bit Gray 코드체계로부터 4-bit의 Gray 코드체계가 형성되는 과정을 보여주고 있다.

0	0 0	0 0 0	0 0 0 0
1	0 1	0 0 1	0 0 0 1
	1 1	0 1 1	0 0 1 1
	1 0	0 1 0	0 0 1 0
		1 1 0	0 1 1 0
		1 1 1	0 1 1 1
		1 0 1	0 1 0 1
		1 0 0	0 1 0 0
			1 1 0 0
			1 1 0 1
			1 1 1 1
			1 1 1 0
			1 0 1 0
			1 0 1 1
			1 0 0 1
			1 0 0 0
<1-bit>	<2-bit>	<3-bit>	<4-bit Gray>

이들 Gray 코드의 구조를 자세히 살펴보면, 원래의 코드(the original set : 가로선 위 쪽)로부터 새로이 형성된 코드(the new set : 가로선 아래 쪽)로 진행하면서 오직 맨 앞에 덧붙인 bit 만이 □0□에서 □1□로 달라지고, 나머지 bit 들은 대칭적으로 같음을 알 수 있다. 다시 말해서 가로선을 중심으로 위 쪽의 코드들과 아래 쪽 코드들이 대칭적으로 오직 1 bit 차이를 나타낸다는 것이다. 또한 이진수의 진행에 따라 오직 1 bit 만 변화하는 원래의 성질을 만족하며, 마지막 코드로부터 처음 코드로의 천이에 대해서도 역시 1 bit 만 변화되고 있다. 따라서 이와 같이 정의된 코드체계는 앞에서 소개한 Gray 코드의 특성을 그대로 만족하며, 이것이 오늘날 가장 보편적으로 사용되고 있는 Gray 코드의 한 형태이다.

그림 5-12에 예시된 자기디스크의 구역번호를 우리가 정의한 Gray 코드로 설정하였다면, 판독에 의하여 얻어지는 주소(구역번호)나 판독을 위하여 부여되는 주소는 모두 Gray 코드로 제공되어야 할 것이다. 그러나 일반적인 디지탈시스템의 다른 부분들은 보통의 이진코드(pure binary code)를 사용하는 경우가 많으므로, 이들 두 가지 코드체계 사이의 변환은 필수적이다. 다시 말해서 디지탈시스템에서 자기디스크의 구역번호를 부여하기 위해서는 □Binary-to-Gray□ 변환이 필요할 것이며, 반대로 자기디스크에서 읽혀진 구역번호를 디지탈시스템이 사용하기 위해서는 □Gray-to-Binary□ 변환을 거쳐야 한다는 것이다. 이들 변환규칙은 같은 bit-수의 Gray 코드와 이진코드를 나열하여 비교함으로써 쉽게 발견할 수 있다.

먼저, □Binary-to-Gray□ 변환규칙은 다음과 같다.

1) 첫 번째 bit는 그대로 취한다.

2) 두 번째 bit 부터 마지막 bit 까지는 현재의 bit와 그 바로 이전 bit의 논리합(mod-2 addition)으로 얻는다.

이진코드의 각 bit를[eqn: b_1 , ``b_2 , ``cdots, ``b_n] 이라 하고, Gray 코드를[eqn: B_1 , ``B_2 , ``cdots, ``B_n] 이라 한다면, 이 변환규칙은 다음과 같이 표현된다.

[eqn: & B_1 ``=`` b_1 `, ## & B_k ``=`` b_k ``` BIGOPLUS``` b_k-1 `, ~ for ~ k``=``2,`3,`cdots,`n]	(5-48)

다음으로, □Gray-to-Binary□ 변환규칙은 다음과 같다.

1) 첫 번째 bit는 그대로 취한다.

2) 두 번째 bit 부터 마지막 bit 까지는 현재의 bit와 그 이전 bits 전체의 논리합(mod-2 addition)으로 얻는다.

이 변환규칙을 식으로 표현하면 다음과 같다.

[eqn: & b_1 ``=`` B_1 `, ## & b_k ``=`` B_k ``` BIGOPLUS``` B_k-1``` BIGOPLUS``` cdots ``` BIGOPLUS``` B_1 `, ~ for ~ k``=``2,`3,`cdots,`n]	(5-49)

실질적으로 이 두 가지 변환규칙은 간단한 논리회로에 의하여 실현될 수 있으며, 그 상태도 역시 쉽게 구할 수 있다. □Binary-to-Gray□ 변환 및 □Gray-to-Binary□ 변환에 대한 상태도와 논리회로 설계는 연습문제를 통하여 제시하기로 한다.

이제, 주제를 바꾸어서 Anti-Gray 코드에 대하여 설명하기로 한다. 일반적으로 주기억장치(main memory)의 주소를 부여할 때에는 주소코드(address code)가 이웃한 번지 사이에서 될 수 있는 한 큰 변화를 갖도록 하는 것이 기억장치의 억세스에 유리하다고 알려져 있다. 그렇다면 주기억장치의 주소는 위에서 설명한 Gray 코드체계와는 상반된 특성을 갖는 코드체계로 부여되어야 할 것이다. 즉, 번지의 순서에 따라 이웃한 이진코드 사이에 가능한 한 여러 bit가 변화하는 코드체계를 구성해야 할 것이다.

하나의 번지로부터 다음 번지로 천이할 때, 앞의 주소코드에 보수(complement)를 취하여 다음 번지의 주소코드로 할당한다면 가장 많은 bit가 변경된다는 것은 명백하다. 그러나 그 두 번지의 다음 번지를 표현하기 위하여 다시 보수를 취한다면, 최초의 번지와 같은 코드로 환원될 것이다. 따라서 각각의 번지들을 유일하게 표현하면서, 번지 수의 차례로 최대의 변화를 나타내도록 하기 위해서는, 하나의 번지로부터 다음 번지는 보수를 취하고, 다시 그 다음 번지는 1 bit 만을 제외한 나머지 이진수에 보수를 취하는 것이 가장 현명한 방법이 될 것이다. 이것은 하나 건너 하나씩 취한 번지가 이른바 Gray 코드를 형성함을 의미하며, k-bit 주소에 대하여 이웃한 번지 사이의 변화는 평균적으로 (k １ 1/2) bits 에 해당한다.

이와 같이 이진수의 진행에 따라 이웃한 코드 사이의 변화가 최대로 나타나도록 설계된 코드를 Anti-Gray 코드라 한다. 우리가 위에서 정의한 Gray 코드체계와 관련하여, n-bit Anti-Gray 코드를 구성하는 과정은 다음과 같이 3 단계로 이루어 진다.

1) (n - 1)-bit Gray 코드를 구성한다.

2) Attachment of leading 0□s : 위 1) 단계에서 구성된 각 코드의 앞에 □0□을 덧붙인다.

3) Interpolation : 구성된 각 코드에 대한 보수코드(complement code)를 각 코드 사이에 삽입한다.

이러한 과정에 의하여 구성되는 코드체계는 이진수의 진행에 따라 n bits 혹은 (n-1) bits 의 변화를 각각 주게 된다. 또한 위 3) 단계에서 새로이 삽입된 보수코드들은 모두 □1□로 시작되며, 2) 단계에서 형성된 기존의 코드들은 모두 □0□으로 시작됨으로 서로 중복되지 않는다. 더욱이 1) 단계에서 형성된 Gray 코드도 중복되지 않으므로, 여기에 보수를 취한 코드들도 서로 중복되지 않는다. 따라서 코드체계 내에는 서로 중복되지 않는 2n 개의 코드가 존재하게 될 것이다. 이는 2n 개의 번지 수를 갖는 주기억장치의 주소로 부여될 수 있으며, 이러한 주소의 설정은 디지탈시스템 내의 여러 가지 레지스터나 카운터로 하여금 각 번지들을 이웃한 번지와 확실히 구별할 수 있게 해 준다.

다음은 위에서 설명한 과정에 의하여 4-bit Anti-Gray 코드를 구성하는 방법을 보여주고 있다.

<3-bit Gray 코드 구성>	<Attach leading 0□s>	<Interpolations>
0 0 0	0 0 0 0	0 0 0 0
0 0 1	0 0 0 1	1 1 1 1
0 1 1	0 0 1 1	0 0 0 1
0 1 0	0 0 1 0	1 1 1 0
1 1 0	0 1 1 0	0 0 1 1
1 1 1	0 1 1 1	1 1 0 0
1 0 1	0 1 0 1	0 0 1 0
1 0 0	0 1 0 0	1 1 0 1
		0 1 1 0
		1 0 0 1
		0 1 1 1
		1 0 0 0
		0 1 0 1
		1 0 1 0
		0 1 0 0
		1 0 1 1

이 절을 통하여 우리는 또 다른 종류의 소스코드를 공부하였다. 가변길이 코드를 사용하여 소스알파벳의 심볼들을 평균적으로 얼마나 짧게 인코딩하느냐의 문제가 일반적인 전송과 결부된 소스코딩의 문제라고 한다면, 이 절에서 취급된 소스코드는 하나의 고정길이 코드로서, 차례로 나열된 심볼들에 대하여 특별한 상관관계를 부여하는 코드체계라고 할 수 있다.

연 습 문 제

5.1	소스알파벳 S Ａ {a, b, c, d}에 대하여 상태천이를 위한 조건확률이 다음과 같이 주어질 때

[eqn: &P`(a vert a`) ``Ａ`` 1/4 ~~&P`(b vert a`) ``Ａ`` 1/4 ~~&P`(c vert a`) ``Ａ`` 1/4 ~~&P`(d vert a`) ``Ａ`` 1/4 # &P`(a vert b`) ``Ａ`` 1/6 &P`(b vert b`) ``Ａ`` 1/3 &P`(c vert b`) ``Ａ`` 1/6 &P`(d vert b`) ``Ａ`` 1/3]

[eqn: &P`(a vert c`) ``Ａ`` 1/4 ~~ &P`(b vert c`) ``Ａ`` 1/8 ~~ &P`(c vert c`) ``Ａ`` 1/2 ~~ &P`(d vert c`) ``Ａ`` 1/8 # &P`(a vert d`) ``Ａ`` 1/4 &P`(b vert d`) ``Ａ`` 1/8 &P`(c vert d`) ``Ａ`` 1/8 &P`(d vert d`) ``Ａ`` 1/2]

(a) 천이그래프(transition graph)를 그려라.

(b) 천이행렬(transition matrix) □를 구하라.

(c) 현 상태에 대한 확률분포를 [pa, pb, pc, pd]라 할 때 차기상태(next state)에 대한 확률분포를 구하라.

(d) 차차기상태(the state after the next state)에 대한 확률분포를 구하라.

(e) 평형분포(equilibrium distribution)를 구하라.

(f) 위의 Markov 과정을 이용하여 Huffman 방식으로 인코딩하고, 이 때 구성되는 코드체계의 평균 코드길이 LM 을 구하라.

(g) 평형상태에서 순수한 Huffman 방식으로 인코딩하고, 이 때 구성되는 코드체계의 평균 코드길이 LH 를 구하라.

(h) 위 (f)와 (g)에서 구한 평균 코드길이를 서로 비교하여 Markov 과정의 효과를 설명하라.

5.2	소스알파벳 S Ａ {a, b, c}에 대한 천이확률들이 다음과 같을 때 문제 5.1을 반복하라.

[eqn: &P`(a vert a`) ``Ａ`` 1/2 ~~&P`(b vert a`) ``Ａ`` 1/4 ~~&P`(c vert a`) ``Ａ`` 1/4 # &P`(a vert b`) ``Ａ`` 1/6 &P`(b vert b`) ``Ａ`` 2/3 &P`(c vert b`) ``Ａ`` 1/6 # &P`(a vert c`) ``Ａ`` 1/8 &P`(b vert c`) ``Ａ`` 1/8 & P`(c vert c`) ``Ａ`` 3/4]

5.3	위 문제 5.1과 5.2에서 구한 천이행렬에 대하여 각각 □2, □4, □8 을 구하여, □원소 사이의 변화량□을 비교하라.

5.4	위 문제 5.1과 5.2에서 구한 천이행렬의 제곱행렬을 이용하여 평형분포를 구하고, 이를 각 문제의 (e)에서 구한 값과 비교하라.

5.5	소스알파벳 S Ａ {a, b, c}에 대한 천이확률들이 다음과 같이 주어진다.

[eqn: &P`(a vert a`) ``Ａ`` 3/4 ~~&P`(b vert a`) ``Ａ`` 1/8 ~~&P`(c vert a`) ``Ａ`` 1/8 # &P`(a vert b`) ``Ａ`` 1/3 &P`(b vert b`) ``Ａ`` 1/3 &P`(c vert b`) ``Ａ`` 1/3 # &P`(a vert c`) ``Ａ`` 1/4 &P`(b vert c`) ``Ａ`` 1/4 &P`(c vert c`) ``Ａ`` 1/2]

(a) 평형분포를 구하라.

(b) Marcov 과정의 개념을 이용한 Huffman 코드를 작성하고 평균 코드길이 LM을 구하라.

(c) 평형상태에서 순수한 Huffman 방법으로 코딩하고 평균 코드길이 LH 를 구하라. 위 (b)에서 구한 LM 과 비교하여 Markov 과정의 효과를 평가하라.

5.6	그림 5-5에 주어진 Run-length 인코더에서는 연속되는 □0□의 수(run-length)를 블록코드로 인코딩하였다. 만일 여기에 Huffman 코드를 도입하려면 어떠한 조건이 필요하며, 그 조건이 만족되었다고 할 때 인코딩 방법을 설명하라.

5.7	그림 5-2의 예측형 Run-length 코딩시스템에 있어서 예측기의 오류확률이 q = 0.03 으로 주어졌다.

(a) Run-length 인코더에서 발생하는 블록코드의 길이를 각각 k = 2, 3, 4, 5, 6, 7, 8, 9 등으로 하였을 때, 채널을 통하여 전송되는 bit 수의 기대값을 구하라. 또한 이들 중 가장 작은 값을 찾아 최적 k 를 결정하라.

(b) 이러한 코딩시스템을 사용하지 않고, 순수한 이진전송(binary transmission)으로 보낼 때, 위 (a)의 결과와 비교되는 평균 bit 수를 구하라.

(c) 위 (a)와 (b)의 결과를 이용하여 예측형 Run-length 코딩시스템의 자료압축율을 구하라.

(d) 위 (a)에서 구한 최적의 k 를 사용할 때, (run-length + 1)의 분산을 구하라.

5.8*	제5-4절에서 설명한 PCM 변조의 양자화에 있어서, 각 수준(quantization levels) 사이의 간격을 a 로 하는 균일 양자화를 수행한다고 하고, 각 표본은 가장 근접한 수준으로 근사화된다고 가정할 때, 양자화 잡음의 전력(mean-square error)은 a2/12 으로 주어짐을 보여라.

5.9*	위 문제 5.8에 설명된 방법으로 다음과 같은 정현파를 양자화할 때,

[eqn: f(t) ``=`` A `cos` omega_m `t]

전체 양자화 수준을 q 개로 하고, 각 수준 사이의 간격을 a 로 하였다면

(a) 신호의 전력은

[eqn: S ``=`` {q^2` a^2} over 8]

와 같이 표시됨을 보여라.

(b) 위 문제 5.8에서 구한 양자화 잡음의 전력과 위 (a)에서 구한 신호의 전력을 이용하여, 신호대 양자화 잡음비(signal-to-quantization noise ratio)를 구하라.

(c) 위 (b)의 결과를 가지고 양자화 수준의 수 q 와 시스템 성능 사이의 관계를 설명하라.

5.10	그림 5-7에 주어진 DPCM 방식의 양자화기에 있어서, 선형 예측기의 성능과 양자화 수준 사이의 관계를 □신호대 양자화 잡음비□의 관점에서 설명하라.

5.11	그림 5-8에 주어진 DM 인코더의 입력으로

[eqn: x(t) ``=`` 2` t ``+` 1 `, ```0 ``<=``t ``<=``5]

와 같은 신호를 인가하였다. 구간 내에서 10(samples/sec)의 속도로 표본화되고, 계단의 크기는 0.5(volts)로 고정되어 있다고 가정할 때,

(a) 입력신호와 적분기의 출력을 비교하여 스케치하라.

(b) 시스템의 각 부분 B, C, E 에서의 신호형태를 스케치하라.

(c) 표본화속도를 그대로 두고 계단의 크기를 1(volt)로 수정하였을 때, 위 (a), (b) 과정을 반복하라.

(d) 계단의 크기를 그대로 두고 표본화속도를 20(samples/sec) 및 5(samples/sec) 으로 수정하였을 때, 위 (a), (b) 과정을 반복하라.

(e) 위 (a), (c), (d) 에서 얻은 결과를 이용하여, 이 신호에 가장 적당한 계단의 크기와 표본화속도는 어떤 것인지 말하라.

5.12*	(Gray code & Anti-Gray code)

(a) 5-bit, 6-bit, 7-bit Gray 코드를 각각 구성하라.

(b) 위 (a)의 결과를 이용하여 6-bit, 7-bit, 8-bit Anti-Gray 코드를 각각 구성하라.

(c) n-bit Gray 코드를 입력으로 하여 n-bit 이진코드를 발생하는 시스템의 상태도(state diagram)를 그려라.

(d) n-bit 이진코드를 입력으로 하여 n-bit Gray 코드를 발생하는 시스템의 상태도를 그려라.

(e) 4-bit Gray 코드를 입력으로 받아 4-bit 이진코드를 출력하는 조합논리 회로를 설계하고 그 논리도를 그려라.

(f) 4-bit 이진코드를 입력으로 받아 4-bit Gray 코드를 출력하는 조합논리 회로를 설계하고 그 논리도를 그려라.