Código turbo

El código turbo es un código sistemático de bloques paralelos en cascada que puede corregir errores que ocurren cuando la información digital se transmite a través de un canal de comunicación ruidoso . Turbocódigo es sinónimo del conocido término en la teoría de la codificación: código concatenado ( propuesto por D. Forney en 1966).

Un código turbo consiste en una cascada de códigos sistemáticos conectados en paralelo. Estos componentes se denominan códigos de componentes. Los códigos convolucionales, los códigos de Hamming, los códigos de Reed-Solomon , los códigos de Bowes-Chowdhury-Hokvingham y otros se pueden utilizar como códigos de componentes . Dependiendo de la elección del código de componente, los códigos turbo se dividen en códigos turbo convolucionales ( Códigos convolucionales turbo , TCC ) y códigos de producto de bloque ( Códigos de producto turbo , TPC ) [1] .

Los códigos Turbo se desarrollaron en 1993 y son una clase de códigos correctores de errores altamente eficientes , utilizados en ingeniería eléctrica y comunicaciones digitales , y también han encontrado su aplicación en comunicaciones por satélite y otras áreas en las que es necesario lograr el máximo. tasa de transferencia de datos a través de un canal de comunicación con ruido en una banda de frecuencia limitada .

Historia

Hasta la llegada del código turbo, estaba muy extendido el método de codificación concatenada, en el que los datos se codificaban primero mediante el código Reed-Solomon , y luego mediante el código convolucional . Se acerca lo suficiente al límite de Shannon y combina un bloque de corrección de errores usando el código Reed-Solomon y un bloque de códigos convolucionales decodificados usando el algoritmo Viterbi .

Los códigos turbo fueron propuestos por C. Berrou , A. Glavieux y P. Thitimajshima de la École Nationale Supérieure des Télécommunications de Bretagne (ENST Bretagne) , la Escuela Nacional Superior de Telecomunicaciones de Bretaña ( Francia )) en 1993 en el artículo " Near Shannon Limit Error- correcting Coding and Decoding : Turbo-code" [ 2] , publicado en IEEE Proceedings . En un artículo posterior [3] , Burrow acredita la intuición de G. Battail , J. Hagenauer y P. Hoeher , quienes teóricamente predijeron el procesamiento de datos probabilísticos a fines de la década de 1980 . Burrow también menciona que Robert Gallagher y M. Tanner ( M. Tanner ) todavía en un momento representaron métodos de codificación y decodificación con principios generales muy cercanos a los códigos turbo, pero en ese momento no se disponía de las capacidades informáticas necesarias .

Estructura del código Turbo

Según Shannon , el mejor código es aquel que transmite un mensaje en un tiempo infinitamente largo, generando elementos de código aleatorios en cada momento del tiempo. . El receptor tiene infinitas versiones de un mensaje destrozado al azar. De estas copias, el decodificador debe seleccionar la copia más cercana al mensaje transmitido. Este es un código teóricamente ideal que puede corregir todos los errores en una señal. Turbocode es un paso en esa dirección. Está claro que no debemos enviar un mensaje informativo durante un tiempo infinito. Duplicar o triplicar el tiempo de transferencia es suficiente para un rendimiento aceptable, lo que proporcionará resultados bastante decentes para los canales de comunicación.

Una característica de los códigos turbo es una estructura paralela que consta de códigos convolucionales sistemáticos recursivos (RSC) que funcionan en paralelo y utilizan la creación de una versión aleatoria del mensaje. La estructura paralela utiliza dos o más códigos RSC , cada uno con un intercalador diferente . El propósito del intercalador es ofrecer a cada codificador una versión no correlacionada o aleatoria de la información , por lo que los bits de paridad de cada RSC se vuelven independientes .

En los códigos turbo, los bloques tienen una longitud del orden de varios kbits. El propósito de esta longitud es aleatorizar eficientemente la secuencia que va al segundo codificador. Cuanto mayor sea el tamaño del bloque, mejor será su correlación con el mensaje del primer codificador, es decir, la correlación es pequeña.

Hay varios esquemas de código turbo:

PCCC - en caso de concatenación de códigos convolucionales paralelos
SCCC es un esquema de conexión en serie de códigos convolucionales, los códigos SCCC tienen un alto rendimiento en altas relaciones señal-ruido
TPC : código de producto turbo , utiliza códigos de bloque en lugar de códigos convolucionales; dos códigos de bloque diferentes (generalmente códigos de Hamming ) se conectan en serie sin un intercalador intermedio . Dado que los dos códigos son independientes y funcionan en filas y columnas, lo que en sí mismo proporciona una aleatorización razonablemente buena, no se requiere intercalador .

Codificación

