TECHNIQUES MODERNES DE CODAGE - vitevu.free.frvitevu.free.fr/tipe/tmc_cours_general_codage_2004.pdf · Extrait d’un livre sur les Communications Radiomobiles ... La suite des signaux

TECHNIQUES MODERNES DE CODAGE

Janvier-Mars 2004

JOSEPH J. BOUTROS

Département Communications & Electronique

Ecole Nationale Supérieure des Télécommunications

Photocopie Interdite, sauf pour le cours TMC, Brique ADC.

Extrait d’un livre sur les Communications Radiomobiles édité par Hermes sous la direction de Xavier Lagrange

2 TMC 2004 – Brique ADC

1. Introduction : modélisation du système et description de l’alphabet.

Le codage correcteur d’erreurs est une fonction essentielle dans les systèmes de transmission de l’information. Le codage de canal a acquis durant ces dernières années une importance considérable. Le progrès des circuits électroniques a fait croître l’intérêt que les scientifiques ont pour le codage. Tous les systèmes actuels fixes et mobiles de transmission numérique par câble, voie radioélectrique et fibre optique sont dotés de codes correcteurs d’erreurs afin d’améliorer considérablement la qualité de service. L’installation du codage de canal est devenue indispensable dans tous les domaines de télécommunications et d’enregistrement. La théorie du codage possède sa propre histoire et son charme particulier puisqu’elle communique avec plusieurs théories parmi lesquelles figurent la théorie des groupes, l’algèbre, les communications numériques et le traitement du signal. Une grande partie des outils mathématiques datent du 19ème et du début du 20ème siècle. Pourtant nous considérons la théorie du codage comme une partie intégrante de la théorie de l’information fondée par Shannon en 1948. Voici les dates clefs qui ont marqué le domaine depuis la fin des années 40 : 1948 C.E. Shannon, A Mathematical Theory of Communication. 1949 M.J.E. Golay, Note on Digital Coding. 1950 R.W. Hamming, Error Detecting and Error Correcting Codes. 1955 E. Elias, Coding for Noisy Channels. 1956 D. Slepian, A Class of Binary Signaling Alphabets. 1963 R. Gallager, Low Density Parity Check Codes. 1963 R.M. Fano, A Heuristic Discussion of Probabilistic Coding. 1966 G. D. Forney, Concatenated Codes. 1967 J. Leech, Notes on Sphere Packings. 1967 A.J. Viterbi, Error Bounds for Convolutional Codes and an Asymptotically Optimal Decoding Algorithm. 1972 G. D. Forney, ML Sequence Estimation of Digital Sequences in the Presence of Intersymbol Interference. 1973 G. D. Forney, The Viterbi Algorithm. 1974 L.R. Bahl, J. Cocke, K. Jelinek, J. Raviv, Optimal Decoding of Linear Codes for Min. Symbol Error Rate. 1977 H. Imai, S. Hirakawa, Multilevel Coding Method using Error Correcting Codes. 1978 J.K. Wolf, Efficient Maximum Likelihood Decoding of Linear Block Codes Using a Trellis. 1979 G. Battail, M.C. Decouvelaere and P. Godlewski, Replication Decoding. 1981 R.M. Tanner, A Recursive Approach to Low Complexity Codes. 1982 G. Ungerboeck, Channel Coding with Multilevel/Phase Signals. 1986 J.H. Conway and N.J.A. Sloane. Soft Decoding Techniques for Codes and Lattices. 1987 L.F. Wei, Trellis Coded Modulation with Multi-Dimensional Constellations. 1987 G. Battail, Pondération des Symboles Décodés par l'Algorithme de Viterbi. 1988 G. D. Forney, Coset Codes, Part I and II. 1989 J. Hagenauer and P. Hoeher, A Viterbi Algorithm with Soft Decisions Outputs and its Applications. 1993 C. Berrou, A. Glavieux, P. Thitimajshima, Near Shannon Limit Error Correcting Coding and Decoding. 1996-1999 D.J.C. MacKay, Good error-correcting codes based on very sparse matrices. 1998-2001 M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman, Improved low-density parity-check codes using irregular graphs and belief propagation. 1999-2000 B.J. Frey, D.J.C. MacKay, Irregular Turbo codes. 2000-2002 J. Boutros, G. Caire, E. Viterbo, H. Sawaya, S. Vialle, Turbo code at 0.03 dB from capacity limit. 1997-2002 J. Boutros, G. Caire, Iterative multiuser joint decoding: unified framework and asymptotic analysis. Par manque de place, nous avons omis une dizaine d’articles intéressants. Le lecteur est prié de consulter les références bibliographiques associées à ce chapitre. Dans la suite de ce chapitre, nous utiliserons parfois l’expression codage de canal équivalente à celle de code correcteurs d’erreurs. Le terme codage de canal est synonyme de la transformation appliquée à la séquence des symboles à transmettre pour l’adapter au canal de transmission. Ainsi, le rôle du codage de canal est de protéger les données numériques contre les erreurs introduites par le canal de transmission. Le besoin du codage de canal augmente avec le volume important des données communiquées ou enregistrées. Une théorie fournissant de bons codes et de bons algorithmes de codage est là pour satisfaire ce besoin. De plus, les progrès techniques des circuits intégrés et des processeurs de traitement de signal rendent possible la réalisation de ces algorithmes.

Joseph J. Boutros 3

Nous distinguons les deux classes suivantes de codes correcteurs : les codes en blocs et les codes en treillis. La figure 1 donne un simple résumé de la grande famille de codage. Dans la première classe à droite de la figure, citons les codes les plus célèbres comme les codes BCH, Reed Solomon, Goppa, Golay et Hamming. La deuxième classe à gauche de la même figure est moins riche en variété, mais présente beaucoup plus de souplesse surtout dans le choix des paramètres et des algorithmes de décodage disponibles. Citons par exemple les codes convolutifs binaires systématiques récursifs très utilisés dans les modulations codées (TCM). Une troisième classe dite codes concaténés est obtenue par concaténation série, parallèle ou hybride de codes convolutifs et de codes en blocs. Ainsi, les turbo codes classiques sont construits par concaténation parallèle de codes convolutifs récursifs. Les codes dits produits sont le résultat de la concaténation de deux codes en blocs. Une concaténation de plusieurs codes de parité entrelacés donne naissance aux codes à faible densité de Gallager. Les turbo codes, les codes de Gallager ainsi que les codes produits forment un cas particulier de la grande famille des codes de Tanner.

Les Codes Correcteurs

Les Codes en Treillis Les Codes en Blocs

Modulations Codées en Treillis

Les Codes Convolutifs

Les Codes Non Linéaires

Modulations Codées en Blocs

Les Codes Linéaires

Les Codes Récursifs Les Codes Non Récursifs Les Codes Non CycliquesLes Codes Cycliques

Les Codes Concaténés

Figure 1 : La famille des codes correcteurs d’erreurs.

1.1. Modèle d’un système de transmission utilisant le codage de canal. Un système de communications relie, par l’intermédiaire d’un canal, une source de données à un utilisateur. Le canal peut être un câble coaxial, une liaison radioélectrique, une fibre optique ou un support d’enregistrement comme la bande magnétique. La figure 2 nous montre les différents blocs constituant la chaîne de transmission numérique. La source fournit de l’information sous forme de symboles. Les symboles appartiennent à un certain alphabet A. Par exemple, l’alphabet binaire est A={0,1}. L’ensemble A est le plus souvent constitué de q=pm éléments, où p et m sont deux entiers naturels. q est le cardinal de l’alphabet. Les symboles provenant de la source d’information sont traités par un codeur de source. Ce dernier permet de représenter les données de façon plus compacte (compression de données). A la sortie du codeur de source, les symboles sont groupés en blocs que l’on appelle mots de source. Les symboles sont ensuite traités par le codeur de canal qui transforme la séquence des symboles formant le mot de source en une séquence appelée mot de code.


Source Codeur de Source Codeur de Canal

Démodulateur Canal Modulateur

Décodeur de canal Décodeur de source Utilisateur

Figure 2 : Les différents blocs de la chaîne de communication. Le mot de code est une nouvelle séquence de symboles plus longue que le mot de source et ayant plus de redondance. Le modulateur placé après le codeur de canal convertit chaque symbole du mot de code en un signal analogique choisi dans un ensemble fini de signaux. La suite des signaux analogiques est transmise sur le canal. Les signaux reçus diffèrent des signaux émis à cause du bruit et des distorsions rencontrées sur le canal. Le démodulateur effectue une opération de détection en transformant les signaux reçus en une suite de symboles. Un symbole détecté est la meilleure estimation faite par le démodulateur du signal émis. Le démodulateur commet parfois des erreurs d’estimation puisque le signal reçu est entaché de bruit. La séquence des symboles après démodulation s’appelle mot reçu. Les erreurs font que les symboles du mot reçu ne ressemblent pas toujours à ceux du mot de code. Le décodeur de canal utilise la redondance contenue dans un mot de code pour corriger les erreurs dans le mot reçu et fournir une estimation du mot de source. L’estimation est égale au mot de source si le décodeur de canal arrive à corriger toutes les erreurs. Enfin, le décodeur de source délivre l’information à l’utilisateur en inversant l’opération du codeur de source. Nous nous limiterons dans le cadre de ce chapitre à l’étude du codeur et du décodeur de canal. Sans aucune ambiguïté, puisque les sujets de modulation et de codage de source ne seront pas abordés dans cette étude, nous parlerons de codeur et de décodeur. Le modèle de la figure 2 est ainsi valable pour tous les systèmes de transmission mobile de 2ème et 3ème générations : GSM, IS-95, UMTS, EDGE, Iridium, Skybridge, Globalstar. Sachant que la plupart de ces systèmes utilisent une modulation QPSK ou un équivalent de cette modulation, nous limitons l’étude des performances des codes correcteurs d’erreurs sur un canal véhiculant des signaux issus d’une modulation BPSK ( théoriquement équivalente à la QPSK). L’énergie passe-bande moyenne par bit d’information est notée Eb. L’énergie moyenne par bit codé, associée aux symboles BPSK, est notée Ec. Nous utiliserons le rapport signal-à-bruit Eb/No, où No/2 est la densité spectrale du bruit passe-bande. Le taux de codage R sera défini au paragraphe suivant où le codeur lit k bits d'information et fournit n bits codés. D’où la relation Ec=REb. Le rendement R est équivalent au nombre de bits émis par dimension de la modulation. Il est majoré supérieurement par la capacité du canal au sens de Shannon, donnée par la théorie de l’information. La nature de l’interface reliant le démodulateur au décodeur de canal a une influence directe sur la qualité de la transmission et permet de distinguer deux types de décodage : 1- Le décodage à décisions fermes, dit décodage hard. Le démodulateur fournit au décodeur la valeur des

symboles détectés. Ainsi, le canal équivalent vu par le codage de canal englobant le modulateur, le vrai canal et le démodulateur est modélisé par un seul bloc à entrée discrète et à sortie discrète appartenant à l’alphabet des symboles. Par exemple, dans le cas binaire, le codeur et le décodeur entourent un canal binaire symétrique (BSC) illustré figure 3. Le canal BSC est caractérisé par ses probabilités de transition p(0/0)=p(1/1)=1-p et p(0/1)=p(0/1)=p, où la probabilité d’erreur est définie par [48]

Joseph J. Boutros 5

=

0

2NE

Qp c

0

1

0

1

p

p

1-p

1-p

0

1

+∞

-∞

cE2+

cE2−

Canal BSC Canal gaussien

Figure 3 : Les deux principaux modèles de canaux de transmission. 2- Le décodage à décisions souples, dit décodage soft. Le démodulateur fournit au décodeur la probabilité a

posteriori des symboles détectés ou leurs valeurs de confiance. Ainsi, le canal équivalent est un canal gaussien à entrée binaire cE2± et à sortie réelle prenant toutes les valeurs entre -∞ et +∞, selon une loi gaussienne. La sortie du canal gaussien est décrite par l’échantillon reçu r=I+b où I est le symbole de la modulation BPSK et b est un bruit réel additif blanc gaussien de variance N0. En présence d’évanouissements dus aux trajets multiples, le canal gaussien est remplacé par un canal de Rayleigh à évanouissements indépendants décrit par r=αI+b, où l’évanouissement réel positif suit la loi de probabilité p(α)=2α e -α2.

Les performances du décodage à décisions souples dépassent largement celles du décodage à décisions dures. Généralement, l’absence de valeurs de confiance à l’entrée du décodeur génère une perte de 2 à 3 dB environ sur un canal gaussien et beaucoup plus sur un canal de Rayleigh (la valeur exacte dépend de l’ordre de diversité). Les limites théoriques du décodage dur et du décodage souple sont fixées par la capacité du canal BSC et du canal gaussien respectivement. La Figure 4 présente la capacité de différents canaux exprimés en bits/dimension en fonction du rapport signal-à-bruit Eb/N0 exprimé en décibels (dB). D’après les courbes de capacité, il n’existe aucun code capable de faire tendre le taux d’erreur vers 0 si Eb/N0 est inférieur à –1.6dB (en soft ) et +0.4dB (en hard). Les mêmes courbes nous renseignent aussi sur la valeur minimale du rapport signal-à-bruit pour un rendement fixé, e.g. (Eb/N0 )min = 0.2dB pour R=0.5 bit d’information/dimension sur un canal gaussien. La perte en capacité avec et sans évanouissements est de l’ordre de 2.5 dB pour les grandes valeurs de l’efficacité spectrale (R>1.0).

