7.11  오류-수정부호

인공위성과 컴퓨터통신을  고찰해 보면   이러한 디지털 통신에서 전문(message) 또는 단어(word)들은
이진 n짝(tuple), 즉 n짝은 0과 1, 또는 비트(bit)만으로 되어 있다.
n 비트 단어는 길이 n인 2진 문자열(binary string of  length n.)이라 한다.

   암호(Codes) 전문(message)을  부호화(encoding)한다는 것은   길이 n의 단어 W를
parity check bits라 부르는  m개의 비트를 W에 첨가하여 길이 n+m의 다른 단어 C로
변환하는 과정을 의미한다.
부호 화한 단어를  암호어(code word)라 한다. 수신된  전문을 복호(decoding)한다는 것은
복호한 전문 또는  전송 중 생긴 오류가 갖고 있는  지시를 제공하는 다른  과정을 의미한다.
부호화와 복호 조직을 암호라 한다.

 가장 간단한 암호중의 하나는 홀짝 조사 부호(parity check code)이다.
이 암호는 단어에 있는 수가
  짝수: 단어에 0을 더한다.     (1)
  홀수: 단어에 1을 더한다.

 parity란 말은 단어에 있는 1의  수가 짝수인가 홀수인가를 말한다.
(1)에서 주어진 부호화 규칙은 암호어의 parity가 항상 짝수가 되게 만든다.
                        /(잡음)
전문--(부호화)->암호어--(전송)->/수신된 전문--(복호)->복호된 전문 또는 오류 표시
message- encoding-code   word- transmission-received message- decoding-decoded
message or error indication

 디지털 통신에서 전송되는 것은 부호 화된 언어  C이다.  그러나 전송의 통로에서 몇 종류의 간섭과 잡음
때문에 C의 한 개 이상의 비트가 바뀔 수 있다.
따라서 전송한 전문이 항상 수신된 전문이라고는 할 수 없다. 위의 도형을 보면 알 수 있다.
 Parity check code는 복호자가 하나 하나의  오류를 검출하게 할 수 있다.
R을 수신한 전문이라  하자. 하나의 오류란 하나의 비트가 0이 1로 변했던가 또는 1이 0으로 변했다는 뜻이다.
어느 경우에서나 그 단어 R은 홀수이다.
 컴퓨터와의 내부 통신과 같은 디지털 통신의 몇 가지 형태에  대하여 parity check  code는 적절한 것이나
주요한 하나의  함정이 있다. 즉 오류가 일어나면 어느 비트가 틀렸는지를 모르므로 수정하는 방법을 모른다는 것이다.
더욱이, 중복된 오류가  전송 중에 나타날 수 있다. 말하자면, 전송  중에 두 개의 1이  0으로 바뀌었으면,
수신한  전문은 아직  짝수의 parity를  갖고 복호는  마지막 비트를 빼버림으로써 오류가 일어난다.
이  경우에 복호된 전문에 있는 비트 중 적어도 하나의 비트가 오류이다.

해밍 코드(Hamming   Codes):
parity   check 코드는 오류 검출(error-detecting) 부호의 한 예이나,
오류 정정 코드는 아니다. 이 논의의 나머지 부분에 대하여는,  Hamming(7,4)code라 부르는
오류 검출-정정 코드를  생각하기로 하자. 1950년대  Bell연구소에서 수학자 Richard W. Hamming이  창안한,
널리 쓰이는 부호(코드)들의 집합 중 하나인,  이 코드는 수신된  전문에 있는 단  하나의 오류의 존재를 검출할 수 있고
어느 비트가 수정되어져야  하는지를 말해 줄 수 있는 부호화-복호  조직이다. (7,4)코드에서 부호화 과정은
4비트어 W = [w1 w2 w3 w4]를 7비트 코드어

   C = [c1 c2 c3 w2 w3 w4]

로 변환하는 것으로 되어 있다. 여기서, c1,  c2c 과 c3은 parity check 비트를 표시한다.
(4비트보다 긴  단어는 길이 4의 단어들의 열로 쪼갤 수 있다.)

부호화(Encoding): 해밍 (7,4) 코드에서  parity check비트 c1,  c2와 c3는
  정보 비트 w1, w2, w3과 w4로 다음과 같이 정의된다.

  c1 = w1 + w2 + w4
  c2 = w1 + w3 + w4         (2)
  c3 = w2 + w3 + w4

여기서, 셈은 법 2로 행한다. 행렬을 이용하여, (2)는 다음과  같은 곱으로 쓰여질 수 있다.

  [c1  ; c2 ; c3]=[1 1 0 1 ; 1 0 1 1 ; 0 1 1 1][w1 ; w2 ; w3 ;w4]

 전문을 복호하는  방법을 자세히  살펴보기 전에  특수한 행렬을 소개할 필요가 있다.
