제 3 장

채널코딩

3-1  채널코딩의 필요성

	정보이론

제 3 장 오류검출 코드

앞에서 설명한 바와 같이, 실제적으로 사용되는 모든 채널(channel)들은 그것을 통하여 신호가 전송될 때 필연적으로 잡음(noise)의 영향을 받는다. 이러한 잡음의 영향은 디지탈시스템에 있어서 오류(error)로 나타나며, 이를 수신측에서 보상하기 위해서는 특별한 코드체계를 사용하여야 한다.

이 장에서는 채널에서 발생한 잡음에 의하여 수신측에 나타나는 오류를 제어할 수 있도록 코드체계를 조작하는 이른바 채널코딩(channel coding)의 문제를 다루고자 한다.

채널코딩은 크게 나누어, 단지 오류의 발생 여부 만을 가려내는 오류검출코드(error- detection code)와 오류의 발생 여부는 물론 발생된 오류를 수신측에서 독립적으로 수정할 수 있는 오류정정코드(error-correction code)로 구분된다.

공간을 통하여 정보를 전송하거나 기억장치에 정보를 저장하고자 할 때, 우리는 그 정보가 좋은 신뢰성을 가지고 채널을 통과하기를 원할 것이다. 경험에 의하면 오류제어 체계를 사용하지 않으면서 높은 신뢰성을 갖는 장비를 제작한다는 것은 큰 신호전력을 요구하기 때문에 그 비용과 시간 면에서 매우 어렵다. 더욱이 어떤 시스템이 고신뢰성을 유지하기 위해서는 그것을 구성하고 있는 부품들이 모두 철저히 선정된 고급품이어야만 가능하다.

이러한 사실로 볼 때 오류제어 체계의 중요성은 두드러 진다. 다시 말해서 시스템의 비용을 낮추어 조금 덜 신뢰성 있는 것으로 만들더라도, 신호처리 중에 발생하는 오류를 검출 혹은 정정할 수 있는 체계를 갖춘다면 그 단점을 보상하여 더 나은 신뢰성을 제고시킬 수 있다는 것이다.

더 나아가서 오류검출코드는 시스템의 유지보수(maintenance)를 위하여 기여하는 바 크다. 오늘날 오류검출 체계를 갖추지 않은 대형 디지탈시스템은 그 유지보수가 거의 불가능한 것으로 알려져 있다. 시스템의 입력에 일정한 형태의 이진열(binary sequence)을 인가하고, 각 블록별로 오류의 발생 여부를 검사하여 오류가 발생된 부위를 진단함으로써 대형 디지탈시스템의 고장 부분을 용이하게 찾아낼 수 있으며, 이러한 방법은 최근 디지탈시스템의 유지보수를 위하여 필수적으로 갖추어야 하는 기능이 되어 가고 있는 것이다.

재전송(retransmission)이 가능한 시스템에서는 오류정정 체계를 갖추지 못했더라도 오류검출만으로 충분한 경우가 많다. 즉 오류의 존재가 검출되면 현재 진행된 메시지나 동작을 재차 수행하도록 요청하는 형식이다. 이 때, 두번째 수행에서도 오류가 발생되면 또 다시 요청하는 방식으로 반복하면 될 것이다. 보통의 정보통신시스템에서는 이러한 반복의 횟수를 한정하여, 정해진 횟수 만큼 반복하여도 오류가 발생하면 해당 메시지를 포기하는 형식을 취하고 있다.

일정한 길이의 정보(데이터 블록)에 대하여 오류검출을 가능하도록 하기 위해서는 어떤 것이 정확한 정보인지를 판단하는 기준이 마련되어야 한다. 다시 말해서, 수신측에서 채널을 통과한 정보를 받아 오류의 발생 여부를 판단할 수 있도록 하기 위하여 송신측은 수신측과 약속된 기준이나 제한을 코드체계 내에 부여하여 전송해야만 한다는 것이다. 오류검출을 위한 기준이나 제한을 부여하는 문제는 오류정정에서의 그것보다 비교적 간단하다.

특수한 목적을 갖는 시스템을 설계할 때, 단순히 오류의 존재를 검출하여 재전송을 요구하는 것만으로는 부족할 경우도 많다. 그렇다면 오류검출코드에 있어서 오류의 존재성은 검출할 수 있으면서 그 오류를 정정할 수 없는 이유는 무엇일까 ?

	정보이론

제 4 장 오류정정 코드

일반적으로 디지탈시스템은 □0□과 □1□ 만으로 이루어진 이진신호를 사용함으로, 만일 우리가 일정한 블록 내에서 오류가 발생한 위치를 알아 낼 수 있다면 이를 정정할 수도 있을 것이다. 다시 말해서 오류 발생위치에 있는 □0□은 □1□로, □1□은 □0□으로 교환하는 단순한 논리에 의하여 이를 해결할 수 있다는 것이다. 따라서 오류정정의 문제는 결국 오류의 발생위치를 정확히 알아내는 일로 귀결되며, 이는 송신측의 코딩방식에 관한 문제로서 지금까지 알려진 여러가지 특수한 방식에 의하여 해결할 수 있는 문제이다.

오류정정코드의 사용에 대하여 우리에게 특별한 의미를 부여해 주는 것은 위성통신의 경우이다. 하나의 지상국(earth station)으로부터 위성체(space probe)를 통하여 또 다른 지상국으로 정보를 전송하는 경우를 생각해 보면, 그 전송시간은 신호처리 속도에 비하여 매우 길어, 수신측에서 오류를 검출하여 송신측에 재전송을 요구한다는 것은 시스템의 효율 면에서 대단히 불합리한 일일 것이다. 이 때 오류정정코드를 사용함으로써 재전송 요구 없이 수신측에서 곧바로 정확한 정보를 얻을 수 있다면 대단히 편리할 것이다.

오늘날 정보통신시스템에서는 여러가지 형태의 정교하게 설계된 오류정정코드가 사용되고 있으며, 이들 중에는 하나의 블록(Block) 내에서 동시에 여러 개의 오류를 정정할 수 있는 것들도 있다.

또한 오류정정코드는 전형적인 저장시스템(storage system)에서도 매우 유용하게 쓰인다. 예를 들어서 자기테이프에는 많은 양의 정보가 수시로 저장되었다가 지워지곤 한다. 따라서 수년 동안 계속 사용된 자기테이프는 점차로 그 질이 저하되고 마침내 신뢰성을 상실하게 되는 것이다. 이렇게 되면 그 자기테이프에 기록되어 있던 정보를 영원히 상실하게 되며, 경우에 따라서는 그 정보의 원본까지도 잃게 될 수도 있다. 이 때, 만일 그 정보의 코드에 오류정정 능력을 부여해 두었다면 그 해당오류를 정정하여 정보의 상실을 방지할 수 있을 것이다.

오류정정코드는 정보통신시스템 및 저장시스템에서 오래 전부터 사용되어 왔으며, 그들 오류정정 기능은 하드웨어(H/W) 혹은 소프트웨어(S/W)로 구현하여 설치되었다.

특히 소프트웨어로 실현된 오류제어 체계는 시스템의 중요한 부분에 대하여 그 능력을 충분히 부여하고 덜 중요한 부분에 대해서는 간단한 체계로 설치하거나 생략할 수 있는 등 융통성이 크다는 장점이 있다.

일반적으로 알려진 시스템의 약점은 어느 부분이 오류에 대하여 취약하고, 어느 부분의 오류정정 능력을 많이 필요로 하는 지에 대한 의문을 오직 경험에 의해서만 판단할 수 있다는 사실에 있다. 이러한 약점을 극복하기 위한 하나의 방편으로, 먼저 소프트웨어로 구성된 오류제어 체계를 적용하여 모의실험(simulation)을 거쳐 시스템의 취약 부분을 파악한 후 최적의 오류제어 체계를 설계하고, 그에 따른 하드웨어를 설치하는 방식을 제시할 수 있을 것이다. 명백히 하드웨어로 구현된 오류제어 체계는 소프트웨어로 구현된 것보다 수행시간이 짧아 실시간 처리에 유리하지만 그 비용면에서는 불리하다.

이 장의 전반부에서는 오류검출코드를 구성하는 방식을 다루고, 이를 기반으로 후반부에서는 간단한 오류정정코드에 대하여 공부하기로 한다.

3-2  패리티 검사

이진 메시지가 오류검출 능력을 가질 수 있도록 하는 가장 간단한 방법은 전체 메시지를 일정한 길이로 나누어 블록(block)을 형성하고, 각 블록이 짝수 개의 □1□을 포함하도록 패리티 bit를 부여한 후 수신측에서 이를 검사하는 것이다. 이 때 각 블록은 짝수 패리티(even parity)를 가진다고 말하며, 수신측에서 이에 대한 검사를 행하는 과정을 패리티 검사(parity check)라 한다.

보통의 경우 전체 메시지를 (n - 1) bits 길이의 블록으로 나누고, 각 블록의 n 번째 bit로 패리티 검사 bit(parity-check bit)를 추가한다. 이 때, 블록 전체에 짝수 개의 □1□이 포함되도록 검사 bit를 부여하고, 수신측에서는 각 블록 내에 있는 □1□의 갯수를 세어 오류발생 여부를 판단한다. 만일 수신된 블록에 포함된 □1□의 갯수가 홀수이면 그 블록은 전송 중에 적어도 1 bit의 오류를 포함하게 되었음을 알 수 있는 것이다. 그림 3-1은 이와 같은 단순 패리티 검사(simple parity check)를 위하여 검사 bit를 부여하는 방식을 보여준다.

nth	(n-1)st	·····	3rd	2nd	1st
↑ 패리티 검사 bit

그림 3-1  단순 패리티 검사를 위한 블록의 형성

단순 패리티 검사를 행하는 전송시스템에 있어서, 만일 어떤 블록에 두 bit의 오류가 발생되었다면 이는 검출될 수 없음이 명백하다. 요컨대 단순 패리티 검사는 홀수 개의 오류만을 검출할 수 있으며 짝수 개의 오류에 대해서는 검출이 불가능하다.

한 블록 내의 각 bit에서 오류가 발생될 확률을 p라 하고 각 bit는 서로 독립적이라고 가정하면, 단일오류(1 bit error)가 발생될 확률은

[eqn: P_E_1 ~=~ binom n 1 ~p^1~ (1~-~p)^n-1 ~simeq~ np]                        (3-1)

와 같이 나타낼 수 있다.

여기서 [eqn: binom n 1]은 [eqn: n] 개의 서로 다른 원소에서 1 개를 택하는 □조합의 수□로서

[eqn: binom n r ~==~ {n`!} over {r`! ~(n`-`r)`!}]                              (3-2)

로 표현되는 이항계수(binomial coefficient)의 정의에 따라 계산되는 수이다.

한 블록 내에서 2 bits의 오류가 발생될 확률은 위와 마찬가지 방법에 의하여

[eqn: P_E_2 ~=~ binom n 2 ~p^2~ (1~-~p)^n-2 ~simeq~ {n(n~-~1) p^2} over 2]	(3-3)

라 쓸 수 있다.

식(3-1)과 식(3-3)을 비교하여 보면, 2 bits 오류가 발생될 확률은 단일오류가 발생될 확률을 제곱하여 2로 나눈 것과 근사하다. 다시 말해서 단일오류가 발생될 확률이 매우 작은 값이라고 가정하면 2 bits 오류가 발생될 확률은 더욱 작아져서 거의 무시할 수 있는 값이 된다는 것이다. 이러한 사실은 2 bits 이상의 오류가 발생되는 경우를 무시하고 오로지 단일오류만을 검출하더라도 간단한 시스템에 대해서는 상당히 의미있는 오류제어를 수행할 수 있음을 말해준다.

일반적으로 오류검출코드를 설계할 때, 한 블록 내에서 검출할 수 있는 오류의 갯수나 각 블록의 최적길이 등은 채널의 상태에 따라 주어지는 오류확률 p를 기준으로 공학적 상보성(engineering trade-off)을 고려하여 정해진다.

오류검출코드에 있어서, 한 블록의 전체 bit 수(total number of bits)와 순수한 정보 bit 수(number of information bits)의 비를 Redundancy라 정의한다.

그림 3-1에 표현된 단순 패리티 검사의 경우 Redundancy는

[eqn: n over {n`-`1} ```Ａ```1``／``1 over {n`-`1}]	(3-4)

와 같이 계산되며, 이 때 1/(n-1)을 Excess-Redundancy라 한다.

식(3-4)에서 알 수 있는 바와 같이, Redundancy를 줄이기 위해서는 블록의 길이 n 을 증가시켜야 하며, 반면에 오류검출 능력을 향상시키기 위해서는 블록의 길이를 될수록 짧게 하여야 한다. 또한 하나의 블록 내에서 2 bits 이상의 오류를 검출하도록 하기 위해서는 패리티 검사 bit의 수를 증가시켜야 하며, 이에 따라 Redundancy도 증가하게 된다.

n-bit 블록에 대하여 (n-k) bits의 패리티를 부여하고 나머지 k bits를 정보로 사용한다면, 이 때의 Redundancy는 다음과 같이 표현된다.

Redundancy [eqn: =~ { \total`` \number`` \of`` bits } over { \number`` \of`` \informat\ion`` bits } ~=~ n over k]	(3-5)

일반적으로 Redundancy가 증가하면 전송된 블록에서 순수한 정보의 비율이 낮아지고 오류검출 능력은 향상되어 시스템의 신뢰성이 좋아진다. 반대로 Redundancy가 감소하면 시스템의 신뢰성은 떨어지나 블록 내의 정보율이 증가한다. 따라서 오류검출코드의 Redundancy를 결정하는 것도 공학적 상보성을 갖는다고 할 수 있다. 그림 3-2는 한 블럭 내에 여러 bits의 패리티를 부여하는 방식을 나타내고 있다.

nth	(n-1)st	···	(k+1)st		kth		···	2nd	1st
패리티 검사 bits (n-k) bits						정보 bits k bits

그림 3-2  다중 패리티 검사를 위한 블록의 형성

3-3  독립오류와 백색잡음

제2-2절에서 설명한 바와 같이, 일반적으로 신호시스템의 모델은 그 채널에서 필연적으로 잡음의 영향을 받아 수신된 디지탈 정보에는 언제나 오류를 포함하고 있다는 가정을 전제로 한다. 이러한 오류에 대하여

(1) 블록 내의 각 bit는 동일한 오류확률 p를 가진다.

(2) 블록 내의 각 bit 사이에는 독립성이 유지된다.

라고 규정지을 경우, 우리는 이를 간단한 백색잡음(white noise)이라 볼 수 있다. 본래 백색광(white light)은 인간의 눈으로 식별할 수 있는 모든 주파수에서 일정한 양의 에너지를 포함하고 있는 광선을 말한다. 위에서 정의된 백색잡음은 블록 내의 모든 bit에서 일정한 크기의 오류확률을 가지므로 그 유사성에 따라 그러한 이름을 갖게 되었다고 할 수 있다. 그림 3-3은 블록 내의 각 bit에 대한 오류확률을 그래프로 나타낸 것이다.

그림 3-3  백색잡음 (독립오류)

요컨대 백색잡음을 가정하면 이론의 전개가 쉽다. 그러나 실제에 있어서 각 bit의 오류확률은 서로 상이하게 나타날 수 있으며, 채널이 놓인 환경이나 전원공급기의 성능변화 등에 의하여 오류가 무더기로 발생할 가능성도 있으므로 각 bit는 서로 독립이라고 할 수 없다. 이와 같이 위의 두가지 조건을 만족하지 않는 잡음을 유색잡음(colored noise)이라 하며, 이러한 잡음에 의한 오류는 매우 복잡한 양상을 띈다. 채널코딩에 있어서 중요시하는 유색잡음에 의한 오류 중에는 다발성 오류(burst error)라는 것이 있다. 이를 제어하기 위한 코드체계에 대해서는 제3-5절에서 취급하기로 하고 여기서는 우선 백색잡음에 의한 오류의 특성을 정리해 두기로 한다.

오늘날 정보통신 기술이 눈부시게 발달되었다고는 하나 신호시스템의 설계에 있어서 실제로 발생할 수 있는 잡음의 형태를 정확하게 고려한다는 것은 거의 불가능하다. 따라서 백색잡음은 이론적으로 오류의 특성을 분석하는 데 있어서 하나의 합리적인 가정으로 자주 수용되고 있다.

블록 내의 한 bit에서 오류가 발생할 확률이 p이므로 오류가 발생되지 않을 확률은 당연히 (1 - p)이다. 따라서 하나의 블록(n bits)이 오류 없이 전송될 확률은

[eqn: (`1`-``p`)^n]	(3-6)

