Decodificación secuencial

Reconocida por John Wozencraft , la decodificación secuencial es una técnica de memoria limitada para decodificar códigos de árbol . La decodificación secuencial se utiliza principalmente como un algoritmo de decodificación aproximado para códigos convolucionales de longitud de restricción larga . Es posible que este enfoque no sea tan preciso como el algoritmo de Viterbi, pero puede ahorrar una cantidad sustancial de memoria de la computadora. Se utilizó 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 trata de minimizar el costo 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:

Dado un árbol parcialmente explorado (representado por un conjunto de nodos que son el límite de exploración), nos gustaría saber cuál es el mejor nodo desde el cual explorar más. La métrica de Fano (llamada así por Robert Fano ) permite calcular a partir de cuál es el mejor nodo para explorar más a fondo. Esta métrica es óptima dado que no hay otras restricciones (por ejemplo, memoria).

Para un canal simétrico binario (con probabilidad de error ), la métrica de Fano se puede derivar a través del teorema de Bayes . Estamos interesados en seguir el camino más probable dado un estado explorado del árbol y una secuencia recibida . Usando el lenguaje de la probabilidad y el teorema de Bayes , queremos elegir el máximo entre : ${\ estilo de visualización p}$ $P_{i}$ ${\ estilo de visualización X}$ ${\mathbf{r} }$ ${\ estilo de visualización i}$

Expresamos la probabilidad como (mediante el uso de la probabilidad del canal simétrico binario para los primeros bits seguidos de un anterior uniforme sobre los bits restantes). $\Pr({\mathbf {r} }|P_{i},X)$ $p^{d_{i}}(1-p)^{n_{i}b-d_{i}}2^{-(N-n_{i})b}$ ${\ estilo de visualización n_ {i} b}$