비터비 알고리즘 (Viterbi Algorithm)
1. 개요
o 길쌈코드 (Convolutional Code)를 위한 복호화 (Decoding)방법에는,
비터비 알고리즘을 이용한 최대 유사도 (Maximum likelihood) 복호화와 순차 복호화가 있음
o 비터비 알고리즘은 최대 유사도 복호화에서 최대 성능 이득을 얻고 하드웨어 구현을 간소하게 함
o 더욱 낮은 에러율을 갖기 위해 긴 구속장이 필요할 때 순차 복호화 사용함
2. 최대 유사도 복호화 - 비터비 알고리즘
o 최대 유사도 복호 수신기는 수신된 코드어(Code Word)에 가장 근사하는 코드를 선택함
o 비터비 알고리즘 : 단지 2개의 이전 노드 만을 통하여 각 상태 노드들에 도달할 수 있도록 단순화하고, 각 노드에 대해 수신된 수열과 가장 일치하는 경로 (최소 거리 경로) 만 유지하도록 함으로써, 최대 유사도 복호를 계산하는 방법임
o 경판정 (Hard Decision) 복호화
- 수신된 신호 --> [복조기] --> [2진비트 검출기] --> [비터비 검출기] --> 복호된 메시지 시퀀스
- 경판정의 의미 :
비터비 복호기 전단의 복조기 / 비트 검출기에서 이미 수신된 비트 시퀀스를 '0' 또는 '1'로 결정함
- 통계적 유사도 척도(Metric)로 해밍 거리를 사용함
o 연판정 (Soft Decision) 복호화 , SOVA (Soft-decision Output Viterbi Algorithm)
- 경판정 복호에서, 2진 비트 검출기에 의해 수행되는 비트 양자화는 연속하는 값을 갖는 복조 신호를 2 레벨의 이산 신호로 대응시킴으로써 정보의 손실이 있음
- 2진 비트 검출기를 사용하지 않고, 유사도 척도를 해밍 거리에서 Euclidean 거리로 바꾼 것.
- 추가적인 Coding Gain을 얻음
o 비터비 알고리즘을 사용한 계산의 복잡도는 "2N" 에 비례하며, 구속장 N < 10 인 경우에 매우 효율적임
3. 특징
o 짧은 구속장 길이 (N < 10) 일 때 적용함
o 구조가 비교적 간단함
o 100Mbps 정도의 상대적으로 높은 속도에서도 복호 (디코딩)가 가능함
o 에너지 효율이 중요한 디지털 통신에 적합함
o TCM (Trellis-Coded Modulation) 등에 기본이 되는 복호 방법임
o 길쌈 코드를 위한 복호기(Decoder)를 효율적으로 구현하는데 필수적임
4. 구현 - 복호된 메시지를 계속 관측하는 방법
o Register Transfer 방식
o Trace-back 방법
- 고속의 복호기가 요구되는 경우, 집적회로로 구현할 때 더 효율적임
- Two-port RAM을 사용하여 효율적으로 구현함
참고 자료 : http://pweb.netcom.com/~chip.f/Viterbi.html
이상