La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

THÈSE

212 pages
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 ...
Voir plus Voir moins

Vous aimerez aussi

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 . . . . . . . . . . . . . . . . . . . . . . . . 130 5.4.3 Expectedcomputationalcostoftheproposedalgorithm . . . . . 131 5.4.4 ConstrainedoptimizationoftrellisparametersT andT . . . . . 1321 2 5.4.5 Extensionofthecombinedtrellisdecodingalgorithm . . . . . . . 133 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 6 BitstreamconstructionstrategiesforVLCs 139 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 6.2 Problemstatementanddefinitions . . . . . . . . . . . . . . . . . . . . . . 141 6.3 Bitstreamconstructionalgorithms . . . . . . . . . . . . . . . . . . . . . . 143 6.3.1 Constantmapping(CMA) . . . . . . . . . . . . . . . . . . . . . . . 143 6.3.2 Stable(SMA)algorithm . . . . . . . . . . . . . . . . . . . 145 6.3.3 Stablesmppingconstructionrelyingonastack basedalgorithm (SMA stack) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 6.3.4 Layeredbitstream . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 6.4 Decodingalgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 6.4.1 Applyingthesoftdecodingprinciples(CMAalgorithm) . . . . . 150 6.4.2 Turbo decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 6.4.3 MMSEprogressivedecoding . . . . . . . . . . . . . . . . . . . . . 151 6.5 Codedesign . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 6.5.1 Pseudo lexicographic(p lex)codes . . . . . . . . . . . . . . . . . . 153 6.5.2 Hu Tuckercodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 6.6 Simulationresults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 6.6.1 Error resilienceofalgorithmsCMA,SMAandSMA stackfor p lexHuffmanandHu Tuckercodes . . . . . . . . . . . . . . . . . . 155 6.6.2 Progressivity performance of CMA andlayered algorithms and impactofthecodedesign . . . . . . . . . . . . . . . . . . . . . . . 158 6.6.3 Error resiliencewithCMA. . . . . . . . . . . . . . . . . . . . . . . 160 6.6.4 Turbo decodingperformanceofCMA . . . . . . . . . . . . . . . . 160 6.7 Discussion and future work : error resilient image coding and M ary sourcebinarization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 6.7.1 Imagecoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 6.7.2 M arysourcebinarization . . . . . . . . . . . . . . . . . . . . . . . 164 6.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin