Turbocodi

Els turbocodis són una nova classe de codis de correcció d'errors FEC, que es van introduir, juntament amb un algorisme de descodificació. La importància dels turbocodis és que permeten una comunicació fiable i la seva eficiència energètica estar molt propera al límit teòric predit per Shannon. Des de la seva introducció, els turbocodis s'han utilitzat per a aplicacions de baixa potència, com ara les comunicacions per satèl·lit, així com per a aplicacions d'interferència limitada, com els serveis de tercera generació (3G) de comunicacions mòbils.

Història

El 1993, un grup d'investigadors de França va presentar una nova classe de codis de correcció d'errors i una tècnica de descodificació iterativa associada a aquests codis. Aquests codis es van anomenar turbocodis. Es va produir un gran avanç en la teoria de la codificació. Els resultats inicials van mostrar que els turbocodis podien aconseguir una eficiència energètica molt propera al límit predit per Shannon (a 0.5 dB del límit). Això constitueix un augment significatiu en l'eficiència energètica sobre altres tècniques de codificació conegudes en el moment.

Aquest va ser un resultat extraordinari que al principi va ser rebut amb escepticisme. Però, més tard, altres investigadors van començar a validar els resultats de forma independent, i es va començar una recerca massiva amb l'objectiu d'explicar i millorar notablement els turbocodis. Gran part d'aquesta investigació es va centrar en la millora de la viabilitat dels turbocodis.

A finals de la dècada de 1990, les virtuts dels turbocodis eren ben conegudes, i es van començar a adaptar-se en els diferents sistemes. Actualment s'incorporen en els estàndards utilitzats per les comunicacions de la NASA en l'espai (CCSDS), les comunicacions per satèl·lit, la radiodifusió de vídeo digital (DVB-T), i en els dos estàndards de comunicació mòbil de tercera generació (UMTS i CDMA2000).

Característiques

La Turbo codificació:

• Les prestacions d'un codificador convolucional milloren a l'augmentar la memòria, però no es pot augmentar la memòria indiscriminadament, ja que la complexitat en el procés de descodificació creix exponencialment
• Els turbocodis són esquemes de codificació que augmenten la memòria de codificació de forma artificial.
• Es basen a concatenar esquemes de codificació relativament simples amb la finalitat d'obtenir un codi equivalent en prestacions a un més complex

Les característiques fundamentals dels turbocodis són:

• Ús de codificació paral·lela concatenada
• Ús de codificadors Convolucionals Recursius
• Ús d'un dispersor Pseudo-aleatori
• Ús de descodificació iterativa

Turbocodis: funcionament

Diagrama d'un Sistema de Transmissió

Els turbocodis es basen en la concatenació de dos codificadors relativament senzills separats per un dispersor. El conjunt és equivalent a un únic codificador convolucional de memòria tan gran com la profunditat del dispersor però amb un procés de descodificació simplificat que en cap cas arribaria a la complexitat del convolucional equivalent.

Un únic codi de protecció d'errors no sempre proporciona la protecció necessària amb una complexitat acceptable. La solució és concatenar dos (o més) codis, això crea un codi molt més potent que els tradicionals. La proposta original dels turbocodis consistia a la concatenació de dos codificadors convolucionals sistemàtics (RSC) amb un dispersor.

La forma de treballar d'aquests codis es basa a permetre que el codificador final lliuri unes decisions lleus o soft en compte de greus o hard, amb l'objectiu de poder realimentar aquestes decisions, un altre cop, cap al codi inicial en un procés iteratiu semblant al que governa el principi dels motors turbo. Quantes més iteracions s'apliquen a aquest procés més refinada i fiable acaba sent la decisió hard definitiva, reduint en cada iteració la probabilitat d'error.

El Codificador

Diagrama d'un Turbo Codificador

Un turbocodi és la concatenació en paral·lel de dos codis RSC separats per un dispersor.

