순차 디코딩

존 워젠크래프트가 인정한 순차적 디코딩은 트리 코드를 디코딩하기 위한 제한된 메모리 기법이다. 순차적 디코딩은 주로 긴 제약 조건-길이 합성 코드의 대략적인 디코딩 알고리즘으로 사용된다. 이 접근방식은 Viterbi 알고리즘만큼 정확하지는 않을 수 있지만 상당한 양의 컴퓨터 메모리를 절약할 수 있다. 1968년 파이오니어 9 임무에서 수녀원 코드를 해독하는 데 사용되었다.

순차적 디코딩은 트리를 저장하는 데 필요한 계산 비용과 메모리 요구 사항을 최소화하기 위해 트리 코드를 탐구한다.

미터법과 알고리즘의 선택에 따라 다양한 순차적 디코딩 접근법이 있다. 메트릭스:

• 파노 미터법
• 지간구로프 미터법
• 갤러거 미터법

알고리즘에는 다음이 포함된다.

• 스택 알고리즘
• 파노 알고리즘
• 크리퍼 알고리즘

파노 미터법

부분적으로 탐색된 트리(탐색 한계인 노드 집합으로 표현됨)를 고려할 때, 우리는 더 멀리 탐색할 수 있는 최적의 노드를 알고 싶다. Fano 메트릭스(Robert Fano의 이름을 따서 명명)는 어떤 노드에서 더 멀리 탐색하기에 가장 좋은 노드인지 계산할 수 있게 해준다. 이 메트릭은 다른 제약 조건(예: 메모리)이 없는 경우에 최적이다.

