UNIVERSITÉ DE LIMOGES U F R DE SCIENCES ET TECHNIQUES

UNIVERSITÉDELIMOGES
U.F.R.DESCIENCESETTECHNIQUES
THÈSE
pourobtenirlegradede
DOCTEURDEL’UNIVERSITÉDELIMOGES
Discipline:mathématiquesetsesapplications
présentéeetsoutenuepubliquement
par
AyoubOTMANI
le06décembre2002
CodesCortexetconstructionde
codesauto-duauxoptimaux
Directeursdethèse
Thierry BERGER
Philippe GABORIT
JURY
Président
Pascale CHARPIN Directeurderecherche INRIA-Rocquencourt
Rapporteurs
Philippe PIRET Ingénieur CANON
Patrick SOLÉ Directeurderecherche CNRS
Examinateurs
Christine BACHOC Professeurdel’UniversitédeBordeauxI
Thierry BERGER Professeurdel’UniversitédeLimoges
Jean-ClaudeCARLACH IngénieurFRANCE-TELECOM
Philippe GABORIT Maîtredeconférencesdel’UniversitédeLimoges
Jean-Pierre TILLICH Maîtredeconférencesdel’UniversitéParisXITabledesmatières
Remerciements 3
1 Introduction 5
1.1 LacourseverslalimitedeShannon . . . . . . . . . . . . . . . . . 5
1.2 Motivations etrésumé . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Généralités 11
2.1 Notionsfondamentales . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Codesauto-duaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 CodesCortex 21
3.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Généralisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3 Auto-dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4 Groupedepermutation . . . . . . . . . . . . . . . . . . . . . . . . 26
3.5 Classed’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.6 CasoùlecodedebaseestH . . . . . . . . . . . . . . . . . . . . . 328
3.6.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.6.2 Produitencouronne . . . . . . . . . . . . . . . . . . . . . . 33
3.6.3 GroupedepermutationdeP . . . . . . . . . . . . . . . . . 34k
3.6.4 Interprétationdesclassesd’équivalence . . . . . . . . . . . 36
3.6.5 Bornessurladistanceminimale . . . . . . . . . . . . . . . 39
3.6.6 Quasi-cyclicité . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.6.7 Construction decodesextrémauxdetypeII . . . . . . . . 43
3.7 Décodageitératifsuruncanalgaussien . . . . . . . . . . . . . . . 57
3.7.1 Modulationdephaseàdeuxétats . . . . . . . . . . . . . . 58
3.7.2 Canalgaussien . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.7.3 Rapportdevraisemblanceapriori . . . . . . . . . . . . . . 59
3.7.4 Canalàsortiesouple . . . . . . . . . . . . . . . . . . . . . . 60
3.7.5 Décodageàmaximumdevraisemblanceparbit . . . . . . 60
3.7.6 Informationextrinsèque . . . . . . . . . . . . . . . . . . . . 61
3.7.7 Applicationauxcodescortexbinaires . . . . . . . . . . . . 62
12 Tabledesmatières
4 Treilliscycliques 67
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.1.1 ContrainteslocalesetgraphedeTanner . . . . . . . . . . . 68
4.1.2 GraphedeTannergénéralisé . . . . . . . . . . . . . . . . . 69
4.1.3 Treilliscycliques . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2 GraphesdeTannerdescodesCortex . . . . . . . . . . . . . . . . . 76
4.3 Treilliscycliquesdefaiblecomplexité . . . . . . . . . . . . . . . . 77
4.3.1 TreilliscycliqueducodedeGolayà16états . . . . . . . . . 77
4.3.2 GraphedeTanneràlacets . . . . . . . . . . . . . . . . . . . 79
4.3.3 Codesauto-duauxextrémauxettreilliscycliquesdefaible
complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.3.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5 Codesauto-duauxoptimaux 89
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.2 Présentation d’unenouvelleconstruction . . . . . . . . . . . . . . 91
5.3 Codesauto-duauxsurF . . . . . . . . . . . . . . . . . . . . . . . . 952
5.4 Codesauto-duauxsurF . . . . . . . . . . . . . . . . . . . . . . . . 963
5.5 Codesauto-duauxsurF . . . . . . . . . . . . . . . . . . . . . . . . 994
5.5.1 Cashermitien . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.5.2 Caseuclidien . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.6 Codesauto-duauxsurF . . . . . . . . . . . . . . . . . . . . . . . . 1045
5.7 Codesauto-duauxsurF . . . . . . . . . . . . . . . . . . . . . . . . 1077
5.8 Codesauto-duauxsurZ . . . . . . . . . . . . . . . . . . . . . . . . 1094Remerciements
La rédaction deces lignes mefournit l’occasion d’exprimer ma joie d’avoir
étéentourépendanttoutescesannéesdepersonnesd’unetrèsgranderichesse.
Parmi ces personnes, je pense d’abord à mes directeurs de thèse, Thierry BER-
GER etPhilippe GABORIT, quim’ontoffert lapossibilité inestimablededécou-
vrir le monde passionnant, enrichissant et éprouvant de la recherche en ma-
thématiques. Je tiens donc à leur exprimer toute ma gratitude en m’invitant à
apporter ma bien modeste pierre à cet édifice qu’est celui de la connaissance
scientifique. Ils ont non seulement manifesté à mon encontre une perpétuelle
confiancequifutunesourcesupplémentairedemotivation,maisilsontenplus
misàmadispositiontouslesmoyensmatérielsnécessairesaubondéroulement
decettethèse.
J’aimerais par conséquent qu’ils sachent que je suis conscient de la chance
que j’ai eue en les rencontrant, tant sur le plan scientifique par les échanges
fructueuxquenousavonseus,quesurleplanhumain.
On pourrait se dire qu’il n’a pu qu’épuiser ses réserves de chance après
cela. Il n’en est rien car j’ai en effet rencontré d’autres personnes formidables.
Je penseàJean-Claude CARLACH leco-inventeur descodes qui forment lesu-
jetdecettethèse.Jecroisn’avoirjamaisrencontréjusqu’àaujourd’huiuneper-
sonne qui soit capable de produire autant d’idées à la seconde! Certains ré-
sultats présentés dans cette thèse ne sont que des aboutissements d’un travail
d’exploitationdesfruitsdesoninventifettoujours optimisteesprit.
Les choses ne semblent pas s’arranger avec l’arrivée dans son entourage
professionnel d’Emmanuel CADIC. Ces deux personnes représentent à mon
avis ce qui se fait de mieux en termes de symbiose. Je n’ai qu’un seul regret :
n’avoireuquedetropraresréunionsdetravailaveceux.
Ce ne sont pas heureusement pour moi les seules personnes qui méritent
d’êtrementionnées.Ily aeneffetdeuxpersonnes quej’aimeraisciter tantleur
placefutimportantegrâceauxinnombrablesdiscussionsquej’aieuesaveceux.
JepenseàGregoryOLOCCO etJean-PierreTILLICH. Lechapitre4decettethèse
n’aurait tout simplement jamais vu le jour sans leur participation. Je remercie
Gregory de m’avoir fait profiter de son enthousiasme communicatif sans le-
quellestravauxquenousavonsmenésensemblen’aboutiraientsansdoutepas.
Quant à Jean-Pierre, j’ai trouvé en lui la rigueur sans laquelle des faits consta-
tésempiriquementn’auraientpasétédémontrés.Jelesremercietousdeuxpour
leurgrandedisponibilité,leurpatiencedontilsontcontinuellementfaitpreuve.
Je dois dire que le sujet de cette thèse était à l’origine un sujet de stage
de DEA effectué au sein du projet CODES de l’INRIA-Rocquencourt encadré à
3l’époqueparPascaleCHARPIN. Jeluiexprimetoutemareconnaissanced’avoir
continué à s’intéresser à mon travail avec un oeil bienveillant tout au long de
ces années jusqu’à accepter de faire partie du jury. Je profite de cette occasion
pour féliciter les membres du projet pour leur chaleureux accueil en toute sai-
son.
JeremerciePatrickSOLÉdem’avoirfaitl’honneurd’êtrerapporteur,d’avoir
ainsiacceptédesupporteràlalecturedespremièresébauchesdecemanuscrit.
Plusieurs améliorations furent apportées grâce àses remarques. Mes quelques
rencontresavecluim’ontpermisdedécouvrirunepersonned’unegrandegen-
tillesse.
JesuiségalementhonoréquePhilippePIRET estbienvouluprendresurson
précieux temps pour être rapporteur. Son invitation à se voir m’a fourni une
opportunité de découvrir une personne passionnée, curieuse, encline à com-
prendreetàfairecomprendre.
UntrèsgrandMerciàChristineBACHOC d’êtremembredujurycarsapré-
senceestunhonneur.
J’ai effectué ma thèse au sein du Laboratoire d’Arithmétique deCalcul for-
meletd’Optimisation (LACO). Plusieurs de ses membres ont contribué àagré-
menter ma vie en son sein. Je pense aux anciens doctorants maintenant par-
tis comme Mohamed ZAHIDI, Stéphane DELLIÈRE, Delphine BOUCHER, Cyril
BRUNIE etCyrilVERVOUX maisaussiàPhilippeSÉGALAT, LaurentDUBREUIL,
Meriem HERAOUA, Thomas CLUZEAU, Matthieu LE FLOC’H, Mickaël LESCOP
et Jean-Yves ENJALBERT. D’autres enfin comme Martine GUERLETIN, Yolande
PINOL etNadineTCHÉFRANOFF ontfacilitémontravailens’occupantdessou-