Código turbo

En teoría de la información , los códigos turbo son una clase de códigos de corrección de errores hacia adelante (FEC) de alto rendimiento desarrollados alrededor de 1990-91, pero publicados por primera vez en 1993. Fueron los primeros códigos prácticos en acercarse a la capacidad máxima del canal o límite de Shannon , un máximo teórico para la tasa de codificación en 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 comunicaciones satelitales ( de espacio profundo ) , así como en otras aplicaciones donde los diseñadores buscan lograr una transferencia de información confiable a través de enlaces de comunicación con ancho de banda o latencia limitados 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. Hasta que expiró la patente de los códigos turbo, ^{[ 1 ]} el estado libre de patentes de los códigos LDPC fue un factor importante en la continua relevancia de LDPC. ^{[ 2 ]}

El nombre "código turbo" surgió del bucle de retroalimentación utilizado durante la decodificación normal del código turbo, que se comparó con la retroalimentación de los gases 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. ^{[ 3 ]}

La solicitud de patente fundamental para los códigos turbo se presentó el 23 de abril de 1991. En dicha solicitud, Claude Berrou figura como el único inventor de los códigos turbo. Esta solicitud dio lugar a varias patentes, entre ellas la patente estadounidense 5,446,747 , que expiró el 29 de agosto de 2013.

El primer artículo público sobre códigos turbo fue " Codificación y decodificación de corrección de errores cerca del límite de Shannon: códigos turbo ". ^{[ 4 ]} Este artículo se publicó en 1993 en las Actas de la Conferencia Internacional de Comunicaciones del IEEE. El artículo 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 a tres autores: Berrou, Glavieux y Thitimajshima (de IMT Atlantique, antigua [Télécom Bretagne] antigua ENST Bretagne , Francia). Sin embargo, queda claro en la solicitud de patente original que Berrou es el único inventor de los códigos turbo y que los demás autores del artículo contribuyeron con material distinto a los conceptos centrales.

Los códigos turbo fueron tan revolucionarios en el momento de su introducción que muchos expertos en el campo de la codificación no creyeron en los resultados reportados. Cuando se confirmó su rendimiento, se produjo una pequeña revolución en el mundo de la codificación que condujo a la investigación de muchos otros tipos de procesamiento iterativo de señales. ^{[ 5 ]}

La primera clase de código turbo fue el código convolucional concatenado paralelo (PCCC). Desde la introducción de los códigos turbo paralelos originales en 1993, se han descubierto muchas otras clases de código turbo, incluidos los códigos convolucionales concatenados en serie y los códigos de repetición-acumulación . Los métodos de decodificación turbo iterativos 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 surgió del concepto de codificación turbo.

Además de los códigos turbo, Berrou también inventó los códigos convolucionales sistemáticos recursivos (RSC), que se utilizan en la implementación de ejemplo de los códigos turbo descrita en la patente. Los códigos turbo que utilizan códigos RSC parecen tener un mejor rendimiento que los que no los utilizan.

Antes de la llegada de los códigos turbo, las mejores construcciones eran códigos concatenados en serie basados ​​en un código de corrección de errores Reed-Solomon externo combinado con un código convolucional interno de longitud de restricción corta decodificado mediante Viterbi , también conocidos como códigos RSV.

En un artículo posterior, Berrou reconoció 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". Añade 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 eran poco prácticos en aquel momento. ^{[ 6 ]}

Existen numerosos ejemplos de códigos turbo, que utilizan distintos codificadores de componentes, relaciones de entrada/salida, entrelazadores y patrones de perforación . Esta implementación de ejemplo describe un codificador turbo clásico y demuestra el diseño general de los códigos turbo paralelos.

Esta implementación del codificador envía tres subbloques de bits. El primer subbloque es el bloque de m bits de datos de carga útil. El segundo subbloque son n/2 bits de paridad para los datos de carga útil, calculados mediante un código convolucional sistemático recursivo (código RSC). El tercer subbloque son n/2 bits de paridad para una permutación conocida de los datos de carga útil, calculados también mediante un código RSC. Por lo tanto, se envían dos subbloques de bits de paridad redundantes pero diferentes con la carga útil. El bloque completo tiene m + n bits de datos con una tasa de codificación de m / ( m + n ) . La permutación de los datos de carga útil se lleva a cabo mediante un dispositivo llamado entrelazador .

En cuanto al hardware, este codificador de código turbo consta de dos codificadores RSC idénticos, C ₁ y C ₂ , como se muestra en la figura, que están conectados entre sí mediante un esquema de concatenación, llamado concatenación paralela :

En la figura, M es un registro de memoria. La línea de retardo y el entrelazador obligan a que los bits de entrada d _k aparezcan en secuencias diferentes. En la primera iteración, la secuencia de entrada d _k aparece en ambas salidas del codificador, x _k e y _1k o y _2k, debido a la naturaleza sistemática del codificador. Si los codificadores C ₁ y C ₂ se utilizan en n ₁ y n ₂ iteraciones, sus tasas son respectivamente iguales a

