THÈSE

oN d’ordre:03217 THÈSE présentée devantl’UniversitédeRennes1 pourobtenir legradede: DOCTEUR DE L’UNIVERSITÉ DE RENNES 1 Mention INFORMATIQUE par Hervé JÉGOU Équiped’accueil:Temics IRISA ÉcoleDoctorale:Matisse Composanteuniversitaire: IFSIC Titredelathèse: Codesrobustesetcodesjointssource canal pourtransmissionmultimédiasurcanauxmobiles Soutenuele23novembre2005devantlacommissiond’examen M.: Albert BENVENISTE Président MM.: RobertM. GRAY Rapporteurs Luc VANDENDORPE MM.: Ramesh PYNDIAH Examinateurs Michel KIEFFER Christine GUILLEMOT DirecteurdethèseàmafamilleRemerciements Une thèse n’est pas seulement l’aboutissement du travail d’un doctorant. C’est égalementunechargepourlejuryetlesproches.Cettecourtepagederemerciements leurestdédiée. Je remercie en premier lieu Albert BENVÉNISTE pour l’honneur qu’il m’a fait de présidermonjurydethèse. Je remercie mes rapporteurs, Robert M. GRAY, Professeur à l’Université de Stan ford,etLuc VANDENDORPE,Professeuràl’UniversitéCatholiquedeLouvain,pourle soinqu’ilsontapportéàlalectureetàl’évaluationdecemanuscrit. J’associe pleinement à ces remerciements Ramesh PYNDIAH, Professeur à l’École nationaleSupérieuredesTélécommunicationsdeBretagneetMichel KIEFFER,Maître deconférenceàl’UniversitédeParisXI,pourleremarquabletravailderelecturequ’ils onteffectuéentantqu’examinateurs. Je remercie particulièrement Christine GUILLEMOT pour m’avoir encadré, mais également formé et motivé. Je tiens à souligner son professionnalisme et ses qualités d’écoute, qui ont contribué à ce que j’estime avoir été une collaboration fructueuse. Christine,jet’exprimemareconnaissance. Je tiens à remercier les membres de l’équipe TEMICS, qui ont contribué à une bonne ambiance de travail durant ces trois années. Un grand merci en particulier à Jonathan,SimonetaugrandVivien. Jeremercielesmembresdel’IRISApourlesdiscussionsenrichissantesquej’aipu avoiraveceux. Jeremercieenfinmesamisetmafamille,pouravoirsupportéetacceptémeschoix. MercienparticulieràCatherine,quiaprispartmalgréelleàcetteaventure.0 TabledesmatièresTabledesmatières Tabledesmatières 0 I Problématiqueetrésumédescontributions 7 Introduction 9 1 Préliminaires 11 1.1 EntropieetInformationmutuelle . . . . . . . . . . . . . . . . . . . . . . . 12 1.2 ChaînesdeMarkovetchaînesdeMarkovcachées . . . . . . . . . . . . . 14 1.3 Codagedesource . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.1 Catégorisationdescodesdesource . . . . . . . . . . . . . . . . . . 19 1.3.1.1 Codesàlongueurfixe . . . . . . . . . . . . . . . . . . . . 19 1.3.1.2 Codesàfixeverslongueurvariable . . . . . . 19 1.3.1.3 Codesàlongueurvariableverslongueurfixe . . . . . . 20 1.3.1.4 Codesàversvariable. . . . 20 1.3.2 Codesdesourceusuels . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3.2.1 Codesoptimauxetlimitationspratiques . . . . . . . . . 21 1.3.2.2 Codagearithmétique . . . . . . . . . . . . . . . . . . . . 22 1.3.2.3 Codeslexicographiques . . . . . . . . . . . . . . . . . . . 23 1.3.3 Unautretypedecodesource . . . . . . . . . . . . . . . . . . . . . 23 1.4 Capacitédecanaletmodèlesdecanaux . . . . . . . . . . . . . . . . . . . 24 1.4.1 Enjeuxducodagedecanal . . . . . . . . . . . . . . . . . . . . . . 24 1.4.2 Formulationthéoriqueetcapacité . . . . . . . . . . . . . . . . . . 25 1.4.3 Modèlesdecanauxusuelsetleurcapacité. . . . . . . . . . . . . . 26 1.4.3.1 Canalbinairesymétriqueetcanalàeffacement . . . . . 26 1.4.3.2 Canalàbruitadditifgaussiensansmémoire . . . . . . . 27 1.4.3.3 Canaldiscretsansmémoire . . . . . . . . . . . . . . . . 28 1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 12 Tabledesmatières 2 Étatdel’artetcontributionsencodageconjointsource/canal 31 2.1 Principaleslimitationsduprincipedeséparation . . . . . . . . . . . . . . 31 2.2 Codagedesourcerobusteetcodageconjointsource canal:classification 33 2.3 Techniquesdecodagedesourcerobusteetsource/canal . . . . . . . . . 37 2.3.1 Impactdeserreurssurlescodesdesource . . . . . . . . . . . . . 37 2.3.2 Techniquesdepaquétisation . . . . . . . . . . . . . . . . . . . . . 40 2.3.3 Codesréversibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.3.4 Étiquetagebinaireoptimisécanal . . . . . . . . . . . . . . . . . . . 43 2.3.5 Protectioninégaleauxerreurs . . . . . . . . . . . . . . . . . . . . . 44 2.3.6 DécodagesoupledeCLV . . . . . . . . . . . . . . . . . . . . . . . 44 2.3.7conjointsource canaldeCLV . . . . . . . . . . . . . . . 45 2.4 Résumédescontributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.4.1 Codesmultiplexés . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.4.2 Décodageconjointsource/canal . . . . . . . . . . . . . . . . . . . 49 2.4.3 Constructiondetrainbinaire . . . . . . . . . . . . . . . . . . . . . 51 2.4.4 Nouveauxcodesdesource . . . . . . . . . . . . . . . . . . . . . . 51 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 II Contributions 53 3 Multiplexedcodes 55 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.2 Problemstatementandnotation . . . . . . . . . . . . . . . . . . . . . . . 57 3.3 Multiplexedcodes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.3.1 Principleanddefinitions . . . . . . . . . . . . . . . . . . . . . . . . 58 3.3.2 Conversionofthelowerprioritybitstream . . . . . . . . . . . . . 59 3.3.3 Hierarchicaldecompositionofγ . . . . . . . . . . . . . . . . . . . 62 3.4 Complexityofthehierarchicaldecompositionofthevariableγ . . . . . . 64 3.5 Compressionefficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.6 MultiplexedcodesbasedonaconstrainedpartitionC . . . . . . . . . . . 67 3.6.1 ConstrainedchoiceofpartitionC . . . . . . . . . . . . . . . . . . . 67 3.6.2 Conversionofthelowprioritybitstreamintof valuedvariables 68j 3.6.3 Optimalsetoftransformations . . . . . . . . . . . . . . . . . . . . 69 3.6.4 Encodingprocedure . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.7 Binarymultiplexedcodes . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.8 Probabilitydistributionfunctionapproximation . . . . . . . . . . . . . . 74 3.9 Errorhandlingonabinarysymmetricchannel . . . . . . . . . . . . . . . 76 3.10 DiscussionandParameterschoice . . . . . . . . . . . . . . . . . . . . . . 77 3.10.1 RedundancyintermsoftheratioS versusS +S . . . . . . . . 77H H L 3.10.2 PMFapproximationinherenttocodeswithconstrainedpartitions 79 3.10.3 Elementsofencodinganddecodingcomplexity . . . . . . . . . . 79Tabledesmatières 3 3.11 Simulationresults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.12 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4 First ordermultiplexedcodes 87 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.2 ProblemstatementandNotation . . . . . . . . . . . . . . . . . . . . . . . 89 4.3 First ordermultiplexedcodes . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.3.1 Memorylessmultiplexedcodes:areview . . . . . . . . . . . . . . 90 4.3.2 First ordercodes:definition . . . . . . . . . . . . . . 91 4.4 Error resilienceanalysisonaDMC . . . . . . . . . . . . . . . . . . . . . . 93 4.4.1 Modelingthedependenciesinthecodingandtransmissionchain 93 4.4.2 AsymptoticSERandMSEbounds . . . . . . . . . . . . . . . . . . 95 4.4.3 ImpactoftheIAonerror resilience. . . . . . . . . . . . . . . . . . 96 4.5 Codedesign:crossed IAandcodekernel . . . . . . . . . . . . . . . . . . 96 4.5.1 Crossed IAstrategy . . . . . . . . . . . . . . . . . . . . . . . . . . 97 4.5.1.1 Reductionoferrorpropagation . . . . . . . . . . . . . . 99 4.5.1.2 ConstrainedoptimizationoftheIA . . . . . . . . . . . . 99 4.5.2 Definitionandpropertiesofthekernel. . . . . . . . . . . . . . . . 100 4.5.3 Maximumcardinalityofthekernel . . . . . . . . . . . . . . . . . . 101 4.6 Softdecodingofmultiplexedcodes . . . . . . . . . . . . . . . . . . . . . . 101 4.6.1 AdaptationoftheBCJRalgorithmformultiplexedcodes . . . . . 101 4.6.1.1 Initializationofforwardandbackwardrecursions . . . 102 4.6.1.2 Complexityanalysis . . . . . . . . . . . . . . . . . . . . . 103 4.6.2 Estimationcriteria:MAP,MPMandMMSE . . . . . . . . . . . . 104 4.7 Hardandsoftre synchronizationofcontexts . . . . . . . . . . . . . . . . 104 4.7.1 Error resilienceanalysisforfinitelengthsequences . . . . . . . . 105 4.7.2 Synchronizationusingmemorylessmultiplexedcodes . . . . . . 106 4.8 SimulationResults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.8.1 SERandSNRperformanceofmemorylessandfirst ordermulti plexedcodes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.8.2 RespectiveSERandSNRperformanceofmultiplexedandarith meticcodesinatandemsource channelcodingscheme . . . . . . 108 4.8.3 Synchronizationofthecodes . . . . . . . . . . . . . . . . . . . . . 110 4.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 5 Newstatemodelsforsoftdecodingofvariablelengthcodes 115 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 5.2 Errorrecoveryanddecodingwithalengthconstraint:alink . . . . . . . 117 5.2.1 Thegain/lossbehaviorofaVLC . . . . . . . . . . . . . . . . . . . . 118 5.2.2 ExtensiontotheBSC . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.2.3 Codeselectioncriteria . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.3 Stateaggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1244 Tabledesmatières 5.3.1 Optimalstatemodel . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.3.2 Aggregatedstatemodel:abriefdescription . . . . . . . . . . . . 125 5.3.3 Aggregatedstatemodel:analysis . . . . . . . . . . . . . . . . . . 126 5.4 Combinedtrellisdecoding . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 5.4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 5.4.2 Thedecodingalgorithm . . . . . .