비터비 복호 알고리즘 (Viterbi Decoding Algorithm)

한 줄 정의: 길쌈부호 등 트렐리스 구조로 표현되는 부호화 시스템에서, 가능한 경로 중 수신 신호와 가장 잘 맞는 경로를 효율적으로 찾아내는 최우도 복호 알고리즘입니다.

쉽게 풀면

비터비 알고리즘은 미로 속에서 목적지까지 갈 수 있는 수많은 경로 중 가장 그럴듯한 하나를 찾아내는 과정에 비유할 수 있습니다. 매 갈림길마다 모든 경로를 일일이 다 따라가 보는 대신, 각 지점까지 가장 유력한 경로만 남기고 나머지는 버리는 방식으로 계산량을 크게 줄입니다. 이렇게 하면 전체 경우의 수를 다 살펴보지 않고도 가장 가능성 높은 원래의 비트열을 효율적으로 찾아낼 수 있습니다.

왜 중요한가

길쌈부호처럼 트렐리스 구조를 갖는 부호는 이론적으로 모든 가능한 경로를 비교해야 최적의 복호 결과를 얻을 수 있는데, 비터비 알고리즘은 이를 훨씬 적은 계산으로 수행할 수 있게 해주어 실용적인 오류정정 시스템 구현을 가능하게 한 핵심 알고리즘으로 다뤄집니다.

논문에서는 이렇게 쓰입니다

"본 연구는 연판정(soft-decision) 비터비 복호기를 구현하여 경판정 방식 대비 성능 향상을 확인하였다."

수신 신호의 세부 신뢰도까지 활용하는 복호 방식이 단순 판정 방식보다 더 나은 결과를 냈다는 뜻입니다.

"제안된 시스템은 트렐리스 경로 저장 깊이를 조정하여 복호 지연과 성능 간의 균형을 맞추었다."

과거 경로를 얼마나 오래 기억할지 조절해 처리 속도와 정확도 사이의 절충점을 찾았다는 의미입니다.

조금 더 깊게 보면

비터비 알고리즘은 트렐리스의 각 상태마다 지금까지의 누적 경로 거리(메트릭)를 계산해 저장하고, 여러 경로가 같은 상태로 모일 때 가장 유력한 경로 하나만 남기는 생존 경로 선택 과정을 반복합니다. 신호의 세부 값을 그대로 활용하는 연판정 방식이 단순히 0과 1로만 판단하는 경판정 방식보다 일반적으로 더 나은 오류정정 성능을 보이는 것으로 알려져 있습니다.

주의할 점

부호의 구속장이 커질수록 고려해야 할 상태 수가 급격히 늘어나 계산량과 메모리 요구량이 함께 증가하므로, 실시간 시스템에서는 구속장 선택 시 복잡도를 함께 고려해야 합니다.