-2 -1 0 1 2 3 4 5 6 7 8Eb/N0 (dB)

0.0

0.5

1.0

1.5

2.0

Capa

cite

(bits

/dim

)

BSC / Modulation BPSK

Entree et sortie gaussiennes Rayleigh

AWGN / Modulation BPSK

Figure 4 : La capacité en bits par dimension fonction du rapport signal-à-bruit.


1.2. L’alphabet du code. Les symboles d’un code correcteur d’erreurs appartiennent à un alphabet fini A ayant q éléments. Dans la majorité des cas, cet alphabet fini est mathématiquement muni de la structure d’un corps. Ainsi, l’alphabet contient un élément neutre 0 pour l’opération d’addition + et un élément neutre 1 pour l’opération de multiplication ×. Tout élément β de A admet un opposé -β, et tout élément non nul de A admet un inverse β-1. Ce corps fini à q éléments sera noté GF(q) dans la suite de l’exposé (GF pour Galois Field). La taille de l’alphabet GF(q), résultat direct de l’algèbre des corps de Galois, est de la forme q=pm, avec p premier et m entier positif. p est la caractéristique du corps et pour tout élément β du corps, la somme β +β +...+β (p fois) est nulle. Tout corps GF(q) admet au moins un élément primitif α qui génère le groupe multiplicatif GF(q)-{0}. Ainsi, tout élément non nul s’écrit comme une puissance de l’élément primitif. L’ordre de α est égal à q-1, i.e. q-1 est le plus petit entier tel que αq-1=1. L’ordre d’un élément β=αi est égal à (q-1)/pgcd(q-1,i). Un résultat dérivé des propriétés des corps finis et très utile pour l’étude des codes cycliques est la factorisation :

∏−∈

