Turbocode - Turbo code

En théorie de l'information , les turbocodes (à l'origine en français Turbocodes ) sont une classe de codes de correction d'erreur directe (FEC) hautes performances développés vers 1990-1991, mais publiés pour la première fois en 1993. Ils ont été les premiers codes pratiques à se rapprocher de près du canal maximum capacité ou limite de Shannon , un maximum théorique pour le débit de code auquel une communication fiable est encore possible compte tenu d'un niveau de bruit spécifique. Les turbocodes sont utilisés dans les communications mobiles 3G / 4G (par exemple, dans UMTS et LTE ) et dans les communications par satellite ( espace lointain ) ainsi que d'autres applications où les concepteurs cherchent à obtenir un transfert d'informations fiable sur des liaisons de communication limitées en bande passante ou en latence dans le présence de bruit de corruption de données. Les turbocodes sont en concurrence avec les codes de contrôle de parité à faible densité (LDPC), qui offrent des performances similaires.

Le nom "code turbo" est né de la boucle de rétroaction utilisée lors du décodage normal du code turbo, qui était analogue à la rétroaction d'échappement utilisée pour la suralimentation du moteur . Hagenauer a fait valoir que le terme turbocode est un abus de langage car il n'y a pas de rétroaction impliquée dans le processus de codage.

Histoire

La demande de brevet fondamentale pour les turbocodes a été déposée le 23 avril 1991. La demande de brevet mentionne Claude Berrou comme le seul inventeur des turbocodes. Le dépôt de brevet a donné lieu à plusieurs brevets dont le brevet américain 5 446 747 , qui a expiré le 29 août 2013.

Le premier article public sur les turbocodes était " Near Shannon Limit Error-correcting Coding and Decoding: Turbo-codes ". Cet article a été publié en 1993 dans les Actes de la conférence internationale sur les communications de l'IEEE. Le document de 1993 a été formé à partir de trois soumissions distinctes qui ont été combinées en raison de contraintes d'espace. La fusion a amené le journal à citer trois auteurs : Berrou, Glavieux et Thitimajshima (de Télécom Bretagne, ex ENST Bretagne , France). Cependant, il ressort clairement du dépôt de brevet original que Berrou est le seul inventeur des turbocodes et que les autres auteurs de l'article ont contribué à d'autres éléments que les concepts de base.

Les turbocodes étaient si révolutionnaires au moment de leur introduction que de nombreux experts dans le domaine du codage ne croyaient pas aux résultats rapportés. Lorsque les performances ont été confirmées, une petite révolution dans le monde du codage a eu lieu qui a conduit à l'étude de nombreux autres types de traitement itératif du signal.

La première classe de turbocode était le code convolutif concaténé parallèle (PCCC). Depuis l'introduction des turbocodes parallèles originaux en 1993, de nombreuses autres classes de turbocodes ont été découvertes, y compris les versions série des codes convolutifs concaténés en série et des codes à accumulation répétée . Des méthodes de décodage turbo itératif ont également été appliquées à des systèmes FEC plus conventionnels, y compris des codes convolutifs corrigés par Reed-Solomon, bien que ces systèmes soient trop complexes pour des implémentations pratiques de décodeurs itératifs. L'égalisation turbo découle également du concept de codage turbo.

En plus des turbocodes, Berrou a également inventé les codes convolutifs systématiques récursifs (RSC), qui sont utilisés dans l'exemple de mise en œuvre des turbocodes décrits dans le brevet. Les turbocodes qui utilisent des codes RSC semblent fonctionner mieux que les turbocodes qui n'utilisent pas de codes RSC.

Avant les turbocodes, les meilleures constructions étaient des codes concaténés en série basés sur un code de correction d'erreur Reed-Solomon externe combiné à un code convolutif de courte longueur de contrainte décodé par Viterbi , également connu sous le nom de codes RSV.

Dans un article ultérieur, Berrou a crédité l'intuition de "G. Battail, J. Hagenauer et P. Hoeher, qui, à la fin des années 80, ont mis en évidence l'intérêt du traitement probabiliste". Il ajoute « R. Gallager et M. Tanner avaient déjà imaginé des techniques de codage et de décodage dont les principes généraux sont intimement liés », alors que les calculs nécessaires étaient alors impraticables.

