Código convolucional

En telecomunicaciones , un código convolucional es un tipo de código corrector de errores que genera símbolos de paridad mediante la aplicación deslizante de una función polinómica booleana a un flujo de datos. Esta aplicación deslizante representa la convolución del codificador sobre los datos, lo que da origen al término «codificación convolucional». La naturaleza deslizante de los códigos convolucionales facilita la decodificación de enrejado mediante un enrejado invariante en el tiempo. La decodificación de enrejado invariante en el tiempo permite decodificar los códigos convolucionales mediante decisión suave de máxima verosimilitud con una complejidad razonable.

La capacidad de realizar una decodificación de decisión suave de máxima verosimilitud económica es uno de los principales beneficios de los códigos convolucionales. Esto contrasta con los códigos de bloque clásicos, que generalmente se representan mediante una estructura enrejada variable en el tiempo y, por lo tanto, suelen decodificarse mediante una decisión dura. Los códigos convolucionales se caracterizan a menudo por la tasa de codificación base y la profundidad (o memoria) del codificador.${\displaystyle [n,k,K]}$La tasa de código base se suele dar como${\displaystyle k/n}$donde k es la tasa de datos de entrada sin procesar y n es la tasa de datos del flujo codificado del canal de salida. k es menor que n porque la codificación de canal inserta redundancia en los bits de entrada. La memoria a menudo se denomina "longitud de restricción" K , donde la salida es una función de la entrada actual, así como de la anterior.${\displaystyle K-1}$entradas. ^{[ 1 ]} La profundidad también puede darse como el número de elementos de memoria v en el polinomio o el número máximo posible de estados del codificador (típicamente:${\displaystyle 2^{v}}$).

Los códigos convolucionales suelen describirse como continuos. Sin embargo, también puede decirse que tienen una longitud de bloque arbitraria, en lugar de ser continuos, ya que la mayoría de las codificaciones convolucionales en el mundo real se realizan sobre bloques de datos. Los códigos de bloque codificados convolucionalmente suelen emplear terminación. La longitud de bloque arbitraria de los códigos convolucionales contrasta con la de los códigos de bloque clásicos , que generalmente tienen longitudes de bloque fijas determinadas por propiedades algebraicas.

La tasa de codificación de un código convolucional se modifica comúnmente mediante perforación de símbolos . Por ejemplo, un código convolucional con una tasa de código 'madre'${\displaystyle n/k=1/2}$puede perforarse a una tasa más alta de, por ejemplo,${\displaystyle 7/8}$Simplemente al no transmitir una parte de los símbolos del código. El rendimiento de un código convolucional perforado generalmente aumenta con la cantidad de paridad transmitida. La capacidad de realizar una decodificación de decisión suave económica en códigos convolucionales, así como la flexibilidad en la longitud del bloque y la tasa de codificación de estos códigos, los hace muy populares para las comunicaciones digitales.

Los códigos convolucionales fueron introducidos en 1955 por Peter Elias . Se creía que podían decodificarse con una calidad arbitraria a costa de un mayor coste computacional y una mayor latencia. En 1967, Andrew Viterbi determinó que los códigos convolucionales podían decodificarse mediante máxima verosimilitud con una complejidad razonable utilizando decodificadores basados ​​en enrejados invariantes en el tiempo: el algoritmo de Viterbi . Posteriormente se desarrollaron otros algoritmos de decodificación basados ​​en enrejados, incluido el algoritmo de decodificación BCJR .

Los códigos convolucionales sistemáticos recursivos fueron inventados por Claude Berrou alrededor de 1991. Estos códigos demostraron ser especialmente útiles para el procesamiento iterativo, incluido el procesamiento de códigos concatenados como los códigos turbo . ^{[ 2 ]}

Utilizando la terminología "convolucional", un código convolucional clásico podría considerarse un filtro de respuesta de impulso finito (FIR), mientras que un código convolucional recursivo podría considerarse un filtro de respuesta de impulso infinito (IIR).

Los códigos convolucionales se utilizan ampliamente para lograr una transferencia de datos confiable en numerosas aplicaciones, como video digital , radio, comunicaciones móviles (por ejemplo, en redes GSM, GPRS, EDGE y 3G (hasta la versión 7 de 3GPP) ^{[ 4 ] [ 5 ]} ) y comunicaciones por satélite . ^{[ 6 ]} Estos códigos a menudo se implementan en concatenación con un código de decisión dura, en particular Reed-Solomon . Antes de los códigos turbo, tales construcciones eran las más eficientes, acercándose más al límite de Shannon .

