Worldlex Wiki L'un des principaux avantages des codes convolutifs réside dans leur capacité à effectuer un décodage économique par décision souple au maximum de vraisemblance. Ceci contraste avec les codes en blocs classiques, généralement représentés par un treillis temporel et donc typiquement décodés par décision dure. Les codes convolutifs sont souvent caractérisés par leur débit de base et la profondeur (ou mémoire) de l'encodeur . Le débit de base est généralement donné par , où
Les codes convolutifs sont souvent décrits comme continus. Cependant, on peut également dire qu'ils ont une longueur de bloc arbitraire, plutôt que d'être continus, car la plupart des codages convolutifs en pratique sont effectués sur des blocs de données. Les codes par blocs à codage convolutif utilisent généralement une terminaison. La longueur de bloc arbitraire des codes convolutifs contraste avec celle des codes par blocs classiques , qui ont généralement des longueurs de bloc fixes, déterminées par des propriétés algébriques.
Le débit de codage d'un code convolutif est couramment modifié par perforation de symboles . Par exemple, un code convolutif avec un débit de codage « mère » peut être perforé à un débit supérieur, notamment en ne transmettant pas une partie des symboles de code. Les performances d'un code convolutif perforé sont généralement proportionnelles à la quantité de parité transmise. La possibilité d'effectuer un décodage à décision souple économique sur les codes convolutifs, ainsi que la flexibilité de la longueur des blocs et du débit de codage, expliquent leur grande popularité dans les communications numériques.
Peter Elias . On pensait alors qu'il était possible de les décoder avec une qualité arbitraire, au prix d'une complexité de calcul et d'un délai importants. En 1967, Andrew Viterbi a démontré que les codes convolutifs pouvaient être décodés par maximum de vraisemblance avec une complexité raisonnable grâce à des décodeurs invariants dans le temps basés sur des treillis : l' algorithme de Viterbi . D'autres algorithmes de décodage basés sur des treillis ont été développés ultérieurement, notamment l' algorithme de décodage BCJR .Les codes convolutionnels systématiques récursifs ont été inventés par Claude Berrou vers 1991. Ces codes se sont avérés particulièrement utiles pour le traitement itératif, y compris le traitement de codes concaténés tels que les turbo codes .
En utilisant la terminologie « convolutionnelle », un code convolutionnel classique pourrait être considéré comme un filtre à réponse impulsionnelle finie (FIR), tandis qu'un code convolutionnel récursif pourrait être considéré comme un filtre à réponse impulsionnelle infinie (IIR).
Où les codes convolutifs sont utilisés
Les codes convolutifs sont largement utilisés pour assurer un transfert de données fiable dans de nombreuses applications, telles que la vidéo numérique , la radio, les communications mobiles (par exemple, les réseaux GSM, GPRS, EDGE et 3G (jusqu'à la version 7 du 3GPP) ) et les communications par satellite . Ces codes sont souvent implémentés en concaténation avec un code à décision dure, notamment le code de Reed-Solomon . Avant l' avènement des turbocodes, ces constructions étaient les plus efficaces, se rapprochant le plus de la limite de Shannon .
Encodage convolutif
Pour encoder des données par convolution, on utilise k registres mémoire , chacun contenant un bit d'entrée. Sauf indication contraire, tous les registres mémoire sont initialisés à 0. L'encodeur comporte n additionneurs modulo 2 (un additionneur modulo 2 peut être implémenté avec une simple porte OU exclusif booléenne , dont la logique est : polynômes générateurs , un par additionneur (voir figure ci-dessous). Un bit d'entrée m₁ est injecté dans le registre le plus à gauche. À l'aide des polynômes générateurs et des valeurs présentes dans les autres registres, l'encodeur produit n symboles . Ces symboles peuvent être transmis ou supprimés selon le débit de codage souhaité. On décale ensuite les valeurs de tous les registres vers la droite ( m₁ devient m₀ , m₀ devient m⁻₁ ) et on attend le bit d'entrée suivant. S'il ne reste plus de bits d'entrée, l'encodeur continue le décalage jusqu'à ce que tous les registres soient revenus à l'état zéro (terminaison par vidage du bit).
La figure ci-dessous représente un codeur de taux 1/3 ( m / n ) avec une longueur de contrainte ( k ) de 3. Les polynômes générateurs sont 
Codes récursifs et non récursifs
L'encodeur illustré ci-dessus est un encodeur non récursif . Voici un exemple d'encodeur récursif, qui admet à ce titre une structure de rétroaction :
L'encodeur présenté en exemple est systématique car les données d'entrée sont également utilisées dans les symboles de sortie (Sortie 2). Les codes dont les symboles de sortie n'incluent pas les données d'entrée sont dits non systématiques.
Les codes récursifs sont généralement systématiques, et inversement, les codes non récursifs sont généralement non systématiques. Ce n'est pas une obligation stricte, mais une pratique courante.
L'encodeur présenté en exemple sur l'image 2 est un encodeur à 8 états, car les 3 registres permettent de créer 8 états possibles (2<sup> 3</sup> ). Un décodeur correspondant utilise généralement lui aussi 8 états.
Les codes convolutionnels systématiques récursifs (RSC) sont devenus plus populaires grâce à leur utilisation dans les turbocodes. On les appelle également codes pseudo-systématiques.
Voici d'autres exemples de codes RSC et d'applications :
Utile pour l'implémentation du code LDPC et comme code constitutif interne pour les codes convolutifs concaténés en série (SCCC).
Utile pour les codes SCCC et les turbocodes multidimensionnels.
Utile comme code constitutif dans les turbocodes à faible taux d'erreur pour des applications telles que les liaisons par satellite. Convient également comme code externe SCCC.
Réponse impulsionnelle, fonction de transfert et longueur de contrainte
Un encodeur convolutif est ainsi nommé car il effectue une convolution du flux d'entrée avec les réponses impulsionnelles de l'encodeur :
où
Un codeur convolutif est un système linéaire discret invariant dans le temps . Chaque sortie d'un codeur peut être décrite par sa propre fonction de transfert , étroitement liée au polynôme générateur. Une réponse impulsionnelle est associée à une fonction de transfert par la transformée en Z.
Les fonctions de transfert du premier encodeur (non récursif) sont :
Les fonctions de transfert du deuxième encodeur (récursif) sont :
Définir
Diagramme de treillis
Imaginons que l'encodeur (illustré sur l'image 1 ci-dessus) possède un « 1 » dans sa cellule mémoire de gauche ( m₀ ) et un « 0 » dans celle de droite ( m⁻¹ ). ( m₁ n'est pas une cellule mémoire à proprement parler , car elle représente une valeur actuelle). Nous désignerons cet état par « 10 ». Selon le bit d'entrée , l'encodeur peut, à l'étape suivante, passer soit à l'état « 01 », soit à l'état « 11 ». On constate que toutes les transitions ne sont pas possibles (par exemple, un décodeur ne peut pas passer de l'état « 10 » à l'état « 00 », ni même rester dans l'état « 10 »).
Toutes les transitions possibles peuvent être représentées comme ci-dessous :
Une séquence encodée peut être représentée par un chemin sur ce graphe. Un chemin valide est indiqué en rouge à titre d'exemple.
Ce diagramme illustre le décodage : si une séquence reçue ne correspond pas à ce graphe, c’est qu’elle a été reçue avec des erreurs, et il faut choisir la séquence correcte la plus proche (correspondant au graphe). Les algorithmes de décodage réels exploitent ce principe.
Distance libre et distribution des erreurs
La distance libre ( d ) est la distance de Hamming minimale entre différentes séquences codées. La capacité de correction ( t ) d'un code convolutif correspond au nombre d'erreurs que ce code peut corriger. Elle peut être calculée comme suit :
Puisqu'un code convolutif ne fonctionne pas par blocs, mais traite un flux binaire continu, la valeur de t s'applique à un ensemble d'erreurs relativement proches les unes des autres. Autrement dit, plusieurs groupes de t erreurs peuvent généralement être corrigés lorsqu'ils sont relativement éloignés les uns des autres.
La distance libre peut être interprétée comme la longueur minimale d'une « rafale » erronée à la sortie d'un décodeur convolutif. Il est important de tenir compte du fait que les erreurs se manifestent par des « rafales » lors de la conception d'un code concaténé avec un code convolutif interne. La solution courante à ce problème consiste à entrelacer les données avant le codage convolutif, afin que le bloc externe (généralement de type Reed-Solomon ) puisse corriger la plupart des erreurs.
Décodage des codes convolutifs
Il existe plusieurs algorithmes pour le décodage des codes convolutifs. Pour des valeurs de k relativement faibles , l' algorithme de Viterbi est universellement utilisé car il offre des performances optimales et est hautement parallélisable. Les décodeurs de Viterbi sont ainsi faciles à implémenter sur du matériel VLSI et sur des processeurs dotés d' un jeu d'instructions SIMD .
Les codes à contrainte longue sont plus facilement décodés par divers algorithmes de décodage séquentiel , dont l' algorithme de Fano est le plus connu. Contrairement au décodage de Viterbi, le décodage séquentiel n'est pas basé sur le maximum de vraisemblance, mais sa complexité n'augmente que légèrement avec la longueur de la contrainte, permettant ainsi l'utilisation de codes robustes à contrainte longue. Ces codes ont été utilisés dans le cadre du programme Pioneer au début des années 1970 pour l'exploration de Jupiter et de Saturne, avant d'être remplacés par des codes plus courts, décodés par l'algorithme de Viterbi, généralement concaténés avec de grands codes correcteurs d'erreurs Reed-Solomon. Ces derniers accentuent la pente de la courbe du taux d'erreur binaire global et produisent des taux d'erreur résiduelle non détectée extrêmement faibles.
Les algorithmes de décodage de Viterbi et séquentiel fournissent des décisions binaires : les bits qui forment le mot de code le plus probable. L’ algorithme de Viterbi à sortie souple permet d’ajouter une mesure de confiance approximative à chaque bit . L’ algorithme BCJR permet d’obtenir des décisions binaires de maximum a posteriori (MAP) pour chaque bit .
Codes convolutifs populaires
En effet, les structures de codes convolutifs prédéfinies, obtenues lors de recherches scientifiques, sont utilisées dans l'industrie. Ceci est lié à la possibilité de sélectionner des codes convolutifs catastrophiques (entraînant un nombre d'erreurs plus élevé).
Un code convolutif décodé Viterbi particulièrement populaire, utilisé au moins depuis le programme Voyager , a une longueur de contrainte Mars Pathfinder , Mars Exploration Rover et la sonde Cassini vers Saturne utilisent un
Le code convolutif avec une longueur de contrainte de 2 et un taux de 1/2 est utilisé dans le GSM comme technique de correction d'erreurs.
Codes convolutifs perforés
Il est possible de concevoir un code convolutif de n'importe quel taux de codage par sélection polynomiale ; cependant, en pratique, une procédure de perforation est souvent utilisée pour atteindre le taux de codage souhaité. La perforation est une technique permettant de générer un code de taux m / n à partir d'un code de base à faible taux (par exemple, 1/ n ). Elle consiste à supprimer certains bits à la sortie de l'encodeur. Les bits supprimés sont définis selon une matrice de perforation . Les matrices de perforation suivantes sont les plus fréquemment utilisées :
| Taux de code | Matrice de perforation | Distance libre (pour le code convolutif standard K=7 de la NASA) | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1/2 (Sans perforation) |
| 10 | ||||||||||||||
| 2/3 |
| 6 | ||||||||||||||
| 3/4 |
| 5 | ||||||||||||||
| 5/6 |
| 4 | ||||||||||||||
| 7/8 |
| 3 |
Par exemple, pour créer un code de taux 2/3 à l'aide de la matrice appropriée du tableau ci-dessus, il faut prendre la sortie d'un encodeur de base et transmettre le premier bit de chaque branche, puis chaque bit de chaque branche. L'ordre de transmission précis est défini par la norme de communication applicable.
Les codes convolutifs perforés sont largement utilisés dans les communications par satellite , par exemple dans les systèmes Intelsat et la diffusion vidéo numérique .
Les codes convolutifs perforés sont également appelés « codes perforés ».
Turbo codes : remplacement des codes convolutifs
Les codes convolutifs simples décodés par l'algorithme de Viterbi cèdent désormais la place aux turbocodes , une nouvelle classe de codes convolutifs courts itérés qui approchent les limites théoriques imposées par le théorème de Shannon, avec une complexité de décodage bien moindre que celle de l'algorithme de Viterbi appliqué aux longs codes convolutifs pour des performances équivalentes. La concaténation avec un code algébrique externe (par exemple, Reed-Solomon ) résout le problème des seuils d'erreur inhérents à la conception des turbocodes.