En la fig. 1 es un diagrama de bloques general de un codificador turbo de bloque M.

Primero, llega a la entrada del PAD ( Packet Assembler / Disassembler ) un bloque de datos con una longitud de bits . En el formador de paquetes, se agregan bits adicionales de información de servicio a los datos, correspondientes al estándar de formación de paquetes utilizado e incluyendo los caracteres para su comienzo y fin [4] . Es decir, se obtiene un paquete formado por bits. $tu$ $k$ $(nk)$ $X_{0}$ $norte$

Además , la secuencia de bits entra en paralelo en las ramas que contienen el intercalador y el codificador de componentes conectados en serie. Por lo tanto, todos los codificadores de componentes lo utilizan como entrada a la vez. $X_{0}$ $METRO$ $X_{0}$

Intercalado en códigos turbo

En los intercaladores , según una ley pseudoaleatoria, los bits entrantes se mezclan. A diferencia del intercalador rectangular por símbolo que se usa en los códigos Reed-Solomon , los códigos turbo usan intercalado de un solo bit , que es similar a las permutaciones aleatorias. Además, más adelante, durante las operaciones de decodificación, se dará por conocida esta ley de entrelazado . Las secuencias resultantes se envían a las entradas de los codificadores.

La tarea del intercalador es transformar la secuencia de entrada para que las combinaciones de bits correspondientes a palabras de código con bajo peso ( el peso es el número de bits distintos de cero de la palabra de código) a la salida del primer codificador se transformen en combinaciones que dan palabras de código con alto peso en las salidas de otros codificadores. Por lo tanto, los codificadores emiten palabras de código con diferentes pesos. Al codificar, las palabras de código se forman de manera que se obtenga la máxima distancia promedio posible entre ellas ( la distancia entre dos palabras de código es el número de bits en que se diferencian). Debido al hecho de que los bloques de código están formados por partes casi independientes, a la salida del codificador turbo, la distancia promedio entre palabras de código es mayor que la distancia mínima para cada codificador componente y, por lo tanto, aumenta la eficiencia de codificación. $X_{0}$

La permutación para cada longitud de bloque especificada viene dada por un reordenamiento específico de enteros según lo dispuesto por el siguiente algoritmo ( ECSS -E-ST-50-01C) [5] . $k$ $1, 2...,k$

$k = 8 * k_0$ , donde uno de los siguientes valores: , , , , dependiendo de la profundidad de entrelazado requerida $k_0 =$ $223$ $223*2$ $223*4$ $223*5$

Las siguientes operaciones se realizan en los valores de a para obtener las direcciones de permutación . En las siguientes ecuaciones, denota el entero más grande menor o igual que , y denota uno de los siguientes cuatro números primos : $s = 1$ $s = k$ $\ símbolo de negrita \ pi (s)$ $\mathcal{b} \boldsymbol x \mathcal{c}$ $\símbolo en negrita x$ $\ símbolo de negrita p_q$ $p_0 = 31,$ $p_1 = 37,$ $p_2 = 43,$ $p_3 = 47,$

$m = (s-1)\mod 2$

$i = \mathcal{b} \frac{ s-1 }{2*k_0} \mathcal{c}$

$j = \mathcal{b} \frac{ s-1 }{2} \mathcal{c} - i*k_0$

$q = (19*i+1) \mod 4$

$c = (p_q*j+21*m) \mod k_0$

$\boldsymbol\pi(s) = 2*(q + 4*c + 1) - m$

La interpretación de la permutación es que el -ésimo bit transmitido por el intercalador es el -ésimo bit del bloque de información de entrada. El intercalador escribe el bit recibido en la dirección calculada. $\boldsymbols$ $\negrita\pi(s)$

Tasa de código

Tasa de código : la relación entre la longitud del bloque de código en la entrada y la longitud del bloque de código transformado en la salida del codificador.

En ausencia de un perforador (ver Fig. 1), la secuencia original se multiplexa con secuencias de bits de paridad , formando una palabra de código para ser transmitida por el canal. Entonces el valor de la tasa de código en la salida del codificador turbo $X_{0}$ $V_1,\ldots,V_M$

$R = \frac{k}{n(M+1)}$

Para aumentar la tasa de código, se utiliza la punción (perforación) de ciertos bits de control de la secuencia de salida. Por lo tanto, la tasa de código aumenta a

$R = \frac{k}{n(N+1)}$ , donde , y puede ser fraccionario si el número de brocas de control que quedan después de la perforación no es un múltiplo de . $N<M$ $norte$ $norte$

Si tenemos en cuenta que los turbocódigos operan con bloques de gran longitud c , entonces , y la tasa de código es igual a $k > 10000$ $k \aproximado n$