먼저, 2진법으로 셈을 하면 음의 정수는  존재하지 않는다는 사실,
즉, 1의  덧셈 역원은 1이자 -1은  아니라는 사실을 관찰할 수 있다.
이것을 염두에 두면, 연립방정식 (2)를 다음과 같은 동치인 꼴로 쓸 수 있다.

  c3 + w2 + w3 + w4 = 0
  c2 + w1 + w3 + w4 = 0         (4)
  c1 + w1 + w2 + w4 = 0

 이것들은 parity check 방정식이라  불린다. 이것은 각 c1  가 원래 단어에 있는 숫자  중의
3개에 대한 parity  check라는 뜻이다. 예를 들어, 세 수 w2, w3와 w4에 있는 수가 홀수이면,
앞에서 논의한 parity check 코드에서와  같이, c1 = 1  등 을 취할  것이다.
행렬 곱으로 (4)는 다음과 같이 쓸 수 있다.

[0 0 0 1 1 1 1 ; 0  1 1 0 0 1 1 ; 1  0 1 0 1 0 1 ] *
  [c1 ;  c2 ; w1 ; c3 ; w2 ; w3 ; w4] = [0 ; 0 ; 0]         (5)

(5)에 있는 3*7 행렬
H = [0 0 0 1 1 1 1 ; 0 1 1 0 0 1 1 ; 1 0 1 0 1 0 1 ]
을 parity check 행렬이라 한다. (5)에서 코드어
C = [ c1 c2 w1 c3 w2 w3 w4 ]의 2진수는 행렬방정식

 HC^t  =  0           (6)

임을 보았다. H를 더 가까이서 조사하면 놀라운 사실, 즉 H의 열들은 왼쪽에서 오른쪽으로,
수 1부터  7까지의 수를 2진수로 표시하고 있음이 나타난다. 예를 들어, 열

 [1 ; 1 ; 0]

을 1 1 0 으로 나타내면, 이것은  수 6의 2진수 표현임을 알게 된다.
R를 수신된 전문을 표시하는 1*7행렬이라 하자. H는 3*7행렬이  T고 R 는 7*1행렬이므로

S= HR^t      (7)

은 3*1 행렬인데 이것을 syndrome이라 한다.

복호(Decoding): 수신된 전문 R 의 syndrome이

S = HR^t   = 0

이라면, (6)의 결과에 의하여  R 은 코드 어라는  결론을 얻고, 전송이 올바르고 R이
본래 부호 화한  전문 C와  같다고 추정된다.
전문의 복호는 간단히 R 에 있는 3개의 check 비트를 빼버림으로써 완성된다.
앞에서 언급한 바와 같이, 해밍  (7,4) 코드는 전문 R  에 있는 단일 오류를 검출하고 정정하게 해준다.
지금, C를 코드 어라 하고 E = [ e1 e2 e3 e4 e5 e6 e7 ]를 전송 중 C에 추가한 단일 오류 잡음
어라 하자. E의 원소들은 다음과 같이 정의된다.

                  1. (잡음이 i번째 비트를 바꿀 때)
        e i   =  {
                  0. (잡음이 i번째 비트를 바꾸지 않을 때)
 

수신된 전문은 그 때 R = C + E이다. 성질 R^t  = C^t  + E^t  과
분해법칙으로부터, R의 syndrome은 E의 syndrome

HR^t  = H(C^t  + E^t  ) = HC^t  + HE^t  = 0 + HE^t  = HE^t

과 같다.
행렬덧셈의 정의에서 E의 syndrome

HE^t   = [e4 + e5 + e6 + e7 ; e2 + e3 + e6 + e7 ; e1 + e3 + e5 + e7]
 

은 H의 열 벡터와 오류 발생 기능  비트를 나타내는 계수를 갖는 기호와의 합

HE^t =e1[0;0;1]+e2[0;1;0]+e3[0;1;1]+e4[1;0;0]+e5[1;0;1]+e6[1;1;0]+e7[1;1;1]       (8)

으로 쓸 수 있다.
 이제, 2진수로 된  원소를 갖는 3*1  행 벡터들의 집합을  생각하자.
세 원소들의 각각을 택하는 방법은 2가지뿐이므로 이런 벡터들은  2^3  =  8개가  있다.
7개의  0이  아닌  벡터는   H의 열들이거나 (8)에 나열한 열벡터들이다.
수신된 전문 R의 syndrome S은 2진수로 된 원소를 갖는 3*1 열벡터  이다.
따라서, S =/= 0 이면 S는 H의 열벡터 중 하나  이어야 한다.
R이 단일 오류를  가지면, S =/= 0 이고, E의 원소들은 1의 한 원소를 제외하고는 모두 0이므로
(8)로부터 syndrome 자신이 어느 비트가 오류인지를 가리킨다는 것을 알게 된다.
실제로는, (8)을  쓸 필요가 없이 바로 수신된 전문 R의 syndrome  S을 계산한다.
S는 H의  한 열이고 결과적으로 오류인 그 비트의 2진수이다.
암호작성과 부호 이론의 이 간략한 기술에서는 이 매혹적인  주제(8)에 나열한 열 벡터들이다.
수신된 전문 R의 syndrome S은 2진수로 된 원소를 갖는 3*1 열 벡터이다.