Codage conditionnel et codage de SW

Télécharger le fichier pdf d’un mémoire de fin d’études

Sources I.I.D. et distribution jointe bien connue

Dans cette partie, la source X et l’information adjacente Y g´en`erent conjoin-tement des suites de symboles {(Xn, Yn)}+n=1∞, i.i.d., a` valeurs dans des alphabets quelconques X et Y, respectivement. La distribution de probabilit´e jointe P (X, Y ) est suppos´ee parfaitement connue. Nous ´etudions tout d’abord les performances de codage de sources (Partie 2.1.1), puis d´ecrivons les sch´emas de pratiques qui ont et´ propos´es dans cette situation (Partie 2.1.2).

Performances de codage

Nous nous interrogeons ici sur la performance du sch´ema de codage avec infor-mation adjacente au d´ecodeur seulement. Intuitivement, on pourrait se dire que ce sch´ema est beaucoup moins eﬃcace en terme de compression que celui disposant de l’information adjacente ´egalement au codeur (voir Figure 2.1). Dans cette partie, nous comparons donc les performances de ces deux sch´emas de codage dans deux cas : le codage sans pertes et le codage avec pertes.

Codage de sources sans pertes

Dans cette partie, nous supposerons que les alphabets X et Y sont d´enombrables. En codage de sources sans pertes, on veut reconstruire sans erreurs au d´ecodeur la suite de symboles {Xn}+n=1∞. Dans ce cas, on appelle codage conditionnel [Gucsel72] le sch´ema dans lequel Y est connu a` la fois au codeur et au d´ecodeur, et codage de Slepian Wolf (SW) [SW73] celui o`u Y n’est disponible qu’au d´ecodeur. En r´ealit´ le codage de SW tel que d´efini dans [SW73] correspond au cas plus g´en´eral de la compression distribu´ee de deux sources X et Y . Ici, par simplicit´e, l’appellation co-dage de SW d´esignera cependant le cas asym´etrique, o`u seul X est compress´ et o`u Y est directemment disponible au d´ecodeur. On appelle RXc|Y (codage conditionnel) et RXSW|Y les d´ebits minimums auxquels il est possible de coder X pour assurer une reconstruction sans pertes de la source. D’apr`es [Gucsel72] et [SW73], ces d´ebits sont donnés par RXc|Y = RXSW|Y = H(X|Y ) (2.1) o`u H(X|Y ) est l’entropie conditionnelle de X sachant Y . Il n’y a donc pas de perte de performance dans le cas o`u l’information adjacente est disponible uniquement au d´ecodeur. Ce r´esultat ´etonnant a justifi´e l’int´erˆet pour le codage de sources avec information adjacente au d´ecodeur et plus g´en´eralement pour le codage de sources.

En codage de sources avec pertes, on tol`ere un certain ´ecart entre la source et sa reconstruction. L’´ecart moyen maximum est sp´ecifi´ par une contrainte fix´ee de qualit´e de reconstruction appel´ee contrainte de distortion. Dans ce cas, on appelle codage de Wyner-Ziv (WZ) [WZ76] le sch´ema o`u Y est connu au d´ecodeur seulement, et codage conditionnel avec pertes le cas o`u Y est connu au codeur et au d´ecodeur.

Soit d(., .) une mesure de distortion et D la contrainte de distortion telle que E[d(X, Xˆ)] ≤ D. D’apr`es [WZ76], pour du codage de WZ, le d´ebit minimum atteignable pour une contrainte de distortion D est RXWZ|Y (D) = inf I(X; U|Y ) (2.2) o`u le inf est sur l’ensemble des distributions de probabilit´e fU|X pour lesquelles U ↔ X ↔ Y forment une chaˆıne de Markov et telles qu’il existe une fonction de reconstruction F : U × Y → X telle que E [d(X, F (U, Y ))] ≤ D. En codage condi-tionnel avec pertes, on a d’apr`es [Gucsel72], RXc|Y (D) = inf I(X; U|Y ) (2.3) o`u le inf est sur les distributions de probabilit´e fU |X,Y telles que E [d(X, U)] ≤ D.WZ c ´

Les fonctions RX|Y (D) et RX|Y (D) sont appel´ees fonctions d´ebit-distortion. Etant donn´e que l’ensemble de minimisation pour le cas WZ est plus restreint que pour le cas conditionnel, [Zam96] montre que RXc|Y (D) ≤ RXWZ|Y (D), avec egalit´e seulement dans certains cas tels que le cas Gaussien. [Zam96] propose ´egalement une comparaison pr´ecise des performances. Il s’agit ensuite de d´eterminer l’expression explicite de ces fonctions d´ebit-distortion, pour des mod`eles donn´es de sources. Cela peut ˆetre un probl`eme diﬃcile, puisqu’il s’agit de faire une recherche sur les fonctions contenues dans les ensembles de minimisation de (2.2) et (2.3). Le cas Gaussien a et´ trait´e dans [Wyn78], et [BKW10] propose une analyse pour des m´elanges de Gaussiennes.

