컴퓨터구조

[컴퓨터 구조] Hamming Code

hccode0419 2025. 1. 4. 23:35

1. Hamming Code

data를 송신할 때 1001 0101 이런 데이터를 보냈는데 받을 때 에러가 생겨 1101 0101 으로 data를 받았다고 하자.

 

이런 일은 당연하게도 일어나면 안 되는 것이다. 

 

data bit가 하나라도 의도와 달라지면 우리가 원하는 data를 얻지 못한다. 

 

그래서 data를 보낼 때 몇개의 bit를 추가로 보내어 오류를 검출하고 정정까지 할 수 있도록 하는 것이 Hamming code다.

 

2. Hamming Code 작동 방식

hamming code는 송신한 data와 4개의 parity bit를 통해 문제를 해결할 수 있다. 

1) 검출 방법

검출 방법은 간단하다. 위의 표대로 방법만 따라가면 된다.

 

① parity bit 검출

P1을 구하기 위해서는 위 표에서 X표시된 bit만 비교하면 된다.

P1은 1의 개수가 짝수가 되도록 설정하면 된다. 

 

예시를 들면 p1 d1 d2 d4 d5 d7을 비교했을 때 각각의 bit가 p1 0 0 0 0 1 이라면 p1은 1이 되어야 한다.

 

마찬가지로 p2, p4, p8을 구할 수 있다.

 

② 오류 검출

parity bit를 검출했으니 만약 data 송신 중 오류 검출을 해보자.

 

오류 검출도 똑같은 방법으로 진행한다. 

 

수신된 data에서 p1, p2, p4, p8에 해당하는 bit를 구하면서 1의 개수가 홀수인 부분을 찾는다. 

 

parity bit 검출 단계에서 1의 개수를 짝수가 되게 설정했기 때문에 1의 개수가 홀수라는 것은 어떤 bit에서 오류가 나타난 것이다.

 

만약 p1, p4에서 1의 개수가 홀수면 

p1 + p4 = 5, 즉 5번째 bit에서 오류가 난 것이다. 

 

 

③ 오류 정정

위 과정을 통해 5번째 bit에서 오류가 나타난 것을 확인했으니 5번째 bit를 0 → 1 또는 1 → 0으로 교체하면 오류가 없는 data가 된다. 

 

2) 예제 문제

위 방법을 토대로 예제 문제를 풀어보자.

 

data : 1001 0101

 

① parity bit 검출

 

- p1 검출

p1을 검출할 때는 p1, d1, d2, d4, d5, d7를 확인해야 한다.

1의 개수가 짝수가 되도록 p1을 설정해야 하므로 p1은 0이다.

p1 = 0

 

- p2 검출

p2를 검출할 때는 p2, d1, d3, d4, d6, d7를 확인해야 한다.

1의 개수가 짝수가 되도록 p2를 설정해야 하므로 p2는 1이다. 

p2 = 1

 

- p4 검출

p4를 검출할 때는 p4, d2, d3, d4, d8을 확인해야 한다. 

1의 개수가 짝수가 되도록 p4를 설정해야 하므로 p4는 0이다.

p4 = 0

 

- p8 검출

p8을 검출할 때는 p8, d5, d6,d7,d8을 확인해야 한다.

1의 개수가 짝수가 되도록 p8을 설정해야 하므로 p8은 0이다.

p8 = 0

 

최종적으로 다음과 같이 12bit가 전송될 것이다.

 

 

② 오류 검출

 

- 송신된 data 

- 수신된 data 

 

위와 같이 수신된 data가 송신된 data와 다르게 d2에서 오류가 났다. 

 

하지만 수신을 받는 입장에서는 오류가 났는지 모르기 때문에 확인해야한다. 

 

- p1 확인

p1을 확인하면 1의 개수가 홀수다.

 

- p2 확인

p2를 확인하면 1의 개수가 짝수다.

- p4 확인

p4를 확인하면 1의 개수가 홀수다.

- p8 확인

p8을 확인하면 1의 개수가 짝수다.

 

1의 개수가 홀수인 parity bit는 p1, p4다.

 

즉 p1 + p4 = 5 -> 5번째 bit에서 오류난 것을 확인할 수 있다.

 

③ 오류 정정

위 과정을 통해 5번째 bit에서 오류난 것을 확인했으니 5번째 bit를 변경하면 된다. 

 

결론적으로 Hamming code를 통해 수신된 data가 오류가 생긴것을 확인할 수 있었고 오류를 정정하여 원래 data로 받을 수 있다.

'컴퓨터구조' 카테고리의 다른 글

[컴퓨터 구조] Register  (0) 2025.03.17
[컴퓨터 구조] memory  (0) 2025.01.02
[컴퓨터 구조] cache memory  (0) 2025.01.02