Code de correction d'erreur concaténé

théorie du codage , les codes concaténés constituent une classe de codes correcteurs d'erreurs obtenus par la combinaison d'un code interne et d'un code externe . Ils ont été conçus en 1966 par Dave Forney pour résoudre le problème de la recherche d'un code présentant à la fois une probabilité d'erreur décroissante exponentiellement avec la longueur des blocs et une complexité de décodage polynomiale . Les codes concaténés se sont largement répandus dans les communications spatiales dans les années 1970.

Le théorème de codage de canal de Shannon démontre que, sur de nombreux canaux courants, il existe des schémas de codage capables de transmettre des données de manière fiable à tous les débits inférieurs à un certain seuil , appelé capacité du canal. En effet, la probabilité d'erreur de décodage peut être rendue exponentiellement décroissante lorsque la longueur des blocs du schéma de codage tend vers l'infini. Cependant, la complexité d'un schéma de décodage optimal naïf, qui calcule simplement la vraisemblance de chaque mot de code transmis possible, croît exponentiellement avec la longueur des blocs , rendant ainsi un tel décodeur optimal rapidement irréalisable.

Dans sa thèse de doctorat , Dave Forney a démontré que les codes concaténés pouvaient être utilisés pour obtenir des probabilités d'erreur décroissantes de manière exponentielle à tous les débits de données inférieurs à la capacité, avec une complexité de décodage qui n'augmente que polynomialement avec la longueur du bloc de code.

Soit C un code [ n , k , d ], c'est-à-dire un _code par blocs de longueur n , de dimension k , de distance de Hamming minimale d , et de taux r = k / n , sur un alphabet A :

Soit C _out un code [ N , K , D ] sur un alphabet B avec | B | = | A | ^k symboles :

Le code interne C _{_in} prend une entrée parmi | A | ^_k = | B | possibles, l'encode en un n -uplet sur A , la transmet et la décode en une sortie parmi | B | possibles. On considère cela comme un (super) canal capable de transmettre un symbole de l'alphabet B. On utilise ce canal N fois pour transmettre chacun des N symboles d'un mot de code C _{_out} . La concaténation de C _{_out} (code externe) avec C _{_in} (code interne), notée C_{_out} C_{_in} , est donc un code de longueur N_n sur l'alphabet A :

Il mappe chaque message d'entrée m = ( m ₁ , m ₂ , ..., m _K ) à un mot de code ( C _in ( m ' ₁ ), C _in ( m ' ₂ ), ..., C _in ( m ' _N )), où ( m ' ₁ , m ' ₂ , ..., m ' _N ) = C _out ( m ₁ , m ₂ , ..., m _K ).

L' idée clé de cette approche est que si C in est décodé par une méthode du maximum de vraisemblance (présentant ainsi une probabilité d'erreur décroissante exponentiellement avec la longueur), et que C out est un code de longueur N = 2 nr  décodable en temps polynomial de N , alors le code concaténé peut être décodé en temps polynomial de sa longueur combinée n 2  = O ( N ⋅ log( N )) et présente une probabilité d'erreur décroissante exponentiellement, même si C in  a une complexité de décodage exponentielle. Ce point est abordé plus en détail dans la section Décodage des codes concaténés .

Dans une généralisation de la concaténation ci-dessus, il existe N codes internes possibles C_{_{in , i}} et le i -ème symbole d'un mot de code C _{_out} est transmis sur le canal interne en utilisant le i -ème code interne. Les codes de Justesen sont des exemples de codes concaténés généralisés, où le code externe est un code de Reed-Solomon .