Un exemple d'encodeur

Il existe de nombreuses instances différentes de turbocodes, utilisant différents encodeurs de composants, rapports d'entrée/sortie, entrelaceurs et modèles de perforation. Cet exemple de mise en œuvre d'un codeur décrit un turbo-codeur classique et illustre la conception générale des turbo-codes parallèles.

Cette implémentation de codeur envoie trois sous-blocs de bits. Le premier sous-bloc est le bloc à m bits de données utiles. Le deuxième sous-bloc est constitué de n/2 bits de parité pour les données utiles, calculés à l'aide d'un code convolutif systématique récursif (code RSC). Le troisième sous-bloc est constitué de n/2 bits de parité pour une permutation connue des données utiles, à nouveau calculée à l'aide d'un code RSC. Ainsi, deux sous-blocs de bits de parité redondants mais différents sont envoyés avec la charge utile. Le bloc complet a m + n bits de données avec un taux de code de m / ( m + n ) . La permutation des données utiles est effectuée par un dispositif appelé entrelaceur .

Du point de vue matériel, ce turbo codeur est constitué de deux codeurs RSC identiques, C ₁ et C ₂ , comme illustré sur la figure, qui sont connectés l'un à l'autre à l'aide d'un schéma de concaténation, appelé concaténation parallèle :

Sur la figure, M est un registre mémoire. La ligne à retard et l'entrelaceur forcent les bits d'entrée d _k à apparaître dans des séquences différentes. A la première itération, la séquence d'entrée d _k apparaît aux deux sorties du codeur, x _k et y _1k ou y _{2k en} raison de la nature systématique du codeur. Si les codeurs C ₁ et C ₂ sont utilisés en n ₁ et n ₂ itérations, leurs cadences sont respectivement égales à

${\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}}}$

Le décodeur

Le décodeur est construit de la même manière que l'encodeur ci-dessus. Deux décodeurs élémentaires sont interconnectés entre eux, mais en série et non en parallèle. Le décodeur fonctionne à une vitesse inférieure (c'est-à-dire, ), ainsi, il est destiné au codeur, et est destiné en conséquence. donne une décision douce qui provoque un retard. Le même retard est causé par la ligne à retard dans l'encodeur. Le fonctionnement du 's provoque un retard. ${\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}}$

Un entrelaceur installé entre les deux décodeurs est utilisé ici pour diffuser les rafales d'erreurs provenant de la sortie. Le bloc DI est un module de démultiplexage et d'insertion. Il fonctionne comme un commutateur, redirigeant les bits d'entrée vers un moment et vers un autre. À l'état OFF, il alimente les deux et les entrées avec des bits de remplissage (zéros). ${\displaystyle \textstyle DEC_{1}}$${\displaystyle \textstyle DEC_{1}}$${\displaystyle \textstyle DEC_{2}}$${\displaystyle \textstyle y_{1k}}$${\displaystyle \textstyle y_{2k}}$

Considérons un canal AWGN sans mémoire et supposons qu'à la k- ième itération, le décodeur reçoit une paire de variables aléatoires :

${\displaystyle {\begin{aligned}~x_{k}&=(2d_{k}-1)+a_{k}\\~y_{k}&=2(Y_{k}-1)+b_{ k}\end{aligné}}}$

où et sont des composantes de bruit indépendantes ayant la même variance . est un k- ième bit de la sortie du codeur. ${\displaystyle \textstyle a_{k}}$${\displaystyle \textstyle b_{k}}$${\displaystyle \textstyle \sigma ^{2}}$${\displaystyle \textstyle Y_{k}}$${\displaystyle \textstyle y_{k}}$

Les informations redondantes sont démultiplexées et envoyées via DI à (quand ) et à (quand ). ${\displaystyle \textstyle DEC_{1}}$${\displaystyle \textstyle y_{k}=y_{1k}}$${\displaystyle \textstyle DEC_{2}}$${\displaystyle \textstyle y_{k}=y_{2k}}$

