En la teoría de la información , los códigos turbo (originalmente en Turbocódigos franceses ) son una clase de códigos de corrección de errores directos (FEC) de alto rendimiento desarrollados alrededor de 1990-1991, pero publicados por primera vez en 1993. Fueron los primeros códigos prácticos que se acercaron de cerca al canal máximo. capacidad o límite de Shannon , un máximo teórico para la tasa de código a la que aún es posible una comunicación confiable dado un nivel de ruido específico. Los códigos turbo se utilizan en comunicaciones móviles 3G / 4G (por ejemplo, en UMTS y LTE ) y en satélites ( espacio profundo ) comunicaciones , así como otras aplicaciones donde los diseñadores buscan lograr una transferencia de información confiable a través de enlaces de comunicación restringidos por ancho de banda o latencia en presencia de ruido que corrompe los datos. Los códigos turbo compiten con los códigos de verificación de paridad de baja densidad (LDPC), que proporcionan un rendimiento similar.
El nombre "código turbo" surgió del bucle de retroalimentación utilizado durante la decodificación del código turbo normal, que se anotó con la retroalimentación de escape utilizada para la turboalimentación del motor . Hagenauer ha argumentado que el término código turbo es un nombre inapropiado ya que no hay retroalimentación involucrada en el proceso de codificación. [1]
Historia
La solicitud de patente fundamental para los códigos turbo se presentó el 23 de abril de 1991. La solicitud de patente enumera a Claude Berrou como el único inventor de los códigos turbo. La solicitud de patente dio lugar a varias patentes, incluida la patente de EE. UU . 5.446.747 , que expiró el 29 de agosto de 2013.
El primer documento público sobre códigos turbo fue " Codificación y decodificación de corrección de errores del límite cercano a Shannon: códigos turbo ". [2] Este artículo fue publicado en 1993 en las Actas de la Conferencia Internacional de Comunicaciones de IEEE. El documento de 1993 se formó a partir de tres presentaciones separadas que se combinaron debido a limitaciones de espacio. La fusión hizo que el artículo enumerara tres autores: Berrou, Glavieux y Thitimajshima (de Télécom Bretagne, ex ENST Bretagne , Francia). Sin embargo, se desprende claramente de la solicitud de patente original que Berrou es el único inventor de los códigos turbo y que los otros autores del artículo contribuyeron con material diferente a los conceptos básicos. [ síntesis incorrecta ]
Los códigos turbo eran tan revolucionarios en el momento de su introducción que muchos expertos en el campo de la codificación no creían en los resultados informados. Cuando se confirmó el rendimiento, tuvo lugar una pequeña revolución en el mundo de la codificación que llevó a la investigación de muchos otros tipos de procesamiento de señales iterativo.
La primera clase de código turbo fue el código convolucional concatenado en paralelo (PCCC). Desde la introducción de los códigos turbo paralelos originales en 1993, se han descubierto muchas otras clases de códigos turbo, incluidas versiones en serie, códigos convolucionales concatenados en serie y códigos de acumulación repetida . Los métodos de decodificación turbo iterativa también se han aplicado a sistemas FEC más convencionales, incluidos los códigos convolucionales corregidos de Reed-Solomon, aunque estos sistemas son demasiado complejos para implementaciones prácticas de decodificadores iterativos. La ecualización turbo también se deriva del concepto de codificación turbo.
Además de los códigos turbo, Berrou también inventó códigos convolucionales sistemáticos recursivos (RSC), que se utilizan en la implementación de ejemplo de códigos turbo descritos en la patente. Los códigos turbo que usan códigos RSC parecen funcionar mejor que los códigos turbo que no usan códigos RSC.
Antes de los códigos turbo, las mejores construcciones eran códigos concatenados en serie basados en un código externo de corrección de errores Reed-Solomon combinado con un código convolucional de longitud de restricción corta decodificado por Viterbi interno , también conocido como códigos RSV.
En un artículo posterior, Berrou dio crédito a la intuición de "G. Battail, J. Hagenauer y P. Hoeher, quienes, a finales de los 80, destacaron el interés del procesamiento probabilístico". Agrega que " R. Gallager y M. Tanner ya habían imaginado técnicas de codificación y decodificación cuyos principios generales están estrechamente relacionados", aunque los cálculos necesarios no eran prácticos en ese momento. [3]
Un codificador de ejemplo
Hay muchas instancias diferentes de códigos turbo, que utilizan diferentes codificadores de componentes, relaciones de entrada / salida, intercaladores y patrones de perforación. Esta implementación de codificador de ejemplo describe un codificador turbo clásico y demuestra el diseño general de códigos turbo paralelos.
Esta implementación de codificador envía tres subbloques de bits. El primer subbloque es el bloque de datos de carga útil de m bits. El segundo subbloque es n / 2 bits de paridad para los datos de carga útil, calculados utilizando un código convolucional sistemático recursivo (código RSC). El tercer subbloque es n / 2 bits de paridad para una permutación conocida de los datos de carga útil, nuevamente calculados usando un código RSC. Por lo tanto, se envían dos sub-bloques redundantes pero diferentes de bits de paridad con la carga útil. El bloque completo tiene m + n bits de datos con una tasa de código de m / ( m + n ) . La permutación de los datos de la carga útil se lleva a cabo mediante un dispositivo llamado intercalador .
En cuanto al hardware, este codificador de código turbo consta de dos codificadores RSC idénticos, С 1 y C 2 , como se muestra en la figura, que están conectados entre sí mediante un esquema de concatenación, llamado concatenación en paralelo :
En la figura, M es un registro de memoria. La línea de retardo y el intercalador fuerzan a los bits de entrada d k a aparecer en diferentes secuencias. En la primera iteración, la secuencia de entrada d k aparece en ambas salidas del codificador, x k y y 1k o y 2k debido a la naturaleza sistemática del codificador. Si los codificadores C 1 y C 2 se utilizan en n 1 y n 2 iteraciones, sus velocidades son respectivamente iguales a
El decodificador
El decodificador está construido de manera similar al codificador anterior. Dos decodificadores elementales están interconectados entre sí, pero en serie, no en paralelo. La el decodificador funciona a menor velocidad (es decir, ), por lo que está destinado a la codificador y es para correspondientemente. produce una decisión suave que causademora. El mismo retraso es causado por la línea de retraso en el codificador. LaCausas de la operación demora.
Un intercalador instalado entre los dos decodificadores se usa aquí para dispersar ráfagas de error provenientes de producción. El bloque DI es un módulo de demultiplexación e inserción. Funciona como un conmutador, redirigiendo los bits de entrada a en un momento y para en otro. En estado APAGADO, alimenta a ambos y entradas con bits de relleno (ceros).
Considere un canal AWGN sin memoria y suponga que en k -ésima iteración, el decodificador recibe un par de variables aleatorias:
dónde y son componentes de ruido independientes que tienen la misma varianza . es un k -ésimo bit de salida del codificador.
La información redundante se demultiplexa y se envía a través de DI a (Cuándo ) y para (Cuándo ).
produce una decisión blanda; es decir:
y lo entrega a . se llama el logaritmo de la razón de verosimilitud (LLR).es la probabilidad a posteriori (APP) de la bit de datos que muestra la probabilidad de interpretar un recibo poco como . Teniendo en cuenta el LLR ,produce una decisión difícil; es decir, un bit decodificado.
Se sabe que el algoritmo de Viterbi no puede calcular la APP, por lo que no se puede utilizar en. En lugar de eso, se utiliza un algoritmo BCJR modificado . Para, el algoritmo de Viterbi es apropiado.
Sin embargo, la estructura representada no es óptima, porque utiliza solo una fracción adecuada de la información redundante disponible. Para mejorar la estructura, se utiliza un bucle de retroalimentación (ver la línea de puntos en la figura).
Enfoque de decisión blanda
La interfaz del decodificador produce un número entero para cada bit en el flujo de datos. Este número entero es una medida de la probabilidad de que el bit sea un 0 o 1 y también se denomina bit suave . El número entero podría extraerse del rango [−127, 127], donde:
- −127 significa "ciertamente 0"
- −100 significa "muy probablemente 0"
- 0 significa "podría ser 0 o 1"
- 100 significa "muy probablemente 1"
- 127 significa "ciertamente 1"
Esto introduce un aspecto probabilístico al flujo de datos desde la interfaz, pero transmite más información sobre cada bit que solo 0 o 1.
Por ejemplo, para cada bit, el extremo frontal de un receptor inalámbrico tradicional tiene que decidir si un voltaje analógico interno está por encima o por debajo de un nivel de voltaje umbral determinado. Para un decodificador de código turbo, el extremo frontal proporcionaría una medida entera de qué tan lejos está el voltaje interno del umbral dado.
Para decodificar el bloque de datos de m + n bits, el front-end del decodificador crea un bloque de medidas de probabilidad, con una medida de probabilidad para cada bit en el flujo de datos. Hay dos decodificadores en paralelo, uno para cada uno de los subbloques de paridad de n ⁄ 2 bits. Ambos decodificadores utilizan el subbloque de m verosimilitudes para los datos de carga útil. El decodificador que trabaja en el segundo subbloque de paridad conoce la permutación que utilizó el codificador para este subbloque.
Resolver hipótesis para encontrar bits
La innovación clave de los turbocódigos es cómo utilizan los datos de probabilidad para conciliar las diferencias entre los dos decodificadores. Cada uno de los dos decodificadores convolucionales genera una hipótesis (con probabilidades derivadas) para el patrón de m bits en el subbloque de carga útil. Los patrones de bits de hipótesis se comparan y, si difieren, los decodificadores intercambian las probabilidades derivadas que tienen para cada bit de las hipótesis. Cada decodificador incorpora las estimaciones de probabilidad derivadas del otro decodificador para generar una nueva hipótesis para los bits en la carga útil. Luego comparan estas nuevas hipótesis. Este proceso iterativo continúa hasta que los dos decodificadores presentan la misma hipótesis para el patrón de m bits de la carga útil, típicamente en 15 a 18 ciclos.
Se puede establecer una analogía entre este proceso y el de resolver acertijos de referencias cruzadas como crucigramas o sudoku . Considere un crucigrama parcialmente completado y posiblemente confuso. Dos solucionadores de acertijos (decodificadores) están tratando de resolverlo: uno que posee solo las pistas "abajo" (bits de paridad) y el otro que posee solo las pistas "cruzadas". Para empezar, ambos solucionadores adivinan las respuestas (hipótesis) a sus propias pistas, anotando qué tan seguros están en cada letra (bit de carga útil). Luego, comparan notas, intercambiando respuestas y calificaciones de confianza entre sí, notando dónde y cómo difieren. Con base en este nuevo conocimiento, ambos obtienen respuestas actualizadas y calificaciones de confianza, repitiendo todo el proceso hasta que convergen en la misma solución.
Actuación
Los códigos turbo funcionan bien debido a la atractiva combinación de la apariencia aleatoria del código en el canal junto con la estructura de decodificación físicamente realizable. Los códigos turbo se ven afectados por un piso de error .
Aplicaciones prácticas que utilizan códigos turbo
Telecomunicaciones:
- Los códigos turbo se utilizan ampliamente en los estándares de telefonía móvil 3G y 4G ; por ejemplo, en HSPA , EV-DO y LTE .
- MediaFLO , sistema de televisión móvil terrestre de Qualcomm .
- El canal de interacción de los sistemas de comunicación por satélite , como DVB-RCS [4] y DVB-RCS2 .
- Misiones recientes de la NASA , como Mars Reconnaissance Orbiter, utilizan códigos turbo como alternativa a la corrección de errores de Reed-Solomon : códigos decodificadores de Viterbi .
- IEEE 802.16 ( WiMAX ), un estándar de red metropolitana inalámbrica, utiliza codificación turbo en bloque y codificación turbo convolucional.
Formulación bayesiana
Desde el punto de vista de la inteligencia artificial , los códigos turbo pueden considerarse como un ejemplo de propagación de creencias descabelladas en las redes bayesianas . [5]
Ver también
- Código convolucional
- Algoritmo de Viterbi
- Decodificación de decisión suave
- Intercalador
- Algoritmo BCJR
- Código de verificación de paridad de baja densidad
- Códigos convolucionales concatenados en serie
- Ecualizador turbo
- Corrección de errores hacia adelante
Referencias
- ^ Joachim Hagenauer, Joachim; et al. "Decodificación iterativa de bloques binarios y códigos convolucionales" (PDF) . Archivado desde el original (PDF) el 11 de junio de 2013 . Consultado el 20 de marzo de 2014 .
- ^ Berrou, Claude; Glavieux, Alain; Thitimajshima, Punya, Near Shannon Limit Error - Correcting , consultado el 11 de febrero de 2010
- ^ Berrou, Claude, Los códigos turbo de diez años están entrando en servicio , Bretaña, Francia , consultado el 11 de febrero de 2010
- ^ Difusión de vídeo digital (DVB); Canal de interacción para sistemas de distribución por satélite , ETSI EN 301 790, V1.5.1, mayo de 2009.
- ^ McEliece, Robert J .; MacKay, David JC ; Cheng, Jung-Fu (1998), "La decodificación turbo como una instancia del algoritmo de" propagación de creencias "de Pearl (PDF) , IEEE Journal on Selected Areas in Communications , 16 (2): 140-152, doi : 10.1109 / 49.661103 , ISSN 0733-8716 .
Otras lecturas
Publicaciones
- Battail, Gérard. "Un marco conceptual para comprender los códigos turbo". Revista IEEE sobre áreas seleccionadas en comunicaciones 16.2 (1998): 245–254.
- Brejza, Matthew F. y col. "20 años de codificación turbo y pautas de diseño conscientes de la energía para aplicaciones inalámbricas con limitaciones de energía". Encuestas y tutoriales de comunicaciones de IEEE 18.1 (2016): 8–28.
- Garzón-Bohórquez, Ronald, Charbel Abdel Nour y Catherine Douillard. "Mejora de los códigos Turbo para 5G con intercaladores de paridad restringidos por pinchazos". Turbo Codes and Iterative Information Processing (ISTC), 2016 IX Simposio Internacional sobre. IEEE, 2016.
enlaces externos
- "Acercándose al código perfecto" , IEEE Spectrum, marzo de 2004
- "El código UMTS Turbo y una implementación de decodificador eficiente adecuada para radios definidas por software" ( Revista Internacional de Redes de Información Inalámbricas )
- Dana Mackenzie (2005), "Llévalo al límite", New Scientist , 187 (2507): 38–41, ISSN 0262-4079 .( vista previa , copia )
- "Pushing the Limit" , un artículo de Science News sobre el desarrollo y la génesis de los códigos turbo
- Simposio internacional sobre códigos turbo
- Biblioteca de modulación codificada , una biblioteca de código abierto para simular códigos turbo en matlab
- "Turbo Ecualización: Principios y nuevos resultados" , un artículo de IEEE Transactions on Communications sobre el uso de códigos convolucionales junto con la ecualización de canales.
- TI ++ Página La TI ++ es una biblioteca de C ++ de gran alcance que en particular soportes códigos turbo
- Publicaciones de códigos turbo por David MacKay
- Página de inicio de AFF3CT (una caja de herramientas de corrección de errores de avance rápido) para simulaciones de códigos turbo de alta velocidad en software
- Código turbo de la Dra. Sylvie Kerouédan y el Dr. Claude Berrou (scholarpedia.org).
- Diseño de referencia 3GPP LTE Turbo .
- Estime el rendimiento de Turbo Code BER en AWGN (MatLab).
- Codificación convolucional concatenada paralela: códigos turbo (MatLab Simulink)