État de l’art sur les turbo décodeurs à haut débit

État de l’art sur les turbo décodeurs à haut débit

Rôle des codes correcteurs d’erreurs en communication numérique

Une chaîne de communication permet de transmettre une quantité d’information donnée avec le moins d’erreurs possible. Les données peuvent être numériques – un fichier texte ou une image, ou analogiques – une source sonore. Cependant, grâce à des flexibilités et des puissances de traitement dans le temps discret, les systèmes de communication modernes sont la plupart numériques. C’est pourquoi, lorsque les données sont analogiques, elles doivent être numérisées avant d’être transmises de l’émetteur au récepteur.

La chaîne de transmission  est constituée d’un milieu de transmission – appelé canal, d’un couple codeur-décodeur de source, d’un couple modulateur démodulateur ainsi que d’un couple codeur-décodeur de canal. La donnée d’information de la source est représentée par une séquence numérique qui est à l’entrée du codeur de source. Durant cette étape, la séquence numérique x sera compressée au maximum. Ensuite, le codeur de canal ajoute à la séquence compressée de la redondance produite par certaines lois qui permettent au récepteur de vérifier les erreurs et de les corriger. La séquence de sortie du codeur de canal est notée c avec une longueur n. Elle est envoyée au modulateur, qui transforme la séquence numérique c en signaux continus w compatibles avec le milieu de transmission. L’émetteur envoie une donnée au récepteur à travers un milieu de transmission, où la donnée peut être déformée ou interférée. Le canal est dépendant du milieu physique par lequel transitent les informations et dans lequel w est bruité. Dans les communications mobiles, plusieurs types de canaux de transmission peuvent être utilisés pour les échanges d’information entre l’émetteur et le récepteur. Les techniques de modulation, non détaillés ici, varient de simples techniques – utilisant des symboles complexes discrets – aux techniques plus avancées – Orthogonal Frequency Division Multiplexing (OFDM) ou multiantennes (MIMO).

Le signal analogique w produit par le modulateur est altéré en un autre signal analogique wˆ qui est le point d’entrée du démodulateur, le premier bloc du récepteur. Le modulateur qui réalise l’opération inverse du modulateur convertit le signal analogique wˆ en signal numérique en bande de base cˆ équivalent. Ce signal est l’estimation du signal c et est fourni au décodeur de canal. Le décodeur de canal s’appuie sur la connaissance de l’ensemble des mots de codes pour choisir, à partir d’un mot reçu, le plus vraisemblable. Le résultat du décodage du canal est noté bd, et est utilisé par le décodeur de source pour produire l’estimation du signal numérique émis bx. Le bruit modifie le signal émis jusqu’à un niveau tel qu’à la réception, le signal reçu est alors différent du signal émis. Lorsque l’estimation bd est différente du signal émis d, alors, l’estimation bx et le signal numérique x ne sont pas identiques. Dans ce cas, une erreur de transmission est rencontrée s’il n’y a pas de moyen de protection des données. Une solution est d’introduire un mécanisme de codage/décodage approprié. L’émetteur ajoute au signal numérique émis de la redondance qui est utilisée par le récepteur afin de détecter les erreurs voire les corriger. A travers l’histoire des communications numériques, parmi les solutions proposées pour la protection des données, les turbocodes sont reconnus comme révolutionnaires au niveau des performances de correction d’erreurs et au principe de décodage itératif. Dans la section suivante, leurs principes fondamentaux sont rappelés.

Principes généraux des turbocodes 

En 1948, Shannon a introduit le théorème célèbre : Si le débit de l’information à l’entrée du canal est inférieur à la capacité du canal, alors il est possible de transmettre le contenu de l’information sur le canal avec une probabilité d’erreur aussi petite que souhaitée. Ce théorème est d’une importance fondamentale dans le monde des communications numériques. Il donne une limite supérieure que l’on peut atteindre en termes de taux de transmission des données fiables pour un canal de transmission. Cependant, pour prouver ce théorème, Shannon a utilisé un code aléatoire de longueur infinie. En pratique, ce code n’existe pas. Depuis, les chercheurs s’efforcent de construire des codes correcteurs d’erreurs de longueurs finies s’approchant du code aléatoire, pour être capable d’atteindre au maximum la limite du théorème de Shannon.

