à‰tude des codes ldpc réguliers.

RéPUBLIQUE ALGéRIENNE DéMOCRATIQUE ET POPULAIRE Ministère de l'enseigneMent supérieur ET DE LA RECHERCHE SCIENTIFIQUE IFIQUE UNIVERSITé DE DJILALI LIABES SIDI BEL ABBéS départeMent d'electronique

MéMoire de fin d'etude pour l'obtention de diplôMe

MASTER II EN GéNIE ELECTRIQUE OPTION : GéNIE INFORMATIQUE

Présenté par:

Melle MEGHOUFEL Lamia Nour El Houda

Encadré par:

Mme R. MELIANI Docteur Chargé de Cours
(UDL)

Thème :

Etude des codes LDPC réguliers

Devant le jury composé par :

Mr A. BOUNOUA MCA (UDL) Président du jury.

Mr Z. CHAMA MCA (UDL) Examinateur.

ANNéE UNIVERSITAIRE: 2011/2012

REMERCIEMENTS

Tout d'abord, je voudrais remercier M^me R. MELIANI. Plus qu'un encadreur de mémoire, elle été d'abord mon professeur. Je lui remercie vivement, pour m'avoir proposé ce sujet assez passionnant et apporté son soutien ainsi que de nombreuses idées nécessaires à sa réalisation. Ses compétences scientifiques, son sens de l'orientation et ses qualités humaines notamment, sa patience et son organisation, m'ont permis de surmonter de nombreuses difficultés liées à ce travail.

Je remercie aussi notamment M^r A. Bounoua le président du jury et M^r Z. Chama pour l'honneur qu'ils m'ont fait en participant à mon jury de mémoire.

Je tiens à louer mon père pour sa bienveillance, sans laquelle ce mémoire n'aurait jamais vu le jour. La préparation et l'achèvement de ce mémoire n'auraient aucun goût sans le réconfort de ma mère et mes soeurs.

Enfin c'est avec sincérité que je veux dire MERCI à toutes ces personnes qui ont contribué, de prés ou de loin, à cette expérience très personnelle que peut représenter un mémoire.

SOMMAIRE Remerciements Sommaire Liste des figures
Introduction générale		.1
Chapitre I
I.1. Introduction		.4
I.2. La chaine de transmission numérique		..5
I.2.1. La source numérique		.6
I.2.2. Codage de source		..6
I.2.3. Codage de canal		7
I.2.4. L?émetteur		.9
? Modulations numériques
I.2.5. Canal de transmission numérique		17
? Modèles des canaux de transmission numériques
I.2.6. Le récepteur		20
I.3. Conclusion	.20
Chapitre II
II.1. Introduction	..21			II.2. Les codes convolutifs
22
II.2.1. Présentation des codes convolutifs	22

II.2.2. Présentation des codeurs convolutifs .24

· Diagramme d'état

· Diagramme en treillis

II.2.3. Décodage des codes convolutifs 26

· Principe de l'algorithme de Viterbi

II.3. Les codes en blocs linéaires ..27

II.3.1. Définition générale d'un code en bloc 27

II.3.2. Définition d'un code linéaire 28

· Propriétés des codes linéaires

II.3.3. Généralité du décodage ..28

II.3.4. génération d'un mot de code ..29

· Matrice génératrice

· Principe de réalisation du codeur

II.3.5. Détection des erreurs de transmission ...30

· Matrice de contrôle de parité

II.3.6. Famille des codes en blocs linéaires ..32

· Les codes cycliques

· Les codes de Hamming

· Les codes BCH (Bose -Chaudhuri-Hocquenghem)

· Les codes de Reel-Solomon

II.4. Conclusion 35

Chapitre III

III.1. Introduction .36

III.2. Définition des codes LDPC 36

III.3. Les graphes de Tanner pour les codes LDPC .38

III.4. Encodage des codes LDPC .39

III.5. Construction des codes LDPC 41

III.5.1. Construction géométrique des codes LDPC .41

III.5.2. Construction des codes LDPC de Gallager ..42

III.5.3. Les codes LDPC aléatoires ..43

III.5.4. Les codes LDPC quasi-cycliques ou réguliers 44

III.6. Décodage des codes LDPC .46

? Décodage MLG des codes LDPC

? Algorithme de décodage a basculement de bit (BF)

? Algorithme de propagation de croyance (BP)

III.7. résultats de simulation 51

III.8. conclusion 56

Conclusion générale et perspectives 57

Lexique

Bibliographie

Liste des figures

Figure I.1 : Schéma général d'une chaine de transmission numérique ..5

Figure I.2 : Place du codage de canal dans une chaine de transmission numérique ..8

Figure I.3 : Comparaison des probabilités d'erreurs binaires avec et sans codage ...8

Figure I.4 : Constellation de la modulation d'amplitude Tous Ou Rien ..11

Figure I.5 : Probabilité d'erreur par symbole de la MDA 12

Figure I.6 : Constellation des symboles en modulation de phase MDP-M pour M=2,4 et 8 13

Figure I.7 : probabilité d'erreur par symbole de la MDP	.14
Figure I.8 : Constellations de la MAQ-16 et MAQ-64	16
Figure I.9 : Canal de transmission numérique	.18
Figure I.10 : Description d'un canal binaire symétrique	..18
Figure I.11 : Diagramme du canal binaire symétrique	.19
Figure II.1 : Schéma de principe d'un codeur convolutif	23
Figure II.2 : Circuit d'un codeur convolutif C (2, 1, 3)	23
Figure II.3 : Diagramme d'état du codeur C (2, 1, 3)	..25
Figure II.4 : Exemple de treillis	26
Figure II.5 : Diagramme en treillis du codeur C (2, 1, 3)	26
Figure II.6 : Principe de réalisation du codeur	30
Figure III.1 : Graphe bipartite d'un code LDPC	..37
Figure III.2: Représentation sous forme pseudo-triangulaire inférieure de la matrice H	39

Figure III.3 : Evaluation des performances du TEB sur un canal gaussien d'un code LDPC régulier de

rendement R=1/2 et de paramètres de la matrice (3*6) associée à une modulation

MDP2 51

Figure III.4 : Evaluation des performances du FER sur un canal gaussien d'un code LDPC régulier de

rendement R=1/2 et de paramètres de la matrice (3*6) associée à une modulation

MDP2 52

Figure III.5 : Evaluation des performances du TEB et du FER sur un canal gaussien d'un code LDPC régulier de rendement R=1/2 et de paramètres de la matrice (3*6) associée à une modulation

MDP2 52

Figure III.6 : Evaluation du décodage itératif sur canal gaussien d'un code LDPC régulier de rendement

1/2 associé à une modulation MDP-2 53

Figure III.7 : Evaluation du décodage itératif sur canal gaussien d'un code LDPC régulier de rendement

1/2 associé à une modulation MDP-2 53

Figure III.8 : Evaluation des performances du TEB et du FER sur un canal gaussien d'une modulation MDP-2 à la ₁ière ,4ième et la ^6ième itération d'un code LDPC régulier de rendement R=1/2 et de

paramètres (1000*2000) .54

Figure III.9 : Evaluation du TEB sur canal gaussien d'un turbo code poinçonné ou non poinçonné et d'un code LDPC régulier de rendement 1/2 associé à une modulation MDP-2 à la ^5ième et à la 6ième

itération .54

INTRODUCTION GéNéRALe

Nous vivons dans l'ère des télécommunications et de l'information. Lors des deux dernières décennies, les communications numériques ont beaucoup évolué. De nos jours, l'information est dans la plupart des cas véhiculée sous forme numérique, que ce soit sur support filaire (fibres optiques), ou en radio, réseaux cellulaires ou réseaux locaux sans fil ou bien des systèmes de stockage de l'information. Cette évolution a été déclenchée et entretenue par une forte demande de transmission et de traitement fiable, rapide et efficient de l'information de tous les types (traitement de la voix, des données ou des images). Et ce phénomène est présent dans tous les domaines (militaire, gouvernemental, commercial, etc.). De plus en plus, les communications fusionnent avec les technologies de traitement des données par l'ordinateur.

Les éléments d'un système de communications consistent en la transformation analogique / numérique de l'information, la réduction de la redondance, le cryptage et la protection contre les erreurs. Dans la transmission analogique, le signal est transmis tel quel, ce qui peut causer une perte de l'information utile à la réception à cause des interférences et du bruit existant sur le canal de transmission. En plus, la quantité d'information transmise est très grande et la transmission est faite dans des circuits d'une grande complexité et donc lents. Les communications numériques ont permis de contrer ces désavantages. En appliquant des méthodes de traitement numérique du signal, on réussit à protéger le signal de manière plus efficace. Les enjeux sont : une transmission à haut débit, en temps réel, à bas taux d'erreur, sécuritaire et avec une basse consommation énergétique. Dans un système de transmission, le traitement numérique du signal peut être appliqué à plusieurs reprises.

Le codage du canal numérique transforme la séquence d'information utile en une séquence discrète codée nommée mot de code. Le mot de code peut être binaire ou non-binaire. Dans ce mémoire, on étudie seulement les codes binaires. Le défi du codage de l'information numérique est de réussir à bien récupérer l'information à la réception, le moins possible affectée par les bruits du canal de transmission. Le récepteur transforme la séquence reçue codée en une séquence estimée d'information. Cette séquence doit être idéalement la même séquence discrète transmise, mais en réalité elle est affectée par des erreurs de transmission. La séquence discrète est ensuite transformée en une séquence continue et elle est livrée à la sortie.

En 1948, Shannon [1] a démontré qu'il existe une limite au débit d'information transmis en présence du bruit, appelée <<la capacité du canal>>, mais n'a pas explicité les moyens de l'approcher. A partir de ce moment là, les chercheurs ont commencé à étudier différentes méthodes de construction des codes correcteurs d'erreurs et de minimiser le plus possible les erreurs de décodage. Même si le caractère asymptotique de cette limite ne laisse aucun espoir de l'atteindre, la communauté de la théorie de l'information a cherché comment s'en approcher au plus prés de cette fameuse limite (capacité du canal).

Donc deux familles ont été imposées : les codes en bloc linéaires et les codes convolutifs afin de réaliser des bons résultats de transmission sans erreurs. Ces deux familles présentent des excellentes performances; mais cette révolution a ouvert de nombreuses voies de recherches dans le domaine du codage correcteur des erreurs et plus globalement dans les systèmes de communications numériques. Cette avancée a eu pour conséquence une redécouverte des codes de GALLAGER, appelés aussi les codes LDPC (Low Densité Parity Check), n'avaient pas suscite à cette période d'engouement. Une raison communément admise pour expliquer cet oubli, est la difficulté pour l'époque de concevoir des circuits performants permettant de traiter les algorithmes d'écrits. En 1995, encouragé par le contexte qui a suivi la découverte du principe turbo, MACKEY redécouvre les codes de GALLAGER. Par la suite de nombreux travaux se sont intéressés à ces deux familles de codes : Turbo-codes et codes LDPC, et plus généralement à l'application du principe itératif dans un système de communication numérique, et ceci sera démontré dans ce mémoire.

Ce mémoire est composé de trois chapitres. Le détail de chacun est décri ci-dessous :

Le chapitre I est consacré à l'introduction sur la conception d'une chaine de transmission numérique que nous allons décrire avec chaque élément de base en partant de la source de message jusqu'au destinataire.

Le chapitre II traite les deux familles des codes correcteurs d'erreurs : les codes convolutifs et les codes en bloc linéaires.

Enfin le chapitre III est basé sur les codes LDPC qui sont conçus à partir des codes en blocs linéaires avec leurs codages et décodage en s'appuyant sur le décodage itératif, ensuite nous ferons des simulations.

Ce mémoire sera terminé par une conclusion générale et quelques perspectives.

Chapitre I :

Description générale d'une chaine

de transmission numérique

I.1. Introduction

De tous temps, l'homme a besoin de communiquer. En 1794 CLAUDE CHAPPE construit un télégraphe entre Paris et Lille. Il est alors possible de transmettre un message sur une longue distance. Puis, grâce à l'électricité, le télégraphe se perfectionne : mise en place d'une communication sous forme de messages codés. Les années 1832s et 1876s ont vécu des inventions importantes telles que le Morse grâce à SAMUEL MORSE et le téléphone grâce à GRAHAM BELL là où la voix peut être transmise.

La communication à distance est désormais possible grâce à une simple paire de fils en cuivre et à une source d'énergie. Aujourd'hui, il est possible de transmettre à n'importe quelle distance des milliers de conversations en simultané.

Les systèmes de transmission numérique véhiculent l'information entre une source et un destinataire en utilisant un support physique comme le câble, la fibre optique, la propagation sur un canal radioélectrique etc... Les signaux transportés peuvent être soit directement d'origine numérique, soit d'origine analogique (parole, image,...) mais convertis sous une forme numérique. La tache du système de transmission est d'acheminer le signal de la source vers le destinataire avec le plus de fiabilité possible.