${\displaystyle \textstyle DEC_{1}}$donne une décision douce ; c'est à dire:

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

et le livre à . est appelé le logarithme du rapport de vraisemblance (LLR). est la probabilité a posteriori (APP) du bit de données qui montre la probabilité d'interpréter un bit reçu comme . La prise en compte du LLR conduit à une décision difficile ; c'est-à-dire un bit décodé. ${\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}}$

Il est connu que l' algorithme de Viterbi est incapable de calculer APP, il ne peut donc pas être utilisé dans . Au lieu de cela, un algorithme BCJR modifié est utilisé. Pour , l' algorithme de Viterbi est approprié. ${\displaystyle \textstyle DEC_{1}}$${\displaystyle \textstyle DEC_{2}}$

Cependant, la structure représentée n'est pas optimale, car elle n'utilise qu'une fraction appropriée des informations redondantes disponibles. Afin d'améliorer la structure, une boucle de rétroaction est utilisée (voir la ligne pointillée sur la figure). ${\displaystyle \textstyle DEC_{1}}$

Approche décisionnelle douce

Le frontal du décodeur produit un entier pour chaque bit du flux de données. Cet entier est une mesure de la probabilité que le bit soit un 0 ou un 1 et est également appelé bit mou . L'entier peut être tiré de la plage [−127, 127], où :

• -127 signifie "certainement 0"
• −100 signifie "très probablement 0"
• 0 signifie "cela peut être 0 ou 1"
• 100 signifie "très probablement 1"
• 127 signifie "certainement 1"

Cela introduit un aspect probabiliste dans le flux de données du frontal, mais il transmet plus d'informations sur chaque bit que juste 0 ou 1.

Par exemple, pour chaque bit, le frontal d'un récepteur sans fil traditionnel doit décider si une tension analogique interne est supérieure ou inférieure à un niveau de tension de seuil donné. Pour un décodeur de turbocode, le frontal fournirait une mesure entière de la distance entre la tension interne et le seuil donné.

Pour décoder le bloc de données à m + n bits, le frontal du décodeur crée un bloc de mesures de vraisemblance, avec une mesure de vraisemblance pour chaque bit dans le flux de données. Il y a deux décodeurs parallèles, un pour chacune des n / 2 sous-blocs de parité de bits. Les deux décodeurs utilisent le sous-bloc de m probabilités pour les données utiles . Le décodeur travaillant sur le deuxième sous-bloc de parité connaît la permutation que le codeur a utilisée pour ce sous-bloc.

Résoudre des hypothèses pour trouver des bits

L'innovation clé des turbocodes est la façon dont ils utilisent les données de probabilité pour réconcilier les différences entre les deux décodeurs. Chacun des deux décodeurs convolutifs génère une hypothèse (avec des vraisemblances dérivées) pour le motif de m bits dans le sous-bloc de charge utile. Les schémas binaires d'hypothèse sont comparés, et s'ils diffèrent, les décodeurs échangent les probabilités dérivées qu'ils ont pour chaque bit dans les hypothèses. Chaque décodeur incorpore les estimations de vraisemblance dérivées de l'autre décodeur pour générer une nouvelle hypothèse pour les bits de la charge utile. Puis ils comparent ces nouvelles hypothèses. Ce processus itératif se poursuit jusqu'à ce que les deux décodeurs proposent la même hypothèse pour le motif à m bits de la charge utile, typiquement en 15 à 18 cycles.

Une analogie peut être établie entre ce processus et celui de résoudre des énigmes de références croisées comme les mots croisés ou le sudoku . Considérez un jeu de mots croisés partiellement terminé, peut-être brouillé. Deux solveurs de puzzle (décodeurs) tentent de le résoudre : l'un ne possédant que les indices "down" (bits de parité), et l'autre ne possédant que les indices "cross". Pour commencer, les deux solveurs devinent les réponses (hypothèses) à leurs propres indices, notant à quel point ils sont confiants dans chaque lettre (bit de charge utile). Ensuite, ils comparent leurs notes, en échangeant des réponses et des cotes de confiance les uns avec les autres, en remarquant où et comment elles diffèrent. Sur la base de ces nouvelles connaissances, ils proposent tous deux des réponses et des cotes de confiance mises à jour, répétant l'ensemble du processus jusqu'à ce qu'ils convergent vers la même solution.

