비테르비 디코더

비터비 디코더는 비터비 알고리즘을 사용하여 콘볼루션 코드 또는 트레일리스 코드를 사용하여 인코딩된 비트스트림을 디코딩하는 데 사용한다.

콘볼루션으로 인코딩된 스트림을 디코딩하는 다른 알고리즘(예: Fano 알고리즘)이 있다. Viterbi 알고리즘은 자원이 가장 많이 소모되지만 최대우도 디코딩을 한다. 제약조건 길이 k≤3의 경련 코드 해독에 가장 많이 사용되지만 실제로는 k=15까지의 값이 사용된다.

비테르비 디코딩은 앤드루 J. 비테르비(Andrew J. Viterbi)에 의해 개발되어 논문에 발표되었다. Viterbi, A. (April 1967). "Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm". IEEE Transactions on Information Theory. 13 (2): 260–269. doi:10.1109/tit.1967.1054010.

비테르비 디코더의 하드웨어(모뎀)와 소프트웨어 구현이 모두 있다.

Viterbi 디코딩 알고리즘에는 Viterbi 디코딩이 사용된다.

하드웨어 구현

하드웨어 Viterbi 디코더를 구현하는 일반적인 방법

기본(구멍이 뚫리지 않은) 코드에 대한 하드웨어 Viterbi 디코더는 일반적으로 다음과 같은 주요 블록으로 구성된다.

BMU(분지 메트릭 단위)
경로 메트릭 단위(PMU)
트레이스백 유닛(TBU)

BMU(분지 메트릭 단위)

분기 메트릭 유닛의 샘플 구현

분기 메트릭 단위의 기능은 코드 알파벳에서 가능한 모든 기호와 수신된 기호 사이의 거리인 분기 메트릭을 계산하는 것이다.

어려운 결정과 부드러운 결정 비테비 디코더들이 있다. 어려운 결정 Viterbi 디코더는 입력에서 간단한 비트스트림을 수신하며, 해밍 거리를 미터법으로 사용한다. 부드러운 결정 Viterbi 디코더는 각 수신 기호의 신뢰성에 대한 정보를 포함하는 비트스트림을 수신한다. 예를 들어, 3비트 인코딩에서 이 신뢰성 정보는 다음과 같이 인코딩될 수 있다.

가치를 매기다	의미
000	최강의	0
001	비교적 강한	0
010	상대적으로 약한	0
011	최약체	0
100	최약체	1
101	상대적으로 약한	1
110	비교적 강한	1
111	최강의	1

물론 신뢰성 데이터를 인코딩하는 방법만이 아니다.

제곱 유클리드 거리는 소프트 의사결정 디코더의 측정 기준으로 사용된다.

경로 메트릭 단위(PMU)

특정 K=4 디코더에 대한 경로 메트릭 단위의 샘플 구현

