해밍 코드, 해밍 부호(Hamming Code)

정의

해밍 부호(Hamming code)는 이진 선형 블록 오류 정정 부호의 일종이다.

특징

해밍 코드는 1950년에 미국의 Bell 연구소의 Richard Hamming에 의해 고안되었으며,

데이터 전송 또는 메모리 액세스 등의 경우 최대 2 비트 오류를 감지하거나 1 비트 오류를 수정할 수 있다.

 

신드롬(syndrome): 오류 검사에 사용되는 유일한 패턴.

해밍 조건

해밍 부호는 어떤 길이의 데이터어(data word)에도 사용할 수 있다.

해밍 코드는 n개의 데이터어에 k개 패리티 비트를 더하여 n + k 비트의 새로운 코드어(code word)를 생성한다.

신드롬 값 C는 k개의 비트로 이루어지고 0에서 2k – 1 사이의 2k 개의 범위를 가진다.

이 값 중 하나(보통 0)는 오류가 없음을 나타내기 위해 사용되고, 나머지 2k – 1값은 n + k 비트의 한 곳에서 오류가 있음을 나타낸다.


2k – 1의 각각은 오류가 있는 비트를 유일하게 나타내는데 사용되므로 k의 범위는 n + k 보다 크거나 같아야 한다.

2k  1 >= n + k


위 식에서

2k – k – 1 >= n를 얻는다.


이 관계는 k 개의 체크 비트와 함께 사용될 수 있는 데이터 비트 수를 계산하기 위한 공식을 제공한다.

k가 3이면 데이터 비트의 수는 4 (23 – 1 – 3 = 4)

k가 4이면 데이터 비트의 수는 11 (24 – 1 – 4 = 11). 

데이터 비트는 11보다 작고 5보다는 커야 한다. 데이터에는 적어도 5 비트가 있어야 하며, 그렇지 않으면 3 개의 체크 비트만 필요하다.

패리티 생성 및 검사를 위한 비트의 그룹화는 0에서 2k  1까지의 이진수의 리스트로부터 결정될 수 있다.


해밍 코드 생성 규칙 (en.wikipedia.org에서 인용)

패리티 비트

전체 비트

데이터 비트의

범위

Name

효율

231Hamming(3,1)
(Triple repetition code)
1/3 ≈ 0.333
372 ~ 4Hamming(7,4)4/7 ≈ 0.571
4155 ~ 11Hamming(15,11)11/15 ≈ 0.733
53112 ~ 26Hamming(31,26)26/31 ≈ 0.839
66327 ~ 57Hamming(63,57)57/63 ≈ 0.905
712758 ~ 120Hamming(127,120)120/127 ≈ 0.945
8255121 ~ 247Hamming(255,247)247/255 ≈ 0.969

m

Hamming

밍 부호의 생성

최하위 비트(LSB)는 1, 3, 5, 7 등의 2 진수에 있는 1이다.

다음 하위 비트는 2, 3, 6, 7 등의 2 진수에 있는 1이다.


해밍 부호의 패리티 비트 생성 및 확인에 사용된 각 비트 그룹은 1, 2, 4, 8, 16 등과 같이 2의 거듭 제곱인 숫자로 시작한다.

이들 번호는 패리티 비트들의 위치 번호이다.


생성 규칙은 아래 표와 같다. (en.wikipedia.org에서 인용)

Bit position1234567891011121314151617181920
Encoded data bitsp1p2d1p4d2d3d4p8d5d6d7d8d9d10d11p16d12d13d14d15
Parity
bit
coverage
p1NoNoNoNoNoNoNoNoNoNo
p2NoNoNoNoNoNoNoNoNoNo
p4NoNoNoNoNoNoNoNoNo
p8NoNoNoNoNoNoNoNo
p16NoNoNoNoNo


예제)

비트 위치

1

2

3

4

5

6

7

8

9

10

11

12

 

P1

P2

1

P4

1

0

0

P8

0

1

0

0

네 개의 패리티 비트 P1 P2 P4 P8의 위치는 1, 2, 4, 8이며 데이터어 8 비트는 나머지 위치에 있다.


