해밍 거리(Hamming distance)

길이가 같은 두 문자열을 자리마다 비교해 다른 곳을 셉니다. 1011101과 1001001은 셋째와 다섯째 자리가 달라 해밍 거리가 2입니다. 0과 1로 된 비트열이라면, 두 수를 이진수로 적어 자리마다 비교하는 셈입니다. 비트열을 '1이 있는 자리들의 집합⁠(set)⁠'으로 보면, 해밍 거리는 둘 중 한쪽에만 있는 원소⁠(element)⁠들의 모임(대칭차⁠, symmetric difference⁠)의 크기입니다(집합 연산). 0/1 벡터⁠(vector)⁠ 사이의 맨해튼 거리⁠(Manhattan distance)⁠와도 같습니다. 컴퓨터는 두 비트열을 XOR(자리마다 두 비트가 다르면 1, 같으면 0)한 뒤 1의 개수를 세어 구합니다(불 대수⁠, Boolean algebra⁠). 대칭차의 크기를 합집합⁠(union)⁠의 크기로 나누면 1에서 자카드 지수⁠(Jaccard index)⁠를 뺀 값이 됩니다. 물론 세 규칙을 지키는 거리 함수⁠(metric)⁠입니다.

3비트 문자열 여덟 개를 정육면체의 꼭짓점⁠(vertex)⁠에 놓으면, 한 비트만 다른 문자열끼리 모서리로 이어집니다. 해밍 거리는 모서리를 따라가는 최단 경로⁠(shortest path)⁠의 길이입니다. 이 정육면체는 그래프이고, n비트라면 n차원 정육면체(초입방체⁠, hypercube⁠)가 됩니다. 한 점에서 거리가 k인 문자열은 n자리 가운데 뒤집을 k자리를 고르는 방법의 수, 곧 이항계수⁠(binomial coefficient)⁠ $\binom{n}{k}$개입니다. 꼭짓점을 누르면 노란 점 A와 분홍 점 B가 번갈아 옮겨집니다. 지금 A = , B = , 해밍 거리는 입니다.

잡음이 있는 통신선에서는 비트가 가끔 뒤집힙니다. 0은 000으로, 1은 111로 세 번 되풀이해 보내기로 약속합시다. 약속한 문자열을 부호어라 합니다. 두 부호어⁠(codeword)⁠ 사이의 해밍 거리가 3이라, 비트 하나가 뒤집혀도 받은 문자열(예: 010)은 여전히 원래 부호어(000)에 더 가깝습니다. 가장 가까운 부호어로 읽으면 오류가 고쳐집니다. 색은 해밍 거리로 나눈 보로노이 영역⁠(Voronoi region)⁠입니다. 일반적으로 부호어 사이의 최소 거리가 d이면 d − 1개까지의 오류는 알아챌 수 있고(부호어가 다른 부호어로 바뀌지 않으니), $(d-1)/2$의 소수점 아래를 버린 $\lfloor (d-1)/2 \rfloor$개까지는 고칠 수 있습니다(여전히 원래 부호어가 가장 가까우니). 다만 이 반복 부호⁠(repetition code)⁠는 3비트를 보내 1비트만 전하니 낭비가 큽니다.

벨 연구소의 해밍은 7비트로 4비트를 보내면서도 오류 하나를 고치는 오류 정정 부호⁠(error-correcting code)⁠를 만들어 1950년에 발표했습니다. 데이터 비트 d₁…d₄에 검사 비트⁠(check bit)⁠ p₁, p₂, p₃를 더하는데, 그림의 세 원 안에서 1의 개수가 각각 짝수가 되도록 정합니다. 짝수인지는 2로 나눈 나머지⁠(remainder)⁠로 봅니다. 보낼 데이터를 (이진수 )로 정하면 부호어는 입니다. 비트를 눌러 뒤집어 보세요(잡음). 받은 문자열은 입니다. 1의 개수가 홀수가 된 원에 1, 짝수인 원에 0을 적어 이진수로 읽은 값을 신드롬⁠(syndrome)⁠이라 하며, 지금 입니다. 병의 증상들을 모아 원인을 짚는 '증후군'에서 빌린 이름입니다. 한 비트 잡음 두 비트 잡음 잡음 지우기

