Turbo código

Los turbo códigos son una nueva clase de códigos de corrección de errores (FEC), que se introdujeron, junto con un algoritmo de decodificación. La importancia de los turbo códigos es que permiten una comunicación fiable y su eficiencia energética está muy cerca del límite teórico predicho por Shannon. Desde su introducción, los turbo códigos se han utilizado en aplicaciones de baja potencia, como las comunicaciones por satélite, así como para aplicaciones de interferencia limitada, como los servicios de tercera generación (3G) de comunicaciones móviles.

Historia[editar]

En 1993, un grupo de investigadores de Francia presentó una nueva clase de códigos de corrección de errores y una técnica de decodificación iterativa asociada a estos códigos. Estos códigos se llamaron turbo códigos. Esto produjo un gran avance en la teoría de la codificación. Los resultados iniciales mostraron que los turbo códigos podían conseguir una eficiencia energética muy cercana al límite predicho por Shannon (a 0.5 dB del límite). Esto constituye un aumento significativo en la eficiencia energética sobre otras técnicas de codificación conocidas en el momento.

Este fue un resultado extraordinario que en un principio fue recibido con escepticismo. Pero, más tarde, otros investigadores comenzaron a validar los resultados de forma independiente, y se comenzó una investigación masiva con el objetivo de explicar y mejorar notablemente los turbo códigos. Gran parte de esta investigación se centró en la mejora de la viabilidad de los turbo códigos .

A finales de la década de 1990, las virtudes de los turbo códigos eran bien conocidas, y se empezaron a adaptarse en los diferentes sistemas. Actualmente se incorporan en los estándares utilizados por las comunicaciones de la NASA en el espacio (CCSD), las comunicaciones por satélite, la radiodifusión de vídeo digital (DVB-T), y en los dos estándares de comunicación móvil de tercera generación (UMTS y CDMA2000).

Características[editar]

La turbo codificación:

Las prestaciones de un codificador convolucional mejoran al aumentar la memoria, pero no se puede aumentar la memoria indiscriminadamente ya que la complejidad en el proceso de decodificación crece exponencialmente.
Los turbo códigos son esquemas de codificación que aumentan la memoria de codificación de forma artificial.
Se basa en concatenar esquemas de codificación relativamente simples con el fin de obtener un código equivalente a uno de prestaciones más complejas.

Las características fundamentales de los turbo códigos son:

Uso de codificación paralela concatenada
Uso de codificadores convolucionales recursivos
Uso de un dispersor pseudoaleatorio
Uso de decodificación iterativa

Funcionamiento[editar]

Los turbo códigos se basan en la concatenación de dos codificadores relativamente sencillos separados por un dispersor.

El conjunto es equivalente a un único codificador convolucional de memoria tan grande como la profundidad del dispersor pero con un proceso de decodificación simplificado que en ningún caso alcanza la complejidad del convolucional equivalente.

Un único código de protección de errores no siempre proporciona la protección necesaria con una complejidad aceptable. La solución es concatenar dos (o más) códigos, esto crea un código mucho más potente que los tradicionales.

La propuesta original de los turbo códigos consistía en la concatenación de dos codificadores convolucionales sistemáticos (RSC) con un dispersor.

La forma de trabajar de estos códigos se basa en permitir que el codificador final entregue unas decisiones leves o soft en lugar de graves o hard, con el objetivo de poder realimentar estas decisiones, de nuevo, hacia el código inicial en un proceso iterativo similar al que gobierna el principio de los motores turbo. Cuantas más iteraciones se aplican a este proceso más refinada y fiable es la decisión hard definitiva, y se reduce en cada iteración la probabilidad de error.

El codificador[editar]

Un turbo código es la concatenación en paralelo de dos códigos RSC separados por un dispersor.

En el codificador del esquema los dos codificadores tienen la misma tasa ½ del codificador RSC. El codificador de la rama de arriba recibe los datos directamente, mientras que el codificador de la rama inferior recibe la información después de dispersarse por una función de permutación α.

El dispersor α es en general un dispersor pseudo-aleatorio, que mueve los bits de la posición i a la posición α (i) de acuerdo con una prescripción (regla), que se generada aleatoriamente. El dispersor opera en bloques, intercalado grupos de bits a la vez, y por tanto los turbo códigos son en realidad bloques de códigos. Dado que ambos codificadores son sistemáticos y reciben el mismo conjunto de datos (aunque con un orden permutado), solo hay que enviar la salida de una de las ramas. Por convenio, se transmite la salida de la rama superior y la salida del codificador inferior no se transmite. Sin embargo, las salidas de paridad de los dos codificadores se transmiten. La tasa general de un turbo código formado por la concatenación en paralelo de dos tasas de 1 / 2 de un codificador sistemático es r = 1 / 3. La tasa típica de un turbo código incrementa a r = 1 / 2 para transmitir solo los índices impares de los bits de paridad del codificador superior y para transmitir los índices pares de los bits de paridad del codificador inferior.

El decodificador[editar]

Un turbo código, como ya hemos dicho anteriormente, se basa en la utilización de dos o más códigos constituyentes, la decodificación se basa en aplicar el criterio MAP para poder tener tanto entradas como salidas soft (decodificador soft in - soft out). Como se puede ver, la filosofía turbo se basa en aprovechar la información extrínseca proporcionada por el código y convertirla en información a priori para una etapa posterior de decodificación (esta parte se toma como 0 en la primera etapa). En un esquema con dos códigos este bucle de realimentación debe tener en cuenta los dos decodificadores y también la etapa de dispersión.

