De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

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 polinomial booleana a un flujo de datos. La aplicación deslizante representa la "convolución" del codificador sobre los datos, lo que da lugar al término "codificación convolucional". La naturaleza deslizante de los códigos convolucionales facilita la decodificación de Trellis utilizando un Trellis invariante en el tiempo. La decodificación de Trellis invariante en el tiempo permite que los códigos convolucionales sean decodificados por decisión suave de máxima probabilidad con una complejidad razonable.

La capacidad de realizar una decodificación de decisión blanda de máxima probabilidad 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 están representados por un enrejado variable en el tiempo y, por lo tanto, generalmente se decodifican por decisión difícil. Los códigos convolucionales se caracterizan a menudo por la tasa de código base y la profundidad (o memoria) del codificador . La tasa de código base se da típicamente como , donde es la tasa de datos de entrada sin procesar y es la tasa de datos del flujo codificado del canal de salida. es menor que porque la codificación de canal inserta redundancia en los bits de entrada. La memoria a menudo se denomina "longitud de restricción" , donde la salida es una función de la entrada actual y de la anterior.entradas. La profundidad también se puede dar como el número de elementos de memoria en el polinomio o el número máximo posible de estados del codificador (típicamente:) .

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 emplean típicamente 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 tasa de código de un código convolucional se modifica comúnmente mediante la perforación de símbolos . Por ejemplo, un código convolucional con una tasa de código "madre" puede perforarse a una tasa más alta de, por ejemplo, simplemente no transmitiendo una parte de los símbolos de 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 de decisión flexible económica en códigos convolucionales, así como la longitud de bloque y la flexibilidad de la velocidad del código de los códigos convolucionales, los hace muy populares para las comunicaciones digitales.

Historia [ editar ]

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 con una complejidad razonable utilizando decodificadores basados ​​en trellis invariantes en el tiempo: el algoritmo de Viterbi . Posteriormente se desarrollaron otros algoritmos de decodificación basados ​​en trellis, 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 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 [ editar ]

Etapas de codificación de canales en GSM. [2] Codificador de bloque y comprobación de paridad: parte de detección de errores. Codificador convolucional y decodificador Viterbi - parte de corrección de errores. Intercalado y desintercalado: la separación de las palabras de código aumenta en el dominio del tiempo y evita distorsiones por 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 estricta, particularmente Reed-Solomon . Antes de los códigos turbo, tales construcciones eran las más eficientes, acercándose más al límite de Shannon .

Codificación convolucional [ editar ]

Para codificar datos convolucionalmente, 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 modulo-2 sumadores (un sumador de módulo 2 se puede implementar con un solo Boolean puerta XOR , 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 (ver figura a continuación). Un bit de entrada m 1se introduce en el registro más a la izquierda. Usando 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 tasa de código deseada. Ahora bit cambiar todos los valores de registro a la derecha ( m 1 se mueve a m 0 , m 0 se mueve a m -1 ) y esperar 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 de bit de descarga).

Img.1. Tasa de 1/3 codificador convolucional no recursivo, no sistemático con restricción de longitud 3

La figura a continuación es una tasa de 1 / 3 ( m / n ) de codificador con longitud de restricción ( k ) de 3. polinomios generadores están G 1 = (1,1,1), G 2 = (0,1,1) y G 3 = (1,0,1) . Por lo tanto, los bits de salida se calculan (módulo 2) de la siguiente manera:

n 1 = m 1 + m 0 + m −1
n 2 = m 0 + m −1
n 3 = m 1 + m −1 .

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

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

Los códigos convolucionales no sistemáticos son más populares debido a una 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 [ editar ]

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

Img.2. Codificador convolucional sistemático recursivo de tasa 1/2 de 8 estados. Se utiliza como código constitutivo en 3GPP 25.212 Turbo Code.

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 posibles estados del codificador (2 3 ). Un enrejado de decodificador correspondiente normalmente utilizará también 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 pseudo-sistemáticos.

Otros códigos RSC y aplicaciones de ejemplo incluyen:

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

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

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

Útil para SCCC y códigos turbo multidimensionales.

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

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

Respuesta de impulso, función de transferencia y longitud de la restricción [ editar ]

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

donde x es una secuencia de entrada, y j es una secuencia de la salida j , h j es una respuesta de impulso para la salida j y denota convolución.

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

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

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

Definir m por

donde, para cualquier función racional ,

.

Entonces m es el máximo de los grados polinomiales 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.

Diagrama de enrejado [ editar ]

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

