Code convolutif

En télécommunications , un code convolutif est un type de code correcteur d'erreurs qui génère des symboles de parité par application glissante d'une fonction polynomiale booléenne à un flux de données. Cette application glissante correspond à la « convolution » de l'encodeur sur les données, d'où le terme « codage convolutif ». La nature glissante des codes convolutifs facilite le décodage par treillis à l'aide d'un treillis invariant dans le temps. Ce type de décodage permet un décodage par décision souple au maximum de vraisemblance des codes convolutifs avec une complexité raisonnable.

L'un des principaux avantages des codes convolutifs réside dans leur capacité à effectuer un décodage économique par décision souple à 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. ${\displaystyle [n,k,K] <semantics><mrow><mstyle><mo>[</mo><mi>n</mi><mo>,</mo><mi>k</mi><mo>,</mo><mi>K</mi><mo>]</mo></mstyle></mrow><annotation>{\displaystyle [n,k,K]}</annotation></semantics></math><img src=$ ${\displaystyle k/n <semantics><mrow><mstyle><mi>k</mi><mrow><mo>/</mo></mrow><mi>n</mi></mstyle></mrow><annotation>{\displaystyle k/n}</annotation></semantics></math><img src=$ ${\displaystyle K-1 </span referrerpolicy=$ entrées. La profondeur peut également être donnée comme le nombre d'éléments de mémoire ${\displaystyle 2^{v </span referrerpolicy=$ ).

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 taux de codage d'un code convolutif est généralement modifié par perforation de symboles . Par exemple, un code convolutif avec un taux de codage « mère » ${\displaystyle n/k=1/2 <semantics><mrow><mstyle><mi>n</mi><mrow><mo>/</mo></mrow><mi>k</mi><mo>=</mo><mn>1</mn><mrow><mo>/</mo></mrow><mn>2</mn></mstyle></mrow><annotation>{\displaystyle n/k=1/2}</annotation></semantics></math><img src=$ ${\displaystyle 7/8 <semantics><mrow><mstyle><mn>7</mn><mrow><mo>/</mo></mrow><mn>8</mn></mstyle></mrow><annotation>{\displaystyle 7/8}</annotation></semantics></math><img src=$

Histoire

Les codes convolutifs ont été introduits en 1955 par 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 XOR booléenne , dont la logique est : , ) et n 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).

Image 1. Encodeur convolutif non récursif et non systématique de taux 1/3 avec une longueur de contrainte de 3

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 1,1,1 et Par conséquent, les bits de sortie sont calculés (modulo 2) comme suit :

n ₁ = m ₁ + m ₀ + m ₋₁

n ₂ = m ₀ + m ₋₁

n ₃ = m ₁ + m ₋₁ .

Les codes convolutifs peuvent être systématiques et non systématiques :

répète systématiquement la structure du message avant l'encodage
modifications non systématiques de la structure initiale

Les codes convolutionnels non systématiques sont plus répandus en raison de leur meilleure immunité au bruit. Cela est lié à la distance libre du code convolutionnel.

Une brève illustration du code convolutif non systématique.

Une brève illustration du code convolutif systématique.

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 ^3 ). 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).

Img. 4. Code convolutionnel systématique récursif à quatre états (RSC).

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 :

