Algoritmo de decodificación convolucional de Viterbi

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 14 de enero de 2020; la verificación requiere 1 edición .

En 1967, Andrew Viterbi desarrolló y analizó un algoritmo de decodificación basado en el principio de máxima verosimilitud . El algoritmo se optimiza mediante el uso de las características estructurales de una red de código particular. La ventaja de la decodificación de Viterbi sobre la decodificación de fuerza bruta es que la complejidad del decodificador de Viterbi no es una función del número de símbolos en la secuencia de palabras clave .

El algoritmo implica calcular una medida de similitud (o distancia ) entre la señal recibida en el momento t y todas las rutas de la red que ingresan a cada estado en el momento t . El algoritmo de Viterbi no considera aquellos caminos reticulares que, según el principio de máxima verosimilitud, no pueden ser óptimos. Si dos caminos entran en el mismo estado, se elige el de mejor métrica ; tal camino se llama supervivencia . La selección de rutas supervivientes se realiza para cada estado. Así, el decodificador se adentra más en la red, tomando decisiones eliminando caminos menos probables. El rechazo preliminar de caminos improbables simplifica el proceso de decodificación. En 1969, Jim Omura demostró que la base del algoritmo de Viterbi es la estimación de máxima verosimilitud . Tenga en cuenta que el problema de selección de la ruta óptima se puede expresar como la elección de una palabra clave con una métrica de máxima verosimilitud o una métrica de distancia mínima .

Esencia del método

El mejor esquema de decodificación para códigos de corrección es la decodificación de máxima verosimilitud. , cuando el decodificador determina un conjunto de probabilidades condicionales correspondientes a todos los vectores de código posibles , y decide a favor de la palabra de código correspondiente al máximo . Para un canal simétrico binario sin memoria (un canal en el que las probabilidades de transmisión 0 y 1, así como las probabilidades de error de la forma 0 -> 1 y 1 -> 0 son las mismas, los errores en el j-ésimo e i- Los símbolos del código son independientes), el decodificador de máxima verosimilitud se reduce al decodificador de mínima distancia de Hamming . Este último calcula la distancia de Hamming entre la secuencia recibida r y todos los vectores de código posibles y toma una decisión a favor del vector más cercano al recibido. Naturalmente, en el caso general, tal decodificador resulta muy complicado incluso para tamaños de código grandes y prácticamente irrealizable. La estructura característica de los códigos convolucionales (repetibilidad de la estructura fuera de la ventana de longitud ) permite crear un decodificador de máxima verosimilitud bastante aceptable en términos de complejidad.

El principio de funcionamiento del decodificador

La entrada del decodificador recibe un segmento de la secuencia con una longitud superior a la longitud del código del bloque . Llamémoslo la ventana de decodificación. Comparemos todas las palabras clave del código dado (dentro de un segmento de longitud ) con la palabra recibida y seleccionemos la palabra clave más cercana a la recibida. El primer cuadro de información de la palabra clave seleccionada se recibe como una estimación del cuadro de información de la palabra decodificada. Después de eso, se ingresan nuevos símbolos en el decodificador , y los símbolos más antiguos ingresados ​​​​anteriormente se descartan, y el proceso se repite para determinar el siguiente marco de información. Así, el decodificador Viterbi procesa fotograma a fotograma secuencialmente, moviéndose a lo largo de una red similar a la utilizada por el codificador. En un momento dado, el decodificador no sabe en qué nodo se encuentra el codificador y no intenta decodificarlo. En su lugar, el decodificador determina la ruta más probable a cada nodo a partir de la secuencia recibida y determina la distancia entre cada ruta y la secuencia recibida. Esta distancia se llama la medida de la divergencia del camino. Como estimación de la secuencia recibida, se selecciona el segmento con la menor medida de divergencia. El camino con la medida más pequeña de divergencia se llama camino sobreviviente.

Ejemplo

Considere la operación del decodificador Viterbi usando un ejemplo simple. Creemos que la codificación se realiza utilizando un código convolucional (7,5) . Usando el diagrama de Trellis del codificador, intentemos, tomando algún segmento , rastrear la ruta más probable del codificador. En este caso, para cada sección del diagrama Trellis, anotaremos la medida de la divergencia del camino a cada uno de sus nodos. Suponga que se transmite la secuencia de código U = (00000000…) y la secuencia recibida tiene la forma r = (10001000…), es decir, se produjeron errores en el primer y tercer marco de la palabra de código. Como ya hemos visto, el procedimiento de decodificación y el resultado no dependen de la palabra clave transmitida y están determinados únicamente por el error contenido en la secuencia recibida. Por lo tanto, es más fácil suponer que se transmite la secuencia cero, es decir, U = (00000000...). Habiendo recibido el primer par de símbolos (10), el decodificador determina la medida de divergencia para la primera sección de la red, habiendo recibido el siguiente par de símbolos (00), para la segunda sección, etc. Al mismo tiempo, de los caminos incluidos en cada nodo, dejamos el camino con menor divergencia, ya que el camino con mayor divergencia actual ya no puede acortarse en el futuro. Tenga en cuenta que para el ejemplo que se está considerando, a partir del cuarto nivel, la métrica (o medida de divergencia) de la ruta cero es menor que cualquier otra métrica. Como no hubo más errores en el canal, está claro que al final se elegirá este camino como respuesta. Este ejemplo también muestra que las rutas supervivientes pueden diferir entre sí durante bastante tiempo. Sin embargo, en el sexto o séptimo nivel, los primeros siete bordes de todos los caminos supervivientes coincidirán entre sí. En este momento, según el algoritmo de Viterbi, se toma una decisión sobre los símbolos transmitidos, ya que todos los caminos supervivientes salen del mismo vértice, es decir, corresponden a un símbolo de información.

La profundidad a la que se fusionan los caminos supervivientes no se puede calcular por adelantado; es una variable aleatoria que depende de la multiplicidad y probabilidad de errores que se produzcan en el canal. Por lo tanto, en la práctica, normalmente no se espera a que se fusionen las rutas, sino que se establece una profundidad de decodificación fija.

En el paso i), el grado de diferencia entre las métricas de los caminos correcto e incorrecto es suficientemente grande ( , ), es decir, en este caso sería posible limitar la profundidad de decodificación a . Pero a veces, el camino que es más largo a una sección determinada puede resultar ser el más corto al final, por lo que no debe dejarse llevar por la reducción del tamaño de la ventana de decodificación b para simplificar el trabajo del decodificador. En la práctica, la profundidad de decodificación suele elegirse en el rango , donde  es el número de errores corregidos por un código dado. A pesar de la presencia de dos errores en el fragmento recibido, su decodificación se produjo sin error, y la secuencia cero transmitida se aceptará como respuesta.

Véase también

Literatura