De multiples variations du probl`eme de codage de WZ ont et´ propos´ees et etudi´ees. Ainsi, [Gas04, GDV06, Ooh99] pr´esentent le cas plus g´en´eral de plusieurs sources a` compresser et [VP10] traite le probl`eme de la s´ecurit´e dans un probl`eme de codage avec information adjacente. Dans [FE06], deux informations adjacentes sont disponibles : l’une des deux est pr´esente a` la fois au codeur et au d´ecodeur, l’autre n’est observ´ee qu’au d´ecodeur. Dans [MWZ08] le codeur re¸coit de l’information sur la distortion entre la source et l’information adjacente pr´esente au d´ecodeur. De plus, la question des d´elais de d´ecodage a ´egalement et´ abord´ee. En ce sens, [Ten04] s’int´eresse `a la construction de codeurs WZ temps r´eel, et [SP13, WG06] supposent que l’information adjacente arrive avec du retard au d´ecodeur. Enfin, [Pra04, VP07] abordent ce probl`eme des d´elais d’un point de vue l´eg`erement diﬀ´erent. Dans ces travaux, lors du d´ecodage d’un symbole Xn, le d´ecodeur a acc`es `a tous les symboles pr´ec´edents X1 . . . Xn−1.

Sch´emas de codage

Nous d´ecrivons ici quelques solutions existantes pour le codage sans pertes puis pour le codage avec pertes.

Solutions pratiques pour le codage sans pertes

La plupart des sch´emas de codage sans pertes [GD05, XLC04] s’appuient sur des codes de canal tels que les turbo-codes [CPR03, SLXG04], et les codes LDPC (Low Density Parity Check codes) [EY05a, LXG02, MUM10a, WLZ08]. Le choix des codes LDPC pr´esente plusieurs int´erˆets. Tout d’abord, [MUM10a] montre que les codes LDPC permettent d’atteindre l’entropie conditionnelle (2.1), a` condition tou-tefois de construire le code avec pr´ecaution [CHJ09b]. Ensuite, de nombreux ou-tils ont et´ d´evelopp´es pour les codes LDPC en codage de canal : algorithmes de d´ecodage [CBMW10, CF02b, DM98, DF05, DF07, GCGD07, LGTD11, Sav08a, Wei08], analyse de performances [AK04,BB06,CRU01,FFR06,LFK09,Ric03,PRW06,WKP05, RSU01, RU01] et construction de codes [PFD08] notamment. En codage de SW, il est donc possible d’utiliser ces outils, soit directement, soit apr`es un travail d’adapta-tion. Ces arguments s’appliqueraient ´egalement pour des turbo-codes, mais, comme indiqu´e dans [XLC04], les m´ethodes de construction de codes performants sont plus simples et plus flexibles pour les codes LDPC que pour des turbo-codes.

Une majorit´e des sch´emas propos´es pr´ec´edemment [CF02a,CPR03,SLXG04,EY05a, LXG02,MUM10a] s’appuie sur des codes LDPC binaires. Or, dans un probl`eme de co-dage de sources, les symboles a` coder sont souvent non-binaires, comme par exemple les pixels d’une image ou les coeﬃcients de leur transform´ee en cosinus discr`ete (DCT) ou en ondelette. Dans ce cas, une solution fr´equemment employ´ee est de transformer les symboles en plans de bits qui seront cod´es ind´ependamment `a l’aide de codes LDPC binaires [EY05a, LXG02, VL12]. Il existe cependant une d´ependance statis-tique entre les plans de bits, qui doit ˆetre prise en compte lors du d´ecodage si l’on veut ´eviter une perte de performance [LW08,TZRG10a,VMFG07,VCFG08]. Mais les m´ethodes propos´ees pour tenir compte de cette d´ependance induisent une complexit´ suppl´ementaire de d´ecodage et, surtout, prennent diﬃcilement en compte l’ensemble des d´ependances. C’est pourquoi nous nous int´eresserons ici `a des codes LDPC tra-vaillant directement avec des symboles non-binaires, c’est-a`-dire dans GF(q), le corps de Galois de dimension q [MS77].