비밀은 자리 번호에 있습니다. 검사 1은 번호의 이진수 첫째 자리가 1인 위치(1, 3, 5, 7)를, 검사 2는 둘째 자리가 1인 위치(2, 3, 6, 7)를, 검사 3은 셋째 자리가 1인 위치(4, 5, 6, 7)를 봅니다. 그래서 k번 비트가 뒤집히면 k의 이진수에서 1인 자리의 검사들만 홀수가 되고, 신드롬이 곧 k입니다. 부호어 16개 각각을 중심으로 거리 1 안의 문자열(자기 자신과 이웃 7개)을 모으면 $16 \times 8 = 128 = 2^7$, 7비트 문자열 전체를 빈틈없이 겹치지 않게 덮습니다. 이런 부호를 완전 부호⁠(perfect code)⁠라고 합니다. 두 비트가 뒤집히면 엉뚱한 부호어로 '고쳐' 버립니다. 비트마다 독립적으로 확률⁠(probability)⁠ q로 뒤집힌다면 한 덩어리의 오류 개수는 이항분포⁠(binomial distribution)⁠를 따르니, q가 작을 때 둘 이상일 확률은 7자리 가운데 두 자리를 고르는 21가지에서 나오는 약 $21q^2$입니다. q = 0.001이면 약 0.002%입니다. 검사를 행렬⁠(matrix)⁠로 적으면 신드롬은 받은 벡터에 검사 행렬⁠(parity-check matrix)⁠을 곱한 값(2로 나눈 나머지)입니다.

이어지는 곳.

• 오늘날 서버에 쓰는 ECC 메모리(오류 정정 메모리)는 흔히 해밍 부호⁠(Hamming code)⁠에 전체 짝수 검사 비트 하나를 더한 확장 해밍 부호나 그 변형을 씁니다. 검사 비트 하나를 더하면 부호어 사이의 최소 거리가 3에서 4로 늘어납니다. 비트 하나가 뒤집히면 고치고, 둘이 뒤집히면 적어도 알아챕니다.
• QR 코드와 CD는 더 강한 리드–솔로몬 부호⁠(Reed–Solomon code)⁠를 씁니다. 1960년 어빙 리드와 구스타브 솔로몬이 만든 부호로, 비트 하나하나 대신 여러 비트의 덩어리(보통 8비트) 단위로 다룹니다. 덩어리 안에서 비트가 몇 개 망가지든 오류 하나로 세므로 연달아 망가진 부분에 강하고, CD는 여기에 자료의 순서를 흩어 기록하는 방법까지 더해 긁힌 자국을 견딥니다.
• RSA 같은 암호가 엿듣는 사람을 막는다면, 오류 정정 부호는 잡음을 막습니다. 둘 다 보내는 내용을 약속된 방식으로 바꾸어 보내지만 막는 상대가 다릅니다.
• 오류 정정 부호가 일부러 여분을 더한다면, 거꾸로 여분을 덜어 내 길이를 줄이는 쪽은 허프만 부호⁠(Huffman coding)⁠ 같은 압축입니다.
• 길이가 다른 문자열까지 비교하려면 글자를 넣고 빼는 것도 허용하는 편집 거리⁠(edit distance)⁠로 넘어갑니다.
• 받은 문자열을 가장 가까운 부호어로 읽는 것은 최근접 이웃⁠(nearest neighbor)⁠ 찾기와 같습니다.
• 부호어를 얼마나 촘촘히 둘 수 있는지, 곧 잡음이 있는 통로로 오류 확률을 원하는 만큼 작게 하면서 한 번에 얼마나 많은 정보를 보낼 수 있는지의 한계는 통로 부호화 정리⁠(noisy-channel coding theorem)⁠가 답합니다.