Le schéma synoptique d'un système de transmission numérique [2] est donné à la figure I.1 où l'on se limite aux fonctions de bases. La source émet un message numérique sous la forme des d'éléments binaires. Le codeur englobe généralement deux fonctions fondamentalement différentes : la première appelée codage de source associe un support physique adéquat aux éléments abstraits émis par la source, et la seconde appelée codage de canal consiste à introduire la redondance dans le signal émis en vue de le protéger contre le bruit et les perturbateurs présents sur le canal de transmission. Le canal de transmission inclus l'émetteur, le milieu physique de transmission sur lequel le signal sera émis et le récepteur. Enfin du coté récepteur, les fonctions de décodage de source et décodage de canal sont les inverses respectifs des fonctions de codage de source et codage de canal situées du coté émetteur.

Maintenant, nous allons décrire de façon succincte les éléments qui constituent une chaine de transmission numérique en partant de la source vers le destinataire.

I.2. La chaine de transmission numérique

Canal de transmission

Source

Émetteur

Milieu de transmission

Destinatair

Décodage
de source

Décodage de canal

Récepteur

Codage de source

Codage de canal

Figure I.1 : Schéma général d?une chaine de transmission numérique.

Les trois caractéristiques principales [2] permettant aux fonctions de bases (éléments généraux de la chaine de transmission numérique) de comparer entre elles les différentes techniques de transmission sont les suivantes :

? La probabilité d'erreurs Pe par bit transmis permet d'évaluer la qualité d'un système de transmission. Elle est fonction de la technique de transmission utilisée, mais aussi du canal sur lequel le signal est transmis. En pratique, elle est estimée par le Taux d'Erreur Binaire (TEB);

? L'occupation spectrale du signal émis doit être connue pour utiliser efficacement la bande passante du canal de transmission. On est contraint d'utiliser de plus en plus des modulations à grande efficacité spectrale;

? La complexité du récepteur est le troisième aspect important d'un système de transmission.

I.2.1. La source numérique

