Code de contrôle de parité basse densité - Low-density parity-check code

En théorie de l'information , un code de contrôle de parité à faible densité ( LDPC ) est un code de correction d'erreur linéaire , une méthode de transmission d'un message sur un canal de transmission bruyant . Un LDPC est construit à l'aide d'un graphe de Tanner clairsemé (sous-classe du graphe bipartite ). Les codes LDPC sont des codes approchant la capacité , ce qui signifie qu'il existe des constructions pratiques qui permettent de fixer le seuil de bruit très près du maximum théorique (la limite de Shannon ) pour un canal symétrique sans mémoire. Le seuil de bruit définit une limite supérieure pour le bruit de canal, jusqu'à laquelle la probabilité de perte d'informations peut être rendue aussi faible que souhaité. En utilisant des techniques de propagation de croyances itératives , les codes LDPC peuvent être décodés dans le temps de manière linéaire à leur longueur de bloc.

Les codes LDPC sont de plus en plus utilisés dans les applications nécessitant un transfert d'informations fiable et très efficace sur des liaisons à bande passante ou à canal de retour contraint en présence de bruit corrompant. La mise en œuvre des codes LDPC a pris du retard par rapport à d'autres codes, notamment les codes turbo . Le brevet fondamental pour les codes turbo a expiré le 29 août 2013.

Les codes LDPC sont également connus sous le nom de codes Gallager , en l'honneur de Robert G. Gallager , qui a développé le concept LDPC dans sa thèse de doctorat au Massachusetts Institute of Technology en 1960.

Histoire

Difficiles à mettre en œuvre lorsqu'ils ont été développés par Gallager en 1963, les codes LDPC ont été oubliés jusqu'à ce que son travail soit redécouvert en 1996. Les codes turbo , une autre classe de codes approchant la capacité découverte en 1993, est devenu le schéma de codage de choix à la fin des années 1990, utilisé pour des applications telles que le Deep Space Network et les communications par satellite . Cependant, les progrès des codes de contrôle de parité à faible densité les ont vus surpasser les codes turbo en termes de plancher d'erreur et de performances dans la plage de taux de code supérieure , laissant les codes turbo mieux adaptés uniquement aux taux de code inférieurs.

Applications

En 2003, un code LDPC de style IRA (irrégulière répétition accumulée) a battu six codes turbo pour devenir le code de correction d'erreur dans la nouvelle norme DVB-S2 pour la transmission par satellite de la télévision numérique . Le comité de sélection DVB-S2 a fait des estimations de la complexité du décodeur pour les propositions Turbo Code en utilisant une architecture de décodeur série beaucoup moins efficace plutôt qu'une architecture de décodeur parallèle. Cela a forcé les propositions de Turbo Code à utiliser des tailles de trame de l'ordre de la moitié de la taille de trame des propositions LDPC.

En 2008, LDPC a battu turbo codes convolutifs comme la correction d'erreurs système (FEC) pour l' UIT-T G.hn standard. G.hn a choisi les codes LDPC sur les codes turbo en raison de leur complexité de décodage moindre (en particulier lorsqu'ils fonctionnent à des débits de données proches de 1,0 Gbit / s) et parce que les codes turbo proposés présentaient un plancher d'erreur significatif dans la plage de fonctionnement souhaitée.

Les codes LDPC sont également utilisés pour 10GBASE-T Ethernet, qui envoie des données à 10 gigabits par seconde sur des câbles à paires torsadées. Depuis 2009, les codes LDPC font également partie de la norme Wi-Fi 802.11 en tant que partie optionnelle de 802.11n et 802.11ac , dans la spécification PHY à haut débit (HT).

Certains systèmes OFDM ajoutent une correction d'erreur externe supplémentaire qui corrige les erreurs occasionnelles (le «plancher d'erreur») qui dépassent le code interne de correction LDPC même à de faibles taux d'erreur sur les bits . Par exemple: le code Reed-Solomon avec modulation codée LDPC (RS-LCM) utilise un code externe Reed-Solomon. Les normes DVB-S2, DVB-T2 et DVB-C2 utilisent toutes un code externe de code BCH pour éliminer les erreurs résiduelles après le décodage LDPC.

Utilisation opérationnelle

Les codes LDPC sont fonctionnellement définis par une matrice creuse de contrôle de parité . Cette matrice clairsemée est souvent générée aléatoirement, sous réserve des contraintes de parcimonie - la construction du code LDPC est abordée plus loin . Ces codes ont été conçus pour la première fois par Robert Gallager en 1960.