이다.

또한 하나의 블록에서 단일오류(1 bit error)가 발생될 확률은

[eqn: np`(`1-p`)^n-1]	(3-7)

로 표시된다. 또한 블록 내의 n bits 중 k bits에서 오류가 발생할 확률은 이항계수를 이용하여

[eqn: binom n k``p^k ``(`1`-``p`)^n-k]	(3-8)

와 같이 쓸 수 있다.

그러므로 하나의 블록 내에서 짝수 개(0, 2, 4, …)의 오류가 발생될 확률은 식(3-8)을 이용하여 다음과 같이 계산된다.

[eqn: &binom n 0 p^0 `(1`-`p)^n ``+`` binom n 2 p^2 `(1`-`p)^n-2`` +`` cdots ``+`` binom n 2m p^2m `(1`-`p)^n-2m ``+`` cdots ## &~~~~~=~ sum_m=0^[n/2] `binom n 2m p^2m `(1`-`p)^n-2m]	(3-9)

여기서 [·]은 □괄호 안의 숫자보다 크지 않은 최대의 정수□를 의미한다.

한편, 하나의 블록 내에서 홀수 개(1, 3, 5, …)의 오류가 발생할 확률은 위의 식(3-9)에 표시된 확률의 역확률이므로

[eqn: 1``- `sum from mＡ0 to{ [n/2]}` binom n 2m `p^2m `(1`-`p) ^n-2m]	(3-10)

와 같이 얻어진다.

앞 절에서 설명한 단일 패리티 검사는 홀수 개의 오류를 검출할 수 있으므로 식(3-10)에 주어진 확률은 검출 가능한 오류에 대한 확률이다. 또한 오류가 전혀 발생하지 않을 확률은 식(3-9)의 첫번째 항에 해당되므로, 단일 패리티 검사에 의하여 검출되지 않는 오류가 발생할 확률은

[eqn: sum from mＡ1 to {[n/2]} binom n 2m `p^2m `(1`-`p`)^n-2m]	(3-11)

로 주어진다.

일반적으로 실용적인 채널에 있어서 다수의 오류가 발생할 확률은 대단히 작을 것이 명백하므로 식(3-10)이나 (3-11)의 계산은 처음 몇 개의 항에 의하여 지배될 것이다.

[예제 1] 각 bit의 독립오류확률이 [eqn: p=0.01]인 채널을 통하여, 1 bit 패리티를 포함하여 블록당 8 bits인 메시지가 전송된다고 할 때 다음을 구하라.

(1) 하나의 블록이 오류 없이 전송될 확률 [eqn: P_1]

(2) 단일오류가 발생될 확률 [eqn: P_2]

(3) 단일 패리티 검사에 의하여 검출되지 않는 오류가 발생될 확률 [eqn: P_3]

[풀이]

(1) 식(3-6)에 의하여   [eqn: P_1 ~=~ (1-0.01)^8 ~=~ 0.99^8 ~simeq~ 0.923]

(2) 식(3-7)에 의하여   [eqn: P_2 ~=~ 8 cdot 0.01^1 cdot0.99^7 ~simeq~ 0.075]

(3) 식(3-11)에 의하여

