오류정정부호(error correcting codes)

서울대학교 수학과 조교수 김명환

2차 세계대전 이후 통신수단의 급속한 발달에 따라, 정보를 신속하고 정확하게, 그리고 경제적으로 전달하기 위한 연구가 활발해 짐으로써, 부호이론(coding theory), 혹은, 보다 넓은 의미의 정보이론(information theory)은 수학의 가장 중요한 응용분야의 하나로 각광을 받고 있다. 1948년 미국의 수학자 샤논(Shanon)이 처음 이 분야의 연구를 개척한 이래, 부호이론은 이제 물리, 화학, 생물, 공학 등의 학문 분야 뿐만 아니라 인공위성과의 통신, 컴퓨터, 컴팩트 디스크 등 첨단산업기술에 까지 광범위하게 응용되고 있다.

쉬운 이해를 위하여 여기서는 2-진 부호(binary code)에 대하여만 다루기로 하자. 부호란 간단히 말하면 보내고자 하는 정보를 0 과 1 로 이루어진 수자열로 바꾸어 놓은 것이다. 예를 들어서, ㄱ,ㄴ,ㄷ,ㄹ,...,ㅎ,ㅏ,ㅑ,ㅓ,ㅕ,...,ㅣ 등에 서로 다른 수자열을 하나씩 대응시킨다고 하자. (1,0,0,0,1), (1,1,0,1,0) 등과 같이, 0 과 1 을 다섯개(이 개수를 부호의 길이라고 부름) 늘어 놓으면 32 개의 서로 다른 수자열을 만들 수 있으므로 한글자모 24 글자에 하나씩 대응시키고도 8 개의 수자열이 남는다. 남는 수자열에는 마침표, 쉼표, 또는 빈칸 등을 대응시킬 수도 있을 것이다. 이제 보내고 싶은 문장을 부호화하여 전송하였다고 하자. 그런데 입력잘못이나 전파방해등의 여러 가지 원인으로 여기 저기서 0 과 1 이 뒤바뀌는 오류가 발생할 가능성이 상존한다는 것이 문제가 된다. 때로는 엉뚱한 문장으로 변할수도 있을 것이다. 이럴때, 같은 수자열을 두세번씩 되풀이하여 전송한다든가 무의미한 수자열을 삽입한다든가 하여, 전송하고자 하는 수자열에서 오류가 생길 확률을 줄이는 방법도 있으나, 보다 근본적인 해결책으로 제안된 것이 스스로 오류를 발견하고 정정하는 기능을 가진 부호이다.

오류정정부호에서는 우선 부호의 길이를 크게 잡아서 서로 다른 수자열의 개수가 충분히 많아지도록 한다. 그런 다음 수자열의 일부만을 문자에 대응시키고 나머지 수자열들은 무의미한 수자열로 남겨 두는 것이다. 이제 만약 문자에 대응되지 않은 수자열이 수신되었다면, 그것은 부호의 전송과정에서 오류가 발생하였다는 증거가 된다. 하지만 오류가 발생하여 0 과 1 이 뒤바뀐 결과 다른 문 자에 대응된 수자열로 나타나면 어떻게 하는가? 이러한 가능성을 완전히 제거할 수는 없겠지만 이러한 일이 일어날 확률을 무시해도 좋을 정도로 줄일 수는 있다. 예를 들어 문자에 대응된 수자열들은 서로 비슷하지 않도록 하는 것이다. (부호의 길이를 엄청나게 크게 하면 이것은 간단히 해결된다. 그러나 시간적, 경제적, 기술적인 제한을 고려하면 이것도 매우 복잡한 수학문제가 된다.) 한편, 이렇게 발견된 오류를 정정하는 기능은 어떻게 부여하는가?  문자가 대응되지 않은 수자열 각각에 대하여 그것과 어느 정도 이상 비슷한 수자열 중에서 문자와 대응된 것이 하나만 존재하도록 할 수 있다면, 문자가 대응되지 않은 수자열이 나타났을 때 그것이 어떤 수자열의 오류인지는 자명해진다. 여기서 어느 정도로 표현한 그 정도가 바로 부호가 스스로 알아서 정정할 수 있는 오류의 범위가 되며, 그 정도 이상의 악성 오류는 정정할 수 없으므로 사용하는 통신수단과 시간적, 경제적, 기술적인 제한을 고려하여 그 정도를 조절한다. 간단하게 설명하였지만 실은 이 부분이 수학적으로 가장 어려운 부분으로서 정수론, 대수학, 확률론, 조합수학등의 여러 분야가 밀접하게 관련되어 있다.

이러한 부호의 종류로는 해밍(Hamming)부호와 해밍부호가 일반화된 BCH(Bose- Chaudhuri-Hocquenghem)부호 등이 있으며, 최근 크게 각광을 받고 있는 RS (Reed-Solomon)부호도 BCH부호의 일종이다. 그 외에도, 부호의 길이가 길 때 유용한 져스트슨(Justesen)부호, BCH부호를 변형시킨 RM(Reed-Muller)부호, 대수곡선을 이용한 가파(Goppa)부호 등이 있다. 한편,  위에서 소개한 것과는 다른 원리로 만들어진 부호로서 많은 문자를 수자열과 대응시킬 수 있는 장점을 가진 비선형(nonlinear)부호, 연속적으로 발생하는 오류를 정정하는데 편리한 나선(convolutional)부호 등이 개발되어 사용되고 있다.

조선일보 1993년 8월 31일, 23면