código convolucional

Tipo de código de corrección de errores mediante convolución

En telecomunicaciones , un código convolucional es un tipo de código de corrección 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. La 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 enrejada utilizando un enrejado invariante en el tiempo. La decodificación enrejada invariante en el tiempo permite que los códigos convolucionales se decodifiquen mediante decisiones suaves con la máxima probabilidad y una complejidad razonable.

La capacidad de realizar una decodificación económica de decisiones suaves de máxima probabilidad es uno de los principales beneficios de los códigos convolucionales. Esto contrasta con los códigos de bloque clásicos, que generalmente están representados por un enrejado variable en el tiempo y, por lo tanto, suelen decodificarse mediante decisiones difíciles. Los códigos convolucionales a menudo se caracterizan por la tasa de código base y la profundidad (o memoria) del codificador . La tasa de código base generalmente se da como , donde n es la tasa de datos de entrada sin procesar y k es la tasa de datos del flujo codificado del canal de salida. n es menor que k 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 las entradas anteriores. La profundidad también se puede dar como el número de elementos de memoria v en el polinomio o el número máximo posible de estados del codificador (normalmente:) . ${\displaystyle [n,k,K]}$ ${\displaystyle n/k}$ ${\displaystyle K-1}$ ${\displaystyle 2^{v}}$

Los códigos convolucionales a menudo se describen como continuos. Sin embargo, también se puede decir que los códigos convolucionales tienen una longitud de bloque arbitraria, en lugar de ser continuos, ya que la mayor parte de la codificación convolucional del mundo real se realiza en bloques de datos. Los códigos de bloque codificados convolucionalmente suelen emplear terminación. La longitud de bloque arbitraria de los códigos convolucionales también se puede contrastar con los códigos de bloque clásicos , que generalmente tienen longitudes de bloque fijas que están determinadas por propiedades algebraicas.

La velocidad de código 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" se puede perforar a una tasa más alta, por ejemplo, simplemente no transmitiendo una parte de los símbolos del código. El rendimiento de un código convolucional perforado generalmente escala bien con la cantidad de paridad transmitida. La capacidad de realizar una decodificación económica por decisión suave en códigos convolucionales, así como la longitud del bloque y la flexibilidad de la velocidad del código de los códigos convolucionales, los hace muy populares para las comunicaciones digitales. ${\displaystyle n/k=1/2}$ ${\displaystyle 7/8}$

Historia

Los códigos convolucionales fueron introducidos en 1955 por Peter Elias . Se pensaba que los códigos convolucionales podían decodificarse con calidad arbitraria a expensas del cálculo y el retraso. En 1967, Andrew Viterbi determinó que los códigos convolucionales podían decodificarse con máxima probabilidad y complejidad razonable utilizando decodificadores basados ​​en enrejado invariantes en el tiempo: el algoritmo de Viterbi . Posteriormente se desarrollaron otros algoritmos decodificadores basados ​​en trellis, incluido el algoritmo de decodificación BCJR .

Claude Berrou inventó los códigos convolucionales sistemáticos recursivos alrededor de 1991. Estos códigos resultaron especialmente útiles para el procesamiento iterativo, incluido el procesamiento de códigos concatenados, como los códigos turbo . ^[1]

Usando 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).

Dónde se utilizan códigos convolucionales

Etapas de codificación de canales en GSM. ^[2] Codificador de bloque y verificación de paridad: parte de detección de errores. Codificador convolucional y decodificador Viterbi – parte de corrección de errores. Intercalado y desintercalado: separación de palabras clave que aumenta en el dominio del tiempo y para evitar distorsiones en ráfagas.

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 3GPP versión 7) ^{[3] [4]} ) y satélite. comunicaciones . ^[5] Estos códigos a menudo se implementan en concatenación con un código de decisión difícil, particularmente Reed-Solomon . Antes de los códigos turbo, tales construcciones eran las más eficientes y se acercaban más al límite de Shannon .

Codificación convolucional