− −=−}0{)(

1 )(1qGF

q xxβ

β

La construction des corps de Galois GF(q) se base sur l’anneau des entiers Ζ ou sur l’anneau des polynômes GF(p)[x]. Notons que GF(p) est le plus petit sous-corps de GF(q) lorsque q=pm. Considérons l’ensemble des q entiers {0,1,...,q-1}. Munissons cet ensemble d’une addition et d’une multiplication modulo q. On obtient un anneau quotient, noté Ζ/qΖ. L’anneau quotient Ζ/qΖ est un corps si et seulement si q est un nombre premier. Dans ce cas, Ζ/qΖ est égal à GF(q) (q=p et m=1) puisque deux corps finis ayant le même nombre d’éléments sont isomorphes. La construction de GF(q) à partir de Ζ/qΖ n’est pas très intéressante, il est plus utile de construire les corps de Galois à partir des anneaux de polynômes. En effet, soit p(x) un polynôme premier de degré m de GF(p)[x]. Ce dernier est l’anneau des polynômes à coefficients dans GF(p). Nous pouvons construire le corps quotient GF(p)[x]/p(x), qui contient pm éléments (pm polynômes de degré inférieur ou égal à m-1). Ce corps n’est autre que GF(pm) puisqu’il est d’ordre fini pm. Lorsque le monôme x est un élément primitif, le polynôme irréductible p(x) est dit polynôme primitif. Nous décrivons ci-dessous la construction des corps GF(4), GF(8) et GF(16), extensions du corps de base GF(2). Notons que tous les systèmes de télécommunications utilisent une représentation binaire ou issue du binaire ce qui limite l’intérêt pratique des corps de Galois au cas p=2. Rappelons que le corps GF(2) est constitué des deux éléments 0 et 1 où les opérations se font modulo 2. Construction de GF(4) : q=4 p=2 m=2 p(x)=x2+x+1 GF(4)=GF(2)[x]/p(x) où toutes les opérations s’effectuent modulo p(x) GF(4)={0, α0=1, α1=x, α2=x+1} et on a x3+1=(x+1)(x2+x+1) Construction de GF(8) : q=8 p=2 m=3 p(x)=x3+x+1 GF(8)=GF(2)[x]/p(x) où toutes les opérations s’effectuent modulo p(x) GF(8)={0, α0=1, α1=x, α2= x2, α3= x+1, α4= x2+x, α5= x2+x+1, α6= x2+1} et on a x7+1=(x+1)(x3+x+1)(x3+x2+1) Construction de GF(16) : q=16 p=2 m=4 p(x)=x4+x+1 GF(16)=GF(2)[x]/p(x) où toutes les opérations s’effectuent modulo p(x) GF(16)={0, α0=1, α1=x, α2=x2, α3=x3, α4=x+1, α5=x2+x, α6=x3+x2, α7=x3+x+1, α8=x2+1, α9=x3+x, α10=x2+x+1, α11=x3+x2+x, α12=x3+x2+x+1, α13=x3+x2+1, α14=x3+1} et on a x15+1=(x+1)(x2+x+1)(x4+x+1)( x4+x3+1)( x4+x3+ x2+x+1) La recherche des polynômes primitifs utilisés dans la construction des corps de Galois, mais aussi pour la génération des séquences pseudo-aléatoires ainsi que pour la construction des codes récursifs constituant les

Joseph J. Boutros 7

turbo codes, s’effectue de deux façons différentes : un tirage aléatoire suivi d’un test de primalité, ou une factorisation du polynôme xn+1 par la méthode de Berlekamp ou Cantor-Zassenhaus. L’étude de la structure d’un code correcteur et son décodage à décisions dures sont effectués dans l’espace GF(q)n muni de la distance de Hamming. Cette distance est égale au nombre de composantes différentes entre deux vecteurs de longueur n :

∑=

≠==n

iiiiiHH yxdenombreyxdyxd

0),(),(

Considérons par exemple les deux vecteurs quaternaires (q=4) de longueur 5, x=(1, 2, 0, 0) et y=(1,2,3,3). Dans ce cas, la distance de Hamming dH(x,y) est égale à 2. Remarquons que dH(x,y)=dH(x-y,0). Par suite, nous définissons le poids de Hamming WH(x) d’un mot x

0)0,()( ≠== iHH xdenombrexdxW e.g. le mot binaire (q=2) de longueur 5, x=(1,1,00,1) est de poids de Hamming 3.

2. Les Codes en Blocs Linéaires Les premières recherches de bons codes correcteurs d’erreurs entamées à la fin des années 40 concernaient des suites de symboles organisés par paquets. Un paquet de symboles de longueur finie est dit bloc. Afin de pouvoir utiliser des outils mathématiques efficaces, les chercheurs ont imposé la contrainte de linéarité aux codes correcteurs structurés en blocs. 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. Les codes linéaires sont décrits de trois manières différentes. Après la définition des principaux paramètres d’un code au premier sous-paragraphe, les codes en blocs linéaires seront décrits comme des espaces vectoriels contruits à partir d’un corps de Galois. Ce sous-paragraphe repose donc sur des outils simples d’algèbre linéaire. Une classe particulière de codes linéaires dits codes cycliques est étudiée au troisième sous-paragraphe En effet, la contrainte de cyclicité ajoutée à celle de linéarité engendre une famille très efficace de codes correcteurs. La description matricielle est remplacée par une description polynômiale. Enfin, le quatrième sous-paragraphe étudie une description graphique d`un code en blocs. L’outil graphique s’avère parfois très puissant et s’appliquera aussi aux codes convolutifs de longueur infinie.

2.1 Principaux Paramètres Nous exposons de façon très directe et concise la plupart des paramètres associés à un code en blocs. Les définitions et les théorèmes présentés ne constituent en aucun cas un exposé complet sur les codes qui nécessiterait des milliers de pages. Définition 1 (Code en Blocs) Un code en blocs C de taille M=qk, défini sur un alphabet de q symboles, est un ensemble de M vecteurs appelés mots de code. Les vecteurs sont de longueur n et leurs composantes sont q-aires. Ainsi, selon la définition ci-dessus, un code est une application bijective qui associe à chaque vecteur formé de k symboles q-aires (k symboles d’information), un vecteur image de longueur n avec des composantes dans le même alphabet (n symboles codés). Le code ajoute au débit initial n-k symboles supplémentaires. La quantité

nkR = bits d’info/bits codés

n’est autre que le rendement de C, appelé aussi taux de codage. L’opération de codage en blocs est sans mémoire, i.e. les blocs sont codés de manière indépendante sans aucune corrélation entre deux blocs consécutifs. Les deux paramètres n et k sont respectivement appelés la longueur et la dimension du code C. Sauf quelques exceptions rares, l’alphabet du code est un corps de Galois GF(q) appelé le corps des symboles. Souvent, les codes sont binaires et le corps des symboles est le simple ensemble GF(2)={0, 1}. Dans la suite de ce chapitre, un code en blocs C respectant la définition 1 sera noté [n,k]q.


Exemple : Considérons le code de Hamming binaire [7, 4]2, où n=7, k=4, q=2. Le code contient qk=16 mots de code de longueur 7 bits chacun. Voici la liste des mots de code :

0000 000 0001 011 0010 110 0011 101 0100 111 0101 100 0110 001 0111 010

1000 101 1001 110 1010 011 1011 000 1100 010 1101 001 1110 100 1111 111

Table 1. Le code de Hamming [7, 4]2 Définition 2 (Code Linéaire) Un code linéaire de longueur n est un sous-espace vectoriel de dimension k de l’espace GF(q)n. Le code [7, 4]2 de l’exemple précédent est linéaire. En effet, c’est un sous-espace vectoriel de dimension 4 de l’espace GF(2)7 : le mot 0=(0000000) appartient au code et la somme de deux mots de code appartient également au code. L’ajout de la contrainte de linéarité pourrait nuire à la qualité du code recherché, mais heureusement l’étude des performances d’ensemble montre que les codes linéaires sont très proches des meilleurs codes en blocs. Ainsi, la linéarité facilite l’étude des codes en blocs et permet l’utilisation d’outils algébriques très puissants, sans réduire la classe des codes linéaires à une classe inefficace. Nous supposons que le lecteur est capable de déduire plusieurs caractéristiques des codes linéaires à partir des propriétés algébriques des espaces vectoriels et des groupes sous-jacents. Définition 3 (Distance Minimale) Soit C[n,k]q un code en blocs. La distance de Hamming minimale de C est définie par :

),()( ,min yxdMinCd HCyxH ∈= Lorsque le code est linéaire, il est clair que la distance minimale est égale au poids de Hamming minimal car dH(x,y)=dH(x-y,0)=WH(x-y). En plus la distribution des distances autour du mot 0 sera parfaitement identique à la distribution des distances autour de n’importe quel mot de code non nul. Le code en blocs linéaire devient ainsi un ensemble géométriquement uniforme dans l’espace de dimension n. Toujours dans l’exemple précédent, la distance minimale du code [7,4] est égale à 3. Le lecteur vérifiera que tous les mots diffèrent de 3 symboles au moins, ou de manière équivalente, que le poids minimal est égal à 3. En général, un code [n,k]q de distance minimale d sera noté [n,k,d]q. Sachant que les mots de code les plus proches sont espacés de dHmin, nous pouvons introduire un nombre ν d’erreurs (modifier ν symboles dans le mot) en restant capable de retrouver le mot de code initial. En effet, si

[ 2)1( min −=≤ Hdt ]ν , le mot modifié (le mot erroné) reste dans la boule de rayon t centrée sur le mot initial. Le code est donc capable de corriger au maximum t symboles erronés situés dans le même mot de code. En plus, si nous modifions au maximum dHmin-1 symboles dans le mot initial, ceci ne le transforme pas en un deuxième mot de code. Nous sommes ainsi capable de détecter la présence au maximum de T=dHmin-1 symboles erronés dans un même mot de code. La définition suivante en découle. Définition 4 (Capacité) Les deux quantités [ ]2)1( min −= Hdt et 1min −= HdT sont respectivement appelées capacité de correction et capacité de détection d’un code correcteur d’erreurs. La capacité de correction du code n’est pas dépassée si le nombre effectif ν d’erreurs dans le mot erroné vérifie

min1212 Hdt ≤+≤+ν . Dans certains canaux de transmission, le démodulateur informe le décodeur sur l’état

Joseph J. Boutros 9

suspect d’un symbole. Ce symbole sera déclaré effacé ou non fiable. Algébriquement, un effacement correspond à une erreur de position connue, mais d’amplitude inconnue appartenant à GF(q). Une erreur au sens exact a une position inconnue et une amplitude inconnue appartenant à GF(q)-{0}. Il est évident que la capacité d’un code à remplir des effacements est égale à sa capacité de détection. En combinant les deux capacités (correction+effacement), nous pouvons dire que la capacité totale d’un code n’est pas dépassée si

min12 Hd≤++ ρν où ν est le nombre d’erreurs et ρ est le nombre d’effacements. Un décodeur capable de corriger des erreurs et de remplir des effacements à la fois présente des meilleurs performances qu’un décodeur sans effacement (purement hard). Cependant, il reste moins efficace qu’un décodeur à entrée souple qui prend ses décisions selon la métrique euclidienne calculée entre le mot reçu et tous les mots de code.

2.2 Représentation Matricielle Dans le cas d’un code linéaire, et selon la définition 2, tout mot de code est une combinaison linéaire de k mots de code formant la base de C. Donc, Cc ∈∀ , nous pouvons écrire kk guguguc +++= ...2211 , où les coefficients ui appartiennent au corps des symboles GF(q) et les mots gi sont les k mots de code de la base. Définition 5 (Matrice génératrice) Soit C un code linéaire [n,k,d]q et soit {g1,g2,...,gk} la base de C. La matrice génératrice de C est une matrice k×n dont les lignes sont formées par les vecteurs gi de la base. Selon la définition ci-dessus, nous avons G=[gij], nji ≤≤ ,1 , gi=[gi1,gi2,...,gin]. Soit u=(u1,u2,...,uk) le mot d’information, i.e. le vecteur contenant les k symboles d’information. Alors nous pouvons écrire la relation matricielle liant le mot de code c et le mot d’information u :

uGc = Définition 6 (Code Systématique) Soit C un code en blocs [n,k,d]q. Ce code est dit systématique si tous les mots de code contiennent les k symboles d’information non modifiés. Les n-k symboles restants sont appelés symboles de parité. La matrice génératrice d’un code systématique est de la forme G=[I|P], où I est la matrice identité k×k et P est une matrice de type k×(n-k) qui dépend du code. Cette forme systématique de la matrice G peut être obtenue à partir de n’importe quelle forme non-systématique sans modifier le code linéaire C, tout simplement en appliquant des permutations de colonnes et des opérations dans GF(q) sur les lignes. Par la suite, nous pouvons dire que tout code en blocs linéaire est équivalent à un code systématique. Exemple : Rappelons que la base d’un espace vectoriel n’est pas unique, d’où la possibilité d’avoir plusieurs matrices génératrices pour un même code C. Une base possible du code [7, 4, 3]2 est formée de 4 vecteurs bien choisis dans la table 1. Ainsi, nous construisons comme exemple deux matrices génératrices où la deuxième est sous forme systématique :

=

1111111100011010111001101000

1G

=

1101000011010011100101010001

2G

Définition 7 (Matrice de Parité) Soit H une matrice (n-k)×n à éléments dans GF(q), qui vérifie cHt=0 pour tout mot c d’un code linéaire C. Alors, H est dite matrice de parité du code C. Remarquons que H est orthogonale à G, puisque la définition ci-dessus implique GHt=0. Lorsque G est systématique et si GF(q) est de caractéristique p, nous pouvons prendre comme matrice de parité la forme simple H=[(p-1)Pt|I].


Exemple : Les matrices de parité associées aux deux matrices génératrices G1 et G2 du code [7,4,3]2 sont

==

100101101011100010111

21 HH

Théorème 1 (Les colonnes de H) Le code linéaire C[n,k,d]q contient un mot de poids égal à w si et seulement si la matrice de parité possède w colonnes linéairement indépendantes. Preuve. Supposons qu’il existe un mot de code c de poids w, alors l’égalité cHt=0 nous fournit une combinaison linéaire nulle de w colonnes de H. La réciproque se démontre en formant un mot de code à partir des coefficients de la combinaison linéaire des w colonnes dépendantes. CQFD. Le théorème ci-dessus s’applique facilement à la matrice de parité du code [7,4]2 pour vérifier que la distance minimale est égale à 3. Ce code est donc capable de corriger 1 bit erroné sur les 7 bits constituant un mot. Considérons maintenant l’ensemble C⊥ des mots de GF(q)n qui vérifient

∑=

⊥∈∈∀=>=<n

iii CyetCxyxyx

10,

Il est trivial de montrer que C⊥ est un code. Ce code est le complément orthogonal de C, ou le dual de C. Il contient donc tous les mots de GF(q)n orthogonaux (produit scalaire nul) aux mots du code C. Si G (respectivement H) est la matrice génératrcie (respectivement de parité) du code C [n,k]q, alors H (respectivement G) est la matrice génératrice (respectivement de parité) du code C⊥. Ceci prouve que le code dual est un code de longueur n et de dimension n-k, i.e. C⊥[n,n-k]q. Notons enfin que l’espace entier GF(q)n n’est pas nécessairement la somme directe de C et de son dual, ceci est toujours vrai dans le corps des complexes mais non vrai dans les corps finis.

2.3 Représentation Polynômiale Dans la famille des codes linéaires, il existe une classe très importante, celle des codes en blocs linéaires et cycliques. Dans un code cyclique, toute opération de décalage cyclique appliquée à un mot de code fournit un autre mot de code. La représentation vectorielle et matricielle des codes linéaires est remplacée par une représentation polynômiale. En effet décaler un mot de code d’une case revient à multiplier le polynôme par l’indéterminée x et prendre le reste modulo xn-1. Ainsi, il suffit d’additionner ou de multiplier des polynômes tout en restant dans l’anneau quotient modulo xn-1, i.e. l’anneau GF(q)[x]/(xn-1). Voici la définition exacte d’un code cyclique. Définition 8 (Code Cyclique) Un code cyclique est un idéal de l’anneau GF(q)[x]/(xn-1). La définition ci-dessus se traduit par les deux propriétés suivantes vérifiées par un code cyclique : − C est un sous-groupe additif de GF(q)[x]/(xn-1). − si c(x)∈C et a(x)∈GF(q)[x]/(xn-1), alors a(x)c(x)∈C. Théorème 2 (Polynôme Générateur) Soit C un idéal de GF(q)[x]/(xn-1), i.e. un code linéaire cyclique de longueur n. Alors 1. Il existe un et un seul polynôme unitaire g(x) de degré minimal dans C. 2. C est un idéal principal généré par g(x). 3. g(x) est un facteur de xn-1.

Joseph J. Boutros 11

4. Tout c(x)∈C s’écrit de manière unique c(x)=u(x)g(x) dans GF(q)[x], avec deg(u(x))<n-r et r=deg(g(x)). La dimension de C est égale à n-r, i.e. r=deg(g(x))=n-k.

5. Si le polynôme générateur est donné par g(x)=g0+g1x+...+grxr, alors le code C est généré comme sous-

espace de GF(q)n par la matrice :

=

=

−−

)()(

...)(

...00...0

......0... 1

01

01

01

xgxxg

xgx

gggggg

ggg

G

rn

r

r

r

Preuve. 1. Soit g(x) le polynôme non nul de C de degré minimal r. Nous pouvons toujours transformer g(x) en un

polynôme unitaire en inversant le coefficient dominant. Supposons qu’il existe un deuxième polynôme unitaire f(x) de degré minimal r. La différence g(x)-f(x) appartient à C et a un degré inférieur à r. Ceci contredit le fait que r est minimal. Donc g(x) est unique.

2. Soit c(x)∈C. Par division euclidienne, nous pouvons écrire c(x)=u(x)g(x)+r(x) avec deg(r(x))<deg(g(x)). Mais r(x)=c(x)-u(x)g(x) )∈C. Ceci est une contradiction sauf si r(x)=0.

3. Ecrivons xn-1=h(x)g(x)+r(x) dans GF(q)[x], avec deg(r(x))<deg(g(x)). En se plaçant dans GF(q)[x]/(xn-1) nous obtenons r(x)=-h(x)g(x)∈C. Donc r(x)=0.

4 et 5. D’après 2., tout mot de code c(x) est de la forme c(x)=u(x)g(x) dans l’anneau quotient GF(q)[x]/(xn-1). Mais deg(c(x))<n et la même expression reste donc valable dans GF(q)[x]. Ainsi, le code est formé de tous les polynômes multiples de g(x). Les n-r mots g(x),xg(x),...,xn-r-1g(x) sont linéairement indépendants et génèrent tous les mots de code. Ils forment donc les lignes de la matrice génératrice. La dimension du code est égale à k=n-r.

CQFD. Définition 9 (Polynôme de Parité) D’après le théorème 2, xn-1=h(x)g(x) où g(x) est le polynôme générateur du code cyclique C de longueur n. Le polynôme h(x) de degré k, quotient de xn-1 par g(x), est dit polynôme de parité du code C. Théorème 3 (Dual d’un Code Cyclique) Soit C[n,k]q un code linéaire cyclique. Alors son dual C⊥ est cyclique et il est généré par le polynôme g⊥ (x)=xkh(x-1). Preuve. D’après la définition 9, on a h(x)g(x)=xn-1=0 dans l’anneau GF(q)[x]/(xn-1). Pour tout mot de code

c(x)=u(x)g(x), on a c(x)h(x)=u(x)h(x)g(x)=0. Nous obtenons donc un produit de convolution nul,

pour j=0,1,..,n-1. Construisons la matrice suivante :

∑−

=− =

1

00

n

iijihc

=

=

−−

)()(

...)(

...00...0

......0... 1

01

01

01

xhxxh

xhx

hhhhhh

hhh

H

kn

k

k

k

La nullité du produit de convolution se traduit par cHt=0. H est bien la matrice de parité du code C. En comparant avec la forme de G dans le théorème, nous concluons que h(x) est le polynôme générateur du code dual si les symboles sont lus à l’envers. C’est-à-dire que h(x) est le polynôme générateur d’un code équivalent à C⊥ et que C⊥ est un code cyclique. Sinon, en gardant les symboles du code dans le même ordre mais en inversant les coefficients de h(x), nous pouvons dire que C est généré par le polynôme xkh(x-1). CQFD.


Définition 10 (Syndrome) Soit C [n,k]q un code linéaire. Soit v=(vn-1,...,v1,v0)=v(x) un mot quelconque de GF(q)n ou de GF(q)[x]. Nous appelons syndrome de v : 1. Code linéaire de matrice de parité H. Syndrome matriciel :

le vecteur s=(sn-k-1,...,s1,s0)=vHt 2. Code cyclique de polynôme générateur g(x). Syndrome polynômial :

le polynôme s(x)= sn-k-1xn-k-1+...+s1x+s0=v(x)modulo g(x) 3. Code cyclique où β1,β2,...,βn-k ∈GF(q) sont les n-k racines de g(x), GF(q)⊂GF(Q). Syndrome algébrique :

les n-k quantités Sj=v(βj) ∈GF(q), j=1,2,...,n-k. Les syndromes sont utilisés dans les algorithmes de décodage à décisions dures d’un code en blocs. En effet, si v=c+e, où c est un mot de code et e un vecteur d’erreur, alors s=vHt=cHt+eHt=eHt. Le syndrome ne dépend que de l’erreur et pourra être utilisé pour déterminer e. De la même façon, sachant que c(x)=0 modulo g(x) et que c(βj)=0, losrque v(x)=c(x)+e(x) on a s(x)=e(x) modulo g(x) et Sj=e(βj). Les algorithmes à décisions souples n’utilisent pas les syndromes. D’ailleurs la notion d’erreur (en sortie du canal) n’existe plus dans ce type d’algorithmes car l’entrée du décodeur est représentée par des nombres réels.

3. Les Codes Convolutifs

Les codes convolutifs forment une classe extrêmement souple et efficace de codes correcteurs d’erreurs. Ce sont les codes les plus utilisés dans les systèmes de télécommunications fixes et mobiles. Théoriquement, ils ont les mêmes caractéristiques que les codes en blocs sauf pour la valeur de leur dimension et leur longueur. Les codes convolutifs s’appliquent sur des séquences infinies de symboles d’information et génèrent des séquences infinies de symboles codés. Depuis l’invention des turbo codes en 1993, nous groupons les codes en blocs et les codes convolutifs dans une même classe. La plupart des algorithmes récents de codage et de décodage blocs et convolutifs, ainsi que la description de la structure des codes sont très similaires. Tout code convolutif est facilement convertible en un code en blocs par troncature ou par terminaison de son treillis. Ceci est souvent le cas dans les systèmes de transmissions radiomobiles et cablés où l’information est organisée par paquets. Dans la suite de cet exposé, nous limitons notre étude aux codes convolutifs linéaires binaires, i.e. définis sur le corps GF(2). La généralisation des résultats aux codes non binaires est immédiate.

3.1 Représentation Polynômiale et Matricielle La construction des codes convolutifs est directement inspirée de la structure des codes en blocs linéaires cycliques. Considérons la matrice génératrice suivante :

=

MMM

L

L

110111110111

110111110111

G

La matrice G est de taille infinie. Elle s’obtient en décalant d’une ligne à l’autre le motif 11 10 11 de 2 colonnes. Sa forme ressemble à celle d’un code cyclique défini au théorème 2. Cette matrice génère un code linéaire binaire de longueur infinie et de dimension infinie dont le rendement est égal à ½. En effet, le codeur associé à G se réalise facilement à l’aide d’un registre à décalage de mémoire 2, 5 connexions et 2 additionneurs. La figure 1 montre la structure de ce codeur.


e

s1

s2

T T

Figure 1 : Codeur convolutif (7,5) non récursif non systématique, R=1/2, L=3. Il est possible de généraliser la forme de la matrice G en remplaçant le motif 11 10 11 par une sous-matrice binaire de k lignes et de n×L colonnes. Des copies de cette sous-matrice sont placées tout le long de la diagonale de G avec des décalages de n colonnes. Le code linéaire binaire infini de rendement R=k/n défini par G est appelé code convolutif et nécessite k registres à décalage. L’exemple de la figure 1 correspond à un code convolutif non systématique. Le code est non récursif car les bits de sortie ne sont pas réinjectés dans le registre à décalage. La longueur du registre à décalage, notée L, est dite longueur de contrainte. Nous appelons mémoire du code la quantité ν=L-1. Structure d’un code convolutif non récursif La sortie d’un codeur convolutif à l’instant t dépend de l’entrée à l’instant t et de l’état du codeur défini par le contenu de son registre. L’exemple de la figure 1 montre un code convolutif à 4 états possibles car ν=2 bascules. Sachant que l’entrée est constituée de k=1 bit, il existe donc deux transitions possibles partant et arrivant à chaque état. Le cas d’un code convolutif général avec k et ν quelconques se déduit aisément :

Etat du codeur = k×ν Nombre des états = 2kν Une transition = k bits

Nombre des transitions par état = 2k Nombre total des transitions = 2 k×2kν=2kL

L’entrée du codeur convolutif est formée de k bits à un instant donné, ou de k séquences infinies pour t=0...+∞. Les k entrées binaires du codeur sont indexées par i, où i=1...k. La séquence infinie associée à une des entrées s’écrit comme une série en x, où x symbolise un retard d’une période T. Les coefficients de la série sont les bits de l’entrée correspondante.

∑+∞

==

0)(

l

llxexe ii i=1..k

Le coefficient est le bit présent à l’entrée numéro i du codeur à l’instant . De la même façon les n sorties binaires du codeur sont indexées par j et s’écrivent comme une série en x.

lie l

∑+∞

==

0)(

l

llxsxs jj j=1..n

Nous définissons le polynôme générateur gij(x) qui lie l’entrée i à la sortie j. Le polynôme gij(x) est de degré inférieur ou égal à L-1. Le coefficient d’indice r du polynôme est égal à un 1 si une connexion existe entre la sortie j et le r-ième bit du ième registre du codeur. Le code de la figure1 est défini par deux polynômes générateurs g1(x)=1+x+x2 et g2(x)=1+x2. L’indice i est souvent omis lorsque k=1. La notation octale est utilisée fréquemment, e.g. 1+x+x2 est remplacé par 7 et 1+x2 par 5, d’où la notation concise (7,5) qui intègre tous les paramètres du code. Les sorties se calculent en fonction des entrées à l’aide des polynômes générateurs gij (x) :

( ) ∑=

=k

iijij xgxexs

1)()( j=1...n

Soient E et S les vecteurs définis par E=[e1(x),e2(x),...,ek(x)] et S=[s1(x),s2(x),...,sn(x)]

Le vecteur de sortie s’exprime en fonction du vecteur d’entrée : S=EG

où G est la matrice génératrice définie par


=

)()()(

)()()()()()(

21

22221

11211

xgxgxg

xgxgxgxgxgxg

G

knkk

n

n

L

MMMM

L

L

Structure d’un code convolutif récursif Le code convolutif devient récursif lorsque les polynômes générateurs sont remplacés par des fractions de deux polynômes. Ainsi, une partie de la sortie est réintroduite dans le registre à décalage selon des connexions définies par les polynômes situés au dénominateur. Il est possible ainsi de construire toute sorte de codes convolutifs récursifs. Parmi ces derniers, les seuls codes présentant un intérêt théorique et pratique sont les codes récursifs systématiques de rendement k/(k+1). Ces codes seront appelés RSC (Recursive Systematic Convolutional Codes). Les codes non récursifs, toujours considérés non systématiques afin de garantir une bonne distance minimale, seront appelés NRNSC (Non Recursive Non Systematic Convolutional Codes). Considérons le code RSC de la figure 2. Ce code est obtenu par simple modification du code NRNSC de la figure 1. En effet, le premier code convolutif est défini par les deux équations s1(x)=(1+x+x2)e(x) et s2(x)=(1+x2)e(x), ou de manière équivalente s1(t)=e(t)+e(t-1)+e(t-2) et s2(t)=e(t)+e(t-2), où sj(t)= sjt et e(t)=et. Après division par g1(x)= 1+x+x2, nous obtenons le code RSC de la figure 2 défini par les équations :

)(1

1)()()( 2

2

01 xexx

xxsxexs++

+==

ou de manière équivalente s1(t)=e(t) et s0(t)= e(t)+e(t-2)+s0(t-1)+s0(t-2).

T T

e s1

s0

Figure 2 : Code convolutif récursif (1,5/7), R=1/2, L=3. De manière similaire à un code NRNSC, la sortie d’un codeur convolutif RSC à l’instant t dépend de l’entrée à l’instant t et de l’état du codeur défini par le contenu de son registre. Quelque soit la valeur de k, un seul registre suffit pour la construction du codeur (construction dite canonique). Un code RSC ajoute un seul bit de parité aux k bits d’information de l’entrée, i.e. R=k/(k+1). L’exemple de la figure 2 montre un code RSC à 4 états. Le cas d’un code RSC avec k et ν quelconques se déduit aisément :

Etat du codeur = ν Nombre des états = 2ν Une transition = k bits

Nombre des transitions par état = 2k Nombre total des transitions = 2 k×2ν=2k+ν

Le code RSC est défini par n=k+1 polynômes générateurs, g0(x), g1(x),...,gk(x) :

)()()(

)(...1)()(1 0

0 xexgxg

xsetkixexs ik

i

iii ∑

====

4.2 Représentation en Treillis L’idée d’une représentation graphique d’un code convolutif provient des caractéristiques markoviennes de la sortie du codeur. Les graphes équivalents à la représentation polynômiale sont souvent plus faciles à manipuler et permettent de dériver des résultats plus puissants. Tout code convolutif est représenté par trois graphes équivalents mais différents : l’arbre du code, le treillis du code et le diagramme d’états.


L’arbre est un graphe de hauteur et de largeur infinies. Un noeud dans l’arbre représente un état possible du codeur. Une branche symbolise une transition d’un état à l’autre. Classiquement l’arbre commence à son sommet par l’état 0 (le registre à décalage est initialisé à 0). Tout chemin dans l’arbre du code est une séquence possible (un mot de code) à la sortie du codeur convolutif. Le treillis est obtenu en repliant l’arbre sur sa largeur. Le diagramme d’états est à son tour construit en repliant le treillis sur sa longueur. Incontestablement, le treillis est l’outil graphique le plus performant pour caractériser un code et concevoir des algorithmes de décodage. Nous illustrons ci-dessous le treillis des deux codes NRNSC (7,5) et RSC (1,5/7) à 4 états. Cas du code NRNSC R=1/2, g1=7 g2=5 : notons a=00, b=01, c=10, d=11 les 4 états possibles du codeur convolutif. Les deux bits constituant l’indice de l’état ne sont autres que les deux bits contenus dans le registre à décalage. Supposons que le codeur est dans l’état a à l’instant t=0. Deux transitions partent de l’état a, la première a → a correspond à une entrée e=0 et une sortie s=00 ; la seconde a → c correspond à une entrée e=1 et une sortie s=11. Ces deux transitions restent valables à n’importe quel instant t dans le treillis. De la même façon, deux transitions partent de l’état c, la première c → b est produite par une entrée e=0 et génère une sortie s=10 ; la deuxième c → d correspond à e=1 et s=01. Ce raisonnement permet de dessiner le treillis du code NRNSC entre t=0 et t=+∞. Notons que le treillis devient périodique à partir de la 3ème étape où l’on retrouve les 8 transitions entre les 4 états. En général, le treillis d’un code convolutif devient répétitif après L=ν+1 étapes. Le treillis illustré figure 3 indique les deux bits de sortie sur chaque branche. La valeur de l’entrée est occultée puisqu’une branche descendante correspond à e=1 et une branche montante à e=0.

00

11

00 00 0000

00 0000

11 1111

11 11

11

11

10 10 10 10

10 10 10

01 01 01 01

01 01 01

Etats

a=00

b=01

c=10

d=11

Figure 3: Treillis des deux codes convolutifs (7,5) et (1,5/7). Les mots du code (7,5) sont tous les chemins possibles dans le treillis. Il est facile de vérifier que le code est linéaire, i.e. le chemin 00...0 appartient au treillis et la somme de deux chemins est un troisième chemin dans le treillis. Le chemin a → c → b → a possède le poids de sortie minimal WHmin=5. Nous en déduisons que la distance minimale dHmin (aussi appelée distance libre dfree) du code convolutif (7,5) est égale à 5. Cas du code RSC R=1/2, g0=7, g1=5 : les 4 états a, b, c, d sont notés de manière similaire à ceux du code NRNSC. La structure du treillis est parfaitement identique : deux branches arrivent et partent de chaque état. Le treillis devient périodique à la 3ème étape, lorsque toutes les transitions sont tracées. La différence entre le code récursif et non récursif réside dans l’étiquetage binaire des branches. En effet, sachant que le code RSC est systématique, le 1er bit de sortie est égal à l’entrée. Ainsi les deux bits associés à une branche du treillis de la figure 3 représente toujours les deux bits de sortie et la valeur de l’entrée est contenue dans le 1er bit. Par exemple, la transition c → b correspond à e=1 et à s=10. Remarquons que la distance minimale de ce code RSC est elle aussi égale à 5 et se déduit du chemin a → c → b → a. Une entrée non nulle permet de quitter l’état 0 dans les deux cas récursifs et non récursifs. En revanche, une entrée nulle n’est pas suffisante pour revenir à l’état 0 dans le cas du code RSC, e.g. le retour b → a est généré par e=0 pour le code NRNSC, et par e=1 pour le code RSC.


Transformation d’un code convolutif Considérons un code convolutif binaire récursif ou non récursif de rendement R=k/n et de mémoire quelconque. Durant u étapes dans le treillis, le codeur reçoit k×u bits d’information et délivre n×u bits codés. Parmi ces bits codés, v sont supprimés et n×u-v sont émis sur le canal. Cette opération, appelée perforation du code convolutif, transforme le rendement R=k/n en un rendement R’=(k×u)/(n×u-v). Par exemple, un code convolutif de rendement 1/2 est facilement converti par perforation en un code de rendement 2/3 (u=2 v=1) ou un rendement 3/4 (u=3,v=2). Tout code convolutif est convertible en un code en blocs. Il suffit de stopper l’avance dans le treillis après un nombre de branches fixé par la longueur du code en blocs recherché. Une méthode triviale consiste à couper le treillis sans spécifier l’état final (troncature). La bonne méthode transforme le code convolutif en un code en blocs en forçant le retour à l’état 0 par une terminaison du treillis.

4. Performances ML des Codes Correcteurs Nous établissons dans ce paragraphe des bornes théoriques sur la probabilité d’erreur par mot et par bit à la sortie d’un décodeur correcteur d’erreurs. Comme nous l’avons déjà précisé au premier paragraphe, l’étude des performances est limitée à trois types de canaux avec une modulation BPSK : canal BSC, canal gaussien et canal de Rayleigh. Il existe une grande panoplie d’algorithmes de décodage optimal et sous-optimal. Afin de déterminer les performances d’un code liées à sa propre structure et indépendantes de l’algorithme de décodage utilisé, nous supposons que le décodeur est optimal au sens ML, i.e. Maximum Likelihood ou Maximum de Vraisemblance. Ce décodeur ML est physiquement réalisable ou non selon la taille du code et sa complexité. La figure 1 illustre le schéma général du codage de canal où c est le mot de code émis et r est la sortie du canal (observation). Pour des raisons de simplicité, nous considérons seulement un code C linéaire et binaire. Les deux séquences r et c sont de longueur n lorsque C est un code en blocs et elles sont de longueur infinie lorsque C est un code convolutif (n=+∞).

Codeur Canal Décodeurinformationc r

Figure 1 : Schéma de codage de canal. Deux grandeurs probabilistiques permettent de juger de la qualité de service d’un système de communications numériques : la probabilité d’erreur par mot de code Pew et la probabilité d’erreur par bit Peb. Les meilleurs critères d’optimisation appliqués par les décodeurs reviennent à minimiser Pew ou Peb. L’optimisation de Peb est souvent plus difficile et peut s’effectuer dans certains cas particuliers où la probabilité a posteriori (APP) d’un bit est accessible. L’algorithme Forward Backward présenté au paragraphe 5 est capable d’évaluer l’APP d’un bit lorsque le code est représentable par un treillis de complexité raisonnable. Les performances estimées ci-dessous se limitent au cas d’un décodage minimisant la probabilité d’erreur par mot. En effet, la minimisation de Pew est équivalente à la maximisation de la probabilité a posteriori par mot p(c|r). Ce critère est nommé critère MAP, Maximum a Posteriori. En ajoutant l’hypothèse que tous les mots de code sont équiprobables, le critère MAP se réduit au critère ML qui consiste à maximiser la vraisemblance p(r|c). Le critère ML utilisé par un décodeur se traduit de 3 manières différentes selon la nature du canal : − Canal BSC :

),()|( crdMincrpMax HCcCc ∈∈

⇔

Le décodeur optimal au sens ML minimise ainsi la distance de Hamming :

∑=

=n

iiiHH crdcrd

1),(),(

− Canal Gaussien (AWGN) : ),()|( crdMincrpMax E

CcCc ∈∈⇔

Le décodeur optimal au sens ML minimise ainsi la distance euclidienne :

∑∑==

−==n

iii

n

iiiEE crcrdcrd

1

2

1

22 ),(),(


− Canal de Rayleigh : )|,(),|( αα crdMincrpMax E

CcCc ∈∈⇔

Le décodeur optimal au sens ML est supposé connaître la valeur de l’évanouissement et minimise ainsi la distance euclidienne :

∑∑==

−==n

iiii

n

iiiiEE crcrdcrd

1

2

1

22 )|,()|,( ααα

4.1 Performances sur le Canal Gaussien Dans le cas d’un code linéaire, la probabilité d’erreur par mot se calcule en supposant que le mot 00..0 a été

émis. Donc, Pew=Pe|0. En appliquant la borne de l’union , nous pouvons écrire (∑≤

ii

ii APAP U )

( )∑−∈

→≤}0{0

Ccew cPP (4.1)

où P(0→c) est la probabilité d’erreur par paire égale à la probabilité de décoder c lorsque 0 est émis et se calcule en supposant que les deux mots 0 et c sont séparés par un hyperplan médiateur. Lorsque l’entrée du décodeur est ferme (canal BSC), la probabilité d’erreur par paire est majorée par la borne de Bhattacharyya

( ) )()1(40

cWHppcP −≤→ (4.2) Lorsque l’entrée du décodeur est souple (canal gaussien), la probabilité d’erreur par paire est égale à

( )

=→

0

2)(0

NE

cRWQcP bH (4.3)

Il suffit de combiner les formules 4.1, 4.2 et 4.3 pour obtenir une borne supérieure de la probabilité d’erreur par mot dans les deux cas de décisions dures et souples. Le raisonnement ci-dessus montre que la distribution de poids de Hamming d’un code est nécessaire pour estimer ses performances. Par conséquent, nous définissons les quatre fonctions énumératrices de poids suivantes [5][45] : 1. Polynôme énumérateur de poids d’un code en blocs, A(x)

( ) ∑=

=n

i

ii xaxA

0

où le coefficient ai est égal au nombre de mots de code de poids WH=i. 2. Polynôme énumérateur entrée-sortie d’un code en blocs, A(x,y)

( ) ∑ ∑= =

=n

i

n

j

jiij yxayxA

0 0,

où le coefficient aij est égal au nombre de mots de code de poids j correspondant à une entrée de poids i (poids des k bits d’information). 3. Fonction de transfert d’un code convolutif, T(D)

∑+∞

==

0)(

i

ii DaDT

où le coefficient ai est égal au nombre de chemins dans le treillis de poids i. 4. Fonction de transfert entrée-sortie d’un code convolutif, T(I,D)

∑ ∑+∞

=

+∞

==

0 0),(

i j

jiij DIaDIT

où le coefficient aij est égal au nombre de chemins dans le treillis de poids j correspondant à une entrée de poids i.


Codes en Blocs Linéaires Binaires En utilisant le polynôme énumérateur de poids, la borne de l’union sur la probabilité d’erreur par mot pour un canal BSC devient

∑=

−≤n

di

iiew

H

ppaPmin

)1(4 (4.4)

où la probabilité de transition du canal BSC est

=

0

2NRE

Qp b .

La probabilité d’erreur par bit sur le canal BSC se déduit du polynôme énumérateur entrée-sortie en écrivant que le poids de l’entrée i est le nombre de bits erronés parmi les n bits codés :

∑ ∑= =

−≤n

dj

n

i

jijeb

H

ppaniP

min 1)1(4 (4.5)

Si le polynôme énumérateur A(x,y) est difficile à calculer, nous appliquons l’approximation suivante

ewH

eb Pn

dP min≈ (4.6)

De la même façon, la formule 4.7 nous donnent la borne de la probabilité d’erreur par mot pour un décodeur à décisions souples

∑=

≤

n

di

biew

HNE

iRQaPmin 0

2 (4.7)

La probabilité d’erreur par bit d’un décodeur à décisions souples s’obtient toujours par l’approximation 4.6. Codes Convolutifs Linéaires Binaires La fonction de transfert des codes convolutifs joue le même rôle que le polynôme énumérateur de poids des codes en blocs. Il est aisé de retrouver les mêmes expressions. La probabilité d’erreur par bit avec des décisions dures est donnée par

∑ ∑+∞

=

+∞

=−≤

min 1)1(4

Hdj i

jijeb ppa

kiP (4.8)

et la probabilité d’erreur d’un décodeur à décisions souples est majorée par

∑ ∑∞+

=

∞+

=

≤

min 1 0

2

Hdj i

bijeb N

EjRQa

kiP (4.9)

4.2 Performances sur le Canal à Evanouissements La probabilité d’erreur par mot sur un canal à évanouissements indépendants et connus est toujours majorée par la borne de l’union 4.1. Afin de retrouver les expressions finales de Pew et Peb sur le canal de Rayleigh, nous recalculons les probabilités d’erreur par paire P(0 → c) pour une sortie ferme et une sorte souple. Le canal de Rayleigh à sortie ferme est équivalent à un canal BSC avec évanouissements. La formule 4.2 est

toujours valable mais avec une probabilité de transition

04

1

NE

pb

≈ . Ainsi, les expressions de Peb décrites au

sous-paragraphe précédent en fonction de p pour les codes en blocs et les codes convolutifs sont applicables. La probabilité P(0 → c) d’un canal de Rayleigh à sortie souple est la moyenne sur toutes les valeurs des évanouissemenents de la probabilité d’erreur par paire conditionnelle

( ) ( ) )(

01

121)(|00 cW

bH

NE

R

dpcPcP

+

≤→=→ ∫α

ααα (4.10)

La borne ci-dessus nous fournit directement une majoration du taux d’erreur binaire du canal de Rayleigh à sortie souple comme suit :


− pour un code en blocs : ∑=

+

≤n

dii

bi

Heb

H

NE

R

an

dPmin

0

min

1

1 (4.11)

− pour un code convolutif : ∑ ∑+∞

=

+∞

=

+

≤min 1

01

1

Hdj ij

bijeb

NE

R

akiP (4.12)

Exemple 1 Le système radiomobile américain IS-95, basé sur la technique d`accès multiple CDMA, utilise des codes convolutifs binaires non récursifs à 256 états. Le premier code de rendement 1/2 et de générateurs (561,753) est intégré à la liaison descendante. Le deuxième protège la voie montante, il est de rendement 1/3 et les générateurs sont (557,663,711). La grande mémoire L=9 de ces deux codes leur garantit une grande distance minimale, dHmin=12 pour le premier code et dHmin=18 pour le deuxième. La Figure 2 illustre les performances du code (561,753) sur le canal gaussien sans évanouissements.

0.0 1.0 2.0 3.0 4.0Eb/N0 (dB)

10-6

10-5

10-4

10-3

10-2

10-1

100

Pe(

bit)

Borne theorique

Simulation

Figure 2 : Performance du code convolutif R=1/2 à 256 états de la liaison descendante du système américain IS-95,

canal AWGN.

Exemple 2 La couche physique du système GSM est dotée d'un code convolutif binaire permettant de protéger les informations circulant sur les canaux parole et données. Son rendement est égal à 1/2, sa longueur de contrainte 5 et ses générateurs (23,33). Ce code à faible complexité présente une distance minimale dHmin=7. Ses performances estimées par simulation sur ordinateur sont illustrées Figure 3 ci-dessous.


0 1 2 3 4 5 6 7 8Eb/N0 (dB)

10-5

10-4

10-3

10-2

10-1

100

Pe(

bit)

Canal avec evanouissements

Canal gaussien

Figure 3 : Performance du code convolutif R=1/2 à 16 états utilisé dans le système GSM.

5. Algorithmes de décodage. Nous décrivons dans ce pragarphe trois algorithmes de décodage applicables aux codes en blocs et aux codes convolutifs. Ces trois algorithmes effectuent leurs opérations sur le treillis représentant la structure du code [1][5][48][59]. Le premier algorithme décrit ci-dessous est celui de Viterbi [28][56]. C'est un algorithme de décodage à entrée ferme ou souple mais à sortie toujours dure. Le deuxième algorithme [3][34] du sous-paragraphe 5.2 est un Viterbi modifié (SOVA) délivrant une sortie souple. Enfin, le dernier sous-paragraphe présente l'algorithme Forward-Backward [1] capable de calculer la probabilité a posteriori exacte de n'importe quel paramètre lié au treillis du code. C'est un algorithme de décodage à entrée et sortie souples. L'algorithme de Viterbi, le SOVA et le Forward-Backward sont couramment utilisés dans les systèmes mobiles et fixes à codage simple ou concaténé.

5.1 L'Algorithme de Viterbi La description de l’algorithme de Viterbi (VA) est faite dans le cadre du décodage à maximum de vraisemblance (à entrée ferme ou souple) des codes convolutifs. La description reste similaire pour le décodage d’une modulation codée en treillis, d’un code en blocs à partir de son treillis ou pour la détection ML sur un canal avec interférence entre symboles. Il suffit de modifier la définition de la métrique pour changer le décodage ou la détection. Soit C un code convolutif binaire de rendement R=k/n et de longueur de contrainte L. L’algorithme de Viterbi est le moyen le plus répandu pour le décodage ML lorsque C possède un treillis de taille raisonnable, i.e. un nombre d’états inférieur ou égal à 256. Au delà de cette limite, et même pour des treillis à 240 ou à 250 états, une solution possible est le décodage séquentiel par l’algorithme de Fano (complexité non contrôlable à faible


Eb/N0). Récemment (depuis 1997), le décodage itératif nous permet de décoder de manière sous-optimal des codes convolutifs variant dans le temps à 21000 états. Comparativement, l’algorithme de Viterbi est de faible complexité et il est beaucoup plus simple à décrire. Le décodage à maximum de vraisemblance revient à chercher dans le treillis du code C le chemin le plus proche de la séquence reçue, i.e. l’observation. La distance employée dans l’algorithme est la distance euclidienne dans le cas soft (entrée souple) ou bien la distance de Hamming dans le cas hard (entrée ferme). Rappelons que le nombre d’états dans le treillis d'un code C non récursif est égal à 2k(L-1) et que le nombre de transitions par état est 2k. Chaque noeud dans le treillis est connecté de chaque coté par 2k branches vers les noeuds antérieurs et postérieurs. Le nombre total de branches entre deux étapes dans le treillis est 2k(L-1)×2k = 2kL. La séquence à décoder étant théoriquement de longueur infinie, on se limite en pratique à la recherche du chemin le plus proche sur une fenêtre de largeur W. Les chemins manipulés dans le treillis du code sont donc de longueur W branches. Si l’on essaie d’appliquer une méthode de décodage par recherche exhaustive, nous nous trouvons confrontés à la recherche du meilleur chemin parmi (2kL)Wpossibilités. La complexité d’un tel procédé est prohibitive puisqu’elle est exponentielle en fonction de W. L’algorithme de Viterbi décrit ci-dessous apporte une grande réduction de la complexité de la recherche. Description du VA: Le temps est noté par l’indice t. Un état dans le treillis est noté par st à l’instant t, où .

