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 limitada . Este enfoque puede no ser tan preciso como el algoritmo de Viterbi, pero puede ahorrar una cantidad sustancial de memoria de 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 métricas y algoritmos. Las métricas incluyen:

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

Los algoritmos incluyen:

• Algoritmo de pila
• Algoritmo de Fano
• Algoritmo Creeper

Métrica Fano

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 Fano (llamada así por Robert Fano ) permite calcular cuál es el mejor nodo desde el cual explorar más. Esta métrica es óptima si no hay otras restricciones (por ejemplo, la 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 la ruta más probable dado un estado explorado del árbol y una secuencia recibida . Utilizando el lenguaje de la probabilidad y el teorema de Bayes queremos elegir el máximo de: ${\displaystyle p}$ ${\displaystyle P_{i}}$ ${\displaystyle X}$ ${\displaystyle {\mathbf {r} }}$ ${\displaystyle i}$

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

Ahora introducimos la siguiente notación:

• ${\displaystyle N}$para representar la longitud máxima de transmisión en las 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 (la distancia de Hamming entre las etiquetas de las ramas y la secuencia recibida) ${\displaystyle P_{i}}$
• ${\displaystyle n_{i}}$ser la longitud de en ramas. ${\displaystyle P_{i}}$

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

Expresamos lo anterior en términos de la cantidad de elecciones de ramas que uno ha hecho, , y la cantidad de ramas de cada nodo, . ${\displaystyle \Pr(P_{i}|X)}$ ${\displaystyle n_{i}}$ ${\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 manera 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 Fano. El punto importante que hay que tener en cuenta es que tenemos dos términos: uno basado en la cantidad de bits incorrectos y otro basado en la cantidad de bits correctos. Por lo tanto, podemos actualizar la métrica Fano simplemente sumando por cada bit que no coincida y por cada bit que coincida. ${\displaystyle \log _{2}p+1-R}$ ${\displaystyle \log _{2}(1-p)+1-R}$

Tasa de corte computacional

Para que la decodificación secuencial sea una buena opción de algoritmo de decodificación, el número de estados explorados debe ser 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áxima denominada tasa de corte computacional, donde hay un límite de retroceso finito. Para el canal simétrico binario: ${\displaystyle R_{0}}$

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

Algoritmos

Algoritmo de pila

El algoritmo más simple de describir es el "algoritmo de pila", en el que se almacenan las mejores rutas encontradas hasta el momento. La decodificación secuencial puede introducir un error adicional por encima de la decodificación de Viterbi cuando la ruta correcta tiene o tiene rutas con mayor puntuación por encima; en este punto, la mejor ruta se eliminará de la pila y ya no se considerará. ${\displaystyle N}$ ${\displaystyle N}$

Algoritmo de Fano

El famoso algoritmo Fano (que debe su nombre a Robert Fano ) requiere muy poca memoria y, por lo tanto, es adecuado para implementaciones de hardware. Este algoritmo explora hacia atrás y hacia adelante desde un único punto en el árbol.

1. El algoritmo Fano es un algoritmo de decodificación secuencial que no requiere una pila.
2. El algoritmo Fano sólo puede operar sobre un árbol de código porque no puede examinar la fusión de rutas.
3. En cada etapa de decodificación, el algoritmo Fano conserva la información sobre tres rutas: la ruta actual, su ruta predecesora inmediata y una de sus rutas sucesoras.
4. Basándose en esta información, el algoritmo Fano puede pasar de la ruta actual a su ruta predecesora inmediata o a la ruta sucesora seleccionada; por lo tanto, no se requiere una pila para poner en cola todas las rutas examinadas.
5. El movimiento del algoritmo Fano está guiado por un umbral dinámico T que es un múltiplo entero de un tamaño de paso fijo Δ.
6. 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 clave continúa avanzando a lo largo de una ruta de código, siempre que la métrica Fano a lo largo de la ruta de código no disminuya.
7. Una vez que todas las métricas de la ruta sucesora son menores que T , el algoritmo retrocede a la ruta predecesora si la métrica de la ruta predecesora supera a T ; a partir de entonces, se realizará un examen de umbral en otra ruta sucesora de este predecesor revisado.
8. 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.
9. Para el algoritmo Fano, si se vuelve a visitar una ruta, el umbral dinámico examinado actualmente es siempre inferior al 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 llegar a un nodo terminal del árbol de código y detenerse.

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 una cola de prioridad para elegir el nodo de métrica máxima (llamado peso)