Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

263 avenue du G´ en´ eral Leclerc CS 74205 35042 RENNES CEDEX Campus de Beaulie

263 avenue du G´ en´ eral Leclerc CS 74205 35042 RENNES CEDEX Campus de Beaulieu . F 35 042 Rennes Cedex Codage de sources distribu´ e : codage sym´ etrique et adaptatif en d´ ebit de sources corr´ el´ ees Stage eﬀectu´ e par Velotiaray TOTO-ZARASOA Diplˆ ome d’ing´ enieur de l’IFSIC Master Recherche Signal / TRAMP / Image Ann´ ee 2006-2007 Sous la responsabilit´ e de Christine GUILLEMOT et Aline ROUMY (IRISA) G´ erard FAUCON (SPM, IFSIC) Septembre 2007 Remerciements Avant d’aller plus loin dans la pr´ esentation de cette exp´ erience profession- nelle dans le domaine de la recherche ` a l’IRISA, il me semble indispensable d’adresser mes plus sinc` eres remerciements aux personnes sans lesquelles je n’aurais pas pu soutenir aujourd’hui. Je remercie donc en premier lieu mes deux responsables de stage ` a l’IRISA et dans l’´ equipe TEMICS, Dr Christine Guillemot et Dr Aline Roumy. Christine Guillemot est directeur des recherches de l’´ equipe, au sein de l’INRIA ; Aline Roumy est chercheur dans le domaine du traitement du signal, de la th´ eorie du codage et de la th´ eorie de l’information. Elles ont eu de la patience et leurs conseils m’ont ´ enorm´ ement aid´ e dans mes travaux. Merci ´ egalement ` a Dr Claude Labit, directeur de l’IRISA, qui m’a donn´ e l’opportunit´ e d’eﬀectuer mon stage dans l’enceinte de l’IRISA. Merci ` a Dr Khaled Lajnef, chercheur de l’´ equipe qui travaille ´ egalement dans le domaine du codage distribu´ e. Il m’a beaucoup aid´ e ` a comprendre le codage distribu´ e dans ses d´ etails. Merci enﬁn ` a toute l’´ equipe TEMICS, pour leurs r´ eponses ` a mes questions dans le cadre de mes travaux ainsi que de m’avoir accueilli comme membre de l’´ equipe. Velotiaray Toto-Zarasoa. R´ esum´ e La compression sans perte et distribu´ ee d’informations provenant de plusieurs sources corr´ el´ ees a fait ses d´ ebuts en 1973 quand Dr D. Slepian et Dr J. K. Wolf d´ emontrent que la limite d’une compression disjointe, avec restitution conjointe, n’est autre que l’entropie conjointe de ces sources. Ce qui est remarquable est que cette limite est la mˆ eme que lors d’une compression conjointe. La mise en œuvre th´ eorique passe par un codage al´ eatoire, ce qui est impossible ` a impl´ ementer en pratique. On montre que le codage de canal permet d’atteindre cette limite : les donn´ ees ´ etant corr´ el´ ees, l’une est une version bruit´ ee de l’autre. R´ ecemment, Li et al. et D. Varodayan et al. ont respectivement propos´ e un codage sym´ etrique, c’est ` a dire permettant ` a chacune des sources de transmettre des quantit´ es diﬀ´ erentes d’information tant qu’on restitue les sources sans erreur, et un codage adaptatif en d´ ebit, laissant au syst` eme la possibilit´ e de s’adapter aux diﬀ´ erents niveaux de corr´ elation entre les sources. Nous nous aidons de ces deux travaux pour concevoir notre algorithme. La combinaison de ces deux m´ ethodes commence par le d´ ecodage de la diﬀ´ erence entre les deux s´ equences sources, ` a partir de leurs versions compress´ ees au niveau des entropies conditionnelles : leurs syndromes. Pour le codage LDPC, un algorithme de A. Liveris et al. permet un tel d´ ecodage : la propagation de croyance. En ce qui concerne le codage convolutif, un algorithme permettant ´ egalement de retrouver un mot ` a partir de sa version bruit´ ee a ´ et´ e mise au point par l’´ equipe TEMICS. Plus les sources sont corr´ el´ ees moins les syndromes doivent ˆ etre grands, d’o` u l’adaptation en d´ ebit. D’autre part, on transmet au d´ ecodeur, ainsi que les syndromes, des parties compl´ ementaires des sources ; recouvrer la diﬀ´ erence entre les sources permet donc de compl´ eter ces parties. Enﬁn, on ﬁnalise le d´ ecodage en s’aidant de la repr´ esentation matricielle des diﬀ´ erents codes. La taille des parties syst´ ematiques transmises varie d’une source ` a l’autre pour permettre un codage sym´ etrique. Summary Lossless distributed compression of correlated data from separate sources was ﬁrst studied in 1973 when Dr D. Slepian and Dr J. K. Wolf stated that, as long as joint decoding is performed, the limit of a disjoint compression is the joint entropy of the sources. What is surprising is that the limit is the same as when joint coding of the sources is executed. Theoretical implementation uses random coding, which is not practically feasible. It has been shown that channel coding is one means to reach that bound : the data being correlated, one of the sources can be viewed as a noise-corrupted version of another. Lately, Li et al. and D. Varodayan et al. respectively suggested symmetric coding, that is to let the sources free to send diﬀerent amount of data as long as error free recovering of the sources can be done, and rate-adaptive coding, which leaves the system the possibility to adjust to diﬀerent levels of correlation between the sources. We make use of these two works to design our algorithm. While combining both these frameworks, one must begin with decoding the diﬀerence pattern bet- ween the sources, using their conditional-entropy-level compressed versions : their syndromes. For LDPC coding, the algorithm which completes such a decoding was discovered by A.Liveris et al. : belief propagation. When using convolutional codes, a similar algorithm decodes a word from its er- roneous version and was proposed by the TEMICS team. The more the sources are correlated the less the syndromes have to be long, that is how rate adaptive coding is carried out. Besides the syndromes, some complementary parts of the sources have to be transmitted to the decoder ; then retrieving the diﬀerence pattern between the sources returns to ﬁlling these parts in. Finally, the decoding ends with the use of the matrix representation of the codes. The size of the transmitted systematic parts diﬀer from one source to another to allow symmetric coding. Table des mati` eres Introduction 1 I ´ Etat de l’art 3 1 Th´ eorie de l’information 4 1.1 Entropie et information mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 L’entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 L’information mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.3 S´ equences conjointement typiques : . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Codage source (compression de l’information) . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Les diﬀ´ erents types de codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.2 Th´ eor` eme du codage source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.3 Le codage de Huﬀman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Codage canal (transmission de l’information) . . . . . . . . . . . . . . . . . . . . . . . 6 1.3.1 Capacit´ e du canal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3.2 Th´ eor` eme du codage canal : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Codage source-canal conjoint : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Codage LDPC 9 2.1 Repr´ esentations d’un code LDPC : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 uploads/Geographie/ rapport-de-stage 15 .pdf