해밍 코드 생성 및 에러 검출

해밍 코드 - 생성 방법

패리티 코드를 응용하여 한 비트의 에러를 찾고 정정할 수 있다.

원본 데이터에 추가적인 비트가 붙으므로 많은 양의 데이터 전달이 필요함.

2개 이상의 비트 에러가 발생하면 정정이 불가능하다.

 

아래의 식을 만족한다

p=4일때 d는 5이상 11이하이다.

즉, 원본 데이터의 비트 수가 5개 이상 11이하 일때 패리티 비트를 4개 갖는 것이다.

p=3일때 d는 2이상 4이하이다.

즉, 원본 데이터의 비트 수가 2개 이상 4개 이하일 때 패리티 비트를 3개 갖는다.

 

패리티 비트의 위치는 1, 2, 4, 8, 16, 32, ...의 위치에 들어가며 기호 P1, P2, P4, ....로 나타낸다.

원본 데이트는 나머지 위치에 순서대로 들어가며 D3, D5, D6... 로 나타낸다.

원래의 데이터 비트에 사이사이에 패리티 비트를 적절한 위치로 삽입시켜주면 해밍코드의 순서이다.

 

예를 들어,

원본 데이터의 비트 수가 8개일 때 패리티 비트의 수는 4개이므로

원본 데이터의 비트 사이사이에 패리티 비트를 적절히 위치시켜주면 전체적인 순서를 잡을 수 있다.

이렇게 1, 2, 4, 8, ... 번째에 패리티 비트를 맞춰주고 남은 자리에는 원본 데이터를 순서대로 채워주면 된다.

( 4번째 비트 위치에 P4로 표기하여야 한다. D4는 오타. 아래 설명부터 수정됨 )

 

 

이제 본격적으로 해밍 코드를 생성해보자.(위의 예를 가지고)

P1은 P1을 포함하여 시작해서 1칸을 취하고 1칸을 띄고 1칸을 취하고 이렇게 끝까지 반복한다.

P2는 P2을 포함하여 시작해서 2칸을 취하고 2칸을 띄고 2칸을 취하고 이렇게 반복.

P4도 마찬가지로 P4를 포함하여 4칸 취하고 4칸 띄고 반복.

취할 때 데이터가 없으면 있는 데까지만 취한다.

 

아래에 취하는 영역을 표시해봤다.

 

이제 P1, P2, P4, P8을 구할 것인데

자신의 영역의 1의 개수가 짝수가 되도록 P1, P2, P4, P8을 만든다.

여기에 ⊙은XOR을 나타낸다. 1이 홀수개 이면 1을 생성한다.

즉, 짝수 패리티가 되도록 만들면 되는 것이다.

 

P1, P2, P4, P8을 구해보자.

구하기 위해 이제 완본 데이터를 00101110이라고 주어졌다고 생각한다.

 

이제 해밍 코드가 생성되었다.

 

해밍 코드 - 에러 검출 및 정정 방법

생성과 같은 방법으로 새로 P1, P2, P4, P8,... 을 구한다.

여기서 다른점은 각각을 구할때 자신도 포함하여 짝수 패리티를 검사하는것이다.

 

아래와 같이 P1, P2, P4 P8을 구한다.

 

이제 구한 패리티를

P8 P4 P2 P1로 역순으로 정렬한다.

이때 모든 패리티가 0이면 에러가 없는것이고 1이 있다면 에러가 발생한 것이다.

이때 에러의 위치는 아까 역순으로 정렬한 패리티를 10진수로 바꾸면 된다.

 

위의 예에서는 0101이 되므로 5이다.

즉, 비트 위치 5에서 에러가 난것이므로

1이면 0으로 0이면 1로 바꿔준다.