1. 비터비 복호 방식 (비터비 알고리즘) 이란?
ㅇ 채널을 통해 수신되는 데이터들을,
- 트렐리스도의 여러 경로를 통해 탐색한 후,
- 그 중에서 가장 가능성이 높은 (최대 우도) 경로를 선택하고, (최대 우도 복호,MLD)
- 선택된 경로 상의 데이터들에 대해 오류정정을 하면서,
- 이를 복호하는 알고리즘
ㅇ 1965년도 Andrew J. Viterbi 박사가 제안한 경로 탐색 알고리즘에 따름
2. 비터비 복호 방식의 특징
ㅇ 주로, 구속장이 짧은 길쌈부호의 복호 알고리즘으로 널리 사용
- 비터비 복호의 복잡도는 구속장에 따라 지수적으로 증가하게됨
. 통상, 9 이하의 구속장을 갖는 길쌈부호의 복호에 적당
ㅇ 장단점
- 장점 : 뛰어난 복호 성능, 빠른 동작 속도, 용이한 구현, 낮은 비용, 일정한 복호 시간 등
- 단점 : 하드웨어 복잡도 큼 (특히, 구속장이 클수록)
ㅇ 최대 우도 검파 방식(Maximum Likelihood Detection/Decision)의 일종
3. 비터비 복호 알고리즘의 동작 방식
ㅇ 비터비 복호 방식은,
- 각 상태 별로 들어오는 경로를 살펴보아,
- `수신 비트열`과 `트렐리스도 상의 가능한 경로 상의 비트열`과 (메트릭 값을) 비교하여,
- 가장 가능성 있는 경로를 선정하게 됨 (이때, 오류정정도 함께 이루어짐)
ㅇ 메트릭 (Metric)
- 비교 기준이 되는 수치(파라미터)가 메트릭(Metric) 임
. 메트릭 例로는, 주로 해밍 거리가 가장 쉽게 이해됨
. 실제 메트릭은, 채널 특성 및 정합필터 출력의 양자화 방식에 따라 수치가 매겨짐
ㅇ 생존 경로 (Surviving Path)
- 각 상태별로 들어오는 경로 마다 계산된 메트릭들 중에서 가장 작은 값을 갖는 경로 선택
. 여기서 선택된 경로를 생존 경로 이라고 함
- 한편, 비교 대상이 없는 경로는 그대로 생존 경로로 놔둠
ㅇ 경로 제거
- 트렐리스도 상에서. 계산된 메트릭 보다 큰 값을 갖는 경로들은 버리게 됨
. 가능성 없는 경로를 일찍 제거하여, 복호화시의 복잡도를 줄일 수 있음 (계산량 감축)
※ 사실상, 비터비 복호 알고리즘은,
- `최대 우도` 및 `해밍 최소 거리` 메트릭를 갖는 부호어를 선택하는 것과 등가적임