Pour réaliser une transmission numérique, le message à transmettre doit être sous forme numérique. Si la source délivre un message analogique tel que le signal de parole (sortie d'un microphone) ou le signal d'image (sortie d'une caméra), il faut le numériser en échantillonnant le message analogique puis en quantifiant les échantillons obtenus. Chaque échantillon quantifié est ensuite codé.

Le message à transmettre porte de l'information ; cette information est caractérisée par l'entropie [1]. Celle-ci est une fonction mathématique qui intuitivement correspond à la quantité d'information contenue ou délivrée par une source d'information. Cette source peut être un texte écrit dans une langue donnée, un signal électrique ou encore un fichier informatique quelconque (collection d'octets).

Du point de vue d'un récepteur, plus la source émet d'informations différentes, plus l'entropie est grande, et vice versa. Plus le récepteur reçoit d'informations sur le message transmis, plus l'entropie vis-à-vis de ce message décroit, en lueur de ce gain d'information.

La définition de l'entropie d'une source selon SHANNON [1] est telle que, plus la source est redondante, moins elle contient d'informations. En l'absence de contraintes particulières, l'entropie est maximale pour une source dont tous les symboles sont équiprobables.

I.2.2. Codage de source

Un problème très important en communication est la représentation efficace des données générées par une source. Ce processus de représentation est le codage de source. Il consiste à supprimer la redondance contenue dans les messages de la source d'information. Pour être efficace l'encodeur doit s'appuyer sur les caractéristiques probabilistes de la source. Les mots de codes les plus courts seront par exemple affectés aux messages les plus fréquents de plus forte probabilité, ceci est le cas du code Morse.

L'entropie de la source impose donc une limite fondamentale à la longueur moyenne d'un mot de code utilisé pour représenter les symboles émis par cette source. Le théorème de codage de source s'appuie sur le premier théorème de SHANNON [1]. Il indique qu'il est possible de représenter les symboles émis à l'aide de mot, dont la longueur moyenne la plus faible est bornée par l'entropie de la

source. Tout code dont la longueur moyenne serait plus faible ne pourrait représenter, sans erreur de décodage les différents symboles associés à cette source.

En général, l'alphabet de la source et l'alphabet du canal sont différents. Un des premiers buts du codage est de passer de l'un à l'autre. Un autre point est que le code associé à une source est souvent très redondant. L'objectif du codage de source est alors d'éliminer cette redondance, pour aboutir à un code dont la longueur moyenne est la plus proche possible du rapport entre l'entropie de la source et l'entropie maximale de l'alphabet.

I.2.3. Codage de canal

Le bruit et les interférences du canal dégradant les signaux de communication transmis, provoquent des erreurs de détection en réception. Pour un niveau de bruit et d'interférences données, la probabilité d'erreurs peut être réduite en augmentant la puissance d'émission, puisqu'elle est une fonction décroissante de celle-ci. Cependant, cette augmentation de puissance n'est pas toujours souhaitable ; d'autre part elle se traduit par un accroissement de la consommation électrique du terminal, à éviter pour des terminaux sans fil, et d'autre part, dans le cas dans une transmission en espace libre, elle augmente les interférences inter-utilisateurs ce qui accroit la probabilité d'erreurs.

Une autre solution est le codage de canal présenté à la figure I.2. Il consiste à ajouter au message binaire des bits de redondance, de telle sorte que le message codé ait une structure particulière. En réception le décodeur de canal vérifie si cette structure est bien respectée. Dans le cas contraire, une erreur est détectée et éventuellement corrigée c'est la théorie du codage/décodage des erreurs [3]. Nous allons étudier deux types de codage dans le deuxième chapitre : le codage convolutif et le codage en bloc linéaire.

Débit Db

Msg binaire

Insertion bits de redondance

Codage de canal

Msg binair

Dc>Db

Débit

Émetteur

Signal s(t)

Milieu de
transmission

Bruits,
interférences

Récepteur

Signal r(t)

Dc>Db

Débit

Msg binair

Décodage de canal

Msg binaire

Débit Db

Figure I.2 : Place du codage de canal dans une chaine de transmission numérique.

Canal de transmission

Pour répondre aux contraintes imposées par le canal de transmission l'émetteur réalise une opération appelée <<modulation>> [5].

Le codage de canal a pour inévitable contre partie une augmentation du débit de données utiles. On cherchera donc des codages offrant la meilleure protection pour une augmentation du débit minimal. Cette efficacité pourra être mesurée par :

? Le rendement du codeur R= ???? ; ou Db et D_c représentent respectivement le débit binaire avant et

????

après le codage ;

? Le gain de codage [4], c'est-à-dire la réduction de puissance permise par le codage de canal pour

une probabilité d'erreur donnée. La figure I.3 montre une réduction de puissance après un codage de canal.

Figure I.3 : Comparaison des probabilités d'erreurs binaires avec et sans codage.

I.2.4. L'émetteur

L'émetteur a pour fonction de transformer le message (analogique ou numérique) en un signal électrique S(t), de nature analogique. Le signal émis par la source (suite de symboles) est ainsi transformé en une grandeur physique variable en fonction de temps. Le signal émis (issu de l'émetteur) doit être adapté aux contraintes imposées par le canal de transmission, contraintes au premier rang desquelles figure la nécessité de n'occuper que la bande de fréquence permise. La conception de l'émetteur doit également prendre en compte les problèmes de fonctionnement du récepteur, les interactions avec le système de codage-décodage correcteur d'erreurs s'il existe, et les impératifs de fonctionnement liés au système de transmission lui-même.

? Modulations numériques

La modulation a pour objectif d'adapter le signal à émettre au canal de transmission. Pour les transmissions en bande de base, la forme d'onde utilisée pour la mise en forme du signal physique est le plus souvent une porte ou un créneau. Dans le cas de transmissions sur porteuse [6], l'opération consiste à modifier un ou plusieurs paramètres d'une onde porteuse de forme sinusoïdale d'expression générale centrée sur la bande de fréquence du canal.

S(t) = A(t) cos (??0??+ ?? ) I.1

Dans cette expression les paramètres modifiables sont:

o L'amplitude : A ,

o La fréquence : f0=^??0 2?? ,

o La phase: ?0.

Dans les procédés de modulation binaire, l'information est transmise à l'aide d'un paramètre qui ne prend que deux valeurs possibles. Dans les procédés de modulation M-aire, l'information est transmise à l'aide d'un symbole qui prend sa valeur parmi M = 2ⁿ réalisations possibles, ce qui permet d'associer à un état de modulation un mot de n éléments binaires. L'ensemble de ces symboles est appelé alphabet et forme une constellation caractéristique pour chaque modulation. Supposons que la source délivre des éléments binaires toutes les Tb secondes, la période symbole est définie par T_s = nTb et le débit binaire s'exprime Db = 1/Tb.

La rapidité de modulation R = 1/T_s= Db / log2M s'exprime en bauds et correspond au nombre de changements d'états par seconde d'un ou de plusieurs paramètres modifiés simultanément. Un changement de phase du signal porteur, une excursion de fréquence ou une variation d'amplitude sont par définition des changements d'états.

Les types de modulation les plus fréquemment rencontrés sont les suivants :

o Modulation par Déplacement d'Amplitude MDA et en anglais ASK (Amplitude Shift Keying ASK) ,

o

Figure I.4 : Constellation de la modulation d'amplitude tout ou rien.

Modulation par Déplacement de Phase MDP et en anglais (Phase Shift Keying PSK);

o Modulation d'Amplitude de deux porteuses en Quadrature MAQ et en anglais (Quadrature Amplitude modulation QAM) ;

o Modulation par Déplacement de Fréquence MDF et en anglais (Frequency Shift Keying FSK).

? Modulation par déplacement d'amplitude (MDA)

Consiste à faire varier l'amplitude du signal selon la loi de transcodage associée. Celui-ci s'exprime alors:

S(t) = A(t) cos (co0t + 4) ) avec A(t) = ?k akh(t - kT??) I.2

Où h(t) est un filtre de mise en forme des impulsions, par exemple une porte (h(t) = 1 si t E[0,

T_s[ et 0 ailleurs), 4) est une phase de référence et {ak} la suite des symboles M-aires. Ce type de modulation est simple à réaliser mais est assez peu employé pour M > 2 car ses performances sont moins bonnes que celles d'autres modulations, notamment en ce qui concerne sa résistance au bruit.

? Exemple de modulation par déplacement d'amplitude (MDA)

Un exemple de modulation d'amplitude est la modulation binaire Tout Ou Rien (TOR) encore appelée par son abréviation anglaise : OOK pour "On Off Keying".

Dans ce cas, un seul bit est transmis par période T, et par conséquent n=1 et M=2. Le symbole ak prend sa valeur dans l'alphabet (0, a0). La constellation de la modulation d'amplitude « tout ou rien » est représentée sur la figure I.4.

? Les performances de la MDA

Le spectre du signal modulé est décalé de #177;f0 et comporte donc un raie aux fréquences #177;f0.

Pour pouvoir comparer les différentes modulations entre elles, il est d'usage d'exprimer la probabilité d'erreur en fonction du rapport _Eb/N0 où Eb représente l'énergie émise par bit, et N0 représente la densité spectrale de puissance de bruit.

En fonction de ce rapport on trouve [7] que la probabilité d'erreur par symbole est donnée par la relation :

M-1 [\1^31°g MEbPs(e)= _M erfc2 _M2-1.N ] I.3

0

Cette probabilité d'erreur par symbole P_s(e) est tracée en fonction de ^No et de paramètre M à la

figure I.5.

Figure I.5 : Probabilité d'erreur par symbole de la MDA.

? Modulation à déplacement de phase (MDP)

Le seul paramètre susceptible de varier est la phase de l'onde porteuse [8]. A la sortie du modulateur, le signal s'exprime:

S(t) = AEk h(t - kT_s)cos[_==(ku0t + 4k) I.4

Comme nous l'avions fait pour les MDA, il est possible de comparer les MDP entre elles, en utilisant la probabilité d'erreur par symbole Pe en fonction du rapport Eb/N0. Rappelons que Eb

Où A représente l'amplitude constante de l'onde porteuse et ???? la valeur de la phase pendant un intervalle de temps [kT_s, (k + 1)T_s[. Pour une modulation MDP-M, ???? prend ses valeurs dans un alphabet de M éléments:

???? = ?? + (2?? + 1) ?? ?? , n = 0,1,....,M-1 I.5

La complexité de l'ensemble émission/réception de la MDP augmente avec M, mais reste raisonnable, ce qui en fait une modulation fréquemment utilisée pour M allant de 2 à 16 avec de bonnes performances.

Dans les inconvénients de la MDP, citons l'existence de sauts de phase importants qui font apparaître des discontinuités d'amplitude. Les modulations décalées ou tournées peuvent être une solution à ce problème. La figure I.6 montre différentes constellations de MDP pour M= 2, 4 et 8.

Figure I.6 : Constellation des symboles en modulation de phase MDP-M pour M=2,4 et 8.

? Les performances de la MDP

L'augmentation de M réduit la distance entre symboles adjacents sur la constellation et cela dégrade naturellement les performances.

représente l'énergie émise par bit, et N0 représente la densité spectrale de puissance de bruit. En fonction de ce rapport, on trouve en bibliographie [7] que la probabilité d'erreur par symbole est donnée par la relation :

P_s(e)= erfc [ M. ?????0 ? sin ?? M ] I.6

Cette probabilité d'erreur par symbole Ps(e) est tracée à la figure I.7 pour M allant de 2 à 32 en fonction de Eb /N0 et on constate que pour conserver une probabilité d'erreur par symbole constante lorsque M augmente, il faut aussi augmenter le rapport Eb /N0. Autrement dit, il faut augmenter l'énergie émise par bit Eb. Pour M = 8, le rapport Eb /N0 nécessaire à une probabilité d'erreur donnée est 4 dB plus grand que pour M =4. Pour M grand, le rapport _Eb/N0 doit être augmenté de 6 dB chaque fois que l'on double M c'est-à-dire chaque fois que l'on ajoute un bit par symbole émis.

Figure I.7 : probabilité d'erreur par symbole de la MDP

? 1.3.2 Modulation d'amplitude en quadrature (MAQ)

Les modulations précédentes ne constituent pas une solution satisfaisante pour utiliser efficacement l'énergie émise lorsque le nombre de points M est grand [9]. En effet, dans la MDA les points de la constellation sont sur une droite, et dans la MDP les points sont sur un cercle. Or, la probabilité d'erreur est fonction de la distance minimale entre les points de la constellation, et la meilleure modulation est celle qui maximise cette distance pour une puissance moyenne donnée. Un choix plus rationnel est alors une modulation qui répartit les points uniformément dans le plan.

Pour ce faire, on écrit le signal modulé s(t) sous la forme suivante:

s(t) = a(t) cos(aa0t + 00) - b(t) sin(aa0t + 00) I.7

Où les deux signaux a(t) et b(t) ont pour expression :

a(t) =Ek akh(t - kT) et b(t) =Ek bkh(t - kT) I.8

Le signal modulé s(t) est donc la somme de deux porteuses en quadrature, modulées en amplitude par les deux signaux a(t) et b(t).

On considère généralement que les symboles ak et bk prennent respectivement leurs valeurs dans le même alphabet à M éléments donnant ainsi naissance à une modulation possédant E = M² états. Chaque état est donc représenté par un couple (ak, bk) ou ce qui revient au même par un symbole complexe ck = ak +jbk. Dans le cas particulier mais très fréquent où M peut s'écrire M = 2ⁿ, alors les ak représentent un mot de n bits et les bk représentent aussi un mot de n bits. Le symbole complexe ck = ak + jbk peut par conséquent représenter un mot de 2n bits. L'intérêt de cette configuration est que le signal s(t) est alors obtenu par une combinaison de deux porteuses en quadrature modulées en amplitude par des symboles ak et bk indépendants. Cette modulation prend naturellement le nom de modulation d'amplitude en quadrature (MAQ) et si sa constellation comporte E états, on la note MAQ-E.

Par exemple, la MAQ-16 est construite à partir de symboles ak et bk qui prennent leurs valeurs dans l'alphabet {#177;d, #177;3d} où d est une constante donnée. Une représentation de la constellation de cette modulation est donnée figure I.8 ainsi que celle de la constellation de la MAQ-64.

? Comment sont vérifiées les autres contraintes (puissance hors bande, etc.).

Figure I.8 : Constellations de la MAQ-16 et MAQ-64.

Nous avons vu différentes modulations qui peuvent être utilisées dans un système de transmission numérique.

Un élément supplémentaire apparait après la modulation est le filtrage. Il représente soit une caractéristique passe-bas pour un signal en bande de base, soit une caractéristique passe-bande pour un signal modulé. Le filtrage assure la mise en forme définitive du signal avant l'émission, compte tenu du codage ou de la modulation utilisée et des contraintes du canal.

La mise en forme à la fois spectrale et temporelle peut être effectuée sur le signal modulé, mais aussi sur le signal en bande de base, c'est à dire sur le signal issu du codeur binaire à signal. A ce propos, remarquons que les frontières qui séparent les différentes fonctions de l'émetteur sont parfois difficiles à définir.

Pour en terminer avec cette partie consacrée à l'émission, examinons la question de l'adaptation du signal aux conditions de transmission. Comment savoir si le signal émis est bien adapté si ce n'est en regardant simultanément :

? La qualité du message reçu, c'est à dire le Taux d'Erreur Binaire (TEB) ou le rapport signal à

bruit ( S/N ) ;

Figure I.9 : Canal de transmission numérique.

Cela montre que la mise au point de l'émetteur ne peut se faire indépendamment de celle du récepteur. La définition des chaines de transmission idéale conduira à des conditions qui portent à la fois sur l'émetteur et sur le récepteur, notamment sur leurs fonctions de filtrage.

Le filtrage y apparaitra comme une fonction essentielle qui devra répondre au double but :

o assurer le minimum de distorsion au signal qui sera traité par le récepteur ;

o limiter l'occupation des fréquences à la seule bande permise.

I.2.5. Canal de transmission numérique

Le propre d'une transmission étant de se faire à distance, il faut utiliser un milieu physique qui assure le lien entre la source et le destinataire et un signal approprié au milieu choisi en ce sens qu'il s'y propage bien. Citons par exemple un signal électrique dans un milieu conducteur ou un signal électromagnétique en espace libre.

La notion du canal de transmission [10] est délicate à expliciter. Selon le contexte, le terme de canal de transmission a des significations différentes. Le canal de transmission au sens de la propagation est la portion du milieu physique utilisé pour la transmission particulière étudiée.

Le canal de transmission au sens de la théorie de l'information inclut le milieu physique de propagation et également des organes d'émission et de réception montrés à la figure I.9.

Emetteur

---

Milieu de transmission

--

Récepteur

Canal

? Modèles des canaux de transmission

? Canal binaire symétrique

Le Canal Binaire Symétrique (CBS) est un canal discret dont les alphabets d'entrée et de sortie sont finis et égaux à {0,1}. On considère dans ce cas que le canal comprend tous les éléments de la chaîne compris entre le codeur de canal et le décodeur correspondant à la figure I.10.

modulateur ---

démodulateur

--

Codeur

Décodeur

Milieu de
transmission

Canal à entrée et sortie discrète

Figure I.10 : Description d'un canal binaire symétrique.

On note respectivement ak et yk les éléments à l'entrée et à la sortie du canal binaire symétrique CBS. Si le bruit et autres perturbations causent des erreurs statistiquement indépendantes dans la séquence binaire transmise avec une probabilité p, alors [11] :

Pr (yk = 0ak = 1) = Pr (yk = 1ak = 0) = p I.9

Pr (yk = 1ak = 1) = Pr (yk = 0ak = 0) = 1-p I.10

Le fonctionnement du CBS est résumé sous forme de diagramme sur la figure I.11.

Chaque élément binaire à la sortie du canal ne dépend que de l'élément binaire entrant correspondant, alors le canal est dit sans mémoire.

Figure I.11 : Diagramme du canal binaire symétrique.

? Canal à bruit additif blanc gaussien

Le modèle de canal le plus fréquemment utilisé pour la simulation de transmissions numériques [9], qui est aussi un des plus faciles à générer et à analyser, est le canal à Bruit Blanc Additif Gaussien (BBAG). Ce bruit modélise à la fois les bruits d'origine interne (bruit thermique dû aux imperfections des équipements...) et le bruit d'origine externe (bruit d'antenne...). Ce modèle est toutefois plutôt associé à une transmission filaire, puisqu'il représente une transmission quasi-parfaite de l'émetteur au récepteur. Le signal reçu s'écrit alors:

r (t) = s(t) + b(t) I.10

Où b(t) représente le Bruit Blanc Additif Gaussien BBAG, caractérisé par un processus aléatoire gaussien de moyenne nulle, de variance ób²et de densité spectrale de puissance bilatérale Öbb = N0 /2. La densité de probabilité conditionnelle de r (t) est donnée par l'expression:

(r_s)²

1 _₂

p(r\s) =

2??a_??

e 2a ?? I.11

I.2.6. Le récepteur

Nous venons de voir que l'émetteur permet de transcrire le message en un signal afin de le transmettre sur le canal. Inversement, le récepteur doit extraire le message du signal reçu. Pour cela, il procède soit de manière séquentielle en prenant une suite de décisions sur les symboles successifs du message émis dans le cas numérique, soit par simple démodulation dans le cas analogique.

Le travail du récepteur est complexe en raison de la différence entre le signal émis et le signal reçu. Un bon fonctionnement du récepteur est lié à l'exploitation des connaissances à priori de la structure du signal émis, mais également aux conditions dans lesquelles s'est déroulée la transmission.

Le récepteur qui a pour fonction de reconstituer le message émis par la source à partir du signal reçu, comprend des circuits d'amplification, de changement de fréquence, de démodulation (pour les transmissions sur onde porteuse), de filtrage puis d'échantillonnage et de prise de décision [10]. Le changement de fréquence et le démodulateur permettent de ramener le signal modulé en bande de base. Le signal en bande de base est ensuit filtré puis échantillonné à des instants caractéristiques. Finalement un circuit de décision identifie la valeur des éléments binaires transmis à partir des échantillons reçus.

I.3. Conclusion

L'information transmise entre une source et un destinataire est toujours menaçante par des parasites, des perturbations et des erreurs de transmission situant le long du milieu de transmission.

Alors une théorie de détection et de correction de ces erreurs de transmission est produite par des chercheurs pour répondre à ces problèmes.

Chapitre II :

Les codes correcteurs d'erreurs

II.1. Introduction

La communication à distance (téléphone, télévision, satellite, etc.) entre machines et usagers nécessite des lignes de transmission acheminant l'information sans la modifier. Les lignes utilisées sont en général loin d'être parfaites. Alors le problème majeur de la transmission des données est l'augmentation du débit de transmission, qui peut être réglée par les méthodes de compression, et les erreurs introduites par les supports de transmission. Et tout ceci entraine une information reçue et erronée. Pour cela, l'information devra être codée d'une manière spéciale permettant de déceler les erreurs, ou ce qui est encore mieux de les corriger automatiquement. On a été amené à concevoir la théorie des codes correcteurs et détecteurs d'erreurs.

La théorie des codes correcteurs d'erreurs à été introduite dans les années 40s par les travaux de GOLAY, HAMMING et SHANNON. Cette théorie à été développée pour répondre à un besoin et aux problèmes cités auparavant (transmission des données sur un canal de transmission bruité, compression des données...) et trouve de nos jours de nombreuses applications.

Les codes correcteurs d'erreurs sont un outil visant à améliorer la fiabilité des transmissions sur un canal bruité. La méthode qu'ils utilisent consiste à envoyer sur le canal plus de données que la quantité d'information à transmettre. Une redondance est ainsi introduite. Si cette redondance est structurée de manière exploitable, il est alors possible de corriger d'éventuelles erreurs introduites pour le canal. On peut alors malgré le bruit retrouver la quasi-intégralité des informations transmises au départ.

Dans ce mémoire nous regroupons les codes selon deux classes:

? La première est les codes convolutifs, qui forment une classe souple et efficace de codes correcteurs d'erreurs;

? La deuxième famille est la famille des codes en blocs. Dans ces derniers, l'information est d'abord coupée en blocs de taille constante et chaque bloc est transmis indépendamment des autres avec une redondance qui lui est propre. La plus grande sous famille de ces codes rassemble ce que l'on appelle les codes linéaires qui constitue les codes cycliques, les codes de HAMMING, les codes BCH [12], les codes de Reed Solomon, les codes de GOLAY etc....

II.2. Les codes convolutifs

Les codes convolutifs ont été introduits en 1955 par P. Elias [13] comme une alternative aux codes en blocs. Sans algorithme effectif de décodage, celle-ci est restée longtemps sans application pratique. En 1959, les codes convolutifs sont remis au bout du jour par D.W. Hagelbarger [14] sous le nom de codes récurrents. L'intérêt naissant de la communauté pour ces codes a permis, dès 1961, aux premiers algorithmes de décodage de voir le jour. Les performances de ce nouveau type de code correcteur d'erreurs dépassent de loin celles des codes classiques, notamment celles de codes en blocs. Les algorithmes de décodage séquentiel, de décodage à seuil, mais surtout l'algorithme de Viterbi [15] ont rendu les codes convolutifs populaires et répandus.

Ceux-ci sont particulièrement adaptés aux communications spatiales ; ils occupent alors une place privilégiée dans la grande histoire de l'aventure spatiale. En effet, la NASA adopte comme standard le code découvert par J.P. Odenwalder [16] en 1970. Ce même code est utilisé par la navette Voyager pour coder les photos de Jupiter, Saturne, Uranus et Neptune, au début des années 80.

Les codes convolutifs traitent l'information non plus par morceaux mais par flux. Ils sont souvent traités comme des blocs linéaires en flux sur des corps finis. Nous nous limiterons ici aux cas binaire (le corps à 2 éléments).

II.2.1. Présentation des codes convolutifs (ou récurrents)

Un code convolutif transforme des mots de k éléments binaires en mots de n éléments binaires (n > k) selon le schéma de la figure II.1. Le codeur est constitué de k registres à décalage en parallèle et d'un circuit combinatoire. Pour chaque mot de k éléments binaires en entrée, les registres sont décalés vers la droite et le mot est inséré à gauche, dans la première colonne. Les (m + 1)k éléments binaires contenus dans les registres sont alors combinés selon des opérations logiques pour former un mot de n éléments binaires en sortie.

La différence avec les codeurs en bloc est que chaque mot en sortie dépend non seulement de l'entrée courante, mais aussi des entrées précédentes, les registres créant un effet de mémoire de profondeur m [17]. La longueur m + 1 des registres est appelée longueur de contrainte du code. On note un tel code C (n, k, m + 1).

Figure II.1 : Schéma de principe d'un codeur convolutif.

Pour illustrer ce dernier, on prend comme exemple un codeur (2, 1, 3). Le circuit d'un code C (2, 1, 3) est représenté sur la figure II.2. Ce codeur code des mots de 1 élément binaire en mots de 2 éléments binaires (il a donc un rendement R = 1/2). A chaque instant t se trouvent dans le registre le

dernier élément binaire m(t) ainsi que les deux précédents m(t - Tb) et m(t - 2Tb), Tb désignant le
temps bit. La sortie c(t) = [c1(t) c2(t)] correspondant à l'entrée m(t) vaut :

c1(t) = m(t) + m(t - Tb) + m(t - 2Tb) II.1

c2(t) = m(t) + m(t - 2Tb) II.2

Les additions étant modulo 2 (ou exclusif (1+1=0)).

Figure II.2 : Circuit d'un codeur convolutif C (2, 1, 3).

Ou 2 est le nombre de sorties, 1 est le nombre d'entrées et 3 le nombre des registres. II.2.2. Représentations des codeurs convolutifs

Pour analyser les codes convolutifs, on représente graphiquement le fonctionnement du codeur. L'étude du codage convolutif peut être faite par un diagramme arborescent [18] qui devient vite impraticable dès que la séquence à coder dépasse quelques bits, puisque la dimension de l'arbre double à chaque étage.

Aussi, elle peut être représentée à l'aide d'un diagramme d'état ou le diagramme en treillis. On suppose que les registres des codeurs sont initialisés à zéro.

? Diagramme d'état

La sortie du codeur dépend de l'entrée et du contenu des registres et chaque nouvelle entrée produit un décalage des registres et une sortie. On peut donc considérer un codeur convolutif comme une machine à états telle que :

o les états sont définis par les k × m éléments binaires les plus à gauche avant le décalage ;

o les transitions entre états sont provoquées par l'arrivée d'un mot de k éléments binaires en entrée.

Dans l'exemple précédent C (2, 1, 3), 4 états sont possibles, définis par les 2 éléments binaires les

plus à gauche avant le décalage. Lorsque le codeur est dans un état XY (X et Y ? {0, 1}), le
registre contient XYZ, avec Z ? {0, 1}. L'arrivée d'un élément binaire E en entrée met le codeur dans l'état EX (contenu du registre EXY) et génère une sortie : c = [E +X +Y E +Y]. Le codeur peut ainsi être représenté par le diagramme d'état [19] de la figure II.3.

En partant, par convention, d'un état initial 00, ce diagramme donne la sortie associée à toute entrée.

.

Figure II.3 : Diagramme d'état du codeur C (2, 1, 3).

? Diagramme en treillis

Le diagramme en treillis [11] représente toutes les évolutions possibles au cours du temps de l'état du codeur, avec les sorties associées, selon les entrées.

Pour faciliter l'algorithme de décodage, la représentation la plus courante du codage est la représentation en treillis.

L'état du codeur à l'instant k est représenté par l'état {dk-1, dk-2,.....dk-m-1}. A chaque arrivée d'un élément binaire dk, une sortie (un mot de code) est générée, puis juste après le codeur passe dans l'état

suivant qui est {dk, dk-1, dk-m}.

Le treillis est formé de noeuds reliés par des branches : les noeuds représentent les différents états du codeur possibles : il y en a 2^m-1 s'il y a une entrée ^2(m-1)k s'il y a k entrées, les branches représentent les différentes transitions possibles d'un noeud à un autre (ou d'un état du codeur au suivant) lors de l'arrivée d'un bit d'entrée.

Voici le treillis de la figure II.4 : les états sont 00, 01, 10,11. Partant, par exemple de l'état 00, l'arrivée d'un 0 mène le codeur à l'état 00 (transition en pointillé pour l'arrivée d'un 0) et l'arrivée d'un 1 mène le codeur à l'état 10 (transition en trait plein pour l'arrivée d'un 1). A chaque branche on peut associer le mot codé soit les 2 bits de code sur la figure II.4.

Figure II.4 : Exemple de treillis.

Alors la figure II.5 représente un tel diagramme pour le codeur C (2, 1, 3) précédent.

Le diagramme en treillis peut être vu comme un déroulement du diagramme d'état sur une échelle temporelle, en partant de l'état 00 à l'instant initial. A partir d'un certain moment, le treillis consiste en la répétition d'un motif, témoin de la structure cyclique du diagramme d'état.

Figure II.5 : Diagramme en treillis du codeur C (2, 1, 3).

II.2.3. Décodage des codes convolutifs

En pratique, il est possible de tirer un meilleur parti des possibilités de détection et de correction des codes convolutifs en faisant appel à des méthodes probabilistes [19], dont la plus connue est l'algorithme de Viterbi, qui est un algorithme de décodage au maximum de vraisemblance sur tout canal sans mémoire.

? Pricipe de l'algorithme de viterbi

L'algorithme de viterbi [15] permet à partir de n'importe quelle séquence binaire (tronquée) de déterminer la séquence d'information produisant la séquence codée qui lui est la plus probable. Cette propriété d'optimalité est vraie même lorsque la séquence fournie au codeur est accompagnée d'une information de fiabilité (décodage souple). En particulier, pour le décodage d'un code convolutif poinçonné, les symboles décimés sont réintroduits dans le décodeur, avec une valeur quelconque et une fiabilité nulle. Le décodeur prendra automatiquement en compte, et de façon optimale, cette information.

La complexité par bit d'information du décodeur de Viterbi est proportionnelle à 2k+m. Ce caractère exponentiel est la raison principale pour laquelle les codes retenus pour les applications ont

souvent une seule entrée (k=1) et une longueur de contrainte faible (m < 10).

L'algorithme de décodage de Viterbi consiste à trouver le chemin minimum dans un treillis de codage (graphe orienté sans cycle).

II.3. Les codes en blocs linéaires

II.3.1. Définition générale d'un code en bloc

Le message à transmettre est découpé en blocs de k bits, qui sont alors traités séparément par le

codeur.

On appelle code un ensemble C de 2^k n-uplets de bits, avec n > k, dont les éléments sont appelés mots [20]. Les blocs à transmettre sont traduits en des éléments du code, chacun des 2^k messages différents possibles correspondant de manière unique à un des mots du code.

On appelle distance de Hamming entre deux mots du code le nombre de composantes par lesquelles ils diffèrent. La distance minimale d'un code C, notée d, est alors la distance de Hamming minimale entre deux mots quelconques.

Un code est alors défini par les trois paramètres (n, k, d), où n est la taille du code, k sa dimension et d sa distance minimale.

II.3.2. Définition d'un code linéaire

La plupart des codes connus appartiennent à une classe de codes appelés codes linéaires [21]. Cette classe est définie par une forte contrainte sur la structure du code. La structure imposée nous aide dans la recherche des bons codes et permet de faciliter la réalisation du codeur et du décodeur. Les codes les plus puissants ne sont pas nécessairement linéaires, mais peu de méthodes existent pour rechercher les bons codes non linéaires.

Le nombre des mots du code C est 2^k. On regroupe les trois paramètres n, k, et d d'un code linéaire C en disant que C est de type (n, k, d).

? Propriétés des codes linéaires

Définition 1

La distance de Hamming entre 2 mots est égale aux nombres de symboles qui diffèrent.

Des solutions existent pour les codes Reed-Solomon Généralisés (RSG) pour les codes cycliques dans certains cas favorables, mais pas, par exemple, pour les codes de Goppa ou les codes géométriques.

Définition 2

Le poids de Hamming d'un mot est égal aux nombres de symboles égaux à 1.

Définition 3

La distance minimale d'un code C est le minimum entre 2 mots de code x et y. On notera cette distance d(x, y) et on suppose que x et y sont des mots différents de C (on suppose que C a au moins deux mots).

dmin = min{d (x, y)} II.3

II.3.3. Généralités du décodage

Plusieurs méthodes de décodage existent. Le décodage du maximum de vraisemblance est la méthode la plus souhaitable mais n'est pas toujours réalisable en pratique, sauf pour les codes convolutifs. Elle consiste, à partir d'un modèle probabiliste du canal, à calculer le mot le plus probable compatible avec le mot reçu. Il est facile de montrer que le décodage utilisant le maximum de vraisemblance consiste à retrouver le mot de code le plus proche (au sens de Hamming) du mot reçu.

Le décodage en revanche va utiliser la structure algébrique du code ou de son dual. La connaissance de la seule matrice génératrice ne suffit en général pas à décoder de manière efficace, et la structure algébrique n'est pas nécessairement facile à obtenir à partir de la matrice génératrice (c'est même l'un des fondements de la sécurité de certains crypto systèmes tels que celui de McEliece) [22].

Le décodage d'un code en bloc est un problème difficile. On ne connait pas d'autre algorithme pour décoder les codes linéaires, que des techniques au coût exponentiel dans le nombre d'erreurs corrigées par bloc.

Pour de petits codes en blocs binaires, ce coût n'est pas un problème et les solutions donnent des résultats satisfaisants. Dans les autres cas, la connaissance du code (par exemple par la donnée d'une matrice génératrice) sera insuffisante et il faudra retrouver la structure algébrique.

II.3.4. Génération du mot de code

? Matrice de génération de code

C'est une matrice notée G [21], elle sert à générer le mot de code C_m à partir du message X_m soit :

C_m=X_m.G II.4

Nous nous intéressons à des codes systématiques, la matrice G est donc de la forme :

G=[P Ik] II.5

G est une matrice (k, n), P une matrice (k, n-k) et Ik la matrice identité (k, k).

? Principe de réalisation du codeur

Chaque bit de parité s'exprime donc par [21] :

bi = .m1 p1

?? II.6
1=1

En binaire les _Pji E {0, 1} et les bi sont obtenus par une simple addition binaire.

Le principe de la réalisation technique en est donc simple, il suffit de disposer de deux registres à décalage et un inverseur (switch électronique) ce qui donne la figure II.6 :

Figure II.6 : Principe de réalisation du codeur

II.3.5. Détection des erreurs de transmission

Pour détecter les erreurs de transmission, on doit tenir compte de deux facteurs qui sont les suivants [21] :

? Matrice de contrôle de parité

Nous définissons un espace dual engendré par la matrice H tel que :

H = [In-k PT] II.7

En décomposant les matrices nous obtenons :

G.HT = [P Ik] IIIn_k

?? ] = P + P = 0 II.8

En effet, P est constitué d'éléments binaires tels que : a + a = 0.

D'où la relation fondamentale :

G.HT = 0 II.9

? Syndrome :

On appelle syndrome le vecteur s de dimension M défini par :

ST = Hx^T II.10

Si S est un vecteur nul alors x est un mot de code, sinon le vecteur x contient des bits erronés. Il est possible de détecter la présence d'erreurs dans un mot de code par le calcul du syndrome.

Nous pouvons établir la relation servant de base à la détection d'erreurs pour tout mot de code:

G_m.H^T = X_m.G.H^T = 0 II.11

Le détecteur va utiliser cette relation. En effet, si le mot du code reçu Y_m est entaché d'erreurs, nous pouvons l'exprimer sous la forme :

Code reçu = code émis + erreur Y_m = C_m + E_m II.12

En effectuant le contrôle :

Y_m.H^T = C_m.H^T + Em. H^T = Em. H^T II.13

(v0, v1, ..., vn-1) ? C (vn-1, ^v0,..., vn-2) ? C

S'il n'y a pas eu des erreurs de transmission, alors on a :

Em. H^T = 0 II.14

Em. H^T est par définition le syndrome de l'erreur S_m , avec :

S_m = Y_m. Em. H^T = Em. H^T II.15

Le syndrome ne dépend que de l'erreur de transmission commise et non du mot du code.

II.3.6. Famille des codes en blocs

Nous donnons ci-dessous une liste non exhaustive de familles de code en bloc linéaires. Les codes que nous considérons sont binaires ou sont définis sur une extension du corps à deux éléments. Nous noterons (n, k, d) un code linéaire défini sur un alphabet à q éléments de longueur n, de dimension k et de distance minimale d.

Nous avons choisi de ne lister ici que des familles de codes ayant un intérêt pratique (s'ils sont utilisés, typiquement Reed-Solomon ou BCH, ou susceptibles de l'être comme les codes géométriques) ou théorique [12].

? Les codes cycliques

Les codes cycliques forment une sous-classe des codes linéaires, et sont les plus utilisés en pratique [23]. Ils conjuguent en effet de nombreux avantages : leur mises-en oeuvre (codage/décodage) est facile, ils offrent une gamme étendue de codes, avec de nombreux choix de paramètres (n, k, d), et enfin permettent de corriger différents types d'erreurs, isolées ou par paquets.

Les codes cycliques sont des codes linéaires stables par permutation circulaire des coordonnées. Ils ont une forte structure mathématique : si on les voit comme des espaces vectoriels de polynômes (les coordonnées des mots deviennent les coefficients des polynômes). Un code linéaire C est dit cyclique s'il est stable par permutation circulaire des coordonnées. Donc, on peut écrire :

Si l'on représente le vecteur ci-dessus par le polynôme v(x) = v0 + v1x +.... + _vn-1xn-1, alors la permutation circulaire d'une unité à droite correspond à la multiplication par x modulo xⁿ-1.

? Codes de Hamming :

Ce code est lui aussi très simple mais a un bien meilleur taux de transmission. Pour le définir il est nécessaire d'introduire la notion de matrice de parité :

C'est une matrice H de taille (n - k) X n qui a pour noyau le code C tout entier. Ainsi si c ? C, on aura toujours Hc^T = 0, et uniquement dans ce cas là. Remarquons qu'un même code C peut avoir plusieurs matrices de parité différentes, de même qu'il peut avoir plusieurs matrices génératrices différentes.

On appellera syndrome d'un mot c l'élément S obtenu en calculant S = Hc.

Le code de Hamming est donc un code binaire défini par sa matrice de parité plutôt que par sa matrice génératrice [24]. C'est la matrice de dimension r X (2^r -1) qui contient toutes les colonnes non nulles distinctes que l'on peut écrire sur r bits. Ainsi pour r = 3 on a :

? Les codes BCH (Bose-Chaudhuri-Hocquenghem)

Les codes BCH (Bose-Chaudhuri-Hocquenghem) binaires sont des codes cycliques particuliers. La famille des codes BCH contient les codes de Reed-Solomon qui servent pour la lecture des CD [25]. Lorsque le cardinal de l'alphabet sur lequel un code de Reed-Solomon est défini est une puissance de 2, alors il est possible de définir son sous-code binaire (les mots de code ayant des coefficients 0 ou 1).

Ce sous-code est stable par addition (la somme de deux mots binaires est un mot binaire) et donc linéaire. Un code de Reed-Solomon (n, k, d) avec q = 2m fournira un code BCH binaire (n, kÇ d'), avec k' est la nouvelle dimension et d' est la nouvelle distance du code BCH obtenu à partir du code de Reed-Solomon. La longueur est conservée, en revanche la distance minimale peut augmenter, et la dimension diminue fortement. Les valeurs exactes de d' et k' sont dépendantes de la structure du corps fini et ne peuvent être décrites par des formules closes simples.

Si g(x) est le polynôme générateur du code Reed-Solomon, alors, le code BCH aura pour générateur le polynôme binaire de plus bas degré multiple de g(x). Le décodage d'un code BCH sera très similaire au décodage du code de Reed-Solomon dont il est issu.

? Les codes de Reed-Solomon

Les codes de Reed-Solomon ont été développés par Reed et Solomon dans les années 50 [26] mais avaient déjà été construits par Bush [27] un peu avant, dans un autre contexte. Ces codes sont certainement les codes par blocs les plus utilisés pour la correction d?erreurs en étant présents dans les CD, les DVD et la plupart des supports de données numériques. Ils sont trés utilisés car ils sont extrêmaux du point de vue de la capacité de correction.

Les codes de Reed-Solomon sont des codes cycliques q-aires de longueur n = q -1. Le polynôme générateur d'un code de Reed-Solomon est de la forme :

g (x )= fl(x - a^??)

??-1 II.16
??=1

Où a est un élément primitif du corps fini à q éléments. Il a pour degré d-1. Le code correspondant au polynôme générateur ci-dessus a pour longueur n = q-1, pour distance minimale d et

pour dimension k = n - d + 1. Nous avons donc affaire à des codes (n, k, n - k + 1).

Ces codes sont efficaces dans la correction d'erreurs par paquet du fait de leur structure. Ils ont été employés dans les communications spatiales et restent encore utilisées dans les codes concaténés.

II.4. Conclusion

Pour différents types de codes, le rapport signal à bruit nécessaire pour atteindre une probabilité d'erreur inférieure à 10^-5 est de 4.5 dB pour les codes convolutifs, il est de 5.4 dB pour les codes BCH et Reed-Solomon, et est de valeurs inférieures à 1 dB pour les codes turbo et 0.005 dB pour les codes LDPC.

Les codes LDPC font partie de la classe des codes blocs linéaires et s'approchent davantage de la limite de Shannon (capacité d'un canal). Ce sont les codes que nous allons étudier en détail dans ce mémoire. Leurs performances peuvent dépasser les performances des autres types de codes présentés, même des codes turbo.

Chapitre III :

Les codes LDPC réguliers

Et résultats de simulation

Un code LDPC est un code dont la matrice de contrôle de parité H est de faible densité (matrice creuse). La faible densité signifie qu?il y a plus de « 0 » que de « 1 » dans la matrice H [31]. Un code

III.1. Introduction

Les codes LDPC ont été découverts par Gallager [28], dans les années 60, 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'en 1981 quand Tanner leur a donné une nouvelle interprétation d'un point de vue graphique [29]. Sa théorie a été aussi ignorée pour les prochaines 14 années jusqu'au jour où quelques chercheurs en codage ont commencé à étudier les codes en graphes et le décodage itératif.

La première construction algébrique et systématique de codes LDPC basée sur les géométries finies a été proposée par Kou, Lin et Fossorier dans les années 2000 [30]. La classe de codes LDPC à géométrie finie possède une bonne distance minimale et les graphes de Tanner n'ont pas de cycles courts. Leur structure est cyclique ou quasi-cyclique, ce qui fait que leur codage est simple et peut être réalisé avec des registres à décalage linéaire. Avec ce type de codes de grande longueur, on obtient de très bonnes performances d'erreurs.

La construction et le décodage des codes LDPC peuvent être fait de plusieurs manières. Un code LDPC est caractérisé par sa matrice de parité.

III.2. Définition des codes LDPC

Un code LDPC régulier est défini comme l'espace nul d'une matrice de contrôle de parité H [28], qui a les propriétés suivantes :

(1) chaque ligne à p valeurs de 1 ;

(2) chaque colonne à y valeurs de 1 ;

(3) le nombre de 1 en commun entre deux colonnes quelconques, désigné parA, n'est pas plus grand que 1 (donc A = 0 ou A = 1) ;

(4) p et y ont des valeurs petites en comparaison avec la longueur du code et avec le nombre de lignes de la matrice H.

L'irrégularité de ces codes se spécifie à travers deux polynômes A(x) et p (x):

LDPC peut être représenté sous forme matricielle ou bien sous la forme d'un graphe bipartite (représentation de Tanner). Par exemple, la matrice suivante :

H =	1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 1

Figure III.1 : Graphe bipartite d'un code LDPC.

Si toutes les colonnes ou toutes les lignes de H n'ont pas le même poids, le code LDPC s'appelle code LDPC irrégulier.

La matrice peut être représentée par le graphe de la figure III.1. Les lignes de la matrice sont représentées par des carrés et sont appelées noeuds de contrôle, les colonnes de la matrice sont représentées par des cercles et sont appelées noeuds de données et les « 1 » représentent les arrêtes du graphe.

Il y a deux familles de codes LDPC : les codes réguliers ou quasi-cycliques qui feront l'objet de notre étude et les codes irréguliers. Les codes LDPC réguliers sont les codes dont le nombre de « 1 » par ligne et le nombre de « 1 » par colonne sont constants. Par extension, les codes LDPC irréguliers sont les codes définis par des matrices de contrôle de parité où le nombre de « 1 » par ligne ou par colonne n'est pas constant.

?? ?? = ??????^??-1

??=2 III.1

?? ?? = ??????^??-1 III.2

??=2

III.3. Les graphes de Tanner pour les codes LDPC

Les graphes de Tanner [29] sont très utiles pour la représentation des codes en blocs linéaires, parce qu'ils affichent la relation entre les bits des mots-codes et les noeuds de contrôle de parité. Ils ont été proposés pour la première fois par Tanner pour le décodage itératif des codes LDPC. Les codes LDPC sont représentés sous forme de graphes bipartites. Un graphe est bipartite si son ensemble de noeuds (í) peut être divisé en deux sous-ensembles disjoints í, í1 et í2, de façon que chaque arête joint un noeud dans í1 avec un noeud dans í2 et sans que deux noeuds dans í1 ou dans í2 soient connectés. Pour un code LDPC, les deux ensembles de noeuds í1 et í2 représentent les n bits du mot-code (noeuds des variables) et les J équations de contrôle de parité qui doivent être satisfaites par les bits codés (noeuds de contrôle). Toutes les connexions sont faites entre chaque noeud de bit codé et ses noeuds de contrôle correspondants (qu'on vérifie dans la somme de contrôle).

Un chemin dans un graphe est une séquence de noeuds et d'arêtes, qui commence et finit par des noeuds, tel que chaque arête est incidente avec les noeuds qui la précèdent et la suivent et aucun noeud n'apparaît plus d'une fois. La longueur d'un chemin est donnée par le nombre d'arêtes formant le chemin. Un chemin qui commence et finit avec le même noeud s'appelle cycle. Si un graphe bipartite contient des cycles, ces cycles ont des longueurs paires. La longueur du plus court cycle dans le graphe s'appelle le périmètre du graphe.

Pour un code LDPC régulier, les degrés de tous les noeuds de bits codés sont égaux à ?? (le poids de chaque colonne de la matrice H) et les degrés de tous les noeuds de contrôle sont égaux à ?? (le poids de chaque rangée de la matrice H). Ainsi, le graphe de Tanner est régulier. Il ne peut pas y avoir deux bits codés qui peuvent être vérifiés par deux équations différentes, donc le graphe ne va contenir aucun cycle de longueur 4. Pour décoder un graphe d'un code LDPC avec le décodage itératif, il est important que le graphe de Tanner du code ne contienne aucun cycle de courte longueur (4 ou 6, mais en particulier 4), parce que les cycles courts limitent la performance d'erreurs et empêchent le processus de décodage de converger vers la performance obtenue avec le décodage à vraisemblance maximale MLD (Maximum Likelihood Decoding) [32].

Avec un gap g petit si possible. Nous verrons dans la suite comment ceci peut être accompli efficacement ;

III.4. Encodage des codes LDPC

Les travaux de T.J. Richardson et R.L Urbanke [33] ont montré que la matrice de contrôle doit subir un prétraitement avant l'opération d'encodage. L'objectif de ce prétraitement est de mettre la matrice H de taille m × n sous une forme presque triangulaire inférieure, comme illustré sur la Figure III.2, en utilisant uniquement des permutations de lignes ou de colonnes.

Cette matrice est composée de 6 sous-matrices creuses, notées A, B, C, D, E et d'une sous-matrice triangulaire inférieure T de taille m-g × m-g. Une fois que le prétraitement de H est achevé, le principe d'encodage est basé sur la résolution du système représenté par l'équation matricielle suivante :

cH^T = 0 III.3

Figure III.2: Représentation sous forme pseudo-triangulaire inférieure de la matrice H.

L'algorithme de prétraitement est décrit ci-dessous de manière succincte :

1- La triangulation est une permutation des lignes ou des colonnes pour avoir une approximation de la matrice H sous forme triangulaire inférieure :

H = A B T

C D E

2- Le contrôle de rang est l'élimination gaussienne pour effectuer la pré multiplication

par	?? 0 -????^-1 ?? .

Cette pré multiplication permet d'obtenir :

?? 0 ?? ?? ?? ?? ?? ??

-???? -1 ?? ?? ?? ?? = -????^-1?? + ?? - ????^-1?? + ?? 0

Il est nécessaire de vérifier que -ET^-1B+D est inversible pour que le processus de prétraitement soit utilisable pour la résolution de l'équation III.3.

Lors de la résolution de l'équation III.3, le mot de code recherché est décomposé en trois parties : c = (d, r1, r2) où d est la partie systématique (c'est-à-dire un élément de la base canonique du sous espace vectoriel de dimension n-m comme indiqué sur la figure III.2, où les bits de redondances recherchés sont séparés en deux vecteurs r1 et r2 de tailles respectives g et m-g. Après multiplication à droite par la

matrice ?? 0

-????^-1 ?? , l'équation III.3 devient:

?????? + ????1^?? + ????2^??= 0 III.4

-????^-1?? + ?? ???? + -????^-1?? + ?? ??1^?? = 0 III.5

L'équation III.5 permet de trouver ??1^?? en inversant Ö = -????^-1?? + ??. L'équation III.4 permet ensuite de trouver ?????? . Remarquons que la phase de prétraitement est une phase qui nécessite de nombreuses opérations coûteuses en temps de calcul. Par contre, toutes les opérations répétées au cours de l'encodage ont une complexité en o(n) excepté la multiplication de -????^-1?? + ?? ???? par la matrice carrée (-Ö^-1) de taille g x g qui après insertion n'est plus creuse d'où une complexité en o(g²) . T.J. Richardson et R.L Urbanke [33] ont aussi montré que l'on peut obtenir une valeur de g égale à une faible fraction de n : g = ???? où ?? est un coefficient suffisamment faible pour que o(g²) << o(n) pour des valeurs de n allant jusqu'à 10⁵. Ainsi, la complexité de l'approche d'encodage est de complexité O(n).

Ces codes peuvent être raccourcis par élimination des colonnes de la matrice de parité.

III.5. Construction des codes LDPC

III.5.1. Une construction géométrique des codes LDPC

Les codes LDPC peuvent être construits de manière algébrique à partir de points et de lignes de la géométrie finie, comme la géométrie Euclidienne et la géométrie projective définies sur des champs finis [34]. Une géométrie finie est formée de points et lignes, qui ont les propriétés suivantes :

(1) chaque ligne à ?? points ;

(2) chaque point appartient à ?? lignes ;

(3) deux points sont connectés par juste une ligne ;

(4) deux lignes sont soit disjointes, soit leur intersection est un seul point.

Pour chaque type de géométrie, on peut construire des codes LDPC de type 1 (géométrie Euclidienne) et de type 2 (géométrie projective), qui sont vraiment connexes et leurs graphes sont conjugués entre eux : les noeuds des bits codés d'un graphe sont les noeuds de contrôle pour l'autre graphe. Pour le type 1, on peut former une matrice de parité H dont les rangées sont les vecteurs d'incidence des lignes existantes dans la géométrie finie et les colonnes sont les points. Le graphe correspondant à cette matrice n'a aucun cycle de longueur 4. Pour un code LDPC de type 2, la matrice de parité H est la transposée de la matrice correspondante de type 1 : les rangées sont les vecteurs d'incidence des points et les colonnes sont les lignes de la géométrie finie. Les graphes correspondants à ces matrices n'ont aucun cycle de longueur 4.

Les codes EG-LDPC (basés sur la géométrie euclidienne) et les codes PG-LDPC (basés sur la géométrie projective) ont des performances d'erreurs presque identiques [34]. Dans la construction des codes EG-LDPC de type 1 et 2, on peut éliminer le point d'origine de la géométrie et toutes les lignes qui passent par l'origine. Ainsi, on met le code EG-LDPC de type 1 dans une forme cyclique et le code EG-LDPC de type 2 dans une forme quasi-cyclique. Ceci simplifie le circuit de codage ; on doit garder en mémoire juste la première rangée de H et les autres rangées seront ajoutées à l'aide d'un registre à décalage linéaire. La différence entre les 4 types de codes (EG-LDPC et PG-LDPC de type 1 et 2) est comment on trouve les positions des valeurs de < 1 > dans la première rangée de la matrice de parité et les différents paramètres des codes obtenus. Les formules pour calculer ces paramètres sont données en [34].

Pour les codes EG-LDPC de type 1, les colonnes éliminées correspondent aux points d'un ensemble de paquets parallèles qui ne passent pas par l'origine de la géométrie finie. On obtient une nouvelle matrice irrégulière dans laquelle les colonnes ont le même poids, mais les lignes ont des poids inférieurs. Son noyau donne un code LDPC irrégulier plus court avec la même distance minimale que le code initial. Pour les codes EG-LDPC de type 2, il faut mettre la matrice de parité dans une forme circulaire et on élimine les colonnes correspondant à un ensemble de lignes. On obtient un code quasi-cyclique plus court. On doit mentionner que plus on réduit la matrice de parité, plus on obtient une meilleure performance d'erreurs du code.

III.5.2. La construction des codes LDPC de Gallager

Pour construire la matrice de parité H d'un code LDPC de Gallager, il faut d'abord construire une sous-matrice Hj ayant un poids des colonnes égal à 1 et un poids de lignesp. Ensuite, on doit trouver de permutations des colonnes de cette sous-matrice pour former les autres sous-matrices avec lesquelles on forme la matrice de Gallager qui se présente de manière suivante :

H1

H2

H=

. . .

H??

Lorsqu'on choisit les permutations des colonnes des sous-matrices, on doit garder une bonne distance minimale de la matrice de parité H et il faut éviter les cycles courts dans son graphe de Tanner. Gallager ne donne aucune méthode de construction pour ce type de codes.

Si on compare les performances en terme de Taux d'Erreurs Binaire d'un tel code LDPC avec d'autres codes LDPC obtenus par ordinateur, qui ont le même rendement et presque la même longueur, on peut observer que le code EG-LDPC est meilleur.

On ne peut pas construire de codes LDPC dans la forme de Gallager basés sur la géométrie projective, parce que les lignes dans une géométrie projective n'ont pas la même structure parallèle simple que les lignes de la géométrie Euclidienne.

III.5.3. Les codes LDPC aléatoires

On peut construire de codes LDPC pseudo-aléatoires à l'aide de l'ordinateur d'une manière basée sur un ensemble de conditions données par la définition des codes LDPC. Ces codes fournissent de bonnes performances [35]. La construction de la matrice de parité H est faite en plusieurs étapes. On choisit la première colonne de la matrice de manière aléatoire, ayant un certain poids. À chaque étape, une nouvelle colonne de même poids est ajoutée à une matrice formée partiellement. La colonne ajoutée est choisie entre plusieurs colonnes selon les conditions à respecter par la matrice de parité d'un code LDPC [34].

En raison des conditions imposées pendant la construction du code, le graphe de Tanner ne contient pas de cycles d'ordre 4 et alors son périmètre est égal à au moins 6. Cette construction n'est efficace que pour des petites valeurs du poids des colonnes (3 ou 4). Pour des valeurs de poids plus grandes, les ordinateurs n'arrivent pas à effectuer efficacement les calculs (en un temps raisonnable).

Le code construit par cette méthode n'est pas unique parce que les colonnes sont choisies aléatoirement et il y a une multitude de choix possibles. Ainsi, ce type de construction génère un ensemble de codes LDPC aléatoires.

Il est très difficile de déterminer la distance minimale du code et pour de petites valeurs des poids, la limite inférieure pour la distance minimale peut être très petite. Ces codes n'ont pas les mêmes propriétés structurales que les codes de géométrie finie (pas de structure cyclique ou quasi-cyclique). En conséquence, l'implémentation matérielle de ces codes est beaucoup plus complexe et ne peut pas être réalisée avec des registres à décalage linéaires.

Ces codes ne peuvent pas être décodés par le décodage logique majoritaire ou par le décodage avec basculement de bit (BF). Avec le décodage SPA, la solution ne converge pas aussi vite que dans le cas des codes LDPC de géométrie finie.

En termes de performance, ces codes s'approchent beaucoup de la limite de Shannon.

III.5.4. Les codes LDPC quasi-cycliques ou réguliers

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

Cette méthode consiste en la décomposition d'une matrice carrée, régulière et circulaire en plusieurs matrices circulaires de mêmes dimensions, mais avec des poids différents [34]. On obtient ces nouvelles matrices à partir 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é parmi les différentes colonnes. À partir de chaque nouvelle colonne ainsi formée, on forme une matrice circulaire par permutations circulaires successives de la colonne en bas. La méthode présentée s'appelle la décomposition des colonnes d'une matrice de parité.

De même, on peut décomposer la matrice initiale en descendants, 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ée. 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 dont le graphe de Tanner n'a pas de cycles de longueur 4.

Des matrices creuses circulaires peuvent être construites à partir des vecteurs d'incidence des lignes dans une géométrie Euclidienne ou projective. De plus, il n'existe pas deux lignes (ou deux colonnes) dans la même matrice ou dans différentes matrices circulaires ayant plus d'une valeur de 1 en commun. En conséquence, les codes LDPC quasi-cycliques peuvent être construits en décomposant une ou un groupe de ces matrices circulaires géométriques [36].

? Les codes LDPC quasi-cycliques (QC) réguliers pour un codage rapide et pratique

Par rapport aux codes LDPC construits de manière aléatoire, la matrice de parité d'un code QC-LDPC consiste en plusieurs matrices de permutation ou matrices nulles. Ainsi, la mémoire de stockage peut être réduite considérablement (il suffit de mémoriser les premières rangées de chaque sous-matrice : les autres rangées sont formées par permutations circulaires). Cette structure est orientée sur la réalisation d'un décodeur plus efficace. Ce qui est important est que cette nouvelle structure de matrice de code LDPC ne diminue pas les performances du code.

Il a été démontré que le périmètre d'un code QC-LDPC est limité en haut par un certain nombre qui est déterminé par les positions des matrices circulaires de permutations [37]. On peut donc obtenir de bons performances du code en contrôlant la structure des cycles.

Une classe spéciale de codes LDPC quasi-cycliques sont les codes LDPC de type bloc (B-LDPC) qui possèdent un algorithme de codage efficace en raison de la structure simple de leurs matrices de parité. Avec l'implémentation efficace du codeur et du décodeur des codes B-LDPC et leurs bonnes performances représentent un axe très prometteur pour l'implémentation des systèmes de codage LDPC en temps réel. Les codes B-LDPC sont construits comme des codes QC-LDPC irréguliers avec des matrices de parité presque triangulaires inférieures, de sorte qu'ils aient un algorithme de codage efficace, un bon palier de bruit et un plancher d'erreurs bas. Leur complexité ne dépend pas de manière linéaire de la taille des matrices de parité.

Pour la construction des codes B-LDPC, au lieu de faire la multiplication entre la matrice de parité et le vecteur de message, on construit un système d'équations composé par des multiplications de matrices et de vecteurs de taille inférieure. Ainsi, on obtient un codage plus rapide et une structure plus simple.

Quand il n'y a pas de sous-matrices nulles dans la structure de H, le code est régulier et le rendement du code est supérieur au rendement d'un code irrégulier parce que dans ce cas la matrice H possède un rang maximal (si H est triangulaire inférieure ou supérieure avec des éléments non-nuls sur la diagonale principale, H a le rang maximum).

Dans [38], les auteurs proposent une méthode efficace de construction des codes B-LDPC, nommé le Principe A : on choisit d'abord les blocs sur les colonnes avec un petit poids tels que la longueur minimale des cycles entre les noeuds de degré inférieur soit maximum. Ensuite, on choisit les blocs des colonnes correspondants aux noeuds avec un degré supérieur tels que le périmètre du graphe de Tanner soit maximum. Les codes qui sont ainsi construits ont un plancher d'erreurs bas et des meilleures valeurs des rapports de Taux d'Erreurs Binaires (TEB) et de Taux d'Erreurs par Trame (TET).

La performance d'erreurs de contrôle peut être améliorée si on impose que le degré des petits cycles inévitables soit le plus grand possible.

On doit mentionner que les noeuds de degré élevé sont plus sensibles aux erreurs (parce qu'ils ont plusieurs chemins pour la mise à jour des messages entre les noeuds variables et les noeuds de parité). Richardson [39] a montré par la méthode d'évolution de la densité (density evolution) que les codes de

très grande longueur (qui convergent vers l'infini) s'approchent de très près de la limite de Shannon. Mais ceci n'est pas valide pour les codes courts. Les performances des codes LDPC dépend aussi de cycles existants dans le graphe de Tanner et de la distance minimale du code.

III.6. Décodage des codes LDPC

Par rapport aux autres types de codes, le décodage des codes LDPC ne pose pas autant de problèmes pour les chercheurs que leur construction. Le travail le plus difficile est de trouver les meilleures méthodes pour construire des codes LDPC efficaces. Un code LDPC peut être décodé par plusieurs méthodes. On peut citer :

1. Décodage avec des décisions fermes

? Décodage avec la logique majoritaire (MLG) ; ? Décodage avec basculement de bit (BF) ;

2. décodage avec des décisions pondérées

? Décodage basé sur la probabilité a posteriori (APP) ;

? Décodage itératif basé sur la propagation de la confiance (somme-produit SPA) ;

3. Décodage mixte (ferme et pondéré) ? Décodage BF pondéré.

La méthode MLG est la plus simple du point de vue de la complexité du circuit. La méthode BF demande un peu plus de complexité du circuit, mais elle donne des meilleures performances d'erreur que la méthode MLG. Les méthodes APP et SPA donnent des meilleures performances d'erreurs, mais nécessitent aussi une plus grande complexité du circuit. Le décodage BF pondéré représente un bon compromis entre les deux caractéristiques. Quand à la méthode SPA, donne les meilleurs TEB entre les 5 types de décodage.

? Décodage MLG des codes LDPC

La méthode MLG à une seule étape [34] peut être appliquée au décodage des 4 types de codes LDPC.

On calcule les syndromes :

??-1 (??)

???? ?? = ?? * ???? ?? = ?????? ??,??

??=0 III.6

Où ????(??) (1= ?? = ?? ) sont les ?? lignes de H qui sont orthogonales sur le bit de la l-ème position. L'ensemble des sommes de contrôle ???? (??) sont orthogonales sur le bit d'erreurs ???? et on peut les utiliser

pour l'estimation de ????. Le bit d'erreurs est bien corrigé si dans le vecteur d'erreurs il y a moins de ??/2 erreurs.

? Algorithme de décodage à basculement de bit (BF) des codes LDPC

Cette méthode est basée sur l'échange du nombre d'échecs de parité quand un bit de la séquence reçue est basculé. Il s'agit d'une méthode itérative de décodage [28]. Le décodeur calcule toutes les sommes de parité et ensuite, il change chaque bit dans la séquence reçue s'il fait partie de plus de ?? équations de parité échouées. La valeur de S est un seuil fixé et dépend des paramètres du code (??,??, dmin) et du rapport signal à bruit ou (Signal Noise Ratio SNR).

À partir de la séquence modifiée, le décodeur recalcule les sommes de parité et le processus est répété jusqu'à ce que toutes les sommes de parité soient nulles.

Le nombre d'itérations du décodage est une variable aléatoire et dépend du rapport signal à bruit du canal. Pour des meilleures performances, on peut utiliser des seuils adaptatifs ?? et utiliser aussi une méthode hybride entre BF et MLG. Le décodage BF corrige beaucoup de séquences d'erreurs qui possèdent plus de bits erronés que la capacité du code pour corriger les erreurs.

? Algorithme de propagation de croyance

Dans cette partie, nous nous intéressons au décodage itératif souple des codes LDPC. L'algorithme de décodage itératif présenté initialement par Gallager [40], revu ensuite par MacKay [41] dans le cadre de la théorie des graphes, est connu sous le nom d'algorithme de propagation de croyance (Belief

Pr ?? = 1 ?? =

¹-??' ?????/?? (1-2 Pr ??' =1 ?? )

2

III.10

Propagation (BP)). Cet algorithme peut être vu comme un algorithme d'échange d'information entre les noeuds du graphe à travers les branches. Ces messages transitant de noeuds en noeuds portent une information probabiliste sur l'état des noeuds.

Le principe de la propagation de croyance est l'application directe de la règle de Bayes sur chaque bit d'une équation de parité. La vérification de parité permet de calculer une estimation de chaque bit. Ces estimations, formant des messages se propageant sur les branches du graphe, sont alors échangées itérativement afin de calculer une information a posteriori sur chaque bit. Dans le cas d'une propagation de croyance sur un graphe sans cycle, les messages échangés sont indépendants, ce qui conduit au calcul simple et exact des probabilités a posteriori : l'algorithme est dans ce cas optimal. Dans le cas des codes LDPC, le graphe factoriel présente des cycles.

Dans ces conditions, l'hypothèse de messages indépendants n'est plus valide. Cependant, plus le graphe est creux (c'est à dire moins la matrice de contrôle de parité est dense), plus l'approximation d'un graphe sans cycle devient valide. C'est donc sous cette hypothèse que l'algorithme de décodage est décrit.

Si on considère une équation de parité c faisant intervenir un ensemble de bits Vc, la règle de Bayes appliquée au bit v permet d'exprimer les probabilités suivantes conditionnellement à la séquence reçue { y } :

Pr ?? = 0 ?? = Pr(_??' ??'

?????/?? = 0{??}) III.7

Pr ?? = 1 ?? = Pr(_??' ??'

?????/?? = 1{??}) III.8

Où la somme est réalisée modulo 2. Gallager a démontré dans [42] que ces deux probabilités sont égales

à :

1+ ??' ?????/?? (1-2 Pr ??' =1 ?? )

Pr ?? = 0 ?? = III.9

2

En utilisant la relation :

???????? 2 1 ???? 1-Pr?(??^' =1 ?? )

Pr ?(??' =1{??} = 1 - 2Pr?(??^' = 1 ?? ) III.11

On peut calculer le rapport de vraisemblance suivant :

1 + Pr ?? = 0 ??	?? '	????? ??	????????	1 ???? Pr ??' =	0 ??	0 ?? )	III. 12 III.13
				2 Pr?(??^' =	1{??}
Pr ?? = 1 ?? 1 - Qui peut être simplifié par : 1 Pr?(?? = 0	?? ' ??	?? )	????? ???????? = ??'?????	1 ???? Pr ??' =	0 ??
				2 Pr?(??^' = 1 ???????? 2 ???? /??	1{??} Pr?(??^' =
???????? 2???? Pr?(?? = 1	??	)			Pr?(??^' =	1{??}

La fonction tanh étant une fonction monotone impaire, on peut décomposer la relation précédente de la manière suivante :

Pr?(?? = 0{??}

Pr?(?? = 1{??}

= ???????? ????

??'???

Pr?(??^' = 0 ?? ) Pr?(??^' = 1{??}

???????? ????

??/??

III.14

???????? 2 1 ???? Pr?(?? = 0{??}

1 Pr?(??^' = 0 ?? )

= ???????? 2 ???? Pr?(??^' = 1{??}

Pr?(?? = 1{??}

??'?????/??

III.15

En utilisant le fait que : ?? ?? = - ln ????????	??	= ln	exp ?? + 1	= ?? ^-1(??) III. 16
	2		exp ?? - 1

On peut exprimer la valeur absolue du rapport de vraisemblance dans l'espace logarithmique par :

Pr?(?? = 0{??} ???? Pr?(?? = 1{??}

= ?? ?? ???? ??'????? /??

Pr?(??^' = 0 ?? ) Pr?(??^' = 1{??}

III. 17

Cette relation va servir de base pour la description de l'algorithme de propagation de croyance. Dans ce qui suit nous allons présenter les résultats de simulation.

III.7. Résultats de la simulation

Dans cette partie, nous décrivons une série de simulations faites sous Matlab/Simulink. C'est l'outil de références pour la simulation numérique, il offre des possibilités avancées que ce soit en matière d'identification ou de commande. Il permet de manière plus générale, de résoudre une grande diversité de problèmes de simulation, dans des domaines aussi variés que le traitement de signal. L'objectif ici est d'illustrer le plus simplement possible le module de théorie de l'information dont la partie concernant le codage de canal constitue la finalité. La démarche consiste à évaluer les performances des codes LDPC réguliers [43] et ensuite, de comparer les performances avec celles des turbo-codes.

Pour évaluer les performances des codes LDPC réguliers, nous avons pris un code LDPC régulier associé à une modulation MDP-2 sur un canal gaussien.

Nous allons voir sur les figures suivantes l'évolution du TEB et du FER en fonction du rapport signal à bruit _Eb/N0 (dB). Nous avons pris un code LDPC régulier de rendement 1/2 et de paramètres de la matrice (3*6).

^10-1

^10-2

^10-3

^10-4

^10-5

10-6 ^{0 1 2 3 4}

¹⁰⁰

Eb/N0(dB)

Figure III.3 : Evaluation des performances du TEB sur un canal gaussien d'un code LDPC régulier de rendement R=1/2 et de paramètres de la matrice (3*6) associée à une modulation MDP2.

^{Eb/N0 (dB)}

^10-1

^10-2

^10-3

^10-4

10-5 ^{0 1 2 3 4}

¹⁰⁰

Figure III.4 : Evaluation des performances du FER sur un canal gaussien d'un code LDPC régulier de rendement R=1/2 et de paramètres de la matrice (3*6) associée à une modulation MDP2.

^{Eb/N0 (dB)}

^10-1

^10-

^10-3

^10-4

^10-5

10-6 ^{0 1 2 3 4}

¹⁰⁰

^{Le gain=1dB}

^FER

^TEB

Figure III.5 : Evaluation des performances du TEB et du FER sur un canal gaussien d'un code LDPC régulier de rendement R=1/2 et de paramètres de la matrice (3*6) associée à une modulation

MDP2.

^10-1

^10-2

^10-3

^10-4

^10-5

^10-6

^{0 1 2 3}

¹⁰⁰

^{iter1 iter2 iter3 iter4 iter5 iter6}

^{Eb/N0 (dB)}

Figure III.6 : Evaluation du décodage itératif sur canal gaussien d'un code LDPC régulier de rendement 1/2 associé à une modulation MDP-2.

^Eb/N0(dB)

^10-1

^10-2

^10-3

^10-4

^10-5

10-60 ^{1 2 3}

¹⁰⁰

^{iter1 iter2 iter3 iter4 iter5 iter6}

Figure

III.7 : Evaluation du décodage itératif sur canal gaussien d'un code LDPC régulier de rendement 1/2 associé à une modulation MDP-2.

^10-1

^10-2

^10-3

^10-4

^10-5

10-60 ^{1 2 3}

¹⁰⁰

^{TEB(iter1) TEB(iter4) TEB(iter6) FER(iter1) FER(iter4) FER(iter6)}

^{Eb/N0 (dB)}

Figure III.8 : Evaluation des performances du TEB et du FER sur un canal gaussien d'une modulation MDP-2 à la ₁ière ,4ième et la ^6ième itération d'un code LDPC régulier de rendement R=1/2 et de paramètres (1000*2000).

^{Eb/N0 (dB)}

^10-1

^10-2

^10-3

^10-4

^10-5

^10-6

^10-7

^{0 1 2 3}

¹⁰⁰

^{5iter LDPC}

^{6iter LDPC}

^{5iter Turbo_code_non_poinçonné 6iter Turbo_code_non_ poinçonné 5iter Turbo_code_poinçonné 6iter Turbo_code_poinçonné}

Figure III.9 : Evaluation du TEB sur canal gaussien d'un turbo code poinçonné ou non poinçonné et d'un code LDPC régulier de rendement 1/2 associé à une modulation MDP-2 à la 5ième et à la ^6ième itération.

? Commentaires

? Prenons les figures III.3 et III.4, on remarque que le TEB et le FER diminuent à chaque

fois que le rapport signal à bruit augmente.

? Si on considère la figure III.5 et qu'on prend un Eb/N0=3dB, on remarque qu'on a un

FER = 4*10^-2, et un TEB = 1.5*10^-3.

Voyant maintenant d'après la figure III.5 le gain en dB entre la courbe représentant le TEB et celle représentant le FER.

Prenons sur cette figure, un TEB et un FER de 10^-2, on remarque qu'il faudrait un Eb/N0(dB) égal à 3.4 dB pour le FER et un _Eb/N0 égal à 2.4 dB pour le TEB ; donc on gagnerait : (3.4dB - 2.4 dB) = 1dB.

? Nous allons par la suite montrer le coté itératif du code LDPC régulier à six itérations.

Nous avons pris un rendement 1/2, et de paramètres (1000*2000).

D'après les courbes obtenues de la figure III.6, on remarque le TEB diminue lorsque le nombre des itérations augmente.

Par exemple d'après la figure III.6, pour un Eb/N0=0.5 dB on a :

o Pour la première itération on a un TEB=4*10^-2.

o Pour la sixième itération on a un TEB=3*10^-5.

Donc on remarque très clairement la diminution du TEB.

Maintenant, on va montrer le caractère itératif de ce code. On a choisit le code LDPC de rendement R=1/2.

D'après les courbes obtenues à partir de la figure III.7, on remarque le FER diminue lorsque le nombre des itérations augmente.

Par exemple d'après la figure III.7, pour un Eb/N0=0.5 dB on a :

o Pour la première itération on a un FER=5*10^-2.

o Pour la sixième itération on a un FER=4*10-5.

Donc on remarque très clairement la diminution du FER.

? Sur la figure III.8, nous remarquons l'effet du caractère itératif qui apparait sur les courbes du TEB et du FER ; ce qui veut dire que le rajout du nombre d'itérations fait que le TEB et le FER diminuent. La différence est très claire par exemple sur les courbes de la ^1ière et la ^6ième itération.

? Dans le codage correcteurs d'erreurs, nous avons aussi le caractère itératif dans le turbo

code. Nous allons montrer ceci dans les figures suivantes en prenant un turbo code de rendement 1/2 poinçonné ou non poinçonné, un code LDPC régulier de même rendement et avec des paramètres (1000*2000) et en comparant les résultats.

D'après les courbes obtenues de la figure III.9, on remarque que les turbo-codes poinçonnés sont moins bons que les codes LDPC et les turbo-codes non poinçonnés.

Les codes LDPC sont meilleurs par rapport les turbo-codes poinçonnés et les turbo-codes non poinçonnés présentent de meilleurs résultats avec le caractère itératif.

III.8. Conclusion

Le problème majeur dans la théorie du codage est la construction des codes qui s'approchent de la capacité du canal et la conception d'algorithmes de codage et de décodage efficaces.

Les codes LDPC réguliers sont des codes correcteurs qui approchent la limite de Shannon. Il a été démontré que les codes LDPC longs avec un décodage itératif basé sur la propagation de croyance atteignent une performance d'erreurs à une fraction de décibel de la limite du Shannon.

Les codes LDPC sont en grande compétition avec les codes turbo dans les systèmes de communications numériques qui demandent une fiabilité élevée. Aussi, les codes LDPC ont quelques avantages par rapport aux codes turbo.

CONCLUSION GéNéRALe eT PeRSPeCTIveS

L'objectif de ce mémoire est l'étude et l'évaluation d'un code LDPC régulier en se basant sur le décodage itératif.

Le codage de canal présente une étape importante dans notre travail. C'est pour cette raison que l'étude du codage et du décodage d'un canal était nécessaire afin d'éclaircir le rôle et l'effet d'un code correcteur d'erreur sur le signal à transmettre.

Dans le chapitre É, on a présenté une brève étude de la chaîne de transmission numérique.

Dans le chapitre II, nous avons étudié les deux grandes familles des codes correcteurs d'erreurs, les codes convolutifs et les codes en blocs linéaires.

Dans le chapitre III, nous avons étudié un nouveau type des codes correcteurs d'erreurs qui sont les codes LDPC réguliers ainsi que leur décodage itératif et nous avons évalué leurs performances par simulation.

Les résultats de simulation ont montré que les codes LDPC réguliers réalisent de bons résultats avec le décodage itératif sur un canal gaussien associé à une modulation MDP-2 afin de minimiser le Taux d'Erreurs Binaire (TEB) et le FER en fonction du rapport signal à bruit Eb/N0 (dB).

Ainsi, les codes LDPC deviennent maintenant un sujet d'actualité dans le domaine des télécommunications. C'est pour cela que nous allons donner quelques perspectives.

Ces codes possèdent un grand nombre de paramètres, pour cela, l'optimisation de leurs paramètres serait un thème d'avenir afin de les adapter à de nombreux canaux. Cette adaptation offre de nombreuses perspectives d'utilisation.

Par exemple, des codes LDPC peuvent être conçus pour des communications optiques, du stockage magnétique, des canaux à entrées multiples et à sorties multiples et de la transmission par satellite. Un code LDPC a d'ailleurs été choisi pour la norme DVB-S2, constituant ainsi un point de départ à l'expression de leur potentiel dans des utilisations industrielles. Ainsi, les architectures des décodeurs LDPC deviennent maintenant un sujet d'actualité dans le domaine de l'adéquation algorithme-architecture.

LEXIQUE

TEB : Taux d'Erreurs Binaire.

MDA : Modulation par Déplacement d'Amplitude.

MDP : Modulation par Déplacement de Phase.

MAQ : Modulation d'Amplitude de deux porteuses en Quadrature.

MDF : Modulation par Déplacement de Fréquence.

TOR : modulation Tous Ou Rien.

CBS : Canal Binaire Symétrique.

BBAG : Bruit Blanc Additif Gaussien.

BCH: Bose Chaudhuri Hocquenghem.

RSG: Reed Solomon Generalized.

LDPC: Low Density Parity Check Coded.

MLD: Maximun Likelihood Decoding.

EG-LDPC: Euclidian Geometry-Low Density Parity Check Coded.

PG-LDPC: Projective Geometry-Low Density Parity Check Coded.

QC-LDPC: Quasi Cyclique-Low Density Parity Check Coded.

B-LDPC: Bloc-Low Density Parity Check Coded.

TET: Taux d'Erreurs par Trames.

BF: Bit Flipping.

MLG: Majority Logic Décoding.

APP: A Posteriori Probability.

SNR: Signal Noise Ratio.

BP: Belief Propagation.

BIBLIOGRAPhIe

[1] C. E. SHANNON, «A mathematical theory of communication,» Bell System Technical Journal, vol. 27, pp. 379-423 et 623-656, Juillet et Octobre 1948.

[3] J.M. WOZENCRAFT, I.M. Jacobs, «Principle of Communications Engineering», John Wiley, New York, 1965.

[4] J. B. DORE, «Optimisation conjointe de codes LDPC et de leurs architectures de décodage et mise en oeuvre sur FPGA«, Thèse de doctorat, INSA DE RENNES, pour obtenir le grade de Docteur de l'INSA de Rennes, 26 octobre 2007.

[5] A. GLAVIEUX, J. Michel, «Introduction : Codage et Communications Numériques«, Paris, Masson, 1996.

[6] BIC J.C. DUPONTEIL D. IMBEAUX, «Eléments de Communications Numériques, Transmission sur fréquence porteuses«, Paris, Dunod, 1986.

[7] J. G. PROAKIS, «Digital communications«, Mc Graw-Hill, USA, 1989,

[8] M. DEGAUQUE, «Transmission numérique sur porteuse : ASK, FSK et PSK«, Probatoire du CNAM de Bordeaux, juillet 1998.

[9] O. BERDER, «Optimisation et stratégies d'allocation de puissance des systèmes de transmission multi-antenne«, Thèse de doctorat de l'université de Bretagne occidentale, 2002.

[10] A.L. FAWE, L. DENEIRE, «Principe de Télécommunications«, 1995-1996.

[11] J. G. PROAKIS, «Digital Communications«, Mc Graw-Hill, Third Edition, Singapore, 1995.

[12] M. BOSSERT, «Channel coding for telecommunication«, JOHN WILEY & SONS, 1999.

[13] P. ELIAS, «Coding for noisy channels», IRE International Convention Record, (part 4), pages 3766. 1955.

[14] D.W. HAGELBARGER, «Recurrent codes. Easily mechanized, burst_correcting binary codes«. Rapport technique J.38, Bell syst, Juillet 1959.

[15] A. J. VITERBI, «Error bounds for convolutional codes and an asymptotically optimum decoding algorithm«, IEEE Transactions on Information Theory, April 1967.

[16] J.P. ODENWALDER, «Optimal decoding algorithm«, IEEE, Transactions on Information Theory, IT-13: 260-269, Avril 1967.

[17] G.C. CLARK, J.B. CAIN, «Error correcting coding for digital communication«, plenum press 1981.

[18] M.A. SAHRAOUI, A. ZEBIDA, «Codes détecteurs et correcteurs d'erreurs appliqués aux images fixes«, Institut d'informatique, USTO 1995.

[19] A. BENHALLAM, «Comparaison entre différentes procédures de décodages des codes convolutionnels«, Note Interne, Institut National polytechnique de Toulouse, 1985.

[20] R. PELLIKAAN, X. W. Wu and S. BULYGIN, «Error-correcting codes and cryptology», Preliminary version, February 21, 2011.

[22] R.J. McEiece, «A public key cryptosystem based on algebraic coding theory DSN progress report 42-44«, jet propulsion laboratory, CA, January-February, 1978, pp.114-16.

[23] A. POLI, L. HUGUET, '' Codes Correcteurs : Théorie et Applications'', Masson, Paris 1989.

[24] S. FOUGHALI, S. KHELIFA, ' Concaténation des Codes Cycliques (Reed Solomon - Hamming) appliquées aux images fixes'', Institut d'Informatique, USTO 1998.

[25] M. DEMAZURE, Cours d'algèbre, Cassini 1997.

[26] I. S. REED, G. SOLOMON,» Polynomial codes over certain finite fields», Journal of the SIAM, pp.300-304, June 1960.

[27] K. A. BUSH, «Orthogonal arrays of index unity«, Annals of Mathematical Statistics, pp.426-434, 1952.

[28] R. GALLAGER, "Low Density Parity Check Codes", IRE Trans. Inform. Theory, vol. IT-8, pp. 2129, 1962.

[29] R. M. TANNER, «A Recursive Approach to Low Complexity Codes«, IEEE Trans. Inform, Theory, vol. IT-27, pp. 533-547, 1981.

[30] S. LIN, Y. KOU, M. FOSSORIER, "Low Density Parity Check Codes Construction Based on Finite Geometries", in Proc.GLOBECOM 2000, San Francisco, Calif., Novembre 27-Decembre 1.

[31] C. BERROU, «Codes et turbo codes«, ^1ière édition, springer-verlag, France, 2007.

[32] N.WIBERG, H. A. LOELIGER, and R. KOTTER, «Codes and Iterative Decoding on General Graphs«, Eur. Trans. Telecommun., vol. 6, pp. 513-26, 1955.

[33] T.J. RICHARDSON, R.L. URBANKE, «Efficient encoding of Low-Density Parity-Check«.

[34] S. LIN, D. COSTELLO, «Error control coding«, Prentice Hall, 2004.

[35] D. J. MACKAY, «Good error-correcting codes based on very sparse matrices«, IEEE Trans. Inform. Theory, vol. 45(2), pp. 399-431, 1999.

[36] S. LIU, L. CHEN, J. XU and I. DJURDJEVIC, «Near Shannon Limit Quasi-Cyclic Low Density Parity-Check Codes«, in Proc. IEEE GLOBECOM 2003, 2003. San Francisco, Calif., December 1-5.

[37] S. MYUNG, K. YANG, J. KIM, «Low density parity-check codes«, IEEE Trans. Inform. Theory, vol. 51, pp. 2894 - 2901, 2005.

[38] H. ZHONG, T. ZHANG, «Block-LDPC : A Practical LDPC Coding System Design Approach«, IEEE Transactions on Circuits and Systems, vol. 52(4), pp. 766-775, 2005.

[39] T. RICHARDSON, M. SHOKROLLAHI and R. URBANKE, «Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes«, IEEE Trans. Inform. Theory, vol. 47(2), pp. 619-637, 2001.

[40] H. TANG, J. XU, Y.KOU, S. LIN ET K. ABDEL-GHAFFAR, «On Algebraic Construction of Gallager and Circulant Low Density Parity Check Codes«, IEEE Trans. Inform. Theory, vol. 50(6), pp. 1269 - 1279, 2004.

[41] D. MACKAY AND R. M. NEAL, «Near shannon limit performance of low density parity-check codes«, Electronic Letter, August 1996.

[42] R. G. GALLAGER, «Low-density parity-check codes», Ph.D. dissertation, 1963.

[43] L. MOSTARI, R. MELIANI, A. BOUNOUA, «Iterative Effect on LDPC Code Performance», RMT, vol. 1, 2, Juillet 2011.

? Sites internet

[2] http://81.e-monsite.com/2009/09/11/2745497chaine-pdf.pdf.

[21] http://greyc.ensicaen.fr~gbinetT infocoursT inf b linéaires.pdf.

RESUME

Le développement rapide des réseaux mondiaux et les immenses possibilités offertes par les transactions électroniques en communications continues, posent aujourd'hui de manière cruciale, le problème de la protection de l'information contre les erreurs de transmission d'une part, et d'autre part, il faut que ces données soit non intelligibles sauf à l'auditoire voulu. Afin de pallier ces deux contraintes on utilise le codage de l'information pour combattre les erreurs de transmissions.

La découverte dans les années 90 des Turbo-codes et, plus généralement du principe itératif appliqué au traitement du signal, a révolutionné la manière d'appréhender un système de communications numériques. Cette avancée notable a permis la redécouverte des codes correcteurs d'erreurs inventés par R. Gallager en 1963, appelés codes Low Density Parity Check (LDPC).

L'intégration des techniques de codage dites avancées, telles que les Turbo-codes et les codes
LDPC, se généralise dans les standards de communications. Dans ce contexte, l'objectif de ce mémoire est d'étudier de nouvelles structures de codage de type LDPC réguliers en se basant sur le codage itératif.

Mots clés : Codage de canal, Codes LDPC, turbo codes, graphe de Tanner, TEB, TET, Décodage itératif.

ABSTRACT

The rapid development of global networks and the immense possibilities offered by electronic transactions in continuous communication, today meet a crucial problem of information protection against transmission errors on the one hand, and secondly require that the data is unintelligible except to the audience wanted. To overcome these two constraints we use the coding of information to combat the transmission errors.

The introduction of Turbo-codes in the early 90's and, more generally the iterative principle has deeply modified the methods for the design of communication systems. This breakthrough has also resurrected the Low Density Parity Check (LDPC) codes invented by R. Gallager in 1963. Advanced channel coding techniques such as Turbo-codes and LDPC, are now increasingly considered for introduction into communication systems and standards. This evolution towards industrialization motivates the definition of new flexible and efficient decoding architecture for LDPC codes. In this context, the objective of this thesis is to explore new coding structures like regular LDPC based on the iterative coding.

Key words: Channel coding, LDPC codes, turbo codes, Tanner graph, BER, SNR, iterative decoder.