{\displaystyle y_{i}^{j}=\sum _{k=0}^{\infty }h_{k}^{j}x_{i-k}=(x*h^{j})[i], <semantics><mrow><mstyle><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mrow><mi>j</mi></mrow></msubsup><mo>=</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msubsup><mi>h</mi><mrow><mi>k</mi></mrow><mrow><mi>j</mi></mrow></msubsup><msub><mi>x</mi><mrow><mi>je</mi><mo>−</mo><mi>k</mi></mrow></msub><mo>=</mo><mo>(</mo><mi>x</mi><mo>∗</mo><msup><mi>h</mi><mrow><mi>j</mi></mrow></msup><mo>)</mo><mo>[</mo><mi>je</mi><mo>]</mo><mo>,</mo></mstyle></mrow><annotation>{\displaystyle y_{i}^{j}=\sum _{k=0}^{\infty }h_{k}^{j}x_{ik}=(x*h^{j})[i],}</annotation></semantics></math></span><img src=

où est une séquence de sortie est une réponse impulsionnelle pour la sortie ${\displaystyle {* </span referrerpolicy=$ désigne la convolution.

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 :

${\displaystyle H_{1}(z)=1+z^{-1}+z^{-2},\, <semantics><mrow><mstyle><msub><mi>H</mi><mrow><mn>1</mn></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mn>1</mn><mo>+</mo><msup><mi>z</mi><mrow><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo><msup><mi>z</mi><mrow><mo>−</mo><mn>2</mn></mrow></msup><mo>,</mo><mspace></mspace></mstyle></mrow><annotation>{ displaystyle H_ {1} (z) = 1 + z ^ {-1} + z ^ {-2}, \,}</annotation></semantics></math><img src=$
${\displaystyle H_{2}(z)=z^{-1}+z^{-2},\, <semantics><mrow><mstyle><msub><mi>H</mi><mrow><mn>2</mn></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><msup><mi>z</mi><mrow><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo><msup><mi>z</mi><mrow><mo>−</mo><mn>2</mn></mrow></msup><mo>,</mo><mspace></mspace></mstyle></mrow><annotation>{ displaystyle H_ {2} (z) = z ^ {-1} + z ^ {-2}, \,}</annotation></semantics></math><img src=$
${\displaystyle H_{3}(z)=1+z^{-2}.\, <semantics><mrow><mstyle><msub><mi>H</mi><mrow><mn>3</mn></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mn>1</mn><mo>+</mo><msup><mi>z</mi><mrow><mo>−</mo><mn>2</mn></mrow></msup><mo>.</mo><mspace></mspace></mstyle></mrow><annotation>{\displaystyle H_{3}(z)=1+z^{-2}.\,}</annotation></semantics></math><img src=$

Les fonctions de transfert du deuxième encodeur (récursif) sont :

${\displaystyle H_{1}(z)={\frac {1+z^{-1}+z^{-3}}{1-z^{-2}-z^{-3}}},\, <semantics><mrow><mstyle><msub><mi>H</mi><mrow><mn>1</mn></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mrow><mfrac><mrow><mn>1</mn><mo>+</mo><msup><mi>z</mi><mrow><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo><msup><mi>z</mi><mrow><mo>−</mo><mn>3</mn></mrow></msup></mrow><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mo>−</mo><mn>2</mn></mrow></msup><mo>−</mo><msup><mi>z</mi><mrow><mo>−</mo><mn>3</mn></mrow></msup></mrow></mfrac></mrow><mo>,</mo><mspace></mspace></mstyle></mrow><annotation>{\displaystyle H_{1}(z)={\frac {1+z^{-1}+z^{-3}}{1-z^{-2}-z^{-3}}},\,}</annotation></semantics></math><img src=$
${\displaystyle H_{2}(z)=1.\, <semantics><mrow><mstyle><msub><mi>H</mi><mrow><mn>2</mn></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mn>1.</mn><mspace></mspace></mstyle></mrow><annotation>{\displaystyle H_{2}(z)=1.\,}</annotation></semantics></math><img src=$

Définir ${\displaystyle m=\max _{i}\operatorname {polydeg} (H_{i}(1/z))\, </span referrerpolicy=$

où, pour toute fonction rationnelle ${\displaystyle f(z)=P(z)/Q(z)\, <semantics><mrow><mstyle><mi>f</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mi>P</mi><mo>(</mo><mi>z</mi><mo>)</mo><mrow><mo>/</mo></mrow><mi>Q</mi><mo>(</mo><mi>z</mi><mo>)</mo><mspace></mspace></mstyle></mrow><annotation>{\style d'affichage f(z)=P(z)/Q(z)\,}</annotation></semantics></math><img src=$

{\displaystyle \operatorname {polydeg} (f)=\max(\deg(P),\deg(Q))\, <semantics><mrow><mstyle><mi>polydeg</mi><mo>⁡</mo><mo>(</mo><mi>f</mi><mo>)</mo><mo>=</mo><mo>max</mo><mo>(</mo><mi>deg</mi><mo>⁡</mo><mo>(</mo><mi>P</mi><mo>)</mo><mo>,</mo><mi>deg</mi><mo>⁡</mo><mo>(</mo><mi>Q</mi><mo>)</mo><mo>)</mo><mspace></mspace></mstyle></mrow><annotation>{\displaystyle \operatorname {polydeg} (f)=\max(\deg(P),\deg(Q))\,}</annotation></semantics></math></span><img src=

Alors ${\displaystyle H_{i}(1/z)\, <mrow><mstyle><mi>K</mi><mo>=</mo><mi>m</mi><mo>+</mo><mn>1</mn><mspace></mspace></mstyle></mrow><annotation>{\displaystyle K=m+1\,}</annotation></semantics></math><img src=$

Diagramme de treillis

{\displaystyle t=\left\lfloor {\frac {d-1}{2}} ight floor . </span referrerpolicy=

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

{ displaystyle h ^ {1} = 171_ {o} = [1111001] _ {b </span referrerpolicy=

{\displaystyle h^{2}=133_{o}=[1011011]_{b <semantics><mrow><mstyle><msup><mi>h</mi><mrow><mn>2</mn></mrow></msup><mo>=</mo><msub><mn>133</mn><mrow><mi>o</mi></mrow></msub><mo>=</mo><mo>[</mo><mn>1011011</mn><msub><mo>]</mo><mrow><mi>b</mi></mrow></msub></mstyle></mrow><annotation>{ displaystyle h ^ {2} = 133_ {o} = [1011011] _ {b}}</annotation></semantics></math></span><img src=

Courbes théoriques du taux d'erreur binaire d'un canal à bruit blanc gaussien additif codé en QPSK (décision souple). Des contraintes plus longues permettent d'obtenir des codes plus performants, mais la complexité de l'algorithme de Viterbi augmente exponentiellement avec ces contraintes, limitant ainsi l'utilisation de ces codes plus performants aux missions spatiales lointaines où le gain de performance justifie largement la complexité accrue du décodeur.

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 de 15 et un taux de 1/6 ; ce code offre des performances supérieures d'environ 2 dB au code plus simple. ${\displaystyle K=7 <semantics><mrow><mstyle><mi>K</mi><mo>=</mo><mn>7</mn></mstyle></mrow><annotation>{\displaystyle K=7}</annotation></semantics></math><img src=$

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

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.