T(t,st-1,st) représente la branche à l’instant t dans le treillis associée à la transition de l'état à l'état . La somme des carrés des distances entre le chemin choisi dans le treillis et toute l’observation est dite métrique cumulée d’un noeud et elle est notée λ(t, st).

)1(20 −=<≤ Lkt Ss

1−ts ts

ts − Initialisation : λ(0,0)=0.0 et λ(0,s)=+∞ pour s≠0. − A l’étape t, pour chaque état st : On choisit la branche T(t,st-1,st) telle que la distance cumulée λ(t, st) entre le chemin sélectionné et l’observation soit minimale

( ) ( ) ( )[ ]nobservatiosstTdstMinst tttst t,,,(,1, 1

211 −− +−=

−λλ

On stocke ensuite le chemin survivant ),,(),1(),( minmin tt sstTstsurvivantstsurvivant +−=

− Résultat du décodage ML (avec un délai de W branches) : on fournit la dernière branche T(t-W,s,s’) appartenant au survivant(t,s) ayant la plus petite métrique cumulée λ(t, s).

L’algorithme de Viterbi nécessite donc le calcul de 2kL métriques à chaque étape t, d’où une complexité de W×2kL linéaire en W. Cependant, la complexité reste exponentielle en k et L, ce qui limite l’utilisation aux codes de petite taille (kL de 7 à 10 maximum). La largeur W de la fenêtre de décodage est égale à 5L environ. Cette valeur garantie que les survivants convergent vers un chemin unique à l’intérieur de la fenêtre de décodage. L’algorithme de Viterbi nécessite le stockage de 2k(L-1) métriques cumulées et 2k(L-1) survivants de longueur 5kL bits. Un exemple de décodage à décisions dures: Nous illustrons l’algorithme de Viterbi décrit ci-dessus par une simple application au décodage à décisions dures du code convolutif (7,5) à 4 états et de rendement 1/2. Notez que la distance minimale de ce code est dHmin=5. Le treillis est représenté sur la Figure 3 du paragraphe 3. La métrique d’une branche d2(T(t,st-1,st),observation) est égale à la distance de Hamming dH(T(t,st-1,st), 2 bits reçus) entre les deux bits de la branche et les deux bits reçus à l’instant t. Les Figures 1-6 montrent l’état de la fenêtre de décodage pour t=0..15. Les métriques cumulées sont affichées sur le côté droit de la fenêtre. Les chemins survivants sont dessinés en lignes continues. Dans cet exemple, nous supposons que le codeur a émis le chemin 00….00 et que le décodeur a reçu l’observation r=10 00 00 00 00 10 00 00 00 00 00 …


+∞

+∞

+∞

+∞

+∞

1

10

Figure 1 : Etat de la fenêtre à l’instant 1

2

1

2

3


2

3

3

1


3

4

4

4


5

3

5

4


3

6

5

6 Figure 6 : Etat de la fenêtre à l’instant 15

5.2 L’Algorithme de Viterbi à Sortie Souple L’algorithme de Viterbi (noté VA) est modifié afin de fournir à sa sortie une valeur de confiance ou de fiabilité (équivalente à une probabilité a posteriori) associée à chaque bit décodé. La valeur des bits décodés est toujours donnée par le chemin ayant la métrique cumulée minimale fourni par l’algorithme. Les valeurs de confiance produites par le VA modifié sont utilisées dans le décodage à décisions souples d’un code externe. Le décodeur interne basé sur le VA à sorties souples (noté SOVA) reçoit et fournit des valeurs souples, il se comporte ainsi comme un dispositif amplifiant le rapport signal-à-bruit. Le SOVA améliore donc le gain en rapport signal-à-bruit dans tout système de codage concaténé, e.g. deux codes convolutifs en série ou en parallèle, un code


convolutif et un code en blocs, une modulation codée en treillis et un code correcteur, et enfin un code correcteur d’erreurs suivi d’un canal avec interférence entre symboles. Le gain par rapport au VA classique varie de 1 à 4dB sur un canal gaussien sans décodage itératif. Malgré sa sous-optimalité, le SOVA présente des performances très proches de l’algorithme Forward-Backward qui calcule de manière exacte les probabilités a posteriori (les APPs) des bits décodés. Pour simplifier la description du SOVA, plaçons nous dans le cas d’un code convolutif binaire de rendement 1/n. Nous avons ainsi deux transitions partant de chaque état et deux transitions arrivant à chaque état dans le treillis. Ce cas inclut aussi les codes convolutifs k/n obtenus par perforation d’un code 1/n. Le nombre d’états dans le treillis du code est noté S=2ν où ν=L-1 est la mémoire du code. Supposons que le VA classique prend des décisions avec un délai W suffisamment grand pour que les 2ν survivants convergent vers le même chemin avec une très grande probabilité. A l’instant t, l’algorithme de Viterbi doit choisir un survivant pour l’état Sst <≤0 . Ceci est illustré sur la Figure 7. Le VA sélectionne le chemin ayant la plus petite métrique cumulée. Dans le cas où le canal est un canal gaussien (AWGN) à sortie souple, les métriques cumulées s’expriment sous la forme :

∑ ∑−= =

=−=−

=t

Wtj

n

i

mijij

cm

m mxrNE

Nxr

M1

2)(

00

2)(

2,1)(2

où xij(m) est le ième bit codé à l’instant j parmi les n bits associés à une branche du chemin d’indice m arrivant à

l’état st. L’échantillon rij est l’observation en sortie du canal correspondant au bit numéro i à l’instant j. Nous supposons que les symboles (confondus avec les bits) appartiennent à une modulation BPSK, i.e.

cij Ex 2±= où Ec est l’énergie moyenne par symbole codé sur fréquence porteuse. En mettant en facteur

cE2 , nous écrivons les symboles sous la forme 1±=ijx d’où le rapport Ec/N0 apparu dans l’équation précédente. Avec les notations définies ci-dessus et en supposant qu’aucune information a priori n’est disponible sur les chemins dans le treillis, la probabilité que le chemin m soit émis sachant l’observation est proportionnelle à

mMenobservatiomcheP −α)/min( Nous indexons le chemin ayant la métrique cumulée minimale par m=1. Ainsi nous avons et le VA choisit le chemin survivant numéro 1. Après normalisation par la somme des probabilités des deux cas possibles, la probabilité de choisir le mauvais chemin survivant, à l’instant t et pour l’état st, est égale à :

21 MM ≤

∆−−−

−

+=

+=

+=

eeeeep MMMM

M

st 11

11

1221

2

avec . La probabilité pst approche 0.5 si M2≈M1 et tend vers 0.0 si M2>>M1. L’algorithme de Viterbi commettra des erreurs avec une probabilité pst sur les e positions où les chemins 1 et 2 ont des bits d’information différents uj

(1)≠uj(2) pour les positions j=j1,j2,…,je. Notez que e=2 dans la Figure 7. Les positions

où uj(1)=uj

(2) ne sont pas affectées par la sélection du survivant. Notons Wm la largeur de la fenêtre dans le treillis où les chemins 1 et 2 arrivant à l’état st ne sont pas confondus. Ainsi, nous avons e bits d’information différents et Wm-e bits d’information identiques.

012 ≥−=∆ MM

Notons la probabilité que le bit uj

(1) associé au chemin 1 de l’état st soit erroné. Supposons que les valeurs

de soient stockées en mémoire pour les instants passés j=t-Wm…t-1. Prenons comme valeur initiale jp̂

jp̂ 0ˆ =jp (le bit décodé reste parfaitment fiable tant que les deux chemins donnent la même valeur). Sachant que l’algorithme de Viterbi a selectionné le chemin 1, nous pouvons mettre à jours les probabilités d’erreurs des bits différents selon la formule :

tt sjsjj ppppp )ˆ1()1(ˆˆ −+−← pour j=j1,j2,…,je

Cette équation nous fournit une approximation de la probabilité d’erreur pour le bit d’information uj. Même si le SOVA est incapable de fournir l’APP exacte du bit uj, une valeur de confiance µj est facilement obtenue à partir de : jp̂


+∞<≤−

= jj

jj p

pµµ 0

ˆˆ1

log

En combinant les deux équations ci-dessus, nous obtenons une formule de mise à jour des valeurs de confiance :

j

j

eeef jj αµ

αµ

αµµ

++

=∆←∆

∆+1log1),(

Rappelons que la mise à jour est effectuée sur les positions j=j1,j2,…,je. Le facteur α introduit dans la fonction f() permet d’éviter les débordements de la valeur de confiance à fort rapport signal-à-bruit. Asymptotiquement, nous pouvons normaliser la moyenne de la valeur de confiance à 1.0 en choississant le facteur

0min4

NEd c

H=α puisque l’effet dominant est déterminé par les chemins les plus proches, avec

cH Ed minxx2)1()2( 8=− où dHmin est la distance minimale du code convolutif. Une approximation simple et

très pratique de la fonction f() est

)/,min(),( αµµ ∆≈∆ jjf Cette dernière formule permet une mise à jour très rapide de la valeur de confiance sans même connaître la valeur du rapport Ec/N0. Nous pouvons maintenant décrire de manière générale les étapes de l’algorithme SOVA : Stockage: L’indice t du temps, modulo W+1 Les suites des bits décodés par décisions dures u(st)={ ut-W(st),…, ut(st)}, uj(st)∈±1 pour 0 . Sst <≤Les suites de valeurs de confiance µ(st)={ µt-W(st),…, µt(st)} avec +∞<≤ )( tj s0 µ pour 0 . Sst <≤

Les valeurs des métriques cumulées λ(t, st) pour Sst <≤0 . Mise à jour: a) Etape VA classique: Pour chaque état st, calculer λ(t, st). Stocker la métrique cumulée, le survivant et le bit décidé ut(st). b) Etape de décision à sortie souple: Pour chaque état st, stocker la différence des deux métriques