$R = \frac{1}{N+1}$

De las fórmulas anteriores , se puede ver que con la ayuda de un perforador, perforando un número diferente de bits de control, es posible regular la tasa de código. Es decir, puedes construir un codificador que se adapte al canal de comunicación. Cuando el canal es ruidoso, el perforador perfora menos bits, lo que provoca una disminución en la tasa de código y un aumento en la inmunidad al ruido del codificador. Si el canal de comunicación es de buena calidad, se puede perforar una gran cantidad de bits, lo que provoca un aumento en la tasa de transferencia de información [6] .

Decodificación

Algoritmo de decodificación de probabilidad posterior máxima (MAP)

Al realizar una decodificación con corrección de errores, es fundamental analizar las probabilidades a priori ya posteriori de la llegada de la palabra clave correcta. A priori es la información que tiene el decodificador antes de la llegada de la palabra código, ya posteriori es la información que se obtiene después de procesar la palabra código.

Burrow propone para su uso en decodificadores turbo el algoritmo Máximo de probabilidad A posteriori (MAP ) , también conocido como algoritmo Bala ( Bahl-Cocke-Jelinek-Raviv (BCJR) ). El algoritmo de Bal proporciona una estimación de confianza " suave " para el bit decodificado. Es decir, presenta un grado de confianza en el resultado de la decodificación en la salida. A diferencia de la estructura " dura ", en la que sólo se forma a la salida del decodificador el valor más probable del bit decodificado ("0" o "1"), al tomar una decisión "suave", se realiza un muestreo más detallado de la señal de salida, que caracteriza la probabilidad de recepción correcta del bit. Debido al uso de decisiones "suaves" en los decodificadores turbo, es eficiente usar varias iteraciones de decodificación . La información a posteriori obtenida sobre la palabra de código a la salida de la primera iteración de decodificación se alimenta a la entrada del bloque de la siguiente iteración y ya es una probabilidad a priori de la misma. Este enfoque permite mejorar la calidad de la decodificación de iteración en iteración. Por lo tanto, al cambiar el número de iteraciones de decodificación, es posible adaptar el decodificador al estado actual del canal de transmisión y lograr la probabilidad de error de bit requerida [6] .

Relación de probabilidad logarítmica (LLR)

Considere el bit de información como una variable binaria , es decir, el valor en el momento . Su relación log-verosimilitud (LLR) se define como el logaritmo de la relación de sus probabilidades subyacentes. $\boldsymbol u_k$ $\negrita tu$ $k$

$L(u_k) = \ln \frac {Pr(u_k = 1)}{Pr(u_k = 0)}$

Esta métrica se utiliza en la mayoría de los sistemas de corrección de errores con codificación de corrección de errores y se denomina relación de probabilidad logarítmica o LLR . Es ligeramente mejor que la métrica lineal porque, por ejemplo, el logaritmo facilita el manejo de valores muy pequeños y muy grandes. Si las probabilidades de recepción de "0" y "1" son iguales, la métrica es 0.

Una iteración del turbo decodificador iterativo con codificación de dos etapas

En la fig. 2, para facilitar la comprensión, se muestra una variante del esquema de una iteración de decodificación turbo en codificación de dos etapas. Este esquema se puede generalizar fácilmente al caso de un número arbitrario de etapas de codificación.

El decodificador para una iteración contiene una conexión en cascada de dos decodificadores elementales, cada uno de los cuales, basándose en los criterios de máxima probabilidad a posteriori, toma una decisión "suave" sobre el símbolo transmitido. El primer decodificador de la primera iteración de la salida del demodulador recibe soluciones "suaves" para los símbolos de las secuencias y . Así, a la salida del primer decodificador aparece una estimación del símbolo de información que, tras un intercalado posterior, entra en la entrada del segundo decodificador y es información a priori para el mismo. Usando una decisión "suave" sobre la secuencia , el segundo decodificador forma su estimación [7] $X_{0}$ $X_{1}$ $X_{2}$

Decodificador turbo de tres iteraciones con codificación de dos etapas

De la salida de cada iteración, la solución pasa a la entrada de la siguiente. La organización del trabajo del decodificador turbo de tres iteraciones se muestra en la fig. 3. De iteración en iteración, la solución se refina. Al mismo tiempo, cada iteración funciona con estimaciones "suaves" y también proporciona estimaciones "suaves" a la salida. Por lo tanto, tales esquemas se denominan decodificadores con entrada suave y salida suave ( ing. Soft Input Soft Output (SISO) ) [8] . El proceso de decodificación se detiene después de que se han completado todas las iteraciones o cuando la probabilidad de error de bit alcanza el valor requerido. Después de la decodificación, la solución "dura" final se produce a partir de la solución "blanda" obtenida [7] .

