공부하는 퓨퓨

해밍 코드(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.해밍코드

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

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

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

저번 포스팅에서 해밍코드를 통해 패리티 비트 수를 결정하고 패리티 비트를 배치하는 위치에 대해 알아보았다.

이번 포스팅에서는 각 패리티 비트의 체크 비트들을 구하고 오류가 발생한 비트를 찾아보자.

데이터 비트가 4비트라고 했을 때 p=3으로 3개의 패리티 비트가 필요하고 배치 위치는 2^n 자리에 들어가기 때문에 정리하면 아래 표와 같다.

각 패리티 비트의 체크 비트 영역을 구하는 방법은 다음과 같다.

먼저 자기 비트부터 시작해 2^n 만큼 읽는다. 그다음 2^n 만큼 넘어가기를 반복한다.

P1의 시작비트는 1이므로 1, 3, 5, 7,..이 되고 P2의 시작비트는 2이므로 2, 3, 5, 6,...이 된다. 나머지 비트들도 동일하게 적용한다. 

알기 쉽게 표로 정리하면 다음과 같다. 

다음 포스팅에서는 오류가 발생한 비트 검출과 수정에 대해 알아보도록 하자.

해밍코드는 에러를 검출 및 교정한다.

데이터비트와 에러 검출과 수정을 위한 패리티비트로 구성되어 있다.

전송되는 데이터의 비트 수에 따라 패리티 비트의 수가 결정된다. 

패리티 비트의 수를 결정하는 공식은 다음과 같다.

2^p - 1 >= n + p (n은 데이터 비트의 수이고 p는 패리티 비트의 수이다.)

위의 식을 만족하는 p의 최소값이 패리티 비트의 수가 된다.

패리티 비트를 배치해 보자.

패리티 비트의 위치는 우측 비트부터 시작하여 2^n의 자리에 배치된다.(이때 n은 0부터 시작한다.) 

P8 D7 D6 D5 P4 D3 P2 P1 (D는 정보 비트를 나타내고 P는 패리티 비트를 나타낸다.)

예를 들어 p가 3이면 우측 비트부터 1번째, 2번째 그리고 4번째에 패리티 비트가 배치된다.

(2^0=1, 2^1=2, 2^2=4가 되기 때문이다.)

D7 D6 D5 P4 D3 P2 P1

p가 4면 1, 2, 4, 8번째에 패리티 비트가 배치된다.

(2^0=1, 2^1=2, 2^2=4, 2^3=8이 되기 때문이다.)

P8 D7 D6 D5 P4 D3 P2 P1

그렇다면 데이터비트가 4비트일 때 패리티 비트의 수와 배치 위치는?

데이터 비트가 4비트일 때 패리티 비트의 값은 3이 되고 배치위치는 2^n자리에 들어가기 때문에 1, 2, 4자리에 들어간다. (P1, P2, P4)

각 자리의 패리티 비트를 결정하기 위해서는 다음과 같은 규칙을 사용한다.

P1의 값 1, 3, 5, 7 비트를 검사 후 짝수 패리티가 되도록 한다.

P2의 값 2, 3, 6, 7 비트를 검사 후 짝수 패리티가 되도록 한다.

P4의 값 4, 5, 6, 7 비트를 검사 후 짝수 패리티가 되도록 한다.

오늘은 패리티 비트의 배치 방법에 대해서 알아보았다.

다음 포스팅에서 각 패리티 비트의 체크 비트들을 구해 보도록 하자.