Para codificar datos de forma convolucional, se empieza con k registros de memoria , cada uno con un bit de entrada. Salvo que se especifique lo contrario, todos los registros de memoria comienzan con un valor de 0. El codificador tiene n sumadores módulo 2 (un sumador módulo 2 se puede implementar con una sola puerta XOR booleana , donde la lógica es: 0+0 = 0 , 0+1 = 1 , 1+0 = 1 , 1+1 = 0 ) y n polinomios generadores , uno para cada sumador (véase la figura siguiente). Se introduce un bit de entrada m _{1 en el registro más a la izquierda. Utilizando los polinomios generadores y los valores existentes en los registros restantes, el codificador genera} n símbolos. Estos símbolos pueden transmitirse o descartarse según la tasa de codificación deseada. A continuación, se desplazan todos los valores de los registros hacia la derecha ( m ₁ se mueve a m ₀ , m ₀ se mueve a m ₋₁ ) y se espera el siguiente bit de entrada. Si no quedan bits de entrada, el codificador continúa desplazándose hasta que todos los registros hayan vuelto al estado cero (terminación por borrado de bits).        

La figura siguiente muestra un codificador de tasa 1/3 ( m / n ) con una longitud de restricción ( k ) de 3. Los polinomios generadores son _G1 = (1,1,1), G2 = (0,1,1) y G3 = (1,0,1) _{. Por lo tanto, los} bits de salida se calculan (módulo 2) de la siguiente manera:

n ₁ = m ₁ + m ₀ + m ₋₁

n ₂ = m ₀ + m ₋₁

n ₃ = m ₁ + m ₋₁ .

Los códigos convolucionales pueden ser sistemáticos o no sistemáticos:

• El método sistemático repite la estructura del mensaje antes de la codificación.
• cambios no sistemáticos en la estructura inicial

Los códigos convolucionales no sistemáticos son más populares debido a su mejor inmunidad al ruido. Esto se relaciona con la distancia libre del código convolucional. ^{[ 7 ]}

• 
  Un breve ejemplo de código convolucional no sistemático.
• 
  Una breve ilustración de un código convolucional sistemático.

El codificador de la imagen superior es un codificador no recursivo . Aquí hay un ejemplo de uno recursivo y, como tal, admite una estructura de retroalimentación:

El codificador de ejemplo es sistemático porque los datos de entrada también se utilizan en los símbolos de salida (Salida 2). Los códigos cuyos símbolos de salida no incluyen los datos de entrada se denominan no sistemáticos.

Los códigos recursivos suelen ser sistemáticos y, a la inversa, los códigos no recursivos suelen ser no sistemáticos. No es un requisito estricto, pero sí una práctica común.

El codificador de ejemplo en la imagen 2 es un codificador de 8 estados porque los 3 registros crearán 8 estados posibles del codificador (2 ³ ). Un decodificador enrejado correspondiente también utilizará normalmente 8 estados.

Los códigos convolucionales sistemáticos recursivos (RSC) se han popularizado gracias a su uso en los códigos Turbo. Estos códigos también se conocen como códigos pseudosistemáticos.

Otros códigos RSC y ejemplos de aplicaciones incluyen:

Útil para la implementación de códigos LDPC y como código constituyente interno para códigos convolucionales concatenados en serie (SCCC).

Útil para códigos turbo SCCC y multidimensionales.

Útil como código constituyente en códigos turbo de baja tasa de error para aplicaciones como enlaces satelitales. También es adecuado como código externo SCCC.

Un codificador convolucional se denomina así porque realiza una convolución del flujo de entrada con las respuestas impulsionales del codificador :

${\displaystyle y_{i}^{j}=\sum _ {k=0}^{\infty }h_{k}^{j}x_{ik}=(x*h^{j})[i],}$

donde x es una secuencia de entrada, y ^j es una secuencia de salida j , h ^j es una respuesta impulsional para la salida j y${\displaystyle {*}}$denota convolución.