Performance

Les turbocodes fonctionnent bien en raison de la combinaison attrayante de l'apparence aléatoire du code sur le canal et de la structure de décodage physiquement réalisable. Les turbocodes sont affectés par un plancher d'erreur .

Applications pratiques utilisant les turbocodes

Télécommunications :

• Les turbocodes sont largement utilisés dans les normes de téléphonie mobile 3G et 4G ; par exemple, en HSPA , EV-DO et LTE .
• MediaFLO , système de télévision mobile terrestre de Qualcomm .
• Le canal d'interaction des systèmes de communication par satellite , tels que DVB-RCS et DVB-RCS2 .
• Les missions récentes de la NASA telles que Mars Reconnaissance Orbiter utilisent des codes turbo comme alternative à la correction d'erreur Reed-Solomon - les codes de décodeur Viterbi .
• IEEE 802.16 ( WiMAX ), une norme de réseau métropolitain sans fil, utilise le codage turbo par bloc et le codage turbo convolutif.

Formulation bayésienne

Du point de vue de l' intelligence artificielle , les turbocodes peuvent être considérés comme une instance de propagation de croyances bouclées dans les réseaux bayésiens .

Voir également

• Code convolutif
• Algorithme de Viterbi
• Décodage à décision douce
• Entrelaceur
• Algorithme BCJR
• Code de contrôle de parité à faible densité
• Codes convolutifs concaténés en série
• Égaliseur turbo
• Correction d'erreur directe

Les références

Lectures complémentaires

Publications

• Battail, Gérard. "Un cadre conceptuel pour comprendre les turbocodes." Journal IEEE sur les zones sélectionnées dans les communications 16.2 (1998): 245-254.
• Brejza, Matthew F., et al. « 20 ans de turbocodage et de directives de conception écoénergétiques pour les applications sans fil à faible consommation d'énergie. » Enquêtes et didacticiels sur les communications IEEE 18.1 (2016) : 8-28.
• Garzón-Bohórquez, Ronald, Charbel Abdel Nour et Catherine Douillard. « Amélioration des codes turbo pour la 5G avec des entrelaceurs à parité contraints par la perforation. » Turbo Codes and Iterative Information Processing (ISTC), 2016 9ème Symposium International sur. IEEE, 2016.

Liens externes

• "Fermer le code parfait" , IEEE Spectrum, mars 2004
• "Le Turbo Code UMTS et une implémentation efficace du décodeur adapté aux radios définies par logiciel" ( International Journal of Wireless Information Networks )
• Dana Mackenzie (2005), "Take it to the limit", New Scientist , 187 (2507): 38-41, ISSN  0262-4079 .( aperçu , copie )
• "Pushing the Limit" , un article de Science News sur le développement et la genèse des turbocodes
• Symposium International sur les Turbo Codes
• Coded Modulation Library , une bibliothèque open source pour simuler des turbo codes dans matlab
• "Turbo Equalization: Principles and New Results" , un article IEEE Transactions on Communications sur l'utilisation de codes convolutifs conjointement avec l'égalisation de canal.
• IT++ Home Page L' IT++ est une puissante librairie C++ qui supporte notamment les turbo codes
• Publications de turbocodes par David MacKay
• Page d'accueil AFF3CT (A Fast Forward Error Correction Toolbox) pour les simulations de turbo codes à grande vitesse dans le logiciel
• Turbo code par Dr Sylvie Kerouédan et Dr Claude Berrou (scholarpedia.org).
• Conception de référence Turbo 3GPP LTE .
• Estimer les performances du Turbo Code BER dans AWGN (MatLab).
• Codage convolutif concaténé parallèle : Turbo Codes (MatLab Simulink)