[eqn: P_3 &=` sum_m=1^4 binom 8 2m ``0.01^2m cdot 0.99^8-2m ## &=`` binom 8 2 `0.01^2 cdot 0.99^6 +`binom 8 4 `0.01^4 cdot 0.99^4 + binom 8 6 `0.01^6 cdot 0.99^2 + binom 8 8 `0.01^8 cdot 0.99^0 ## &simeq ~ 0.002637]

[예제 2] 위 예제 1에 있어서 □검출되지 않는 오류확률□은 대체로 식(3-11)의 처음 두항에 의하여 지배됨을 알 수 있다. 이 확률의 값이 [eqn: 10^-3]보다 작게 하고자 한다면 주어진 채널에서 블록의 길이를 얼마로 하여야 하는가 ?

[풀이]

일반적으로 블록의 길이가 길어지면 블록 내에서 정보가 차지하는 비율은 높아지고Redundancy는 감소한다. 따라서 검출되지 않는 오류확률을 감소시키기 위해서는 블록의 길이를 짧게 하여야 함을 알 수 있다. 이 예제에 대해서는 다음과 같은 부등식을 적용시킬 수 있다.

[eqn: P_3 &=` sum_m=1^[n/2] `binom n 2m `0.01^2m cdot 0.99^n-2m ## &simeq ``` binom n 2 `0.01^2 cdot 0.99^n-2 `+`` binom n 4 `0.01^4 cdot 0.99^n-4 ~ <=~ 10^-3]

이 부등식을 풀면, [eqn: n``<=``5]를 얻으며, 따라서 구하는 블록의 길이는 5(bits)이다.

3-4  메시지의 재전송

오류검출코드를 사용하는 시스템에 있어서 전송 중 오류가 발생하면 보통 재전송(retransmission)이나 재처리(reprocessing)를 요구할 수 있는 경우가 많다.

자기테이프의 판독장치에 있어서도 보통 하나 이상의 오류검출코드가 사용된다. 판독 중 패리티 검사에서 오류가 검출되면 재판독을 요청하게 된다. 이 때 몇 차까지 재판독을 요청할 수 있도록 할 것인가에 관한 문제는 설정된 오류모델(error model)에 따라 결정된다. 검출된 오류가 테이프의 자성에 큰 손상을 주지 않는다면 재차의 판독에 의하여 정확한 정보를 얻어낼 수 있을 것이다. 그러나 만일 그 오류가 테이프의 자성에 치명적인 손상을 주고 있어서 아무리 재판독을 실시하여도 오류가 발생할 수 밖에 없다면, 반복적인 재판독 요청에 의하여 또 다른 오류를 발생시켜 궁극적으로 패리티 검사를 만족시킬 수도 있다(짝수 개의 오류는 검출되지 않으므로). 이렇게 되면 올바른 메시지가 아니라 오히려 오류가 늘어난 메시지를 얻게 될 것이다. 그러므로 검출된 오류가 일시적인 것이라고 판단될 때에 한하여 한두번의 반복수행을 요청하는 것이 좋을 것이다.

패리티 검사는 컴퓨터의 하드웨어와 소프트웨어 운용에 있어서 오래 전부터 사용되어 왔다. 예를 들어서 과거에 컴퓨터의 기억장치로 흔히 쓰였던 자기드럼(magnetic drum)을 생각하여 보자. 드럼에 기록할 때에는 저장될 블록 내의 모든 bits를 포함하는 레지스터의 논리합이 구해져서 드럼 상의 최종 블록에 저장된다. 저장이 끝나면 곧바로 드럼을 판독하여 모든 정보가 올바로 기억되었는가를 검사한다. 차후에 그 드럼이 판독될 때에는 다시 모든 블록의 패리티를 검사하여 논리합이 □0□이 되는 가를 확인한다. 만일 그렇지 않으면 재판독을 요청한다.

최근 빠른 속도로 확산되어 가고 있는 유선 데이타통신이나 이동통신시스템의 송수신기에 있어서도 일종의 오류검출코드가 사용되고 있다. 수신기는 채널을 통과한 정보를 받아 오류 발생여부를 검사하고, 만일 오류가 검출되면 송신기에 재전송을 요구한다. 만일 재전송에 의하여 수신된 정보에서도 오류가 발생되었다면 또다시 재전송을 요구하게 된다. 그러나 이러한 재전송 요구를 무한히 계속할 수는 없는 것이므로 공통으로 소유하고 있는 계수기(counter)에 의하여 재전송 횟수를 계수하고, 일정한 반복 횟수가 초과되면 해당 블록을 포기하는 방식을 취한다.

3-5  다발오류 검출 코드

채널을 통하여 수신된 메시지 중에는 독립된 bit에서 발생되는 오류도 있지만 다발성 오류(burst error)로 나타나는 경우도 종종 있다. 천둥, 번개와 같은 전파환경의 변화나 전원공급기(power-supply)의 성능 변화에 의한 통신시스템의 이상 혹은 저장시스템의 자성체 표면에 형성된 흠(flake) 등은 이러한 다발성 오류의 전형적인 원인이 된다.

실험을 통하여 우리가 검출할 수 있는 다발오류의 최대 길이는 L(bits)라고 가정하자. 또한 논의를 쉽게 하기 위하여 이 다발오류의 최대 길이 L은 시스템 레지스터의 길이와 일치한다고 가정하자. 우리는 지금까지 bit 단위의 패리티 검사에 의한 오류검출 코드에 대해서만 논의하여 왔으나, 이러한 다발오류를 검출하기 위해서는 word의 위치에 따르는 Word 단위 패리티 검사를 수행하여야 한다. 다시 말해서 전송할 메시지를 L(bits) 길이의 블록으로 나누고, 나누어진 각 블록을 word로 취급하여 이를 단위로 패리티 word를 부여하여 전송하고, 수신측에서는 각 블록 내에서 bit 단위의 패리티 검사와 word 단위의 패리티 검사를 수행하는 것이다. 앞 절에서 설명한 바와 같이, bit 단위의 패리티 검사에 의해서는 이른바 독립오류가 검출될 것이며, word 단위의 패리티 검사에 의해서는 다발오류가 검출될 수 있을 것이다.

이러한 패리티 검사는 그림 3-4와 같이 각 word를 차례로 늘어놓고 행(row) 단위 패리티 검사와 열(column) 단위 패리티 검사를 수행하는 것과 같다. 이 때, 행단위 패리티 검사는 독립오류를 검출하기 위하여 하나의 블록 내에서 수행되는 bit 단위 검사에 해당되며, 열단위 패리티 검사는 다발오류를 검출하기 위한 word 단위의 검사에 해당된다.

그림 3-4  다발오류 검출을 위한 패리티 검사

만일 다발오류가 한 word의 끝 부분으로부터 다음 word의 첫 부분에 걸쳐 있다고 하더라도 하나의 열에는 최대 한 개의 오류가 발생할 것으로 기대된다. 왜냐하면 실험적으로 모든 다발오류의 길이 k는 0□k□L을 만족한다고 가정하였기 때문이다. 주지하는 바와 같이 이러한 다발오류는 word 단위의 패리티 검사에 의하여 검출될 것이며, 다발오류가 검출되면 수신측은 재전송을 요구한다. 일반적으로 다발오류 검출코드는 앞에서 설명하였던 독립오류 검출코드에서와 마찬가지로 오류가 발생된 word의 위치를 판단할 수 없고 단지 다발오류의 발생여부만을 검출함으로 패리티 검사에 참여한 모든 words에 대하여 재전송을 요구하게 된다.

이와 같은 원리로 우리가 실험을 통하여 다발오류의 특성을 정확히 인식할 수 있다면 그에 대하여 적당한 오류검출 코드를 설계할 수 있고 이를 시스템에 적용함으로써 다발성 잡음을 갖는 채널을 통해서도 메시지를 전송할 수 있게 된다.

사실 여기에 제시한 코드체계는 원리적으로 단순하고 오류검출만을 가능케하므로 실질적인 채널에의 적용에는 한계가 있다고 볼 수 있다.

최근 다발오류를 일으키는 잡음의 특성을 구체적으로 분석하고 이들을 실질적으로 제어하는 다발오류 정정코드(burst-error correction code)가 활발히 연구되고 있으며 이들의 하드웨어 구성에 관해서도 많은 제안이 발표되었다. 그러나 이에 관한 구체적 내용은 이 책의 범위를 넘어가므로 생략하기로 한다.

. 다발오류를 일으키는 잡음의 특성과 다발오류 정정코드에 관하여 구체적으로 공부하려는 독자는 다음 문헌을 참고하라.

S.Lin and D.J.Costello,Jr., Error Control Coding - Fundamentals and Appilcations, Chapter 14, 1983, Prentice-Hall.

[예제 3]  어떤 전송시스템에 대하여 특별한 전파환경이 적용되어 다발오류 검출코드를 사용하고자 한다. 다발오류의 최대 길이는 7(bits)이며 하나의 word에 대하여 8-bit ACSII 코드(표 2-1)를 사용하기로 한다. 이 때, 여덟번째 bit는 패리티 검사 bit로 사용하고, 각 7 words에 하나씩의 패리티 검사 word를 둔다. 전송하고자 하는 메시지가 다음과 같을 때 물음에 답하라.

메시지 : Information Eng. 1996

(1) 패리티 검사 bits와 패리티 검사 words를 포함하여 코딩되는 과정을 밝히고 전송되는 메시지를 구하라.

(2) 전송 도중 5 번째 word의 뒷부분으로부터 6 번째 word의 앞부분에 걸쳐 다발오류가 발생되었다고 가정하여 적당한 오류를 부여하고 이들이 검출되는 과정을 밝혀라.

(3) 8-진(octal) ASCII 코드로 위 (1)에서 전송되는 메시지를 써라.

[풀이]

(1) 두가지 패리티 검사에 대하여 공히 짝수(even) 패리티를 적용한다고 가정하면, 주어진 메시지는 각 문자당 8 bits (1 parity bit 포함), 7 문자(word) 당 1 패리티 word로 코딩되어 다음과 같이 나타난다.

I	1  1  0  0  1  0  0  1

n	1  1  1  0  1  1  1  0

f	0  1  1  0  0  1  1  0

o	0  1  1  0  1  1  1  1

r	0  1  1  1  0  0  1  0

m	1  1  1  0  1  1  0  1

a	1  1  1  0  0  0  0  1

패리티	0  1  0  1  0  0  0  0  → P

t	0  1  1  1  0  1  0  0

i	0  1  1  0  1  0  0  1

o	0  1  1  0  1  1  1  1

n	1  1  1  0  1  1  1  0

space	1  0  1  0  0  0  0  0

E	1  1  0  0  0  1  0  1

n	1  1  1  0  1  1  1  0

패리티	0  0  0  1  0  1  1  1  → ETB

g	1  1  1  0  0  1  1  1

·	0  0  1  0  1  1  1  0

space	1  0  1  0  0  0  0  0

1	1  0  1  1  0  0  0  1

9	0  0  1  1  1  0  0  1

9	0  0  1  1  1  0  0  1

6	0  0  1  1  0  1  1  0

패리티	1  1  1  0  1  1  1  0  → n

따라서 전송되는 메시지는 Informa[P]tion En[ETB]g. 1996[n] 이 된다. 여기서 패리티 word는 [ ]로 묶어 표시하였으며, 이들 중 [ETB]는 전송제어문자 □end of transmission block□을 나타낸다 (제2-4절 ASCII 코드 참조).

(2) 전송 도중 5 번째 word □r□의 뒷 부분으로부터 6 번째 word □m□의 앞 부분에 걸쳐 발생된 다발오류는 첫 번째 패리티 word에 의하여 검출될 것이므로, 그 검출과정은 다음과 같이 나타낼 수 있다.

I	1  1  0  0  1  0  0  1

n	1  1  1  0  1  1  1  0

f	0  1  1  0  0  1  1  0

o	0  1  1  0  1  1  1  1

r	0  1  1  1  0  1  0  0

m	0  0  0  0  1  1  0  1

a	1  1  1  0  0  0  0  1

패리티	0  1  0  1  0  0  0  0  → P

□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

패리티 검사	1  1  1  0  0  1  1  0  → 패리티 검사 Fail

→ 재전송 요구

(3) 전송되는 메시지를 8-진 ASCII 코드로 쓰면 다음과 같다.

311356146157162355341120164151157356240305356027347056240261071071066356

3-6  가중치 코드(weighted codes)

지금까지 논의한 오류검출코드들은 일반적으로 정보통신 채널 상에 존재하는 단순한 백색잡음이나 특수한 전파환경을 가정하여 이루어지는 것들이었다. 또한 이러한 코드들이 여러가지 형태의 통신장치나 저장장치에 매우 적당하다는 것도 사실이다. 그러나 직렬전송에 있어서 운용자(사람)가 개입되는 상황이라면, 조작 중 어떤 심볼을 빠뜨린다든가 불필요한 심볼이 삽입되는 오류 혹은 두 심볼을 거꾸로 전송하는 오류 등이 자주 발생하게 된다. 이러한 오류들은 수신되는 메시지의 왜곡을 나타낼 뿐 아니라 시스템의 동기(synchronization)에도 치명적인 손상을 주게 되며, 위에서 논의하였던 코드체계에 의해서는 검출되지 않는다.

운용자의 조작을 필요로 하는 통신시스템에 있어서는 채널 상에서 발생하는 잡음에 의한 오류 이외에 조작의 실수로 발생되는 또다른 형태의 일반적인 오류가 존재하게 된다. 운용자는 실수로 이웃한 두 개의 숫자를 서로 바꾸어 쓰는 경우가 많다(예컨대, 67을 76으로). 또한 세 개의 숫자 중에서 두 개가 서로 같을 경우 나머지 한 숫자를 겹쳐 쓰는 경우도 종종 있다(예컨대, 667을 677로). 영문자와 숫자를 함께 사용하는 시스템에서는 영문자 □O□와 숫자 □0□, 영문자 □I□와 숫자 □1□, 영문자 □B□와 숫자 □8□ 등을 혼동하여 바꾸어 쓰는 오류도 흔히 발생한다.

보통 영문자와 숫자만을 사용하는 시스템들은 26 개의 영문자와 1 개의 공백(space), 그리고 10 개의 십진숫자를 원소로 함으로 소스알파벳(제2-4절 참조)에는 모두 26／1／10Ａ37 개의 심볼이 존재한다.

[eqn: S ``=`` \{`0,`1,`2,` cdots,` 9, `\SP,` A,` B,` C,` cdots,` Z`\} ``:`` 37``\symbols]	(3-12)

다행히도, 37은 하나의 소수(prime number)이며, 우리는 이러한 사실을 이용하여 다음과 같은 방법으로 오류검출 체계를 구축할 수 있다.

우선 메시지를 일정한 길이의 문자열(character string)로 나누고 각 문자열의 최하위에는 문자열 당 한 문자씩의 검사문자(check character)를 부여하기로 한다. 문자열 내의 각 문자는 식(3-12)에 주어진 소스알파벳의 순서에 따라 0, 1, 2, …, 36 으로 코딩된다. 또한 각 문자는 문자열의 최하위로부터 시작하여 1, 2, 3, … 의 가중치(weights)를 부여한다. 이제 우리는 하나의 문자열에 대하여 가중합(weighted sum)을 구할 수 있고, 그 가중합이 □modulo-37□이 되도록(37로 나누어 떨어지도록) 최하위에 검사문자를 추가하는 것이다. 이 때 검사문자가 공백(SP)이 되더라도, 이는 검사문자가 없는 것이 아니라 코드 □10□을 갖는 검사문자로 취급되어야 함을 명심하라. 그림 3-5는 이러한 가중치 코드의 형성과정을 보여주고 있다.

X1	X2	X3	···	Xn-1	Xn		□ 문자열의 형성
× n	× n-1	× n-2		× 2	× 1		□ 가중치
문 자 열					검사 문자

* 가중합 =[eqn: n`X_1 ``+``(n`-`1)`X_2 ``+`` cdots ``+`` 2`X_n-1 ``+``X_n ```(mod-37)]

그림 3-5  가중치 코드

수신측에서는 수신된 문자열 별로 다시 가중합을 구하여 □modulo-37□이 성립되는가를 확인하고, 만일 이를 만족하지 않는다면 위에 예시하였던 종류의 오류가 발생되었다고 판단하는 것이다. 또한 오류가 검출되면 앞에서와 같은 방법으로 재전송이나 재처리를 요구하게 된다.

[예제 4]  다음과 같은 문자열에 대하여 가중치 코드를 적용하고자 한다.

문자열 : NO 557

(1) 가중합을 구하고 검사문자를 부여하여 전송되는 메시지를 구하라.

(2) Key Board 조작의 실수에 의하여 문자열이 □NO 577□로 잘못 전송되었을 경우 수신측에서 이를 검출하는 과정을 보여라.

[풀이]

(1) 검사문자를 □라 하고 식(3-12)의 코드와 그림 3-5와 같은 가중치를 부여하면 가중합은 다음과 같다.

가중합 = N×7 + O×6 + SP×5 + 5×4 + 5×3 + 7×2 + □

= 24×7 + 25×6 + 10×5 + 5×4 + 5×3 + 7×2 + □

= 417 + □

가중합이 modulo-37이어야 함으로  □ = 27 이며 이에 해당하는 문자는 □Q□이다. 따라서 전송되는 메시지는 □NO 557Q□가 된다.

(2) 수신된 메시지는 □NO 577Q□일 것임으로 수신측에서 계산된 가중합은 다음과 같다.

가중합 = 24×7 + 25×6 + 10×5 + 5×4 + 7×3 + 7×2 + 27

= 450 = 6 (modulo-37)

따라서 수신된 메시지는 오류를 포함한다.

이와 같은 원리로 작성된 가중치 코드가 위에서 언급한 운용상의 오류들을 검출할 수 있다는 사실은 쉽게 설명된다. 만일 운용상의 실수에 의하여 문자열의 k 번째 문자와 (k／1) 번째 문자가 서로 바뀌었다고 가정하여 보자. 원래의 가중합은

[eqn: S_1 ~=~ cdots ``+`` k`s_k ``+`` (k`／`1) `s_k／1 ``+`` cdots]	(3-13)

으로 주어지며, 여기서 [eqn: s_k ~및 ~ s_k+1]은 각각 k 번째 문자와 (k／1) 번째 문자의 코드값이다.

한편 조작의 실수에 의하여 뒤바뀐 문자열의 가중합은

[eqn: S_2 ~=~ cdots ``+`` (k`+`1)`s_k ``+`` k`s_k／1 ``+`` cdots]	(3-14)

와 같이 계산된다.

가중치 코드의 원리에 따라 [eqn: S_1]은 37로 나누어 떨어지는 수이고, 이들 두 가중합의 차는

[eqn: S_2 ``-`` S_1 ~=~ s_k ``-``s_k／1]	(3-15)

이 된다.  여기서 [eqn: s_k ~및 ~ s_k+1]은 모두 0 ∼ 36 사이의 값이므로 두 가중합의 차는 37로 나누어 떨어지지 않을 것이다.  단, [eqn: s_k ``=`` s_k+1]인 경우에는 이웃한 두 개의 문자가 서로 같으므로 바뀌어도 오류가 아니며, 이 때 두 가중합의 차는 0(mod-37)이 된다.

따라서 조작의 실수에 의하여 이웃한 두 개의 문자가 뒤바뀐 오류는 수신측의 가중합 계산에 의하여 쉽게 검출된다.

이와 같은 원리를 사용하면 단지 이웃한 문자끼리의 교환 뿐만 아니라 문자열 내의 어떠한 문자끼리의 교환도 검출해 낼 수 있을 것이다. 또한 영문자 □O□와 숫자의 □0□을 혼동한 오류나 문자를 겹쳐 쓴 오류 등 신호처리의 과정에 운용자의 조작이 개입될 때 발생하는 일반적 오류들을 모두 검출할 수 있다.

요컨대 가중치 코드의 원리는 송신측과 수신측에서 상호 약속된 방법으로 문자열의 가중합을 구하여 이를 mod-37로 처리하는 것이다. 위의 [예제 4]에서와 같이 문자열의 길이가 비교적 짧은 경우에는 가중합을 구하는 과정이 그리 복잡하지 않지만, 문자열이 길어지면 위의 방법에 따라 가중합을 구하는 것이 용이하지 않음을 알 수 있다. 더욱이 이러한 처리를 기계적으로 하기 위하여 위의 방법을 적용한다면 다수의 곱셈을 수행하게 됨으로 연산시간도 길어지게 된다.

문자열의 가중합(weighted sum)을 구하는 쉽고도 간단한 방법으로 소위 □Progressive digiting□ 알고리듬이 흔히 쓰인다. 주어진 문자열의 최상위 문자로부터 차례로 나열하여 첫 번째 열(column)을 구성하고, 각 문자에 그 바로 하위의 문자를 차례로 더하여 두 번째 열(합)을 형성시킨다. 이 과정을 한 번 더 진행하여 세번째 열(합의 합)을 형성시키면, 이 세 번째 열의 마지막 원소가 문자열의 가중합이 된다.

예를 들어서 문자열 □wxyz□에 대하여 □Progressive digiting□ 과정을 적용하면 아래 표와 같이 나타난다.

문자열            합              합의 합

w              w                 w

x             w／x             2w／x

y           w／x／y         3w／2x／y

z         w／x／y／z     4w／3x／2y／z

세번째 열(합의 합)의 마지막 원소는 우리가 구하고자 하는 가중합이 됨을 알 수 있다. 이 과정에 있어서 모든 계산은 덧셈이며 각 열을 형성하는 알고리듬이 체계적인 순환과정으로 구성되므로 기계적인 처리에 있어서 대단히 유리하다.

□Progressive digiting□ 과정에 의하여 가중합이 계산되는 원리는 이러하다.

우선, 첫 번째 열의 원소들을 위로부터 차례로 더하여 얻어지는 두번째 열의 마지막 원소가 구해지면 각 문자는 한 번씩 더해진다. 이어서 두 번째 열의 원소를 차례로 더하여 얻어지는 세 번째 열에서는 문자열의 최상위 문자로부터 첫 번째 문자는 n 번, 두 번째 문자는 n-1 번, 그 다음은 n-2 번, …, 마지막(n 번째) 문자는 1 번씩 각각 더하여 진다. 따라서 이러한 과정의 최종 결과는 우리가 구하고자 하는 가중합과 동일하며, 위 표에서 가중합은 세 번째 열(합의 합)의 마지막 원소로 나타나게 되는 것이다.

위의 [예제 4]에서 형성된 전송 메시지 □NO 557Q□에 대하여 □Progressive digiting□ 과정을 적용하여 가중합(weighted sum)을 구해 보면 다음에 제시한 표와 같다. 위에서 설명한 바와 같이, 이 표의 두 번째 열은 첫 번째 열을 차례로 더하여 얻어진 것이며, 세 번째 열은 다시 두 번째 열을 차례로 더하여 얻어진 것이다. 결국, 세 번째 열의 마지막 원소인 □444□는 전송 메시지 □NO 557Q□의 가중합이다. □444□는 □37□로 나누어 떨어지는 수이므로 mod-37을 만족한다. 이는 가중치 코드의 원리에 의하여 오류가 없음을 나타낸다.

문자열	합	합의 합

N=24	24	24

O=25	49	73

sp=10	59	132

5=5	64	196

5=5	69	265

7=7	76	341

Q=27	103	444

[예제 5]  다음과 같은 문자열에 대하여 가중치 코드를 적용하고자 한다. □Progressive digiting□ 알고리듬을 이용하여 검사문자를 부여하고 전송되는 메시지를 구하라.

문자열 : WEIGHTED CODE

[풀이]

검사문자를 □라 하고 주어진 문자열에 대하여 Progressive digiting 과정을 진행하면 다음과 같다.

문자열	합	합의 합

W=33	33	33

E=15	48	81

I =19	67	148

G=17	84	232

H=18	102	334

T=30	132	466

E=15	147	613

D=14	161	774

sp=10	171	945

C=13	184	1129

O=25	209	1338

D=14	223	1561

E=15	238	1799

□	238+□	2037+□

가중합 □2037+□□는 □37□로 나누어 떨어져야 하므로 □ = 35 가 되고, 이에 해당하는 문자는 □Y□이다. 따라서 전송되는 메시지는 □WEIGHTED CODEY□가 된다.

이 절에서 설명한 코딩방식은 전형적인 백색잡음에 대응하기 위한 것이 아니고, 인간의 작업상 발생되는 오류의 검출을 위한 코딩방식의 예이다. 여기서 우리는 코딩방식이 잡음의 특성에 따라 얼마나 판이하게 달라지는가 하는 사실을 볼 수 있다. 일반적으로 오류검출코드 혹은 오류정정코드라 하면 비교적 세련되고 복잡한 구조를 가지고 있는데 이들은 거의 백색잡음의 존재를 가정하고 설계된다. 따라서 독자들은 오류제어 체계는 모두 그와 같이 설계되어야 하는 것으로 착각하기 쉬운데, 이는 그 잡음 조건에 대한 기본적인 가정을 망각하기 때문에 일어나는 실수이다. 요컨대 오류제어를 위한 코드체계는 그 시스템이 놓인 잡음환경에 따라 크게 달라질 수 있음을 명심하라.

ISBN (International Standard Book Number)  운용자의 작업이 결부되는 경우에 사용하는 또 하나의 가중치 코드로써 국제표준 도서번호(ISBN)를 들 수 있다. 이는 오늘날 발행되는 거의 모든 책에 표시되고 있는데, 보통 10 자리 숫자코드로써 출판사에서 부여한다. 전형적인 예로서

ISBN 0-1321-2571-4

를 살펴 보기로 하자.

여기서 □-□은 다른 위치에 표시될 수도 있으며 그 위치는 중요하지 않다. 제일 앞 쪽의 숫자 □0□은 발행국을 표시하는 것으로 미국 혹은 영어 문화권의 국가임을 나타낸다. 그 다음 두 자리 숫자 □13□은 출판사를 표시하는 것으로 □Prentice-Hall□을 표시하고, 그 다음의 6자리 숫자 □21-2571□은 출판사가 부여한 그 책의 도서번호이다. 그리고 맨 마지막의 □4□는 앞에서 논의하였던 가중치 코드의 검사번호(check number)이다.

다시 말해서 국제표준 도서번호는 십진수만을 사용하는 가중치 코드의 일종으로서, 위에서 논의하였던 원리에 의하여 운용자의 실수로 발생되는 오류를 검출하기 위한 코드체계이다. 여기서 10은 소수(prime number)가 아니기 때문에 가중치 코드의 modulus로 사용하기 곤란하여  mod-11을 사용한다(11은 소수임). 이렇게 하면 가중치 코드의 검사번호가 10이 되는 경우도 발생하게 되는데 이 때에는 검사번호를 □X□로 부여한다.

서점에서 책을 고르다가 다음과 같은 국제표준 도서번호를 발견하였다고 하자.

ISBN  89-353-0154-X

이 번호가 올바른 ISBN인지 알아보기 위해서는 다음과 같이 Progressive digiting 과정을 적용하면 될 것이다.

숫자열	합	합의 합

8	8	8

9	17	25

3	20	45

5	25	70

3	28	98

0	28	126

1	29	155

5	34	189

4	38	227

X=10	48	275

가중합 □275□는 □11□로 나누어 떨어지는 수이다. 따라서 mod-11을 만족함으로 이는 올바른 ISBN이다.

여기서 우리는 백색잡음이나 전파환경에 의하여 주어지는 잡음이 아닌 인간의 작업상 실수에 의하여 발생되는 오류를 검출하는 또 하나의 코드체계를 볼 수 있다. 결국, 오류검출코드는 잡음이나 오류의 특성에 따라 설계되어야 하며, 그 종류가 다양한 만큼 매우 광범위한 응용분야를 가졌다고 할 수 있다.

[예제 6]  다음과 같은 도서번호에 ISBN의 규칙에 따라 검사번호를 부여하라.

ISBN  0-07-041468-□

[풀이]	검사번호를 N 이라 하고 Progrssive digiting 과정을 적용하면 다음과 같이 나타난다.

숫자열	합	합의 합

0	0	0

0	0	0

7	7	7

0	7	14

4	11	25

1	12	37

4	16	53

6	22	75

8	30	105

N	N+30	N+135

따라서 가중합은 N+135 이며, 이것이 11로 나누어 떨어져야 함으로 N = 8이 되어야 한다. 따라서 구하는 검사번호는 8 이다.

3-7  간단한 오류정정코드

지금까지 우리는 오류검출코드의 여러가지 양상을 살펴 보았다. 앞에서도 언급한 바와 같이 정보통신시스템이 처한 전파환경에 따라서는 오류검출코드에 의한 재전송이나 재처리가 불가능하여 오류정정코드(error-correction code)를 사용해야만 하는 경우도 많다. 오류정정코드는 채널을 통과하여 수신된 메시지로부터 직접 오류를 수정하여 원래의 메시지를 복원하는 코드체계이다. 따라서 송신측에 재전송을 요구하거나 확인신호(acknowledgement)를 보낼 필요가 없어 장거리 전송이나 고속 실시간 처리를 요하는 시스템에 널리 사용되고 있다.

가장 간단한 오류정정코드로는 모든 메시지를 세번씩 반복하여 전송하고, 수신측에서 그들 중 다수인 것을 취하는 삼중코드(triplication code)를 들 수 있다. 이러한 삼중코드에 대하여 식(3-5)로 주어지는 Redundancy를 구해보면

[eqn: R_T ~=~ {3`k} over k ~=~ 3]	(3-16)

