해밍 코드(Hamming Code)의 오류 검사

해밍 코드(Hamming Code)

 

• 해밍 코드(Hamming Code)란?

오류 검출과 정정을 할 수 있는 코드이다.

데이터 비트 외에 추가적인 많은 비트가 필요하므로 많은 양의 데이터 전송에 유리하다.

 

• 추가되는 패리티 비트의 수

2^p >= d+p+1

(p: 패리티 비트의 수, d: 데이터 비트의 수)

 

사용가능한 데이터 비트 수

p=3 d=2~4

p=4 d=5~11

p=5 d=12~26

 

1비트 오류 검출 및 정정 기능하다.

2비트의 오류 검출은 가능하지만 정정은 불가능하다.

 

• 패리티 비트의 위치

패리티 비트는 2^n (n=0,1,2...)의 위치에 배치한다.

데이터는 그 사이의 빈 자리에 배치한다.

 

• 패리티 비트의 위치 예시

데이터 비트 수=8인 경우, 추가되는 패리티 비트의 수는?

2^p >= 8+p+1

위 식을 만족하는 p의 최소 값 (p=4)

 

해밍코드 전체 비트의 수는?

d+p (8+4=12)

 

패리티 비트와 데이터 비트의 위치는 다음과 같다.

 

• 패리티 비트의 영역

P1의 영역 D3+D5+D7+D9+D11

P2의 영역 D3+D6+D7+D10+D11

P4의 영역 D5+D6+D7+D12

P8의 영역 D9+D10+D11+D12

 

8비트 데이터의 해밍 코드 생성 예제

패리티비트 구하기 (짝수=0, 홀수=1)

P1= D3+D5+D7+D9+D11= 0+1+1+1+1=0

P2= D3+D6+D7+D10+D11= 0+0+1+0+1=0

P4= D5+D6+D7+D12= 1+0+1+1=1

P8= D9+D10+D11+D12= 1+0+1+1=1

 

심드롬(C) 값 구하는 방법

패리티 비트를 포함하여 검사한다.

C1= P1+D3+D5+D7+D9+D11= 0+0+1+1+1+1=0

C2= P2+D3+D6+D7+D10+D11= 0+0+0+1+0+1=0

C4= P4+D5+D6+D7+D12= 1+1+0+1+1=0

C8= P8+D9+D10+D11+D12= 1+1+0+1+1=0

C8C4C2C1=0 이므로 신드롬의 값은 0이다.

 

• 신드롬(Syndrome)

검사된 C8C4C2C1dml 2진 값 0~15 사이에서 만들어지는 오류의 값이다.

신드롬=0이면 오류가 없다.

만약 6이면, 6번째 비트인 D6에서 오류가 발생한 것이다.

 

오류가 있는 경우 예제

C1= 0+0+1+1+1+0=1

C2= 0+0+0+1+0+0=1

C4= 1+1+0+1+1=0

C8= 1+1+0+0+1=1

C8C4C2C1=1011

 

신드롬의 값인 2진수 1011을 10진수로 바꿔준다.

1101(2)→11(10)

11비트인 D11에 오류가 발생했다.

0을 반전하여 데이터를 정정해준다.

오류를 수정한 데이터는 000110111011이 된다.

 

 

 

정리

1.패리티 비트

• 데이터 전송에서 발생하는 오류를 검출하기 위해 가장 간단하게 자주 사용하는 방식으로 패리티 비트라는 추가 비트를 사용한다.

• 홀수 및 짝수의 두 가지 패리티 비트 생성 방식이 있다.

• 패리티 비트 방식은 홀수 개의 오류가 발생하면 검출이 가능하다.

2.해밍코드

• 오류 검출 및 정정을 할 수 있는 코드로 많은 양의 데이터 전송에도 사용할 수 있다.

• 데이터의 비트 수에 따라 추가적인 패리티 비트의 수가 증가한다.

• 신드롬 값으로부터 오류가 발생한 비트를 알 수 있고 이것을 반전하여 오류를 정정한다.