( ) ( )[ ] ( ) ( )[ ]nobservatiosstTdstMinnobservatiosstTdstMax tttttt ),,,(,1),,,(,1 12

112

1 −−−− +−−+−=∆ λλInitialiser µt(st)=+∞. Pour j=t-ν en marche arrière jusqu’à t-Wm, comparer les deux chemins convergents en st et si uj

(1)(st)≠uj(2)(st)

alors mettre à jour les fiabilités par la formule µj(st)=f(µj(st),∆). Sortie souple : L’algorithme fournit une sortie ferme : le bit décodé ut-W associé au meilleur survivant de métrique minimale λ(t, st) parmi tous les états st.

L’algorithme fournit une sortie souple : la valeur souple ut-W× µt-W où Wt

WtWt p

p

−

−−

−=

ˆˆ1logµ est la valeur de

confiance à l’instant t-W du meilleur survivant. Signalons enfin que les µj ou les calculées par le SOVA sont une approximation des probabilités a posteriori.

Si le VA fournit le bit d’information uj, alors

jp̂

j

j

eepuAPPuAPP jjj µ

µ

+=−=−=

1ˆ1)(1)( .


m=1

+1

+1

+1 +1

+1

-1

-1

-1

-1

m=2

t-Wm l

S états

t-W

st

Figure 7 : Exemple d’un treillis décodé par le SOVA.

5.3. L’algorithme Forward-Backward. La plupart des algorithmes de décodage à entrées souples et fermes détermine le meilleur mot de code sans aucune optimisation de la probabilité d’erreur des bits contenus dans l’étiquette du mot. L’algorithme Forward-Backward calcule de manière exacte la probabilité a posteriori de chaque bit associé à un mot de code. C’est un algorithme à entrée souple et à sortie souple applicable à n’importe quel code ayant une représentation graphique sous la forme d’un treillis. La figure 1 illustre le fonctionnement du Forward-Backward. L’entrée (resp. la sortie) scalaire ou vectorielle du canal est notée Xj (resp. Yj). Le temps est noté j et varie de 0 à N. L’état de départ d’une transition est indexé par m et celui d’arrivée est indexé par m’. L’algorithme possède trois entrées, la première recevant l’observation, la deuxième fournit les probabilités a priori des transitions, la troisième décrit la structure du treillis. L’algorithme délivre à sa sortie la probabilité a posteriori à l’instant j de la transition m→m’.

Xj Canal Yj

temps=jm m’1 1

2

3

4

2

3

4

Algorithmep(Yj |Xj)

πj(m’|m)

σj(m,m’)

qj(m,m’)

Structure du treillis

Figure 1 : Structure de l’algorithme Forward-Backward. Les entrées-sorties et les paramètres de l’algorithme sont définis de la manière suivante : Entrées : p(Yj|Xj) : probabilité conditionnelle de la sortie du canal sachant l’entrée πj(m’|m) : probabilité a priori de la transition m→m’ qj(m, m’) : 1 si la transition m→m’, 0 sinon. Sortie : σj(m, m’) : probabilité a posteriori de la transition m→m’ La probabilité a posteriori d’un bit xj notée APP(xj) est définie par ( ) ( )Njj YYYxPxAPP ,...,,| 21= et s’obtient

en additionnant les APP des transitions associées à la valeur xj du bit considéré. Donc ( ) ∑=

jxmmjj mmxAPP

|',)',(σ


Variables : j : temps variant de 0 à N Sj : état dans le treillis à l’instant j γj(m,m’)=P(Sj =m’, Yj| Sj-1=m) : la métrique de l’algorithme αj(m)=P(Sj =m, Y1

j ) : probabilité jointe de l’état m et des observations 1 à j βj(m)=P(Y | Sj =m) : probabilité des observations j+1 à N sachant l’état m. N

j 1+

L’algorithme procède en 4 étapes : la première étape fixe les valeurs initiales des α et des β en supposant par exemple que l’état de départ et l’état d’arrivée sont tous les deux à 0. Le coeur de l’algorithme est constitué d’une procédure aller et d’une deuxième procédure retour pour le calcul des α et des β. Enfin la dernière étape évalue les probabilités a posteriori à partir des probabilités jointes α et β et de la métrique γ. Voici donc le déroulement de l’algorithme : Initialisation

( ) ( ) 0010 00 ≠∀== mmet αα ( ) ( ) 0010 ≠∀== mmet NN ββ

Procédure Aller ∑ == −m

jjj Njmmmm ...1)()',()'( 1αγα

Procédure Retour ∑ −== ++

'11 0...1)'()',()(

mjjj Njmmmm βγβ

Calcul de l’APP )'()',()()',( 1 mmmmmm jjjj βγασ −=

La métrique de l’algorithme Forward-Backward se calcule par le produit : )|()|'()',()',( jjjjj XYpmmmmqmm πγ =

