본문 바로가기

Lecture & Tip/Electronic Engneering

[펌]해밍코드 검출 및 정정 방법

오류를 검출하는 해밍코드에 대해서 나름대로 분석을 해봤는데 컴퓨터구조(전자계산기구조)
공부하시는 분들에게 조금 더 이해하기 쉽도록 하기 위해서 지식을 나눠드립니다..


패리티 비트(Parity Bit)에 의한 오류 검출은 단지 오류 검출만 되지만 해밍코드
(Hamming Code)는 오류 검출후 오류 정정까지 가능한 것입니다.
해밍 코드는 R. W. Hamming에 의해 고안된 것이며, 데이터 비트에 따른 패리티 비트는
다음 수식에 의해 구해집니다.
2(p승) >= m + P + 1 (m은 데이터 비트값)
즉, 해밍코드에의해 구성된 코드가 16비트로 주어졌을 경우 2(p승)=16 이 되므로
p 값은 4가 되고 식에 의해서 16 >= m+ 4 + 1 이므로 m = 11 이 됩니다..
즉 데이터 비트값 : 11비트, 패리티 비트 : 5(4+1계산)비트 가 되는거겠죠?

이젠 본격적으로 해밍코드의 신기한 오류 검출방식을 보도록 하죠..
해밍코드는 정해진 위치의 패리티를 검색한후 오류체크를 하게되고 잘못된 위치를 찾아내게
됩니다.. 그럼.. 아래의 C1, C2, C4 를 가지고 5의 해밍코드를 우선 구해보겠습니다.
* C1 : 행 1, 3, 5, 7 짝수 패리티 체크
* C2 : 행 2, 3, 6, 7 짝수 패리티 체크
* C4 : 행 4, 5, 6, 7 짝수 패리티 체크
위의 C1, C2, C4 행의 각 셀에 들어있는 수를 비교하여 1의 개수를 짝수로 만들어 줘야
합니다... 10진수 5의 해밍코드를 구해봅시다. 10진수 5는 이진수로 0101 입니다
그럼.. 아래 그림처럼.. 8 4 2 1 위치에 순서대로 0 1 0 1 이 들어가겠죠?
C1 C2 8 C4 4 2 1
0 1 0 1

우선 C1을 비교해보면.. C1은 1,3,5,7 을 비교하라고 했죠? 그럼.. C1,8,4,1 자리의 값들을
비교해보면.. C1은 값이 없고 8,4,1자리의 값이 0,1,1 이기때문에 1의 개수가 짝수가 되려면
C1값에는 0이 들어가면 되겠죠?
다음으로 C2는 2,3,6,7을 비교하라고 했으니 C2,8,2,1자리의 값들을 비교해 보면
C2는 빈값 8,2,1 자리 값들이 0,0,1 이므로 1의 개수가 짝수가 되려면 C2값이 1이 되야
합니다.. C4역시 다음과 같이 하면...
C1 C2 8 C4 4 2 1
0 1 0 0 1 0 1

위와같은 5의 해밍코드를 얻을 수 있습니다..
여기까지 알았으면 이젠 해밍코드가 어떤식으로 오류를 검출해서 변경하는지 알아야 겠죠?
만일... 5라는 데이터 값에 잘못된 값이 들어갔을 경우..

▶ 제대로된 해밍코드
C1 C2 8 C4 4 2 1
0 1 0 0 1 0 1

▶ 잘못된 해밍코드
C1 C2 8 C4 4 2 1
0 1 0 0 0 0 1

값을 보면.. 4라는 위치의 값이 1이 되야 하는데 아래 그림에서보면
0이 들어갔죠??
그럼.. 잘못된 이 해밍코드를 봅시다. 위에서 비교한것 처럼 C1,C2,C4의
자리를 비교해 보죠
C1 : 1,3,5,7 자리값 비교해 보면 1의 개수가 1개 입니다. 짝수가 아니므로 오류값 C1=1
C2 : 2,3,6,7 자리값 비교해 보면 1의 개수가 2개 입니다. 짝수이므로 이상없음 C2=0
C4 : 4,5,6,7 자리값 비교해 보면 1의 개수가 1개 입니다. 짝수가 아니므로 오류값 C4=1
즉, C1=1, C2=0, C4=1 이라는 오류값이 나왔죠? 그럼 이것을 C4 / C2 / C1 순서로 나열해
보시면 1 / 0 / 1 이라고 나오죠? 그럼 이진수 101을 10진수로 고치면? 5라는 수가
나옵니다.. 아래 그림처럼 4라는 위치가 앞에서 부터 5번째 칸이죠??
즉, 5번째 자리의 값이 잘못되었다는 오류를 찾아내게 됩니다.
▶ 제대로된 해밍코드
C1 C2 8 C4 4 2 1
0 1 0 0 1 0 1