Un codificador convolucional es un sistema discreto lineal invariante en el tiempo . Cada salida de un codificador puede describirse mediante su propia función de transferencia , que está estrechamente relacionada con el polinomio generador. Una respuesta impulsional está conectada con una función de transferencia a través de la transformada Z.

Las funciones de transferencia para el primer codificador (no recursivo) son:

• ${\displaystyle H_{1}(z)=1+z^{-1}+z^{-2},\,}$
• ${\displaystyle H_{2}(z)=z^{-1}+z^{-2},\,}$
• ${\displaystyle H_{3}(z)=1+z^{-2}.\,}$

Las funciones de transferencia para el segundo codificador (recursivo) son:

• ${\displaystyle H_{1}(z)={\frac {1+z^{-1}+z^{-3}}{1-z^{-2}-z^{-3}}},\,}$
• ${\displaystyle H_{2}(z)=1.\,}$

Definir m por

${\displaystyle m=\max _{i}\operatorname {polydeg} (H_{i}(1/z))\,}$

donde, para cualquier función racional${\displaystyle f(z)=P(z)/Q(z)\,}$,

${\displaystyle \operatorname {polydeg} (f)=\max(\deg(P),\deg(Q))\,}$.

Entonces m es el máximo de los grados polinómicos de la

${\displaystyle H_{i}(1/z)\,}$y la longitud de la restricción se define como${\displaystyle K=m+1\,}$Por ejemplo, en el primer ejemplo la longitud de la restricción es 3, y en el segundo la longitud de la restricción es 4.

Un codificador convolucional es una máquina de estados finitos . Un codificador con n celdas binarias tendrá 2ⁿ ^estados .

Imaginemos que el codificador (mostrado en la imagen 1) tiene un '1' en la celda de memoria izquierda ( _m₀ ) y un '0' en la derecha ( mₒ1 ). ( m₁ no es realmente una celda de memoria _{, ya que representa un valor actual). Designaremos este estado como "10". Según el bit de entrada ,} en el siguiente turno el codificador puede pasar al estado "01" o al estado "11". Cabe destacar que no todas las transiciones son posibles (por ejemplo, un decodificador no puede pasar del estado "10" al estado "00" ni permanecer en el estado "10").

Todas las transiciones posibles se pueden mostrar como se indica a continuación:

Una secuencia codificada real puede representarse como una ruta en este gráfico. Una ruta válida se muestra en rojo a modo de ejemplo.

Este diagrama nos da una idea sobre la decodificación : si una secuencia recibida no se ajusta a este gráfico, entonces se recibió con errores, y debemos elegir la secuencia correcta más cercana (que se ajuste al gráfico). Los algoritmos de decodificación reales aprovechan esta idea.

La distancia libre ^{[ 8 ]} ( d ) es la distancia de Hamming mínima entre diferentes secuencias codificadas. La capacidad de corrección ( t ) de un código convolucional es el número de errores que puede corregir el código. Se puede calcular como

${\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor .}$

Dado que un código convolucional no utiliza bloques, sino que procesa un flujo de bits continuo, el valor de t se aplica a una cantidad de errores ubicados relativamente cerca unos de otros. Es decir, generalmente se pueden corregir varios grupos de t errores cuando están relativamente alejados entre sí.

La distancia libre puede interpretarse como la longitud mínima de una "ráfaga" errónea en la salida de un decodificador convolucional. El hecho de que los errores aparezcan como "ráfagas" debe tenerse en cuenta al diseñar un código concatenado con un código convolucional interno. La solución más común para este problema consiste en intercalar los datos antes de la codificación convolucional, de modo que el código de bloque externo (generalmente Reed-Solomon ) pueda corregir la mayoría de los errores.

Existen varios algoritmos para decodificar códigos convolucionales. Para valores relativamente pequeños de k , el algoritmo de Viterbi es el más utilizado, ya que ofrece un rendimiento de máxima verosimilitud y es altamente paralelizable. Por lo tanto, los decodificadores de Viterbi son fáciles de implementar en hardware VLSI y en software en CPU con conjuntos de instrucciones SIMD .

