해밍코드(Hamming Code)

에러 검출 코드들은 에러를 검출할 수는 있지만 그 에러를 교정은 불가능하다는 사실이다. 이와같이 불합리한 점을 제거하고 에러의 발견은 물론 교정도 할 수 있는 원리의 코드가 바로 해밍코드(Hamming code)이다.

Hammig 거리와 중 부호에 오류(error)의 검출(detection) 및 정정(correction) 특성을 부여하는 중요한 매개변수로서 거리(distance) 라는 개념을 도입한다.

<정의>

n 차원 벡터(n-tuple vector)인 부호어 의 Hamming 중(weigh) W(c)를 부호벡터 C 내에서 영이 아닌 성분(component)의 개수로 정의한다.

예로서 부호벡터 C = ( 0 1 0 1 1 1 0)의 Hamming 거리는 4이다.

한편, 두 개의 n 차원 벡터 간의 Hamming 거리 d(u,v)는 u와 v의 대응되는 성분 중 서로 다른 성분쌍의 개수를 말한다.

예로서 u = (1 1 1 0 0 1 0) 와 v = (1 0 1 0 0 0 1)간의 Hamming 거리는 3이다. 또 u+v = (0 1 0 0 0 1 1)이므로 Hammig 중 w(u+v)는 3이다. 따라서 u+v 에 대한 Hammng 중의 값은 벡터 u와 v간의 Hamming 거리 d(u,v)와 같음을 알 수 있다.

즉 d(u,v) = w(u+v) (식 1)

임의의 n차원 벡터 u, v, w 사이에 다음과 같은 특성이 있다.

(1) d(u,v) 0 인데 u=v일 경우에 한하여 d(u,v)=0 이다.

(2) d(u,v) = d(v,u)

(3) d(u,v) + d(v,w) d(u,w) (삼각부등식)

선형부호 C에서 서로 다른 두 부호어 간의 Hamming 거리 중 최소치를 부호 C의 최소 Hamming 거리 또는 간략하게 최소거리 (minimum distance) 라 부르며 dmin으로 표시한다.

즉,선형부호 C에서 임의의 두 부호어의 합도 역시 하나의 부호어가 되므로 C 내의 부호벡터 간의 Hamming 거리는 C 에 속하는 두 부호 벡터의 haming 중과 같다.

여기서 을 선형부호 C의 최소중(minimum weigh)이라 부른다.

오류 정정과 능력과 한계식 부호장 n인 부호어의 성분 중, 어느 한 자리에 오류가 발생한 것을 단일 오류(single error)라 하며, 임의의 두 자리에 오류가 발생한 것을 이중오류(double error)라 한다. 이와 마찬가지로 t개의 오류가 발생했을 경우를 t중오류(t-tuple errpr)라 말한다.

부호 C의 최소거리가 3이상, 즉 3 이면 단일 오류를 정정할 수 있으며, 이런 조건을 만족하는 부호를 단일오류정정부호(single-error correcting code)라 한다. 이 부류에 속하는 대표적인 부호로서 최소거리가 3인 (7,4) Hamming 부호가 있다. 일반적으로 부호의 최소거리가 부등식 2t+1을 만족할 때 , 이 부호를 t중오류정정부호(t-error correcting code)라 부른다. 또, 부호의 최소거리가 t+1 의 부등식을 만족하면 부호는 t개 이하의 오류를 검출할 수 있다. 예를 들면, =2 인 부호는 오류정정은 불가능하고, 다만 한 개의 오류를 정정할 수 있고, 두 개의 오류를 검출할 수 있을뿐이다.

= 3 인 부호는 한 개의 오류를 정정할 수 있고, 두 개의 오류를 검출할 수 있다. 다시 말해서 = 3 인 부호는 하나 또는 두 개의 오류까지 검출할 수 있으나 정정에 있어서는 단일부호만이 가능한 것이다.

또 = 5 일때는 두 개의 오류를 정정할 수 있으며 네 개의 오류까지 검출가능하다.

그러면 여기서, 일반적으로 t중오류를 정정할 수 있는 부호의 정보장 k와 부호장 n의 값은 어떻게 정해야 하는지에 대하여 알아보자. 이 문제에 대해서는 여러 가지 한계식이 제안되고 연구되고 있다. 그 중 대표적인 것 하나만을 소개하기로 한다.

선형부호 C가 t중오류정정이 가능하려면 중이 t이하인 두 개의 오류형태가 동일한 승여류(coset)내에 존재해서는 안된다. (n,k) 부호내에는 개의 승여류가 있고 개의 i 중 n차원 부호어(n-tuple code word)가 존재할 수 있으므로 다음의 한계식이 성립된다.

이 부등식을 Hamming 한계식이라 한다.

예를 들어 t = 1 즉, 단일오류정정일 때 이 된다. 따라서 패리티검사비트 수 n-k는 을 만족해야 한다.

Hamming 부호

2개의 원 {0,1}을 계수로 갖는 m차 다항식 p(x)가 영보다 크고 m보다 작은 차수의 어떤 다항식에 의해서도 나누어 떨어지지 않을 때 계약(irreducible)이라 하며, 이 m차의 계약다항식 p(x) 가 보다 큰 차수의 다항식 의 인수가 될 때 p(x)를 원시다항식이라 부르며, (n,k) Hamming 부호의 생성 다항식 G(x)로 표시된다.

부호들은 다음과 같은 매개변수를 갖는다.

m = 3 인 경우 m=7, k=4가 됨을 알 수 있으므로 (7,4)Hamming 부호라 부른다.

위와 같은 (n, k) block code에서 n은 부호어의 길이, k는 정보 심볼, n-k는 redundancy를 의미한다. 부호율 R = k/n가 된다.

정보 심볼

(information)

검사 심볼

(redundancy)

다양한 Hamming부호

부호길이 7비트로 구성되는 해밍(7, 4)부호는 7개 장소의 오류위치를 지시하기 위해서 3비트의 검사비트가 필요하다. 검사비트를 4비트로 하면 오류가 없다는 것을 나타내는 0000을 제외하고 15개의 오류위치를 지시할 수 있기 때문에 해밍(15, 11)부호가 가능하다.

일반적으로 부가하는 검사비트를 n이라고 하면 부호길이는 2n－1 (비트)가 되고 정보비트 길이는(2n－1)－n (비트)로 되는 것을 쉽게 이해할 수 있다.