Para codificar datos de forma convolucional, comience con k registros de memoria , cada uno con un bit de entrada. A menos que se especifique lo contrario, todos los registros de memoria comienzan con un valor de 0. El codificador tiene n sumadores de módulo 2 (se puede implementar un sumador de módulo 2 con una única 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 (consulte la figura siguiente). Un bit de entrada m ₁ se introduce en el registro más a la izquierda. Utilizando los polinomios del generador y los valores existentes en los registros restantes, el codificador genera n símbolos. Estos símbolos pueden transmitirse o perforarse dependiendo de la velocidad de código deseada. Ahora desplace los bits todos los valores de registro hacia la derecha ( m ₁ se mueve a m ₀ , m ₀ se mueve a m ₋₁ ) y espere el siguiente bit de entrada. Si no quedan bits de entrada, el codificador continúa desplazándose hasta que todos los registros hayan regresado al estado cero (terminación de bit de vaciado).

Imagen 1. Codificador convolucional no recursivo y no sistemático de velocidad 1/3 con restricción de longitud 3

La siguiente figura es un codificador de velocidad 1 ⁄ 3 ( m ⁄ n ) con una longitud de restricción ( k ) de 3. Los polinomios generadores son G ₁ = (1,1,1), G ₂ = (0,1,1) y G3 = ₍ 1,0,1) . Por tanto, los bits de salida se calculan (módulo 2) de la siguiente manera:

norte ₁ = metro ₁ + metro ₀ + metro ₋₁

norte ₂ = metro ₀ + metro ₋₁

norte ₃ = metro ₁ + metro ₋₁ .

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

• Repite sistemáticamente la estructura del mensaje antes de codificarlo.
• cambios no sistemáticos la estructura inicial

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

• 
  Una breve ilustración de código convolucional no sistemático.
• 
  Una breve ilustración del código convolucional sistemático.

Códigos recursivos y no recursivos

El codificador de la imagen de arriba es un codificador no recursivo . A continuación se muestra un ejemplo de recursivo y como tal admite una estructura de retroalimentación:

Imagen 2. Codificador convolucional sistemático recursivo de 8 estados de velocidad 1/2. Utilizado como código constituyente en el Código Turbo 3GPP 25.212.

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 con símbolos de salida que 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, sino una práctica común.

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

Los códigos convolucionales sistemáticos recursivos (RSC) se han vuelto más populares debido a su uso en códigos Turbo. Los códigos sistemáticos recursivos también se denominan códigos pseudosistemáticos.

Otros códigos RSC y aplicaciones de ejemplo incluyen:

Imagen. 3. Código convolucional sistemático recursivo (RSC) de dos estados. También llamado "acumulador".

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

Imagen. 4. Código convolucional sistemático (RSC) recursivo de cuatro estados.

Útil para SCCC y códigos turbo multidimensionales.

Imagen. 5. Código convolucional sistemático recursivo (RSC) de dieciséis estados.

Útil como código constituyente en códigos turbo de baja tasa de error para aplicaciones como enlaces por satélite. También apto como código exterior SCCC.

Respuesta al impulso, función de transferencia y longitud de la restricción.

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

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

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

Un codificador convolucional es un sistema lineal discreto 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 impulsiva se conecta con una función de transferencia mediante 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 del polinomio de , y la longitud de la restricción se define como . 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. ${\displaystyle H_{i}(1/z)\,}$ ${\displaystyle K=m+1\,}$

diagrama de enrejado

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

Imagine que el codificador (que se muestra en la imagen 1, arriba) tiene '1' en la celda de memoria izquierda ( m ₀ ) y '0' en la derecha ( m ₋₁ ). ( m ₁ no es realmente una celda de memoria porque representa un valor actual). Designaremos dicho estado como "10". Según un bit de entrada, el codificador en el siguiente turno puede convertir al estado "01" o al estado "11". Se puede ver que no todas las transiciones son posibles (por ejemplo, un decodificador no puede convertir del estado "10" al estado "00" o incluso permanecer en el estado "10").

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

Imagen 6. Un diagrama de rejilla para el codificador en Img.1. Un camino a través del enrejado se muestra como una línea roja. Las líneas continuas indican transiciones donde se ingresa un "0" y las líneas discontinuas donde se ingresa un "1".

Una secuencia codificada real se puede representar como una ruta en este gráfico. Una ruta válida se muestra en rojo como 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 (que se ajuste al gráfico) más cercana. Los algoritmos de decodificación reales explotan esta idea.

Distancia libre y distribución de errores.

Curvas teóricas de tasa de error de bits de QPSK codificado (recursivo y no recursivo, decisión suave), canal de ruido blanco gaussiano aditivo. Las curvas se distinguen ligeramente por aproximadamente las mismas distancias libres y pesos.

La distancia libre ^[7] ( d ) es la distancia mínima de Hamming entre diferentes secuencias codificadas. La capacidad de corrección ( t ) de un código convolucional es la cantidad de errores que el código puede corregir. 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 múltiples grupos de errores t cuando están relativamente separados.

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 popular para este problema es entrelazar datos antes de la codificación convolucional, de modo que el código del bloque externo (generalmente Reed-Solomon ) pueda corregir la mayoría de los errores.

