스스로 잘못을 고치는 부호

모눈에 0과 1을 3×3으로 적습니다. 각 가로줄 끝에 그 줄의 1의 개수가 짝수가 되도록 0이나 1을 덧붙입니다. 각 세로줄 아래에도 같은 일을 합니다.

이제 친구가 아무 칸이나 하나 뒤집습니다. 가로줄을 세어 보면 한 줄만 홀수이고, 세로줄도 하나만 홀수입니다.

그 둘이 만나는 칸이 범인입니다. 도로 뒤집으면 원래대로. 누가 알려 주지 않아도 스스로 고쳤습니다.

1의 개수를 짝수로 맞추려고 덧붙이는 한 자리를 검사 비트(패리티)라 합니다.

검사 비트가 하나뿐이면 「어딘가 틀렸다」까지만 압니다. 어디인지는 모릅니다. 발견은 되고 정정은 안 됩니다.

그런데 검사 비트를 여럿 두고, 각각이 겹치되 서로 다른 자리들을 감시하게 하면 이야기가 달라집니다. 어긋난 검사들의 조합이 틀린 자리를 가리키기 때문입니다.

해밍 (7,4) 부호 — 데이터 4비트에 검사 3비트를 붙여 7비트로 보냅니다.

검사 비트 개로 가지를 가릴 수 있고, 「틀린 데 없음」 한 가지에 「어느 자리가 틀렸나」 가지를 더해야 하므로 .

이면 — 딱 맞습니다. 군더더기가 한 자리도 없어서 완전부호라 부릅니다.

바꿔 말하면 서로 다른 두 부호말은 적어도 세 자리가 다릅니다. 그래서 한 자리가 틀려도 가장 가까운 부호말이 하나로 정해집니다.

얼마나 담을 수 있을까요. 정정 능력을 높이려면 검사 자리를 늘려야 하고, 그만큼 실을 수 있는 데이터가 줍니다. 이 맞바꿈에는 한계가 있습니다.

1948년 섀넌이 그 한계를 못박았습니다. 통로마다 용량이라는 값이 있고, 그보다 낮은 속도로 보내면 오류를 원하는 만큼 0에 가깝게 만들 수 있다는 것입니다.

🚩 그런데 섀넌의 증명은 그런 부호가 있다는 것만 말하고 어떻게 만드는지는 말하지 않았습니다. 제127장 과 같은 종류의 정리입니다. 그 한계에 실제로 닿는 부호(터보·LDPC·폴라)를 찾는 데 반세기가 걸렸습니다.