${\displaystyle {\begin{aligned}~R_{1}&={\frac {n_{1}+n_{2}}{2n_{1}+n_{2}}}\\~R_{2}&={\frac {n_{1}+n_{2}}{n_{1}+2n_{2}}}\end{aligned}}}$

El decodificador está construido de forma similar al codificador anterior. Dos decodificadores elementales están interconectados entre sí, pero en serie, no en paralelo.${\displaystyle \textstyle DIC_ {1}}$el decodificador funciona a menor velocidad (es decir,${\displaystyle \textstyle R_ {1}}$), por lo tanto, está destinado a la${\displaystyle \textstyle C_ {1}}$codificador y${\displaystyle \textstyle DIC_ {2}}$es para${\displaystyle \textstyle C_{2}}$correspondientemente.${\displaystyle \textstyle DIC_ {1}}$produce una decisión blanda que causa${\displaystyle \textstyle L_ {1}}$retraso. El mismo retraso es causado por la línea de retardo en el codificador. El${\displaystyle \textstyle DIC_ {2}}$La operación de provoca${\displaystyle \textstyle L_ {2}}$demora.

Aquí se utiliza un entrelazador instalado entre los dos decodificadores para dispersar las ráfagas de errores provenientes de${\displaystyle \textstyle DIC_ {1}}$salida. El bloque DI es un módulo de demultiplexación e inserción. Funciona como un interruptor, redirigiendo los bits de entrada a${\displaystyle \textstyle DIC_ {1}}$en un momento y para${\displaystyle \textstyle DIC_ {2}}$en otro. En estado APAGADO, alimenta ambos${\displaystyle \textstyle y_{1k}}$y${\displaystyle \textstyle y_{2k}}$entradas con bits de relleno (ceros).

Consideremos un canal AWGN sin memoria y supongamos que en la k -ésima iteración, el decodificador recibe un par de variables aleatorias:

${\displaystyle {\begin{aligned}~x_{k}&=(2d_{k}-1)+a_{k}\\~y_{k}&=2(Y_{k}-1)+b_{k}\end{aligned}}}$

dónde${\displaystyle \textstyle a_ {k}}$y${\displaystyle \textstyle b_ {k}}$son componentes de ruido independientes que tienen la misma varianza${\displaystyle \textstyle \sigma ^{2}}$.${\displaystyle \textstyle Y_{k}}$es un k -ésimo bit de${\displaystyle \textstyle y_ {k}}$Salida del codificador.

La información redundante se desmultiplexa y se envía a través de DI a${\displaystyle \textstyle DIC_ {1}}$(cuando${\displaystyle \textstyle y_{k}=y_{1k}}$) y a${\displaystyle \textstyle DIC_ {2}}$(cuando${\displaystyle \textstyle y_{k}=y_{2k}}$).

${\displaystyle \textstyle DIC_ {1}}$produce una decisión blanda; es decir:

${\displaystyle \Lambda (d_{k})=\log {\frac {p(d_{k}=1)}{p(d_{k}=0)}}}$

y lo entrega a${\displaystyle \textstyle DIC_ {2}}$.${\displaystyle \textstyle \Lambda (d_ {k})}$se denomina logaritmo de la razón de verosimilitud (LLR).${\displaystyle \textstyle p(d_{k}=i),\,i\in \{0,1\}}$es la probabilidad a posteriori (APP) de la${\displaystyle \textstyle d_ {k}}$bit de datos que muestra la probabilidad de interpretar un dato recibido${\displaystyle \textstyle d_ {k}}$un poco como${\displaystyle \textstyle i}$. Teniendo en cuenta el LLR ,${\displaystyle \textstyle DIC_ {2}}$produce una decisión difícil; es decir, un bit decodificado.

Se sabe que el algoritmo de Viterbi no puede calcular APP, por lo tanto no se puede utilizar en${\displaystyle \textstyle DIC_ {1}}$En su lugar, se utiliza un algoritmo BCJR modificado. Para${\displaystyle \textstyle DIC_ {2}}$El algoritmo de Viterbi es uno apropiado.

Sin embargo, la estructura representada no es la óptima, porque${\displaystyle \textstyle DIC_ {1}}$Utiliza únicamente una fracción adecuada de la información redundante disponible. Para mejorar la estructura, se emplea un bucle de retroalimentación (véase la línea punteada en la figura).

El decodificador produce un número entero para cada bit del flujo de datos. Este número entero es una medida de la probabilidad de que el bit sea 0 o 1 y también se denomina bit blando . 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 probable 1"
• 127 significa "ciertamente 1"