Decodificando códigos convolucionales

Curvas de tasa de error de bits para códigos convolucionales con diferentes opciones de modulaciones digitales ( QPSK, 8-PSK , 16-QAM, 64-QAM ) y algoritmos LLR . ^{[8] [9]} (Exacto ^[10] y Aproximado ^[11] ) sobre canal de ruido blanco gaussiano aditivo.

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

Los códigos de longitud de restricción más larga se decodifican de manera más práctica con cualquiera de varios 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 probabilidad, pero su complejidad aumenta sólo ligeramente con la longitud de la restricción, lo que permite el uso de códigos fuertes y con una longitud de restricción larga. Dichos códigos se utilizaron en el programa Pioneer de principios de la década de 1970 para Júpiter y Saturno, pero dieron paso a códigos más cortos, decodificados por Viterbi, generalmente concatenados con grandes códigos de corrección de errores Reed-Solomon que intensifican la curva general de tasa de error de bits y producen tasas de errores residuales no detectados extremadamente bajas.

Tanto los algoritmos de Viterbi como los de decodificación secuencial devuelven decisiones difíciles: los bits que forman la palabra clave más probable. Se puede agregar una medida de confianza aproximada a cada bit mediante el uso del algoritmo de Viterbi de salida suave . Las decisiones suaves máximas a posteriori (MAP) para cada bit se pueden obtener mediante el uso del algoritmo BCJR .

Códigos convolucionales populares

Registro de desplazamiento para el polinomio de código convolucional (7, [171, 133]). Sucursales: , . Todas las operaciones matemáticas deben realizarse en módulo 2. ${\displaystyle h^{1}=171_{o}=[1111001]_{b}}$ ${\displaystyle h^{2}=133_{o}=[1011011]_{b}}$

Curvas teóricas de tasa de error de bits de QPSK codificado (decisión suave), canal de ruido blanco gaussiano aditivo. Las longitudes de restricción más largas producen códigos más potentes, pero la complejidad del algoritmo de Viterbi aumenta exponencialmente con las longitudes de restricción, lo que limita estos códigos más potentes a misiones en el espacio profundo donde el rendimiento adicional vale fácilmente la mayor complejidad del decodificador.