Ainsi, la communauté scientifique a attendu presqu’un demi-siècle pour véritablement s’approcher de la limite de Shannon. En 1992, C. Berrou et A. Glavieux, membre de l’ENST Bretagne, ont inventé les turbocodes qui ont été présentés à la communauté scientifique en 1993 [1]. Ils attirent l’attention grâce à leur principe de décodage qui permet d’obtenir de bonnes performances de correction d’erreurs proches de la limite de Shannon. De plus la complexité de mise en œuvre est acceptable pour une implémentation matérielle. La construction des turbocodes se base sur la théorie de concaténation. Le premier turbocode est construit par une concaténation en parallèle de deux codes élémentaires séparés par un entrelaceur. Son principe de décodage se base sur un algorithme, itératif, où deux unités échangent des informations au cours de chaque itération afin d’améliorer la capacité de correction d’erreurs de chaque unité. Après plusieurs itérations, les deux unités convergent vers un même mot de code, qui est identique au mot de code transmis. Le principe itératif a stimulé la communauté scientifique pour étendre le principe itératif. Il a donc été adopté dans d’autres parties du système de transmission : égalisation [18], détection [19],… Dans la suite, nous allons revoir ensemble brièvement les briques des turbocodes : la concaténation des codes et aussi l’entrelacement.

Théorie de la concaténation

En 1957, Shannon a énoncé un principe fondamental : la probabilité d’erreur du décodage peut être réalisée afin de diminuer exponentiellement en fonction de la longueur de paquet des données qui tend vers l’infini [20]. Ainsi, plus longue est la séquence de donnée, plus exponentiellement faible est la probabilité d’erreur. La probabilité d’erreur devient la meilleure quand la longueur de la séquence tend vers l’infini. Néanmoins, le théorème de codage démontre que la complexité du schéma de décodage optimal qui simplifie les calculs des vraisemblances sur tous les mots codés transmis croît aussi exponentiellement. Il nécessite aussi une mémoire exponentiellement large suivant la taille de la séquence d’information. C’est pourquoi, l’implémentation d’un tel décodeur optimal est impossible [21]. En 1966, Forney a proposé pendant son travail de thèse un type de code [22], appelé les codes enchaînés comme une approche aboutissant à un fort gain de codage, pour une complexité raisonnable, en combinant deux codes simples voire plus. Ce type de code permet d’obtenir une probabilité d’erreur qui décroît exponentiellement et qui est proche de la limite de Shannon. Mais la complexité de décodage augmente tout de même polynomialement avec la longueur de la trame. Le schéma original de concaténation des codes proposé par Forney est illustré en figure 1.2(a). Ce type de code se compose d’un codeur, dit codeur extérieur, connecté à un autre codeur, noté codeur intérieur. Il s’agit d’un code concaténé en série. Quelques années après, une concaténation classique et efficace proposée par Odenwalder [23], utilise pour code intérieur un code convolutif binaire, et pour code extérieur un code en bloc linéaire de type Reed-Solomon (RS). La NASA a ensuite standardisé la concaténation série des codes en ajoutant un entrelaceur entre les deux codes élémentaires (figure 1.2(b)) qui permet d’augmenter significativement la robustesse des codes concaténés. Dès lors, la concaténation en série des codes correcteurs d’erreurs a été largement utilisée dans tous les types de communications numériques.

Entrelacement 