와 같이 계산된다.

이 코드체계에 의하여 독립된 단일오류를 정정할 수 있다는 것은 명백하다. 그러나 식(3-16)에서 보는 바와 같이, 이 코드체계는 정보율(information rate)에 있어서 매우 비효율적이라는 사실 또한 명백하다.

다음으로 간단한 오류정정코드는 사각형코드(rectangular code)이다. 이 코드체계에서  정보는 (m１1)×(n１1)의 배열로 형성된다. 이러한 배열의 형태는 이 코드체계의 원리를 개념적으로 설명하기 위한 것이며, 실제의 전송에 있어서는 일렬로 늘어선 정보 bits를 차례로 배열한 것이다. 그림 3-6은 사각형코드의 배열 형태를 보여주고 있다. 배열의 각 행(row) 별로 한개씩의 패리티 검사 bit를 첨가하여 각 행이 m bits로 되게 하고, 각 열(column) 별로 한개씩의 패리티 검사 bit를 첨가하여 각 열이 n bits가 되도록 한다. 여기서 최하단 우측에 첨가된 패리티 bit는 배열의 형태를 맞추기 위한 것으로 실제의 오류정정 과정에서는 불필요한 bit이다.

그림 3-6  사각형 코드

각 행과 열에서의 패리티 검사는 독립적으로 수행되며, 임의의 단일오류가 발생되면 하나의 행과 하나의 열에 대한 패리티 검사가 실패(fail, odd parity)로 나타나게 될 것이다. 이 때 수신측은 패리티 검사가 실패한 열과 행이 만나는 위치에서 오류가 발생하였음을 알 수 있고, 그 위치의 bit를 교환(□0□이면 □1□로, □1□이면 □0□으로)함으로써 이를 정정할 수 있는 것이다.

그림 3-6에 도시된 사각형코드의 Redundancy는 다음과 같이 계산된다.