Vous trouverez ci-dessous un fragment de graphique d'un exemple de code LDPC utilisant la notation graphique factorielle de Forney . Dans ce graphe, n nœuds variables en haut du graphe sont connectés à ( n - k ) nœuds de contrainte en bas du graphe.

Il s'agit d'une manière courante de représenter graphiquement un code LDPC ( n ,  k ). Les bits d'un message valide, lorsqu'ils sont placés sur les T en haut du graphe, satisfont les contraintes graphiques. Plus précisément, toutes les lignes se connectant à un nœud variable (case avec un signe '=') ont la même valeur, et toutes les valeurs connectées à un nœud de facteur (case avec un signe '+') doivent additionner, modulo deux, à zéro (en en d'autres termes, ils doivent totaliser un nombre pair ou il doit y avoir un nombre pair de valeurs impaires).

En ignorant les lignes sortant de l'image, il y a huit chaînes de six bits possibles correspondant à des mots de code valides: (c'est-à-dire, 000000, 011001, 110010, 101011, 111100, 100101, 001110, 010111). Ce fragment de code LDPC représente un message de trois bits codé sur six bits. La redondance est utilisée ici pour augmenter les chances de récupération après des erreurs de canal. C'est un code linéaire (6, 3) , avec n  = 6 et k  = 3.

Encore une fois en ignorant les lignes sortant de l'image, la matrice de contrôle de parité représentant ce fragment de graphe est

${\ displaystyle \ mathbf {H} = {\ begin {pmatrix} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 \\\ end {pmatrix}}.}$

Dans cette matrice, chaque ligne représente l'une des trois contraintes de contrôle de parité, tandis que chaque colonne représente l'un des six bits du mot de code reçu.

Dans cet exemple, les huit mots de code peuvent être obtenus en mettant la matrice de contrôle de parité H sous cette forme via des opérations de ligne de base dans GF (2) : ${\ displaystyle {\ begin {bmatrix} -P ^ {T} | I_ {nk} \ end {bmatrix}}}$

${\ displaystyle \ mathbf {H} = {\ begin {pmatrix} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 \\\ end {pmatrix}} _ {1} \ sim {\ begin {pmatrix} 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \\ end {pmatrix}} _ {2} \ sim {\ begin {pmatrix} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\\ end {pmatrix}} _ {3} \ sim {\ begin {pmatrix} 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\\ end {pmatrix}} _ {4}.}$

Étape 1: H.

Étape 2: La ligne 1 est ajoutée à la ligne 3.

Étape 3: Les lignes 2 et 3 sont permutées.

Étape 4: La ligne 1 est ajoutée à la ligne 3.

A partir de là, la matrice génératrice G peut être obtenue comme (en notant que dans le cas particulier où il s'agit d'un code binaire ), ou spécifiquement: ${\ displaystyle {\ begin {bmatrix} I_ {k} | P \ end {bmatrix}}}$${\ displaystyle P = -P}$

${\ displaystyle \ mathbf {G} = {\ begin {pmatrix} 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 \\\ end {pmatrix}}.}$

Enfin, en multipliant les huit chaînes de 3 bits possibles par G , les huit mots de code valides sont obtenus. Par exemple, le mot de code pour la chaîne de bits '101' est obtenu par:

${\ displaystyle {\ begin {pmatrix} 1 & 0 & 1 \\\ end {pmatrix}} \ odot {\ begin {pmatrix} 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 \\\ end {pmatrix}} = {\ begin & 1 pmatrix} 1 & 0 & 1 & 1 & 1 & 1 \\ end {pmatrix}}}$ ,

où est le symbole de la multiplication mod 2. ${\ displaystyle \ odot}$

A titre de vérification, l'espace des lignes de G est orthogonal à H tel que ${\ displaystyle G \ odot H ^ {T} = 0}$

La chaîne de bits «101» se trouve dans les 3 premiers bits du mot de code «101011».

Exemple d'encodeur

La figure 1 illustre les composants fonctionnels de la plupart des codeurs LDPC.

Fig. 1. Encodeur LDPC

Lors du codage d'une trame, les bits de données d'entrée (D) sont répétés et distribués à un ensemble de codeurs constitutifs. Les codeurs constitutifs sont généralement des accumulateurs et chaque accumulateur est utilisé pour générer un symbole de parité. Une seule copie des données originales (S _{0, K-1} ) est transmise avec les bits de parité (P) pour constituer les symboles de code. Les bits S de chaque codeur constitutif sont rejetés.

