Decodificación secuencial

Reconocida por John Wozencraft , la decodificación secuencial es una técnica de memoria limitada para decodificar códigos de árbol . Se utiliza principalmente como algoritmo de decodificación aproximada para códigos convolucionales de longitud restringida . Si bien este método puede no ser tan preciso como el algoritmo de Viterbi , permite ahorrar una cantidad considerable de memoria . Se empleó para decodificar un código convolucional en la misión Pioneer 9 de 1968 .

La decodificación secuencial explora el código del árbol de tal manera que se intente minimizar el coste computacional y los requisitos de memoria para almacenar el árbol.

Existe una variedad de enfoques de decodificación secuencial basados ​​en la elección de la métrica y el algoritmo. Las métricas incluyen:

• Métrica de Fano
• Métrica de Zigangirov
• Métrica de Gallager

Los algoritmos incluyen:

• Algoritmo de pila
• Algoritmo de Fano
• Algoritmo Creeper

Dado un árbol parcialmente explorado (representado por un conjunto de nodos que limitan la exploración), nos interesa saber cuál es el mejor nodo para continuar la exploración. La métrica de Fano (llamada así en honor a Robert Fano ) permite calcular cuál es el mejor nodo para seguir explorando. Esta métrica es óptima si no existen otras restricciones (por ejemplo, de memoria).

Para un canal binario simétrico (con probabilidad de error)${\displaystyle p}$La métrica de Fano se puede derivar mediante el teorema de Bayes . Nos interesa seguir el camino más probable.${\displaystyle P_{i}}$dado un estado explorado del árbol${\displaystyle X}$y una secuencia recibida${\displaystyle {\mathbf {r} }}$. Usando el lenguaje de la probabilidad y el teorema de Bayes queremos elegir el máximo sobre${\displaystyle i}$de:

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

A continuación, introducimos la siguiente notación:

• ${\displaystyle N}$para representar la longitud máxima de transmisión en ramas
• ${\displaystyle b}$para representar el número de bits en una rama del código (el denominador de la tasa de código ,${\displaystyle R}$).
• ${\displaystyle d_{i}}$para representar el número de errores de bits en la ruta${\displaystyle P_{i}}$(la distancia de Hamming entre las etiquetas de las ramas y la secuencia recibida)
• ${\displaystyle n_{i}}$ser la longitud de${\displaystyle P_{i}}$en ramas.

Expresamos la probabilidad${\displaystyle \Pr({\mathbf {r} }|P_{i},X)}$como${\displaystyle p^{d_{i}}(1-p)^{n_{i}b-d_{i}}2^{-(N-n_{i})b}}$(utilizando la probabilidad del canal simétrico binario para el primero${\displaystyle n_{i}b}$bits seguidos de una distribución a priori uniforme sobre los bits restantes).

Expresamos lo anterior${\displaystyle \Pr(P_{i}|X)}$en términos del número de opciones de rama que se han elegido,${\displaystyle n_{i}}$y el número de ramas desde cada nodo,${\displaystyle 2^{Rb}}$.

Por lo tanto:

${\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}}}$

Podemos maximizar de forma equivalente el logaritmo de esta probabilidad, es decir

${\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}}}$

Esta última expresión es la métrica de Fano. Lo importante es que tenemos dos términos: uno basado en el número de bits erróneos y otro basado en el número de bits correctos. Por lo tanto, podemos actualizar la métrica de Fano simplemente sumando${\displaystyle \log _{2}p+1-R}$para cada bit que no coincide y${\displaystyle \log _{2}(1-p)+1-R}$para cada bit coincidente.

For sequential decoding to be a good choice of decoding algorithm, the number of states explored should remain small (otherwise an algorithm which deliberately explores all states, e.g. the Viterbi algorithm, may be more suitable). For a particular noise level there is a maximum coding rate ${\displaystyle R_{0}}$ called the computational cutoff rate where there is a finite backtracking limit. For the binary symmetric channel:

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

• John Wozencraft y B. Reiffen, Decodificación secuencial , ISBN 0-262-23006-2
• Rolf Johannesson y Kamil Sh. Zigangirov, Fundamentos de la codificación convolucional (capítulo 6), ISBN 0-470-27683-5

• " Árboles de corrección ": simulador del proceso de corrección que utiliza una cola de prioridad para elegir el nodo de métrica máxima (llamado peso).