Les codes LDPC régulière et irrégulière

LE CODE LDPC

Introduction

Pour protéger les informations transmises dans un canal contre le bruit, les parasites et les attaques réseaux. Il faut d’abord les coder. Cette opération consiste en deux types de codages le codage source et le codage canal. Le codage source peut sécuriser l’information contre les attaques cependant le codage canal peut nous donner si le message est erroné ou non au niveau de la réception (décodage). Ce dernier peut seulement détecter les erreurs ou bien les corriger selon le type de code utilisé.
Dans ce manuscrit je base sur le codage canal plus précisément le code LDPC. Ce chapitre présente l’évolution du code LDPC avec le temps, les notions de base de code LDPC, ses caractéristiques (régulier ou non, faible densité…) et comment construire ce type de code et le code QC-LDPC. Les codes QC-LDPC sont des types particuliers des codes LDPC. Les codes QC-LDPC consiste à créer des sous matrices à partir de la matrice de parité initiale, il est moins complexe au niveau de l’encodage et le décodage. Enfin de ce chapitre on présente les méthodes d’encodage et les algorithmes de décodages.

Historique

Les codes LDPC (Low Density Parity Check) font leur première apparition en 1962 dans une monographie de Gallager [13], mais il a proposé seulement une méthode générale pour construire des codes LDPC pseudo aléatoires ; les bons codes LDPC sont générés par ordinateur (en particulier les codes longs) et leur décodage est très complexe dû au manque de structure.
Ces codes ont été ignorés jusqu’à 1981 quand Tanner leur a donné une nouvelle interprétation d’un point de vue graphique, Sa théorie a été aussi ignorée pour les prochaines 14 années (La raison principale de ce délaissement en est la complexité du décodage par rapport aux capacités calculatoires de l’époque. Alors que la communauté des codes correcteurs se focalisait principalement sur des codes basés sur des structures algébriques fortes.) jusqu’au jour où quelques chercheurs en codage ont commencé à étudier les codes en graphes et le décodage itératif. Deux chercheurs, McKay et Neal, ont introduit une nouvelle classe de codes de blocs conçus pour posséder plusieurs caractéristiques des nouveaux codes turbo. Ces codes de blocs étaient une redécouverte des codes LDPC développés par Gallager. En effet, l’algorithme utilisé pour décoder les turbo-codes a été montré par la suite comme un cas particulier de l’algorithme de décodage pour les codes LDPC présentés par Gallager. Cet article de MacKay présente des constructions de codes LDPC et montre leur bonnes performances par de nombreuses simulations.

Des nouvelles généralisations des codes LDPC de Gallager par un certain nombre de chercheurs, y compris Luby, Mitzenmacher, Shokrollahi, Spielman, Richardson et Urbanke, ont produit de nouveaux codes LDPC irréguliers, qui surpassent facilement les meilleurs codes turbo, Ainsi que d’offrir certains avantages pratiques et une configuration sans doute plus propre pour les résultats théoriques. Aujourd’hui, il existe des techniques de conception pour les constructions des codes LDPC qui s’approchent de la capacité de Shannon à l’intérieur des centièmes de décibels. Les codes LDPC sont rapidement développés avec le temps et ont adopté aux plusieurs applications comme la radiodiffusion numérique par satellite et les normes de communication optique de longue distance et sont très susceptibles d’être adoptés dans la norme de réseau local sans fil IEEE.

Representation du code LDPC

Le code LDPC peut être représenté sous deux formes : la forme matricielle et la représentation graphique dit aussi le graphe de Tanner.

La représentation matricielle

