1. 비터비 복호 방식 (비터비 알고리즘) 이란?
ㅇ 채널을 통해 수신되는 데이터들을,
- 트렐리스도의 여러 경로를 통해 탐색한 후, (경로 탐색)
- 그 중에서 가장 가능성이 높은 (최대 우도) 경로를 선택하고, (최대 우도 복호,MLD)
- 선택된 경로 상의 데이터들에 대해 오류정정을 하면서, (오류정정)
- 이를 복호하는 알고리즘 (효율적임)
ㅇ 1965년도 Andrew J. Viterbi 박사가 제안한 경로 탐색 알고리즘에 따름
2. 비터비 복호 방식의 특징
ㅇ 장단점
- 장점 : 뛰어난 복호 성능, 빠른 동작 속도, 용이한 구현, 낮은 비용, 일정한 복호 시간 등
- 단점 : 하드웨어 복잡도 큼 (특히, 구속장이 클수록)
ㅇ 주로, 구속장이 짧은 길쌈부호의 복호 알고리즘으로 널리 사용
- 비터비 복호의 복잡도는 구속장에 따라 지수적으로 증가하게됨
. 통상, 9 이하의 구속장을 갖는 길쌈부호의 복호에 적당
ㅇ 최대 우도 검파 방식 (Maximum Likelihood Detection/Decision)의 일종
3. 비터비 복호 알고리즘의 동작 방식
ㅇ 비터비 복호 방식(알고리즘) 이란?
- 각 시점 마다 상태 별로 들어오는 경로를 살펴보아,
. 트렐리스도 : 가로 축(시간), 세로 축(부호기 상태)로 구성된, 격자 형태의 상태 천이 그래프
.. 시점 : 트렐리스도의 각 열이 하나의 시점에 대응
.. 상태 : 트렐리스도의 각 행이 하나의 상태에 대응
. (시각 t에서, 상태 s와 입력 비트 u가 결정되면, 출력 심볼과 다음 상태 s'가 유일하게 결정됨)
. 경로 : 하나의 경로가 하나의 수신 비트열(코드워드)에 대응됨
- `수신 비트열`과 `트렐리스도 상의 가능한 경로 상의 비트열` 간에 메트릭 값을 비교하여,
- 가장 가능성 있는 경로를 선정하게 됨
. 이때, 오류정정도 함께 이루어짐
ㅇ 오류정정 (Error Correction)
- 각 시점마다 생존 경로 만을 유지하면서, 최종적으로 선택된 최대 우도 경로(ML Path)를,
. 역추적(Traceback)하여 원래의 비트열을 결정함
- 이 과정에서 수신 중 발생한 오류 비트가 올바른 비트로 복원(오류 정정)됨
ㅇ 메트릭 (Metric)
- 비교 기준이 되는 수치(파라미터)가 메트릭(Metric) 임
. 메트릭 例로는, 주로 해밍 거리가 가장 쉽게 이해됨
. 실제 메트릭은, 채널 특성 및 정합필터 출력의 양자화 방식에 따라, 그에맞게 수치가 매겨짐
ㅇ 생존 경로 (Surviving Path)
- 각 상태별로 들어오는 경로 마다 계산된 메트릭들 중에서 가장 작은 값을 갖는 경로 선택
. 여기서 선택된 경로를 생존 경로 이라고 함
- 한편, 비교 대상이 없는 경로는 그대로 생존 경로로 놔둠
ㅇ 경로 제거 (Path Removal)
- 트렐리스도 상에서, 계산된 메트릭 보다 큰 값을 갖는 경로들은 버리게 됨
. 가능성 없는 경로를 일찍 제거하여, 복호화시의 복잡도를 줄일 수 있음 (계산량 감축)
※ 사실상, 비터비 복호 알고리즘은,
- 트렐리스도 상에서 누적 메트릭이 가장 작은 경로를 선택하는 알고리즘임
. `최대 우도` 또는 `해밍 최소 거리` 메트릭을 갖는 부호어를 선택하는 것은 서로 등가적임
.. 즉, 최대 우도(ML) 또는 최소 거리(MD)를 갖는 부호어를 선택함
. 예로써, 이진 대칭 채널(BSC)에서는, '최소 해밍거리 = 최대 우도'로써, 서로 등가임
* [참고] => 복호 규칙 참조