2진수 대칭 채널(오류 $확률{\displaystyle }$ p ${\displaystyle p$의 경우 Bayes 정리를 통해 Fano 메트릭을 도출할 수 있다. $트리{\displaystyle }$ X$${\$displaystyle X}$의 탐색 상태와$$ 수신된 $시퀀스{\displaystyle \mathbf{}}$ r$${\$displaystyle {\mathbf {r}}}}$을(를) 통해 가장 가능성이 높은 경로 $P{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$$displaystyle$ $P_$${i}$을(를) 따르는 데 관심이 있다$.$ 확률의 언어와 베이지스 정리를 사용하여 다음$$ 중 $최대값$을 $선택$하고자 한다$.$

${\displaystyle \Pr(P_{i}X, {\mathbf {r}}) X, {\mathbf {r}\Pr({\mathbf {r}{} P_{i}X)\Pr(P_{i}X)}}$

이제 다음과 같은 표기법을 도입한다.

• ${\displaystyle \mathrm{분기}}$의 최대 전송 길이를 나타내는$$ N ${\displaystyle N}$
• ${\displaystyle b}$ 코드 분기의 비트 수($코드{\displaystyle }$ 비율의 분모, R ${\displaystyle R})$를 나타내기 위한$$ ${\displaystyle b}.$
• ${\displaystyle d_{}}$ ${\displaystyle i_{}}$ ${\$ 경로 $P{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$의 비트 오류 수를 나타내기 위해$$($$분지 레이블과 수신된 시퀀스 사이의 해밍 거리)
• ${\displaystyle n_{}}$ ${\displaystyle i_{}}$ ${\$는 가지에 있는 $P$ ${\displaystyle i_{}}$ ${\$의 길이여야 한다$$.

We express the likelihood ${\displaystyle \Pr({\mathbf {r} } P_{i},X)}$ as ${\displaystyle p^{d_{i}}(1-p)^{n_{i}b-d_{i}}2^{-(N-n_{i})b}}$ (by using the binary symmetric channel likelihood for the first ${\displaystyle n_$${i}b}$비트에$$ 이어 나머지 비트보다 먼저 균일함).

$이전{\displaystyle {}_{}}$ ${\displaystyle Pr}$(${\displaystyle Pi{}_{}}$ X$){\displaystyle \Pr(P_{i}X)}$은(는) 분기 선택 $,$ n i {\$displaystyle$ n_$\{$$i}}$ 및 각 노드에서 분기 수, $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {\mathrm{Rb}}^{}}$ ${\$ 2$^{Rb})$를 기준으로 표현한다$.$

따라서 다음과 같다.

${\displaystyle {\begin{aligned}\Pr(P_{i} X,{\mathbf {r} })&\propto p^{d_{i}}(1-p)^{n_{i}b-d_{i}}2^{-(N-n_{i})b}2^{-n_{i}Rb}\\&\propto p^{d_{i}}(1-p)^{n_{i}b-d_{i}}2^{n_{i}b}2^{-n_{i}Rb}\end{aligned}}}$

우리는 동등하게 이 확률의 일지를 최대화할 수 있다.

${\displaystyle {\begin{aligned}&d_{i}\log _{2}p+(n_{i}b-d_{i})\log _{2}(1-p)+n_{i}b-n_{i}Rb\\=&d_{i}(\log _{2}p+1-R)+(n_{i}b-d_{i})(\log _{2}(1-p)+1-R)\end{aligned}}}$

이 마지막 식은 Fano 미터법이다. 여기서 중요한 점은 우리가 두 가지 용어를 가지고 있다는 것이다. 하나는 잘못된 비트의 수를 기초로 하고 다른 하나는 오른쪽 비트의 수를 기준으로 한다. 따라서 각 비매칭 비트에 대해$$ ${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle p}$+ ${\displaystyle 1}$- R ${\displaystyle \log$ ${\displaystyle \mathrm{\_}}$${2}$${\displaystyle p}$$+1-R}$를 추가하고 각 일치 비트에 대해 로그 2${\displaystyle {}_{}\log }$(${\displaystyle {1\mathrm{}}_{}}$ - p${\displaystyle }$)${\displaystyle }$+${\displaystyle }$1 -${\displaystyle }$R ${\displaystyle \log _{2}(1-p)+1-R}$을 추가하기만 하면 Fano 메트릭을 업데이트할 수 있다.

계산 컷오프율

디코딩 알고리즘의 좋은 선택에 대한 순차적 디코딩의 경우, 탐색한 상태의 수는 작게 유지하기를 원한다(그렇지 않으면 Viterbi 알고리즘과 같은 모든 상태를 의도적으로 탐색하는 알고리즘이 더 적합할 수 있다). 특정 소음 수준의 경우 계산 컷오프 속도라 불리는$$ 최대 부호화 $속도{\displaystyle {}_{}}$ ${\displaystyle {R\mathrm{}}_{}}$ 0${\$이 있으며, 여기에는 유한 역추적 한계가 있다. 이진 대칭 채널의 경우:

${\displaystyle R_{0}=1-\log _{2}(1+2{\sqrt{p(1-p)}}}$

알고리즘

스택 알고리즘

가장 간단한 알고리즘은 지금까지 발견된 최상의 $N{\displaystyle }$ ${\displaystyle N}$ 경로가$$ 저장된 "스택 알고리즘"이다. 순차적 디코딩은 올바른 경로 $위$에 N ${\displaystyle N}$ 또는$$ 그 이상의 높은 점수 매김 경로가 있을 때 Viterbi 디코딩 이상의 추가 오류를 발생시킬 수 있다. 이때 최적의 경로가 스택에서 떨어져 더 이상 고려되지 않을 것이다.

파노 알고리즘

유명한 Fano 알고리즘(Robert Fano의 이름을 따서 명명)은 메모리 요구사항이 매우 낮기 때문에 하드웨어 구현에 적합하다. 이 알고리즘은 트리의 단일 지점에서 앞뒤로 탐색한다.

1. Fano 알고리즘은 스택이 필요하지 않은 순차 디코딩 알고리즘이다.
2. Fano 알고리즘은 경로 합병을 검토할 수 없기 때문에 코드 트리에서만 작동할 수 있다.
3. 각 디코딩 단계에서 Pano 알고리즘은 현재 경로, 즉시 이전 경로 및 후속 경로의 세 가지 경로에 대한 정보를 보존한다.
4. 이 정보를 바탕으로 Pano 알고리즘은 현재 경로에서 바로 이전 경로 또는 선택된 후속 경로로 이동할 수 있으므로, 검사된 모든 경로를 대기열에 넣는 데 스택이 필요하지 않다.
5. Fano 알고리즘의 이동은 동적 임계값에 의해 유도된다. T 즉, 고정 스텝 크기 integer의 정수 배수다.
6. 경로 메트릭이 다음보다 작은 경로만 T 다음에 방문할 수 있다. 알고리즘에 따르면 코드 경로를 따라가는 Fano 메트릭이 비감소 상태로 유지되는 한 코드 워드 검색 프로세스는 코드 경로를 따라 계속 전진한다.
7. 모든 후속 경로 메트릭이 다음보다 작으면 T, 알고리즘은 이전 경로 메트릭이 비트할 경우 이전 경로로 역방향으로 이동함 T; 그 후, 문턱 시험은 이 재방문한 전임자의 다른 후계자 경로에 대해 후속적으로 수행될 것이다.
8. 이전 경로 메트릭도 다음보다 작은 경우 T, 임계값 T 알고리즘이 현재 경로에 갇히지 않도록 한 단계 낮춘다.
9. Fano 알고리즘의 경우 경로를 재방문할 경우 현재 조사된 동적 임계값은 항상 이전 방문의 순간 동적 임계값보다 낮으며, 알고리즘이 궁극적으로 코드 트리의 터미널 노드에 도달하여 중지할 수 있음을 보장한다.

참조

• 존 워젠크래프트와 B. 레이펜, 순차 디코딩, ISBN0-262-23006-2
• Rolf Johannesson and Kamil Sh. Zigangirov, Convolutional coding의 기초 (6장), ISBN 0-470-27683-5

외부 링크

• "수정 트리" - 우선 순위 대기열을 사용하여 최대 메트릭 노드(중량이라고 함)를 선택하는 수정 프로세스 시뮬레이터