각 패리티 비트는 다음과 같이 계산된다.

P1 = XOR 비트 그룹 (3, 5, 7, 9, 11) = 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 = 0

P2 = XOR 비트 그룹 (3, 6, 7, 10, 11) = 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 0

P4 = XOR 비트 그룹 (5, 6, 7, 12) = 1 ⊕ 0 ⊕ 0 ⊕ 0 = 1

P8 = XOR 비트 그룹 (9, 10, 11, 12) = 0 ⊕ 1 ⊕ 0 ⊕ 0 = 1


8비트 데이터어와 4 비트의 패리티 비트로 12비트 합성어가 생성된다.

비트 위치

1

2

3

4

5

6

7

8

9

10

11

12

 

0

0

1

1

1

0

0

1

0

1

0

0


해밍 부호의 검증

12 비트를 메모리에서 읽어 오류를 검증할 때, 패리티는 패리티 비트를 포함하는 동일한 비트 조합을 통해 검사된다.


예제)

네 개의 체크 비트는 다음과 같이 계산된다.


C1 = XOR 비트 그룹 (1, 3, 5, 7, 9, 11) = 1  1  0  0  0 = 0

C2 = XOR 비트 그룹 (2, 3, 6, 7, 10, 11) = 1  0  0  0  0 = 0

C4 = XOR 비트 그룹 (4, 5, 6, 7, 12) = 1  0  0  0 = 1

C8 = XOR 비트 그룹 (8, 9, 10, 11, 12) = 0  1  0  0 = 1


0 은 짝수 패리티이며 1은 홀수 패리티이다.

비트들은 짝수 패리티로 저장되므로 결과 C = C8C4C2C1 = 0000는 오류가 발생하지 않았음을 나타낸다.

그러나, c가 0이 아닌 경우, 체크 비트에 의해 형성된 4 비트의 이진수는 에러 비트의 위치를 제공한다.



비트 위치:         1  2  3  4  5  6  7  8  9  10  11  12


                     0  0  1  1  1  0  0  1  0  1   0   0       오류 없음


                     1  0  1  1  1  0  0  1  0  1   0   0       비트 1에 오류


                     0  0  1  1  0  0  0  1  0  1   0   0       비트 5에 오류


해당 비트의 XOR로 평가하면 네 개의 체크 비트는 아래와 같이 결정된다.


                                C8        C4        C2        C1


오류가 없는 첫 경우       0         0         0         0


비트 1에 오류가 있음     0         0         0         1


비트 5에 오류가 있음     0         1         0         1


따라서 오류가 없는 경우의 C = 0000

비트 1에 오류가 있는 경우 C = 0001

비트 5에 오류가 있는 경우 C = 0101


C의 이진 값이 0000이 아니면 오류가 있는 비트의 위치를 준다.

확장 해밍 부호

Single-Error Correction, Double-Error Detection (SECDED)


해밍 코드는 단 하나의 오류를 검출하여 정정할 수 있다. 다중 오류는 검출되지 않는다.

코드어에 다른 패리티 비트를 하나 추가하여 해밍 부호는 하나의 오류를 검출하고 이중 오류를 검출할 수 있다.


예) 추가적인 패리티 비트를 포함시키면, 이전 12비트의 코드어는 0011 1001 0100 P13가 된다.

P13은 다른 12비트와 XOR로 계산되어 0011 1001 0100 1 (짝수 패리티)를 생성한다.

13 비트들이 메모리에서 읽혀지면 검사 비트들과 전체 13 비트들에 대한 패리티 P도 계산된다.

계산 결과 발생할 수 있는 네 가지 경우는 아래 표와 같다.


C

P

의미

C = 0

P = 0

오류가 발생하지 않음

C 0

P = 1

단일 오류가 발생하였고 정정될 수 있다.

C 0

P = 0

이중 오류가 발생하였고 검출될 수 있지만 정정될 수 없다.

C = 0

P = 1

P13비트에서 오류가 발생하였다.

  1. 2018.04.26 16:17

    비밀댓글입니다

  2. 2018.05.22 17:56

    비밀댓글입니다

+ Recent posts

티스토리 툴바