Remerciez-le!

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

PASCAL DJIKNAVORIAN Codes de Reed-Solomon Étude et simulation GEL 66680 Théorie

PASCAL DJIKNAVORIAN Codes de Reed-Solomon Étude et simulation GEL 66680 Théorie & Pratique des Codes Correcteurs Faculté des Sciences et de Génie UNIVERSITÉ LAVAL QUÉBEC AVRIL 2007 c ⃝Pascal Djiknavorian, 2007 Table des matières Table des matières ii 1 Introduction 1 1.1 Objectifs, structure et contenu . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Quoi ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Études de codes de Reed-Solomon 4 2.1 Théories, déﬁnitions, et propriétés . . . . . . . . . . . . . . . . . . . . . 4 2.2 Modèle de communication avec codage . . . . . . . . . . . . . . . . . . 5 2.2.1 Processus de communication . . . . . . . . . . . . . . . . . . . . 5 2.2.2 Théorème de Shannon (Théorie de l’information) . . . . . . . . 5 2.2.3 Problème principal du codage . . . . . . . . . . . . . . . . . . . 6 2.3 Généralités sur les codes de Reed-Solomon . . . . . . . . . . . . . . . . 6 2.3.1 Avantages des codes de Reed-Solomon . . . . . . . . . . . . . . 6 2.3.2 Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3.3 Polynômes générateurs . . . . . . . . . . . . . . . . . . . . . . . 7 2.4 Encodage de codes de Reed-Solomon . . . . . . . . . . . . . . . . . . . 8 2.4.1 Circuit d’un encodeur cyclique non binaire . . . . . . . . . . . . 8 2.5 Décodage de codes de Reed-Solomon . . . . . . . . . . . . . . . . . . . 8 2.5.1 Calcul des syndromes . . . . . . . . . . . . . . . . . . . . . . . . 9 2.5.2 Évaluation du polynôme de locations d’erreurs . . . . . . . . . . 10 2.5.3 Évaluation des racines du polynôme de locations d’erreurs . . . 11 2.5.4 Poids des erreurs détectées (Algo de Forney) . . . . . . . . . . . 12 2.6 Notions évoluées codes de Reed-Solomon . . . . . . . . . . . . . . . . . 12 2.6.1 Codes de Reed-Solomon Généralisés . . . . . . . . . . . . . . . . 12 2.6.2 Codes de Reed-Solomon réduits . . . . . . . . . . . . . . . . . . 12 2.6.3 Codes RS vue avec les transformées de fourier . . . . . . . . . . 13 2.6.4 Codes RS avec alternance de codage . . . . . . . . . . . . . . . 13 3 Simulations de codes de Reed-Solomon 14 3.1 La programmation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Table des matières iii 3.2 La simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2.1 Taux de SER en fonction du p du BSC pour diﬀérents cas . . . 15 3.2.2 Taux de SER en fonction du p du BSC pour deux cas . . . . . . 15 3.3 Résultats des simulations . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.4 Analyse des résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.4.1 Au sujet de la ﬁgure 3.1 . . . . . . . . . . . . . . . . . . . . . . 15 3.4.2 Au sujet de la ﬁgure 3.2 . . . . . . . . . . . . . . . . . . . . . . 17 4 Conclusion 19 4.1 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Bibliographie 20 A Code Matlab 22 A.1 Code pour simulation 1 : main.m . . . . . . . . . . . . . . . . . . . . . 23 A.2 Code pour simulation 2 : main2.m . . . . . . . . . . . . . . . . . . . . . 24 A.3 Routine principale de CODEC RS : simuRS.m . . . . . . . . . . . . . . 24 Chapitre 1 Introduction 1.1 Objectifs, structure et contenu Le présent travail a pour but de faire un tour de la théorie des codes correcteurs de Reed-Solomon [5], de son fonctionnement, des algorithmes principaux de décodage, et enﬁn de deux simulations.1 Nous procéderons tout d’abords par une revue des notions requises par le codage de Reed-Solomon. Nous aurons donc alors besoin de notions de base de communication, de la théorie de l’information de Shannon, du principal problème du codage. Ces notions seront suivis de notions de codage, plus particulièrement des principes de codage de base, de déﬁnitions. Nous continuerons ensuite avec les codes de Reed-Solomon. Nous y verrons, après avoir vu des notions de base, les particularités principales. Nous aurons donc une revue du décodage et ainsi des diﬀérents algorithmes utilisées 1.2 Historique Les codes Reed-Solomon sont considérés comme étant un sous groupe de codes cycliques de la famille des codes BCH. Ces derniers ont été mis au jour par Hocquenghem [7] autour de 1960, et de façon indépendante par Bose et Ray-Chaudhuri [8, 9]. Les codes BCH furent généralisés à tous les corps ﬁni par Gorenstein et Zierler dans [10]. 1Le projet n’avait pour indication que de réalisé le laboratoire 8 du livre [23], mais ce dernier ne demande que de programmer un codec RS. Chapitre 1. Introduction 2 Fig. 1.1 – Sonde Voyager 2 de la NASA Approximativement à la même époque, Reed et Solomon ont développé et publié leurs travaux sur une famille de codes qui portera leur noms : les codes de Reed-Solomon [5]. Les codes de Reed-Solomon aurait été découvert plustôt dans le contexte des matrices orthogonales par Bush en 1952 dans [4]. Les codes de Reed-Solomon ont trouvés applications dans le monde de la conser- vation d’informations numérique, ainsi que dans les systèmes de communication. On retrouve par exemple le code RS(255,233,33) qui est utilisé par la NASA2 dans les communications spatiales. Diﬀérentes versions sous le corps de galois binaire exposant huit (GF(28)) se retrouve dans les disques compacts, dvd, transmission HDTV, et puis d’autres versions sous (GF(27)) sont retrouvés dans les modems cables entre autres. Malgré l’arrivé des codes Reed-Solomon, le monde pris bien du temps avant son utilisa- tion, le problème de l’époque était de trouver des algorithmes de décodage eﬃcace, ce que Berlekamp ﬁt [11], puis Massey ﬁt quelques améliorations dans [13]. Peterson [15] et Sugiyama [2] ont également contribué avec leurs algorithmes de décodages. 1.3 Quoi ? "‘C’est quoi les codes Reed-Solomon ?"’ serait probablement votre première question si vous ne savez pas ce que c’est. Voici un façon simple de comprendre ce que c’est avant d’entammer la version poussé de la réponse à cette question. Notez que cela ne constitu qu’un aperçu de réponse, la réponse clair, complète et détaillé est constitué de la totalité du présent document. Lorsque l’on veut transmettre une information d’un point A au point B, il tran- site par ce que l’on uploads/S4/ projet-gel66680-reedsolomon.pdf