제 11 장

대수학적 코딩 이론

11-1 개요

Shannon의 주 정리(Main theorem)는 매우 긴 블록코드(Block code)를 사용하여 채널용량(Channel capacity)에 무한히 접근하는 신호속도(Signaling rate)로 무한히 작은 오류(Error)를 발생시키는 코드체계를 구현할 수 있음을 보뎌 주고 있다. 이에 대한 증명은 매우 긴 블록코드를 사용하는 랜덤코딩(Random encoding)에 근거를 두고 있다. 또한 이러한 랜덤코드 내에는 수신측에서 정정되어야 할 오류들이 여러개 존재할 가능성이 있다. 이러한 사실은 효율적인 코드체계가 높은 오류정정 능력을 가져야만 한다는 것을 말해준다. 우리는 제 4 장에서 단일오류 정정코드(Single-error-coding code)와 이중오류 검출코드(Double-errer-detecting code)의 설계방법에 대하여 공부하였다. 이들의 설계과정은 비교적 간단하였다. 그러나 다중오류 정정코드(Multiple-error-correcting code)에 대한 이론은 대단히 복잡하고 정교하게 구성되어 있다. 따라서 이 책을 통하여 이들 이론의 상세한 부분까지 취급하기는 불가능하며, 여기서는 단지 몇가지 자주 사용되는 다중오류 정정코드의 설계 킹 실현 방법에 대하여 기본적인 개념을 중심으로 설명하고자 한다.

	정보이론

제 11 장 대수학적 코딩 이론

랜덤코드에 대한 개념은 우리가 단말장치(Terminal equipment)에 국한하여 생각할 경우에는 매우 호소력 있는 내용이 된다. 하나의 코드가 길다는 사실은 인코딩을 위한 체계가 매우 방대하다는 것을 의미한다. 왜냐하면 □랜덤□이라는 말은 아무런 패턴이 없다는 말과 동일한 의미이며, 따라서 소스정보(Source information)로부터 코드화된 메시지를 얻어 내는 공식이 없으므로 일일이 찾아보기(Looking-up)에 의한 인코딩이 이루어져야 하기 때문이다. 더구나 디코딩을 위한 체계는 인코딩 체계보다도 더 방대해야만 할 것이다. 왜냐하면 송신측에서 M개의 선택된 n-bit 코드만이 전송된다고 하더라도, 수신측에서는 채널의 영향으로 인하여 전체 2n개의 n-bit 코드가 모두 디코더의 입력으로 들어올 가능성이 있기 때문이다. 만일 이렇게 방대한 디코딩 체계를 사용하지 않으려고 한다면, 수신된 메시지에 해당하는 정확한 메시지를 찾아내기 위하여 대단해 많은 양의 계산을 수행하여야 할 것이다. 다라서 실용적인 면에 있어서는 랜덤코드의 개념은 거의 쓸모가 없게 되는 것이다.

그러므로 우리는 체계적인 구조를 갖는 코드체계를 설계하여야 하며, 이러한 코드체계의 설계를 위해서는 Galois 필드(Galois field)에 대한 대수적 이론을 필요로 한다. 위에서도 언급하였던 바와 같이, 대수학적 코드(Algebraic code)에 대한 이론은 대단히 방대하다. 따라서 이 책의 한정된 지면을 통하여 다중오류 정정코드(Multiple-error- correcting code)에 관한 기본적 개념과 몇가지 예에 대히서만 살펴보고자 한다. 사실 이 책은 여러 가지 상황 하에서 가장 최적의 코드체계를 설계하는 코딩 전문가를 위하여 쓰여진 책이 아니다. 단지 이러한 이론에 대한 기초적인 개념을 필요로 하며, 이들을 확히 정립시키고, 어떤 특별한 상황에서 좀 더 상세한 이론을 필요로 하게 되면 참고문헌을 찾아 해결할 수 있는 능력을 갖고자 하는 독자들을 위하여 저술된 것이다(참고문헌 [5-8], [15-20]) 등을 이러한 목적을 위하여 제시한다).

실제적인 채널에 있어서 이미 개발된 코드체계를 적용하고자 할 때, 그 챈러의 잡음특성(Noise characteristics)을 정확하게 적응시키기는 거의 불가능하다. 왜냐하면 대부분의 코드체계는 순수한 백색잡음(White noise)을 가정하여 설계되어 있으나. 실용채널의 잡음특성은 이상적인 백색잡음이 아니기 때문이다. 우리는 실제로 이러한 상황을 수시로 접하게 된다는 점을 강조해 두는 바이다.

이 장을 통하여 우리들의 촛점은 이진 블록코드(Binary block code)에 맞추기로 한다. 왜냐하면 블록코드는 가장 널리 사용되는 오류정정 코드의 형태로서 다루기 쉬우며, Radix-r 코드는 표시 방법상 복잡하기만 할 뿐 그 기본적인 개념은 이진(Radix-r) 코드와 별 차이가 없기 때문이다.

우리는 먼제 제 4 장을 통하여 논의하였던 Hamming 코드를 신중하게 재 검토할 것이다. 이는 독자들의 기억을 되살리는 의미도 있지만, 제 4 장과는 판이하게 다른 관점에서 그 이론을 성립하고자 하는 것이다.

11-2  오류검출 패리티 코드

제 3-2절에서 취급하였던 단일오류 검출코드(Single-error-detecting code)는 전체 bit 위치에 대하여 하나의 패리티 검사를 수행한다. 검사된(Checked) bit 위치에는 □1□을 표시하고, 검사되지 않은 bit 위치에는 □0□을 표시하며, 다음과 같은 벡터를 얻게 된다(여기서는 단순히 1 × m 행렬이 된다).

[eqn: M ``Ａ`` (1, ~1,~1,~□, ~1`)]	(11-1)

이 백터는 모든 bit 위치에 대하여 피리티 검사가 실시됨을 의미한다.

코드화된 심볼은 n개의 이진수로 이루어진 벡터 c로 표시한다.

[eqn: c ``Ａ`` (0, ~1,~0,~□, ~1`)]	(11-2)

c의 전치행력(Transpace) c2는 c를 세로 방향으로 나열한 열벡터(Column vector)이다. 전성하고자 하는 모든 코드들에 대하여 mod-2(Module-2) 산술을 이용한 행렬의 곱은