Esto introduce un aspecto probabilístico en el flujo de datos desde el extremo frontal, pero transmite más información sobre cada bit que simplemente 0 o 1.

Por ejemplo, para cada bit, la etapa de entrada de un receptor inalámbrico tradicional debe determinar si un voltaje analógico interno está por encima o por debajo de un umbral de voltaje establecido. En el caso de un decodificador de código turbo, la etapa de entrada proporcionaría una medida entera que indicaría la diferencia entre el voltaje interno y dicho umbral.

Para decodificar el bloque de datos de m + n bits, el decodificador crea un bloque de medidas de probabilidad, con una medida de probabilidad para cada bit del 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 probabilidades para los datos de carga útil. El decodificador que trabaja con el segundo subbloque de paridad conoce la permutación que el codificador utilizó para este subbloque.

La principal innovación de los códigos turbo radica en 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 la carga útil. Se comparan los patrones de bits de las hipótesis y, si difieren, los decodificadores intercambian las probabilidades derivadas que poseen 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 de la carga útil. Luego, comparan estas nuevas hipótesis. Este proceso iterativo continúa hasta que los dos decodificadores llegan a la misma hipótesis para el patrón de m bits de la carga útil, generalmente en 15 a 18 ciclos.

Se puede establecer una analogía entre este proceso y la resolución de rompecabezas de referencias cruzadas, como crucigramas o sudokus . Consideremos un crucigrama parcialmente completado, posiblemente ilegible. Dos personas (descifradores) intentan resolverlo: una posee solo las pistas verticales (bits de paridad) y la otra solo las horizontales. Para empezar, ambos adivinan las respuestas (hipótesis) a sus propias pistas, anotando su grado de confianza en cada letra (bit de carga útil). Luego, comparan sus notas, intercambiando respuestas y niveles de confianza, y observan dónde y cómo difieren. Con base en este nuevo conocimiento, ambos elaboran respuestas y niveles de confianza actualizados, repitiendo todo el proceso hasta que convergen en la misma solución.

Los códigos turbo funcionan bien debido a la atractiva combinación de la aparición 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 umbral de error .

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 ^{[ 7 ]} y DVB-RCS2 .
• Las misiones recientes de la NASA , como el Orbitador de Reconocimiento de Marte, utilizan códigos turbo como alternativa a los códigos de corrección de errores Reed-Solomon ( códigos decodificadores Viterbi ).
• IEEE 802.16 ( WiMAX ), un estándar de red metropolitana inalámbrica, utiliza codificación turbo por bloques y codificación turbo convolucional.

Desde el punto de vista de la inteligencia artificial , los códigos turbo pueden considerarse como un ejemplo de propagación de creencias en bucle en redes bayesianas . ^{[ 8 ]}

• Algoritmo BCJR
• Código convolucional
• Corrección de errores hacia adelante
• Entrelazador
• Código de verificación de paridad de baja densidad
• Códigos convolucionales concatenados en serie
• Decodificación de decisiones suaves
• ecualizador turbo
• Algoritmo de Viterbi

• Guizzo, Erico (marzo de 2004). "Closing In On The Perfect Code" . IEEE Spectrum . 41 (3): 36– 42. doi : 10.1109/MSPEC.2004.1270546 . S2CID 21237188. Archivado del original el 11 de octubre de 2009. 
• "El código Turbo UMTS y una implementación de decodificador eficiente adecuada para radios definidas por software" Archivado el 20 de octubre de 2016 en Wayback Machine ( Revista Internacional de Redes de Información Inalámbricas ).
• Mackenzie, Dana (2005). "Llévalo al límite" . New Scientist . 187 (2507): 38– 41.
• "Superando los límites" , un artículo de Science News sobre el desarrollo y la génesis de los códigos turbo.
• Simposio Internacional sobre Códigos Turbo
• Coded Modulation Library , una biblioteca de código abierto para simular códigos turbo en Matlab.
• "Ecualización Turbo: Principios y Nuevos Resultados" Archivado el 27 de febrero de 2009 en Wayback Machine , un artículo de IEEE Transactions on Communications sobre el uso de códigos convolucionales junto con la ecualización de canales.
• Página principal de IT++ IT ++ es una potente biblioteca de C++ que, en particular, admite códigos turbo.
• Publicaciones de códigos turbo de David MacKay
• Página principal 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.
• Kerouédan, Sylvie; Berrou, Claude (2010). "Código turbo" . Scholarpedia . 5 (4). Scholarpedia.org: 6496. Bibcode : 2010SchpJ...5.6496K . doi : 10.4249/scholarpedia.6496 .
• Diseño de referencia 3GPP LTE Turbo .
• Estimación del rendimiento BER del código Turbo en AWGN Archivado el 1 de febrero de 2019 en Wayback Machine (MatLab).
• Codificación convolucional concatenada en paralelo: Códigos turbo (MatLab Simulink)