Etude d'une certaine construction des codes definis par les graphes: codes TLDPC.

Accueil || Parcours || Recherche || S'enregistrer || Mon Compte || Contacts || Aide || Langues

Andriyanova, Iryna (2006) Etude d'une certaine construction des codes definis par les graphes: codes TLDPC. Doctorat Systemes des communications, ENST - COMELEC Communication et Electronique, ENST p.148.

Plein texte disponible en tant que : - thesis_Iryna_last_version.pdf ( 1081 Kb )

Licence: Copyright

Résumé

Ce travail est consacr'e `a l’analyse et la construction de codes d´efinis par des graphes dans le but d’obtenir des familles de codes ayant, pour une complexit´e de d´ecodage faible, de tr`es bonnes performances pour une large plage de rapports signal-`a-bruit.

Nous nous int´eressons `a une famille de codes que nous appelons TLDPC (pour Tailbiting Trellis Low-Density Parity Check) qui contient, comme sous-familles, `a la fois les Turbo codes de Berrou et Glavieux et les codes de Gallager appel´es aussi codes LDPC.

La premi`ere partie de cette th`ese est consacr´ee `a l’´etude des codes TLDPC binaires. Nous nous sommes int´eress´es au caract`ere asymptotiquement bon de ces codes et avons obtenus des conditions n´ecessaires ou suffisantes en ´etudiant les polynˆomes ´enum´erateurs moyens des poids d’ensembles de ces codes, ou en introduisant un certain graphe associ´e `a ces codes dont les cycles sont reli´es `a des mots de code de poids potentiellement faibles.

Cela nous a donn´e des bornes sur la proportion des noeuds de degr´e 2 pour respecter le caract`ere asymptotiquement bon. Nous avons ensuite optimis´e (avec cette contrainte sur les noeuds de degr´e 2) la distribution des noeuds des autres variables au moyen des courbes d’entropie (analogues des courbes EXIT ou Extrinsic Information Transfer charts) pour maximiser les performances de l’algorithme standard de d´ecodage it´eratif (Belief Propagation) et nous obtenons par ce moyen de tr`es bonnes performances.

Dans la deuxi`eme partie de la th`ese, nous ´etudions certains codes LDPC et TLDPC non-binaires. Nous y pr´esentons une famille de codes TLDPC non-binaires, ayant `a la fois une structure simple et de tr`es bonnes performances de d´ecodage it´eratif, dont l’un des

avantages est la pente de leurs courbes de taux d’erreur dans la r´egion de faible rapport signal-`a-bruit plus forte que pour les codes binaires correspondants. Il est `a noter qu’un code LDPC ayant au moins deux symboles de degr´e 2 par ´equation de parit´e peut ˆetre

repr´esent´e comme un code TLDPC ayant des symboles de degr´e 1 dans sa structure. Ces codes LDPC peuvent donc ˆetre vus et d´ecod´es comme des TLDPC. Dans le cas particulier des codes de cycles d’un graphe, cette fa¸con de faire n´ecessite beaucoup moins d’it´erations de d´ecodage grˆace aux symboles de degr´e 1 sans pour autant changer le seuil de correction. En introduisant dans la structure de ces codes de cycles d’un graphe des noeuds de degr´e 1, nous obtenons pour le canal `a effacements en autorisant une petite fraction de symboles effac´es apr`es d´ecodage, une famille de codes dont les performances se rapprochent encore des limites th´eoriques de Shannon.

Table des Matières

1 Introduction



1.1 Context and historical background

1.2 Motivation

1.3 Outline

1.4 Contributions



2 Background

2.1 Sparse-graph codes

2.1.1 Unstructured code ensembles

2.1.2 Structured code ensembles

2.1.3 Belief propagation decoding algorithm

2.1.4 Asymptotic analysis tools

2.1.5 Average weight distribution



3 Family of binary TLDPC codes

3.1 Introduction

3.2 General framework for irregular code constructions and their average spectrum

3.3 Tanner codes. Sufficient conditions for being asymptotically good

3.3.1 Average spectrum of Tanner codes

3.3.2 Sufficient conditions for Tanner codes for being asymptotically good

3.4 Tail-biting trellis LDPC codes

3.5 Sufficient conditions for TLDPC codes for being asymptotically good

3.5.1 Average spectrum of the TLDPC code ensemble

3.5.2 Sufficient conditions for being asymptotically good

3.6 Matching condition for entropy curves of TLDPC codes on the BEC

3.6.1 TLDPC code families without bits of degree 1

3.6.2 TLDPC code families with bits of degree 1

3.7 Necessary conditions for being asymptotically good

3.7.1 Definition of the graph of codewords of (partial) weight 2

3.7.2 Cycles in the graph of codewords of (partial) weight 2

3.7.3 Upper bound on the average degree of the graph of codewords of (partial) weight 2

3.7.4 Conditions on permutation of bits of degree > 2

3.8 Particular TLDPC code families

3.8.1 Family A

3.8.2 Family B

3.8.3 Introduction to TLDPC code families with bits of degree 1

3.8.4 Family C

3.8.5 Family D

3.8.6 Family E

3.8.7 Family F



4 Trapping sets of TLDPC codes

4.1 Introduction: trapping sets of LDPC codes

4.2 Experimental results for a family-E code

4.2.1 Properties of decoding failures

4.3 Generalized definition of trapping sets

4.4 Error-floor estimation

4.4.1 Evaluation of P(T) in AWGN case

4.5 Error-floor estimation of the family-E code over AWGN channel

4.5.1 Trapping sets configurations

4.5.2 Detection of dominant configurations

4.5.3 Error-floor estimation results



5 Codes over GF(q)

5.1 Motivation

5.2 State of art

5.2.1 General definitions

5.2.2 Definition of some useful operations over Rq and Rm+1

5.2.3 LDPC codes over GF(q)

5.3 TLDPC codes over GF(q)

5.3.1 Definition

5.3.2 Decoding operations for ((a, b)) TLDPC code family

5.3.3 Density evolution equations

5.3.4 Results on thresholds

5.3.5 EXIT chart for the (2,3) LDPC code ensemble and the ((1, 1))1-

TLDPC code ensemble

5.3.6 Convergence of the (2,3) LDPC code ensemble and of the ((1, 1))1-TLDPC code ensemble

5.3.7 ((1, b))1 TLDPC codes as irregular LDPC codes with a large fraction of symbols of degree 2

5.3.8 Performance of some families of non-binary TLDPC codes

5.4 Analysis of LDPC codes over Fq having a small constant fraction of symbols of degree 1

5.4.1 Code rate as a function of λ1

5.4.2 Density evolution equations

5.4.3 Obtained thresholds



6 Conclusions and perspectives

6.1 Conclusions

6.2 Future work



A

A.1 APP modified decoding algorithm



B

B.1 Optimisation of the degree distribution (x) to maximise the iterative decoding threshold

B.2 Optimisation of degree distributions for the binary erasure channel

B.2.1 Entropy curves of base codes for families A and B

B.3 Comparison of different types of channel



C

C.1 Trapping set configurations observed during simulations

C.2 Low-weight codewords



D

D.1 Properties of ⊠ and ⊡ operations

D.2 Computation of (5.8) in Lemma 19

D.3 Entropy curve of the ((1, 1))1-TLDPC base code



E

E.1 Noisy channel coding theorem for binary erasure channel

Statistiques de consultation

Administrateurs de l'archive uniquement : éditer cet enregistrement