Un decodificador de Viterbi utiliza el algoritmo de Viterbi para decodificar un flujo de bits que se ha codificado mediante un código convolucional o un código trellis .
Existen otros algoritmos para decodificar un flujo codificado convolucionalmente (por ejemplo, el algoritmo de Fano ). El algoritmo de Viterbi es el que consume más recursos, pero realiza la decodificación de máxima probabilidad . Se utiliza con mayor frecuencia para decodificar códigos convolucionales con longitudes de restricción k≤3, pero en la práctica se utilizan valores de hasta k = 15.
La decodificación de Viterbi fue desarrollada por Andrew J. Viterbi y publicada en el artículo Viterbi, A. (abril de 1967). "Límites de error para códigos convolucionales y un algoritmo de decodificación asintóticamente óptimo". Transacciones IEEE sobre teoría de la información . 13 (2): 260–269. doi : 10.1109 / tit.1967.1054010 .
Hay implementaciones tanto de hardware (en módems) como de software de un decodificador Viterbi.
La decodificación de Viterbi se utiliza en el algoritmo de decodificación iterativo de Viterbi .
Implementación de hardware
Un decodificador Viterbi de hardware para código básico (no perforado) generalmente consta de los siguientes bloques principales:
- Unidad métrica de rama (UMB)
- Unidad métrica de ruta (PMU)
- Unidad de rastreo (TBU)
Unidad métrica de rama (UMB)
La función de una unidad métrica de rama es calcular métricas de rama , que son distancias normalizadas entre cada símbolo posible en el alfabeto de código y el símbolo recibido.
Hay decodificadores Viterbi de decisión difícil y decisión suave. Un decodificador de Viterbi de decisión difícil recibe un flujo de bits simple en su entrada y se usa una distancia de Hamming como métrica. Un decodificador de Viterbi de decisión suave recibe un flujo de bits que contiene información sobre la fiabilidad de cada símbolo recibido. Por ejemplo, en una codificación de 3 bits, esta información de fiabilidad se puede codificar de la siguiente manera:
valor | significado | |
---|---|---|
000 | mas fuerte | 0 |
001 | relativamente fuerte | 0 |
010 | relativamente débil | 0 |
011 | más débil | 0 |
100 | más débil | 1 |
101 | relativamente débil | 1 |
110 | relativamente fuerte | 1 |
111 | mas fuerte | 1 |
Por supuesto, no es la única forma de codificar datos de confiabilidad.
La distancia euclidiana al cuadrado se utiliza como métrica para decodificadores de decisión suave.
Unidad métrica de ruta (PMU)
Una unidad de métrica de ruta resume las métricas de la rama para obtener métricas para rutas, donde K es la longitud de restricción del código, una de las cuales puede eventualmente elegirse como óptima . Cada reloj que hacedecisiones, descartando caminos deliberadamente no óptimos. Los resultados de estas decisiones se escriben en la memoria de una unidad de rastreo.
Los elementos centrales de una PMU son las unidades ACS (Agregar-Comparar-Seleccionar) . La forma en que están conectados entre sí se define mediante un diagrama de enrejado de un código específico .
Dado que las métricas de la rama son siempre , debe haber un circuito adicional (que no se muestra en la imagen) que evite que los contadores métricos se desborden. Un método alternativo que elimina la necesidad de monitorear el crecimiento de la métrica de la ruta es permitir que las métricas de la ruta se "reinicien"; Para utilizar este método, es necesario asegurarse de que los acumuladores de métricas de ruta contengan suficientes bits para evitar que los valores "mejores" y "peores" estén a 2 (n-1) entre sí. El circuito de comparación se mantiene esencialmente sin cambios.
Es posible monitorear el nivel de ruido en el flujo de bits entrante monitoreando la tasa de crecimiento de la métrica de la ruta "mejor". Una forma más sencilla de hacer esto es monitorear una sola ubicación o "estado" y verlo pasar "hacia arriba" a través de, digamos, cuatro niveles discretos dentro del rango del acumulador. A medida que pasa hacia arriba a través de cada uno de estos umbrales, se incrementa un contador que refleja el "ruido" presente en la señal entrante.
Unidad de rastreo (TBU)
La unidad de seguimiento restaura una ruta (casi) de máxima probabilidad a partir de las decisiones tomadas por PMU. Como lo hace en sentido inverso, un decodificador viterbi comprende un búfer FILO (primero en entrar, último en salir) para reconstruir un orden correcto.
Tenga en cuenta que la implementación que se muestra en la imagen requiere doble frecuencia. Hay algunos trucos que eliminan este requisito.
Problemas de implementación
Cuantización para decodificación de decisiones suaves
Para aprovechar al máximo los beneficios de la decodificación por decisión suave, es necesario cuantificar la señal de entrada correctamente. El ancho óptimo de la zona de cuantificación se define mediante la siguiente fórmula:
dónde es una densidad espectral de potencia de ruido y k es un número de bits para una decisión suave.
Cálculo métrico euclidiano
La norma al cuadrado () la distancia entre los símbolos recibidos y los reales en el alfabeto de código puede simplificarse aún más en una forma lineal de suma / diferencia, lo que lo hace menos intensivo en computación.
Considere un codificador convolucional 1/2 , que genera 2 bits ( 00 , 01 , 10 u 11 ) por cada bit de entrada ( 1 o 0 ). Estas señales de retorno a cero se traducen en un formulario de no retorno a cero que se muestra al lado.
alfabeto de código | mapeo de vectores |
---|---|
00 | +1, +1 |
01 | +1, −1 |
10 | −1, +1 |
11 | −1, −1 |
Cada símbolo recibido puede representarse en forma vectorial como v r = {r 0 , r 1 }, donde r 0 y r 1 son valores de decisión suave, cuyas magnitudes significan la confiabilidad conjunta del vector recibido, v r .
Cada símbolo en el alfabeto de código puede, igualmente, estar representado por el vector v i = {± 1, ± 1}.
El cálculo real de la métrica de distancia euclidiana es:
Cada término cuadrado es una distancia normalizada, que representa la energía del símbolo. Por ejemplo, la energía del símbolo v i = {± 1, ± 1} puede calcularse como
Por lo tanto, el término de energía de todos los símbolos en el alfabeto de código es constante (en el valor ( normalizado ) 2).
La operación Agregar-Comparar-Seleccionar ( ACS ) compara la distancia métrica entre el símbolo recibido || v r || y 2 símbolos cualesquiera en el alfabeto de código cuyas rutas se fusionen en un nodo en el enrejado correspondiente, || v i (0) || y || v i (1) || . Esto es equivalente a comparar
y
Pero, desde arriba sabemos que la energía de v i es constante (igual al valor (normalizado) de 2), y la energía de v r es la misma en ambos casos. Esto reduce la comparación a una función mínima entre los 2 términos del producto escalar (medio) ,
ya que una operación mínima en números negativos puede interpretarse como una operación máxima equivalente en cantidades positivas.
Cada término de producto escalar puede expandirse como
donde, los signos de cada término dependen de los símbolos, v i (0) y v i (1) , que se comparan. Por lo tanto, el cálculo de la distancia métrica euclidiana al cuadrado para calcular la métrica de la rama se puede realizar con una simple operación de suma / resta.
Rastrear
El enfoque general del rastreo es acumular métricas de ruta hasta cinco veces la longitud de la restricción (5 ( K - 1)), encontrar el nodo con el mayor costo acumulado y comenzar el rastreo desde este nodo.
La regla práctica comúnmente utilizada de una profundidad de truncamiento de cinco veces la memoria (longitud de restricción K -1) de un código convolucional es precisa solo para códigos de tasa 1/2. Para una tasa arbitraria, una regla empírica precisa es 2.5 ( K - 1) / (1− r ) donde r es la tasa de código. [1]
Sin embargo, calcular el nodo que ha acumulado el mayor costo (ya sea la métrica de ruta integral más grande o más pequeña) implica encontrar los máximos o mínimos de varios números (generalmente 2 K -1 ), lo que puede llevar mucho tiempo cuando se implementa en sistemas de hardware integrados.
La mayoría de los sistemas de comunicación emplean decodificación de Viterbi que involucra paquetes de datos de tamaños fijos, con un patrón fijo de bit / byte al principio o al final del paquete de datos. Utilizando el patrón conocido de bit / byte como referencia, el nodo de inicio puede establecerse en un valor fijo, obteniendo así una ruta de máxima probabilidad perfecta durante el rastreo.
Limitaciones
Una implementación física de un decodificador de Viterbi no producirá un flujo de máxima verosimilitud exacta debido a la cuantificación de la señal de entrada, las métricas de rama y ruta y la longitud de seguimiento finita . Las implementaciones prácticas se acercan dentro de 1 dB del ideal.
La salida de un decodificador Viterbi, al decodificar un mensaje dañado por un canal gaussiano aditivo, tiene errores agrupados en ráfagas de errores. [2] [3] Single-de corrección de errores códigos solo no puede corregir tales ráfagas, por lo que o bien el código convolucional y el decodificador Viterbi deben diseñarse lo suficientemente potente como para reducir los errores a una velocidad aceptable, o estallan códigos correctores de errores obligada ser usado.
Códigos perforados
Un decodificador de hardware viterbi de códigos perforados se implementa comúnmente de tal manera:
- Un depunturador, que transforma el flujo de entrada en el flujo que parece un flujo original (no perforado) con marcas de BORRAR en los lugares donde se borraron los bits.
- Un decodificador viterbi básico que comprende estas marcas de BORRAR (es decir, que no las usa para el cálculo de métricas de rama)
Implementación de software
Una de las operaciones que consumen más tiempo es una mariposa ACS, que generalmente se implementa utilizando un lenguaje ensamblador y extensiones de conjunto de instrucciones apropiadas (como SSE2 ) para acelerar el tiempo de decodificación.
Aplicaciones
El algoritmo de decodificación de Viterbi se utiliza ampliamente en las siguientes áreas:
- Radiocomunicación: TV digital ( ATSC , QAM , DVB-T , etc.), radioenlace , comunicaciones por satélite , modo digital PSK31 para radioaficionados .
- Decodificación de modulación codificada en rejilla (TCM), la técnica utilizada en los módems de línea telefónica para exprimir una alta eficiencia espectral de las líneas telefónicas analógicas de ancho de banda de 3 kHz.
- Dispositivos de almacenamiento informático, como unidades de disco duro .
- Reconocimiento automático de voz
Referencias
- ^ B. Moision, "Una regla práctica de profundidad de truncamiento para códigos convolucionales", 2008 Taller de aplicaciones y teoría de la información, San Diego, CA, 2008, págs. 555-557, doi : 10.1109 / ITA.2008.4601052 .
- ↑ Stefan Host, Rolf Johannesson, Dmitrij K. Zigangirod, Kamil Sh. Zigangirod y Viktor V. Zyablod. "Sobre la distribución de las longitudes de ráfagas de error de salida para la decodificación de Viterbi de códigos convolucionales" .
- ^ Curry, SJ; Harmon, WD "Un límite en la longitud de ráfaga de error del decodificador de Viterbi" .
enlaces externos
- Forney, G. David, Jr (29 de abril de 2005). "El algoritmo de Viterbi: una historia personal". arXiv : cs / 0504020 .
- Detalles sobre la decodificación de Viterbi, así como bibliografía .
- Explicación del algoritmo de Viterbi con enfoque en problemas de implementación de hardware .
- r = 1/6 k = 15 codificación para la misión Cassini a Saturno .
- Generador en línea de decodificadores Viterbi software optimizados (GPL) .
- Software decodificador GPL Viterbi para cuatro códigos estándar .
- Descripción de un decodificador de k = 24 Viterbi, que se cree que es el más grande jamás utilizado en la práctica .
- Hardware decodificador genérico de Viterbi (GPL) .