오류정정

[귀뚜라미]

컴퓨터가 자료를 읽거나, 연산하거나, 저장하거나, 전송하면서 오류가 날 수가 있다. 하드디스크나 CD, DVD 등의 저장 매체도 흠집이 나거나, 자석에 가까이 하거나, 먼지가 들어가면 자료에 오류가 생길 수 있다. 먼 우주에 보낸 우주선이 보내온 자료도 태양풍 등의 영향으로 정보가 유실 혹은 변경될 수도 있다.

이런 오류를 수정하지 못한다면, CD로 음악을 듣다가 튀거나 DVD 영상이 일그러지는 일은 다반사였을 것이고, 흠집이 조금만 나도 버려야 할 것이다. 컴퓨터로 계산한 결과 역시 신뢰할 수 없었을 것이다. 또한 우주선이나 위성이 보내 온 자료가 오류가 났다고 해서, 다시 사진을 찍어서 보내달라는 요청을 할 수는 없는 것이다. 이미 시간도 지났을 것이며, 다시 보내 온 자료의 신뢰성 또한 문제가 될 것이기 때문이다. 따라서 오류가 발생한 자료를 검출하고 수정할 방법이 필요하다.

흠집이 난 CD, 이런 CD도 문제가 없는 경우가 많다. <사진: 김덕화>

2진수 0과 1로 디지털화한 자료를 생각해 보자. 동일한 자료를 두 번 송신하면 간단히 오류를 검출할 수 있을 것이다. 예를 들어 1001이라는 자료를 10011001로 보내자는 것이다. 앞쪽 네 자리와 뒤쪽 네 자리가 불일치하면, 오류라고 판정할 수 있을 것이다. 하지만 앞쪽 자료와 뒤쪽 자료가 불일치할 경우, 어느 자리에서 오류가 났는지는 알 수가 없다. 오류가 발생한 위치까지 알고 싶으면, 동일한 자료를 세 번 보내는 방법을 생각할 수 있다. 예를 들어, 100110001001이라는 자료가 수신됐다면, 가운데 1000은 1001을 잘못 보낸 것으로 볼 수 있고, 따라서 오류를 정정할 수 있다. 하지만, 한두 개의 오류를 검출하고 정정하기 위해 동일한 자료를 두 번, 세 번 보내는 비효율성을 감수해야 하는 것일까?

책 표지에 붙어있는 ISBN 번호

대한민국 주민등록번호 열세 자리 중 맨 끝자리는 그 앞의 열두 자리수가 올바른지 검사하는 오류 검출 부호이다. 도서마다 할당되는 ISBN(International Standard Book Numbering, 국제 도서 표준 번호)이나, 물품에 사용하는 바코드에는 모두 자료의 오류를 검출하는 부호가 붙어 있다. 이처럼 오류 검출 부호는 생활 속에 널리 자리잡고 있지만, 여기서는 오류를 검출하는 가장 고전적인 방법인 ‘배타적 논리합’(exclusive or 혹은 xor)을 이용한 방법만을 소개하기로 한다.

배타적 논리합은 ‘2를 법(法, modulo)으로 하는 덧셈’ 혹은 ‘부울 합’(Boolean sum)이라고도 부르는데, 2진수 0, 1에 대해 다음처럼 정의한 연산을 말한다.

 

덧셈 기호를 쓸 뿐이지 보통의 덧셈과는 다른 것이니까, 1+1이 2, 즉, 2진수 10이 아니라고 해서 이상하게 여길 필요는 없다. 이런 덧셈은 홀수, 짝수를 생각하면 자연스럽게 등장한다. 어떤 정수가 짝수라는 것은 2로 나눈 나머지가 0이고, 어떤 정수가 홀수라는 것은 2로 나눈 나머지가 1이다. 정수가 짝수냐 홀수냐에 따라 0과 1을 대응한 것을 그 정수의 ‘짝홀값’(패리티, parity)이라 부른다. 예를 들어 1+1은 홀수+홀수로 해석하는데, 결과는 짝수이므로 0을 대응하는 것으로 이해하자는 것이다. 앞으로 이 글에서의 2진수의 덧셈은 모두 배타적 논리합을 가리키겠다.

한편 2진수 자료에서 각 자리수의 배타적 논리합을 구한 것을 ‘검사합’(체크섬, checksum)이라 부른다. 물론 이 값은 자료 내에 1이 홀수 개 있는지, 짝수 개 있는지로 결정할 수 있다. 아무튼 2진수 자료에 검사합을 덧붙인 부호를 생각하면 오류를 검출할 수 있다. 예를 들어 1001의 검사합은 1+0+0+1=0이므로, 맨 끝에 0을 덧붙여 10010이라는 자료로 변환하자는 것이다. 만일 이런 식으로 변환한 자료가 10011이라면, 검사합 1+0+0+1=0이 오류 검출 부호 1과 다르므로 오류임을 금방 알 수 있을 것이다. 이렇게 검사합을 이용하여 오류를 검출하는 방법을 ‘짝홀 검사법’(패리티 검사, parity check)이라고 부르는데, 동일한 자료를 두 번 보낸 것과 비교하면 대단히 효율적인 오류 검사법이다.