Ventajas y desventajas de los códigos turbo

Beneficios

De todos los métodos modernos de corrección de errores en la práctica, los códigos turbo y los códigos de verificación de paridad de baja densidad son los que más se acercan al límite de Shannon , el límite teórico del rendimiento máximo de un canal ruidoso. Los códigos Turbo le permiten aumentar la velocidad de datos sin requerir un aumento en la potencia del transmisor , o pueden usarse para reducir la potencia requerida cuando se transmite a una velocidad determinada. Una ventaja importante de los códigos turbo es la independencia de la complejidad de decodificación de la longitud del bloque de información, lo que reduce la probabilidad de errores de decodificación al aumentar su longitud [9] .

Desventajas

La principal desventaja de los códigos turbo es la complejidad de decodificación relativamente alta y la alta latencia, lo que los hace inconvenientes para algunas aplicaciones. Pero, por ejemplo, para su uso en canales por satélite, esta desventaja no es determinante, ya que la propia longitud del canal de comunicación introduce un retraso provocado por la finitud de la velocidad de la luz .

Otra desventaja importante de los códigos turbo es la distancia de código relativamente pequeña (es decir, la distancia mínima entre dos palabras de código en el sentido de la métrica elegida ). Esto lleva al hecho de que, aunque el rendimiento del código turbo es alto cuando la tasa de errores de entrada es grande (es decir, en un canal defectuoso), el rendimiento del código turbo es extremadamente limitado cuando la tasa de errores de entrada es baja. [10] Por lo tanto, en buenos canales, para reducir aún más la probabilidad de error, no se utilizan códigos turbo, sino códigos LDPC .

Aunque la complejidad de los algoritmos de codificación turbo utilizados y la falta de software de código abierto han dificultado la adopción de códigos turbo, muchos sistemas modernos utilizan actualmente códigos turbo.

Aplicación de códigos turbo

France Télécom y Telediffusion de France han patentado una amplia clase de turbocódigos, lo que limita la posibilidad de su libre uso y, al mismo tiempo, estimula el desarrollo de nuevos métodos de codificación como, por ejemplo, LDPC .

Los códigos turbo se utilizan activamente en los sistemas de comunicaciones móviles y por satélite , el acceso inalámbrico de banda ancha y la televisión digital . [8] Los códigos Turbo están aprobados en el estándar de comunicación por satélite DVB-RCS . Los códigos Turbo también han encontrado una amplia aplicación en los sistemas de comunicaciones móviles de tercera generación ( estándares CDMA2000 y UMTS ). [9]

Notas

↑ Zolotarev V.V., Ovechkin G.V., Ovechkin P.V. Decodificación multiumbral para sistemas de transmisión de datos digitales . Consultado el 21 de noviembre de 2008. Archivado desde el original el 30 de enero de 2012. (Ruso)
↑ Berrou C., Glavieux A., Thitmajshima P. Near Shannon Limite la codificación y decodificación de corrección de errores: Turbo-códigos ( 1993). Consultado el 21 de noviembre de 2008. Archivado desde el original el 30 de enero de 2012.
↑ Berrou C. Los códigos Turbo de diez años están entrando en servicio (inglés) (2003). Consultado el 21 de noviembre de 2008. Archivado desde el original el 30 de enero de 2012.
↑ Semenov Yu. A. Protocolos de red X.25 . (Ruso)
↑ ECSS- E -ST-50-01C . Archivado desde el original el 30 de enero de 2012.
↑ 1 2 Zubarev Yu. B., Krivosheev M. I., Krasnoselsky I. N. Difusión de televisión digital. Fundamentos, métodos, sistemas. - M.: Instituto de Investigaciones Científicas de la Radio (NIIR), 2001. - P. 112-120.
↑ 1 2 . Komarov S. V., Postnikov S. A., Levshin V. I., Dremachev D. V., Artemiev N. V. Aplicación de códigos turbo en sistemas de comunicación multimedia de tercera generación: Colección de artículos. Teoría y tecnología de la comunicación por radio. - 2003. - Págs. 112-119.
↑ 1 2 Arkhipkin A. Códigos Turbo: potentes algoritmos para los sistemas de comunicación modernos (Journal. Wireless Technologies) (2006). Consultado el 21 de noviembre de 2008. Archivado desde el original el 30 de enero de 2012. (Ruso)
↑ 1 2 Vargauzin V., Protopopov L. Turbo códigos y decodificación iterativa: principios, propiedades, aplicación (2000). (Ruso)
↑ Moon, Todd K. Codificación de corrección de errores: métodos y algoritmos matemáticos. - John Wiley & Sons, 2005. - página 612.