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 restringida largos . Este enfoque puede no ser 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 intenta 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:
- Métrica de Fano
- Métrica de Zigangirov
- Métrica de Gallager
Los algoritmos incluyen:
- Algoritmo de pila
- Algoritmo de Fano
- Algoritmo Creeper
Métrica de Fano
Dado un árbol parcialmente explorado (representado por un conjunto de nodos que son límite de exploración), nos gustaría saber cuál es el mejor nodo desde el que explorar más. La métrica de Fano (que lleva el nombre de Robert Fano ) permite calcular a partir de cuál es el mejor nodo para explorar más a fondo. Esta métrica es óptima sin otras limitaciones (por ejemplo, memoria).
Para un canal simétrico binario (con probabilidad de error) la métrica de Fano se puede derivar mediante el teorema de Bayes . Nos interesa 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 sobre de:
Introducimos ahora la siguiente notación:
- para representar la longitud máxima de transmisión en ramas
- para representar el número de bits en una rama del código (el denominador de la tasa de código ,).
- para representar el número de errores de bits en la ruta (la distancia de Hamming entre las etiquetas de las ramas y la secuencia recibida)
- ser la longitud de en ramas.
Expresamos la probabilidad como (mediante el uso de la probabilidad de canal simétrico binario para el primer bits seguidos de un uniforme previo sobre los bits restantes).
Expresamos lo anterior en términos de la cantidad de opciones de sucursales que se han realizado, , y el número de ramas de cada nodo, .
Por lo tanto:
Podemos maximizar de manera equivalente el logaritmo de esta probabilidad, es decir
Esta última expresión es la métrica de Fano. El punto importante a tener en cuenta es que tenemos dos términos aquí: uno basado en el número de bits incorrectos y otro basado en el número de bits correctos. Por lo tanto, podemos actualizar la métrica de Fano simplemente agregando para cada bit no coincidente y para cada bit coincidente.
Tasa de corte computacional
Para la decodificación secuencial de una buena elección de algoritmo de decodificación, el número de estados explorados debe permanecer pequeño (de lo contrario, un algoritmo que explore deliberadamente todos los estados, por ejemplo, el algoritmo de Viterbi , puede ser más adecuado). Para un nivel de ruido particular, existe una tasa de codificación máximallamada tasa de corte computacional donde hay un límite de retroceso finito. Para el canal simétrico binario:
Algoritmos
Algoritmo de pila
El algoritmo más simple de describir es el "algoritmo de pila" en el que el mejor Las rutas encontradas hasta ahora se almacenan. La decodificación secuencial puede introducir un error adicional por encima de la decodificación de Viterbi cuando la ruta correcta tieneo caminos de mayor puntuación por encima de él; en este punto, la mejor ruta desaparecerá de la pila y ya no se considerará.
Algoritmo de Fano
El famoso algoritmo de Fano (llamado así por Robert Fano ) tiene un requisito de memoria muy bajo y, por lo tanto, es adecuado para implementaciones de hardware. Este algoritmo explora hacia atrás y hacia adelante desde un único punto del árbol.
- El algoritmo de Fano es un algoritmo de decodificación secuencial que no requiere una pila.
- El algoritmo de Fano solo puede operar sobre un árbol de código porque no puede examinar la combinación de rutas.
- En cada etapa de decodificación, el algoritmo de Fano retiene la información sobre tres rutas: la ruta actual, su ruta predecesora inmediata y una de sus rutas sucesoras.
- Con base en esta información, el algoritmo de Fano puede moverse desde la ruta actual a su ruta predecesora inmediata o la ruta sucesora seleccionada; por lo tanto, no se requiere una pila para poner en cola todas las rutas examinadas.
- El movimiento del algoritmo de Fano está guiado por un umbral dinámico T que es un múltiplo entero de un tamaño de paso fijo ¢.
- Solo se puede visitar a continuación la ruta cuya métrica de ruta no sea menor que T. Según el algoritmo, el proceso de búsqueda de palabras de código continúa avanzando a lo largo de una ruta de código, siempre que la métrica de Fano a lo largo de la ruta de código no disminuya.
- Una vez que todas las métricas de la ruta sucesora son más pequeñas que T , el algoritmo retrocede a la ruta predecesora si la métrica de la ruta predecesora supera a T ; a partir de entonces, el examen de umbral se realizará posteriormente en otro camino sucesor de este predecesor revisado.
- En caso de que la métrica de la ruta predecesora también sea menor que T , el umbral T se reduce un paso para que el algoritmo no quede atrapado en la ruta actual.
- Para el algoritmo de Fano, si se vuelve a visitar una ruta, el umbral dinámico examinado actualmente es siempre más bajo que el umbral dinámico momentáneo en la visita anterior, lo que garantiza que no se produzcan bucles en el algoritmo y que el algoritmo pueda finalmente alcanzar un nodo terminal de el árbol de código y deténgase.
Referencias
- 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
enlaces externos
- " Árboles de corrección ": simulador del proceso de corrección que utiliza la cola de prioridad para elegir el nodo métrico máximo (llamado peso)