[eqn: R_R ~=& {m`n} over {(m`-`1) ` (n`-`1)} ## =&1 ``+`` 1 over {m`-`1} ``+`` 1 over {n`-`1} ``+`` 1 over {(m`-`1)`(n`-`1)}]	(3-17)

여기서 첫번째 항인 1을 제외하면 초과 Reduadancy가 되며, 블록의 구성을 정사각형에 가깝게 설계할수록 Redundancy는 작아진다. 따라서 최소의 Redundancy는 한변이  n bits로 구성된 정사각형코드(square code) 일 때 주어지며 이는

[eqn: R_S ~=~ n^2 over {(n`-`1)^2}]	(3-18)

와 같이 계산된다.

사각형코드의 원리를 좀 더 상세히 관찰하면, 그림 3-7과 같이 패리티 검사 bit를 대각선에 늘어놓은 삼각형코드(triangular code)를 생각할 수 있다. 삼각 배열의 첫번째 행에는 n-1 개의 정보 bits가 배열되고 그 마지막에 하나의 패리티 검사 bit가 부여된다. 그 하위의 행들에는 정보 bits를 한 개씩 줄여서 하나의 패리티 검사 bit와 함께 배열한다. 이렇게 하여 부여된 대각선 상의 n 개의 패리티 검사 bit들은 자신이 포함된 행과 열에 대하여 패리티 검사를 수행하도록 한다.

임의의 단일오류가 발생되면 대각선 상의 패리티 검사 bits 중 두 개가 패리티 검사에 실패하게 되고, 이들을 포함하는 행과 열이 만나는 위치에서 오류가 발생하였음을 알 수 있는 것이다. 오류의 위치를 알게 되면 앞에서와 같이 그 위치에 있는 bit를 교환함으로써 그것을 정정할 수 있다.

그림 3-7  삼각형 코드

이렇게 하면 앞에서 설명한 사각형코드와 동일한 오류정정 능력을 가지면서도 낮은 Redundancy를 갖는 코드를 얻을 수 있을 것이다. 그림 3-7로부터 삼각형코드의 정보 bit는 n(n１1)/2 개이며, 전체 bit 수는 n(n+1)/2 개이다. 따라서 이 코드체계의 Redundancy는

[eqn: R_T ~=~ {n`(n`+`1)} over {n`(n`-`1)} ~=~ 1 ``+`` 2 over {n`-`1}]	(3-19)

와 같이 주어진다. 이를 위의 식(3-17) 및 식(3-18)과 비교하여 보면 삼각형코드가 사각형코드에 비하여 낮은 Redundancy를 가짐을 알 수 있다.

사각형코드로부터 삼각형코드를 유도했던 과정을 좀 더 분석하여 보면, 이들보다 더욱 효율적인 코드체계도 존재할 것임을 짐작할 수 있고, 자연적으로 □Redundancy를 감소시키는 관점에서 가장 효율적인 코드는 무엇일까?□ 하는 의문점이 생긴다.

그림 3-8과 같은 정육면체(cube)를 생각하여 보자. 정육면체의 내부에는 정보 bits가 차례로 배열되고, 하나의 꼭지점에서 만나는 세 변(그림에서 ×로 표시) 상에 패리티 bits를 배열한다. 각 패리티 bits는 자신을 포함하는 절단면 상의 모든 bits에 대하여 패리티 검사를 수행하게 된다. 만일 전송 중 하나의 정보 bit에서 오류가 발생하였다고 가정하면 이것을 포함하는 세 개의 절단면에 대한 세 개의 패리티 검사가 실패하게 되고, 수신측은 패리티 검사가 실패한 세 개의 절단면이 만나는 위치의 bit를 수정하게 된다.

그림 3-8  육면체 코드

그림 3-8에서 보는 바와 같이, 육면체코드(cubic code)의 패리티 검사 bit는 3n１2 개이며, 전체 bit 수는 n3 개이다. 따라서 이 코드체계의 Redundancy는

[eqn: R_C ~=~ {n^3} over {n^3 `-` (3n`-`2)} ~=~ 1 ``+`` {3n `-` 2} over {n^3 `-` 3n `+` 2}]	(3-20)

와 같이 주어진다. 한 변에 위치하는 bit 수 n이 커지면 이 코드체계의 초과 Redundancy는 약 3/n2에 해당한다.

표 3-1에는 지금까지 설명한 사각형코드, 삼각형코드 및 육면체코드에 대하여 파라미터 n에 따르는 정보 bit 수와 패리티 검사 bit 수를 비교하여 나타내었다.

표 3-1  단일오류 정정코드의 효율성 비교

n	사각형코드	삼각형코드	육면체코드
	정보 검사 (n１1)2 2n１1	정보 검사 n(n１1)/2 n	정보 검사 n3１3n／2 3n１2
2 3 4 5 6 7 8 9 10	1 3 4 5 9 7 16 9 25 11 36 13 49 15 64 17 81 19	1 2 3 3 6 4 10 5 15 6 21 7 28 8 36 9 45 10	4 4 20 7 54 10 112 13 200 16 324 19 490 22 704 25 972 28

이 표에서 보는 바와 같이, 파라미터 n이 증가함에 따라 육면체코드의 효율은 다른 두 가지 체계에 비하여 더욱 증가하게 된다. 이처럼 3 차원의 코드의 효율이 2 차원 코드에 비하여 우수하다면 코드체계의 차원을 좀 더 늘려감으로써 더욱 효율적인 코드를 얻을 수 있을 것이다. 물론 실제의 메시지는 3 차원 혹은 그 이상의 차원으로 배열되어 전송되는 것은 아니다. 실제의 전송은 언제나 일렬로 나열된 상태에서 이루어지지만, 단지 메시지가 개념적으로 그와 같이 배열되어 적당한 패리티 검사를 수행한다는 의미이다.

육면체코드의 개념을 확장하면 4 차원 공간에서 구성된 코드체계의 초과 Redundancy는 약 4/n3가 됨을 짐작할 수 있다. 이러한 방법으로 계속 차원을 높여가면 결국 가능한 최상의 차원에서 가장 효율적인 코드가 생성된다는 결론에 도달하게 된다. 이 때 전체 bit 수 2n에 대하여 (n／1) bit의 패리티 검사가 필요하며, 각각의 패리티 검사는 그것을 포함하는 모든 방향의 정보 bit들과 자기 자신을 포함하여 검사를 수행하게 될 것이다.

만일 이러한 패리티 검사 bit들이 일정한 규칙에 따라 배열된다면, 그들은 패리티 검사에 의하여 Syndrome(징후)이라 불리우는 숫자를 생성하게 되며, 우리는 결국 이 Syndrome에 의하여 오류의 위치를 표시하게 되는 것이다. 여기서 Syndrome은 각각의 패리티 검사에서 성공이면 □0□, 실패이면 □1□을 부여함으로써 생성된다. 따라서 이들 (n／1) 개의 검사 bit는 (n／1)-bit 짜리 Syndrome을 생성하며, 이 숫자는 2n／1 개의 서로다른 상태를 표시하게 될 것이다. 이것은 단일오류가 발생할 수 있는 2n 개의 위치와 오류가 발생되지 않는 경우를 포함한 2n／1 보다 큰 수이다.

이들 패리티 검사 bit는 메시지 내에서 정보 bit 들과 혼합되어 전송된다. 따라서 전송에 있어서는 정보나 패리티의 구별이 없이 모든 bit가 동일하게 취급되는 것이다.

이상에서 논의된 접근방법에서 Syndrome이 표시할 수 있는 위치(2n／1 가지)는 실제의 오류가 발생할 수 있는 위치(2n 가지)와 오류가 발생하지 않는 경우(1 가지)를 합한 수의 약 두 배 정도가 된다. 따라서 거의 factor-2 정도의 효율저하를 갖게 된다고 할 수 있다. 그럼에도 불구하고 이러한 개념은 다음 절에서 새로운 오류정정코드를 설계하는 기반으로 사용하게 될 것이다.

3-8  Hamming 오류정정코드

이 절에서는 앞 절의 내용을 기초로 오류정정코드의 설계를 위한 대수학적 접근방법(algebraic approach)에 대하여 취급하고, 백색잡음의 가정 하에서 블록 내의 단일오류(single error)를 정정할 수 있는 최적의 오류정정코드를 설계하고자 한다.

하나의 블록에 대하여 m 개의 독립적인 패리티 검사를 수행한다고 가정하자. 여기서 □독립적□이라는 말은 각각의 패리티 검사 위치가 완전히 중복되지 않도록 수행된다는 의미이다. 만일 임의의 패리티 검사들을 결합하여 다른 패리티 검사를 대신할 수 있다면 이들은 서로 독립적이라고 할 수 없다.

예를 들어서 세 개의 패리티 검사 위치를 다음과 같이 택한다고 가정하면

check-1 : 1, 2, 5, 7

check-2 :      5, 7, 8, 9

check-3 : 1, 2,      8, 9

□check-1□과 □check-2□를 결합하여 □check-3□를 대신할 수 있으며, 이에 따라 세 번째 패리티 검사는 새로운 정보를 전혀 제공하지 못하는 불필요한 검사가 되고 만다. 이러한 패리티 검사를 서로 종속(dependent)되었다고 한다. 그러므로 오류정정코드의 패리티 검사 위치를 설정할 때 종속적 패리티 검사가 되지 않도록 주의하여야 한다.

m 번의 패리티 검사 각각에 대하여 성공(success or even)이면 □0□, 실패(fail or odd)이면 □1□을 부여하는 방법으로 m-bit Syndrome을 형성시켰다고 하면, 이는 2m 개의 서로 다른 상태를 표시할 수 있게 된다. 한편 우리가 하나의 n-bit 블록에서 발생된 단일오류의 정정을 원한다면, 오류의 발생이 가능한 n 개의 위치와 오류가 발생하지 않는 상태를 포함하여 (n／1) 개의 서로 다른 상태를 표시할 수 있어야 한다. 따라서 이와 같이 형성된 Syndrome이 오류의 발생 위치를 정확히 표시하도록 하기 위해서는 우선적으로 다음의 부등식이 성립하여야 할 것이다.

[eqn: 2^m````□````n`+`1]	(3-21)

이 절을 통하여 우리는 식(3-21)의 등식부분을 정확히 만족하는 코드체계를 구성할 것이다. 이는 결국 Syndrome의 기본조건을 만족하는 단일오류 정정코드를 설계하는 문제의 특수해(particular solution)가 될 것이며, 이 코드체계를 Hamming 오류정정코드라고 부른다.

Hamming 코드의 가장 기본적인 생각은 Syndrome이 표현하는 십진수가 바로 오류 발생 위치를 표시하고, 만일 Syndrome의 모든 bit가 □0□이면 오류가 발생하지 않은 경우를 표시하도록 설계하는 것이다.

그렇다면 메시지 블록의 어느 위치에서 패리티 검사를 수행해야 할 것인가? 표 3-2에는 블록 내의 각 위치를 표시하는 Syndrome의 이진수 표현을 나열하였다. 이 표는 단순히 십진수의 이진표현을 대응시켜 나열한 것이지만 이를 자세히 살펴보면 다음과 같은 중요한 사실을 알 수 있다. 즉, Syndrome이 오류가 발생한 위치를 표시하도록 하기 위해서는 그 이진수 표현의 최하위가 □1□이 되는 위치들에 대하여 첫번째 패리티 검사를 적용해야 한다. 왜냐하면 첫번째 패리티 검사는 Syndrome의 첫번째 bit를 형성하며, 만일 이들 위치 중 하나에서 오류가 발생하였다면 바로 Syndrome의 첫번째 bit가 □1□이 되어야 하기 때문이다.

표 3-2  검사 위치와 Syndrome의 이진수 표현

검 사 위 치	Syndrome의 이진수 표현
1 2 3 4 5 6 7 8 9 10 □	0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 □

동일한 원리에 의하여 두번째 패리티 검사는 Syndrome의 이진수 표현의 하위로부터 두번째 열이 □1□이 되는 위치들에 대하여 수행되어야 할 것이다. 이러한 원리는 세번째, 네번째 □ 패리티 검사들에 대해서도 그대로 적용된다.

따라서 제 1의 패리티 검사는 1, 3, 5, 7, 9, 11, 13, 15 □ 등의 위치에 대하여, 제 2의 패리티 검사는 2, 3, 6, 7, 10, 11, 14, 15 □ 등의 위치에 대하여, 제 3의 패리티 검사는 4, 5, 6, 7, 12, 13, 14, 15 □ 등의 위치에 대하여, 제 4의 패리티 검사는 8, 9, 10, 11, 12, 13, 14, 15 □ 등의 위치에 대하여, ··· 각각 수행되어야 할 것이다.

Hamming 오류정정코드에 의한 인코딩 및 디코딩 과정을 구체적으로 설명하기 위하여 가장 간단한 형태인 7-bit Hamming 코드를 예시하기로 한다. 표 3-3은 4-bit 정보 □1011□에 대하여 Hamming 오류정정코드를 적용하여 전송 중 발생된 단일오류를 정정하는 과정을 단계별로 나타내고 있다.

우선 식(3-21)의 등식부분을 만족해야 하므로 23=(4／3)／1Ａ8 과 같이 쓸 수 있다. 그러므로 패리티 검사 bit의 수(Syndrome의 bit 수)는 mＡ3이며, 블록의 전체 bit 수는 nＡ7이 된다.

표 3-3  7-bit Hamming 코드의 인코딩과 디코딩

<인코딩 과정>

1   2   3   4   5   6   7	위  치

1       0   1   1	정보 bits

0   1   1   0   0   1   1	Encoded bits

<전송 및 수신>

□	오  류

0   1   0   0   0   1   1	Received bits

<디코딩 과정>

패리티 검사

Check-1	1  3  5  7

0  0  0  1     Fail □ 1

Check-2	2  3  6  7

1  0  1  1     Fail □ 1

Check-3	4  5  6  7

0  0  1  1     Success □ 0

∴  Syndrome =

0	1	1

= 3 (오류발생위치)

정정(오류발생위치에 1을 더함)

0   1   1   0   0   1   1	정정된 메시지

□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

또한 메시지 블록에서 패리티 검사 bit들이 놓일 위치는 1, 2, 4 위치로 정하기로 한다. 이에 따라 정보 bit들은 각각 3, 5, 6, 7 위치에 놓이게 된다. 즉, 정보를 인코딩하기 위하여 정보 bit들은 3, 5, 6, 7 위치에 두고, 위에서 설명하였던 방법에 의하여 패리티를 계산하여 각각 1, 2, 4 위치에 두는 것이다.

우리는 이 메시지 블록을 □--1-011□라 표기하기로 한다. 여기서 □-□는 패리티 검사 bit 들이 놓일 위치를 나타낸다.

제 1의 패리티는 1, 3, 5, 7 위치에 대하여 짝수 패리티가 되도록 맞추어지므로 블록의 첫번째 bit는 □0□이 되어 전체가 □0-1-011□이 된다. 제 2의 패리티는 2, 3, 6, 7 위치에 대하여 부여되고 그 결과는 □011-011□이 된다. 마지막으로 제 3의 패리티는 4, 5, 6, 7 위치에 대하여 부여되고 결국 □0110011□이라는 코드화된 블록을 얻는다.

이렇게 작성된 코드가 과연 전송 중에 발생하는 단일오류를 정정할 수 있는가를 시험하기 위하여 1-bit 오류를 가정하여 보자. 즉, 코드화된 메시지 □0110011□이 채널을 통하여 전송되는 도중 세번째 위치에서 오류가 발생하게 되었다고 하자(1→0). 이렇게 되면 수신측에서 받는 메시지는 오류를 포함한 □0100011□이 될 것이다.

이 때 수신측에서는 송신측과 똑같은 방법에 의하여 패리티를 검사하고 오류의 위치를 찾아내어 이를 정정하여야 한다. 제 1의 패리티 검사는 1, 3, 5, 7 위치에 대하여 실시되며, 그 결과는 실패(fail)이다. 따라서 Syndrome의 최하위 bit는 □1□이 된다. 제 2의 패리티 검사는 2, 3, 6, 7 위치에 대하여 실시되며 역시 실패이다. 따라서 Syndrome의 두번째 bit도 □1□이 된다. 마지막으로 제 3의 패리티 검사는 4, 5, 6, 7 위치에 대하여 실시되고 그 결과는 성공(success)이다. 그러므로 Syndrome의 최상위 bit는 □0□이 된다. 결국 형성된 Syndrome은 □011□이 되며, 이는 십진수로 □3□을 나타낸다. 따라서 블록의 세번째 위치에서 오류가 발생되었음을 알 수 있으며, 우리는 세번째 위치에 □1□을 더함으로써(논리덧셈) 발생된 오류를 정확히 정정할 수 있는 것이다. 이렇게 되면 수신측에서는 재전송 요구 없이 송신측에서 전송한 그대로의 메시지를 얻게되며, 여기서 패리티 검사 bit로 사용된 1, 2, 4 위치를 제거하게 되면 원래의 정보 □1011□을 3, 5, 6, 7 위치로부터 추출할 수 있게 된다.

이 때, 패리티 bit들도 정보 bit와 똑같은 조건으로 전송되므로 패리티 bit에서 오류가 발생되더라도 같은 방법에 의하여 정정된다. 따라서 메시지가 일단 코드화되면 실제의 정보와 패리티 사이에는 아무런 차이점도 없이 전송된다는 사실이 다시 한번 입증된다.

Hamming 코드의 가장 우수한 점은 송신측의 인코딩 과정이나 수신측의 디코딩 과정이 모두 간단한 논리적 산술(logical arithmetic)에 의하여 이루어 진다는 점이다. 이는 그 인코더와 디코더의 하드웨어 구성이 모두 간단한 논리회로에 의하여 실현될 수 있음을 말해주므로 단일오류 정정을 위한 코드체계로 가장 널리 사용되고 있다. 또한 Syndrome은 전송된 메시지의 내용과는 관계없이 오류가 발생한 위치를 직접 표시하므로 Syndrome이 가리키는 위치에 무조건 □1□을 더해주면(논리덧셈) 수신된 메시지를 정정할 수 있는 것이다. 물론 Syndrome의 모든 bit가 □0□이면 해당 블록에 오류가 발생되지 않은 상태이다.

표 3-3에 제시한 예와 같이, 하나의 블록에 4 개의 정보 bit와 3 개의 패리티 검사 bit를 가지는 7-bit Hamming 코드의 경우에는 그 Redundancy가 7/4 로서 비교적 크다. 그러나 만일 하나의 블록에 대하여 10 개의 패리티 검사 bit를 사용한다고 가정하면, 식(3-21)로부터 210Ａn／1이 되어 전체 bit 수는 nＡ1023이 된다. 따라서 패리티 검사 bit 수의 작은 증가에 대해서도 전체 bit 수는 크게 증가하며, 이에 따라 Redundancy는 1023/1013 으로 현저히 감소됨을 알 수 있다.

일반적으로 n-bit Hamming 코드의 Redundancy는

	정보이론

제 4 장 오류정정 코드

[eqn: R_H ~=~ n over {n ``-`` log_2 `(n `+` 1) }]	(3-22)

와 같이 주어짐을 쉽게 입증할 수 있다.

[예제 7]  (15-bit Hamming 코드)

하나의 블록에 11 bits의 정보와 4 bits의 패리티를 포함하는 15-bit Hamming 코드를 이용하여 정보를 전송하고자 한다. 패리티 검사 bit의 위치를 각각 #1, #2, #4, #8로 정하여 표 3-3과 같은 형태의 인코딩, 디코딩 과정을 보여라. 이 때, 정보는 □11010110011□을 사용하고, 전송 중 발생된 단일오류의 위치는 제 8 위치로 하라.

[풀이]

<인코딩 과정>

1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   (위치)

□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

1         1    0    1         0    1    1    0    0    1    1   (정보)

1    0    1    0    1    0    1    0    0    1    1    0    0    1    1

(Encoded bits)

<전송 및 수신>

□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

×                                  (오류발생)

1    0    1    0    1    0    1    1    0    1    1    0    0    1    1   (수신)

□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

<디코딩 과정>

□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

패리티 검사

check-1  :	1    3    5    7    9   11   13   15

1    1    1    1    0    1    0    1         success → 0

check-2  :	2    3    6    7   10   11   14   15

0    1    0    1    1    1    1    1         success → 0

check-3  :	4    5    6    7   12   13   14   15

0    1    0    1    0    0    1    1         success → 0

check-4  :	8    9   10   11   12   13   14   15

1    0    1    1    0    0    1    1         fail   →   1

Syndrome =

1	0	0	0

= 8  → 오류 발생위치

정정된 메시지는 □101010100110011□로서 송신측에서 인코딩된 메시지와 동일하다.

□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

앞에서 설명한 Hamming 코드는 메시지를 블록으로 구분하여 단일오류를 제어하기 위하여 인코딩하는 한가지 특별한 방법에 지나지 않는다. 다시 말해서 이것과 동일한 오류정정 능력을 갖는 등가코드(equivalent code)들이 존재한다는 것이다. 그 한 종류로서 블록 내의 각 bit의 위치를 서로 교환하면 근소한 차이를 나타내는 등가코드가 될 것이다. 만일 블록 내의 모든 bit에 보수(complement : 0 ↔ 1)를 취한다면 또 한 가지의 등가코드를 얻을 수 있을 것이다.

후자의 보수에 의한 등가코드는 원래의 코드체계와 거의 차별성이 없고 그 변환관계도 매우 간단하게 이루어지지만, 전자의 bit 위치교환에 의한 등가코드는 완전히 다른 코드체계를 형성하면서도 단일오류를 정정하는 원래의 능력은 그대로 소유하게 된다. 그러나 그 변환관계는 후자에 비하여 다소 복잡하여 약간의 알고리듬과 메모리를 필요로 하게 된다.

Hamming 코드의 등가코드 중 가장 널리 사용되고 있는 것으로 꼬리검사코드(tail- check code)를 들 수 있다. Hamming 코드의 메시지 블록 내의 모든 패리티 검사 bit들을 최하위로 보내고 그 상위에 정보 bit들이 놓이도록 위치교환을 수행하면 하나의 유용한 등가코드를 얻을 수 있는데 이를 꼬리검사코드라 한다.

그림 3-9는 원래의 Hamming 코드로부터 꼬리검사코드를 얻기 위하여 수행되는 위치교환을 도시하고 있다.

그림 3-9  Hamming 코드의 위치교환 (꼬리검사코드)

이 때 얻어지는 교환순열(interchange permutation)은 다음과 같다.

[eqn: pmatrix {``1 & 2 & 3 & 4 & 5 & 6 & 7~& ## ``5 & 6 & 1 & 7 & 2 & 3 & 4~ &}]	(3-23)

코드화된 각 블록은 전송되기 전에 교환순열을 거쳐 꼬리검사코드로 변환되고, 수신측은 꼬리검사코드로 형성된 각 블록을 받아 동일한 교환순열을 거쳐 원래의 Hamming 코드로 변환한 후 디코딩 과정에 들어간다. 교환순열은 패리티 검사 bit들을 각 블록의 최하위로 보내고 정보 bit들을 각 블록의 상위에 놓이도록 하는 위치교환에 사용될 뿐 아니라, 수신측에서는 역방향으로 사용되어 수신된 블록과 원래의 메시지 블록을 연결하는 역할을 담당한다(masking). 이 때, 패리티 bit 역시 교환된 상태이므로 Syndrome에 의한 오류의 위치도 교환순열에 의하여 제자리를 찾아가야 할 것이다.

블록의 길이가 긴 코드에 대해서는 하나의 블록이 두 개 이상의 word를 차지하는 경우도 있다. 교환순열을 저장하는 기억장치의 크기는 블록의 길이 n에 비례하므로 원래의 Hamming 코드에 비하여 점유되는 기억장치의 양과 처리를 위한 계산의 양이 증가한다. 따라서 블록의 길이가 상당히 긴 코드에 대해서는 원래의 코드체계에 비하여 교환과정 자체가 다소의 부담으로 작용하는 경우도 있을 것이다.

그러나 패리티 bit들을 각 블록의 후단에 두는 꼬리검사코드는 원래의 Hamming 코드에 비하여 여러가지 장점을 가진다. 주지하는 바와 같이 꼬리검사코드는 하나의 블록 내에서 정보(information)와 패리티(parity)의 구분이 명확하여 블록으로부터 정보를 추출할 때 단순히 각 블록의 앞부분을 취하면 된다. 또한 코드화된 메시지를 블록별로 정렬(sorting)하고자 할 때 순수한 정보의 정렬과 일치한다는 장점이 있다.

식(3-23)에 주어진 교환순열을 이용하여 블록 내의 각 bit의 위치를 교환한다는 것은 실제로 교환표(look-up table)에 의한 □찾아보기□를 수행하는 것과 같다. 다시 말해서 꼬리검사코드는 원래의 Hamming 코드에 비하여 교환표를 위한 기억장치와 교환과정을 위한 처리의 부담을 추가로 안고 있으나, 오늘날 반도체 기술의 발달에 의하여 값싸고 용량이 크며 처리속도가 빠른 기억소자들을 손쉽게 구입할 수 있으므로 이러한 부담은 그 장점에 비하여 매우 사소한 것이라 하겠다.

3-9  채널코딩의 기하학적 접근

우리는 앞 절에서 오류정정코드에 관한 대수학적 접근(algebraic approach)을 시도하였다. 이 절에서는 오류검출코드와 오류정정코드를 포함하여 일반적인 채널코딩의 개념을 n-차원 이진공간(n-dimensional binary space)을 이용하여 표현하는 기하학적 접근(geometric approach)을 소개하기로 한다. 채널코딩에 관한 기하학적 접근의 결과는 앞에서 대수학적 접근에 의하여 유도된 결과들과 정확히 일치하지만, 그 접근과정에서 채널코딩에 대한 새롭고 유용한 개념을 도입하게 되는데 이는 뒤에서 정보이론을 다룰 때 필수적인 개념으로 쓰이게 된다.

채널코딩의 기하학적 모델에서 n-bit 코드체계(code system)는 n-차원 이진공간(binary space)에 대응한다. 또한 n 개의 □0□ 혹은 □1□로 구성된 하나의 n-bit 코드는 n-차원 공간의 한 점으로 표현되며, 코드 내의 각 bit는 그 점의 각 좌표를 나타내게 된다.

일반적으로 n-차원 이진공간은 2n 개의 꼭지점을 가지며, 이들 꼭지점 이외에는 아무런 정점도 갖지 않는다. 또한 이들 꼭지점들은 n-bit 코드체계에 존재하는 2n 개의 코드에 대응시킬 수 있다. 그림 3-10에는 1-차원, 2-차원, 3-차원 이진공간이 1-bit, 2-bit, 3-bit 코드체계에 대응하는 관계를 도시하였다.

그림 3-10  n-차원 이진공간과 n-bit 코드체계의 대응관계

(a) 1-차원 이진공간    (b) 2-차원 이진공간    (c) 3-차원 이진공간

이진공간 내의 모든 정점(point)은 변(edge)에 의하여 연결되어 있고, 하나의 변은 그 변에 의하여 연결된 두 정점 사이에 1 bit 차이를 주고 있다. 따라서 1 bit 오류는 이진공간 내에서 원래의 정점으로부터 한 변(one edge) 이동한 새로운 정점에 천이된 것으로 볼 수 있다.

이러한 개념으로 얻어진 n-차원 입방체의 각 정점은 가능한 n-bit 이진수의 모든 나열(2n 개)을 표시한다. 그러나 패리티 검사 bit를 포함하고 있는 오류검출코드나 오류정정코드는 이들 중 일부만을 사용하게 된다. 앞으로 이론을 전개할 때 혼동을 피하기 위하여, n-차원 공간의 정점들 중 채널코드 체계에서 실제로 사용하는 정점을 특별히 코드점(code points)이라 부르기로 한다.

만일 전송 중 블록 내에서 단일오류(single error)가 발생하면, 그 블록을 표시하는 코드점으로부터 입방체의 변을 따라 이웃한 정점으로 천이하게 될 것이다. 이 때 모든 코드점이 다른 코드점으로부터 최소한 두 변(2 bits) 이상 떨어지도록 설정되었다고 가정하면, 단일오류는 오직 한 변 만큼 천이하게 됨으로, 수신된 블록은 코드점으로 설정되지 않은 정점에 위치하게 될 것이며, 이것은 수신측에 의하여 검출 가능한 오류이다. 더 나아가서, 만일 모든 코드점이 다른 코드점으로부터 최소한 세 변(3 bits) 이상 떨어지도록 설정되었다면, 단일오류는 한 변 만큼 천이시킴으로 수신된 블록은 다른 코드점 보다 원래의 코드점과 가까운 정점에 위치하게 되고, 이것은 수신측에 의하여 정정될 수 있는 오류인 것이다.

이러한 논의를 좀 더 효과적으로 전개하기 위하여 다음과 같은 몇가지 정의를 제시하기로 한다.

1. 거리함수(distance function)

거리함수는 두 개의 코드점(code points) 사이에서 정의되며, 이 두 개의 코드점 사이를 천이할 때 지나게 되는 변(edge)의 최소수를 나타낸다. 또한 이것은 두 개의 코드점을 표시하는 이진수 사이에 서로 다른 bit 수 혹은 두 이진수를 논리적으로 더했을 때 나타나는 □1□의 갯수와도 동일하다.

거리함수에 대한 이와 같은 정의에 의하여 모든 거리함수는 다음의 성질을 만족한다.

1) 동일한 코드점 사이의 거리함수는 0 이다.

[eqn: D`(a, ~a`) ``Ａ`` 0]	(3-24)

2) 코드점 x로부터 코드점 y까지의 거리함수는 y로부터 x까지의 거리함수와 동일하다.

[eqn: D`(x, ~y`) ``Ａ``D`(y, ~x`)]	(3-25)

3) 거리함수는 삼각부등식(triangle inquality)을 만족한다. 즉, 두 코드점 a, c 사이의 거리함수와 c, b 사이의 거리함수를 더하면 a, b 사이의 거리함수 보다 크거나 같다.

[eqn: D`(a, ~c`) ``／``D`(c, ~b`) ``□``D`(a, ~b`)]	(3-26)

거리함수는 채널코딩의 기하학적 접근에 있어서 대단히 중요한 개념이며 보통 Hamming 거리(Hamming distance)라 부르기도 한다. 이는 이진 백색잡음의 가정 하에서 채널코드를 설계할 때 임의의 두 코드점 사이에 이격된 거리를 수학적으로 표현하는 데 유용하다.

2. 시스템의 최소거리(minimum distance of a system)

시스템의 최소거리는 하나의 채널코드 체계에 대하여 정의된다. 채널코드에 사용되는 모든 코드점들의 집합을 시스템이라 하며, 시스템 내의 코드점들 사이에 존재하는 최소의 Hamming 거리를 그 시스템의 최소거리라 한다.

최소거리의 개념은 채널코딩의 오류제어 능력을 평가하는 기준으로 쓰인다. 위에서 간단히 언급한 바와 같이, 시스템 내의 모든 코드점이 다른 코드점으로부터 최소한 몇 개의 변 만큼 이격되어 있는가에 따라서 그 채널코드 체계의 오류제어 능력이 달라지게 된다.

시스템 내의 각 코드점이 유일코드(unique code)를 표현하도록 하기 위해서는 최소거리는 1 이상이어야 한다. 또한 최소거리가 2인 코드체계는 단일오류검출(1-bit error detection) 능력을 부여하며, 최소거리가 3인 코드체계는 단일오류정정(1-bit error correction) 능력을 부여한다. 물론 단일오류정정코드는 이중오류검출(2-bit error detection)에도 사용될 수 있다. 개념을 좀 더 확장하여, 최소거리가 4인 코드체계는 단일오류정정 및 이중오류검출(1-bit error correction and 2-bit error detection)을 동시에 실현할 수 있다. 또한 최소거리가 5인 코드체계는 이중오류정정(2-bit error correction) 코드로 사용될 수 있다.

이와 같이 주어진 코드체계의 최소거리는 그 체계가 소유하는 오류제어 능력을 나타낸다. 역으로, 만일 채널코드를 설계할 때 요구되는 오류검출 혹은 정정 능력이 먼저 결정된다면, 그에 따라 필요한 코드체계의 최소거리도 쉽게 결정된다. 또한 이러한 개념은 임의의 최소거리와 그에 따르는 오류제어 능력에 대하여 자연스럽게 확장될 수 있다.

표 3-4는 지금까지 설명한 코드체계의 최소거리와 오류제어 능력의 관계를 정리하여 나타낸 것이다. 여기서 □유일코드□라 함은 코드체계 내의 모든 코드점들이 최소한 1 bit 이상 서로 달라 각 코드점을 유일하게 구별할 수 있는 체계를 말하며, 이 개념은 우리가 다음 장에서 소스코드(source code)을 다룰 때 코드 형성의 기본 조건으로 유용하게 쓰인다. 또한 삼중오류, 사중오류라 함은 각각 3 bits, 4 bits 오류를 말한다.

표 3-4  최소거리와 오류제어 능력

최소거리	오류제어 능력
1 2 3 4 5 7 9 ＞ ＞	유일코드 단일오류 검출 단일오류 정정 혹은 이중오류 검출 단일오류 정정 및 이중오류 검출 (혹은 삼중오류 검출) 이중오류 정정 삼중오류 정정 사중오류 정정 ＞ ＞

3. 구의 표면(surface of a sphere)

하나의 코드점으로부터 동일한 Hamming 거리에 갖는 정점들의 집합을 구의 표면이라고 한다. 이 때 중심되는 코드점을 그 구의 중심(origin), 설정된 □동일한 Hamming 거리□를 그 구의 반경(radius)이라 한다.

예를 들어서 n-차원 코드점 (0, 0, 0 □, 0)을 중심으로 하고 반경이 1인 구의 표면은 n-차원 이진공간에서 원점으로부터 한 변 떨어져 있는 모든 꼭지점들의 집합, 즉 이진열(binary sequence) 내에 오직 하나의 □1□을 포함하고 있는 모든 정점들의 집합을 표현한다. 따라서 이 구의 표면은 n 개의 원소를 갖는다.

4. 구의 체적(volume of a sphere)

하나의 구에 포함되어 있는 모든 정점의 수를 그 구의 체적이라 한다. 일반적으로 반경이 r 인 구는 하나의 중심과 (r - 1) 개의 구각(shells) 및 구의 표면으로 구성된다. 따라서 구의 체적은 구의 중심, 구각 및 구의 표면에 포함되어 있는 모든 정점을 합한 수와 같다.

5. 공간의 체적(volume of a space)

하나의 이진공간(binary space)에 포함되어 있는 모든 정점의 수를 그 공간의 체적이라 한다. 앞에서 설명한 바와 같이, 일반적으로 n-차원 이진공간에는 모두 2n 개의 정점이 존재한다.(그림 3-10 참조) 따라서 n-차원 공간의 체적은 다음과 같이 쓸 수 있다.

[eqn: V_n ~=~ 2^n]	(3-27)

[예제 8] 그림 3-10(c)에 도시된 3-차원 이진공간에 대하여 다음 물음에 답하라.

(a) 원점 (0, 0, 0)을 중심으로 하고 반경이 1인 구의 표면을 구하라.

(b) 정점 (1, 1, 1)을 중심으로 하고 반경이 1인 구의 체적과 반경이 2인 구의 체적을 각각 구하라.

(c) 이 3-차원 공간의 체적을 구하라.

[풀이]

(a) 원점을 중심으로 반경 1인 구의 표면은 원점으로부터 한 변 떨어진 정점들의 집합이므로

[eqn: \{` (1,0,0), (0,1,0), (0,0,1) \}]

이다. 즉 원점과 1 bit 다른 정점들의 집합으로 표현된다.

(b) 위에서와 같은 방법으로 정점 (1, 1, 1)을 중심으로 반경 1인 구의 표면은

[eqn: \{` (0,1,1), (1,0,1), (1,1,0) \}]

와 같이 주어짐으로 구의 체적은 4 이다.

또한 정점 (1, 1, 1)을 중심으로 반경 2인 구는 하나의 구각과 구의 표면을 포함하며 이들은 각각 다음과 같이 나타난다.

[eqn: \{` (0,1,1), (1,0,1), (1,1,0) \}] : 구각

[eqn: \{` (0,0,1), (1,0,0), (0,1,0) \}] : 구의 표면

따라서 구의 체적은 [eqn: 1 `+` 3 `+` 3 ``=``7] 이다.

(c) 식(3-27)을 이용하여 3-차원 공간의 체적은 [eqn: V_3 ``=``2^3 ``=``8] 이다. 이는 그림 3-10(c)에서도 확인된다.

[예제 9]  n-차원 이진공간에 대하여 다음 물음에 답하라.

(a) 원점 (0, 0, …, 0)을 중심으로 하고 반경이 1인 구의 표면을 구하고, 그 원소의 수를 계산하라.

(b) 원점 (0, 0, …, 0)을 중심으로 하고 반경이 1인 구의 체적과 반경이 2인 구의 체적을 각각 구하라.

(c) 임의의 정점을 중심으로 하고 반경이 k인 구의 체적을 구하라. 단 k≤n 이다.

[풀이]

(a) 원점을 중심으로 반경 1인 구의 표면은 원점으로부터 한 변 떨어진 정점들의 집합이며, 이들은 좌표 내에 오직 하나의 □1□을 포함하므로

[eqn: \{` (1,0,0, cdots, 0), (0,1,0, cdots, 0), `cdot cdot cdot, `(0,cdots, 0,1) \}]

와 같이 표현된다. 따라서 이 집합의 원소수는 n 개의 좌표 중 1 개를 택하는 조합의 수와 같으므로 다음과 같이 계산된다.

[eqn: binom n 1 ~=~ n] (개)

(b) 원점을 중심으로 반경 1인 구의 체적은 중심에 있는 하나의 코드점과 표면의 정점을 합한 수이므로

[eqn: 1 ``+`` binom n 1 ~=~ 1 ``+ ``n]

와 같이 계산된다. 또한 반경 2인 구의 체적은 같은 원리에 의하여

[eqn: 1``+``binom n 1``+ ``binom n 2 ~=~ 1 ``+ ``n``+`` {n`(n`-`1)} over 2]

와 같이 계산된다.

(c) 중심이 원점이 아니라 하더라도 위에서 사용한 원리는 그대로 적용된다. 따라서 임의의 정점을 중심으로 반경 k인 구의 체적은 다음과 같이 계산된다.

[eqn: 1``+``binom n 1``+ ``binom n 2``+ ``cdots ``+``binom n k ~=~ sum_i=0^k `binom n i]

제3-8절에서 대수학적 접근으로 유도하였던 Hamming 코드를 지금까지 설명한 기하학적 접근방법으로 설명하여 보자. 우선 Hamming 코드는 단일오류 정정코드이므로 표 3-4로부터 시스템 내의 모든 코드점들은 최소거리 3을 유지하여야 한다. n-차원 공간 내에서 각 코드점들이 최소거리 3을 유지하기 위해서는 각 코드점을 중심으로 하는 반경 1인 구(unit sphere)가 서로 중첩되지 않아야 할 것이다. 또한 이러한 구들이 n-차원 공간 내에 최소한 서로 다른 코드점의 수(2k 개) 만큼 존재하여야 한다. 따라서 단일오류 정정코드에 대해서는

[eqn: {공간의 ~체적 }over {반경 ~1인 ~구의 ~체적 } ``□`` 코드점의 ~수]	(3-28)

와 같은 관계가 성립한다.

[예제 9]에서 유도했던 바와 같이, n-차원 공간에서 반경 1인 구의 체적은 (1／n)이 며, n-차원 공간의 체적은 2n이므로 식(3-28)은 다음과 같이 쓸 수 있다.

[eqn: 2^n over {n``／``1} ``□```2^k]	(3-29)

한편 블록 전체의 bit 수는 패리티 검사 bit 수와 정보 bit 수의 합으로 표시되므로

[eqn: n ``Ａ``m``／``k]	(3-30)

이다. 이 식을 식(3-29)에 대입하여 정리하면

[eqn: 2^m／k ``□```2^k ``(n`／`1)]	(3-31)

와 같이 나타나고, 양변을 2k으로 나누면

[eqn: 2^m ``□```n``／``1]	(3-32)

을 얻는다. 이 부등식은 우리가 앞 절에서 대수학적 접근으로 유도하였던 식(3-21)과 일치하며, 이는 단일오류 정정코드의 설계를 위한 기본관계식(fundamental relationship)이라 할 수 있다.

이제 이러한 개념을 확장하여 다중오류(2 bits 이상)를 정정하는 코드체계에 대하여 살펴보기로 하자. 이중오류 정정코드(2 bits error correcting code)는 표 3-4로부터 시스템 내의 모든 코드점들이 최소거리 5를 유지하여야 한다. 이것은 n-차원 공간에서 각 코드점을 중심으로 하는 반경 2인 구들이 서로 겹치지 않아야 함을 나타내며, 이를 식으로 표시하면 식(3-28)에서 구의 반경 만이 2로 바뀌어 표시된다. 따라서 이중오류 정정코드의 설계를 위한 기본관계식은 다음과 같이 표현된다.

[eqn: 2^n over {1``／``n``／``n`(n``-``1`)/2 } ``□```2^k]	(3-33)

요컨대 이 부등식은 이러한 bit 수로 코드체계가 실현됨을 의미하는 것이 아니고, 단지 이중오류 정정코드를 설계하기 위해서는 코드점의 수를 이 부등식을 만족하도록 설정해야 한다는 것이다. 즉 n-bit 블록 내에 설정할 수 있는 정보 bit 수 k의 상한(upper bound)을 알려주는 것이다.

이러한 개념은 더 많은 오류를 정정할 수 있는 코드체계에 대해서도 자연스럽게 확장될 수 있으며, 그 결과로 해당 코드체계의 기본관계식을 얻을 수 있는 것이다.

어떤 코드체계에 대한 기하학적 접근에 있어서, 만일 코드점을 중심으로 한 구들이 n-차원 공간의 모든 정점(2n 개)을 포함한다면, 우리는 이를 완전코드(perfect code)라 부른다. 일반적으로 완전코드는 대칭성(기하학적 모델에 있어서 각 정점은 모두 동등하게 취급됨)이 강하며 효율적이고 그에 대한 이론도 매우 간단해진다. 그러나 불행하게도 오류정정 능력이 커질수록 이러한 완전코드는 드물고, 식(3-32)나 식(3-33)과 같은 기본관계식의 등식부분을 만족해야만 한다. 우리가 앞 절에서 유도하였던 Hamming 코드는 완전코드의 한 예이다.

기하학적 접근방법의 한 가지 응용으로서 단일오류 정정코드로부터 단일오류정정 및 이중오류검출(1-bit error correction and 2-bit error detection)을 동시에 실현하는 코드체계를 설계하여 보자.

최소거리 3인 코드체계를 단일오류 정정코드로 사용한다면 이중오류에 대한 제어는 전혀 불가능하다. 더구나 이중오류가 발생한 경우 Syndrome은 당연히 0이 아닌 수로 나타나게 되므로 디코더는 해당되는 위치를 찾아 bit 교환(□0□ ↔ □1□)을 수행하게 된다. 따라서 디코딩을 거친 블록에는 최대 3 bits의 오류가 존재할 가능성이 있는 것이다.

만일 동일한 전송시스템에 단일오류정정과 이중오류검출을 동시에 실현하는 코드체계를 사용한다면 대부분의 경우에 전송시스템의 신뢰성을 크게 향상시킬 수 있다. 이러한 코드체계는 단일오류 발생시 Syndrome에 의하여 수신측에서 직접 정정하며, 이중오류 발생시에는 이를 검출하여 재전송을 요구하는 방식으로 운용될 수 있을 것이다.

표 3-4에 명시된 바와 같이, 이러한 코드체계를 위한 조건은 최소거리 4에 해당하므로 최소거리 3인 단일오류 정정코드를 조작하여 최소거리 1을 늘려주면 될 것이다. 단일오류 정정코드에 이중오류검출 능력을 추가로 부여하기 위해서는 이미 형성된 단일오류 정정코드(Hamming 코드)의 각 블록마다 전체 블록에 대하여 패리티 검사를 수행하는 검사 bit 한개를 첨가시킴으로써 가능하다. 이렇게 하면 원래 최소거리 3을 유지하고 있던 코드점들은 추가된 패리티에 의하여 최소거리 4를 유지하게 될 것이다.

전송 중 오류가 발생되지 않으면, Syndrome은 □0□이 되고 추가된 패리티 검사도 □성공□(success or even)으로 나타난다. 만일 원래의 블록 내에서 단일오류가 발생되면, Syndrome은 오류의 발생위치를 나타내게 되고 추가된 패리티 검사의 결과는 □실패□(fail or odd)로 나타나게 될 것이다. 이러한 경우에는 Syndrome이 지정하는 위치의 bit를 교환함으로써 오류를 정정할 수 있다. 공교롭게도 추가된 패리티 bit에 오류가 발생하였다면, Syndrome은 □0□이 되고 추가된 패리티 검사의 결과는 □실패□일 것이다. 이 때 수신측은 아무런 동작도 필요로 하지 않는다. 전송 중 이중오류가 발생된 경우에는 □0□이 아닌 Syndrome이 형성되고, 추가된 패리티 검사의 결과는 □성공□으로 나타나게 될 것이다. 이 때 수신측은 이중오류가 발생한 위치는 알 수 없으나 이를 검출할 수 있으므로 재전송을 요구하게 된다.  표 3-5는 이와 같은 동작을 정리한 것이다.

표 3-5  단일오류정정 및 이중오류검출

원래의 Syndrome	추가된 패리티 검사	의 미	수신기의 부가동작
0 0 □0 □0	0 1 1 0	오류발생 없음 추가된 패리티 bit에 오류 Syndrome 위치에 오류 이중오류 (위치는 알 수 없음)	부가동작 없음 부가동작 없음 Syndrome 위치의 bit 교환 재전송 요구

여기서 논의된 코드체계는 대수학적 접근방법과 기하학적인 접근방법을 동시에 적용하고 있다고 할 수 있다. 더우기 이 두 가지 접근방식이 상호 보완적으로 적용되어 유용한 코드체계를 형성하고 있는 것이다.

오류정정코드에 관한 이론은 오랜 세월 동안 수많은 학자들에 의하여 꾸준히 연구되어 왔으며 오늘날 매우 다양하고 복잡한 이론으로 정립되어 있다. 이들 중에는 다중오류(multiple errors)나 다발성 오류(burst error)를 검출 혹은 정정할 수 있는 효율적인 체계들이 다수 포함되어 있다. 그러나 우리는 이 책을 통하여 코딩이론에 기초한 정보이론의 기본 개념을 밝히고자 하므로 이들에 대한 구체적 내용은 취급하지 않기로 한다. 다만 여기서는 정보이론의 제반 개념을 유도하기 위한 채널코딩의 일반론만을 제시한 것이다.

.  이 책의 내용을 통독하고 오류정정코드에 관한 구체적 방법론을 공부하고자 하는 독자는 다음 서적을 참고하라.

S.Lin and D.J.Costello,Jr., Error Control Coding - Fundamentals and Applications, 1983, Prentice_Hall.

R.E.Blahut, The Theory and Practice of Error Control Codes, 1983, Addison-Wesley.

채널코딩에 관한 기하학적 접근이 내포하고 있는 가장 기본적인 개념은 코드점들 사이에 유지되고 있는 Hamming 거리이다. 전송 중 발생되는 오류를 성공적으로 제어하기 위해서는 코드점을 표시하고 있는 메시지 블록들을 될수록 먼 거리에 위치시켜야 한다는 생각이다. 만일 메시지 블록 중 어느 두 개가 충분한 거리를 유지하지 못한다면 그 블록에 오류가 발생한 경우 두 블록이 겹치거나 수신측에서 인식할 수 없을 정도로 근접하게 될 것이다.

이러한 거리 개념은 FORTRAN, PASCAL 등 고급언어를 이용한 프로그래밍에 있어서 변수명(variable name)이나 레이블(label) 등을 정할 때도 적용될 수 있다. 변수명과 레이블 등은 언제나 문자의 나열로 구성되는데 이들을 정할 때 될 수 있는 한 여러 문자가 서로 다르게 정하는 것이 좋다. 만일 어떤 두 변수명이 유사한 문자열로 정해졌다면 프로그램의 작성이나 Key Board 입력 시 작은 실수에 의해서도 변수명이 서로 겹쳐 논리오류를 발생시킬 수 있을 것이다. 그러므로 변수명이나 레이블을 많이 사용하는 대형 프로그램 작성 시에는 비교적 긴 명칭들을 사용하여 명칭 상호간의 거리를 멀리 이격시키는 것이 좋다. 그러나 긴 명칭들은 프로그램 입력이나 계산시간이 다소 길어짐으로 불리한 면도 있다. 반면에 짧은 명칭들은 식별하기 좋고 프로그램 입력이나 계산시간이 짧아 유리하지만 사소한 실수에 의해서도 명칭이 서로 중첩되어 논리오류를 발생시키는 단점이 있다. 따라서 명칭의 길이는 프로그램의 규모에 따라 이러한 상보성을 고려하여 결정되어야 할 것이다.

Hamming 코드를 비롯한 오류정정코드에 사용된 거리함수의 개념은 전적으로 백색잡음의 가정 하에서 코드점을 표현하는 블록들이 서로 몇 bits 씩 다른가를 나타내는 실질적인 거리라고 한다면, 제3-6절에서 취급하였던 가중치코드에 있어서 운용자의 실수에 의하여 발생되는 오류들은 문자 상호간의 관계를 파악하는 인간의 심리적 거리에 의하여 제어된다고 할 수 있다.

정보통신 기술의 발달에 따라 정보의 전송속도가 증가될수록, 반도체 기술의 발달에 따라 집적회로의 집적도가 높아질수록 이들에 의하여 처리되는 정보는 다양할 뿐 아니라 고속으로 운용되며 장거리 전송을 요구하게 될 것이다. 이러한 특성은 필연적으로 오류의 발생확률을 증가시키며, 이를 제어하기 위한 채널코드 체계는 더욱 발달된 것이 요구된다고 하겠다. VLSI의 개발이 매우 활발한 오늘날에도 오류제어 코드는 이들 내부에서 하드웨어의 일부로 제작되고 있다.

연 습 문 제

3.1  각 bit에 대한 오류확률이 pＡ0.001로 주어지는 백색잡음 채널을 통하여 16 bits로 이루어진 메시지 블록이 전송된다고 할 때 (nＡ16)

(a) 오류가 발생하지 않을 확률을 구하라.

(b) 16 bits 모두 오류일 확률을 구하라.

(c) 오직 1 bit에서 오류가 발생될 확률을 구하라.

(d) 5 개의 bits에서 오류가 발생될 확률을 구하라.

(e) 짝수 개(0, 2, 4, …)의 오류가 발생될 확률을 구하라.

(f) 단일 패리티검사에 의하여 검출되지 않는 오류가 발생될 확률을 구하라.

3.2  pＡ0.01, nＡ10으로 두고 위 문제 3.1을 반복하라.

3.3  각 bit에 대한 오류확률이 pＡ0.01로 주어질 때, 단일 패리티 검사에 의하여 검출되지 않는 오류가 발생될 확률이 0.005 이하로 나타나려면 블록의 길이 n은 얼마로 하여야 하는가?

3.4  위 문제 3.3에서 오류확률을 그대로 두고(pＡ0.01), 검출되지 않는 오류가 발생될 확률을 10１4 이하로 변경하면 블록의 길이 n은 얼마로 하여야 하는가?

3.5  위 문제 3.3에서 검출되지 않는 오류가 발생될 확률을 그대로 두고 (0.005), 각 bit에 대한 오류확률을 pＡ0.001로 변경하면 블록의 길이 n은 얼마까지 가능한가?

3.6  메시지 블록의 각 bit에서 오류가 발생될 확률은 일반적으로 1 보다 매우 작은 값이다. 이 때, 식(3-11)은 처음 두 항에 의하여 지배된다고 할 수 있다. pＡ0.001 일 때 단일 패리티 검사에 의하여 검출되지 않는 오류가 발생될 확률을 10１5 이하로 하기 위해서는 블록의 길이를 얼마로 하여야 하는가?

3.7  전송하고자 하는 메시지가 다음과 같이 주어질 때 다발오류 검출을 위한 패리티word를 구하라. 단, 각 word는 짝수패리티로 검사되며 parity-word의 길이는 8-bit이다. 또한 5 개의 정보 word 마다 1 개씩의 패리티 word를 두기로 한다.

(a)                 (b)

101 01010	101 00110

011 00110	101 00101

000 11110	000 11101

110 00110	111 10000

111 10101	010 10000

011 11110	101 11110

101 00000	000 00011

110 00011	111 10000

001 00010	001 10110

101 11011	111 11100

3.8  홀수패리티(odd parity)를 사용하여 위 문제 3.7을 반복하라.

3.9  {0Ａ0, 1Ａ1, 2Ａ2, …, 9Ａ9, AＡ10, BＡ11, CＡ12, …, ZＡ35, spaceＡ36}과 같이 규정된 가중치 코드를 사용하여 다음을 코딩하라. 단, 검사문자는 각 메시지의 최후에 둔다.  여기서 □□□는 □space□를 나타낸다.

(a) B23F□□F3	(b) K9K10□ABC

(c) A9A3□□KZ	(d) BOOK□STORE

3.10 위 문제 3.9의 규칙을 이용하여 다음 메시지들의 오류 여부를 판단하라.

(a) A6□7Q0	(b) K9K9

(c) ABCDEF9□Q	(d) B□993A4

3.11 위 문제 3.9의 코딩규칙을

{AＡ1, BＡ2, CＡ3, …, ZＡ26, spaceＡ27, 0Ａ28, 1Ａ29, 2Ａ30, …, 9Ａ37}

와 같이 변경하여 문제 (a), (b), (c), (d)를 반복하라.

3.12 위 문제 3.11의 규칙을 사용하여 다음 메시지들의 오류 여부를 판단하라.

(a) A6□7Q9	(b) K9KR

(c) ABCDEF9□L	(d) B□993AZ

3.13 다음 도서번호가 ISBN이 되도록 검사숫자를 부여하라.

(a) 4-71-89955-?	(b) 0-13-272500-?

(c) 0-15-711706-?	(d) 3-07-034054-?

3.14 다음 ISBN 들이 올바로 부여되었는가 판단하라.

(a) 89-7114-021-6	(b) 0-13165332-6

(c) 3-540-08750-8	(d) 0-387-08750-8

(e) 0-13-637785-X	(f) 0-201-11026-1

3.15 독자들이 소유하고 있는 장서들의 ISBN을 찾아 검토하여 보자.

3.16 사각형 코드를 이용하여 24 개의 정보 bit를 배열하는 여러가지 방법을 설명하고, 그림 3-6을 참고하여 가장 효율적인 가로/세로 길이를 구하라.

3.17 정보 bit가 10 개일 때 그림 3-7과 같은 형태의 삼각형코드를 작성하라. 또한 이 때의 Redundancy를 계산하라.

3.18 정보 bit의 갯수가 각각 20 개, 24 개, 48 개일 경우 위 문제 3.17을 반복하라.

3.19 표 3-1에 나타난 세 가지 코드체계에 대하여 검사 bit가 10 개일 때 각각의 Redundancy를 구하고 효율성을 비교하라.

3.20 위 문제 3.19를 검사 bit의 갯수가 각각 7, 4, 3일 경우에 대하여 반복하라.

3.21 패리티 검사 bit의 갯수가 각각 4, 5, 6일 경우 Hamming 코드의 블록 당 bit 수는 얼마인가? 또한 각각에 대하여 검사 bit가 놓일 위치를 결정하고, 이들이 검사하는 위치를 말하라.

3.22 검사 bit의 갯수가 2인 Hamming 코드에 대하여 위 문제 3.21을 반복하고, 이 때의 코드체계는 제3-7절의 첫머리에 설명한 삼중코드(triplication code)와 같은 효율성을 가짐을 보여라. Redundancy는 얼마인가?

3.23 다음 4-bit 정보들을 각각 7-bit Hamming 코드로 코딩하라. 단, 검사 bit들은 각각 블록 내의 #1, #2, #4 위치에 부여하기로 한다.

(a) 0010	(b) 1111	(c) 1001	(d) 1110

3.24 위 문제 3.23에서 코딩된 블록들이 전송되는 도중에 채널 상의 잡음에 의하여 각각 (a) #3   (b) #4   (c) #5   (d) #6 등의 위치에서 오류가 발생하였다. 표 3-3과 같은 과정을 통하여 오류를 정정하라. 각 블록에 대하여 주어지는 Syndrome을 밝혀라.

3.25 Hamming 코드체계의 수신기에서 다음과 같은 7-bit 블록들을 수신하였다. 각 블록에 오류가 있는지를 검사하고, 만일 있으면 정정하여 올바른 메시지를 밝혀라. 이 때 검사 bit들은 각각 #1, #2, #4 위치에 있다고 가정한다.

(a) 1111111	(b) 0101010	(c) 1001111	(d) 1010111

3.26 다음 11-bit 정보들을 각각 15-bit Hamming 코드로 코딩하라. 단, 검사 bit들은 각각 #1, #2, #4, #8 위치에 부여하기로 한다.

(a) 11111111111	(b) 10101010101

(c) 00011100111	(d) 11011011100

3.27 위 문제 3.26에서 코딩된 블록들이 전송 중 채널 상의 잡음에 의하여 각각 (a) #5  (b) #10   (c) #7   (d) #14 등의 위치에서 오류가 발생하였다. [예제 7]에서 수행한 과정을 통하여 오류를 정정하여 올바른 메시지를 밝혀라. 각각의 블록에 대하여 주어지는 Syndrome은 무엇인가?

3.28 15-bit  Hamming 코드에 있어서 패리티 검사 bit들을 각각 #12, #13, #14, #15 위치에 두는 꼬리검사코드를 설계할 때, 그림 3-9와 같은 형태로 각 bit의 위치교환을 표시하고 식(3-23)과 같은 교환순열을 구하라.

3.29 두 개의 코드점(code point)이 다음과 같이 주어질 때 Hamming 거리 D(x, y)를 구하라.

(a) x Ａ (0, 0, 1, 1, 0),  y Ａ (0, 0, 1, 0, 1)

(b) x Ａ (0, 0, 0),  y Ａ (1, 1, 1)

(c) x Ａ (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),  y Ａ (0, 0, 0, 0, 1, 1, 0, 1, 0, 0)

(d) x Ａ (1, 1, 1, 1, 0, 1, 1),  y Ａ (0, 1, 1, 0, 0, 0, 1)

3.30 그림 3-10(c)에 도시된 3-차원 이진공간에 대하여 다음 물음에 답하라.

(a) 코드점 (1, 0, 1)을 중심으로 하고 반경 1, 반경 2, 반경 3 인 구의 표면(surface of sphere)을 각각 구하라.

(b) 위 (a)에 제시된 각 구의 체적을 구하라.

(c) 원점 (0, 0, 0)을 포함하여 최소거리 2 가 되도록 3 개의 코드점을 갖는 시스템을 구하라.

3.31 삼중오류(3-bit error) 정정코드와 사중오류(4-bit error) 정정코드에 대하여 식(3-32) 및 식(3-33)과 같은 기본관계식을 유도하라.

3.32 표 3-5에서 원래의 Syndrome이 □0□이고 추가된 패리티 검사의 결과가 □실패□(fail or odd)일 때, 수신측의 부가동작이 필요없는 이유는 무엇인가 ?