패리티비트와 해밍코드

해밍 코드의 정의는 위키를 참고 하시고..
간략하게는 통신에서 전송된 비트의 오류 검출 및 수정을 할 수 있는 용도라고 생각하면 되겠다.

https://ko.wikipedia.org/wiki/%ED%95%B4%EB%B0%8D_%EB%B6%80%ED%98%B8

원본 데이터를 기준으로 패리티 비트를 추가해서 새로운 데이터를 만들게 되는데
새로운 데이터를 만드는 과정을 가능한 자세하게 설명하려고 한다.
(처음에 텍스트만 보고 이해가 안 갔으니까..)

우선 원본 데이터 비트 수(n)에 따라 삽입할 패리티 비트의 수(p)가 정해진다.
공식은 아래와 같다.

2^p >= p + n + 1 (2^3: 2의 3승은 8이다)

원본 데이터가 1011 (4비트)라고 한다면, 필요한 패리티 비트의 수(p) = 3이 된다.

p = 2, n = 4를 대입해서 계산해보면
2^2 >= 2 + 4 + 1
4 > = 7 이기 때문에 성립하지 않는다.

p = 3, n = 4를 대입해서 계산해보면
2^3 >= 3 + 4 + 1
8 >= 8 이니까 성립한다.

그러니까 공식을 만족하는 p의 최소값은 3이다.
그럼 원본 데이터 (4비트) + 추가할 패리티 비트 (3비트) 를 결과 비트는 7비트가 된다.
비트의 인덱스를 아래처럼 1 - 7로 붙이면..

1	2	3	4	5	6	7
패리티비트1	패리티비트2	1	패리티비트3	0	1	1

이렇게 구성된다. 패리티 비트가 어느 자리에 들어갈 지는 2^p-1 을 기준으로 한다.
우리는 3개의 패리티 비트를 사용하게 되니까, 2^0, 2^1, 2^2 자리에 패리티 비트를 넣게 된다.

패리티비트1, 2, 3의 명칭을 p1, p2, p3로 정하겠다. 너무 기니까...
p1의 경우는 p1부터 시작해서 2^0(1)칸을 채우고 1칸을 건너뛰게 된다.
p2의 경우는 p2부터 시작해서 2^1(2)칸을 채우고 2칸을 건너뛰게 된다.
p3의 경우는 p3부터 시작해서 2^2(4)칸을 채우고 4칸을 건너뛰게 된다.
각 패리티 비트의 시작점은 위에서 확인했으니까.. (예:1번 칸은 p1의 칸)

	1	2	3	4	5	6	7
p1	p1 시작점
p2		p2시작점
p3				p3시작점

위와 같이 패리티 비트를 채워야되는 위치를 확인할 수 있다.
패리티 비트를 직접 채워보기 전에 이 사항을 먼저 알아야 한다.
패리티 비트는 짝수 패리티 비트와 홀수 패리티 비트가 있다. 비트의 값은 항상 0 또는 1 이니까
원본 데이터의 경우는 1011 이므로 기존 상태는 홀수다. 만약 짝수 패리티 비트를 사용한다면
1의 합이 짝수가 되도록 패리티 비트를 구성하는 것이다.

원본 데이터를 기준으로 짝수 패리티 비트가 되도록 구성해보면 아래와 같다.

	1	2	3	4	5	6	7
원본데이터	p1	p2	1	p3	0	1	1
p1	p1 = 0		1		0		1
p2		p2 = 1	1			1	1
p3				p3 = 0	0	1	1
결과비트	0	1	1	0	0	1	1

1. 각 행마다 위에서 내려온 채워넣어야하는 위치(색상으로 칠해진 곳)에 패리티 비트가 아닌 원본 데이터가 있는 경우에는 그걸 채워넣는다.

2. 그리고 우리는 짝수 패리티 비트를 하기로 했으니까, 1의 합을 보면 p1행은 현재 짝수다.
 따라서, p1 = 0이 들어가면 짝수가 유지된다.
 p2행은 현재 홀수다. 따라서 p2 = 1이 들어가면 짝수가 된다.
 p3행은 현재 짝수다. 따라서 p3 = 0이 들어가면 짝수가 유지된다.

3. 결과비트를 위에서부터 채워진 값을 그대로 내려적는다.

이렇게 구성된 결과비트를 해밍코드라고 한다.
0110011 를 전송했는데, 받는 쪽에서 0111011 로 받았다고 가정하고, 오류를 수정해봅시다.

	1	2	3	4	5	6	7
수신 데이터	0	1	1	1	0	1	1
p1	p1 = 0		1		0		1
p2		p2 = 1	1			1	1
p3				p3 = 1	0	1	1

위와 같이 수신 데이터를 기준으로 p1, p2, p3에 대해 패리티 비트를 계산해보면
우리는 분명 짝수 패리티 비트로 구성했는데, p3 행의 합은 홀수 패리티 비트인 것을 알 수 있다.

p3 = 0이 되면, 정상적으로 짝수 패리티 비트를 만족하므로 4번 칸의 수신 데이터는 1 -> 0 으로
변경되어야 한다. 그럼 전송 데이터와 일치하는 것을 알 수 있다.