1. La distance du code concaténé C _out C _in est au moins dD , c'est-à-dire qu'il s'agit d'un code [ nN , kK , D ' ] avec D ' ≥ dD .

Démonstration : Considérons deux messages différents m₁ ≠ ^m₂ ∈ BK . Soit Δ la distance entre les deux mots de ^code . ^Alors

Il existe donc au moins D positions où la séquence des N symboles des mots de code C _{_out} ( m ^₁ ) et C _{_out} ( m ^₂ ) diffère. Pour ces positions, notées i , nous avons

Par conséquent, il existe au moins d ⋅ D positions dans la séquence de n ⋅ N symboles tirés de l'alphabet A où les deux mots de code diffèrent, et donc

2. Si C _out et C _in sont des codes de bloc linéaires , alors C _out C _in est également un code de bloc linéaire.

Cette propriété peut être facilement démontrée en se basant sur l'idée de définir une matrice génératrice pour le code concaténé en fonction des matrices génératrices de C _out et C _in .

Une approche naturelle pour un algorithme de décodage de codes concaténés consiste à décoder d'abord le code interne, puis le code externe. Pour être pratique, cet algorithme doit avoir une complexité polynomiale par rapport à la longueur du bloc final. Supposons qu'il existe un algorithme de décodage unique en temps polynomial pour le code externe. Il nous faut maintenant trouver un algorithme de décodage en temps polynomial pour le code interne. On entend ici par complexité polynomiale que le temps d'exécution est polynomial par rapport à la longueur du bloc final. L'idée principale est que si la longueur du bloc interne est logarithmique par rapport à la taille du code externe, alors l'algorithme de décodage du code interne peut s'exécuter en temps exponentiel par rapport à la longueur du bloc interne. On peut ainsi utiliser un décodeur à maximum de vraisemblance (MLD) optimal en temps exponentiel pour le code interne.

Plus précisément, soit l'entrée du décodeur le vecteur y = ( y ₁ , ..., y _N ) ∈ ( A ⁿ ) ^N . L'algorithme de décodage se déroule alors en deux étapes :

1. Utilisez le MLD du code interne C _in pour reconstruire un ensemble de mots de code internes y ' = ( y ' ₁ , ..., y ' _N ), avec y ' _i = MLD _{C in} ( y _i ), 1 ≤ i ≤ N .
2. Exécutez l'algorithme de décodage unique pour C _sur y ' .

La complexité temporelle de la première étape est O ( N ⋅ exp( n )), où n = O (log( N )) est la longueur du bloc interne. Autrement dit, elle est de l' ordre de N O (1) (c'est-à-dire polynomiale) par rapport à la longueur du bloc externe N. Comme l'algorithme de décodage externe de la deuxième étape est supposé s'exécuter en temps polynomial, la complexité de l'algorithme de décodage global est également polynomiale.

Bien qu'un schéma de concaténation simple ait déjà été mis en œuvre pour la mission Mariner de 1971 vers Mars les codes concaténés ont commencé à être régulièrement utilisés pour les communications spatiales lointaines avec le programme Voyager , qui a lancé deux sondes spatiales en 1977 Depuis lors, les codes concaténés sont devenus la méthode de codage correcteur d'erreurs efficace par excellence, et le sont restés au moins jusqu'à l'invention des turbocodes et des codes LDPC .

En général, le code interne n'est pas un code par blocs, mais un code convolutif à décision souple , décodé par Viterbi, avec une longueur de contrainte courte. Pour le code externe, on utilise un code par blocs à décision dure plus long, souvent un code de Reed-Solomon avec des symboles de huit bits. La taille de symbole plus importante rend le code externe plus robuste aux pics d'erreurs pouvant survenir en raison des imperfections du canal, et également parce que la sortie erronée du code convolutif lui-même est irrégulière. Une couche d'entrelacement est généralement ajoutée entre les deux codes afin de répartir les pics d'erreurs sur une plage plus large.

La combinaison d'un code convolutif de Viterbi interne avec un code de Reed-Solomon externe (connue sous le nom de code RSV) a été utilisée pour la première fois dans Voyager 2 [ est devenue une construction populaire tant dans le secteur spatial qu'en dehors. Elle est encore utilisée aujourd'hui notamment pour les communications par satellite , comme la norme de diffusion de télévision numérique DVB-S .

Au sens large, toute combinaison (sérieuse) de deux codes ou plus peut être qualifiée de code concaténé. Par exemple, dans la norme DVB-S2 , un code LDPC très efficace est combiné à un code externe algébrique afin d'éliminer les erreurs résiduelles du code LDPC interne dues à son plancher d'erreur inhérent .

Un schéma de concaténation simple est également utilisé sur le disque compact (CD), où une couche d'entrelacement entre deux codes Reed-Solomon de tailles différentes répartit les erreurs sur différents blocs.

La description ci-dessus concerne ce que l'on appelle aujourd'hui un code à concaténation sérielle. Les turbocodes , décrits pour la première fois en 1993, implémentent une concaténation parallèle de deux codes convolutifs, avec un entrelaceur entre les deux codes et un décodeur itératif qui assure la transmission d'informations entre eux. Cette conception offre des performances supérieures à celles de tous les codes à concaténation conçus précédemment.

Cependant, un aspect essentiel des turbocodes réside dans leur approche de décodage itératif. Ce décodage est désormais également appliqué aux concaténations en série afin d'obtenir des gains de codage plus élevés, notamment dans les codes convolutifs à concaténation en série (SCCC). Une forme primitive de décodage itératif a été implémentée avec deux à cinq itérations dans le « code Galileo » de la sonde spatiale Galileo .