[Computer Science] 해밍코드 예제(Example of Hamming Codes)

Hamming Code Examples

포스트 난이도: HOO_Middle

---

# Hamming Code

해밍 코드(Hamming code)는 전송된 데이터가 오류가 있는지를 검사하는 코드이다. 실제로 컴퓨터 메모리와 통신 시스템에서 에러에 대한 부분을 검사하는데 확인을 하며 이를 통해 손쉽게 코드 수정을 할 수가 있다. 해밍코드는 2의 거듭제곱 비트를 활용하여 메시지를 처리하고 이를 통해서 오류 검사 비트를 사용하여 확인하는 과정을 거치게 된다. 아래는 해밍 코드의 예시이다.

# Hamming Code
(n+r+1) <= 2^r

---

# Hamming Code Examples

# Example_01

Let n be the number of message bits, and let r be the number of parity bits.
r satisfies the inequality (n+r+1) <= 2r. 
And the smallest positive integer r satisfying this inequality is the one that works.
In the example with n=4, since (5+r)<=2r and r=3 is the smallest solution.

b1  b2  b3  b4  b5  b6  b7
3 = 1 + 2
5 = 1 + 4
6 = 2 + 4
7 = 1 + 2 + 4

Parity generators: 
b1 = b3 xor b5 xor b7
b2 = b3 xor b6 xor b7
b4 = b5 xor b6 xor b7

Parity checkers: 
q1=b1 xor b3 xor b5 xor b7, 
q2=b2 xor b3 xor b6 xor b7,
q3=b4 xor b5 xor b6 xor b7.

(q1 q2 q3) = ( 1 0 0) --> b1 flipped
(q1 q2 q3) = ( 0 1 0) --> b2 flipped 
(q1 q2 q3) = ( 1 1 0) --> b3 flipped
(q1 q2 q3) = (0 0 1 ) --> b4 flipped

---