En el codificador de l'esquema els dos codificadors tenen la mateixa taxa ½ del codificador RSC. El codificador de la branca de dalt rep les dades directament, mentre que el codificador de la branca inferior rep la informació després de dispersar-se per una funció de permutació α. El Dispersor α és en general un dispersor pseudo-aleatori, que mou els bits de la posició i a la posició α(i) d'acord amb una prescripció (regla), però que és generada aleatòriament. El dispersor opera en blocs, intercalat L bits a la vegada, i per tant els turbocodis són en realitat blocs de codis. Atès que tots dos codificadors són sistemàtics i reben el mateix conjunt de dades (encara que amb un ordre permutat), només cal enviar la sortida d'una de les branques. Per conveni, es transmet la sortida de la branca superior mentre que la sortida del codificador inferior no es transmet. No obstant això, les sortides de paritat dels dos codificadors es transmeten. La taxa general d'un turbocodi format per la concatenació en paral·lel de dues taxes de 1/2 d'un codificador sistemàtic és r = 1 / 3. La taxa típica d'un turbocodi s'incrementa a r= 1 / 2 per transmetre només els índexs senars delsbits de paritat del codificador superior i per transmetre els índexs parells dels bits de paritat del codificador inferior.

El Descodificador

Un turbocodi, com ja hem dit anteriorment, es basa en la utilització de dos o més codis constituents, la descodificació dels quals es basa a aplicar el criteri MAP per tal de poder tenir tant entrades com sortides soft (descodificador soft in – soft out). Com es pot veure, la filosofia turbo es basa a aprofitar la informació extrínseca proporcionada pel codi i convertir-la en informació a priori per a una etapa següent de descodificació (aquesta part s'agafa com 0 en la primera etapa). En un esquema amb dos codis aquest bucle de realimentació ha de tenir en compte tots dos descodificadors i també l'etapa de dispersio.

Diagrama d'un Turbo Descodificador

Igual que amb els codis convolucionals, es pot obtenir una solució ML utilitzant l'equació: $\quad {\tilde {m}}=arg\left\{max_{m}P[m|y]\right\}$ i l'algorisme de Viterbi. No obstant això,a causa de la presència del dispersor,la complexitat de l'algorisme Viterbi quan s'utilitza per a descodificar els turbocodis és $O(2^{L})$, on L és la mida del frame de dades. Això fa que per descodificar els turbocodis, s'hagi de buscar una solució de menor complexitat, encara que sigui una solució subòptima. En particular, es pot trobar una bona estimació de les dades solucionant el següent sistema d'equacions:

$\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)

On $y^{(0)}$ són els bits sistemàtics observats, $y^{(1)}$ són els bits de paritat observats pel codificador 1 i $y^{(2)}$ són els bits de paritat observats pel codificador 2. L'accent sobre una variables representa el seu valor dispersat, és a dir, ${\tilde {y}}$ és la versió dispersada de y. "A" es log-likelihood ratio (LLR) o la mesura logarítmica de versemblanç (LLR), i z és l'anomenada informació extrínseca que es relaciona amb 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 d'equacions es pot resoldre iterativament mitjançant l'estructura que es mostra a la figura. EL descodificador 1 determina la solució d'eq (1) i el descodificador 2 determina la solució d'eq (2). Cada descodificador passa la informació a l'altre descodificador, que al vegada millora l'estimació de probabilitats a posteriori utilitzant la informació obtinguda per l'altre descodificador. L'estimació final de les dades s'obté limitant la sortida d'un dels descodificadors (per convenció, la sortida del segon descodificador) mitjançant:

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

Els turbocodis deuen el seu nom a l'estructura de retroalimentació de la figura i és una analogia amb un motor turbo. De fet, no hi ha res "turbo", sobre els turbocodis, més aviat només existeix l'efecte turbo procedent de la implementació del descodificador.

La solució a posteriori LLR's de (1) i (2) es calculen utilitzant una derivació símbol a símbol de l'algorisme MAP [3]. Encara que l'algorisme de [3] es pot utilitzar directament per calcular els LLR's, l'algorisme és computacionalment complex i sensible a les precisió numèrica.

