비터비 알고리즘으로 모든 휴대전화가 자체 신호를 복호화하게 되다

무선 링크를 통한 디지털 통신은 안테나가 수신하는 비트를 손상시킬 수 있는 잡음과의 싸움이다. 명백한 해결책은 오류 정정 부호를 추가하는 것이지만, 이를 복호화하려면 잡음이 섞인 수신 스트림으로부터 실제로 어떤 메시지가 전송되었는지 알아내는 방법이 필요하다.

비터비의 1967년 알고리즘이 바로 그 일을 했다. 길쌈 부호기(컨벌루션 인코더)는 송신기가 유한한 상태 집합을 거쳐 이동하도록 제약하며, 수신기는 그 상태들의 트렐리스를 유지한다. 각 단계에서 각 상태로 들어오는 가장 저렴한 경로만 유지하므로, 끝에 이르면 각 비트를 독립적으로 선택하는 대신 가장 가능성 높은 단일 메시지를 찾아낸다.

실용적이고 짧은 구속장 부호를 작동 가능하게 함으로써, 이 알고리즘은 순방향 오류 정정을 실제 무선기에 배치할 수 있을 만큼 저렴하게 만들었다. 그것은 막연한 '메시지가 무엇이었나?'라는 질문을 깔끔한 동적 프로그래밍 탐색으로 바꾸었으며, 현재는 배경 잡음으로부터 음성과 데이터를 분리하는 데 사용된다.

가장 가능성 높은 숨겨진 상태 시퀀스를 선택한다

각 상태로 들어오는 단일 최저 비용 경로만 유지하면 탐색 시간이 메시지 길이에 선형이 된다.

비트별 추측 없이 잡음이 섞인 데이터로부터 최대 가능도 시퀀스를 복원한다.

길쌈 부호는 이런 방식으로 복호화할 때만 실제 오류 정정 능력을 얻는다.

신호가 너무 잡음이 많아 직접 읽을 수 없을 때, 그 신호가 유래했을 수 있는 가장 가능성 높은 단일 시퀀스를 재구성하라. 당신이 추가한 구조가 그 탐색을 거의 수고 없이 만들어 준다.

비터비 알고리즘은 전 세계 대다수 휴대전화와 위성 수신기, 자기 기록, 음성 인식, DNA 분석에 사용된다. 비터비는 이후 1985년 퀄컴을 공동 창업했으며, 이 알고리즘은 CDMA와 디지털 셀룰러 전화 통신이 작동 가능하게 되는 데 기여했다.