오류 정정 부호 해설

완벽한 채널은 없습니다. 우주선(宇宙線)은 메모리의 비트를 뒤집고, 흠집은 디스크의 일부를 지우며, 무선 신호는 약해집니다. 디지털 시스템은 운에 맡기는 대신 영리한 방식으로 중복을 더해, 일부가 잘못 도착해도 수신자가 무엇이 보내졌는지 알아낼 수 있게 합니다. 1940년대 후반에 시작된 이 부호들의 수학은 우리가 저장하거나 보내는 거의 모든 비트를 조용히 지키고 있습니다.

해밍 부호어의 일곱 비트가 담긴 서로 겹친 세 원. 패리티 검사에 실패한 원 하나가 강조되어 있다
해밍 부호어의 일곱 비트가 담긴 서로 겹친 세 원. 패리티 검사에 실패한 원 하나가 강조되어 있다

패리티로 오류 검출하기

가장 단순한 보호는 패리티 비트 하나입니다. 1의 총개수가 짝수가 되도록 1이나 0을 더하는 것입니다. 도중에 비트 하나가 뒤집히면 개수가 홀수가 되어 수신자는 무언가 잘못되었음을 압니다. 패리티로는 어느 비트가 틀렸는지 알 수 없고, 두 번의 뒤집힘은 서로 상쇄되어 눈에 띄지 않지만, 비용이 적게 들어 수십 년 동안 메모리와 직렬 링크에 쓰였습니다. 하지만 오류를 검출하는 것은 일의 절반일 뿐입니다. 그다음에는 데이터를 다시 보내야 하기 때문입니다.

반복으로 정정하기

다시 요청하지 않고 오류를 정정하려면, 수신자에게는 다수결로 오류를 이길 만큼의 중복이 필요합니다. 모든 비트를 000이나 111처럼 세 번씩 보내면 수신자는 다수결을 따를 수 있어, 세 개 묶음 안의 뒤집힘 하나가 정정됩니다. 대가는 큽니다. 데이터 비트 하나에 세 비트가 들고, 같은 묶음 안에서 두 번 뒤집히면 여전히 오류가 이깁니다. 부호 이론을 출발시킨 질문은 이보다 더 잘할 수 있느냐는 것이었습니다.

해밍의 부호

1947년 리처드 해밍은 벨 연구소에서 천공 카드로 프로그램을 읽는 릴레이 컴퓨터로 일하고 있었습니다. 이 컴퓨터는 주말에 오류를 발견하면 그냥 멈춰 버렸고, 해밍은 월요일에 돌아와 헛되이 날아간 작업을 마주해야 했습니다. 기계가 오류를 검출할 수 있다면 왜 그 위치를 찾아 정정하지는 못하는가, 하고 그는 물었습니다. 1950년에 발표된 그의 답은 데이터 비트 4개를 7비트로 보내는 것입니다. 1, 2, 4번 위치에 있는 세 패리티 비트는 서로 겹치는 각기 다른 위치 묶음을 검사하며, 이 묶음은 어떤 단일 오류든 고유한 검사 조합을 깨뜨리도록 골라져 있습니다.

신드롬

수신자는 세 검사를 다시 계산합니다. 모두 통과하면 단어를 받아들입니다. 일부가 실패하면, 실패한 검사를 검사 4를 가장 높은 자리로 하여 이진 숫자로 적으면 1부터 7까지의 수가 나옵니다. 이것이 신드롬이며, 정확히 뒤집힌 비트의 위치입니다. 그 비트를 다시 뒤집으면 부호어가 복원됩니다. 이 요령이 통하는 것은 각 위치의 이진 전개가 그 위치가 속한 검사들을 나열하도록 번호가 매겨져 있기 때문이며, 이 부호를 서로 겹친 세 원으로 그리면 아주 깔끔해 보이는 것도 그래서입니다.

해밍 거리

두 단어 사이의 해밍 거리는 서로 다른 위치의 개수입니다. (7,4) 부호에서는 어떤 두 부호어도 적어도 3만큼 떨어져 있습니다. 오류가 하나 있는 단어는 보낸 부호어와는 여전히 거리가 1이고 다른 모든 부호어와는 적어도 2만큼 떨어져 있으므로, 가장 가까운 부호어로 복호하면 오류가 정정됩니다. 일반적으로 부호어끼리 적어도 d만큼 떨어진 부호는 d − 1개의 오류를 검출하고 (d − 1)/2개(내림)의 오류를 정정합니다. 전체 패리티 비트를 더하면 거리가 4로 늘어나, 오류 하나를 정정하고 둘을 검출하는 확장 부호가 됩니다.