Le bit de parité peut être utilisé dans un autre code constituant.

Dans un exemple utilisant le code DVB-S2 à débit 2/3, la taille de bloc codée est de 64800 symboles (N = 64800) avec 43200 bits de données (K = 43200) et 21600 bits de parité (M = 21600). Chaque code constituant (noeud de contrôle) code 16 bits de données à l'exception du premier bit de parité qui code 8 bits de données. Les 4680 premiers bits de données sont répétés 13 fois (utilisés dans 13 codes de parité), tandis que les bits de données restants sont utilisés dans 3 codes de parité (code LDPC irrégulier).

A titre de comparaison, les turbo codes classiques utilisent généralement deux codes constitutifs configurés en parallèle, dont chacun code le bloc d'entrée entier (K) de bits de données. Ces codeurs constitutifs sont des codes convolutifs récursifs (RSC) de profondeur modérée (8 ou 16 états) qui sont séparés par un entrelaceur de code qui entrelace une copie de la trame.

Le code LDPC, en revanche, utilise de nombreux codes constitutifs de faible profondeur (accumulateurs) en parallèle, chacun codant seulement une petite partie de la trame d'entrée. Les nombreux codes constituants peuvent être considérés comme de nombreux «codes convolutifs» de faible profondeur (2 états) qui sont connectés via les opérations de répétition et de distribution. Les opérations de répétition et de distribution remplissent la fonction d'entrelaceur dans le turbo code.

La capacité à gérer plus précisément les connexions des différents codes constitutifs et le niveau de redondance pour chaque bit d'entrée donnent plus de flexibilité dans la conception des codes LDPC, ce qui peut conduire à de meilleures performances que les turbo codes dans certains cas. Les codes turbo semblent toujours plus performants que les LDPC à des taux de code bas, ou du moins la conception de codes à bas débit performants est plus facile pour les codes turbo.

En pratique, le matériel qui forme les accumulateurs est réutilisé pendant le processus de codage. C'est-à-dire qu'une fois qu'un premier ensemble de bits de parité est généré et que les bits de parité sont stockés, le même matériel d'accumulateur est utilisé pour générer un ensemble suivant de bits de parité.

Décodage

Comme pour les autres codes, le décodage par maximum de vraisemblance d'un code LDPC sur le canal symétrique binaire est un problème NP-complet . Il n'est pas pratique d'effectuer un décodage optimal pour un code NP-complet de toute taille utile.

Cependant, les techniques sous-optimales basées sur le décodage itératif de propagation de croyances donnent d'excellents résultats et peuvent être mises en œuvre dans la pratique. Les techniques de décodage sous-optimales considèrent chaque contrôle de parité qui constitue le LDPC comme un code de contrôle de parité unique (SPC) indépendant. Chaque code SPC est décodé séparément en utilisant des techniques d' entrée-sortie douce (SISO) telles que SOVA , BCJR , MAP et d'autres dérivés de ceux-ci. Les informations de décision souple de chaque décodage SISO sont vérifiées par recoupement et mises à jour avec d'autres décodages SPC redondants du même bit d'information. Chaque code SPC est ensuite décodé à nouveau en utilisant les informations de décision souple mises à jour. Ce processus est répété jusqu'à ce qu'un mot de code valide soit atteint ou que le décodage soit épuisé. Ce type de décodage est souvent appelé décodage de produit de somme.

Le décodage des codes SPC est souvent appelé traitement "noeud de contrôle", et la vérification croisée des variables est souvent appelée traitement "noeud variable".

Dans une implémentation pratique de décodeur LDPC, des ensembles de codes SPC sont décodés en parallèle pour augmenter le débit.

En revanche, la propagation des croyances sur le canal d'effacement binaire est particulièrement simple lorsqu'elle consiste en une satisfaction itérative de contraintes.

Par exemple, considérons que le mot de code valide, 101011, de l'exemple ci-dessus, est transmis à travers un canal d'effacement binaire et reçu avec le premier et le quatrième bit effacés pour donner? 01-11. Etant donné que le message transmis doit avoir satisfait aux contraintes de code, le message peut être représenté en écrivant le message reçu en haut du graphe de facteurs.

Dans cet exemple, le premier bit ne peut pas encore être récupéré, car toutes les contraintes qui lui sont connectées ont plus d'un bit inconnu. Afin de procéder au décodage du message, les contraintes de connexion à un seul des bits effacés doivent être identifiées. Dans cet exemple, seule la deuxième contrainte suffit. En examinant la deuxième contrainte, le quatrième bit doit avoir été zéro, car seul un zéro dans cette position satisferait la contrainte.