▶ 잘못된 해밍코드
C1 C2 8 C4 4 2 1
0 1 0 0 0 0 1

컴퓨터는 0과 1이라는 수만인식하기 때문에 0의 값이 잘못되었다고 인식하게되면
0의 값을 1이라고 자동으로 변환하게 됩니다.. 그럼.. 제대로된 해밍코드가 스스로 수정이
되겠죠??
이쯤에서 Tip을 하나 알려드리겠습니다..
이 부분은 설명이 된부분을 아직 제가 못봐서 대부분이 잘 모르고 있지 않을까 싶어서
제가 혼자서 알게된 방법이라서 혹시나 틀린부분이 있더라도 이해해 주시고 쪽지 날려주세요
왜? 아래와 같이 꼭~ 저런 자리를 체크해야하는가?
* C1 : 행 1, 3, 5, 7 짝수 패리티 체크
* C2 : 행 2, 3, 6, 7 짝수 패리티 체크
* C4 : 행 4, 5, 6, 7 짝수 패리티 체크
쉽게 설명하죠.. C 뒤에 붙어있는 숫자들은.. 2(0승)=1, 2(1승)=2, 2(2승)=4
입니다. 그럼.. 여러분이 1,2,4 라는 카드를 각각 몇장씩 들고있다고 생각해 보세요..
그리고 나서 자기 자신의 카드와 합치지 않고 서로 다른 카드와 합쳤을때 만들어지는 수를
만들어 봅시다..
1이라는 숫자를 맞들수 있는것은 단지 1카드 한장밖에 없습니다.. 또한 2라는 숫자를
만들수 있는 카드는 2라는 카드 1장 밖에 없습니다.. 그럼 우선 아래와 같이 써주세요..
* C1 카드자리 : 1
* C2 카드자리 : 2
* C4 카드자리 :
그럼.. 이번엔 3을 만들려면 1이란 카드와 2란 카드가 필요하겠죠? 그럼 1카드 자리와
2카드 자리에 3이라는 값을 써주세요.. 그리고 4를 만들수 있는 카드는 4카드 밖에 없습니다
그럼 다음과 같이 되겠죠?
* C1 카드자리 : 1, 3
* C2 카드자리 : 2, 3
* C4 카드자리 : 4
위와 같이 계속 해보면.. 5는 1과 4카드 자리에 위치하게 되고 6은 2와4 카드자리에 위치,
7은 1,2,4 모든 카드자리에 들어가게 되어서 비로소 아래와 같이 완성이 된다.
* C1 : 행 1, 3, 5, 7 짝수 패리티 체크
* C2 : 행 2, 3, 6, 7 짝수 패리티 체크
* C4 : 행 4, 5, 6, 7 짝수 패리티 체크
이것은.. 그냥.. 혼자서 끄적대다가 규칙적인게 발견이 되어서 이해하기 쉽기에 제가 기술
한것이고.. 좀 더 정확히 알아 봅시다...
10진수 2진수
c4 c2 c1
1 0 0 1
2 0 1 0
3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1

위의 표를 보시면 왼쪽의 10진수를 우측에 해당되는 2진수로 변형시켜 놓았습니다..
아까 위에서 오류가 없는 부분은 0 오류가 있는 부분은 1 이었다는걸 기억해 보십시오
그럼 바로 위에 있는 표를 보듯이 C1은 1이라는 값들이 1,3,5,7 이란 위치에만 1이있고
C2는 2,3,6,7 이란 위치에 C4는 4,5,6,7이란 위치에만 1이있다는것을 한눈에 확인할 수
있죠??
어때요? 해밍코드에 대해서 그냥.. 긴가민가하게 이해하고 넘어가신 분들.. 이정도의
지식이면 해밍코드가 어떻게 만들어졌는지의 원리를 알게되면서 쉽게 이해가 되고 신기하지
않습니까? 도움이 되셨길 바라며 이만 마칩니다 (__)//