Descodificador Viterbi

Un decodificador Viterbi utiliza el algoritmo Viterbi para decodificar un flujo de bits que ha sido codificado utilizando un código convolucional o un código trellis .

Existen otros algoritmos para decodificar un flujo codificado de forma convolucional (por ejemplo, el algoritmo Fano ). El algoritmo de Viterbi es el que consume más recursos, pero realiza la decodificación de máxima verosimilitud . 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). "Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm". IEEE Transactions on Information Theory . 13 (2): 260–269. doi :10.1109/tit.1967.1054010.

Existen 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 de Viterbi iterativo .

Un decodificador Viterbi de hardware para código básico (no perforado) generalmente consta de los siguientes bloques principales:

• Unidad métrica de rama (BMU)
• Unidad métrica de trayectoria (PMU)
• Unidad de rastreo (TBU)

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 del código y el símbolo recibido.

Existen decodificadores de Viterbi de decisión dura y de decisión blanda. Un decodificador de Viterbi de decisión dura recibe un flujo de bits simple en su entrada y se utiliza una distancia de Hamming como métrica. Un decodificador de Viterbi de decisión blanda 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:

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 decisiones suaves.

Una unidad de métrica de ruta resume las métricas de las ramas para obtener métricas para las rutas, donde K es la longitud de restricción del código, una de las cuales puede eventualmente elegirse como óptima . Cada reloj toma decisiones, descartando rutas deliberadamente no óptimas. Los resultados de estas decisiones se escriben en la memoria de una unidad de seguimiento. $Estilo de visualización 2^{K-1}}$$Estilo de visualización 2^{K-1}}$

Los elementos centrales de una PMU son las unidades ACS (Add-Compare-Select) . La forma en que se conectan entre sí está definida por un diagrama de enrejado de un código específico .

Dado que las métricas de las ramas son siempre , debe haber un circuito adicional (no se muestra en la imagen) que evite que los contadores de métricas se desborden. Un método alternativo que elimina la necesidad de monitorear el crecimiento de las métricas de ruta es permitir que las métricas de ruta se "reinicien"; para usar 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 dentro de 2 ^(n-1) entre sí. El circuito de comparación permanece esencialmente sin cambios. ${\displaystyle \geq 0}$

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 hacerlo es monitorear una sola ubicación o "estado" y observar cómo pasa "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.

La unidad de rastreo inverso restaura una ruta de máxima verosimilitud (casi) a partir de las decisiones tomadas por la PMU. Como lo hace en dirección inversa, un decodificador de Viterbi incluye 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 el doble de frecuencia. Hay algunos trucos que eliminan este requisito.

Para aprovechar al máximo los beneficios de la decodificación de decisión suave, es necesario cuantificar correctamente la señal de entrada. El ancho óptimo de la zona de cuantificación se define mediante la siguiente fórmula:

${\displaystyle \,\!T={\sqrt {\frac {N_{0}}{2^{k}}}},}$

donde es una densidad espectral de potencia de ruido y k es un número de bits para una decisión suave. $Estilo de visualización N_{0}$

La distancia de la norma al cuadrado ( ) entre los símbolos recibidos y los reales en el alfabeto del código se puede simplificar aún más en una forma de suma/diferencia lineal, lo que la hace menos intensiva en términos computacionales. ${\displaystyle \ell_{2}}$

Considere un código 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 a una forma sin retorno a cero que se muestra al lado.

Cada símbolo recibido puede representarse en forma vectorial como v _r = {r ₀ , r ₁ }, donde r ₀ y r ₁ son valores de decisión suaves, cuyas magnitudes significan la confiabilidad conjunta del vector recibido, v _r .

Cada símbolo del alfabeto codificado puede, asimismo, representarse mediante el vector v _i = {±1, ±1}.

El cálculo real de la métrica de la distancia euclidiana es:

${\displaystyle \,\!D=({\overrightarrow {v_{r}}}-{\overrightarrow {v_{i}}})^{2}={\overrightarrow {v_{r}}}^{2}-2{\overrightarrow {v_{r}}}{\overrightarrow {v_{i}}}+{\overrightarrow {v_{i}}}^{2}}$

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

