앤드루 비터비(Andrew Viterbi)
잡음 섞인 합성곱 부호(convolutional code)를 가장 그럴듯하게 푸는 비터비 알고리즘(1967)을 내놓고, 링커빗과 퀄컴을 함께 세워 디지털 이동 통신 CDMA를 이끈 이탈리아 태생의 미국 공학자.
앤드루 비터비는 1935년 이탈리아 베르가모의 유대인 집안에서 안드레아 자코모 비터비로 태어났습니다. 1938년 무솔리니 정권이 유대인을 공직과 학교에서 몰아내는 인종법을 만들자, 가족은 1939년 미국으로 건너갔습니다. 보스턴에서 자란 그는 MIT에서 전기 공학을 공부해 1957년 학사와 석사 학위를 받았고, 캘리포니아 패서디나의 제트 추진 연구소(JPL)에서 로켓과 탐사선의 원격 측정 신호를 다루는 일을 시작했습니다. 우주 경쟁이 막 시작된 때였고, 멀리서 오는 약한 신호를 잡음 속에서 되찾는 일이 그의 출발점이었습니다.
나이
1963년 서던캘리포니아 대학에서 박사 학위를 받고 UCLA에서 가르치던 그는, 1967년 4월 합성곱 부호의 오류 확률(probability)에 관한 논문을 발표했습니다. 합성곱 부호의 부호기는 몇 개의 상태를 오가며 비트를 내보내므로, 받는 쪽이 따져야 할 상태열은 시각마다 가지를 쳐서 지수적으로 불어납니다. 그는 시각마다 상태 하나당 '거기서 끝나는 가장 그럴듯한 앞길' 하나만 남기면 된다는 것을 보였습니다(위의 식). 그러나 그 자신은 이것을 오류 확률의 한계를 증명하는 도구로 여겼고, 저장 공간이 너무 들어 실용적이지 않으리라 보았습니다. 곧 데이비드 포니가 이것이 상태들의 격자 위에서 최단 경로(shortest path)를 정확히 찾는 최적의 복호기(decoder)임을 알아보았고, 짐 오무라는 이것이 벨먼의 동적 계획법(dynamic programming)이라고 지적했습니다.
그 뒤 이 알고리즘(algorithm)은 만든 사람의 예상을 넘어 퍼졌습니다. 보이저 탐사선의 신호를 지상에서 푸는 데 쓰였고, 은닉 마르코프 모델(hidden Markov model)로 소리에서 가장 그럴듯한 낱말의 줄을 찾는 음성 인식의 표준 도구가 되었으며, 품사 태깅(part-of-speech tagging)과 유전자 서열 분석에도 쓰입니다. 모두 '가장 그럴듯한 숨은 상태열'을 찾는 같은 물음이기 때문입니다.
그는 이론을 회사로 옮긴 사람이기도 합니다. 1968년 어윈 제이컵스 등과 통신 장비 회사 링커빗을 세웠고, 1985년 다시 제이컵스 등과 퀄컴을 세웠습니다. 퀄컴은 여러 사용자가 같은 주파수를 서로 다른 부호로 나누어 쓰는 CDMA 방식을 휴대전화에 내세웠고, 그 전화 속에서 합성곱 부호를 푸는 것이 비터비 복호였습니다. 이 방식을 처음 나라 규모로 상용화한 곳은 한국입니다. 1993년 CDMA를 표준으로 정한 한국은 전자통신연구원과 국내 전자 회사들이 퀄컴과 함께 개발한 끝에, 1996년 1월 인천과 부천에서 세계 첫 상용 서비스를 시작했습니다.
그는 2004년 서던캘리포니아 대학에 큰 기부를 해 그 공과대학이 그의 이름을 얻었고, 2008년 미국 국가 과학 훈장, 2010년 IEEE 명예 메달을 받았습니다.
이어지는 곳. 비터비 알고리즘(Viterbi algorithm)이 최단 경로, 구문 분석(parsing), 믿음 전파(belief propagation)와 '더하기'만 바꾼 같은 계산이라는 이야기는 「같은 계산, 다른 덧셈」에, 합성곱 부호와 보이저의 통신은 「잡음 너머로」에 있습니다. 바탕의 개념은 동적 계획법, 은닉 마르코프 모델, 오류 정정 부호(error-correcting code)에서 볼 수 있습니다.
관계.
- 영향을 받음 클로드 섀넌 — 비터비의 1967년 논문은 섀넌의 통로 부호화 정리(noisy-channel coding theorem)가 약속한 오류 확률의 한계를 합성곱 부호에서 증명하려는 것이었고, 알고리즘은 그 증명의 도구로 나왔습니다.
연표.
- 1935년 이탈리아 베르가모의 유대인 집안에서 태어나다
- 1939년 파시스트 정권의 인종법을 피해 가족과 함께 미국으로 건너가다
- 1957년 MIT에서 전기 공학 학사와 석사 학위를 받고, 제트 추진 연구소에서 일하기 시작하다
- 1963년 서던캘리포니아 대학에서 박사 학위를 받고 UCLA로 옮기다
- 1967년 합성곱 부호의 오류 한계를 다룬 논문에서 비터비 알고리즘을 내놓다
- 1968년 어윈 제이컵스 등과 링커빗을 세우다
- 1985년 제이컵스 등과 퀄컴을 세우다
- 1996년 한국에서 세계 첫 CDMA 상용 서비스가 시작되다
- 2004년 서던캘리포니아 대학 공대가 그의 기부로 비터비 공과대학이 되다
- 2008년 미국 국가 과학 훈장을 받다
- 2010년 IEEE 명예 메달을 받다
이 인물이 나오는 긴 글
이 인물을 언급하는 페이지
- 편집 거리
… 그럴듯한 경로를 앞 칸들에서 모아 오니, 편집 표를 채우는 것과 같은 동적 계획법입니다. 1967년 공학자앤드루 비터비가 제안했습니다. 긴 문서끼리는 글자를 하나하나 편집하는 대신, 각 단어가 몇 번 나오는지를 모은 벡터를 …
- 은닉 마르코프 모델
… 날마다 '오늘 이 상태에서 끝나는 최선의 날씨열'만 기억합니다. 1967년 이탈리아 태생 미국 공학자앤드루 비터비가 잡음 섞인 신호에서 오류 정정 부호를 풀려고 만든 방법입니다. 이것으로 충분한 까닭은 이렇습니다. …
- 동적 계획법
… 낱말들 뒤에 숨은 상태들의 가장 그럴듯한 줄을 찾는 은닉 마르코프 모델의 비터비 알고리즘(1967년앤드루 비터비), 무게 제한 안에서 가장 값진 물건을 고르는 배낭 문제(무게가 정수이면 물건 수 × 무게 한도 크기의 …