GF(2)와 Hamming 선형 부호

유한체에서 패리티를 계산하기

GF(2)는 0과 1을 원소로 가지며 덧셈은 XOR, 곱셈은 AND와 같습니다. 따라서 1+1=0입니다. 이 산술을 사용하면 “비트 합이 짝수인가?”라는 검사를 행렬 곱으로 표현할 수 있습니다. 실수 위의 최소제곱과 달리 거리나 역행렬을 실수 연산으로 계산해서는 안 됩니다.

Hamming(7,4)는 정보 4비트에 패리티 3비트를 더합니다. H의 열은 위치 1~7의 이진수이며, 아래 행 순서는 낮은 자리부터입니다.

정보에서 부호어로

정보 비트를 위치 3,5,6,7에 낮은 비트부터 놓고 패리티 위치 1,2,4를 정합니다. 각 검사 행과 부호어 c의 내적이 GF(2)에서 0이어야 합니다. 유효 부호어 집합은 H의 영공간이며 차원 4입니다. 생성행렬 G를 쓰면 c=Gm, HG=0으로도 표현합니다.

정보 정수 9는 낮은 자리부터 (1,0,0,1)입니다. 이를 넣으면 위치 1부터 부호어는 0011001입니다. 위치 3이 뒤집힌 수신열의 syndrome은 H의 세 번째 열, 즉 (1,1,0)입니다. 낮은 자리부터 해석하면 정수 3이므로 그 위치를 다시 뒤집습니다.

왜 한 오류를 고칠 수 있는가

H의 모든 열이 서로 다른 비영 벡터입니다. 따라서 가중치 1의 유효 부호어도, 가중치 2의 유효 부호어도 없습니다. 반면 1번 열 XOR 2번 열은 3번 열이므로 위치 1,2,3에 1인 벡터는 영공간에 있습니다. 최소 거리는 정확히 3이고 보장 정정 능력은 1입니다.

검사 통과와 올바른 복원의 차이

같은 정보 9에서 위치 1과 2를 뒤집으면 syndrome이 다시 3입니다. 복호기는 한 오류로 가정하고 위치 3을 뒤집어 다른 유효 부호어로 이동합니다. 복원 정보는 8이며, 정정 뒤 syndrome은 0입니다. 패리티 통과는 원래 메시지라는 증명이 아닙니다. 원래 Hamming 부호는 최대 두 오류를 검출할 수 있지만 이 단일 오류 정정기는 비영 syndrome을 모두 정정하려 하므로 두 오류를 잘못 고칠 수 있습니다.

실습의 파랑은 전송, 주황은 수신 비트입니다. 표에서 정정 결과도 비교하세요. 실제 시스템의 SECDED는 전체 패리티 등을 더해 단일 정정과 이중 검출을 구분하지만 현재 7비트 실험에는 포함하지 않습니다.

확인 문제와 해설

1. 패리티 비트의 오류도 고치나요? 예. H의 모든 위치에 고유 열이 있어 정보와 패리티를 같은 방식으로 검사합니다.
2. 부호어 두 개의 XOR도 유효한가요? 예. H(c₁+c₂)=0이므로 선형 부분공간에 남습니다.
3. n=7, 정보 4비트의 전송률은? 4/7입니다. 실수 벡터 차원 대신 GF(2)에서의 정보 비트 수를 셉니다.

추가 읽기: MIT MAS.160, Hamming Codes and Syndromes.