6. Les codes concaténés. L'idée de construire des codes complexes par combinaison de plusieurs codes élémentaires remonte aux années 50. En effet, Elias avait proposé des codes produits multi-dimensionnels construits à partir de simples codes de parité. Cette méthode de construction itérative a été réutilisée plus tard dans les années 80 par Tanner afin de concevoir des codes sur des graphes. Les codes de Tanner définis par des graphes déterministes ou aléatoires sont une généralisation de tous les codes simples ou concaténés. Ainsi, les codes à faible densité de Gallager obtenus par intersection de codes de parité entrelacés et les codes concaténés en série et en parallèle avec ou sans entrelacement aléatoire sont des cas particuliers de codes de Tanner. Les premiers codes dits concaténés ont été proposées par Forney à la fin des années 60 et s'obtiennent par la mise en cascade de deux codes correcteurs d'erreurs. Le premier code est dit code externe et le deuxième se nomme code interne. Un exemple très célèbre est celui du code Reed-Solomon [255,223]256 (externe) concaténé avec un code convolutif (interne) R=1/2 à 64 états. Ce code longtemps utilisé dans les systèmes de transmission spatiale de la NASA sera remplacé par un turbo code ayant des meilleures performances pour un rapport signal-à-bruit inférieur à 1dB. En revanche, la concaténation série d'un Reed-Solomon (sur le corps de Galois GF(64) ou GF(128)) et d'un code convolutif sera adoptée dans le système EDGE (Enhanced Data rates for GSM Evolution). Cette technique de codage concaténé classique reste moins complexe que les turbo codes et garantit à fort rapport signal-à-bruit une pente très raide du taux d'erreur binaire. La Figure 1 montre les performances du système RS+Convolutif à concaténation série sur le canal gaussien. La zone d'intérêt pratique se situe entre 2.5 et 3.0 dB. Notez la forte et brusque réduction du taux d'erreur par rapport à la modulation non codée. Le code convolutif est décodé par un algorithme de Viterbi à entrée souple.