Al igual que con los códigos convolucionales, se puede obtener una solución ML utilizando la ecuación $\quad {\tilde {m}}=arg\left\{max_{m}P[m|y]\right\}$ y el algoritmo de Viterbi. Sin embargo, debido a la presencia del dispersor, la complejidad del algoritmo Viterbi, cuando se utiliza para descodificar los turbo códigos es $O(2^{L})$ , donde L es el tamaño del frame de datos. Esto hace que para descodificar los turbo códigos , se tenga que buscar una solución de menor complejidad, aunque sea una solución subóptima. En particular, se puede encontrar una buena estimación de los datos solucionando el siguiente sistema de ecuaciones:

\quad A_{i}^{(1)}=log{\frac {P[m_{i}=1|y^{(0)},y^{(1)},z^{(2)}]}{P[m_{i}=0|y^{(0)},y^{(1)},z^{(2)}]}}

(1)

\quad {\tilde {A}}_{i}^{(2)}=log{\frac {P[{\tilde {m}}_{i}=1|{\tilde {y}}^{(0)},y^{(2)},{\tilde {z}}^{(1)}]}{P[{\tilde {m}}_{i}=0|{\tilde {y}}^{(0)},y^{(2)},{\tilde {z}}^{(1)}]}}

(2)

Donde $y^{(0)}$ son los bits sistemáticos, $y^{(1)}$ son los bits de paridad observados por el codificador 1 y $y^{(2)}$ son los bits de paridad observados por el codificador 2. El acento sobre una variables representa su valor dispersado, es decir, ${\tilde {y}}$ es la versión dispersada de y. "A" es log-likelihood ratio (LLR) o la medida logarítmica de similitud (LLR), y z es la información extrínseca que se relaciona con LLR a través de:

\quad z_{i}^{(1)}=A_{i}^{(1)}-y_{i}^{(0)}-z_{i}^{(2)}

(3)

\quad {\tilde {z}}_{i}^{(2)}={\tilde {A}}_{i}^{(2)}-{\tilde {y}}_{i}^{(0)}-{\tilde {z}}_{i}^{(1)}

(4)

El sistema de ecuaciones se puede resolver iterativamente mediante la estructura que se muestra en la figura. EL decodificador 1 determina la solución de eq (1) y el decodificador 2 determina la solución de eq (2). Cada decodificador pasa la información al otro decodificador, que a su vez mejora la estimación de probabilidades a posteriori utilizando la información obtenida por el otro decodificador. La estimación final de los datos se obtiene limitando la salida de uno de los descodificadores (por convención, la salida del segundo decodificador) mediante:

f(n)={\begin{matrix}1&{ifA_{i}^{(2)}>0}\\0&{ifA_{i}^{(2)}<1}\end{matrix}}

(5)

Los turbo códigos deben su nombre a la estructura de retroalimentación de la figura y es una analogía de un motor turbo. De hecho, no hay nada "turbo", sobre los turbo códigos, más bien solo existe el efecto turbo procedente de la implementación del decodificador.

La solución a posteriori LLR's de (1) y (2) se calculan utilizando una derivación símbolo a símbolo del algoritmo MAP [3]. Aunque el algoritmo de [3] se puede utilizar directamente para calcular los LLR's, el algoritmo es computacionalmente complejo y sensible a las precisión numérica y no se usa. Estos problemas se ven atenuados realizando la operación en el dominio logarítmico-aritmético, tal como se presenta en [4] y [5]. El algoritmo resultante se denomina Log-MAP. El algoritmo se compone de dos instancias del algoritmo de Viterbi - una realización de una recursión hacia delante y la otra la realización de una recursión hacia atrás. Por lo tanto la complejidad del algoritmo LogMAP es el doble de la del algoritmo de Viterbi.

Rendimiento[editar]

Hay muchos factores que afectan el rendimiento de los turbo códigos. El parámetro que más influye es el tamaño del dispersor. Cuando el tamaño del dispersor es grande, el rendimiento mejora. Esto implicaría que se debería escoger el tamaño más grande posible. Sin embargo, a medida que aumenta el tamaño del dispersor también aumenta la latencia del descodificador, ya que se ha de recibir todo el código para poder decodificarlo completamente. Por lo tanto los turbo códigos poseen un equilibrio inherente entre el rendimiento y la latencia.

Otro parámetro que afecta el rendimiento es la tasa general del código. Al igual que para otros códigos, el rendimiento mejora a medida que la tasa de código es inferior. Cuando las tasas de código que se utilizan son superiores a 1/3, el patrón que se utiliza afecta al rendimiento. Al igual que en los códigos convolucionales, la restricción de la longitud del código también influye en el rendimiento. Sin embargo, el impacto que tiene la restricción de la longitud en el rendimiento es débil, y por lo tanto solo se consideran las restricciones de longitud cortas de K = 3, 4, o 5 para el diseño de los turbo códigos. El diseño del dispersor juega un papel importante en el diseño de un turbo código, para obtener una relación de señal a ruido SNR buena. En general, un diseño del dispersor al azar dará un buen rendimiento, mientras que hay que evitar dispersores altamente estructuradas, como el "dispersor de bloque". La elección del algoritmo de decodificación y el número de iteraciones de decodificación también influyen en el rendimiento. Se puede ver que el rendimiento mejora a medida que aumenta el número de iteraciones. Esta mejora sigue una ley de rendimientos decrecientes. Además, el número de iteraciones necesarias está en función del tamaño del dispersor cuanto mayor es el dispersor se requieren más iteraciones.

Aunque los códigos de turbo ofrecen un rendimiento extraordinario para tasas de error de bit alrededor de $10^{-5}$ BER, el rendimiento para tasas de bit de error muy pequeñas no es muy impresionante. Para relaciones señal-ruido altas, puede ser mejor utilizar un código convolucional. Este fenómeno puede ser explicado en términos de la distancia del espectro de Hamming de los turbo códigos.