Los códigos de mayor longitud de restricción se decodifican de forma más práctica con cualquiera de los diversos algoritmos de decodificación secuencial , de los cuales el algoritmo de Fano es el más conocido. A diferencia de la decodificación de Viterbi, la decodificación secuencial no es de máxima verosimilitud, pero su complejidad aumenta solo ligeramente con la longitud de la restricción, lo que permite el uso de códigos robustos de gran longitud de restricción. Dichos códigos se utilizaron en el programa Pioneer de principios de la década de 1970 para las misiones a Júpiter y Saturno, pero posteriormente fueron reemplazados por códigos más cortos decodificados mediante Viterbi, generalmente concatenados con códigos de corrección de errores Reed-Solomon de gran tamaño que acentúan la curva general de tasa de error de bits y producen tasas de error residual no detectado extremadamente bajas.

Tanto el algoritmo de Viterbi como el de decodificación secuencial devuelven decisiones definitivas: los bits que forman la palabra clave más probable. Se puede añadir una medida de confianza aproximada a cada bit mediante el algoritmo de Viterbi de salida suave . Las decisiones suaves de máxima probabilidad a posteriori (MAP) para cada bit se pueden obtener mediante el algoritmo BCJR .

De hecho, en la industria se utilizan estructuras de códigos convolucionales predefinidas obtenidas durante investigaciones científicas. Esto se relaciona con la posibilidad de seleccionar códigos convolucionales catastróficos (que provocan un mayor número de errores).

Un código convolucional decodificado por Viterbi especialmente popular, utilizado al menos desde el programa Voyager , tiene una longitud de restricción K de 7 y una tasa r de 1/2. ^{[ 13 ]}

Mars Pathfinder , Mars Exploration Rover y la sonda Cassini a Saturno utilizan un K de 15 y una tasa de 1/6; este código funciona aproximadamente 2  dB mejor que el más simple.${\displaystyle K=7}$codificar a un coste 256 veces mayor en complejidad de decodificación (en comparación con los códigos de las misiones Voyager).

El código convolucional con una longitud de restricción de 2 y una tasa de 1/2 se utiliza en GSM como técnica de corrección de errores. ^{[ 14 ]}

Se puede diseñar un código convolucional con cualquier tasa de codificación mediante selección polinómica; ^{[ 16 ]} sin embargo, en la práctica, a menudo se utiliza un procedimiento de perforación para lograr la tasa de codificación requerida. La perforación es una técnica que se utiliza para crear un código de tasa m / n a partir de un código básico de baja tasa (por ejemplo, 1/ n ). Se logra eliminando algunos bits en la salida del codificador. Los bits se eliminan según una matriz de perforación . Las siguientes matrices de perforación son las más utilizadas:

Por ejemplo, si queremos generar un código con una tasa de 2/3 utilizando la matriz correspondiente de la tabla anterior, debemos tomar la salida de un codificador básico y transmitir el primer bit de cada rama y el primer bit de cada rama de la segunda. El orden específico de transmisión viene definido por el estándar de comunicación correspondiente.

Los códigos convolucionales punteados se utilizan ampliamente en las comunicaciones por satélite , por ejemplo, en los sistemas Intelsat y en la radiodifusión de vídeo digital .

Los códigos convolucionales punteados también se denominan "perforados".

Los códigos convolucionales simples decodificados con Viterbi están dando paso a los códigos turbo , una nueva clase de códigos convolucionales cortos iterados que se aproximan a los límites teóricos impuestos por el teorema de Shannon con una complejidad de decodificación mucho menor que la que requeriría el algoritmo de Viterbi para los códigos convolucionales largos con el mismo rendimiento. La concatenación con un código algebraico externo (por ejemplo, Reed-Solomon ) resuelve el problema de los umbrales de error inherentes a los diseños de códigos turbo.

• Código convolucional cuántico

•  Este artículo incorpora material de dominio público de la Norma Federal 1037C . Administración de Servicios Generales . Archivado del original el 22 de enero de 2022.

• El libro de texto en línea "Teoría de la información, inferencia y algoritmos de aprendizaje" , de David JC MacKay , trata sobre los códigos convolucionales en el capítulo 48.
• La página de códigos de corrección de errores (ECC)
• Explicaciones de Matlab
• Fundamentos de los decodificadores convolucionales para mejorar las comunicaciones digitales.
• Códigos convolucionales (MIT)
• El libro "Teoría de la Información y la Codificación" (TU Ilmenau), archivado el 30 de agosto de 2017 en Wayback Machine , trata sobre códigos convolucionales en la página 48.