${\displaystyle \,\!{\overrightarrow {v_{i}}}^{2}=(\pm 1)^{2}+(\pm 1)^{2}=2}$

Por lo tanto, el término de energía de todos los símbolos del alfabeto codificado 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 cualesquiera 2 símbolos en el alfabeto de código cuyas rutas se fusionan en un nodo en el enrejado correspondiente, ||v _i ⁽⁰⁾ || y ||v _i ⁽¹⁾ || . Esto es equivalente a comparar

${\displaystyle \,\!D_{0}={\overrightarrow {v_{r}}}^{2}-2{\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{0}}}+{\overrightarrow {v_{i}^{0}}}^{2}}$

y

${\displaystyle \,\!D_{1}={\overrightarrow {v_{r}}}^{2}-2{\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{1}}}+{\overrightarrow {v_{i}^{1}}}^{2}}$

Pero, de lo anterior 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 (del medio) ,

${\displaystyle \,\!\min(-2{\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{0}}},-2{\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{1}}})=\max({\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{0}}},{\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{1}}})}$

ya que una operación mínima sobre números negativos puede interpretarse como una operación máxima equivalente sobre cantidades positivas.

Cada término del producto escalar puede expandirse como

${\displaystyle \,\!\max(\pm r_{0}\pm r_{1},\pm r_{0}\pm r_{1})}$

donde los signos de cada término dependen de los símbolos, v _i ⁽⁰⁾ y v _i ⁽¹⁾ , 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.

El enfoque general para el rastreo es acumular métricas de ruta de hasta cinco veces la longitud de restricción (5 ( K - 1)), encontrar el nodo con el mayor costo acumulado y comenzar el rastreo desde este nodo.

La regla general de uso común 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 general precisa es 2,5( K - 1)/(1− r ), donde r es la tasa del 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 la decodificación Viterbi, que implica paquetes de datos de tamaños fijos, con un patrón de bits / bytes fijo al principio o al final del paquete de datos. Al utilizar el patrón de bits / bytes conocido como referencia, el nodo de inicio puede configurarse en un valor fijo, obteniendo así una ruta de máxima verosimilitud perfecta durante el rastreo.

Una implementación física de un decodificador Viterbi no producirá un flujo de máxima verosimilitud exacto debido a la cuantificación de la señal de entrada, las métricas de ramificación y ruta y la longitud finita del rastreo . Las implementaciones prácticas se aproximan 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]} Los códigos de corrección de errores individuales por sí solos no pueden corregir dichas ráfagas, por lo que el código convolucional y el decodificador Viterbi deben diseñarse lo suficientemente potentes para reducir los errores a una tasa aceptable, o se deben utilizar códigos de corrección de errores en ráfagas .

Un decodificador de hardware Viterbi de códigos perforados se implementa comúnmente de la siguiente manera:

• Un desperforador, que transforma el flujo de entrada en un flujo que parece un flujo original (no perforado) con marcas de BORRAR en los lugares donde se borraron los bits.
• Un decodificador básico de Viterbi que entiende estas marcas de BORRAR (es decir, no las utiliza para el cálculo de la métrica de la rama).

Una de las operaciones que consume 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.

El algoritmo de decodificación de Viterbi se utiliza ampliamente en las siguientes áreas:

• Comunicaciones por radio: TV digital ( ATSC , QAM , DVB-T , etc.), retransmisión de radio , comunicaciones por satélite , modo digital PSK31 para radioaficionados .
• Decodificación de la modulación codificada por enrejado (TCM), la técnica utilizada en los módems de líneas telefónicas para obtener una alta eficiencia espectral de las líneas telefónicas analógicas con un ancho de banda de 3 kHz.
• Dispositivos de almacenamiento de computadora, como unidades de disco duro .
• Reconocimiento automático de voz

• 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 una bibliografía.
• Explicación del algoritmo de Viterbi con especial atención a los 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 de software optimizado (GPL).
• Software decodificador GPL Viterbi para cuatro códigos estándar.
• Descripción del decodificador Viterbi ak=24, considerado el más grande jamás utilizado en la práctica.
• Hardware decodificador genérico Viterbi (GPL).