맨해튼 계획에도 참여했던 수학자 해밍(Richard Wesley Hamming, 1915-1998)은 종전 후 벨 연구소에서 일했다. 당시 컴퓨터는 입력 오류가 나는 일이 적지 않았는데, 오류가 났음을 컴퓨터가 알려주면 작업자가 찾아서 교정해 주곤 했다고 한다. 연구소 컴퓨터를 주말에만 쓸 수 있었던 해밍이 다음 주 월요일에 출근해서 결과를 확인하려고 하면, 오류가 나서 컴퓨터가 멈춰 있는 일이 자주 있었다고 한다. 겨우 오류 한두 개 때문에 다시 입력하고, 기도하는 심정으로 결과를 기다려야 하는 일에 진절머리가 난 해밍은 ‘오류를 검출할 수 있다면서, 왜 못 고치는 거지?’라는 생각을 하고 연구에 착수, 1950년 ‘오류 검출 및 오류 정정 부호(code)’라는 논문을 세상에 발표하였다.

해밍이 논문에서 제시한 부호를 해밍 부호라 부르는데, 2진법의 원리를 한껏 이용한 부호이다. 좀더 일반적인 해밍 부호를 소개하는 것도 어렵지는 않지만, 가장 간단한 해밍 [7, 4] 부호만 설명하겠다. [7, 4] 해밍 부호란 7자리 수 중 파란색으로 쓴 4자리 c₃c₅c₆c₇에 원하는 정보를 담고, 아래 표에서와 같이 빨간색으로 계산한  c₁c₂c₄를 끼워 넣은 부호를 말한다.

예를 들어 보내고 싶은 메시지가 1001이었다면, c₃=1, c₅=0,c₆=0, c₇=1이다.

위 그림 처럼 계산되므로, 1001은 0011001로 만들어질 것이다.

해밍 부호를 계산하는 세 식  c₁=c₃+c₅+c₇, c₂=c₃+c₆+c₇, c₄=c₅+c₆+c₇에 나오는 첨자들은 어떤 패턴인지 아래의 오일러-벤(Venn) 다이어그램을 들여다보면 도움이 될 것 같다. 큰 동그라미 세 개에 주목하여 아하 소리가 날 때까지 바라보길 바란다.

아무튼 이렇게 부호를 만들면, 일곱 자리 중 한 자리가 오류가 나더라도 원래 정보였던 1001을 복구할 수 있다! 과연 어떻게 복구할 수 있다는 것일까?

이제부터 일곱 자리 중에 한 자리 정도는 오류가 날 수 있다고 가정하자. 예를 들어 해밍 부호가 1010010이라면, 원래 정보는 무엇이었을까? 아래 세 식을 계산해보자

그러면, 식  c₄=c₅+c₆+c₇만 틀리다. 이 식에만 영향을 주는 것은   c₄뿐이므로,  c₄가 잘못이며 필요한 정보 1010 자체는 제대로임을 알 수 있다. 예를들어, 1110010이라면 어떨까? 이 때는 두 식  c₂=c₃+c₆+c₇, c₄=c₅+c₆+c₇가 틀렸는데, 두 식에만 영향을 주는 것은 c₆뿐이다. 물론c₇도 이 두 식에 영향을 주지만, 이 경우  c₁=c₃+c₅+c₇에도 영향을 주어야 하기 때문이다. 따라서 c₆이 잘못이며, 원래 정보는 1010이 아니라 1000이라고 정정할 수 있다. 곰곰이 생각하면 2+4=6으로 바로 계산할 수 있는데, 2진수만이 부릴 수 있는 마법이다. 한편 세식이 모두 맞지 않다면, c₇이 오류였을 것이다. 이처럼, 해밍 부호를 사용하면 7자리 중 1자리만 오류가 난다면 정확하게 정정할 수 있다.

DVD와 같은 매체는 긁힐 경우 오류가 집중하는 경향이 있으므로, 한 개의 오류만을 정정하는 부호로는 부족하다. 위성에서 보내온 사진 역시 여러 개의 오류를 정정해주는 부호가 필요하다. 일반적인 해밍 부호를 쓰면 오류를 여러 개 정정할 수 있지만, 더 효율적인 부호도 많이 알려져 있다. 대표적인 부호로는 리드(Irving S. Reed, 1923- )와 솔로몬(Gustav Solomon, 1930-1996)이 갈루아 체(Galois field) 위에서의 다항식을 이용하여 1960년에 개발한 리드-솔로몬 부호가 있다. 이 부호는 우주 탐사선 보이저의 디지털 영상 및 하드 디스크, 컴팩트 디스크와 DVD 등의 디지털 자료의 부호화에 사용하며, 디지털 방송 및 닌텐도 등에도 사용한다. 디지털 기술이 발달하기 한참 전에 이미 부호가 만들어져 있었다는 것이 흥미로운데, 개발하고 싶다고 갑자기 첨단 과학이 나오는 것이 아니라 기초 학문이 튼튼해야 나온다는 좋은 사례이기도 하다. 온고지신이다.

보이저 2호가 보낸 토상의 자외선 사진 <출처: NASA>

3세대 이동통신이라 불리는 IMT-2000에는 1993년에 개발된 터보 부호를 탑재한다고 한다. 이처럼 디지털, 첨단 과학에는 오류 정정 부호 이론을 포함한 많은 정보 이론이 쓰인다. 군론 및 대수학, 구 쌓기 및 격자 이론, 조합론, 수론, 유한 기하학, 대수 기하학, 확률론 등 다양한 수학 분야가 관련돼 있다는 것만 언급해 두고, 훗날 소개할 기회를 엿보기로 하자.

글 정경훈 / 서울대 기초교육원 강의교수

서울대학교 수학과에서 학사, 석사, 박사를 받고, 포항공대, 연세대, 위스콘신대, 서울대에서 박사후 과정을 밟았다. 현재 서울대 기초교육원 강의교수이다.