Le code LDPC peut être représenté par la matrice de parité H(n,m) caractérisée par :
m équations de contrôle de parité qui doivent être satisfaites par les bits codés (noeuds de contrôle.

Construction du code LDPC

Les codes LDPC peuvent être construits selon deux méthodes : la méthode aléatoire et la méthode structurée.

La méthode aléatoire

Les codes LDPC aléatoires sont générés par ordinateur. Ces codes fonctionnent bien et ils sont proches de la limite de Shannon. Cette méthode peut génère du code de longueur très grand suite avec une augmentation au poids et de la taille minimale [16]. Cependant, l’encodage des codes LDPC générés aléatoirement est complexe en raison de leur structure.
Il existe certains types populaires de codes LDPC aléatoires, comme la construction de Gallager [17], Ma ckay [18].

L’approche de la construction aléatoire est parfois problématique car elle demande un stockage de la matrice de parité. Cette matrice ne comportant pas de symétrie, ce stockage peut être gourmand.

La méthode structurée

Les codes structurés ont un avantage sur les codes aléatoires concernant la complexité d’ encodage et de décodage de ces codes. Pour réduire la complexité de l’encodage il faut concevoir des codes ayant également une matrice de générateur à faible densité [19]. Dans ce cas, G est également creuse et le nombre d’opérations élémentaires nécessaires au codage est réduit.

Une autre solution pour réduire la complexité du codage consiste à utiliser des techniques de codage qui exploitent une matrice de contrôle de parité H limité pour le codage. Ceci est facilement réalisé lorsque H admet une représentation creuse dans une forme triangulaire inférieure. Dans ce cas, H a la forme suivante [15]:

Où les nombre du valeur non nul est très petite dans chaque ligne par rapport a la longueur n.

Autre type de code LDPC structuré qui est très utilisé c’est QC-LDPC. L’encodage est plus facile si le code LDPC est aussi quasi-cyclique par l’utilisation des techniques et des structures de ce dernier. Ces codes peuvent être construits selon des méthodes algébriques.

Notons que la performance du code LDPC dépond de la méthode choisie pour le construire. les méthodes structurées largement utilisées sont : la construction basée sur la superposition [21], l’utilisation du tableaux (Vandermonde matrix) [20], conception de blocs incomplets équilibrés (Balanced incomplete block designs BIBD)[20], La géométrie finie [22], la construction basée sur des graphe [23].

Les codes LDPC quasi-cyclique

Les codes QC-LDPC ce sont des codes prédéfinis. On peut référer les codes QC-LDPC à des codes QC caractérisé par la matrice de contrôle de parité H qui sont bien adaptés aux algorithmes de décodage LDPC [13]. La matrice de parité doit être creuse et il faut éviter les courts cycles dans le graphe de Tanner. Deux classes principales sont utilisées pour construire un codes QC-LDPC .Et qui sont ; ‘’bloc circulant’’ et ‘’les lignes circulants’’, Deux autres classifications sont aussi possibles : matrice circulant et la permutation des matrices circulantes.

Construction des codes LDPC quasi-cycliques par décomposition circulaire

Cette méthode consiste à décomposer une matrice carrée, régulière et circulaire en plusieurs matrices circulaires de mêmes dimensions, mais avec des poids différents [17]. On peut utiliser deux méthodes : la décomposition des colonnes du matrice de parité et la décomposition du lignes. La décomposition des colonnes consiste à construire des nouvelles matrices à partir de la décomposition de chaque colonne de la matrice de parité initiale, qui est décomposée en plusieurs colonnes de même longueur. Le poids de la colonne initiale est partagé entre les différentes colonnes. À partir de chaque nouvelle colonne, on forme une matrice circulaire par permutations circulaires successives de la colonne en bas vers le haut.

De même, on peut décomposer la matrice initiale, en décomposant sa première ligne en plusieurs lignes et ensuite en faisant des permutations circulaires à la droite de chaque nouvelle ligne. Cette méthode s’appelle la décomposition de rangées. Si la matrice initiale est une matrice creuse, la matrice obtenue est aussi une matrice creuse de densité plus faible, qui donne un code LDPC quasi-cyclique et où le graphe de Tanner ne présente pas le cycle de longueur 4.

L’encodage et le décodage

L’encodage

Un code LDPC peut être codé par les mêmes techniques utilisées par un autre code bloc linéaire, et la complexité de l’encodage dépend de l’algorithme de codage utilisée. La meilleure performance des codes LDPC est réalisée pour une matrice de parité très longue [8]. Si n est la longueur du code donc il existe mots codes ou k est la longueur du message d’information (n>k).
L’encodage de code bloc linéaire classique du code LDPC consiste à écrire la matrice de parité H sous la forme suivante :

Table des matières

1 Introduction 
2 Phénomènes de propagation 
3 Le canal de transmission 
4 Type d’évanouissement (fading)
4.1 L’évanouissement à grande échelle
4.1.1 Perte de propagation (ou perte de trajet)
4.1.2 L’effet de masquage (L’ombrage)
4.2 L’évanouissement à petite échelle
5 Caractéristique du canal à évanouissement
5.1 Le temps de cohérence
5.2 L’étalement temporel
5.3 Le canal sélectif et le canal non sélectif en fréquence
5.3.1 Le canal non sélectif en fréquence
5.3.2 Le canal sélectif en fréquence
6 Les canaux de transmission avec évanouissements 
6.1 Distribution de Rice
6.2 Distribution de Rayleigh
7 La modélisation des canaux avec la loi α-stable 
7.1 Les bruits impulsifs
7.2 Définitions des lois α-stables
7.3 Les propriétés de α-stable
7.4 Densité de probabilité
7.5 Le calcule du SNR Géométrique
7.6 Modélisation d’un canal à bruit additif SαS
8 Conclusion
9 Introduction
10 Historique
11 Définition de code LDPC
12 Representation du code LDPC 
12.1 La représentation matricielle
12.2 La représentation graphique (graphe de Tanner)
13 Les codes LDPC régulière et irrégulière
14 Construction du code LDPC 
14.1 La méthode aléatoire
14.2 La méthode structurée
14.3 Les codes LDPC quasi-cyclique
14.3.1 Les code basés sur les matrice ‘’circulant bloc’’
14.3.2 Les codes basé sur la matrice ‘’circulant en ligne’’
14.4 Construction des codes LDPC quasi-cycliques par décomposition circulaire
15 L’encodage et le décodage
15.1 L’encodage
15.2 Décodage LDPC
15.2.1 Décodage BF
15.2.2 L’algorithme de décodage SPA ( Sum-product Algorithm)
16 Conclusion 
17 Introduction 
18 La chaine de transmission o Bloc émetteur 
18.1.1 Codage de canal, entrelacement et multiplexage
18.2 LE RECEPTEUR
18.3 fading multi-trajets
19 Les paramètres de la simulation
20 Résultat de la simulation 
20.1 Le modèle EPA
20.1.1 La modulation 4QAM
20.1.2 La modulation 16 QAM
20.1.3 La modulation 64QAM
20.1.4 Modulation 254QAM
20.2 Canal de fading ETU
20.2.1 4QA M
20.2.2 Modulation 16QAM
20.2.3 Modulation 64QAM
20.2.4 Modulation 256QAM
20.3 le canal EVA
20.3.1 modulation 4QAM
20.3.2 Modulation 16QAM
20.3.3 Modulation 64QAM
20.3.4 Modulation 256QAM
21 Conclusion

Télécharger le rapport complet