Turbo code
Turbo code est le nom générique d'un code correcteur imaginé dans les années 1990, qui permet de s'approcher aussi près qu'on le souhaite de la limite de Shannon. Les turbo codes représentent une percée majeure dans le domaine des communications numériques. Ils sont utilisés dans de nombreux standards de téléphonie mobile (UMTS, LTE), de communications par satellites (Inmarsat, DVB-RCS) ou de courants porteurs en ligne. Leur inventeur est Claude Berrou qui breveta cette technologie pour le compte de France Télécom et TDF.
Origine
Les turbo codes sont nés au sein de Télécom Bretagne (aujourd'hui IMT Atlantique) à la suite des travaux de Claude Berrou. Ils ont été présentés dans une communication[1] cosignée par Alain Glavieux et Punya Thitimajshima lors de l'International Conference on Communications de à Genève en Suisse.
Lorsqu'il énonça son fameux théorème en 1948, Shannon montrait l'existence d'une borne théorique au-delà de laquelle les communications sont entachées d'erreurs, mais il ne donna pas d'exemple de code réalisable qui permettait d'approcher cette limite. Robert G. Gallager mit au point les codes LDPC (Low Density Parity Check) dans sa thèse au MIT en 1960 qui permettaient d'atteindre cette limite mais à l'époque, leur réalisation pratique était infaisable et ils tombèrent dans l'oubli.
Au début des années 1990, Claude Berrou mit au point les turbo codes qui furent les premiers codes approchant la limite de Shannon pour lesquels on réussit une implémentation matérielle. La clé de cette découverte aurait résidé dans l'utilisation de codes convolutifs récursifs et dans la mise au point de l'information extrinsèque, résultat de la soustraction de l'information a priori (donnée d'entrée) à l'information a posteriori (donnée de sortie). C'est, entre autres, cette soustraction permettant d'éviter les phénomènes de propagation d'erreur dans la boucle « turbo » qui fut difficile à mettre au point.
Principe
Le principe des turbo codes, comme tout code correcteur d'erreur, est d'introduire une redondance dans le message afin de le rendre moins sensible aux bruits et perturbations subies lors de la transmission. Le codage consiste à utiliser deux codeurs simples, dont les entrées ont été entrelacées ; ainsi, chaque codeur voit une série d'informations différentes à son entrée.
Le décodage est une collaboration entre les décodeurs, chacun donnant son « avis » (notion de confiance) sur chaque bit décodé. Cette information est ensuite fournie à l'entrée du prochain décodeur, et ainsi de suite. D'où l'appellation « turbo ».
Codage
Un turbo codeur classique résulte de l'association de deux (ou plus) codeurs. Il s'agit souvent de codeurs convolutifs récursifs systématiques (RSC : Recursive Systematic Coder) car leur récursivité apporte des propriétés pseudo-aléatoires intéressantes.
Concrètement, le turbo codeur produira typiquement trois sorties à envoyer sur le canal de transmission (après modulation éventuelle) :
- la sortie dite systématique, c'est-à -dire l'entrée même du codeur (la séquence )
- la sortie de parité 1 : la sortie du premier codeur
- la sortie de parité 2 : la sortie du deuxième codeur. La différence entre ces deux sorties vient du fait que la trame est entrelacée avant d'entrer dans le deuxième codeur. Elle est « mélangée ».
Ce codage permet donc de répartir l'information apporté par un bit de la trame sur ses voisins (avec le codage de parité 1) et même sur toute la longueur de la trame transmise (avec le codage de parité 2). Ainsi, si une partie du message est fortement abîmée pendant la transmission, l'information peut encore se retrouver ailleurs.
DĂ©codage
Le décodage est le fruit de la collaboration des décodeurs. Ceux-ci vont s'échanger de l'information de manière itérative afin d'améliorer la fiabilité (valeur calculée probabiliste, ou valeur soft) de la décision qui sera prise pour chaque symbole.
La trame arrive, entre dans le premier décodeur, et donne des valeurs soft. Ce qui provient de la trame d'arrivée est supprimé, pour ne garder que les informations extrinsèques apportées par le décodeur (sinon il y a un effet d'avalanche).
Puis les données d'arrivée et les données extrinsèques sont entrelacées et fournies à l'entrée du second décodeur. Une itération consiste en l'activation de chaque décodeur une fois. Ainsi, plus il y a d'itérations, plus le décodeur convergera vers la bonne solution ; cependant effectuer plus d'itérations nécessite souvent plus de temps et plus de matériel.
Utilisation
En raison de leurs excellentes performances de décodage et de la complexité calculatoire modérée des turbo décodeurs, les turbo codes ont été adoptés par plusieurs organismes pour être intégrés dans leurs standards. C'est ainsi que la NASA les utilise dans toutes ses sondes spatiales construites à partir de 2003. L'Agence spatiale européenne (ESA) a été la première agence spatiale à utiliser les turbo codes dans la sonde lunaire SMART-1. Les turbos codes sont aussi utilisés par l'UMTS et l'ADSL 2.
Les turbo codes fonctionnent très bien avec les techniques de multiplexage et de modulation OFDM et OFDMA car ils bénéficient ainsi des étalements en temps et en fréquence du système ; dans les réseaux mobiles 4G LTE et LTE Advanced, ces 2 technologies (turbo codes et OFDMA) sont combinées.
Notes et références
- Claude Berrou, Alain Glavieux et Punya Thitimajshima, « Near Shannon limit error-correcting coding and decoding », IEEE International Conference on Communications, vol. 2,‎ , p. 1064-1070 (ISBN 0-7803-0950-2, lire en ligne)