De hecho, en la industria se utilizan estructuras de códigos convolucionales predefinidos obtenidos durante investigaciones científicas. Esto se relaciona con la posibilidad de seleccionar códigos convolucionales catastróficos (provoca 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. ^[12]

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

El código convolucional con una longitud limitada de 2 y una velocidad de 1/2 se utiliza en GSM como técnica de corrección de errores. ^[13]

Códigos convolucionales perforados

Códigos convolucionales con velocidades de código de 1/2 y 3/4 (y longitud de restricción 7, decisión suave, 4-QAM/QPSK/OQPSK). ^[14]

Se puede diseñar código convolucional con cualquier tasa de código basándose en la selección polinomial; ^[15] sin embargo, en la práctica, a menudo se utiliza un procedimiento de perforación para lograr la velocidad de código requerida. La perforación es una técnica utilizada para crear un código de tasa m / n a partir de un código de tasa baja "básico" (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 punción son las más utilizadas:

Por ejemplo, si queremos crear un código con velocidad 2/3 usando la matriz apropiada de la tabla anterior, debemos tomar una salida de codificador básica y transmitir cada primer bit de la primera rama y cada bit de la segunda. El orden específico de transmisión está definido por el estándar de comunicación respectivo.

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

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

Códigos turbo: sustitución de códigos convolucionales

Un código turbo con códigos de componentes 13, 15. ^[16] Los códigos turbo reciben su nombre porque el decodificador utiliza retroalimentación, como un motor turbo. Permutación significa lo mismo que entrelazado. C1 y C2 son códigos convolucionales recursivos. Los códigos convolucionales recursivos y no recursivos no son muy diferentes en el rendimiento de BER; sin embargo, el tipo recursivo se implementa en los códigos convolucionales Turbo debido a mejores propiedades de entrelazado. ^[17]

Los códigos convolucionales simples decodificados por Viterbi ahora están dando paso a los códigos turbo , una nueva clase de códigos convolucionales cortos iterados que se acercan mucho a los límites teóricos impuestos por el teorema de Shannon con mucha menos complejidad de decodificación que el algoritmo de Viterbi en los códigos convolucionales largos que serían necesarios. para el mismo desempeño. La concatenación con un código algebraico externo (por ejemplo, Reed-Solomon ) aborda la cuestión de los niveles de error inherentes a los diseños de códigos turbo.

Ver también

• Código convolucional cuántico

Referencias

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

1. Benedetto, Sergio y Guido Montorsi. "Papel de los códigos convolucionales recursivos en códigos turbo". Cartas electrónicas 31.11 (1995): 858-859.
2. Eberspächer J. et al. Arquitectura, protocolos y servicios GSM. John Wiley e hijos, 2008. p.97
3. Proyecto de asociación de tercera generación (septiembre de 2012). "3GGP TS45.001: Grupo de especificaciones técnicas Red de acceso de radio GSM/EDGE; Capa física en la ruta de radio; Descripción general". Consultado el 20 de julio de 2013.
4. Halonen, Timo, Javier Romero y Juan Melero, eds. Rendimiento GSM, GPRS y EDGE: evolución hacia 3G/UMTS. John Wiley e hijos, 2004. p. 430
5. Butman, SA, LJ Deutsch y RL Miller. "Rendimiento de códigos concatenados para misiones al espacio profundo". Informe de progreso sobre telecomunicaciones y adquisición de datos 42-63, marzo-abril de 1981 (1981): 33-39.
6. Moon, Todd K. "Codificación de corrección de errores". Métodos y algoritmos matemáticos. Jhon Wiley e hijo (2005). pag. 508
7. Moon, Todd K. "Codificación de corrección de errores". Métodos y algoritmos matemáticos. Jhon Wiley e hijo (2005).- p.508
8. LLR versus demodulación de decisión difícil (MathWorks)
9. Estimación de BER para la decodificación de Viterbi de decisiones duras y blandas (MathWorks)
10. Modulación digital: algoritmo LLR exacto (MathWorks)
11. Modulación digital: algoritmo LLR aproximado (MathWorks)
12. Butman, SA, LJ Deutsch y RL Miller. "Rendimiento de códigos concatenados para misiones al espacio profundo". Informe de progreso sobre telecomunicaciones y adquisición de datos 42-63, marzo-abril de 1981 (1981): 33-39.
13. Sistema global de comunicaciones móviles (GSM)
14. Codificación convolucional perforada (MathWorks)
15. "Convertir polinomios de código convolucional en descripción de enrejado - MATLAB poly2trellis".
16. Código turbo
17. Benedetto, Sergio y Guido Montorsi. "Papel de los códigos convolucionales recursivos en códigos turbo". Cartas electrónicas 31.11 (1995): 858-859.

enlaces externos

• El libro de texto en línea: Teoría de la información, inferencia y algoritmos de aprendizaje, de David JC MacKay , analiza 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 mejores comunicaciones digitales
• Códigos convolucionales (MIT)
• Teoría y codificación de la información (TU Ilmenau) Archivado el 30 de agosto de 2017 en Wayback Machine , analiza los códigos convolucionales en la página 48.

Otras lecturas

Publicaciones

• Francisco, Miguel. "Decodificación del bloque decodificador Viterbi: terminación del enrejado y morderse la cola". Xilinx XAPP551 v2. 0, DD (2005): 1-21.
• Chen, Qingchun, Wai Ho Mow y Pingzhi Fan. "Algunos resultados nuevos sobre códigos convolucionales recursivos y sus aplicaciones". Taller de teoría de la información, 2006. ITW'06 Chengdu. IEEE. IEEE, 2006.
• Fiebig, UC. y Patrick Robertson. "Decodificación de borrado y decisión suave en sistemas rápidos de salto de frecuencia con códigos convolucionales, turbo y Reed-Solomon". Transacciones IEEE sobre Comunicaciones 47.11 (1999): 1646-1654.
• Bhaskar, Vidhyacharan y Laurie L. Joiner. "Rendimiento de códigos convolucionales perforados en comunicaciones CDMA asíncronas en perfectas condiciones de seguimiento de fase". Computadoras e ingeniería eléctrica 30.8 (2004): 573-592.
• Modestino, J. y Shou Mui. "Rendimiento del código convolucional en el canal de desvanecimiento de Rician". Transacciones IEEE sobre comunicaciones 24.6 (1976): 592-606.
• Chen, Yuh-Long y Che-Ho Wei. "Evaluación del rendimiento de códigos convolucionales con MPSK en canales de desvanecimiento de Rician". Actas IEE F-Comunicaciones, radar y procesamiento de señales. vol. 134. N° 2. IET, 1987.