섀넌 한계

해밍의 논문보다 2년 앞선 1948년, 클로드 섀넌은 놀라운 정리를 증명했습니다. 모든 잡음 채널에는 용량이 있으며, 충분히 긴 부호를 쓰면 그 용량보다 낮은 어떤 속도로든 원하는 만큼 적은 오류로 데이터를 보낼 수 있고, 용량을 넘어서면 오류를 피할 수 없다는 것입니다. 섀넌은 그런 부호가 존재한다는 것은 보였지만 어떻게 만드는지는 보이지 않았습니다. 그의 한계에 가까운 실용적인 부호를 찾는 데는 1960년의 리드-솔로몬 부호에서 1993년의 터보 부호, 그리고 저밀도 패리티 검사 부호의 재발견에 이르기까지 반세기가 걸렸습니다.

클로드 섀넌. 1948년 벨 연구소에서 메시지가 담는 정보량을 정밀히 정의하고 비트로 측정했다.
클로드 섀넌. 1948년 벨 연구소에서 메시지가 담는 정보량을 정밀히 정의하고 비트로 측정했다.

우리 주변의 부호

리드-솔로몬 부호 덕분에 CD는 흠집이 있어도 재생되고, QR 코드는 심벌의 최대 30%가 손상되어도 읽힙니다. 서버 메모리는 확장 해밍 부호를 써서 우주선으로 인한 단일 비트 뒤집힘을 고칩니다. 보이저호가 찍은 외행성 사진은 골레이 부호와 이후 리드-솔로몬 부호로 보호되었고, 5G와 Wi-Fi의 LDPC 부호와 폴라 부호는 채널이 허용하는 거의 모든 비트를 짜냅니다. 책의 바코드와 은행 계좌 번호의 마지막 숫자조차 간단한 오류 검출 부호입니다.

직접 탐구하기

오류 정정 부호 시뮬레이터를 열어 임의의 데이터 비트 네 개를 해밍 (7,4) 부호로 부호화하고, 원이나 줄에서 비트를 클릭해 뒤집은 뒤, 복호기가 복구하기 전에 실패한 원들과 신드롬이 오류를 가리키는 모습을 지켜보세요. 추가 패리티 비트를 켜면 이중 오류가 검출되는 것을 볼 수 있고, 메시지를 잡음 채널로 보내면 부호를 쓸 때와 쓰지 않을 때 도착하는 내용을 비교할 수 있습니다.

자주 묻는 질문

오류 검출과 오류 정정은 어떻게 다른가요?

검출은 수신자에게 무언가 잘못되었다는 것만 알려 주므로, 수신자는 데이터를 다시 요청해야 합니다. 패리티 비트나 체크섬이 이 일을 합니다. 정정은 수신자가 요청하지 않고도 원래 데이터를 재구성하게 해 주며, 그러려면 더 많은 중복이 필요합니다. 수백만 킬로미터 떨어진 우주 탐사선이나 DVD처럼 다시 요청할 수 없는 시스템은 정정에 의존합니다.

그냥 모든 것을 두 번 보내면 안 되나요?

사본이 두 개면 오류가 났다는 것은 알 수 있지만 어느 사본이 맞는지는 알 수 없고, 비용도 두 배가 됩니다. 사본이 세 개면 다수결이 가능하지만 비용은 세 배입니다. 해밍의 부호는 두 배가 안 되는 비트로 일곱 비트 블록마다 단일 오류를 정정하며, 더 긴 부호는 훨씬 더 낫습니다.

리처드 해밍은 누구였나요?

미국의 수학자(1915~1998)로, 맨해튼 프로젝트에 참여한 뒤 벨 연구소에서 30년 동안 일했습니다. 그의 부호 외에도 신호 처리의 해밍 창, 해밍 거리, 그리고 강연 「You and Your Research(당신과 당신의 연구)」로 알려져 있습니다. 1968년에 튜링상을 받았습니다.

부호는 오류를 몇 개든 정정할 수 있나요?

중복이 충분할 때만 가능합니다. 부호는 블록당 최대 (d − 1)/2개의 오류를 정정할 수 있으며, 여기서 d는 부호어 사이의 최소 거리입니다. 검사 비트가 더 많은 긴 부호일수록 더 큰 d에 이릅니다. 섀넌의 정리가 궁극적인 한계를 정합니다. 어떤 부호도 채널의 용량을 넘어설 수 없습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

오류 정정 부호 시뮬레이터 열기