Le rôle de la fonction d’entrelacement est particulièrement important. C’est une des caractéristiques principales du turbo codage [32] qui affecte significativement les performances. La performance d’un turbocode est essentiellement amélioré quand la longueur d’entrelaceur augmente [33]. Au niveau du codage, en 1996, Benedetto [32] et Perez [34] ont prouvé que la performance asymptotique dépendait de la distribution des mots codés de poids faible. Par conséquent, la fonction d’entrelacement permet d’éviter que les deux codeurs composants donnent un mot codé de poids faible, et ainsi augmente la distance minimale de Hamming. Si une séquence d’information qui génère un mot codé de poids faible à l’entrée d’un codeur élémentaire est entrelacée selon certaines critères, le processus aboutit à un mot codé de grand poids sous l’autre codeur élémentaire. Au niveau du décodage, l’entrelaceur assure à la sortie de chaque décodeur élémentaire, une dispersion temporelle des erreurs groupées dans des paquets de données. Aussi, elles deviennent des erreurs isolées pour l’autre décodeur qui suit. En augmentant le nombre d’échange des informations du processus de décodage, la probabilité d’erreur des bits s’approche de la limite théorique. La propriété de corrélation du codage concaténé influence le turbo décodage, notamment au niveau de la zone de convergence où le taux d’erreurs binaires chute dès les premières itérations. La construction d’un bon entrelaceur doit tenir compte des motifs des schémas des codes élémentaires ainsi que des motifs d’erreur du canal de propagation. La conception d’entrelaceurs a été abondamment étudiée dans la littérature. Parmi les classes d’entrelaceurs, on peut citer les entrelaceurs simples et performants tels que  Almost Regular Permutation – ARP [35] et Dithered  Relatively Prime – DRP [36] qui ont inspiré les standards DVB-RCS, DVB-RCT et WiMAX (IEEE 802.16). Plus récemment l’entrelaceur Quadratic Permutation Polynomial – QPP a été sélectionné pour la norme 3GPP-LTE [25].

Turbocodes convolutifs retenus pour les standards

Parmi différents codes élémentaires proposés dans la littérature, les codes convolutifs sont largement utilisés dans les schémas des turbocodes grâce à leur grande capacité de correction d’erreur et à leur faible coût du schéma de codage et de décodage. De différentes architectures des turbocodes convolutifs sont largement déployées dans les standards modernes : 3GPP-LTE [25], DVB-RCT [26], DVB-RCS [27]. Dans un premier temps, cette section décrit brièvement le principe de turbo codage et turbo décodage convolutifs. Les principes basiques des codes convolutifs et une classe importante des codes convolutifs – classe des codes convolutifs récursifs systématiques circulaires – sont ensuite rappelés. Le principe de l’algorithme de décodage optimal – algorithme MAP – est introduit à la fin de cette section.

Table des matières