Un désentrelaceur est placé à la sortie du décodeur Viterbi afin de casser les paquets d'erreurs avant le décodage algébrique du code Reed-Solomon par l'algorithme de Berlekemp-Massey.

0 1 2 3 4 5 6 7 8Eb/N0 (dB)

10-8

10-7

10-6

10-5

10-4

10-3

10-2

10-1

100

Pe(

bit)

BPSK sans codage

Borne theorique

Simulation

Figure 1. Concaténation série du RS[255,223]256 et du code convolutif (133,171).

6.1. Les codes produits. Soient C1[n1,k1,d1]q et C2[n2,k2,d2]q deux codes linéaires en blocs définis sur le corps GF(q). Le code produit C=C1×C2 est l’ensemble de toutes les matrices n1×n2 dans lesquelles toute ligne est un mot du code C1 et toute colonne est un mot du code C2. Lorsque les deux codes C1 et C2 sont systématiques, la structure du code produit est décrite Figure (2).

Information Parité 1

Parité 2 Parité 1-2

k2

n1-k1

n2-k2

k1

Figure 2. Structure matricielle d'un code produit. Les k2×(n1-k1) symboles de parité de C1 sont le résultat de k2 opérations de codage horizontal. Les k1×(n2-k2) symboles de parité de C2 sont le résultat de k1 opérations de codage vertical. Enfin, les (n1-k1)×(n2-k2) symboles notés Parité 1-2 s’obtiennent en codant la parité de C2 par n2-k2 codages horizontaux ou en codant la parité de C1 par n1-k1 codages verticaux. Le code produit C[n,k,d]q possède les caractéristiques suivantes :

n=n1×n2, k =k1×k2 et d=d1×d2


Les codes constituants C1 et C2 peuvent être cycliques, ceci ne garantit pas la cyclicité du code produit. En effet, le code produit C est cyclique si les deux constituants sont cycliques et si pgcd(n1,n2)=1. Le décodage à maximum de vraisemblance des codes produits est pratiquement irréalisable. Pour cette raison, ces codes sont restés dans l'ombre jusqu'au début des années 90 quand l'efficacité du décodage itératif a été redécouverte. A titre d'exemple, la Figure 3 illustre les performances de deux codes produits binaires sur le canal gaussien. Le premier est un [20,15]2 et le deuxième un [32,26]2. Le code BCH binaire [20,15] est obtenu par raccourcissement du code primitif [31,26] et le [32,26] est le résultat d'une simple extension du même [31,26]. Le décodage est itératif (voir paragraphe 6.3), i.e. on applique de manière itérative un décodeur SISO sur le code horizontal et après sur le code vertical. Le décodeur SISO de la Figure 3 est un algorithme Forward-Backward opérant sur le treillis BCJR [1] du code BCH.

0 1 2 3 4 5Eb/N0 (dB)

10-6

10-5

10-4

10-3

10-2

10-1

100

BCH(20,15) produit

BCH(32,26) produit

Figure 3. Codes produits [20,15]2 et [32,26]2, canal AWGN, 4 itérations.

6.2. Les turbo codes parallèles et séries Nous étudions dans ce paragrahe les deux concaténations parallèle et série de codes convolutifs. Les Turbo Codes initialement découverts ont été construits par deux codes convolutifs systématiques récursifs concaténés en parallèle et séparés par un entrelaceur [7][8][10][46]. Il est possible de généraliser la concaténation parallèle à plusieurs codes convolutifs séparés par plusieurs entrelaceurs. Vu le rendement très faible d’une concaténation à plus de deux niveaux , nous limitons l’étude aux turbo codes parallèles formés seulement de deux codes convolutifs constituants. Ceci est justifié aussi par les excellentes performances des turbo codes à deux niveaux après un décodage itératif, malgré leur faible distance de Hamming minimale qui n’augmente pas de façon linéaire en fonction de la longueur du code. De la même manière, la concaténation série [6][26] revient à mettre en cascade plusieurs codes convolutifs séparés par des entrelaceurs. Pour les mêmes raisons, nous limitons notre description aux turbo codes séries construits par la cascade de deux codes séparés par un seul entrelaceur. Les concaténations les plus célèbres sont la concaténation parallèle et la concaténation série de deux codes convolutifs. Il est possible de fabriquer des turbo codes hybrides en combinant le série et le parallèle. Notons que les codes concaténés séries proposés par Forney [26] comprenant par exemple un code Reed-Solomon (code externe) et un code convolutif (code interne) sont eux aussi une forme de turbo codes séries. L’impossibilité de décoder le code RS par un décodeur SISO (soft input – soft output) calculant les APPs nous empêche de les classer dans la famille des turbo codes. En revanche, la grande famille des codes imitant le codage aléatoire


comprend les turbo codes au sens strict et les codes en blocs concaténés avec un entrelacement aléatoire [35] ou un entrelacement lignes-colonnes (les codes produits). On pourrait même construire un code produit en remplaçant la permutation aléatoire d’un turbo code par une permutation lignes-colonnes. Les Turbo Codes Parallèles Un turbo code parallèle CP est un code en blocs (J, N) linéaire binaire. Le code CP est construit en concaténant de manière parallèle selon le schéma de la Figure (4) deux codes convolutifs C1 et C2. Le treillis des deux codes démarre de l’état zéro et se termine après N/ki branches dans l’état zéro. L’entrelaceur Π utilisé dans la concaténation est pseudo-aléatoire et il est réalisé en précalculant une permutation aléatoire de taille N.

Code C 1

k1/n1N bits

x

Code C 2

k2/n2

Π

N bits

(n1-k1)×N/k1 bits

(n2-k2)×N/k2 bits

N bits

N bits

Perm.

x1

y1

x2

y2

Figure 4. Turbo codeur parallèle. En pratique, on prend souvent C1=C2. De plus le code constituant C1 est toujours un code RSC. Les turbo codes parallèles basés sur les NRNSC ne présentent pas de gain d’entrelacement, i.e. ils ont un grand coefficient d’erreurs, puisqu’un événement d’erreurs composé d’un nombre fini d’événements simples garde après entrelacement un nombre fini d’événements simples. D’après la Figure (4), les N bits d’information x sont codés par le codeur de C1, entrelacés à travers Π et ensuite codés par C2. Chaque code RSC Ci génère (ni-ki)N/ki bits de parité notés yi. Les bits d’information x=x1 et x2 étant les mêmes à une permutation près, nous ne transmettons pas l’entrée du code C2 afin d’augmenter le rendement de CP. L’émission des bits x2 est utile seulement pour doubler la diversité en présence d’évanouissements sur un canal de Rayleigh. En négligeant la fermeture des deux treillis, le rendement de CP s’obtient par l’expression simple

211

1

2121

212

RRsiR

RRRRR

RRJNR =

−=

−+==

Ainsi, le cas le plus fréquent correspond à R=1/3 avec R1=1/2, et en perforant un bit de parité sur deux nous avons R1=2/3 et R=1/2. Il est préférable de ne pas perforer les bits d’informations afin de garantir une bonne convergence du décodage itératif. Il est possible d’éviter la perforation des bits de parité en utilisant directement un code RSC de rendement 2/3, même si le treillis de ce dernier est un peu plus complexe. Les Turbo Codes Séries Un turbo code série CS est un code en blocs (J, K) linéaire binaire. Le code CS est construit en concaténant de manière série selon le schéma de la Figure 5 deux codes convolutifs C1 et C2. C1 est dit code externe et C2 code interne. Comme pour le code CP, le treillis des deux codes constituant CS démarre de l’état zéro et se termine dans l’état zéro, après K/k1 branches pour C1 et après N/K2 branches pour C2.

PermutationCode C 1

k1/n1K bits

xΠ

N bits

y1 Code C 2

k2/n2 J bits

y2

Figure 5. Turbo codeur série. En pratique, on prend un code externe C1 NRNSC ou RSC, mais le code interne C2 doit toujours être RSC. Les turbo codes séries basés sur un code interne NRNSC ne présentent pas de gain d’entrelacement comme dans le cas des turbo codes parallèles. D’après la Figure 5, les K bits d’information x sont codés par le codeur de C1, entrelacés à travers Π et ensuite recodés par C2. Le code externe génère N=K/R1 bits codés y1. Les bits y1


contiennent les bits d’information x1 si C1 est un RSC. Le code interne RSC génère J=N/R2 bits codés y2 contenant ses bits d’information x2. En négligeant la fermeture des deux treillis, le rendement de CS s’obtient par le simple produit

21 RRJKR ×==

Ainsi, le cas le plus fréquent correspond à R=1/2 avec R1=2/3 et R2=3/4. Nous remarquons déjà que les codes constituant un turbo série ont un rendement plus élevé que ceux constituant un turbo code parallèle. Les treillis des codes constituant CS sont plus complexes que les treillis de CP. D’un autre coté, la distance de Hamming minimale de CS, notée dHmin(CS), est beaucoup plus grande que dHmin(CP) car les événements d’erreurs de poids minimal du code interne C2 sont produits par des événements d’erreurs de C1 qui sont au moins de poids dHmin(C1).

6.3. Le décodage itératif. Le décodeur à maximum de vraisemblance (ML) d’un code concaténé est impossible à réaliser en pratique. Les codes concaténés (produits, turbos ou autres) sont donc décodés par une technique itérative dite turbo décodage qui fait appel à un sous-décodeur ML et SISO des codes constituants. Même si le décodage de chaque constituant est optimal, le décodage itératif global de la concaténation est sous-optimal au sens ML (au sens de la minimisation de la probabilité d’erreur par mot Pew). Le décodage itératif fonctionne au niveau des bits d’information et non au niveau des mots de code. Son but est l’estimation de l’APP (probabilité a posteriori) de chaque bit d’information. Malgré sa sous-optimalité, les performances du décodage itératif tendent vers celles d’un décodeur ML lorsque le rapport signal-à-bruit augmente. Sachant que le décodage itératif d’un code concaténé est basé sur le décodage SISO de ses codes constituants, nous décrivons ci-dessous le décodage à entrée et sortie souples d’un code linéaire C[J,K]2 sur un canal AWGN. Le schéma général du décodeur SISO est illustré Figure 6. Soit r=(r1,r2,...,rJ) le vecteur des échantillons réels reçus à l’entrée du décodeur. L’APP d’un bit codé cj, j=1...J, est égale à

∑ ∑∈ ∈

===Cc Cc

jjjjj rp

