해밍코드 (Hamming Code)

1) 해밍 코드란?

해밍코드는 (1) 코드 생성 (2) 오류 검출 (3) 오류 수정 순으로 진행된다.

​ [송신자] ------데이터 전송-----> [수신자]

1. 데이터 비트에 몇 개의 패리티 비트가 추가된 코드
   1. 패리티 비트
      1. 정보의 전달 과정에서 오류가 생겼는지를 검사하기 위해 추가한 비트
2. 기존의 패리티 비트들은 수신된 데이터 열에 에러의 유무 정도만 판단 가능했음.
   1. 해밍 코드를 이용하면 에러 비트의 위치까지 알 수 있고, 에러 교정도 가능함
3. (예시) 실시간으로 데이터가 전송되어야 하는 경우, 데이터 전송과 동시에 에러 교정이 수행되어야 함.
   1. 이러한 신뢰도 특징을 기반으로, 대부분의 마이크로칩 디바이스에서 사용되고 있음.

2) 얼마나 많은 개수의 체크 비트가 필요한가?

2^p >= d + p + 1

1. p = 패리티 비트 개수
2. d = 데이터 비트 개수
3. (예시) 데이터 비트가 1byte (=8bit), 최소 패리티 비트(p)는 4가 되어야 함.

3) 패리티 비트들과 데이터 비트들은 어느 위치에 삽입되는가?\

1. 송신자가 수신자에게 88(10110000)의 값을 전송한다고 가정함.

index	1	2	3	4	5	6	7	8	9	10	11	12
Data	p1	p2	0	p4	0	0	0	p8	1	1	0	1

1. 데이터 비트 수(8) + 패리티 비트(4) = 총 12bit가 필요함
   1. 총 데이터 비트 수는 12비트일 때, 각각 패리티 비트의 위치는 2^n (n=0, 1, 2... ) 위치로 순서대로 삽입이 됨.
   2. -> 1,2,4,8번째 위치에 삽입이 됨
2. 각각의 데이터 비트들은 나머지 부분에 할당하게 됨.

4) 패리티 비트는 어떻게 결정되는가?

1. 우선, p1을 생성하는데 관여하는 영역은 자기(p1)에서부터 한칸씩 떨어진 위치임
   1. 이때, ''짝수 패리티' 개념이 필요함
      1. 짝수 패리티란?
         1. 전체 비트에서 1의 개수가 짝수가 되도록 패리티 비트를 정하는 것임
         2. 1의 개수가 홀수이면 패리티 비트를 1, 1의 개수가 짝수이면 패리티 비트를 0으로 정하는 것임
2. 1-1. index 1, 3, 5, 7, 9, 11 .... 홀수 부분임
3. 따라서, (1-1)들은 3은 '0', 5는 '0', 7은 '0', 9는 '0', 1도 '0'이기 때문에 1의 개수는 0개(짝수)이므로 p1은 0으로 결정이 됨

index	1	2	3	4	5	6	7	8	9	10	11	12
Data	p1	p2	0	p4	0	0	0	p8	1	1	0	1

index	1	2	3	4	5	6	7	8	9	10	11	12
Data	1	p2	0	p4	0	0	0	p8	1	1	0	1

2. p2을 생성하는데 관여하는 영역은 자기(p2) 자리와 그 다음칸, 또 두칸 떨어져서 두칸... 또 두칸 떨어져서 두칸... 도 두칸 떨어져서 두칸이 p2의 생성에 관여함
   1. index (2,3) , (6,7), (10, 11) , (14,15) ....
   2. p1을 생성했던 것처럼 짝수 패리티를 적용해서 p2의 생성에 관여하는 영역들의 1의 개수를 세어 줌
      1. 3은 '0', 6은 '0', 7은 '0', 10은 '1', 11은 '0'이므로 총 1의 개수는 1개(홀수)이므로 p2는 1으로 결정이 됨

   index	1	2	3	4	5	6	7	8	9	10	11	12
   Data	1	p2	0	p4	0	0	0	p8	1	1	0	1

   index	1	2	3	4	5	6	7	8	9	10	11	12
   Data	1	1	0	p4	0	0	0	p8	1	1	0	1

3. p4을 생성하는 데 관여하는 영역은 자기(p4) 자리와 그 다음 칸, 또 네칸 떨어져서 네칸 ... 두 네칸 떨어져서 네칸... 또 네칸 떨어져서 네칸이 p4의 생성에 관여함
   1. index (4,5,6,7), (12,13,14,15) ....
   2. p1, p2을 생성했던 것처럼 짝수 패리티를 적용해서 p4의 생성에 관여하는 영역들의 1의 개수를 세어 줌
      1. 5는 '0', 6은 '0', 7은 '0'이므로 4는 1의 개수가 즉 0개(짝수)이므로 4는 0으로 결정됨

      index	1	2	3	4	5	6	7	8	9	10	11	12
      Data	1	1	0	p4	0	0	0	p8	1	1	0	1

      index	1	2	3	4	5	6	7	8	9	10	11	12
      Data	1	1	0	0	0	0	0	p8	1	1	0	1

4. 나머지 p8의 규칙도 위와 같이 자기(p4) 자리에서 여덟 칸을 포함하고, 또 여덟칸 떨어져서... 이런 식의 원리로 p8의 생성에 관여하는 것의 1의 개수를 적용해 패리티 비트를 구함
   • 최종 해밍 코드

5. index	1	2	3	4	5	6	7	8	9	10	11	12
   Data	1	1	0	0	0	0	0	1	1	1	0	1

이제 해밍 코드를 송신하면 된다.

5. 어떻게 오류를 검출하는가?

• 오류를 검출하기 위해서는 패리티 Check 비트가 필요함
• 10110000에서 10110001의 값으로 바꿨다고 가정함
• 체크 비트를 생성하는 것은 패리티 비트를 생성하는 것과 원리가 같음
• 이번에는 패리티 비트를 포함하여서 계산함
• C1 = index 1 + index 3 + index 5 + index 7 + index 9 + index 11 = 1 + 0 + 0 + 0 + 0 + 1 + 0 = 2 = 0
• C2 = (index 2 + index 3) + (index 6 + index 7) + (index 10 + index 11) = 1 + 0 + 1 = 2 = 0
• C4 = (index 4 + index 5 + index 6 + index 7 )+ (index 12) = 0 + 1 = 1 = 1
• C8 = (index 8 + index 9 + index 10 + index 11) = 3 = 1

  • index	1	2	3	4	5	6	7	8	9	10	11	12
    Data	1	1	0	0	0	0	0	1	1	1	0	1
    Check	0	0		1				1

    • 체크 비트를 역순으로 정렬하고, 10진수로 바꿔준다.

  C_8C_4C_2C1 = 1100{_{12}}

 

- 1100 -> 12

- 12번째 비트에서 오류가 발생했다는 것을 확인

- 기억하시죠? 우리는 10110000에서 10110001의 값으로 바꿨다고 가정했었음.

- 다시 10110000으로 교정해 줌.

 

 

 

 

또한, 일일히 1의 개수를 구하지 않아도 XOR 연산을 통해 패리티 비트를 구할 수 있음.

XOR 연산 : 입력 값이 같으면 0을 반환, 다르면 1을 반환

위에서와 같이 패리티 비트의 생성을 관여하는 영역들의 데이터의 값이 1인 것들로 인해 ->

XOR 연산하면 간단하게 패리티 비트 생성 및 오류 검출, 교정을 할 수 있음