Introduction
1 Vers les turbo-décodeurs à haut débit
1.1 Introduction
1.2 État de l’art sur les turbo décodeurs à haut débit
1.2.1 Rôle des codes correcteurs d’erreurs en communication numérique
1.2.2 Principes généraux des turbocodes
1.2.3 Turbocodes convolutifs retenus pour les standards
1.2.4 La montée en débit, un défi
1.3 Principe du traitement stochastique pour le décodage de codes LDPC
1.3.1 Principe du calcul stochastique
1.3.2 Décodage stochastique de codes LDPC
1.4 Décodage stochastique des turbocodes
1.4.1 Principe du décodage stochastique des turbocodes
1.4.2 Estimation de la complexité de décodage stochastique pour l’algorithme MAP
1.4.3 Caractéristique des opérations pour le décodage stochastique de turbocodes
1.5 Conclusion
2 Décodage stochastique de turbocodes basé sur l’algorithme MAP
2.1 Introduction
2.2 Architecture du turbo-décodeur convolutif stochastique
2.2.1 Modèle d’un turbo-décodeur stochastique
2.2.2 Architecture d’un décodeur stochastique élémentaire SISO
2.2.3 Interprétation des probabilités issues du canal
2.2.4 Mise à l’échelle des sorties du canal démodulées
2.3 Module Γ
2.3.1 Rôle du module
2.3.2 Architecture du module Γ
2.4 Modules A/B
2.4.1 Rôle des modules
2.4.2 Calcul de nouvelles métriques d’état
2.4.3 Normalisation des métriques récurrentes
2.5 Module Ext
2.5.1 Rôle du module
2.5.2 Architecture du module Ext
2.6 Module DEC
2.6.1 Rôle du module
2.6.2 Solution alternative d’implémentation du module DEC
2.6.3 Diagramme de bloc du module DEC
2.7 Performance de correction d’erreurs de décodeurs stochastiques
2.7.1 Performance du décodage convolutif stochastique
2.7.2 Performance du turbo-décodeur convolutif stochastique
2.7.3 Complexité matérielle d’un décodeur stochastique SISO
2.7.4 Estimation du débit d’un turbo-décodeur stochastique
2.8 Conclusion
3 Conception de turbo-décodeurs stochastiques à haut débit
3.1 Introduction
3.2 Décodage stochastique dans le domaine exponentiel
3.2.1 Conversion en domaine exponentiel
3.2.2 Transformation exponentielle
3.2.3 Transformation logarithmique
3.2.4 Quel ordre pour les transformations exponentielle et logarithmique ?
3.3 Conception des modules d’un turbo-décodeur stochastique intégrant des traitements dans le domaine exponentiel
3.3.1 Module A/B
3.3.2 Module Ext
3.3.3 Module DEC
3.4 Performance de correction d’erreurs de décodeurs stochastiques exponentiels
3.4.1 Performance du décodage convolutif stochastique exponentiel APP
3.4.2 Performance de turbo décodage stochastique exponentiel
3.5 Complexité matérielle d’un décodeur stochastique exponentiel APP
3.6 Estimation du débit d’un turbo-décodeur stochastique exponentiel
3.7 Décodage stochastique en parallèle ou multi-flux
3.7.1 Coût des techniques de mémoires en termes d’efficacité architecturale
3.7.2 Architecture multi-flux
3.8 Architecture des modules d’un turbo-décodeur stochastique multi-flux
3.8.1 Modèle d’un turbo-décodeur stochastique multi-flux
3.8.2 Module Γ
3.8.3 Modules A/B
3.8.4 Module Ext
3.8.5 Module DEC
3.9 Performance de décodeurs stochastiques multi-flux
3.9.1 Performances d’un décodeur convolutif stochastique multi-flux APP
3.9.2 Performance de turbo-décodeurs stochastiques multi-flux
3.9.3 Estimation de la complexité d’un décodeur stochastique multi-flux APP
3.9.4 Estimation du débit d’un turbo-décodeur stochastique multi-flux
3.10 Contribution des deux propositions pour la conception d’un turbo-décodeur à haut débit
3.10.1 Performance d’un décodeur convolutif stochastique exponentiel multiflux APP
3.10.2 Performance d’un turbo-décodeur stochastique exponentiel multi-flux
3.10.3 Complexité d’un décodeur stochastique exponentiel multi-flux
3.10.4 Estimation du débit d’un turbo-décodeur stochastique exponentiel multiflux
3.11 Conclusion
4 Prototypage d’un turbo-décodeur stochastique
4.1 Introduction
4.2 Métriques associées à l’environnement de prototypage
4.2.1 Objectif du prototypage
4.2.2 Plate-forme
4.3 Description de la chaîne de transmission numérique
4.3.1 Générateur des données binaires
4.3.2 Architecture de l’émetteur
4.4 L’émulateur de canal de transmission
4.5 Décodeur stochastique pour turbocodes et codes convolutifs
4.5.1 Architecture globale du turbo-décodeur stochastique
4.5.2 Contrôleur de la partie réception
4.5.3 Générateurs de séquences aléatoires – RNG
4.5.4 Synthèse logique sur circuit FPGA
4.6 Architecture globale de la chaîne de transmission
4.6.1 Architecture globale
4.6.2 Synthèse logique sur circuit FPGA
4.6.3 Performance du prototypage
4.6.4 Débit
4.7 Conclusion
Conclusion

Télécharger le rapport complet