오류 정정 부호(Error-correcting code)

전파는 잡음에 섞이고, 디스크는 긁히고, 메모리의 비트는 우주선(cosmic ray)에 맞아 뒤집힙니다. 믿을 수 없는 통로로 믿을 만하게 보내는 방법은 여분을 덧붙이는 것입니다. 가장 단순한 예는 비트마다 세 번씩 보내고 받는 쪽에서 다수결로 읽는 반복 부호입니다. 셋 중 하나가 뒤집혀도 원래 비트를 되찾습니다. 부호의 성능은 두 수로 잽니다. 보낸 비트 가운데 진짜 정보의 비율인 전송률⁠(code rate)⁠ R과, 부호어끼리 가장 가까운 해밍 거리⁠(Hamming distance)⁠ d입니다. d가 3이면 오류 하나를 고치고, 일반적으로 $\lfloor (d-1)/2 \rfloor$개까지 고칩니다. 반복 부호⁠(repetition code)⁠는 d = 3이지만 R = 1/3이라 값이 비쌉니다.

20×14 = 280비트짜리 그림을, 비트마다 확률⁠(probability)⁠ $q =$ 로 뒤집히는 통로로 보냅니다. 부호: . 다시 보내기

빨간 점이 받은 쪽에서 틀리게 읽은 화소입니다. 오른쪽 곡선은 데이터 4비트 한 묶음이 틀릴 확률입니다. 통로에서 뒤집히는 비트 수는 이항분포⁠(binomial distribution)⁠를 따르니 이항계수⁠(binomial coefficient)⁠로 정확히 계산됩니다. 1950년 벨 연구소의 리처드 해밍이 만든 해밍 부호 (7,4)는 데이터 4비트에 검사 비트⁠(check bit)⁠ 3개를 붙여 7비트로 보냅니다. 검사 비트 셋은 각각 데이터 비트의 서로 다른 묶음에서 1의 개수가 짝수인지 홀수인지(패리티⁠, parity⁠)를 적은 것이라, 비트 하나가 뒤집히면 어긋난 검사들의 조합이 일곱 자리 가운데 어디가 틀렸는지를 알려 줍니다. 7비트 가운데 하나까지의 오류를 고치면서 전송률이 4/7이니, 데이터 4비트에 12비트를 쓰는 3회 반복보다 훨씬 쌉니다. 대신 오류가 둘 이상인 덩어리는 엉뚱한 부호어⁠(codeword)⁠로 '고쳐' 버립니다. 그래서 곡선을 견주어 보면 4비트 묶음이 틀릴 확률은 어느 q에서나 3회 반복보다 조금 높습니다(q가 작을 때 약 $21q^2$ 대 $12q^2$). 적은 비트로 비슷한 보호를 얻는 셈입니다.

그렇다면 믿을 만하게 보내려면 전송률을 0 가까이 낮춰야 할까요? 1948년 섀넌의 통로 부호화 정리⁠(noisy-channel coding theorem)⁠는 아니라고 답합니다. 이 통로에는 용량⁠(capacity)⁠ $C = 1 - H(q)$가 있어서(H는 엔트로피⁠(entropy)⁠; 들어간 비트와 나온 비트의 상호 정보량⁠(mutual information)⁠의 최댓값), 전송률이 C보다 작기만 하면 부호 길이를 늘려 오류 확률을 얼마든지 작게 할 수 있고, C보다 크면 어떤 부호로도 오류 확률을 0에 가깝게 할 수 없습니다. 지금 q에서 용량은 비트당 입니다. 섀넌의 증명은 무작위로 고른 긴 부호가 거의 언제나 좋다는 확률적 논증이었고, 받은 신호가 원래 부호어 근처에 몰린다는 것은 큰 수의 법칙⁠(law of large numbers)⁠에서 나옵니다. 용량에 다가가는 실용적인 부호는 한참 뒤에야 나왔습니다. 1993년 프랑스의 클로드 베루와 알랭 글라비외가 내놓은 터보 부호⁠(turbo code)⁠, 1960년대 미국의 로버트 갤러거가 고안했다가 90년대에 재발견된 LDPC 부호(검사 하나하나가 비트 몇 개만 보는, 성긴 검사 행렬⁠(parity-check matrix)⁠을 쓰는 부호), 2009년 터키의 에르달 아르칸이 내놓은 극 부호⁠(polar code)⁠가 그것입니다. 5G 이동통신은 LDPC와 극 부호를 씁니다.

해밍 부호⁠(Hamming code)⁠처럼 많이 쓰는 부호는 선형입니다. 두 부호어를 자리마다 XOR로 더해도 다시 부호어가 된다는 뜻입니다. 비트를 2로 나눈 나머지⁠(remainder)⁠의 수로 보면 데이터 벡터⁠(vector)⁠에 생성 행렬⁠(matrix)⁠을 곱한 것이 부호어이니, 부호어들은 생성 행렬⁠(generator matrix)⁠의 열공간⁠(column space)⁠입니다. 받은 비트열에 검사 행렬을 곱하면(행렬의 곱⁠, matrix multiplication⁠) 부호어일 때는 0이 나오고, 비트 하나가 뒤집혔을 때는 그 자리에 따라 정해진 값이 나옵니다. 이 결과를 신드롬⁠(syndrome)⁠이라 하며, 신드롬이 오류의 위치를 알려 줍니다. 1960년 미국의 어빙 리드와 구스타브 솔로몬이 내놓은 리드–솔로몬 부호⁠(Reed–Solomon code)⁠는 데이터 k개를 다항식⁠(polynomial)⁠의 계수로 보고, 그 다항식의 값 n개(n > k)를 보냅니다. 차수가 k − 1 이하인 서로 다른 두 다항식은 많아야 k − 1곳에서만 값이 같으니, 두 부호어는 적어도 n − k + 1자리에서 다릅니다(d = n − k + 1). 그래서 어느 값이 망가졌는지 몰라도 $\lfloor (n-k)/2 \rfloor$개까지는 고칠 수 있습니다. 그래서 CD와 DVD, QR 코드, 먼 우주 탐사선의 통신에 쓰였습니다.

이어지는 곳. 받은 비트열을 가장 가까운 부호어로 읽는 것은 부호어들로 나눈 보로노이 영역⁠(Voronoi region)⁠ 가운데 어디에 떨어졌는지 보는 것이고, 좋은 부호를 찾는 일은 고차원 공간에 공을 빽빽이 채우는 문제와 닮았습니다. 오류를 t개까지 고치려면 부호어마다 해밍 거리 t 이내의 비트열들로 이루어진 '공'이 서로 겹치지 않아야 하는데, 공을 겹치지 않게 많이 넣을수록 부호어가 많아져 전송률이 올라가기 때문입니다. 압축(원천 부호화 정리⁠(source coding theorem)⁠, 허프만 부호⁠(Huffman coding)⁠)은 쓸모없는 여분을 없애고, 오류 정정 부호는 쓸모 있는 여분을 규칙적으로 되돌려 놓습니다. 실제 통신은 이 둘을 차례로 씁니다.