Imagine que el codificador (mostrado en Img.1, arriba) tiene '1' en la celda de memoria izquierda ( m 0 ) y '0' en la derecha ( m −1 ). ( m 1 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 para (por ejemplo, un decodificador no puede convertir del estado "10" al estado "00" o incluso permanecer en el estado "10").

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

Img.6. Un diagrama de Trellis 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 las 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 más cercana (que se ajuste al gráfico). Los algoritmos de decodificación reales aprovechan esta idea.

Distancia libre y distribución de errores [ editar ]

Curvas teóricas de tasa de error de bits de QPSK codificado (decisión suave recursiva y no recursiva), canal de ruido gaussiano blanco aditivo. Las curvas se distinguen pequeñas debido a 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 el número de errores que puede corregir el código. Puede calcularse como

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, múltiples grupos de errores t generalmente se pueden corregir cuando están relativamente separados.

La distancia libre se puede interpretar 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 intercalar 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.

Decodificación de códigos convolucionales [ editar ]

Curvas de tasa de error de bit 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 el 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 verosimilitud 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 largos se decodifican de manera más práctica con cualquiera de los 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 solo ligeramente con la longitud de restricción, lo que permite el uso de códigos fuertes de longitud de restricción larga. Tales códigos se usaron 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 aumentan la curva general de tasa de error de bits y producen tasas de error residuales no detectadas extremadamente bajas.

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

Códigos convolucionales populares [ editar ]

Registro de desplazamiento para el polinomio de código convolucional (7, [171, 133]). Ramas: , . Todas las operaciones matemáticas deben realizarse mediante módulo 2.
Curvas teóricas de tasa de error de bit 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 poderosos a misiones en el espacio profundo donde el rendimiento adicional fácilmente vale la pena por la mayor complejidad del decodificador.

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

Un código convolucional descodificado por Viterbi especialmente popular, utilizado al menos desde que el programa Voyager tiene una longitud de restricción de 7 y una tasa r de 1/2. [12]

Mars Pathfinder , Mars Exploration Rover y la sonda Cassini a Saturno utilizan una velocidad 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 × en la complejidad de decodificación (en comparación con los códigos de misión de la 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. [13]

Códigos convolucionales perforados [ editar ]

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

El código convolucional con cualquier tasa de código se puede diseñar basándose en la selección de polinomios; [15] sin embargo, en la práctica, a menudo se utiliza un procedimiento de perforación para lograr la tasa de código requerida. La perforación es una técnica utilizada para hacer 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 perforación son las más utilizadas:

Por ejemplo, si queremos hacer un código con tasa 2/3 usando la matriz apropiada de la tabla anterior, debemos tomar una salida de codificador básico y transmitir cada primer bit desde la primera rama y cada bit desde 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 la radiodifusión de vídeo digital .

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

Códigos turbo: reemplazo de códigos convolucionales [ editar ]

Un código turbo con códigos de componente 13, 15. [16] Los códigos turbo reciben su nombre porque el decodificador usa 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 tan diferentes en el rendimiento de BER, sin embargo, el tipo recursivo se implementa en 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 la misma actuación. La concatenación con un código algebraico externo (por ejemplo, Reed-Solomon ) aborda el problema de los pisos de error inherentes a los diseños de código turbo.

Ver también [ editar ]

  • Código convolucional cuántico

Referencias [ editar ]

  •  Este artículo incorpora  material de dominio público del documento de la Administración de Servicios Generales : "Norma Federal 1037C" .
  1. ^ Benedetto, Sergio y Guido Montorsi. " Papel de los códigos convolucionales recursivos en los códigos turbo ". Electronics Letters 31.11 (1995): 858-859.
  2. ^ Eberspächer J. et al. Arquitectura, protocolos y servicios GSM. - John Wiley & Sons, 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 & Sons, 2004. - p. 430
  5. ^ Butman, SA, LJ Deutsch y RL Miller. "Rendimiento de códigos concatenados para misiones en el espacio profundo". The Telecommunications and Data Acquisition Progress Report 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 and Son (2005) .- p.508
  8. ^ LLR frente a demodulación por decisión difícil (MathWorks)
  9. ^ Estimar BER para decodificación de Viterbi de decisión dura y blanda (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 en el espacio profundo". The Telecommunications and Data Acquisition Progress Report 42-63, marzo-abril de 1981 (1981): 33-39.
  13. ^ Sistema global para comunicaciones móviles (GSM)
  14. ^ Codificación convolucional perforada (MathWorks)
  15. ^ https://www.mathworks.com/help/comm/ref/poly2trellis.html
  16. ^ Código turbo
  17. ^ Benedetto, Sergio y Guido Montorsi. " Papel de los códigos convolucionales recursivos en los códigos turbo ". Electronics Letters 31.11 (1995): 858-859.

Enlaces externos [ editar ]

  • 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 mejorar las comunicaciones digitales
  • Códigos convolucionales (MIT)
  • Teoría y codificación de la información (TU Ilmenau) , analiza los códigos convolucionales en la página 48.

Lectura adicional [ editar ]

Publicaciones [ editar ]

  • Francis, Michael. "Decodificación de bloque de decodificador de Viterbi: terminación de trellis y mordida de 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 decisión suave y borrado en sistemas rápidos de salto de frecuencia con códigos convolucionales, turbo y Reed-Solomon". Transacciones de 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 condiciones perfectas de seguimiento de fase". Computación 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". IEEE Transactions on Communications 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 Rician". IEE Proceedings F-Communications, Radar and Signal Processing. Vol. 134. No. 2. IET, 1987.