¿Cuáles son las alternativas menos exigentes computacionalmente al decodificador Viterbi?

7

¿Cuáles son las alternativas menos exigentes computacionalmente al decodificador Viterbi?

Idealmente, lo que me gustaría es una lista de los métodos aproximados más utilizados, junto con breves ventajas y desventajas.

gyroidben
fuente
¿Pregunta específicamente con respecto a la decodificación de códigos de corrección de errores convolucionales (probablemente la aplicación más conocida)? El algoritmo de Viterbi se puede usar en varias aplicaciones donde se desea la detección de secuencia de máxima verosimilitud.
Jason R
Sí, en eso estaba pensando. Me interesarían tanto los algoritmos específicos de esa aplicación como los métodos de detección de secuencia ML más generales.
gyroidben

Respuestas:

5

Una alternativa directa a un decodificador Viterbi para decodificar códigos convolucionales es un decodificador secuencial. El algoritmo es más simple, pero el rendimiento no es tan bueno. Por ejemplo, las longitudes de restricción comunes para los sistemas que usan la decodificación de Viterbi son típicamente k = 7 o k = 9. Un sistema decodificado con un decodificador secuencial típicamente tiene una longitud de restricción en los años treinta más o menos. La complejidad de un decodificador Viterbi sería prohibitiva a una longitud de restricción tan larga, y el rendimiento de un decodificador secuencial es muy pobre con las cortas longitudes de restricción utilizadas con un decodificador Viterbi.

Otra alternativa sería usar un decodificador APP o MAP, pero estos son más complejos que un decodificador Viterbi (ya que son esencialmente dos decodificadores Viterbi que se ejecutan juntos en direcciones opuestas). Pero si solo quiere decir que no está usando un decodificador "Viterbi" que podría calificar.

Eric Jacobsen
fuente
4

Un enfoque (lejos de ser óptimo):

Un código convolucional de velocidad media se puede ver como dos codificadores de canal codificados multiplicativamente multiplexados. Puede decodificar los dos caminos con los decodificadores multiplicativos inversos y luego combinar los dos caminos. Incluso si hace que los decodificadores creen decisiones suaves, los resultados estarán lejos de ser óptimos, pero deberían ser muy rápidos.

Mark Borgerding
fuente