경로 메트릭 단위는 $2^{K-1}$ - 1 ${\$ K-1} 경로에 $대한$ 메트릭을 $2^{K-1}$ 얻기 $2^{K-1}$ 위해 분기 메트릭을 요약하며, 여기서 K는 코드의 제약 조건 길이이며, 이 중 하나는 최종적으로 최적 경로로 선택할 수 있다. 시계마다 $2^{K-1}$ - $2^{K-1}$ ${\$ 의 결정을 $2^{K-1}$ 내리며, 매우 비최적적인 경로를 벗어 던진다. 이러한 결정의 결과는 추적 장치를 기억하기 위해 기록된다.

PMU의 핵심 요소는 ACS(Add-Compare-Select) 단위다. 그들이 그들 사이에 연결되는 방법은 특정 코드의 trellis 도표로 정의된다.

분기 메트릭은 항상 $\geq 0$ $\geq 0$ ${\displaystyle \geq$ 0 $\geq 0$ 이므로 메트릭 카운터가 오버플로되지 않도록 추가적인 회로(이미지에 표시되지 않음)가 있어야 한다. 경로 메트릭 증가를 모니터링할 필요가 없는 다른 방법은 경로 메트릭이 "롤오버"할 수 있도록 하는 것이다. 이 방법을 사용하려면 경로 메트릭 축전기에 "최상" 및 "최악" 값이 서로 2개^(n-1) 내에 들어가지 않도록 충분한 비트가 포함되어 있는지 확인해야 한다. 비교 회로는 본질적으로 변하지 않는다.

ACS 장치의 샘플 구현

"최상의" 경로 메트릭의 증가 속도를 모니터링하여 들어오는 비트 스트림의 노이즈 레벨을 모니터링할 수 있다. 보다 간단한 방법은 단일 위치 또는 "상태"를 모니터링하고 축전지의 범위 내에서 4개의 이산 레벨을 통해 "위로" 지나가는 것을 보는 것이다. 각 임계값을 통해 위쪽으로 통과할 때, 수신 신호에 존재하는 "소음"을 반영하는 카운터가 증가된다.

트레이스백 유닛(TBU)

트레이스백 유닛의 샘플 구현

역추적 장치는 PMU의 결정으로부터 (거의) 최대 우도 경로를 복원한다. 역방향으로 하기 때문에, viterbi 디코더는 정확한 순서를 재구성하기 위해 FILO(선입선출) 버퍼로 구성된다.

이미지에 표시된 구현에는 이중 주파수가 필요하다는 점에 유의하십시오. 이 요건을 없애는 몇 가지 요령이 있다.

구현 문제

소프트 의사결정 디코딩을 위한 수량화

소프트 의사결정 디코딩의 장점을 충분히 활용하려면 입력 신호를 제대로 정량화할 필요가 있다. 최적 정량화 구역 폭은 다음 공식으로 정의된다.

\displaystyle \,\!T={\sqrt {\frac {N_{0}}{2}{2}^{k}}},}

여기서 $N_{0}$ ${\$ 은 $N_{0}$ 소음 전력 스펙트럼 밀도이며, k는 부드러운 결정을 위한 비트 수입니다.

유클리드 미터법 계산

코드 알파벳에서 수신된 기호와 실제 기호 사이의 거리 제곱 표준( $\ell _{2}$ $\ell _{2}$ ${\$ )은 선형 합계/차이 형태로 더욱 단순화할 수 있어 계산 집약도가 떨어진다.

모든 입력 비트(1 또는 0)에 대해 2비트(00, 01, 10 또는 11)를 생성하는 1/2 콘볼루션 코더를 고려하십시오. 이러한 반환-제로 신호는 옆에 표시된 비반환-제로(Non-Return-to-Zero(제로 되돌리기)

알파벳을 부호화하다	벡터 매핑
00	+1, +1
01	+1, −1
10	−1, +1
11	−1, −1

수신된 각 기호는 v_r = {r₀, r₁}(으)로 벡터 형태로 나타낼 수 있으며, 여기서 r과₀ r은₁ 수신된 벡터의 공동_r 신뢰도를 나타내는 소프트 의사결정 값이다.

마찬가지로 코드 알파벳의 모든 기호는 벡터 v_i = {±1, ±1}(으)로 나타낼 수 있다.

유클리드 거리 메트릭의 실제 계산은 다음과 같다.

\displaystyle \,\!D=({\overrightarrow {v_{r}}-{\overrightarrow {v_{i}}}^{2}-{{r}}^{2}-{{r}}{\overrightarrow {v_{i}}+{v_{i}}}}}}}}}}{{{{{{{{overri}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

각 정사각형 항은 기호의 에너지를 나타내는 규범된 거리다. ex의 경우 기호 v_i = {±1, ±1}의 에너지는 다음과 같이 계산할 수 있다.

\displaystyle \,\!{\overrightarrow {v_{i}}^{2}=(\pm 1)^{2}+(\pm 1)^{2}=2}

따라서 코드 알파벳에 있는 모든 기호의 에너지 용어는 일정하다(정규화된) 값 2)

ACS(Add-Compare-Select) 작업은 수신된 기호 v와_r 해당 trellis, v_i⁽⁰⁾ 및 v의_i⁽¹⁾ 노드에서 경로가 병합되는 코드 알파벳의 기호 2개 사이의 메트릭 거리를 비교한다. 이는 비교하는 것과 같다.

\displaystyle \,\!D_{0}={\overrightarrow {v_{r}}^{2}-2{\overrightarrow {v_{r}}{{0}}}}{\overrightarrow {v_{i}^{0}}}}+{\overrightarrow {v_{0}}}^{2}}:

그리고

\displaystyle \,\!D_{1}={\overrightarrow{v_{r}}^{2}-2{\overrightarrow{v_{r}}{{v_{i}^{1}}{1}}}{{{1}}}}+{\overrighrow {v_{i}^{1}}}}:{2}}:

그러나 위에서 우리는 v의_i 에너지가 일정하다는 것을 알고 있다(정상화(정상화) 값 2와 동일), 그리고 v의_r 에너지는 두 경우 모두 동일하다. 이것은 2 (중간) 도트 제품 조건 사이의 미니마 함수에 대한 비교를 줄인다.

\,\!\min(-2{\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{0}}},-2{\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{1}}})=\max({\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{0}}},{\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{1}}})

