código turbo

Códigos de corrección de errores directos de alto rendimiento

En teoría de la información , los códigos turbo (originalmente en francés Turbocodes ) son una clase de códigos de corrección directa de errores (FEC) de alto rendimiento desarrollados alrededor de 1990-91, pero publicados por primera vez en 1993. Fueron los primeros códigos prácticos que se acercaron al canal máximo. capacidad o límite de Shannon , un máximo teórico para la velocidad 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 comunicaciones por satélite ( espacio profundo ) , así como en otras aplicaciones en las que 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 limitada en el mundo. 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 brindan un rendimiento similar (pero no tienen patente). ^[1]

El nombre "código turbo" surgió del circuito de retroalimentación utilizado durante la decodificación normal del código turbo, que era análogo a la retroalimentación del 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. ^[2]

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 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 ". ^[3] Este artículo fue publicado en 1993 en las Actas de la Conferencia Internacional de Comunicaciones 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 incluyera a tres autores: Berrou, Glavieux y Thitimajshima (de Télécom Bretagne, ex ENST Bretagne , Francia). Sin embargo, de la solicitud de patente original se desprende claramente que Berrou es el único inventor de los códigos turbo y que los demás autores del artículo contribuyeron con material distinto de los conceptos básicos. ^{[ síntesis inadecuada ]}

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 los resultados reportados. Cuando se confirmó el rendimiento, se produjo una pequeña revolución en el mundo de la codificación que llevó a la investigación de muchos otros tipos de procesamiento iterativo de señales. ^[4]

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ódigos turbo, incluidas versiones en serie, códigos convolucionales concatenados en serie y códigos de acumulación repetida . Los métodos iterativos de decodificación turbo también se han aplicado a sistemas FEC más convencionales, incluidos los códigos convolucionales corregidos por 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ó códigos convolucionales sistemáticos recursivos (RSC), que se utilizan en el ejemplo de implementación de códigos turbo descrito 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 interno de longitud corta de restricción decodificado por Viterbi , también conocidos 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 años 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 en aquel momento no eran prácticos. ^[5]

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 m bits de datos de carga útil. El segundo subbloque tiene 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 tiene n/2 bits de paridad para una permutación conocida de los datos de carga útil, nuevamente calculados usando un código RSC. Por tanto, con la carga útil se envían dos subbloques de bits de paridad redundantes pero diferentes. El bloque completo tiene m + n bits de datos con una velocidad 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 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 fuerzan que los bits de entrada dk _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 velocidades 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

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

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

Considere un canal AWGN sin memoria y suponga 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}}}$

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

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

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

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

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

Se sabe que el algoritmo de Viterbi no puede calcular 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. ${\displaystyle \textstyle DEC_{1}}$ ${\displaystyle \textstyle DEC_{2}}$

Sin embargo, la estructura representada no es óptima, porque utiliza sólo una fracción adecuada de la información redundante disponible. Para mejorar la estructura, se utiliza un circuito de retroalimentación (consulte la línea de puntos en la figura). ${\displaystyle \textstyle DEC_{1}}$

Enfoque de decisión suave

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 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 probable 0"
• 0 significa "podría ser 0 o 1"
• 100 significa "muy probable 1"
• 127 significa "ciertamente 1"

Esto introduce un aspecto probabilístico al flujo de datos desde el extremo frontal, 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, la interfaz 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, la interfaz 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 paralelos, 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 en el segundo subbloque de paridad conoce la permutación que el codificador utilizó para este subbloque.

Resolver hipótesis para encontrar bits.

La innovación clave de los códigos turbo 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. Se comparan los patrones de bits de las hipótesis 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 de 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, normalmente 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 posee solo las pistas "abajo" (bits de paridad) y el otro posee solo las pistas "a través". Para empezar, ambos solucionadores adivinan las respuestas (hipótesis) de sus propias pistas y anotan su confianza en cada letra (bit de carga útil). Luego, comparan notas, intercambian 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 a 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 utilizando 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 ^[6] 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 de bloques 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 redes bayesianas . ^[7]