Cette procédure est ensuite répétée. La nouvelle valeur du quatrième bit peut maintenant être utilisée conjointement avec la première contrainte pour récupérer le premier bit comme indiqué ci-dessous. Cela signifie que le premier bit doit être un pour satisfaire la contrainte la plus à gauche.

Ainsi, le message peut être décodé de manière itérative. Pour les autres modèles de canaux, les messages passés entre les nœuds variables et les nœuds de contrôle sont des nombres réels , qui expriment des probabilités et des probabilités de croyance.

Ce résultat peut être validé en multipliant le mot de code corrigé r par la matrice de contrôle de parité H :

${\ displaystyle \ mathbf {z} = \ mathbf {H \ odot r} = {\ begin {pmatrix} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 \\\ end {pmatrix}} \ odot {\ begin {pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\\ end {pmatrix}} = {\ begin {pmatrix} 0 \\ 0 \\ 0 \\\ end {pmatrix}}.}$

Comme le résultat z (le syndrome ) de cette opération est le vecteur zéro trois × un, le mot de code résultant r est validé avec succès.

Une fois le décodage terminé, les bits de message d'origine «101» peuvent être extraits en regardant les 3 premiers bits du mot de code.

Bien qu'illustratif, cet exemple d'effacement ne montre pas l'utilisation du décodage à décision douce ou du passage de message à décision douce, qui est utilisé dans pratiquement tous les décodeurs LDPC commerciaux.

Mise à jour des informations de nœud

Ces dernières années, de nombreux travaux ont également été consacrés à l'étude des effets des horaires alternatifs pour la mise à jour des nœuds variables et des nœuds de contrainte. La technique originale utilisée pour décoder les codes LDPC était connue sous le nom d' inondation . Ce type de mise à jour nécessitait que, avant de mettre à jour un nœud variable, tous les nœuds de contrainte devaient être mis à jour et vice versa. Dans les travaux ultérieurs de Vila Casado et al. , des techniques de mise à jour alternatives ont été étudiées, dans lesquelles les nœuds variables sont mis à jour avec les dernières informations disponibles sur les nœuds de contrôle.

L'intuition derrière ces algorithmes est que les nœuds variables dont les valeurs varient le plus sont ceux qui doivent être mis à jour en premier. Les nœuds hautement fiables, dont la magnitude du rapport de vraisemblance logarithmique (LLR) est grande et ne change pas de manière significative d'une mise à jour à l'autre, ne nécessitent pas de mises à jour avec la même fréquence que les autres nœuds, dont le signe et la magnitude fluctuent plus largement. Ces algorithmes d'ordonnancement montrent une plus grande vitesse de convergence et des niveaux d'erreur inférieurs que ceux qui utilisent l'inondation. Ces seuils d'erreur inférieurs sont obtenus grâce à la capacité de l'algorithme de planification dynamique informée (IDS) à surmonter les ensembles de piégeage de mots de code proches.

Lorsque des algorithmes de planification sans inondation sont utilisés, une autre définition de l'itération est utilisée. Pour un code LDPC ( n ,  k ) de débit k / n , une itération complète se produit lorsque n variables et n  -  k nœuds de contrainte ont été mis à jour, quel que soit l'ordre dans lequel ils ont été mis à jour.

Construction du code

Pour les blocs de grande taille, les codes LDPC sont généralement construits en étudiant d'abord le comportement des décodeurs. Comme la taille des blocs tend vers l'infini, on peut montrer que les décodeurs LDPC ont un seuil de bruit en dessous duquel le décodage est réalisé de manière fiable, et au-dessus duquel le décodage n'est pas réalisé, familièrement appelé effet de falaise . Ce seuil peut être optimisé en trouvant la meilleure proportion d'arcs à partir de nœuds de contrôle et d'arcs à partir de nœuds variables. Une approche graphique approximative pour visualiser ce seuil est un graphique EXIT .

La construction d'un code LDPC spécifique après cette optimisation se décline en deux types principaux de techniques:

• Approches pseudo-aléatoires
• Approches combinatoires

La construction par une approche pseudo-aléatoire s'appuie sur des résultats théoriques selon lesquels, pour une grande taille de bloc, une construction aléatoire donne de bonnes performances de décodage. En général, les codes pseudo-aléatoires ont des codeurs complexes, mais les codes pseudo-aléatoires avec les meilleurs décodeurs peuvent avoir des codeurs simples. Diverses contraintes sont souvent appliquées pour aider à garantir que les propriétés souhaitées attendues à la limite théorique d'une taille de bloc infinie se produisent à une taille de bloc finie.

Des approches combinatoires peuvent être utilisées pour optimiser les propriétés de codes LDPC de petite taille de bloc ou pour créer des codes avec de simples encodeurs.

Certains codes LDPC sont basés sur des codes Reed – Solomon , tels que le code RS-LDPC utilisé dans la norme 10 Gigabit Ethernet . Par rapport aux codes LDPC générés aléatoirement, les codes LDPC structurés - comme le code LDPC utilisé dans la norme DVB-S2 - peuvent avoir un matériel plus simple et donc moins coûteux - en particulier, des codes construits de telle sorte que la matrice H est une matrice circulante .

Encore une autre façon de construire des codes LDPC consiste à utiliser des géométries finies . Cette méthode a été proposée par Y. Kou et al. en 2001.

Codes LDPC et codes Turbo

Les codes LDPC peuvent être comparés à d'autres schémas de codage puissants, par exemple les codes Turbo. D'une part, les performances BER des codes Turbo sont influencées par les limitations des codes faibles. Les codes LDPC n'ont aucune limitation de distance minimale, ce qui signifie indirectement que les codes LDPC peuvent être plus efficaces sur des débits de code relativement élevés (par exemple 3/4, 5/6, 7/8) que les codes Turbo. Cependant, les codes LDPC ne sont pas le remplacement complet: les codes Turbo sont la meilleure solution aux taux de code inférieurs (par exemple 1/6, 1/3, 1/2).

Voir également

Gens

• Robert G. Gallager
• Richard Hamming
• Claude Shannon
• David JC MacKay
• Irving S. Reed
• Michael Luby

Théorie

• Propagation des croyances
• La théorie des graphes
• Code de hamming
• Code linéaire
• Code graphique fragmenté
• Code d'extension

Applications

• G.hn/G.9960 (norme ITU-T pour la mise en réseau sur les lignes électriques, les lignes téléphoniques et les câbles coaxiaux)
• 802.3an ou 10GBASE-T (Ethernet 10 Giga-bit / s sur paire torsadée)
• CMMB (China Multimedia Mobile Broadcasting)
• DVB-S2 / DVB-T2 / DVB-C2 (diffusion vidéo numérique, 2e génération)
• DMB-T / H (diffusion vidéo numérique)
• WiMAX (norme IEEE 802.16e pour les communications micro-ondes)
• IEEE 802.11n-2009 ( norme Wi-Fi )
• DOCSIS 3.1

Autres codes approchant la capacité

• Codes turbo
• Codes convolutifs concaténés en série
• Codes en ligne
• Codes de fontaine
• Codes LT
• Codes Raptor
• Codes de répétition-accumulation (une classe de codes turbo simples)
• Codes Tornado ( codes LDPC conçus pour le décodage d'effacement )
• Codes polaires

Les références

Liens externes

• Présentation des codes de contrôle de parité à faible densité (par Sarah J Johnson, 2010)
• Codes LDPC - un bref tutoriel (par Bernhard Leiner, 2005)
• Codes LDPC (TU Wien)
• Le manuel en ligne: Théorie de l'information, inférences et algorithmes d'apprentissage , par David JC MacKay , traite des codes LDPC au chapitre 47.
• Décodage itératif des codes de contrôle de parité à faible densité (par Venkatesan Guruswami, 2006)
• Codes LDPC: une introduction (par Amin Shokrollahi, 2003)
• Décodage par propagation de croyance des codes LDPC (par Amir Bennatan, Université de Princeton)
• Codes Turbo et LDPC: mise en œuvre, simulation et normalisation (West Virginia University)
• Théorie et codage de l'information (Marko Hennhöfer, 2011, TU Ilmenau) - traite des codes LDPC aux pages 74-78.
• Codes LDPC et résultats de performance
• Lien DVB-S.2, y compris le codage LDPC (MatLab)
• Le code source pour le codage, le décodage et la simulation des codes LDPC est disponible à partir de plusieurs emplacements:
  • Codes LDPC binaires en C
  • Codes LDPC binaires pour Python (algorithme de base en C)
  • Codeur LDPC et décodeur LDPC dans MATLAB
  • Une boîte à outils de correction d'erreur à avance rapide (AFF3CT) en C ++ 11 pour des simulations LDPC rapides