비터비 복호 알고리즘 (Viterbi Decoding Algorithm)
쉽게 풀면
비터비 알고리즘은 미로 속에서 목적지까지 갈 수 있는 수많은 경로 중 가장 그럴듯한 하나를 찾아내는 과정에 비유할 수 있습니다. 매 갈림길마다 모든 경로를 일일이 다 따라가 보는 대신, 각 지점까지 가장 유력한 경로만 남기고 나머지는 버리는 방식으로 계산량을 크게 줄입니다. 이렇게 하면 전체 경우의 수를 다 살펴보지 않고도 가장 가능성 높은 원래의 비트열을 효율적으로 찾아낼 수 있습니다.
왜 중요한가
길쌈부호처럼 트렐리스 구조를 갖는 부호는 이론적으로 모든 가능한 경로를 비교해야 최적의 복호 결과를 얻을 수 있는데, 비터비 알고리즘은 이를 훨씬 적은 계산으로 수행할 수 있게 해주어 실용적인 오류정정 시스템 구현을 가능하게 한 핵심 알고리즘으로 다뤄집니다. 비터비 알고리즘은 통신 분야뿐 아니라 은닉 마르코프 모델에서 가장 가능성 높은 상태열을 찾는 문제 등 트렐리스 형태로 표현 가능한 다양한 최적화 문제에도 동일한 원리로 응용됩니다.
논문에서는 이렇게 쓰입니다
수신 신호의 세부 신뢰도까지 활용하는 복호 방식이 단순 판정 방식보다 더 나은 결과를 냈다는 뜻입니다.
과거 경로를 얼마나 오래 기억할지 조절해 처리 속도와 정확도 사이의 절충점을 찾았다는 의미입니다.
조금 더 깊게 보면
비터비 알고리즘은 트렐리스의 각 상태마다 지금까지의 누적 경로 거리(메트릭)를 계산해 저장하고, 여러 경로가 같은 상태로 모일 때 가장 유력한 경로 하나만 남기는 생존 경로 선택 과정을 반복합니다. 신호의 세부 값을 그대로 활용하는 연판정 방식이 단순히 0과 1로만 판단하는 경판정 방식보다 일반적으로 더 나은 오류정정 성능을 보이는 것으로 알려져 있습니다. 비터비 복호기는 전체 수신 데이터를 다 받은 뒤 복호를 시작하는 대신, 일정 깊이만큼의 경로만 저장하고 그 이전 구간은 확정해 출력하는 방식으로 지연을 줄이는 실용적 구현이 널리 쓰입니다.
주의할 점
부호의 구속장이 커질수록 고려해야 할 상태 수가 급격히 늘어나 계산량과 메모리 요구량이 함께 증가하므로, 실시간 시스템에서는 구속장 선택 시 복잡도를 함께 고려해야 합니다.