Ver también

• algoritmo BCJR
• código convolucional
• Corrección de errores hacia adelante
• Intercalador
• 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

Referencias

1. Erico Guizzo (1 de marzo de 2004). "ACERCANDO EL CÓDIGO PERFECTO". Espectro IEEE ."Otra ventaja, quizás la mayor de todas, es que las patentes LDPC han expirado, por lo que las empresas pueden utilizarlas sin tener que pagar por los derechos de propiedad intelectual".
2. Hagenauer, Joaquín; Oferta, Elke; Papke, Luiz (marzo de 1996). "Decodificación iterativa de bloques binarios y códigos convolucionales" (PDF) . Transacciones IEEE sobre teoría de la información . 42 (2): 429–445. doi : 10.1109/18.485714. Archivado desde el original (PDF) el 11 de junio de 2013 . Consultado el 20 de marzo de 2014 .
3. Berrou, Claude ; Glavieux, Alain ; Thitimajshima, Punya (1993), "Error cercano al límite de Shannon: corrección", Actas de la Conferencia Internacional de Comunicaciones IEEE , vol. 2, págs. 1064–70, doi :10.1109/ICC.1993.397441, S2CID  17770377 , consultado el 11 de febrero de 2010
4. Erico Guizzo (1 de marzo de 2004). "ACERCANDO EL CÓDIGO PERFECTO". Espectro IEEE .
5. Berrou, Claude, Los códigos turbo de hace diez años están entrando en servicio, Bretaña, Francia , consultado el 11 de febrero de 2010.
6. Transmisión de vídeo digital (DVB); Canal de interacción para Sistemas de Distribución Satélite, ETSI EN 301 790, V1.5.1, mayo de 2009.
7. McEliece, Robert J .; MacKay, David JC ; Cheng, Jung-Fu (1998), "La decodificación turbo como 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 (1998). "Un marco conceptual para comprender los códigos turbo". Revista IEEE sobre áreas seleccionadas de las comunicaciones . 916 (2): 245–254. doi : 10.1109/49.661112.
• Brejza, MF; Pequeño.; Maunder, RG; Al-Hashimi, BM; Berrou, C.; Hanzo, L. (2016). "20 años de codificación turbo y pautas de diseño conscientes de la energía para aplicaciones inalámbricas con restricciones de energía" (PDF) . Encuestas y tutoriales de comunicaciones IEEE . 918 (1): 8–28. doi :10.1109/COMST.2015.2448692. S2CID  12966388.
• Garzón-Bohórquez, Ronald; Nour, Charbel Abdel; Douillard, Catalina (2016). Mejora de los códigos Turbo para 5G con entrelazadores de paridad restringida (PDF) . Noveno Simposio Internacional sobre Códigos Turbo y Procesamiento Iterativo de Información (ISTC). págs. 151–5. doi :10.1109/ISTC.2016.7593095.

enlaces externos

• Guizzo, Erico (marzo de 2004). "Acercándonos al código perfecto". Espectro IEEE . 41 (3): 36–42. doi :10.1109/MSPEC.2004.1270546. S2CID  21237188.
• "El código UMTS Turbo y una implementación eficiente de decodificador adecuado para radios definidas por software" ( Revista internacional de redes de información inalámbricas )
• Mackenzie, Dana (2005). "Llevarlo al límite". Científico nuevo . 187 (2507): 38–41.
• "Pushing the Limit", un artículo de Science News sobre el desarrollo y 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 Equalization: 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.
• Página de inicio 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 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
• Kerouédan, Sylvie; Berrou, Claude (2010). "Código turbo". Scholarpedia . Scholarpedia.org. 5 (4): 6496. doi : 10.4249/scholarpedia.6496 .
• Diseño de referencia 3GPP LTE Turbo.
• Estimar el rendimiento BER del código Turbo en AWGN (MatLab).
• Codificación convolucional concatenada en paralelo: códigos turbo (MatLab Simulink)