코딩이론, 0과 1만으로 ‘소통의 오류’를 해결하다
인류 생존의 필요에서 출현한 셈과 연산의 개념은 그 역사가 3만 년이 넘는다.
수학은 보이는 세계를 넘어 추상화의 단계에 이르렀고 인간은 물리적 세계의 이면에 있는 질서를 이해
하기 시작했다.
그렇게 표현된 질서는 종종 조화와 우아함을 갖춘 것으로 보였고 이는 많은 지적 작업의 동력이 되곤
했다.
하지만 세상은 여전히 완전하지 않다.
우주로 간 화성탐사선은 끊임없이 지구로 영상신호를 보내지만 태양의 자기장과 지구의 오존층에 이리
치이고 저리 치여서 엉뚱하게 변질된 신호가 지구에 도착하지 않는가.
원자의 세계는 뉴턴역학의 결정론이 아니라 양자역학의 확률적 개념으로 접근해야 한다는 사실에
아인슈타인은 절망하며 “신은 주사위 놀음을 하지 않는다”고 하지 않았던가.
프랙털의 개념을 발견한 망델브로는 불규칙과 무질서가 자연의 본질에 더 가깝다고 결론내리지 않았는가.
 |
세상은 불완전하고 무작위하고 무질서하다.
오늘날 미술과 건축에도 사용되곤 하는 프랙털의 창시자는 다음과 같이 말했다:
구름은 동그랗지 않고, 산은 원뿔 모양이 아니며 해안선은 원형이 아니고 나무껍질은 부드럽지 않고 번개는 직선으로 움직이지 않는다.
― 브누아 망델브로, ‘자연 속의 프랙털 기하학’ 중에서
인간은 완전한 것을 다루는 깔끔한 수학만이 아니라, 불완전한 세상을 다루는 수학도 생각해야 했다.
그래서 통신 과정에서도 오류가 생기는 불완전한 세상에서 이걸 해결해 주는 코딩이론이 탄생했다.
무작위성(randomeness)을 주요 연구 대상으로 하는 확률론이 탄생했고 매끄럽지 않은 세상을 다루는 프랙털 기하학이 출현했는데 이 둘은 다음 기회에 다루기로
하자.
ㆍ소통의 수학, 코딩이론
지구 바로 옆 행성인 화성 표면 모습도 제대로 볼 수 없는 현실에 좌절만 할 수는 없다.
변질된 신호를 해석해 원래 보내졌을 신호를 추측해야 한다.
화성의 표면과 우주 공간의 영상을 복원해야 한다.
해결의 실마리는 모든 소통과 통신 과정에서 오류가 발생한다는 각성에서 출발한다.
전화, 이메일, 문자 등을 포함한 의사소통 및 정보교환 과정에서 많은 실수와 착오가 발생한다.
코끼리라고 말했는데 왜 캥거루로 전달됐을까.
ㆍ남자는 동그라미를 얘기하는데 여자는 네모라고 알아듣는다
연인 사이에도 뜻이 다르게 전달돼 크고 작은 문제가 생기곤 한다.
남자는 동그라미를 얘기하고 있는데 여자는 네모라고 알아듣는다.
게다가 제3자가 끼어들어 말을 전달하면서 오해가 커지곤 한다.
이런 오해로 역사가 바뀐 예도 많다.
조선의 소현세자는 청나라에 볼모로 끌려간 비운의 왕자다.
타국에서 지내면서 서양 문물을 받아들이고 상재에 능해 거부가 됐으며 노예로 끌려온 많은 조선인을 돈을 주고 해방시킨 영특한 왕자였다.
오랜 볼모 생활을 마치고 그리운 고국 땅으로 돌아왔지만 그의 영특함과 청나라와의 돈독한 관계 때문에 아버지인 인조로부터 반정의 의심을 사서 결국 독살됐다는
설이 있다.
실록에도 독살을 시사하는 표현이 있는데,그가 부왕에게 뭐라고 하든 의심이 깊던 아버지는 바뀐 메시지만 접수하는 상황이었던 것이다.
현대의 용어로는 통신채널의 에러율(error rate)이 극단적으로 높은 경우로 볼 수 있다.
인간사에서 일어나는 이런 일은 디지털 통신에서도 일어난다.
잡음 때문에 0이 1로 바뀌거나 1이 0으로 바뀌곤 한다.
“아니오”라는 메시지를 받아도 여러 정황을 고려해“예”인지“아니오”인지 추측하고 자동으로 교정까지 하는 수학이론이 바로 코딩이론이다.
가히 소통의 이론이라 할 만하다.
코딩이론은 클라우드 섀넌이 1948년 출간한‘통신의 수학 이론’이라는 논문에서 처음 제안됐다.
현대 정보이론의 출발지라고 할 만한 이 논문에는,컴퓨터가 저장할 수 있는 데이터의 최소 단위를 말하는 용어인 비트(bit)도 등장한다.
섀넌이 binary digit의 줄임말로 처음 사용한 이 단어는 이제 현대인의 일상용어가 됐다.
리처드 도킨스는 책 ‘악마의 사도’에서 섀넌을 가리켜 “정보에 대한 학문적 개념을 정한 학자”라고 평가했다.
ㆍ사진을 보내는 방법
화성탐사선은 화성의 사진을 찍어서 지구로 전송한다.
사진을 전송한다는 말은 무슨 뜻일까.
쉬운 예로, 흑백 사진 또는 그레이스케일(greyscale) 사진을 가족에게 보내려면 일단 잘게 쪼갠다.
예컨대 가로로 800개 세로로 600개, 즉 800×600으로 쪼개는데 여기서 1×1로 만들어지는 사각형을 픽셀(pixel·그림 1)이라고 한다.
800×600사진은 48만 개 픽셀로 이뤄지는 직사각형인데 흔히 Super-VGA 사진이라고 한다.
요즘은 10메가 픽셀(1000만 개 픽셀 즉 10000×1000 사진) 이상의 고해상도 사진도 흔하지만 전에는 SVGA급 사진이 많이 사용됐다.
먼저 한 픽셀의 밝기를 0에서 255까지 256개로 구분한다.
0은 검은색, 255는 흰색을 나타낸다.(그림 2)
이제 첫째 행의 왼쪽부터 각 픽셀의 밝기를 체크한다.
한 행이 끝나면 두 번째 행으로 넘어간다.
픽셀마다 어떤 것은 2, 어떤 것은 10 또는 255 등으로 밝기가 모두 다를 것이다.
밝기를 쭉 나열하면 특정 수열이 나온다.
사진을 보낸다는 의미는 이 수열을 보낸다는 뜻이다.
받는 사람이 이 수열을 다시 밝기로 고쳐서 각 픽셀을 그리면, 원래 보낸 그림이 완벽하게 복원된다.
숫자는 이진법으로 바꿔서 보내야 전기적으로 보내기가 용이하기 때문에 10010000, …,
이런 식으로 바꿔서 보내야 한다.
256이면 28이므로,8비트,즉 2진법으로 여덟 자리의 숫자가 필요하다.
결국 보내는 건 많은 수의 0과 1인데 SVGA 사진 하나를 보내려면 8×800×600, 즉 384만 개의 0 또는 1을 보내야 한다.
컬러 사진을 보내는 것도 다를 게 없다.
각 픽셀에 밝기가 아니라, 빨강-초록-파랑(RGB)의 비율을 나타내는 세 개의 숫자를 할당하고 보내는 것만 다르다.
물론 3배 더 많은 숫자를 보내야 하니까 컬러 사진을 보내는 것은 더 느리다.
ㆍ오류의 탐지와 교정
어떤 신호든 에러에서 자유로울 수 없다.
0이 1로, 1이 0으로 바뀌는 일이 곧잘 발생한다.
오류를 잡아내려면 한 자리를 더 쓰면 된다.
즉, 0111이라는 수가 있으면 오른쪽에 숫자 하나를 더 붙이는 것이다.
이때 규칙은 각 자리의 숫자들을 다 더해서 무조건 짝수가 돼야 한다.
0111이라는 숫자엔 1을 하나 더 붙이면 되고, 0110이라면 0을 붙이면 된다.
마지막에 하나 덧붙인 숫자는 아무 정보도 없이 그냥 하나를 더한 것이어서 ‘되풀이 비트’라고도 한다.
원래 4자리만 보내면 되는데 의미도 없는 비트를 하나 더 붙여서 전송 속도를 늦추는 셈이다.
보내고 싶은 메시지가 1011이라면 10111을 보내게 된다.
그런데 통신 중에 에러가 생겨서 10011로 전송됐다면 수신자는 짝수가 아닌 메시지를 보고 에러가 생겼음을 눈치챈다.
전송 속도가 느려진 대신에, 하나의 비트에 생긴 에러는 100% 탐지할 수 있게 됐다.
두 개의 비트에 에러가 나면 이 방법으로는 탐지할 수 없는데, 홀짝의 개념만 쓴 것이니 특별히 수학이라고 할 만한 것도 없다.
하지만 이것을 더 확장하면 2∼3개의 에러도 탐지할 수 있고, 심지어 교정할 수도 있다.
이때부터는 조금 더 깊이 있는 수학이 필요하다.
이제 규칙을 바꿔, 0은 무조건 000으로 바꾸고 1은 111로 바꾸자.
1011이라는 신호를 보내려면 훨씬 긴 111000111111을 보내야 하니 쓸데없이 전송이 느려지고 번거롭다.
그런데 여기에 근사한 아이디어가 숨어 있다.
누군가가 보낸 메시지가 101000으로 왔다면, 에러가 생긴 게 분명하다. 전송 과정에서 어떤 교란이 일어나 앞자리의 101에 에러가 생겼다.
에러를 탐지할 수 있을 뿐 아니라, 원래 신호를 추측해볼 수도 있다.
확률적으로 아마도 111000이었을 것이고, 원래 전송된 신호는 10이었을 거라고 추측하는 것이다. 따라서 자동으로 10으로 교정한다.
이런 식으로 에러가 자동 교정되려면 물론 비싼 대가를 치러야 한다.
10만 비트만 보낼 것을 30만 비트를 보내야 하니까.
여기서 수학자의 역할은, 조금 더 적게 보내면서도 여전히 에러를 자동으로 교정하는 방법을 찾는 것이다.
이러한 노력이 발전해서 현대의 코딩이론이 만들어졌고 이제는 휴대전화나 컴퓨터 통신에 필수불가결한 요소가 됐다.
세상은 불완전하다. 하지만 이에 대처하는 수학은 더 흥미롭게 진화하는 중이다.
☞ Munhwa ☜ ■ 박형주 포스텍 교수
草浮
印萍
|