틀려도 되살아난다

1잡음은 피할 수 없다

메시지를 비트(0과 1)로 보낸다고 합시다. 채널 어딘가에서 0이 1로, 또는 그 반대로 뒤집히는 일은 막을 수 없습니다. 더 큰 문제는 — 받은 쪽이 틀렸다는 사실조차 모른다는 점입니다. 1001을 받았을 때, 그게 원래 보낸 것인지 어딘가 뒤집힌 것인지 알 길이 없죠.

그래서 메시지에 규칙(여분)을 더합니다. 보내도 되는 비트열을 코드워드라 부르고, 아무 비트열이나 코드워드가 되지 못하게 막아두는 겁니다. 그러면 코드워드가 아닌 게 도착했을 때 "어, 뒤집혔구나"를 알 수 있고 — 운이 좋으면 가장 가까운 코드워드로 되돌릴 수도 있습니다.

2거리가 곧 힘 — 반복부호와 해밍 거리

가장 단순한 여분은 그냥 여러 번 보내기입니다. 1을 111로, 0을 000으로. 받은 쪽은 다수결로 판정하죠. 한 비트가 뒤집혀 101이 와도 1이 둘이니 원래 1로 복원됩니다 — 한 개의 오류를 고쳐냅니다.

왜 한 개는 되고 두 개는 안 될까요? 두 코드워드 000과 111은 세 자리가 다릅니다. 이렇게 "두 비트열이 몇 자리에서 다른가"를 해밍 거리라 합니다. 코드워드끼리 최소 거리가 \(d\)이면, 한 코드워드를 \(\lfloor (d-1)/2 \rfloor\)개 이하의 오류로는 다른 코드워드로 착각할 수 없습니다.

반복부호는 \(d=3\)이라 \(\lfloor 2/2\rfloor = 1\)개를 정정합니다. 하지만 1비트를 고치려고 비트 수를 세 배로 늘리는 건 너무 헤픕니다. 더 영리하게 거리를 벌 수는 없을까요?

3해밍(7,4) — 어디가 틀렸는지 짚어낸다

1950년 리처드 해밍은 데이터 4비트에 검사(패리티) 비트 3개만 더해, 총 7비트 안의 어떤 한 비트가 틀려도 그 위치를 정확히 집어내 고치는 부호를 만들었습니다. 비결은 세 패리티가 서로 겹쳐 데이터 비트를 감시하는 구조 — 아래 세 원의 벤 다이어그램이 그 전부입니다.

홀수가 된 원 세 개의 상태 \((c_A,c_B,c_C)\)를 이진수로 읽으면 그대로 틀린 비트의 번호(신드롬)가 됩니다. 아무 것도 안 틀렸으면 \((0,0,0)\). 데이터 4비트로 보낼 수 있는 \(2^4=16\)개의 코드워드는 서로 최소거리 \(d=3\)이라, 7비트 중 어느 한 자리가 뒤집혀도 항상 정확히 원상복구됩니다 — 반복부호와 같은 정정력을, 세 배가 아니라 1.75배(7/4)의 비용으로 얻은 셈입니다.

4유한체와 리드–솔로몬 — CD·QR의 진짜 일꾼

해밍 부호는 한 비트 오류에 강하지만, 현실의 흠집·먼지·전파 방해는 연달아 뭉텅이로(버스트) 비트를 망가뜨립니다. 그래서 CD·DVD·QR코드·위성통신은 한 단계 더 나아간 리드–솔로몬(Reed–Solomon) 부호를 씁니다.

핵심 아이디어는 비트 하나하나가 아니라 바이트(기호)를 통째로 다루되, 그 기호들을 갈루아가 만든 유한체 \(\mathrm{GF}(2^8)\)(원소 256개)의 수로 보고, 다항식의 계수로 늘어놓는 것입니다. 메시지가 정하는 다항식을 여러 점에서 평가해 여분 기호를 붙이면 — 마치 두 점으로 직선을, 세 점으로 포물선을 되살릴 수 있듯 — 일부 기호가 통째로 사라지거나 틀려도 남은 점들로 원래 다항식을 복원할 수 있죠.

5QR코드 — 가려도 읽힌다

QR코드는 리드–솔로몬을 품고 있어서, 일부러 망가뜨려도 읽힙니다. 정정 수준(레벨)은 네 단계 — 대략 복원 가능한 손상 비율이 L ≈ 7%, M ≈ 15%, Q ≈ 25%, H ≈ 30%입니다. 그래서 가운데에 로고를 떡하니 박은 QR코드(보통 레벨 H)가 멀쩡히 스캔되는 거죠. 아래에서 직접 가려 보세요.

6맺으며

오류정정부호는 오류를 없애지 않습니다 — 오류는 늘 일어납니다. 다만 메시지에 수학적 구조를 입혀, 틀린 곳을 스스로 가리키고 되살리게 만들 뿐이죠. 해밍 거리라는 단순한 개념에서 시작해, 갈루아의 유한체 위 다항식까지 — 1977년 발사된 보이저 탐사선이 지금도 성간 공간에서 보내오는 신호가, 그리고 방금 당신이 찍은 QR코드가, 같은 수학으로 "틀려도 되살아나고" 있습니다.