긁힌 CD가 여전히 재생되는 이유, 오류 정정 부호

CD 표면에 흠집이 나도 음악이 그대로 재생되는 것은 오류 정정 부호 덕분이다. 오류 정정 부호는 원래 정보에 계산으로 만든 여분의 정보를 덧붙여, 일부가 망가져도 원래 내용을 되찾을 수 있게 하는 방법이다. 같은 원리가 QR 코드, 위성 통신, 스마트폰의 무선 신호, 컴퓨터 메모리에도 쓰인다.

그냥 두 번 적으면 안 되나

가장 단순한 방법은 같은 내용을 여러 번 적는 것이다. 0을 보내야 하면 000을, 1을 보내야 하면 111을 보낸다. 받는 쪽에서 010이 왔다면 0이 두 개이니 원래는 0이었다고 판단한다. 이것을 반복 부호라 부른다.

반복 부호는 작동하지만 낭비가 심하다. 세 번 반복하면 정보 하나를 보내는 데 세 배의 공간이 든다. 게다가 한 묶음 안에서 두 개가 동시에 틀리면 엉뚱한 답을 내놓는다. 저장 공간과 전송 속도가 귀한 상황에서는 쓸 수 없는 방식이다. 수학자들의 질문은 이것이었다. 여분을 최소한으로 덧붙이면서 오류는 최대한 잡아낼 방법이 있을까.

여분의 정보는 어떻게 오류를 찾아내나

가장 쉬운 예는 패리티 비트다. 데이터에 들어 있는 1의 개수가 짝수가 되도록 끝에 0이나 1을 하나 덧붙인다. 받은 쪽에서 1의 개수가 홀수라면 어딘가 하나가 뒤집혔다는 뜻이다. 비트 하나만 더 써서 오류가 있다는 사실을 알아내는 셈이다. 다만 어디가 틀렸는지는 모른다.

1950년 리처드 해밍은 이 생각을 한 걸음 더 밀었다. 패리티 비트를 여러 개 두되, 각 패리티가 서로 다른 자리의 묶음을 감시하게 만든 것이다. 그러면 어떤 패리티들이 어긋났는지의 조합이 곧 틀린 자리의 번호가 된다. 네 자리 데이터에 세 자리 여분을 붙이는 해밍 부호는 한 자리의 오류를 찾아내 고칠 수 있다. 반복 부호가 세 배를 쓰던 일을 두 배가 안 되는 공간으로 해낸다.

여기서 중요한 개념이 해밍 거리다. 두 부호어가 몇 자리에서 다른지를 센 값이다. 쓸 수 있는 부호어끼리 서로 충분히 멀리 떨어져 있으면, 몇 자리가 틀려도 가장 가까운 부호어로 되돌릴 수 있다. 부호를 설계한다는 것은 결국 부호어들을 공간에 최대한 고르게 흩어 놓는 일이다.

방식	덧붙이는 양	할 수 있는 일
반복 부호(3회)	원래의 2배	한 자리 오류 고침, 낭비 큼
패리티 비트	1자리	오류가 있다는 사실만 앎
해밍 부호(7,4)	4자리당 3자리	한 자리 오류를 찾아 고침
리드-솔로몬 부호	설계에 따라 다름	몰려서 생긴 오류를 고침

CD의 흠집은 왜 특별히 까다롭나

해밍 부호는 오류가 여기저기 하나씩 흩어져 생길 때 잘 작동한다. 그런데 CD의 흠집은 데이터를 수천 개씩 한꺼번에 지운다. 오류가 한곳에 뭉쳐 생기는 것이다. 이런 오류를 버스트 오류라 한다.

CD는 두 가지 방법을 함께 쓴다. 하나는 리드-솔로몬 부호다. 비트 하나가 아니라 여러 비트를 묶은 기호 단위로 계산하기 때문에, 한 기호 안의 비트가 몽땅 틀려도 기호 하나의 오류로 다룬다. 다른 하나는 교차 배치, 곧 인터리빙이다. 연속된 데이터를 디스크 위에 일부러 멀리 흩어 적는다. 그러면 흠집 하나가 지우는 데이터가 원래 순서로 돌려놓았을 때 여러 묶음에 조금씩 나뉜다. 뭉친 오류를 흩어진 오류로 바꿔서 부호가 감당할 수 있게 만드는 셈이다.

그래도 고칠 수 없을 만큼 크게 망가지면 CD 플레이어는 앞뒤 소리를 이어 붙여 빈자리를 메운다. 아주 짧은 구간이라 사람 귀로는 거의 알아채지 못한다.

우주 탐사선은 어떻게 희미한 신호를 알아듣나

수십억 킬로미터 떨어진 탐사선이 보내는 신호는 지구에 닿을 무렵 잡음에 묻힐 만큼 약하다. 출력을 마음대로 키울 수도 없다. 그래서 심우주 통신은 오류 정정 부호의 성능을 극한까지 밀어붙이는 분야가 되었다. 정보 이론을 세운 클로드 섀넌은 잡음이 있는 통로라도 일정한 속도 아래에서는 오류를 원하는 만큼 줄일 수 있다는 사실을 수학적으로 보였다. 이후의 부호 연구는 그 이론적 한계에 얼마나 가까이 다가가느냐의 경쟁이었다. 오늘날의 휴대전화 통신에 쓰이는 부호들은 그 한계에 상당히 가까이 다가가 있다.

남은 과제

부호가 강해질수록 계산이 무거워진다. 오류를 많이 고칠 수 있는 부호일수록 받는 쪽에서 원래 내용을 되찾는 데 드는 계산이 늘어나고, 그만큼 전력과 시간이 든다. 배터리로 움직이는 작은 기기에서는 이 균형이 늘 고민거리다.

양자 컴퓨터는 또 다른 숙제를 던진다. 양자 상태는 들여다보는 순간 흐트러지기 때문에, 비트를 복사해 비교하는 기존 방식을 그대로 쓸 수 없다. 양자 정보를 위한 오류 정정은 활발히 연구되고 있지만, 큰 규모로 안정적으로 작동시키는 방법은 아직 완성되지 않았다.