Viterbi Decoding Algorithm, Viterbi Decoding, Viterbi Decoder   비터비 복호, 비터비 복호 알고리즘, Viterbi 알고리즘

(2023-05-27)

1. 비터비 복호 방식 (비터비 알고리즘) 이란?채널을 통해 수신되는 데이터들을,
     - 트렐리스도의 여러 경로를 통해 탐색한 후,
     - 그 중에서 가장 가능성이 높은 (최대 우도) 경로를 선택하고, (최대 우도 복호,MLD)
     - 선택된 경로 상의 데이터들에 대해 오류정정을 하면서,
     - 이를 복호하는 알고리즘

  ㅇ 1965년도 Andrew J. Viterbi 박사가 제안한 경로 탐색 알고리즘에 따름


2. 비터비 복호 방식의 특징

  ㅇ 주로, 구속장이 짧은 길쌈부호복호 알고리즘으로 널리 사용
     - 비터비 복호의 복잡도는 구속장에 따라 지수적으로 증가하게됨
        . 통상, 9 이하의 구속장을 갖는 길쌈부호복호에 적당

  ㅇ 장단점
     - 장점 : 뛰어난 복호 성능, 빠른 동작 속도, 용이한 구현, 낮은 비용, 일정한 복호 시간 등
     - 단점 : 하드웨어 복잡도 큼 (특히, 구속장이 클수록)

  ㅇ 최대 우도 검파 방식(Maximum Likelihood Detection/Decision)의 일종


3. 비터비 복호 알고리즘의 동작 방식

  ㅇ 비터비 복호 방식은,
     - 각 상태 별로 들어오는 경로를 살펴보아,
     - `수신 비트열`과 `트렐리스도 상의 가능한 경로 상의 비트열`과 (메트릭 값을) 비교하여,
     - 가장 가능성 있는 경로를 선정하게 됨 (이때, 오류정정도 함께 이루어짐)

  ㅇ 메트릭 (Metric)
     - 비교 기준이 되는 수치(파라미터)가 메트릭(Metric) 임
        . 메트릭 例로는, 주로 해밍 거리가 가장 쉽게 이해됨
        . 실제 메트릭은, 채널 특성 및 정합필터 출력의 양자화 방식에 따라 수치가 매겨짐

  ㅇ 생존 경로 (Surviving Path)
     - 각 상태별로 들어오는 경로 마다 계산된 메트릭들 중에서 가장 작은 값을 갖는 경로 선택
        . 여기서 선택된 경로를 생존 경로 이라고 함
     - 한편, 비교 대상이 없는 경로는 그대로 생존 경로로 놔둠

  ㅇ 경로 제거
     - 트렐리스도 상에서. 계산된 메트릭 보다 큰 값을 갖는 경로들은 버리게 됨
        . 가능성 없는 경로를 일찍 제거하여, 복호화시의 복잡도를 줄일 수 있음 (계산량 감축)

  ※ 사실상, 비터비 복호 알고리즘은,
     - `최대 우도` 및 `해밍 최소 거리` 메트릭를 갖는 부호어를 선택하는 것과 등가적임

길쌈부호 복호
   1. 길쌈부호 복호   2. 비터비 알고리즘  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"