Aquests problemes es veuen atenuats realitzant l'operació en el domini logaritmic-aritmètic, tal com es presenta en [4] i [5]. L'algorisme resultant s'anomena Log-MAP. L'algorisme es compon de dues instàncies de l'algorisme de Viterbi - una realització d'una recursió cap endavant i l'altra la realització d'una recursió cap endarrere. Per tant la complexitat de l'algorisme LogMAP és el doble de la de l'algorisme de Viterbi.

Rendiment

Hi ha molts factors que afecten el rendiment dels turbocodis. El paràmetre que més influeix és la mida del dispersor. Quan la mida del dispersor és gran, el rendiment millora. Això implicaria que s'hauría de triar la mida més gran possible. No obstant això, a mesura que augmenta la grandària del dispersor també augmenta la latència del descodificador, ja que s'ha de rebre tot el codi per poder-se descodificar completament. Per tant els turbocodis posseeix un equilibri inherent entre el rendiment i la latència.

Un altre paràmetre que afecta el rendiment és la taxa general del codi. Igual que per altres codis, el rendiment millora a mesura que la taxa de codi esdevé inferior. Quan les taxes de codi que s'utilitzen són superiors a 1 / 3, llavors el patró que es fa servir afecta el rendiment. Igual que en els codis convolucionals, la restricció de la longitud del codi també influeix en el rendiment. No obstant això, l'impacte que té la restricció de la longitud en el rendiment és feble, i per tant només es consideren les restriccions de longitud curtes de K = 3, 4, o 5 pel disseny de turbocodis. El disseny del dispersor té un paper important en l'execució d'un turbocodi, per obtenir una relació de senyal a soroll SNR. En general, un disseny del dispersor a l'atzar donarà un bon rendiment, mentre que dispersors altament estructurades, com ara el "Dispersor de bloc" s'ha d'evitar. L'elecció de l'algorisme de descodificació i el nombre d'iteracions de descodificació també influeixen en el rendiment. Es pot veure que el rendiment millora a mesura que s'augmenta el nombre d'iteracions. Aquesta millora segueix una llei de rendiments decreixents. A més, el nombre d'iteracions necessàries està en funció de la grandària del dispersor- quan més gran és el dispersor es requereixen més iteracions.

Tot i que els codis de turbo ofereixen un rendiment extraordinari per a taxes d'error de bit a voltant de $10^{-5}$ BER, el rendiment per a taxes de bit d'error molt petites no és molt impressionant. Per relacions senyal-soroll altes, pot ser millor utilitzar un codi convolucional. Aquest fenomen pot ser explicat en termes de la distància de l'espectre de Hamming dels turbocodis.

Aplicacions on s'utilitzen els turbocodis

Els turbocodis s'on utilitzats en els sistemes de telecomunicacions, alguns exemples són:

• En Comunicacions satèl·lit i espacials
• En la televisió Digital, per exemple en: DVB-RCS, DVB-SH, DVB-S2
• En les Comunicacions de fibra òptica
• En Comunicacions sense fils (wireless)
• En Sistemes de gravació óptics
• En els Modems ADSL
• En Telemetría

Vegeu també

• Codi corrector
• Codi de Hamming (7,4)
• Codi de Hamming
• Teoria de la informació

Bibliografia

• Turbo codes: desirable and designable, Alexandre Giulietti, Bruno Bougard, Liesbet van der Perre
• Turbo code applications: a journey from a paper to realization, Keattisak Sripimanwat
• Turbo Codes and Iterative Processing, Matthew C. Valenti
• Codificación de Canal. Turbocodificación, Matilde Sánchez y Javier Ramos
• Sistemes de Transmissió Joan Claudi Socoró, Jose A. Morán i Rosa Maria Alsina

Enllaços externs

• Turbo Codes, Matthew C. Valenti
• Fundamentals of Turbo Codes
• Turbo Codes Arxivat 2011-01-24 a Wayback Machine.