Concr`etement, le codeur r´ealise le codage du vecteur de source xn a` l’aide d’une matrice creuse H de taille n × m (m < n) et dont les coeﬃcients non nuls sont dans GF(q). Les proportions de coeﬃcients non nuls par ligne et par colonne de H sont d´etermin´ees par les distributions de degr´es λ(x) et ρ(x) [RSU01]. Le d´ecodeur dis-pose du mot de code um = HT xn et d’un vecteur d’information adjacente yn, a` partir desquels il doit reconstruire le vecteur de source xn. En codage de canal, plusieurs algorithmes de d´ecodage LDPC ont et´ introduits. Un aper¸cu de ces algorithmes est disponible dans [RU01]. On peut citer le d´ecodage de type hard [LGTD11], le d´ecodage avec des niveaux quantifi´es [PDDV12], les algorithmes de type minimum-somme [DF05, Sav08a, Sav08c, CLXZS13] et les algorithmes de type somme-produit [DM98, GCGD07, Mac99]. Ces derniers, qui sont les plus performants, r´ealisent une estimation approch´ee au sens du maximum a posteriori et sont syst´ematiquement uti-lis´es en codage de SW. La performance de tous ces algorithmes d´epend beaucoup des distributions des degr´es λ(x) et ρ(x) du code. C’est pourquoi des m´ethodes appel´ees ´evolution de densit´ [BB06, LFK09, WKP05, RSU01, RU01, SRA08, RU05, Sav08b] ont et´ introduites pour ´evaluer la performance asymptotique d’un code en fonc-tion de ses distributions de degr´es. Ensuite, une fois qu’une bonne distribution de degr´es est obtenue, il s’agit de construire soigneusement la matrice H a` longueur finie [PFD08, VCNP09].

Décodeur LDPC somme-produit

Les sch´emas de codage qui ont et´ propos´es dans la th`ese ont tous pour base des codes LDPC non binaires avec un d´ecodage de type somme-produit. C’est pourquoi dans cette partie nous d´ecrivons cet algorithme de d´ecodage somme-produit.

A partir du vecteur de sources xn, on obtient donc le mot de code um = HT xn. On souhaite r´ealiser une estimation approch´ee de xn a` partir de um et yn au sens du maximum a posteriori a` l’aide d’un algorithme somme-produit [KFL01] que nous d´ecrivons ici. Pour le cas non binaire et en codage de canal, cet algorithme est pr´esent´ dans [LFK09]. Nous en avons repris les notations. Nous exprimons simplement ici la version SW de cet algorithme. On peut repr´esenter par un graphe G les d´ependances entre les diﬀ´erentes variables al´eatoires du probl`eme (voir un exemple sur la Figure 2.2). Dans ce graphe, on appelle nœuds variables (NV) les sommets repr´esentant les variables X1 . . . Xn et nœuds de parit´e (NP) les sommets repr´esentant les compo-santes U1 . . . Um du mot de code. Une arˆete relie un NV i a` un NP j si et seulement si Hi,j = 0. On note NP(i) l’ensemble des NP connect´es `a un NV i et NV(j) l’en-semble des NV connect´es `a un NP j. La distribution de degr´es des NV est donn´ee par λ(x) = i>1 λixi−1, o`u λi repr´esente la proportion d’arˆetes de degr´ i, c’est-a`-dire provenant de NV reli´es `a i NP. De mˆeme, la distribution de degr´es des NP est donn´ee par ρ(x) = j>1 λj xj−1. Le d´ebit d’un code de distributions de degr´es (λ(x), ρ(x))

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

1 Introduction
2 ´Etat de l’art
2.1 Sources i.i.d. et distribution jointe bien connue
2.1.1 Performances de codage
2.1.2 Schèmas de codage
2.2 Distribution de probabilité mal connue
2.2.1 Modélisation des sources
2.2.2 Problèmes de codage
3 Contributions
3.1 Modèles de sources
3.1.1 Paramètres fixés
3.1.2 Paramètres variables sans mémoire
3.1.3 Paramètres variables avec mémoire
3.2 Analyse de performance
3.2.1 Codage conditionnel et codage de SW
3.2.2 Paramètres estimés
3.2.3 L’analyse outage
3.2.4 Application au cas d’un r´eseau `a trois noeuds
3.3 Sch´emas de codage de SW
3.3.1 Sch´ema de codage pour le mod`ele SwP
3.3.2 R´esultats de simulations
3.4 Design de codes LDPC non-binaires
3.4.1 D´ecodage LDPC
3.4.2 ´Evolution de densit´e
3.4.3 Exemples
3.5 Codage de WZ avec mod`ele de Markov cach´e
3.5.1 Analyse de performance
3.5.2 Sch´ema de codage
3.5.3 R´esultats de simulation
4 Conclusion et perspectives
4.1 Sch´emas de codage
4.1.1 D´ecodage de type minimum-somme pour le codage de SW
4.1.2 ´Evolution de densit´e pour le cas incertain
4.2 Incertitude sur les mod`eles
4.2.1 S´election de mod`eles pour des applications particuli`eres
4.2.2 Mod`eles plus complexes
4.2.3 Incertitude sur les mod`eles de sources pour des probl`emes particuliers de codage
4.3 G´en´eralisation `a un r´eseau de capteurs
4.3.1 Analyse de performance
4.3.2 Autres strat´egies de codage
4.3.3 Construction de codes
4.3.4 R´eseaux plus grands
4.3.5 Une seule source mais plusieurs capteurs
Bibliographie
Annexes
A Analyse de performances
B Sch´emas de codage de SW
C Design de codes LDPC non-binaires
D Codage de WZ pour un canal de corr´elation distribu´e suivant un mod`ele de Markov cach´e