ccPccrprccPrcPcAPP

)(),(),|(

)|,()|()( (1)

Décodeur SISO

π(bi) ou π(cj)

APP(bi) ou APP(cj)

Ext(bi) ou Ext(cj)

K ou J a posteriori

K ou J a priori

structure du code

J observations

K ou J a priori

p(rj/cj)

Figure 6. Décodeur à entrée et sortie souples (SISO).

La vraisemblance p(r|cj,c) est nulle si le jème bit du mot c n’est pas égal à cj. La probabilité a priori de la paire (cj,c) est elle aussi nulle lorsque le jème bit de c est différent de cj. Sachant que les observations et que les probabilités a priori sont indépendantes, nous obtenons :

∑ ∑ ∏∈ ∈ =

=∝j jcCc cCc

Jj ccrpcPcrpcAPP

| | 1)()|()()|()(

llll π (2)

De manière similaire à ce qui précède l’équation (2), l’APP d’un bit d’information bi, i=1...K, est égale à

∑ ∑ ∏∈ ∈ =

=∝i ibCc bCc

Ji ccrpcPcrpbAPP

| | 1)()|()()|()(

llll π (3)


Un décodeur SISO reçoit toujours J observations sur les bits codés et calcule K APPs (resp. J APPs) sur les bits d’information (resp. sur les bits codés). En revanche, nous pouvons lui fournir K probabilités a priori sur les bits d’information ou J probabilités a priori sur les bits codés, i.e. il existe deux cas possibles pour l’entrée du SISO. Il est possible aussi d’exiger le calcul de K a priori sur les bits d’information ou J probabilités a priori sur les bits codés, i.e. il existe deux cas possibles pour la sortie du SISO. Ainsi, pour un code linéaire binaire fixé, nous avons 4 décodeurs SISO différents. Puisque C peut être systématique ou non-systématique, nous obtenons un total de 8 versions différentes de décodeurs SISO. Les probabilités a priori calculées par un décodeur SISO sont dites informations extrinsèques et sont notées Ext(cj) et Ext(bj). A titre d’exemple, nous développons les équations du SISO lorsque C[J,K]2 est un code en blocs obtenu par la terminaison d’un code convolutif RSC. Nous supposons aussi que C est un des deux constituants d’un turbo code parallèle. Dans ce cas, les K bits d’information bi de C sont parmi les J bits codés cj. Nous séparons les K bits d’information b1, b2, ..., bK et les J-K bits de parité cK+1,cK+2, ..., cJ. Le décodeur reçoit les K a priori π(bi) et aucune a priori sur les bits de parité, i.e. π(cj)=1/2 pour j=K+1...J. En mettant en facteur l’observation et l’information a priori du bit bi, la formule (3) devient

∑ ∏ ∏∈ ≠= +=

××∝ibCc

K

i

J

Kjjjiiii crpbbrpbbrpbAPP

| ,1 1)|()()|()()|()(

lllll ππ (4)

L'information extrinsèque calculée par le décodeur SISO du RSC se calcule donc par la formule (3ème terme de l’équation 4) :

∑ ∏ ∏∈ ≠= +=

∝ibCc

K

i

J

Kjjji crpbbrpbExt

| ,1 1)|()()|()(

lllll π (5)

Le décodeur SISO décrit dans ce paragraphe est utilisé comme bloc de base dans le décodage itératif d’un code concaténé. La somme est souvent évaluée à l’aide de l’algorithme Forward-Backward [1] qui profite de la

structure du treillis pour faciliter la recherche des mots de codes. Le forward-backward peut être remplacé par une autre version optimale ou sous-optimale comme celles décrites dans les articles [3][34][39].

∑∈Cc

Enfin, nous clôturons ce chapitre en illustrant les performances d'un turbo code parallèle avec un décodage itératif basé sur le Forward-Backward. La figure 7 nous montre le taux d'erreur d'un code turbo parallèle pour deux valeurs de la taille de l'entrelaceur N=1024 et N=65536 sur le canal gaussien. Le rendement global du turbo code est 1/2 (la limite de Shannon se situe donc à 0.2 dB) et le code constituant est un RSC (23,35) à 16 états. L'effet des évanouissements et de la diversité sur l'efficacité du code est bien présenté figure 8. Le code est de rendement 1/3 (la limite de Shannon se situe vers -0.5 dB), la taille de l'entrelaceur est N=4096. Le décodage itératif a été limité à 4 itérations seulement. Dans cette figure 8, la courbe à l'extrême gauche correspond aux performances sur le canal gaussien sans évanouissements. Celle située à l'extrême droite montre le taux d'erreur sur un canal de Rayleigh (un seul trajet à évanouissemnts). En plaçant par exemple 4 antennes de réception bien décorrélées, il est possible de multiplier l'ordre de diversité par 4 et d'approcher le canal AWGN. REMERCIEMENTS L'auteur remercie Sandrine VIALLE-FONTENELLE, docteur-ingénieur à Motorola Research, pour son aide précieuse dans la rédaction de ce manuscrit.


0.0 0.5 1.0 1.5 2.0Eb/N0 (dB)

10-6

10-5

10-4

10-3

10-2

10-1

100

Pe(

bit)

Entrelaceur 1024

Rendement 1/2

12 Iterations

Entrelaceur 65536

Rendement 1/2

20 Iterations

Figure 7. Turbo Code Parallèle 1/2, code constituant RSC (23,35), canal AWGN.

0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 2.0Eb/N0 dB

10-5

10-4

10-3

10-2

10-1

100

Pe(

bit)

AWGN

RAYLEIGH

2

4

8

16

Figure 8. Turbo Code Parallèle 1/3, code constituant RSC (23,35), canal avec évanouissements et une diversité

de réception 2, 4, 8 et 16.


REFERENCES [1] L.R. Bahl, J. Cocke, F. Jelinek, J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. on Information Theory, vol. 20, pp. 284-287, March 1974. [2] G. Battail, M.C. Decouvelaere, P. Godlewsky, “Replication decoding,’’ IEEE Trans. on Inf. Theory, vol. IT-25, pp. 332-345, May 1979. [3] G. Battail, “Podération des symboles décodés par l’algorithme de Viterbi,” Annales des Télécommunications, vol. 42, no. 1-2, pp. 1-8, Janvier-Février 1987. [4] G. Battail, Théorie de l'Information, Masson, Paris, 1997. [5] S. Benedetto, E. Biglieri, V. Castellani, Digital Transmission Theory, Prentice-Hall, Englewood Cliffs, New Jersey, 1987. [6] S. Benedetto, G. Montorsi, D. Divsalar, F. Pollara, “Serial concatenation of interleaved codes: Performance analysis, design and iterative decoding,”TDA Progress Report 42-126, JPL, August 1995. [7] S. Benedetto, G. Montorsi, “Unveiling turbo-codes: some results on parallel concatenated coding schemes, ” IEEE Trans. on Inf. Theory,vol. 42, no. 2, pp. 409-429, March 1996. [8] S. Benedetto, G. Montorsi, “Design of parallel concatenated convolutional codes,” IEEE Trans. Com., vol. 44, no. 5, pp. 591-600, May 1996. [9] E.R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968. [10] C. Berrou, A. Glavieux, P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding : turbo-codes,” Proceedings of ICC'93, Genève, pp. 1064-1070, Mai 1993. [11] E. Biglieri, D. Divsalar, P.J. McLane, M.K. Simon, Introduction to Trellis-Codes Modulation with Applications, Macmillan, New York, 1991. [12] R.E. Blahut, Theory and Practice of Error Control Codes, Addison-Wesley, 1983. [13] J. Boutros, E. Viterbo, C. Rastello, J.C. Belfiore, “Good Lattice Constellations for both Rayleigh Fading and Gaussian Channels,” IEEE Trans. on Inform. Theory, vol. 42, no. 2, pp. 502-518, March 1996. [14] J. Boutros, O. Pothier, “Convergence Analysis of Turbo Decoding,” Canadian Workshop on Information Theory, Toronto, pp. 25-28, June 1997. [15] J. Boutros, E. Viterbo, “Signal Space Diversity : a Power and Bandwidth Efficient Diversity Technique for the Fading Channel,” IEEE Trans. on Inform. Theory, vol. 44, no. 4, July 1998. [16] J. Boutros, O. Pothier, G. Zémor, “Generalized Low Density (Tanner) Codes : approaching the channel capacity with simple and easily decodable block codes,” IEEE International Conference on Communications, Vancouver, June 1999. [17] J. Boutros, G. Caire, E. Viterbo, E. Sawaya, S. Vialle, “Turbo code at 0.03 dB from capacity limit , ” IEEE International Symposium on Information Theory, July 2002. [18] J. Boutros, G. Caire, “Iterative multiuser joint decoding: unified framework and asymptotic analysis, ” IEEE Trans. on Information Theory, vol. 48, pp. 1772-1793, July 2002. [19] L.H. Charles Lee, Convolutional coding, fundamentals and applications, Artech House, 1997.


[20] G. Cohen, J.L. Dornstetter, P. Godlewski, Codes Correcteurs d'Erreurs, Masson, 1992. [21] J.H. Conway, N.J.A. Sloane, “Soft Decoding Techniques for Codes and Lattices, including the Golay Code and the Leech Lattice,” IEEE Trans. Inform. Theory, vol. 32, pp. 41-50, 1986. [22] D. Divsalar, M.K. Simon, “The Design of Trellis Coded MPSK for Fading Channels: Performance Criteria,” IEEE Trans. on Communications, vol. 36, pp. 1004-1012, September 1988. [23] D. Divsalar, S. Dolinar, R.J. McEliece, F. Pollara, “Transfer function bounds on the performance of turbo codes,” TDA Progress Report 42-121, JPL, August 1995. [24] P. Elias, “Coding for Noisy Channels,” IRE Convention Record, vol. 3, part 4, pp. 37-46, 1955. [25] R.M. Fano, “A Heuristic Discussion of Probabilistic Coding,” IEEE Trans. on Inform. Theory, vol. IT-9, pp. 64-74, April 1963. [26] G.D. Forney, Concatenated Codes, Cambridge, MIT press, 1966. [27] G.D. Forney, “Maximum-Likelihood Sequence Estimation of Digital Sequences in the Presence of Intersymbol Interference,” IEEE Trans. Inform. Theory, vol. IT-18, pp. 363-378, May 1972. [28] G.D. Forney, “The Viterbi algorithm,” Proceedings of the IEEE, vol. 61, no. 3, pp. 268-278, March 1973. [29] G.D. Forney, Coset Codes, Parts I & II, IEEE Trans. on Inform. Theory, vol. 34, September 1988. [30] B.J. Frey, D.J.C. MacKay, “Irregular turbo codes,” IEEE Intern. Symp. on Information Theory, June 2000. [31] R.G. Gallager, Low-density parity-check codes, MIT Press, 1963. [32] R.G. Gallager, Information Theory and Reliable Communication, Wiley, New York, 1968. [33] M.J.E. Golay, “Note on Digital Coding,” Proc. IRE, vol. 37, P. 657, June 1949. [34] J. Hagenauer, P. Hoeher, “A Viterbi algorithm with soft-decision outputs and its applications,” Proceedings IEEE GlobeCom’89, Dallas, Texas, pp. 47.1.1-47.1.7, November 1989. [35] J. Hagenauer, E. Offer, L. Papke, “Iterative decoding of binary block and convolutional codes,” IEEE Trans. on Inf. Theory, vol. 42, no. 2, pp. 429-445, March 1996. [36] R.W. Hamming, “Error Detecting and Error Correcting Codes,” Bell Syst. tech. J., vol. 29, pp. 147-160, April 1950. [37] H. Imai, S. Hirakawa, “Multilevel Coding Method using Error-Correcting Codes,” IEEE Trans. on Inform. Theory, vol. 23, pp. 371-377, 1977. [38] J. Leech, “Notes on Sphere Packings,” Canadian Journal of Mathematics, vol. 19, pp. 251-267, 1967. [39] Y. Li, B. Vucetic, Y. Sato, “Optimum Soft-Output Detection for Channels with Intersymbol Interference,” IEEE Trans. on Inf. Theory, vol. 41, no. 3, May 1995. [40] S. Lin, D.J. Costello, Error Control Coding: Fundamentals and applications, Englewood Cliffs, NJ, Prentice-Hall, 1983. [41] M.G. Luby, M. Mizenmacher , A. Shokrolloahi, D.A. Spielman, “Improved low-density parity-check codes using irregular graphs ,” IEEE Trans. On Information Theory, vol. 47, pp. 585-598, February 2001. [42] M.G. Luby, M. Mizenmacher , A. Shokrolloahi, D.A. Spielman, “Improved low-density parity-check codes using irregular graphs and belief propagation,” IEEE Intern. Symp. On Inf. Theory, August 1998.


[43] D.J.C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Transactions on Information Theory, vol. 45, pp. 399-431, March 1999. [44] D.J.C. MacKay, R.M. Neal, “Near Shannon limit performance of low density parity check codes,” Electronics Letters, vol. 32, pp. 1645, August 1996. [45] F.J. MacWilliams, N.J.A. Sloane, The theory of error-correcting codes, North-Holland, Englewood Cliffs, eight impression, 1993. [46] L.C. Perez, J. Seghers, D.J. Costello, “A Distance Spectrum Interpretation of Turbo Codes,” IEEE Trans. on Inf. Theory, vol. 42, no. 6, pp. 1698-1709, November 1996. [47] O. Pothier, L. Brunel, J. Boutros, “A Low Complexity FEC Scheme based on the Intersection of Interleaved Block Codes,” IEEE VTC'99, Houston, 18-21 May, 1999. [48] J.G. Proakis: Digital Communications, New York, McGraw Hill, 3rd edition, 1995. [49] N. Seshadri, C-E.W. Sundberg, “Multilevel Trellis Coded Modulations for the Rayleigh Fading Channel,” IEEE Trans. on Communications,vol. 41, no. 9, September 1993. [50] C.E. Shannon, “A Mathematical Theory of Communication,” Bell Syst. Tech. J., vol. 27, pp. 379-423, July 1948. [51] C.E. Shannon, “A Mathematical Theory of Communication,” Bell Syst. Tech. J., vol. 27, pp. 623-656, October 1948. [52] D. Slepian, “A Class of Binary Signaling Alphabets,” Bell Syst. Tech. J., vol. 35, PP. 203-234, Jan 1956. [53] R.M. Tanner, “A Recursive Approach to Low Complexity Codes,” IEEE Trans. on Information Theory, Vol. IT-27, September 1981. [54] G. Ungerboeck, “Channel Coding with Multilevel/Phase Signals,” IEEE Trans. Inform. Theory, vol. IT-28, pp. 56-67, January 1982. [55] S. Vialle, J. Boutros, “A Gallager-Tanner Construction based on Convolutional Codes,” Proceedings of WCC'99, pp. 393-404, Paris, January 1999. [56] A.J. Viterbi, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm,” IEEE Trans. Inf. Theory, vol. IT-13, pp. 260-269, April 1967. [57] A.J. Viterbi, J.K. Omura, Principles of digital communications and coding, McGraw-Hill, 1979. [58] L.F. Wei, “Trellis-Coded Modulation with Multi-Dimensional Constellations,” IEEE Trans. Inform. Theory, vol. IT-33, pp. 483-501, July 1987. [59] J.K. Wolf, “Efficient Maximum Likelihood Decoding of Linear Block Codes Using a Trellis,” IEEE Trans. Inf. Theory, vol. IT-24, pp. 76-81, January 1978.

_____________________________

_____________

Documents

TECHNIQUES MODERNES DE CODAGE - vitevu.free.frvitevu.free.fr/tipe/tmc_cours_general_codage_2004.pdf · Extrait d’un livre sur les Communications Radiomobiles ... La suite des signaux