[eqn: M`c^T ``Ａ`` 0]	(11-3)

과 같이 표시할 수 있다. 여기서 이 행렬의 곱이 0이 되는 이유를 밝히는 것은 대단히 중요한 일이다. 사실 (11-3)은 패리티 검사(Parity check)를 간단한 식으로 표현한 것이다. 다시 말해서 벡터 M의 각 요소는 패리티 검사가 수행되는 벡터 c의 위치를 선택해 주는 역할을 하는 것이다.

다음으로 코드심볼 c를 전송하는 도중에 단일오류(Single error)가 발생하였다고 가정하여 보자. 수신된 코드는 mod-2로

[eqn: c ``／`` e]	(11-4)

와 같이 나타나게 되며, 여기서 e는 오류가 발생된 위치만이 □1□이고 나머지 다른 위치들은 □0□으로 펴시되는 오류벡터(Error vector)이다.

마지막으로 검사벡터(check vector)와 오류를 포함하고 있는 수신심볼 벡터와의 곱을 생각하여 보자.

[eqn: M`(c ``／``e`) ``&Ａ`` M`c^T ``／`` M`e^T## &Ａ`` M`c^T ``□`` 0]

(11-5)

여기서 MeT는 단일오류(Single error)에 의하여 나타난 Syndrome을 표시한다. 요컨대 오류를 포함하고 있는 메시지의 Syndrome은 홀수개의 오류에 대해서는 □1□, 짝수개으 오류에 대히서는 □0□으로 나타난다. 물론, 오류가 없는 메시지에 대한 Syndrome도 □0□이다.

11-3  Hamming 코드

제 4-3절에서는 단일오류 정정코드(Single-error-correcting code)의 한 특수한 형태인 Hamming 코드를 취급하였다. 이러한 Hamming 코드의 근본은 다음과 같은 위치에서 패리티 검사를 수행하는 것이었다.

check-1    1,   3,    5,    7,    9,   11,   13,   15, □

check-2    2,   3,    6,    7,   10,   11,   14,   15, □

check-3    4,   5,    6,    7,   12,   13,   14,   15, □

check-4    8,   9,   10,   11,   12,   13,   14,   15, □

Hamming 코드의 한 예로서, n Ａ 7인 경우를 생각하여 보면, 우리는 다음과 같은 검사행렬(Check matrix)을 제안할 수 있다.

← 세번째 검사[eqn: M ``Ａ`` pmatrix {0 & 0 & 0 & 1 & 1 & 1 & 1# 0 & 1 & 1 & 0 & 0 & 1 & 1# 1 & 0 & 1 & 0 & 1 & 0 & 1}]

← 두번째 검사

← 첫번째 검사	(11-6)

여기서 패리티 검사의 차례는 행렬의 제일 밑에 있는 행(Raw)으로 부터 시작되도록 하였다. 패리티 검사의 각 위치는 행렬의 해당 행(Raw)에 □1□로 표시되어 있다.

다시 c를 코드벡터라 두면, 모든 소스코드에 대하여

[eqn: M`c^T ``Ａ`` 0]	(11-7)

이 성립한다. 이는 코드화된 메시지의 정의에 의한 것이며, 기술적인 특수용어(Jargon : 은어)로서 □행렬 M은 정확하게 코드벡터 c를 전멸시킨다(annihilate)□라고 말한다. 소스코드 c가 채널을 통하여 전송되는 도중에 단일오류(Single error) e가 발생하였다고 가정하면, 수신된 메시지는

[eqn: c``／`` e]	(11-8)

로 나타나며, 이에 대한 행렬 표현은

[eqn: M`(c ``／``e`)^T ``&Ａ`` M`c^T ``／`` M`e^T## &Ａ`` M`e^T]

(11-9)

와 같이 나타낼 수 있다. 이 식의 결과 MeT는 바로 Syndrome이 되며, 이는 원래의 코드 c와는 전혀 관계없고, 오르지 오류 e에 의하여 결정된다는 사실을 알 수 있다. 또한 Syndrome은 하나의 숫자로 나타나며, 이 숫자는 오류가 발생한 위치를 표시한다. 따라서 패리티 검사행렬(Parity-check matrix) M의 열(Columm)들은 발생가능한 단일오류(Single error)에 대한 모든 Syndrome을 표시할 수 있어야 한다.

단일오류 패리티 검사를 이용하는 코드체계에 대하여 피리티 검사행렬 M을 나타내기 위해서는, 각각의 행(Raw)에 있어서 피리티 검사가 수행되는 위치는 □1□로 하고, 패리티 검사가 수행되지 않는 위치는 □0□으로 표시함으로써 가능하게 된다. 이러한 패리티 검사행렬의 Rank는 그 행렬의 행의 갯수(the number of rows in M)와 같다고 가정한다. 여기서 Rank의 계산은 mod-2 산술을 이용한다. 예를 들어서, 다음과 같은 행렬을 생각하여 보자.

[eqn: M ``Ａ`` pmatrix {1 & 1 & 1 & 1# 0 & 0 & 1 & 1# 1 & 1 & 0 & 0 }]	(11-10)

행렬의 Rank는 성형독림인(Linearly independent) 행의 수를 말한다. (11-10)의 행렬에 있어서, 아래쪽의 두 행을 합하며(mod-2) 맨 위의 행이 된다. 따라서 이 행렬의 Rank는 2이다. 이것은 아래쪽의 두 패리티 검사가 만족되면 윗쪽의 패리티 검사는 저절로 만족된다는 사실을 보여 주는 것이다. 또한 이러한 3행을 모두 더하녀(mod-2) □0000□이 된다. 그러므로 패리티 검사행렬(parity-check matrix)의 각 행이 서로 선형종속이면, 적어도 하나의 Syndrome-bit는 다른 것들로 부터 결정될 수 있으며, 이 때 우리는 우리가 원하는 만큼의 서로 다른 Syndrome을 얻어낼 수 없으므로 필요한 오류제어를 할 수 없게 되며, 결국 신호용량(Signaling capacity)을 낭비하는 것이 된다.

일반적인 피리티 검사의 경우에도 인코딩 과정(Encoding process)은 모든 정확한 코드에 대하여

[eqn: M`c^T ``Ａ`` 0]	(11-11)

을 만족하도록 수행되어야 한다. 또한 오류 e에 의하여 수신메시지는 c ／ e가 되고

[eqn: M`(c ``／``e`)^T ``Ａ`` M`c^T]	(11-12)

와 같은 식이 성립함은 물론이다. 여기에서도 MeT는 Syndrome을 표시한다. 이 Syndrome은 오로지 오류에 의하여 결정되며, 이것이 나타내는 숫자는 오류가 발생한 위치를 말해 준다.

단일오류(Single error)가 발생하면, 다음과 같은 디코딩 규칙(Decoding rule)에 의하여 오류를 수정하고 원하는 메시지를 수용하게 된다. 먼저, Syndrome을 계산하여 패리티 검사행렬(Parity-check matrix)의 해당되는 열(Column)을 발견한다. 그 열은 정확히 오류가 발생한 위치를 표시하므로 수신된 메시지에서 오류의 위치를 찾아낼 수 있게 되는 것이다. 따라서 어떠한 단일오류 정정코드(Single-error-correcting code)에 대히서도 주어진 Syndrome을 이용하여 패리티 검사 행렬(Parity-check matrix)의 해당하는 열을 찾아낼 수 있다. 물론 Syndrome이 모두 □0□이면 오류가 발생하지 않았음을 나타낸다.

만일 다중오류 정정코드(Multiple-error-correcting code)를 사용하고 있다면, Syndrome은 오류가 발생한 위치에 해당하는 패리티 검사행렬의 열에 대한 합(mod-2)으로 나타나게 될 것이다. 여기서 만일 행렬의 정확한 열만 발견한다면 이러한 대응관계는 유일하게 결정될 것이다. 따라서 이러한 Syndrome에 의하여 유도되는 다중오류((Multiple error)도 유일하게 결정된다. 만일 Syndrome이 0이 아닌 어떤 숫자로 나타나고, 허가된 열의 함으로 표시될 수 없는 경우가 발생하며, 이 때는 발생한 오류를 정정할 방법이 없다. 이러한 경우, 우리는 단지 오류의 발생을 검출(Detection)할 수 있을 뿐이다.

예를 들어서, 이중 오류 정정코드(Double-error-correcting code)의 경우에는 두 개의 오류에 의하여 발생할 수 있는 어떤 Syndrome도 패리티 검사행렬의 유일한 한 쌍의 열의 합으로 표시될 수 있어야 한다. 이 때, 패리티 검사행렬의 서로 다른 두 쌍의 열은 그 합이 동일한 Syndrome을 표시하여서는 안된다. 만일, 그렇게 동일한 Syndrome을 나타내는 열들이 존재한다면, 그 Syndrome에 의하여 두 개의 오류를 찾아낼 방법이 없다. 따라서 임의의 두 열의 합은 다른 하나의 열과 동일하여서는 안도니다. 이렇나 사실을 수학적으로 표시하면

[eqn: M`(e_1 ``／`` e_2`)^T ``Ａ`` M`e_1^T ``／``M`e_2^T~~ ;~~ Syndrome]	(11-13)

와 같이 나타나고, 이 때 Syndrome은 어떠한 한 쌍의 오류 (e1, e2)에 대해서도 유일하게 결정되어야 하며, 모든 단일오류 e에 대해서도 유일한 값으로 나타나야 하는 것이다. 또한 Syndrome이 모두 □0□으로 표시되는 것은 오류가 전혀 발생하지 않은 경우에 한한다.

이중오류 이상의 다중오류를 정정하는 코드체계에 대해서도 지금까지 설명한 내용을 그대로 확장하여 적용할 수 있다.

11-4  이중오류 검출코드

제 4-6절에서 소개하였던 이중오류 검출코드(Double-error-detecting code)에 대해서는 다음과 같이 모든 위치를 검사할 수 있는 생을 가장 윗쪽에 첨가시킨 패리티 검사행렬(Parity-check matrix)을 사용하게 된다(n Ａ 8).

[eqn: M ``Ａ`` pmatrix {1 & 1 & 1 & 1 & 1 & 1 & 1 &1# 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0# 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0# 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 }]	(11-14)

첫번째 요소가 □1□인 모든 Syndrome은 나머지 요소들을 가지고 단일오류(Single error)의 위치를 결정하는 실제의 Syndrome으로 사용하며, 이 때 만일 실제의 Syndrome이 모두 □0□이면 추가된 패리티 검사 위치(Additional parity-check position)에 오류가 발생하엿다는 것을 의미한다(패리티 검사행렬 M의 마지막 열에 유의하라). 첫번째 요소가 □0□인 Syndrome에 대해서는 오류가 발생하지 않은 경우와 짝수(2, 4, 6, 8 □)개의 오류가 발생한 경우의 두가지로 나누어 볼 수 있다. 모든 Syndrome-bit가 □0□으로 나타나는 경우는 오류가 발생하지 않은 것(0개의 오류)을 나타내며, 그렇지 않은 경우는 두 개 이상의 오류가 발생하였음을 표시하지만, 패리티 검사행렬의 열로서 이러한 Syndrome을 표시할 수 없으므로 오류의 발생위치를 찾아낼 수는 없다. 단지, 우리는 짝수개의 오류가 발생하였음을 검출(Detection) 할 수 있을 뿐이다.

11-5  다항식과 벡터

지금까지 전개한 것처럼, □0□과 □1□로 이루어진 코드열(Code sequence)은 벡터로 취급하는 것이 편리하다. 그러나 이러한 관점을 다항식(Polynomial)의 개념으로 대치하면 좀 더 유리한 표현을 얻을 수 있다. 코드체계를 표시하기 위한 다항식에 있어서, 코드의 각 bit는 변수 x의 거듭제곱에 대한 계수(Coefficient)로 간주된다. 예를 들어서 코드열(1, 0, 1, 1, 0)은 다항식

[eqn: P_1 `(x`) ``Ａ`` x^4``／``x^2``／`` x]	(11-15)

로 대치할 수 있는 것이다. 어던 의미에서는 이러한 다항식이 □0□과 □1□의 코드열을 생성하는 발생함수(Generator function)로 간주될 수도 있을 것이다. 또 하나의 예로서, 코드열 (0, 1, 1, 0, 1)에 대한 다항식 표현은

[eqn: P_2 `(x`) ``Ａ`` x^3``／``x^2``／`` x]	(11-16)

와 같이 나타난다.

일정한 차수(Degree)를 갖고, 정수를 계수(Coefficients)로 하는 모든 다항식의 집합은 덧셈과 빼셈에 대하여 닫혀 있다. 즉, 그 집합 내의 어떤 두 다항식을 더하거나 빼더라도 그 결과는 다시 그 집합의 원소가 된다는 것이다. 이러한 사실은 우리들의 mod-2 산술에 대해서도 그대로 성립한다. 예를 들어서, (11-15)와 (11-16)에 주어진 두 다항식을 생각하여 보자. 이들 두 다항식을 서로 더하면 P1(x) ／ P2(x) Ａ x4 ／ x3 ／ x ／ 1 (mod-2)이 되어, 그 결과로 나타나는 다항식은 다시 4차의 다항식임을 알 수 있다. 또한 다항식의 덧셈에는 결합법칙(Associative)이 성립한다. 즉, 3개의 다항식 P1, P2, P3에 대하여 (P1 ／ P2) ／ P3 Ａ P1 ／ (P2 ／ P3)이다. 모든 4차 다항식의 집합 내에는 (0, 0, 0, 0, 0)으로 표시되는 0-원소(Zero polynomial)에 대응되고, 이는 실제로 0과 동일한 값을 가진다. 0-다항식이 아닌 모든 다항식은 구 자신의 덧셈에 관한 역원소(Additive inverse)를 가지며, 임의의 두 다항식의 합은 같은 차수(Degree)를 가진 새로운 다항식으로 나타나므로, 모든 n차 다항식의 집합은 Group을 형성한다. 여기서 다항식의 모든 계수(Coefficient)들은 0 혹은 1이다.

Modular 산술의 목적은 가능한 모든 숫자를 주어진 수의 범위 내로 한정시키고자 하는 것이다 이는 모든 숫자를 Modulus m으로 나누어, 그 나머지(양수)만을 취하여 0, 1, 2, □, (m１1) 등 m개의 숫자만으로 표시하고자 하는 것이다. 여기서 표시되는 모든 나머지들은 해당 Modulus m보다 작다.

다항식의 산술에 있어서, 두 다항식의 곱(Product)은 각 다항식의 차수를 더한맡큼의 차수를 가지게 된다. 이와 같은 곱의 차수를 n보다 작은 최대차수(Maximum degree) 이내로 유지하기 위해서는 앞에서 언급했던 방법에 의하여 차수를 한정시켜야 한다. 따라서 우리는 다항식에 대하여 Modular 산술을 적용하고자 한다. 여기에서의 다항식은 코드열(Code sequence)을 등가적으로 표현한 것이다. 모든 숫자를 Modulus로 나누어 그 나머지만을 취하여 그 숫자를 대신하는 Modular 산술에서와 마찬가지로, 모든 다항식을 n차 Modulus 다항식(the Modulus polynimial of degree n)으로 나누어 그 나머지를 다항식의 곱(Product)으로 사용하기로 하자. 그 결과로 나타나는 나머지는 n개의 계수(Coefficients)를 갖는 (n１1)차의 다항식이 되며, 이를 코드심볼에 대한 표현으로 사용하기로 한다.

일반적으로 Modulus는 솟수(prime number)여야 한다. 솟수인 Modulus를 사용하면, 임의의 두 숫자를 곱하여 0이 된다는 사실은 그 중 적어도 하나의 숫자가 0이라는 것을 확신시켜 주는 것이다. 반면에 솟수가 아닌 Modulus를 사용하며, 두 수의 곱이 0이라 하더라도, 그 두 수 모두 0이 아닐 가능성이 있는 것이다. 마찬가지 이유 때문에, 우리느 솟수 다항식(Prime polynomial)을 Modulus로 사용하기를 원한다. 여기서 솟수 다항식이라 함은 임의의 두 다항식의 곱으로 표시될 수 없는 다항식을 말한다.

n차 다항식은 그 최고 차수의 계수가 0일 수도 있다. 이 때, 이 다항식은 실제로 n보다 낮은 차수를 가지게 되지만, 우리는 이를 n차항의 계수가 0인 n차 다항식으로 취급할 수 있는 것이다. 모드열(Code sequence)을 표현하는 모든 다항식의 계수는 0 아니면 1이다. 여기서 최고 차수(highest power of x)의 계수가 1인 다항식을 Monic 다항식(Monic polynomial)이라 부른다.

독자들은 아마도 □왜 다항식 사이의 곱셈(Multiplication)은 사용하지 않는가?□라는 의문을 제기할 것이다. 이 의문에 대한 대답은 한마디로 구조적 코드체계(Structured coding system)를 유도하기 위함이다. 우리는 우리들의 코딩이론을 될 수 있는 한 구조적이 되도록 형성시켜야 한다. 그렇게 해야만 궁극적으로 우리가 얻는 코드체계가 구조적이 될 것이며, 그를 위한 인코딩, 디코딩 장비(Encoding and decoding equipment)도 구조적이 될 것이다. 여기서 구조적이라는 말은 제 10 장에서 언급된 랜덤(Random)이라는 말과 상반된 의미를 가진다. 또한 코드체계가 구조적으로 규정되면, 이를 실현하는 하드웨어(H/W : Hardware)나 소프트웨어(S/W : Software)를 제작하기가 쉽다. 요컨대 오류제어코딩이론에 있어서는 랜덤(Random)하거나 구조성이 약한(loghtly structured) 모든 코드체계를 배제한다.

11-6  솟수 다항식

솟수 다항식(Prime polynomial)은 그 보다 낮은 차수의 다향식의 곱으로 표시될 수 없는 Monic 다항식을 말한다. 그러나 이들 다항식의 모든 계수(Coefficents)는 mod-2 산술에 의하여 결정되므로 우리가 예상하는 결과들이 그대로 도출될 것인지에 대하여 임의 차수가지 확신할 수는 없을 것이다. 여기서 우리는 실험적으로 몇 가지 예를 제시하므로써 솟수 다항식에 대한 개념을 정리해 두고자 한다. 물론 Galois 필드에 대한 상헤산 내용을 모두 취급할 수는 없으나. mod-2 산술에 있어서 다항식의 요소분해(Fantorization)에 관한 사항을 간단히 언급하기로 한다.

0차 다항식(Polynomial of degree zero)으로는 다음과 같은 상수 다항식 하나만이 존재한다.

[eqn: P``Ａ``1]	(11-17)

이는 일반적 산술(Normal arithmetic)에서의 숫자 1에 대응한다.

1차의 Monic 다항식으로는 다음과 같은 두 가지가 존재한다.

[eqn: &~~x# &x``／``1]	(11-18)

이들 두 1차 다항식은 모두 솟수 다항식(Prime polynomial)이다. 여기서 x의 계수 1은 생략하였으며, 앞으로도 x의 거듭제곱(Prime Polynomial)에 계수 1이 붙게 되면 이를 생략하기로 한다.

2차의 Monic 다항식으로는 다음과 같이 4가지를 제시할 수 있다.

[eqn: &x^2 ``Ａ``x□x## &x^2``／``1 ``Ａ`` (x``／``1`)`(x``／``1`)## &x^2``／``x ``Ａ`` x`(x``／``1`)## &x^2``／``x``／``1 ``Ａ`` rm 솟수 다항식]

(11-19)

이들 중 두번째 식은

[eqn: x^2``／``1 ``Ａ`` (x``／``1`)^2]	(11-20)

와 같이 쓸 수 있으며, 일반적 산술에 있어서의 계산과는 다르게 나타남을 알 수 있다. 식의 우변을 mod-2 산술을 이용하여 계산하면

[eqn: (x``／``1`)^2 ／ x^2``／``2x``／``1]	(11-21)

와 같이 나타나고, 여기서 2 Ａ 0(mod-2)이므로

[eqn: x^2``／``2x``／``1 ``Ａ`` x^2``／``1]	(11-22)

임을 입증할 수 있다.

다항식

[eqn: x^2``／``x``／``1]	(11-23)

은 정말 솟수 다항식인가? 이는 두 개의 1차 다항식(11-18)으로 나누어 봄으로써 알 수 있을 것이다. 만일 x2 ／ x ／ 1이 합성 다항식(Composite polynomial)이라면 이들 1차 다항식 만이 가능한 분해요소(Factor)가 될 수 있을 것이다. x2 ／ x ／ 1이 x로 나누어 떨어지지 않음은 명백하므로, (x ／ 1)로 나누어 보기로 하자. 이것마저 나누어 떨어지지 않느다면 x2 ／ x ／ 1은 솟수 다항식일 것이 틀림없다.

x  0

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

x／1 －x2／x／1

x2／x

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

0    1

0    0

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

1  ←  나머지

그러므로 x2 ／ x ／ 1은 솟수 다항식(Prime polynomial)이다.

마지막으로 3차의 Monic 다항식에 대하여 살펴보자. 우리가 예상하는 대로 여기서는 8가지의 다항식이 가능하다.

x3	Ａ	x□x□x

x3 ／ 1	Ａ

x3 ／ x	Ａ	x(x2 ／ 1)

x3 ／ x ／ 1	Ａ

x3 ／ x2	Ａ	x2(x ／ 1)

x3 ／ x2 ／ 1	Ａ

x3 ／ x2 ／ 1	Ａ	x(x2 ／ x ／ 1)

x3 ／ x2 ／ x ／ 1	Ａ	(11-24)

이들 중 4가지는 명백하게 요소분해(Fantorixation)되므로 등식으로 표시하였고, 나머지 4가지는 빈칸으로 남겨 두었다.

3차 다항식이 요소분해되면 그 요소들 중 적어도 하나는 1차 다항식이 된다. 1차 다항식 x에 의하여 나누어 떨어지는 다항식들은 이미 (11-24)에 표시하였으므로, 요소 (x ／ 1)에 대해서만 살펴보면 될 것이다. 먼저, x2 ／ 1에 대해서는

1      1     1

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

1 1 －1 0 0 1

1 1

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

1  0

1  1

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

1  1

1  1

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

0   ←  나머지

와 같이 나타나므로

[eqn: x^2 ``／``1``Ａ`` (x``／``1`)`(x^2``／``x``／``1`)]	(11-25)

이다. 따라서 x2 ／ 1은 솟수 다항식이 아니다.

다음으로 x2 ／ x ／ 1에 대해서는

1      1     0

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

1 1 －1 0 1 1

1 1

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

1  1

1  1

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

0  1

0  0

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

1   ←  나머지

와 같이 나타나므로

[eqn: x^3 ``／``x^2` `／``1``Ａ`` x□x`(x``／``1`)``／``1]	(11-26)

와 같이 나타나므로 x3 ／ x2 ／ 1도 솟수 다항식이다.

마지막으로 x3 ／ x2 ／ x ／ 1에 대하여 진행하여 보면

[eqn: x^3 ``／``x^2` `／``x``／``1``&Ａ`` x^2`(x``／``1`)``／``(x``／``1`)## &Ａ``(x^2``／``1`)`(x``／``1`)## &Ａ`` (x``／``1`)^3]

(11-27)

와 같이 표시되므로 이는 합성 다항식(Composite polynomial)이다.

지금까지의 결과를 종합하여 보면, 3차의 Monic 다항식 중에는 다음과 같은 두 개의 솟수 다항식(Prime monic polynomial)이 존재한다.

[eqn: &x^3 ``／``x``／``1## &x^3 ``／``x^2``／``1]

(11-28)

4차, 5차에 대한 솟수 다항식을 유도하는 문제는 연습문제로 제시하고, 그 이상의 차수에 관한 사항은 거런하지 않기로 한다. 우리가 필요로 하는 차수의 솟수 다항식을 구해 내기 위해서는, 그 차수의 반(haif the degree)까지의 하위 차수의 솟수 다항식에 대해서만 요소분해 되는지 살펴보면 된다(연습문제 9번을 참고하라). 아무튼 최적의 코드를 어떻게 설계할 것이지에 관한 사항은 더 진행하지 않겠고, 단지 확고한 구조적 체계를 갖는 다중오류 정정코드(Multiple-error-correcting code)를 위한 코딩이론의 전개에 중점을 두기로 한다. 이러한 구조적 이론이 확립되면 이들 체계를 하드웨어나 소프트웨어에 의하여 실현하는 문제는 쉽게 해결된다.

솟수 다항식(Prime polynomial)은 모든 차수에 대하여 존재한다. n차 다항식은 2n개의 서로 다른 것으로 구성된다. n보다 낮은 차수의 솟수 다항식이 각각 몇개나 존재하는지를 알 수 있다면, 이들로부터 몇 개의 서로 다른 곱(Product)을 형성시킬 수 있는지 알 수 있을 것이다. 이러한 두 숫자(n보다 낮은 차수의 솟수 다항식의 갯수와 이들로부터 형성되는 서로 다른 곱의 갯수) 사이의 차(Difference)가 바로 n차 솟수 다항식의 갯수이다. 이들 숫자를 각각 적당히 한정함으로써 n차 촛수 다항식의 갯수를 한정할 수 있게 된다.

11-7  원시근

오류정정 코드(Error-correcting code)의 실현에 들어가기 전에 또 하나의 중요한 사항을 언급해 두고자 한다. 일반적 대수(Normal algebra)에 있어서 1의 n제곱근(the nth of unity)은 방정식 xn - 1 Ａ 0의 해(Solution)이다. 또한 이는

[eqn: e^{j``2pik/n} , ~ k``Ａ``0,~1,~2, ~□,~(n``-``1`)]	(11-29)

로 주어진다. Euler의 공식으로부터 (ej2□k/n)n Ａ cos2□k ／ jsin2□k Ａ 1임을 상기하라. 여기서 j는 허수단위(Imaginary unit)를 표시한다.

이들 근 중 어느 하나라도 그것의 거듭제곱을 연속적으로 구해 나가면 결국 (11-29)에 주어진 모든 근을 얻을 수 있다. 여기서 k는 n에 대하여 비교솟수(Relative prime)임을 가정하였다. 이러한 사실을 입증하기 위하여 (11-29)에 주어진 근을 m Ａ 1, 2, □, (n - 1), n에 대하여 거듭제곱을 취하여 보자. 이의 m제곱(mth power)은

[eqn: e^{j``2pikm/n}]	(11-30)

와 같이 표시되며, 이들 중 어느 두 개가 같다고 가정하면

[eqn: e^{j``2pikm_1 /n} ``Ａ`` e^{j``2pikm_2 /n}]	(11-31)

와 같은 식으로 나타낼 수 있다. 이것은 다시

[eqn: e^{j``2pik(m_1 - m_2 ) /n} ``Ａ`` 1]	(11-32)

로 쓸 수 있다. 이 방정식은

[eqn: {k`(m_1 - m_2 )} over n ``Ａ`` rm 정수]	(11-33)

일 때 만족한다. 여기서 k는 n에 대하여 비교솟수(Relative prime : 공약수가 없음)이므로 (m1 - m2)는 n으로 나누어 떨어져야만 한다. 그러나 m1과 m2는 모두 n이하의 수이므로 (m1 - m2)는 n보다 작다. 따라서 (11-33)을 만족하기 위해서는 m1 Ａ m2이여야 한다. 그러므로 k가 n에 대하여 비교솟수(Relative prime)이면, 하나의 근에 대한 연속적인 거듭제곱(Successive power)은 모든 근을 형성하게 된다. 우리는 이 근을 원시근(Primitive root)이라 부르기로 한다.

이러한 원시근(Primitive root)이 우리들의 이론에 있어서 중요한 위치를 차지하는 이유는 우리가 필요로 하는 모든 숫자를 제공하는 발생기(Generator)의 역할을 하기 때문이다. 코딩이론에서는 이러한 내용을 오로지 mod-2 산술 내에서 검토한다.

11-8  대수학적 Hamming 코드

제 4-3절에서 밝힌 바와 같이, 완전 Hamming 코드(Perfect Hamming code)는 n Ａ 2m １ 1 개의 bit로 구성된다. n Ａ 7 Ａ 23 １ 1인 경우, 이 코드체계에 대한 패리티 검사행령(Parity- check matrix)은 (11-6)으로부터 다음과 같이 표시될 수 있을 것이다.

[eqn: M ``Ａ`` pmatrix {0 & 0 & 0 & 1 & 1 & 1 & 1 # 0 & 1 & 1 & 0 & 0 & 1 & 1 # 1 & 0 & 1 & 0 & 1 & 0 & 1 }]	(11-34)

여기서 행렬 M의 각 열(Column)을 서로 교환하더라도, 등가코드(제 4-4절)를 형상하므로, 근본적으로 코드체계의 특성은 변하지 않는다. 단지 단일오류(Single error)가 발생하였을 때 나타나는 Syndrome을 어느 열(Column)에서 어떻게 찾아 내느냐의 문제만이 달라질 뿐이다.

이제, 이 장을 통하여 전개하려는 새로운 대수학적 접근방식(Algebraic error)을 사용하기 위하여 다음과 같은 솟수 다항식(Prime polynomial)을 고려하여 보자.

[eqn: x^3 ``／``x ``／``1]	(11-35)

여기서 a를 이 다항식의 근이라 하면

[eqn: a^3 ``／``a ``／``1]	(11-36)

와 같은 방정식이 성립한다. 이를 우리가 사용하는 mod-2 산술을 이용하여 재배열하면

[eqn: a^3 ``Ａ``a ``／``1]	(11-37)

이 된다. 이 식은 a에 대한 3제곱 혹은 그 이상의 거듭제곱이 그 보다 낮은 거듭제곱의 식으로 표시될 수 있음을 압시하고 있다. 따라서 a에 관한 모든 다항식은 1, a, a2의 선형결합(Liner combination)으로 나타낼 수 있다. 이제, 밑으로부터 1, a, a2의 성분을 가진 3차원 열벡터(Column 3-vector)를 사용하여 a에 대한 거듭제곱의 식을 표시하여 보자. 이러한 열벡터들은 해당하는 a의 거듭제곱에 대한 계수(Coefficient)들을 제공하게 된다.

모든 거듭제곱의 식에 a가 곱해지면 벡터의 성분들은 위로 한 위치씩 옮겨가게 되고, a3이 나타나게 되면 언제나 a3 Ａ a ／ 1을 사용함으로써 벡터의 성분들은 오로지 1, a, a2에 대한 것으로만 이루어지도록 할 것이다. 이렇게 하여 a의 여러 가지 거듭제곱의 식을 표시하여 보면 다음과 같다.

[eqn: 1``Ａ`` pmatrix {0# 0# 1``}]

[eqn: a``Ａ`` pmatrix {0# 1# 0``}]

[eqn: a^2``Ａ`` pmatrix {1# 0# 0``}]

[eqn: a^3 ``Ａ``a``／``1``Ａ`` pmatrix {0# 1# 1``}]

[eqn: a^4 ``Ａ``a^2``／``a``Ａ`` pmatrix {1# 1# 0``}]

[eqn: a^5 ``Ａ``a^3``／``a^2``Ａ`a^2 ``／``a``／``1``Ａ`` pmatrix {1# 0# 1``}]

[eqn: a^7 ``Ａ``a^3``／``a``Ａ`` pmatrix {0# 0# 1``}]	(11-38)

결과적으로 a는 이 솟수 다항식의 원시근(Primitive root)에 해당한다. 왜냐하면 a에 의하여 발생되는 여러 가지 거듭제곱의 식들은 서로 다른 7개의 3-tuple들을 모두 (Zero 3-tuple은 제외) 생산하기 때문이다.

이러한 새로운 접근방식을 이용한 패리티 검사행렬을 나타내면 다음과 같다.

[eqn: pmatrix {1 & 1 & 1 & 0 & 1 & 0 & 0 # 0 & 1 & 1 & 1 & 0 & 1 & 0 # 1 & 1 & 0 & 1 & 0 & 0 & 1 }]	(11-39)

취급의 편의를 위하여 열(Clonum)의 순서를 (11-38)에서와 반대로 하였으며, 그 순서는 어느 것으로 하여도 관계 없다. 특히 (11-34)에 나타낸 Hamming 코드의 검사행렬도 이 행렬의 열을 재배열함으로써 나타낼 수 있음을 주목하라. (11-39)의 행렬에 있어서, 수신측(Receiving end)이 수행하는 a의 연속적인 거듭제곱(Successive power)을 사용한 Syndrome의 계산도 비교할 수 있다. Syndrome과 감사행렬의 열(Clonum) 사이의 대응관계를 얻었다면, 그 열과 해당하는 a의 거듭제곱 사이의 대응관계를 발견한 것과 마찬가지일 것이다. 만일, 우리가 이 예제에서 사용한 것과 다른 솟수 다항식 x3 ／ x2 ／ 1을 가지고 전개하였다면, (11-39)와는 약간 다르나 그 특성은 동일한 검사행렬을 얻을 수 있을 것이다.

이러한 대수학적 접근방법(Algebraic approach)을 이용한 인코딩(Encoding) 과정은 어떻게 이루어질 것인가? 우선, Syndrome (0, 0, □, 0)은 오류(Error)가 발생하지 않은 경우를 나타내어야 하므로, 이 때의 전송다항식(Sent polynomial)은 Modulus 다항식 x3 ／ x ／ 1로 나누어 떨어져야 할 것이다. 따라서 a6, a5, a4, a3에 해당하는 위치에는 정보 bit(Information)를 두고, a2, a, 1에 해당하는 위치에는 임시로 0을 부여한다. 이렇게 하여 형성된 다항식을 Modulus 다항식으로 나누어 보면 하나의 나머지(Remainder)를 얻게 될 것이다. 이 때, 이 나머지를 앞에서 형성했던 다항식의 a2, a, 1에 해당하는 위치에 부여하면(mod-2 addition), 그 결과로 나타나는 다항식은 원래의 Modulus 다항식으로 나누어 떨어지게 될 것이다. 이것이 바로 인코딩 과정(Encoding process)이다. 즉 Modulus 다항식에 의한 나머지를 코드 다항식(Code polynomial)의 마지막 세 위치에 부여함으로써 전체 다항식이 솟수 다항식으로 나누어 떨어지도록 하는 것이다.

그렇다면 이러한 코드체계의 디코딩 과정(Decoding process)은 어떠한가? 수신측(receiving end)에서는 단순히 채널을 통하여 들어 온 다항식을 Modulus 다항식으로 나눈다. 이 나눗셈의 결과로 나타나는 나머지(remainder)는 바로 Syndrome에 해당하며, 이를 a에 관한 다항식으로 펴현하면 해당하는 열(Column)을 찾아낼 수 있으며, 그 위치가 오류발생위치(Error position)인 것이다.

우리는 이 절을 통하여 제 4-3절에서 취급하였던 Hamming 코드를 대수학적 접근방법(Algebraic approach)에 의하여 유도하였다. 하나의 예제를 통하여 이러한 체계의 개념을 좀 더 구체화시케 보도록 한다.

예제 □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

위에서 설명했던 코드체계에 대하여 다음과 같은 메시지가 주어져 있다.

1 0 0 1 _ _ _

이를 인코딩하고, 하나의 단일오류(Single error)를 가정하여, 이것이 수신측에서 디코딩될 때 처리되는 과정을 보여라.

♠♠♠♠♠ 풀이

주어진 메시지에 대한 다항식은 x6 ／ x3이므로, 이를 솟수 다항식 x6 ／ x3 ／ 1로 나누어 그 나머지(Remainder)를 표시하면 다음과 같다.

1      0     1       0

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

1 0 1 1 －1 0 0 1 0 0 0

1 0 1 1

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

0  1  0  0

0  0  0  0

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

1  0  0  0

1  0  1  1

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

0  1  1  0

0  0  0  0

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

1  1  0   ←  나머지

따라서 코드화된 메시지는

(1 0 0 1 1 1 0)

이다. 이 때, 코드화된 메시지에 대한 코드 다항식(Code polynomial)은 Modulus 다항식 x3 ／ x ／ 1로 나누어 떨어진다.

위 메시지가 채널을 통하여 전송되는 도중에 다음과 같이 밑줄친 부분에 단일오류가 발생하였다고 가정하자.

(1 0 0 0 1 1 0) ← 수신메시지

수신측에서는 이 메시지를 Modulus 다항식으로 나누어 검토하게 되므로

1      0     1       1

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

1 0 1 1 －1 0 0 0 1 1 0

1 0 1 1

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

0  1  1  1

0  0  0  0

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

1  1  1  1

1  0  1  1

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

1  0  0  0

1  0  1  1

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

0  1  1   ←  나머지

와 같은 계산을 수행하게 될 것이다. 따라서 그 결과로서 나타나는 나머지는

[eqn: a^3``Ａ`` pmatrix {0# 1# 1``}]

이 되며, 이는 4번째 위치에서 오류가 발생하였음을 나타낸다. 이 4번째 위치에 1을 더하여(mod-2) 정정된 메시지를 얻을 수 있고, 송신측에서 보낸 정보를 구하기 위해서는 단순히 마지막의 3 bit를 제거하면 된다.

11-9  단일오류 정정코드의 인코딩과 디코딩

이 장을 통하여 전개되는 대수학적 코딩이론(Algebraic coding theroy)은 앞에서 설명하였던 크드체계를 기본으로 하여 개발되어 왔다. 코딩이론을 전개하는데 있어서 반드시 이렇나 코드체계를 사용해야 하는 것은 물론 아니다. 그러나 이들은 하드웨어(H/W : Hardware)나 소프트웨어(S/W : Software)를 사용하여 쉽게 실현될 수 있다는 장점을 가지고 있다. 사실, 다항식을 사용한 나눗셈 과정으로부터 나머지를 도출해 내는 일은 실현상 대단히 복잡한 것처럼 보이지만 궤환로를 가진 레지스터(Shift register feedback path)에 의하여 간단하게 구현될 수 있다. 앞 절에서와 같이 다항식을 이용한 7-bit 코드체계를 사용한다고 가정하고, 정보메시지 1001을 인코딩해 보기로 하자. 먼저, 인코딩된 메시지를 다음과 같은 형태의 다항식으로 표시하자.

[eqn: 1□x^6``／``0□x^5 ``／``0□x^4``／``0□x^3 ``／``0□x^*2 ``／``0□x^* ``／``1^*]	(11-40)

여기서 *(Asterisk)이 붙어있는 항들은 계수(Coefficient)가 정해져야 하는 항임을 나타내고 있다. 또한, 이들 계수는 (11-40)이 Modulus 다항식 x3 ／ x2 ／ 1로 나누어 떨어진다는 조건에 의하여 결정된다.

앞 절에서와 같이, 결정되지 않은 이들 계수를 모두 0으로 하고 Modulus 다항식으로 나누어 그 나머지(Remainder)를 얻는다. 그 결과, 나머지는 □110□이 되므로 a2 ／ a로 펴시된다. 이를 원래의 정보메시지 a6 ／ a3에 더하면 다음과 같이 인코딩된 메시지를 얻게 된다.

[eqn: a^6``／``a^3 ``／``a^2``／``a``Ａ``(a^3 ``／`` a``／``1`)``(a^3``／``a`)]	(11-41)

이 식에서 나타낸 바와 같이 인코딩된 메시지는 Modulus 다항식 a3 ／ a ／ 1로 나누어 떨어진다. 이러한 나눗셈 과정을 실제적으로 어떻게 구헌할 것인가? 그림 11-1과 같은 쉬프트 레지스터(Shift resiter)를 생각하여 보자.

그림 11-1  궤환로를 가진 쉬프트 레지스터

메시지는 레지스터의 오른쪽으로부터 높은 차수를 선두로 하여 들어오게 되고, 마지막 3개의 □0□이 자동적으로 공급된다고 가정하자. 또한 레지스터의 아래쪽에 표시된 통로는 궤환(Feedback)이 이루어지는 위치를 표시하고 있다. 이들 궤환로(Feedback path)는 Modulus 다항식에 의하여 결정된다. 레지스터의 최상위(the hoghest position)에 □1□이 부여되어 있을 때, 궤환로가 도달하는 위치에 □1□이 더해지게 된다. 그림 11-2에 이러한 동작에 대한 자세한 과정을 나타내었다 여기서 첫번째 숫자(x6의 계수)가 레지스터의 최상위(the left-hand position)에 부여될 때까지 수행되는 4번의 자리이동(Shift)은 검토할 필요가 없으므로 표시하지 않았다. 이 그림에 있어서 겹줄로 표시된 각 난의 첫번째 줄은 레지스터의 시작상태(Start)를 표시하며, 두번째 줄을 궤화로에 의하여 궤환이 이루어진 상태를 나타내고, 마지막 세번째 줄을(겹줄 바로 위)덧셈의 결과로 나타난 상태를 표시하고 있다. 겹줄(Double line)의 위치에서는 자리 이동(Shift)이 일어난다. 그리고 그 다음 줄은 이러한 자리이동의 결과로 나타난 상태를 표시한다. 두 개의 겹줄 사이에 있는 세 개의 줄은 다음 자리이동이 일어나기 전까지 일어나는 일들을 구체적으로 나타낸 것이다.

그림 11-2  동작의 세부도

전체적으로 이러한 구성을 갖는 세 줄(Three lines)은 서로 다른 4가지가 존재한다. 그 마지막 자리이동의 결과가 바로 나머지(Remainder)가 된다. 앞에서 우리가 사용하였던 나눗셈의 결과와 비교하여 보면, 결굴 그림 11-1의 쉬프트 레지스터는 나눗셈을 수행하였음을 알 수 있다.

그림 11-3은 이러한 코드체계의 인코더를 실제로 구현한 것이다.

앞에서와 같이 메시지는 레지스터의 오른쪽으로부터 차례로 입력되고, 레지스터 왼쪽에는 자리이동에 의하여 메시지를 출력하기 위한 스위치가 마련되어 있다. 나머지(Remainder)가 계산되었을 때 원래의 정보 bit들은 이미 출력되어 있는 상태이며, 스위치를 레지스터 방향으로 접속시키므로써 계산된 나머지를 얻을 수 있도록 하면 된다. 이 때, 계산된 나머지의 첫번째 bit는 언제나 0이므로 이는 버린다. 인코딩의 과정은 이렇게 간단히 실현된다.

그림 11-3  인코더의 구현

쉬프트 레지스터는 실제적인 하드웨어로 실현하기가 매우 용이하다. 또한 각 위치의 mod-2 덧셈은 Exclusive-OR 게이트로 실현하면 된다. 나머지 하드웨어도 간단한 소자를 연결하므로써 쉽게 구현될 수 있다.

소프트웨어를 사용하여도 어렵지 않게 프로그래할 수 있다. 최상위(left position)에 □1□이 부여된 경우에는 궤환로(Feedback path)가 있는 위치에 1을 더해주면(mod-2) 되고, 계산이 끝난 상태에서 자리이동(Shift)을 반복한다. 이러한 과정을 구체적으로 실현하는 프로그램도 결코 복잡하지는 않을 것이다.

이러한 코드체계의 인코딩 과정은 이처럼 간단한 하드웨어나 소프트웨어에 의하여 실현된다.

다음으로 우리는 디코딩 과정에 대하여 취급해 보기로 한다. 수신측에서 수행되는 디코딩 과정(Decoding process)은, 오류가 발생하였을 때 이를 정정하기 위하여 먼저 들어온 메시지의 일부를 간직해 두어야 한다는 점을 제외하고는 인코딩 과정과 유사하다.

나눗셈 과정을 통하여 얻은 나머지는 발생 오류의 위치를 나타내는 Syndrome에 해당한다. 나머지가 0이면 메시지는 오류없이 정확하게 전송된 것이며, 앞의 4 bit만을 취함으로써 송신측에서 보낸 정보를 얻을 수 있다.

나머지가 0이 아닌 겨우, 그것은 a의 어떤 거듭제곱 ak으로 나타나게 될 것이다. 여기에 사용된 지수 k를 어떻게 발견할 것인가? 물론 찾아보기(Table look-up)에 의해서도 이를 디코딩할 수 있다. 그러나 이러한 상황은 짧은 코드의 경우에나 가능한 방법이고, 어느 정도 복잡한 코드에 대해서는 너무 큰 기억장치를 요구하게 되므로 불합리해진다(최근에 기억장치의 가격은 매우 저렴해지고 있다).

제 11-8절의 내용을 상기하여 보면, a7 Ａ 1이었다. 따라서 a6 Ａ 1/a이다. 이러한 사실을 이용하여, 우리는 Syndrome에 대한 ak을 찾아낼 수 있다.

[eqn: &(a^6`)``a^k``Ａ``a^{k-1} , mod-(a^3``／``a``／``1`)## &(a^6`)``a^k-1 ``Ａ``a^{k-2} ## &~~~~~~~~~~~~~□]	(11-42)

이러한 과정을 나머지 □001 Ａ 1□이 될 때까지 계속하면 k의 값을 알 수 있다.

예를 들어서 앞에서와 같이 송신측에서 인코딩되어 전송된 메시지가

1 0 0 1 1 1 0

이라 하고, 전송 주에 채널로부터 잡음(Noise)의 영향을 받아 a2위치에 단일 오류(Single error)가 발생하였다고 가정하자. 채널로부터 수신된 메시지는

1 0 0 1 0 1 0

이 된다. 여기서 오류에 의하여 변경된 bit에는 밑줄을 그어 놓았다. 수신측에서 수행되는 나눗셈 과정은 다음과 같이 진행될 것이다.

1      0     1       0

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

1 0 1 1 －1 0 0 1 0 1 0

1 0 1 1

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

0  1  0  0

0  0  0  0

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

1  0  0  1

1  0  1  1

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

0  1  0  0

0  0  0  0

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

1  0  0   ←  나머지

따라서 이 나머지 값을 ak이라 두고 지수 k를 구하여 보자.

[eqn: a^k``Ａ`` pmatrix {1# 0# 0``}]	(11-43)

식의 양변에 a6 Ａ 1/a을 곱하면 좌변은 차수가 1 줄어들게 되고, 우변은 각 성분(Component)이 아래로 한 위치씩 이동하게 된다.

[eqn: a^3`a^k``Ａa^k-1``Ａ`` pmatrix {0# 1# 0``}]	(11-44)

이러한 과정을 우변에서 1이 인식될 때까지(성분 1이 최하위에 놓일 때까지) 계속 진행하면

[eqn: a^6`a^k-1``Ａa^k-2``Ａ`` pmatrix {0# 0# 1``} ``Ａ``1]	(11-45)

와 같은 식을 얻을 수 있다. a6 Ａ 1이므로 k Ａ 2임을 알 수 있다. 따라서 우리는 a2 위치에서 오류가 발생하였음을 인식하여, 그 위치에 1을 더하므로써(mod-2) 정정된 메시지를 얻을 수 있는 것이다.

소프트웨어에 의하여 실현하고자 할 때, 이러한 과정은 오로지 오류가 발생한 경우에 한하여 수행된다는 사실을 주의하라. 오류가 발생하지 않았다면 각 위치가 모두 0인 Syndrome을 얻게 되며, 이러한 경우에는 Syndrome을 계산해 내는 일 이외에 더 이상 수행해야 할 일이 없는 것이다. 또한 실시간 코딩시스템(Real-time coding system)에 있어서는 이러한 과정이 수행되든지 혹은 수행되지 않든지 그 계산을 수행할 수 있는 용량(Capacity)을 반드시 가지고 있어야 한다.

11-10  이중오류 정정코드

이중오류 정정코드(Double-error-correcting code)에 대하여 설명하기 위해서는 4개의 패리티 검사(Parity checks) 위치를 갖는 15-bit Hamming 코드의 특성을 관찰해 볼 필요가 있다.

먼저 Modulus 다항식으로 사용할 솟수 다항식(Prime polynomial)을 선택하기 위하여

[eqn: x^4 ``／``x``／``1]	(11-46)

을 검토하여 보자. x는 이 다항식의 분해요소(Factor)가 되지 않음은 명백하다. 또한   (x ／ 1)을 분해요소로 갖기 위해서는 모든 계수의 합이 0이 되어야 하므로(연습문제 9번을 참조하라) 이것 역시 이 다항식의 분해요소가 될 수 없다. 따라서 우리는 2차 다항식 x2 ／ x ／ 1에 대해서만 살펴보면 (11-46)의 다항식이 솟수 다항식(Prime polynomial)임을 입증할 수 있다.

다음으로 이것이 원시근 조건(Primitive condition)을 만족하는지를 검토할 필요가 있다. a에 대한 거듭제곱(Powers of a)들은 다음과 같이 계산된다.

[eqn: 1`Ａ`` pmatrix {0# 0# 0# 1``}]

[eqn: a`Ａ`` pmatrix {0# 0# 1# 0``}]

[eqn: a^2`Ａ`` pmatrix {0# 1# 0# 0``}]

등등	(11-47)

예상했던 바, a15 Ａ 1이며, 그 이전의 거듭제곱에서는 1이 되는 것이 없다. 그러므로 (11-46)은 원시근 조건(Primitive condition)을 만족하는 다항식이며, 패리티 검사행렬(Parity-check matrix)은 다음과 같이 주어진다.

[eqn: a^14 ``a^13 ``a^12 ``a^11 ``a^10 ``a^9 ``a^8 ``a^7 ``a^6 ````a^5 `````a^4 ````a^3 ````a^2 ````a ````1]

[eqn: pmatrix {1 & ``1 & ``1 & ``1 & ``0 & ``1 & ``0 &``1 &``1 &``0 &``0 &``1 &``0 &``0 &``0# 0 &``1 &``1 &``1 &``1 &``0 &``1 &``0 &``1 &``1 &``0 &``0 &``1 &``0 &``0# 0 &``0 &``1 &``1 &``1 &``1 &``0 &``1 &``0 &``1 &``1 &``0 &``0 &``1 &``0# 1 &``1 &``1 &``0 &``1 &``0 &``1 &``1 &``0 &``0 &``1 &``0 &``0 &``0 &``1}]	(11-48)

이는 15-bit 코드체계에 있어서 단일오류(Single error)를 정정할 수 있는 패리티 검사행렬(Parity-check matrix)이다. 만일 두 개 이상의 오류를 정정할 수 있도록 하려면, 이 행렬에 추가적인 행(Row)들을 부가하여야 할 것이다. 이중오류의 정정을 위해서는 여기에 4개의 행을 더 첨가하면 될 것이다.

현재로서는 서로 다른 두 개의 오류에 대해서 동일한 Syndrome을 발생시킬 가능성이 있다. 즉

[eqn: a^k ``／`` a^m ``Ａ`` a^k' ``／``a^m']	(11-49)

을 만족하는 지수들이 나타날 수 있는 것이다. 예를 들어서, a와 a2 위치의 두 열(Column)은 a12과 a14 위치의 두 열과 동일한 Syndrome을 제공하게 된다. 따라서 우리는 (11-48)에 주어진 것보다 더 많은 행(Row)을 필요로 하게 된다. 그렇게다면 이 추가적인 행들을 위하여 a2을 발생기(Generator)로 사용하면 어떠한가? 그러나 블행히도 두 개의 Syndrome

[eqn: a_1 ``／`` a_2 ``Ａ`` s_1~~ ;~~1 st~Syndrome]	(11-50)

과

[eqn: a_1^2 ``／`` a_2^2 ``Ａ`` s_2~~ ;~~2 nd~Syndrome]	(11-51)

은 다음과 같은 방정식에 의하여 관련되어 있다.

[eqn: s_1^2 ``Ａ``(a_1 ``／``a_2` )^2 ``Ａ``a_1^2 ``／`` 2a_1 `a_2 ``／``a_2^2 ``Ａ`` a_1^2 ``／`` a_2^2 ``Ａ``s_2]	(11-52)

여기서 a1은 a의 한 거듭제곱이고, a2는 a의 또 다른 거듭제곱이다.

다음으로 위의 2nd-Syndrome으로 세제곱(Cume)을 사용하여 보자. 즉

[eqn: a_1^3 ``／`` a_2^3 ``Ａ`` s_2~~ ;~~2 nd~Syndrome]	(11-53)

이를 s1을 사용하여 다시 정리하면 다음과 같다.

[eqn: s_2 ``&Ａ``a_1^3 ``／``a_2^3``Ａ``(a_1``／`` a_2 `)`( `a_1^2 ``／``a_1 `a_2`` ／``a_2^2` ) ## &Ａ``s_1 `( a_1^2 ``／`` a_1` a_2 ``／``a_2^2 `)## &Ａ``s_1` (a_1 `a_2 ``／``s_1^2` )]

(11-54)

여기서

[eqn: a_1 ``／`` a_2 ``Ａ`` s_1]

[eqn: a_1 `a_2``Ａ``s_1^2 ``／``s_2 over s_1 , ~s_1 ``□``0]	(11-55)

이다.

이러한 계산에 있어서, 좀 더 원활한 곱셈(혹은 나눗셈)을 수행하기 위해서는 관계하는 양들을 모두 거듭제곱(Power)의 형태로 표현하는 것이 좋을 것이다. 왜냐 하면 이들 거듭제곱 형태의 곱셈(혹은 나눗셈)은 지수의 덧셈(혹은 뺄셈)으로 이루어지기 때문이다. 또한 덧셈(Addition)을 실시하고자 할 때에는 이들을 열벡터(Column vector)의 형태로 표현하여 대응하는 성분(Compmnent)을 서로 더해주면 되는 것이다. 그러므로 우리는 계속 이러한 두 가지 형태의 표현(거듭제곱의 형태와 벡터 혹은 행렬의 형태)을 사용하여 계산을 진행하게 된다. 또한 검사행렬(Check matrix) 자체는 변환을 위한 표(Table)를 제공하게 된다.

(11-55)와 같이 두 수의 합(Sum)과 곱(Product)이 주어지면, 우리는 거의 자동적으로 2차 방정식(Quadratic equation)의 □근과 계수와의 관계□를 생각하게 된다.

[eqn: a^2 ``-``(s_1` ) `a ``／``(s_1^2 ``／``s_2 over s_1 `) ``Ａ``0]	(11-56)

이 방정식의 두 근(Roots)은 두 개의 오류에 대한 Syndrome을 제공한다.

만일 하나의 오류만이 발생하였다면 Syndrome은

[eqn: a_1 ``Ａ`` s_1]

[eqn: a_1^3 ``Ａ`` s_2]	(11-57)

이 된다. 또한

[eqn: s_1^2 ``／``s_2 over s_1 ``Ａ``2s_1^2 ``Ａ``0]	(11-58)

이 성립하게 되므로, 2차 방정식은

[eqn: a^2 ``／`` s_1 a``Ａ``0~~~{rm 혹은}~~~&a ``Ａ``s_1# & a ``Ａ``0]	(11-59)

으로 귀결된다.

오류가 전혀 발생하지 않은 경우에는

[eqn: s_1 ``Ａ`` s_2 ``Ａ``0]	(11-60)

이 되고, 2차 방정식은

[eqn: a^2 ``Ａ``0~~~{rm 혹은}~~~& a ``Ａ``0# & a ``Ａ``0]	(11-61)

으로 귀결된다.

따라서 행렬의 아래쪽 행(Row)들은 a2을 발생기로 하여 구성한다. 결국 행렬의 각 열(Column)들은 다음의 거듭제곱에 대응하게 된다.

[eqn: 1, ~a^3 ,~ a^6,~ a^9 ,~ a^12 ,~ a^15 ,~ a^18 ,~ □]

이에 따라 이중오류 정정코드(Double-error-correcting code)를 위한 패리티 검사 행렬(Parity-check matrix) M은 다음과 같이 구성된다.

[eqn: a^14 `a^13 `a^12 `a^11 `a^10 ``a^9 ``a^8 ``a^7 ``a^6 ````a^5 `````a^4 ````a^3 ````a^2 ````a ``````1]

[eqn: 1 & ``1 & ``1 & ``1 & ``0 & ``1 & ``0 &``1 &``1 &``0 &``0 &``1 &``0 &``0 &``0# 0 &``1 &``1 &``1 &``1 &``0 &``1 &``0 &``1 &``1 &``0 &``0 &``1 &``0 &``0# 0 &``0 &``1 &``1 &``1 &``1 &``0 &``1 &``0 &``1 &``1 &``0 &``0 &``1 &``0# 1 &``1 &``1 &``0 &``1 &``0 &``1 &``1 &``0 &``0 &``1 &``0 &``0 &``0 &``1]

M  Ａ

[eqn: 1 &``1 & ``1 & ``1 & ``0 &``1 &``1 &``1 &``1 &``0 &``1 &``1 &``1 &``1 &``0# 1 &``0 &``1 & ``0 & ``0 &``1 &``0 &``1 &``0 &``0 &``1 &``0 &``1 &``0 &``0# 1 &``1 &``0 &``0 &``0 &``1 &``1 &``0 &``0 &``0 &``1 &``1 &``0 &``0 &``0# 1 &``0 &``0 &``0 &``1 &``1 &``0 &``0 &``0 &``1 &``1 &``0 &``0 &``0 &``1]

Syndrome s1은 행렬의 상위 행(Upper rows)으로부터, s2는 행렬의 하위 행(Lower rows)으로부터 얻어진다. 이들 두 Syndrome은 2차 방정식을 통하여 두 개의 근을 제공하므로써 이중오류(Double error)의 위치를 지정하게 된다.

그렇다면 이제 이들 코드체계를 어떻게 인코딩할 것인가를 생각하여 보자. 모든 패리티 검사를 동시에 만족시키는 방법을 명확히 제시할 수는 없으나, 유명한 Chiness 나머지 정리(Chiness remainder theorem)에 근거하여 다중오류 정정에 관한 기본적 개념을 전개하여 보기로 하자.

이해하기 쉬운 구체적 예로서, 모든 위치에 0을 가지는 코드를 생각하자. 다음으로 이 코드가 채널을 통하여 전송되는 도중에 a3과 a4 위치에서 오류를 발생시켜 1로 변경되었다고 가정하자. 그렇다면 수신메시지에 대한 Syndrome은 해당하는 두 열(Column)의 합으로 나타나게 될 것이다.

[eqn: pmatrix { 1# 0# 0# 0# 1# 0# 1# 0}]	／	[eqn: pmatrix { 0# 0# 1# 1# 1# 1# 1# 1}]	Ａ	[eqn: pmatrix { 1# 0# 1# 1# 0# 1# 0# 1}]	혹은	s1 Ａ	[eqn: pmatrix { 1# 0# 1# 1}]	Ａ a7
						s2 Ａ	[eqn: pmatrix { 0# 1# 0# 1}]	Ａ a8

(11-63)

여기서

[eqn: s_1^2 ``+``s_2 over s_1 ``=`` (a^7 `)^2 ``+`` a^8 over a^7 ``=`` a^14 ``+``a``=``]	[eqn: pmatrix { 1# 0# 0# 1}]	／	[eqn: pmatrix { 0# 0# 1# 0}]	Ａ	[eqn: pmatrix { 1# 0# 1# 1}]	[eqn: =``a^7]

(11-64)

와 같이 계산되므로, 구하는 2차 방정식은 다음과 같다.

[eqn: x^2 ``／``a^7` x ``／`` a^7``Ａ``0]	(11-65)

여기에 x Ａ 1을 대입하면, 1 ／ a7 ／ a7 Ａ 0,

[eqn: pmatrix { 0# 0# 0# 1}]	／	[eqn: pmatrix { 1# 0# 1# 1}]	／	[eqn: pmatrix { 1# 0# 1# 1}]	Ａ	[eqn: pmatrix { 0# 0# 0# 1}]	[eqn: □``0]

(11-66)

x Ａ a를 대입하면 ;

[eqn: a^2 ``+`` a^8 ``+`` a^7``=]	[eqn: pmatrix { 0# 1# 0# 0}]	／	[eqn: pmatrix { 0# 1# 0# 1}]	／	[eqn: pmatrix { 1# 0# 1# 1}]	Ａ	[eqn: pmatrix { 1# 0# 1# 0}]	[eqn: □``0]

(11-67)

x Ａ a2를 대입하면 ;

[eqn: a^4 ``+`` a^9 ``+`` a^7``=]	[eqn: pmatrix { 0# 0# 1# 1}]	／	[eqn: pmatrix { 1# 0# 1# 0}]	／	[eqn: pmatrix { 1# 0# 1# 1}]	Ａ	[eqn: pmatrix { 0# 0# 1# 0}]	[eqn: □``0]

(11-68)

x Ａ a3를 대입하면 ;

[eqn: a^6 ``+`` a^10 ``+`` a^7``=]	[eqn: pmatrix { 1# 1# 0# 0}]	／	[eqn: pmatrix { 0# 1# 1# 1}]	／	[eqn: pmatrix { 1# 0# 1# 1}]	Ａ	[eqn: pmatrix { 0# 0# 0# 0}]	[eqn: Ａ``0]

(11-69)

x Ａ a4를 대입하면 ;

[eqn: a^8 ``+`` a^11 ``+`` a^7``=]	[eqn: pmatrix { 0# 1# 0# 1}]	／	[eqn: pmatrix { 1# 1# 1# 0}]	／	[eqn: pmatrix { 1# 0# 1# 1}]	Ａ	[eqn: pmatrix { 0# 0# 0# 0}]	[eqn: Ａ``0]

(11-70)

x Ａ a5를 대입하면 ;

[eqn: a^10 ``+`` a^12 ``+`` a^7``=]	[eqn: pmatrix { 0# 1# 1# 1}]	／	[eqn: pmatrix { 1# 1# 1# 1}]	／	[eqn: pmatrix { 1# 0# 1# 1}]	Ａ	[eqn: pmatrix { 0# 0# 1# 1}]	[eqn: □``0]

(11-71)

등을 얻을 수 있다. 그러므로 두 오류(Errors)는 a3과 a4 위치에서 발생하였음을 알 수 있다.

우리는 이러한 코드체계를 통하여 동시에 발생한 두 개의 오류(Double-error) 혹은 단일오류(Single-error)를 찾아 정정할 수 있으며, 그러한 시스템이 어떻게 동작하는가를 계산에 의하여 자세히 인식할 수 있다. 또한 a의 여러 거듭제곱(Powers of a)들은 행렬의 상위 4개의 행(Row)에 주어져 있다.

다중오류 정정코드(Mulitiple-error-correcting code)에 있어서도 간단한 디코딩 규칙(Decoding rule)이 존재한다. Syndrome에 관련된 문제를 원활하게 처리하기 위해서는 컴퓨터 프로그램으로 작성하는 것이 좋을 것이다. 예로써, 이중오류 정정코드(Double- error-correcting code)를 위해서는 2차 방정식의 근을 구하는 프로그램이 요구될 것이다. 이러한 근을 구하는 가장 간단한 방법은 저장된 메시지(Stored message)의 각 위치에 대하여 주어진 2차식을 계산하여 보는 것이다. 이 때, 어떤 a의 거듭제곱이 2차식을 만족하면 그것은 방정식의 근이 되며, 정정되어야 할 위치를 지정하게 될 것이다.

이러한 계산은 오로지 오류가 발생한 경우에 한하여 필요함은 명백하다. 그러나 실시간 처리 시스템(Real-time signaling system)에 있어서는 동시에 몇 개의 메시지를 저장할 필요가 있다. 왜냐하면 실시간 처리 시스템이 동작할 때에는 하나의 메시지에 대하여 정정을 수생하면서 두번째 메시지의 정정에 관한 Syndrome 등을 계산하는 동시에 세번째 메시지의 초기상태에 대하여 검사하는 등 병렬처리 형태로 작용하기 때문이다. 그러므로 이러한 시스템에 있어서는 최소한 두 메시지에 대한 시간지연(Time delay)이 항상 존재하게 된다. 이러한 사실은 제어회로(Control circuit)의 궤환로(Feedback path)를 구성하는데 있어서 대단히 중요한 문제이다. 이는 시스템의 불안정상 문제(Instability problem)를 야기시킬 수 있는 것이다.

11-11  요약

이 장에서 우리는 구조적 코드체계(Structured coding system)의 필요성에 관하여 논의하였다. 또한 이러한 구조적 코드체계를 인코딩하고 디코딩하는 체계적인 방법에 대하여 설명하였다. 그러한 과정을 통하여, 하나의 다항식을 다른 다항식으로 나누어 그 나머지를 생성시키는 방법을 제시하였다.

나눗셈을 통하여 형성되는 Syndrome은 채널에 의하여 발생하는 오류(Error)에만 관계하고 원래의 정보메시지와는 무관하다는 사실을 입증하였다. 다음으로 하나의 다향식을 솟수 다항식으로 나누어 그 나머지를 취하는 일반적 형태의 필요성을 강조하였다. 돗붙여서, 모든 근의 요소들이 다항식의 원시근(Primitive roots)에 대한 거듭제곱으로 표시되어야 한다는 조건을 제시하였다. 마지막으로, 이들 이론을 이용하여 이중오류 정정코드(Double-eeror-correcting code)를 구성하는 방법을 언급하였다.

우리는 유한필드(Finite field)에 대하여 필요한 정체적 이론이나 코딩에 관한 일반적 이론을 제시하지는 않았다. 단지 하나의 코드체계가 대수학적으로 형성되는 과정을 보여 주었을 뿐이다. 특별히 예시된 코드체계는 우리가 취급하는 특수한 경우를 이해하는데 도움을 주기 위하여 도입되었다. 사실, 이 장을 통하여 제시된 코드체계는 코딩이론의 극히 일부에 지나지 않는다. 코딩이론에 관하여 좀 더 체계적이고 구체적인 연구를 원하는 독자는 참고문헌에 소개된 여러 서적들을 참조하기 바란다(참고문헌 [1], [5], [8], [18], [20] 등이 제시된다).

코딩이론의 대부분은 계산비용(cost of computing)이 비교적 싸고 가억장치의 비용이 비교적 비쌌던 시기에 제창되었다. 1985년을 기준으로 하여 기억장치(Storage)에 사용되는 소자들의 가격이 급격히 떨어지자 과거에 개발되었던 모든 이론을 전면적으로 재검토해야 할 필요성이 야기되었다. 기억장치를 최대로 활용하는 찾아보기(Table look- up) 형식의 인코딩과 디코딩을 수행하는 코드체계의 설계 방법들이 유행하게 되었고, 계산의 복잡성을 근간으로 하는 연구, 개발은 훨씬 줄어 들게 되었다. 아시 한번 강조하건대, 코딩이론의 거의 모두가 백색잡음(White noise)을 가정하여 개발되었다. 그러나 실제에 있어서는 채널 상의 잡음이 백색잡음이 아닌 경우가 많으며, 백색잡음을 가정하여 얻어 낸 여러 가지 이론적 장점들이 실제적으로는 잘 적용되니 않을 수도 있는 것이다.

연 습 문 제

11.1	랜덤코드(Random code)의 정보이론적 의의를 밝히고, 이것이 실제적인 코드시스템으로 사용될 수 없는 이유를 설명하라.

11.2	백색잡음(White noise)을 근거로 하여 설계된 코드체계를 백식이 아닌 잡음 특성을 가지는 채널에 적용하여 사용할 때, 채널의 부작용 효과를 최소한으로 줄일 수 있는 방책을 논의하라.

11.3	Hamming 코드에 대한 패리티 검사행렬(Parity-check matrix) M이 다음과 같이 표시된다.

[eqn: M ``Ａ`` pmatrix {0 & 0 & 0 & 1 & 1 & 1 & 1 # 0 & 1 & 1 & 0 & 0 & 1 & 1 # 1 & 0 & 1 & 0 & 1 & 0 & 1 }]

(1) 수신된 메시지가 c ／ e Ａ (0011001)일 때, Syndrome을 계산하고, 이 메시지 내에서 오류가 발생하였는지를 판단하라.

(2) 수신된 메시지가 c ／ e Ａ (0011101)일 때, Syndrome을 계산하고, 이 메시지 내에서 오류가 발생하였으면 이를 정정하라.

(3) 주어진 패리티 검사행렬의 행들(Rows)은 선형독립(Linearly independent)임을 밝혀라. 또한, 이 행렬의 Rank는 얼마인가?

11.4	이중오류 검출코드(Double-error-detecting code)에 대한 패리티 검사행렬이 다음과 같이 형성되어 있다.

[eqn: M ``Ａ`` pmatrix {1 & 1 & 1 & 1 & 1 & 1 & 1 &1 # 0 & 0 & 0 & 1 & 1 & 1 & 1 &0 # 0 & 1 & 1 & 0 & 0 & 1 & 1 &0 # 1 & 0 & 1 & 0 & 1 & 0 & 1 &0 }]

수신된 메시지가 아래와 같이 주어질 때, 각 경우에 대하여 Syndrome을 계산하고, 오류가 발생한 상태를 설명하라.

(1) c ／ e Ａ (0 1 1 0 0 1 1 1)

(2) c ／ e Ａ (0 1 1 0 1 1 1 0)

(3) c ／ e Ａ (0 1 1 0 0 1 1 0)

(4) c ／ e Ａ (0 1 1 1 1 1 1 0)

(5) c ／ e Ａ (0 1 1 0 0 0 1 0)

11.5	다음과 같이 주어진 코드열(Code sequence)을 다항식으로 표시하라.

(1) 1, 1, 0, 1, 1, 1

(2) 0, 1, 0, 1, 0, 1

(3) 1, 0, 0, 1, 1, 1

(4) 1, 1, 0, 1, 1

(5) 1, 1, 0, 0, 0

11.6	다음에 표시된 다항식을 Monic 솟수 다항식 x3 ／ x ／ 1로 나누어 그 나머지를 구하라. 이 때, Modular 산술을 사용하라.

(1) P1(x) Ａ x3 ／ x2 ／ x ／ 1

(2) P2(x) Ａ x4 ／ x3 ／ x ／ 1

(3) P3(x) Ａ x4 ／ x2 ／ x

(4) P4(x) Ａ x3 ／ x2  ／ 1

11.7	다음의 정리를 증명하라.

정의

하나의 다항식에 대한 모든 계수의 합(mod-2)이 0이면 그 다항식은 (x ／ 1)로 나누어 떨어지며, (x ／ 1)을 분해요소(Factor)로 가지는 모든 다항식은 계수의 합(mod-2)이 0이다.

11.10	솟수 다항식 x3 ／ x ／ 1을 이용하여 제 11-8절의 과정을 진행시켜 패리티 검사행렬 M을 유도하고, 다음의 물음에 답하라.

(1) 정보 메시지(1 1 0 1 ---)을 위에서 구한 검사행렬을 이용하여 인코딩하라.

(2) 위 (1)에서 인코딩된 메시지가 채널을 통하여 전송되는 도중에 a3 위치에서 오류가 발생하였다. 이 때, 수신된 메시지를 쓰고, 이에 대한 Syndrome을 구하여 정정하라.

(3) 정보 메시지 (1 0 1 1 ---)에 대하여 위 (1), (2) 과정을 반복하라.

(4) 정보 메시지 (1 1 1 0 ---)에 대하여 위 (1), (2) 과정을 반복하라.

11.11	솟수 다항식 x4 ／ x ／ 1을 이용하여 패리티 검사행렬을 유도하라.

11.12	솟수 다항식 x4 ／ x3 ／ 1을 이용하여 패리티 검사행렬을 유도하라.

11.13	두 개의 오류(Two error)에 대한 Syndrome은 각각의 Syndrome을 더한 것(mod-2)과 같음을 보여라.

11.14	제 11-9절에서 제시한 단일오류 정정코드의 인코더(Encoder)를 실현하는 프로그램을 작성하라.

11.15	Modulus 다항식 x4 ／ x3 ／ 1을 이용한 인코더의 쉬프트 레지스터(Shift register)를 그림으로 나타내어라.

11.16	솟수 다항식 x3 ／ x ／ 1에 의하여 형성된 코딩 시스템에 있어서, 채널로부터 수신된 메시지가 (1 0 0 1 1 1 1)이었다. 여기서 밑줄을 그은 부분은 오류가 발생한 위치를 표시한다.

(1) 수신 메시지를 솟수 다항식으로 나누어 그 나머지를 구하여라.

(2) 위 (1)에서 구한 나머지를 ak이라 두고, 지수 k의 값을 찾아라.

(3) ak 위치에 1을 더하므로써 (mod-2) 오류를 정정하라.

11.17	(11-62)에 주어진 이중오류 정정코드(Double-error-correcting code)의 패리티 검사행렬을 확인하고, 정확한 메시지(000000000000000)이 전송 도중 a5, a8 위치에서 오류를 발생시켰다고 할 때 Syndrome을 구하고, (11-64)∼(11-71)의 계산을 반복하여 오류의 위치를 찾아라.

11.18	7-bit Hamming 코드에 대하여 찾아보기(Table look-up) 방식으로 이루어지는 인코딩과 디코딩을 실시할 경우, 인코더 표(Encoder-table)와 디코더 표(Decoder -table)의 형태와 크기에 관하여 설명하라.