음수에 대한 $최소$ 연산은 양의 수량에 대한 $최대$ 등가 연산으로 해석될 수 있기 때문이다.

각 도트 제품 용어는 다음과 같이 확장될 수 있다.

\,\!\max(\pm r_{0}\pm r_{1},\pm r_{0}\pm r_{1}

여기서, 각 용어의 부호는 비교되는 기호 v와_i⁽⁰⁾ v에_i⁽¹⁾ 따라 달라진다. 따라서 분기 메트릭을 계산하기 위한 제곱 유클리드 메트릭 거리 계산은 간단한 추가/추상 연산을 통해 수행할 수 있다.

트레이스백

트레이스백에 대한 일반적인 접근방식은 제약조건 길이의 최대 5배(5K - 1)까지 경로 지표를 축적하고 누적 비용이 가장 큰 노드를 찾아 이 노드에서 트레이스백을 시작하는 것이다.

일반적으로 사용되는 절삭 깊이에서 수녀원 코드의 메모리(기존 길이 K-1)의 5배인 엄지손가락 규칙은 비율 1/2 코드에 대해서만 정확하다. 임의 비율의 경우 정확한 엄지손가락 규칙은 2.5(K - 1)/(1-r)이며 여기서 r은 코드 비율이다.^[1]

그러나 가장 큰 비용(가장 크거나 가장 작은 적분 경로 메트릭 중 하나)을 누적한 노드 계산에는 여러 (일반적으로 2^K-1) 숫자의 최대값 또는 최소값을 구하는 작업이 포함되며, 임베디드 하드웨어 시스템에서 구현될 경우 시간이 많이 소요될 수 있다.

대부분의 통신 시스템은 고정된 크기의 데이터 패킷을 포함하는 Viterbi 디코딩을 데이터 패킷의 시작 또는/또는/그리고 데이터 패킷의 끝에서 고정 비트/바이트 패턴을 사용한다. 알려진 비트/바이트 패턴을 참조로 사용함으로써, 시작 노드를 고정 값으로 설정하여 추적 중 완벽한 최대우도 경로를 얻을 수 있다.

제한 사항

Viterbi 디코더의 물리적 구현은 입력 신호, 분기 및 경로 메트릭의 정량화 및 유한 트레이스백 길이로 인해 정확한 최대 우도 스트림을 생성하지 않는다. 실제 구현은 이상적인 1dB 이내에서 접근한다.

부가적인 가우스 채널에 의해 손상된 메시지를 디코딩할 때 Viterbi 디코더의 출력에 오류 버스트로 그룹화된 오류가 있다.^[2]^[3] 단일 오류 수정 코드만으로는 이러한 버스트를 수정할 수 없으므로, 콘볼루션 코드와 비테르비 디코더는 오류를 허용 가능한 속도로 감소시킬 수 있을 정도로 충분히 강력하도록 설계하거나, 버스트 오류 수정 코드를 사용해야 한다.

펑크가 난 코드

펑크 난 코드의 하드웨어 바이터비 디코더는 일반적으로 다음과 같은 방식으로 구현된다.

비트가 지워진 곳에서 ERASR 표시가 있는 원본(구멍이 나지 않은) 스트림처럼 보이는 스트림으로 입력 스트림을 변환하는 디퍼레이터.
이러한 ERASR 표시를 이해하는 기본 viterbi 디코더(즉, 분기 메트릭 계산에 사용하지 않음)

소프트웨어 구현

가장 많은 시간이 소요되는 작업 중 하나는 ACS 나비인데, 일반적으로 디코딩 시간을 단축하기 위해 조립 언어와 적절한 명령 집합 확장(SSE2 등)을 사용하여 구현된다.

적용들

Viterbi 디코딩 알고리즘은 다음 영역에서 널리 사용된다.

무선 통신: 디지털 TV(ATSC, QAM, DVB-T 등), 무선 릴레이, 위성 통신, 아마추어 무선용 PSK31 디지털 모드.
3kHz 대역 아날로그 전화선 중 높은 스펙트럼 효율을 짜내기 위해 전화선 모뎀에 사용되는 기술인 트렐리스 코드 변조(TCM) 디코딩.
하드 디스크 드라이브와 같은 컴퓨터 저장 장치.
자동 음성 인식

참조

^ B. Moision, "경련 코드에 대한 엄지손가락 자르기 깊이 규칙," 2008년 정보 이론 및 응용 프로그램 워크샵, 샌디에이고, CA, 2008, 페이지 555-557, doi :10.1109/ITA. 2008.4601052.
^ 스테판 호스트, 롤프 요한네슨, 드미트리히 K. 지간기로드, 카밀 슈 지간기로드, 빅토르 V. 자야블로드. "경련 코드의 Viterbi 디코딩을 위한 출력 오류 버스트 길이 분포에 대하여"
^ Curry, S. J.; Harmon, W. D. "Viterbi 디코더 오류 버스트 길이에 대한 바운드"

외부 링크

Forney, G. David, Jr (29 Apr 2005). "The Viterbi Algorithm: A Personal History". arXiv:cs/0504020.
비터비 디코딩에 대한 자세한 내용과 참고 문헌 목록.
하드웨어 구현 문제에 초점을 맞춘 Viterbi 알고리즘 설명.
토성으로의 카시니 임무에 대한 r=1/6 k=15 부호화
최적화된 소프트웨어 Viterbi 디코더(GPL)의 온라인 생성기.
4가지 표준 코드용 GPL Viterbi 디코더 소프트웨어.
실제 사용 중 가장 큰 것으로 여겨지는 k=24 Viterbi 디코더에 대한 설명.
일반 Viterbi 디코더 하드웨어(GPL).

[1] B. Moision, "경련 코드에 대한 엄지손가락 자르기 깊이 규칙," 2008년 정보 이론 및 응용 프로그램 워크샵, 샌디에이고, CA, 2008, 페이지 555-557, doi :10.1109/ITA. 2008.4601052.

[2] 스테판 호스트, 롤프 요한네슨, 드미트리히 K. 지간기로드, 카밀 슈 지간기로드, 빅토르 V. 자야블로드. "경련 코드의 Viterbi 디코딩을 위한 출력 오류 버스트 길이 분포에 대하여"

[3] Curry, S. J.; Harmon, W. D. "Viterbi 디코더 오류 버스트 길이에 대한 바운드"

[1]

[2]

[3]

Search