Dans l\u2019article fondateur \u00ab\u00a0A Mathematical Theory of Communication<\/em>\u00a0\u00bb [1], paru en 1948, Shannon donne une d\u00e9finition math\u00e9matique rigoureuse de la notion d\u2019information, prolongeant les travaux de Nyquist (1924) et Hartley (1928). Cette d\u00e9finition s\u2019inspire de l\u2019entropie thermodynamique de Boltzmann et se construit dans un cadre probabiliste. Elle mesure la quantit\u00e9 d\u2019inattendu dans la r\u00e9alisation d\u2019un ph\u00e9nom\u00e8ne al\u00e9atoire\u00a0; plus cet \u00e9v\u00e8nement est vraisemblable, moins l\u2019information apport\u00e9e par sa r\u00e9alisation est \u00e9lev\u00e9e. L\u2019unit\u00e9 d\u2019information est le Shannon. 1 Shannon correspond \u00e0 l\u2019information apport\u00e9e par la r\u00e9alisation d\u2019un \u00e9v\u00e8nement parmi deux \u00e9quiprobables. Shannon cr\u00e9e \u00e9galement le mod\u00e8le g\u00e9n\u00e9rique du sch\u00e9ma de communication (le paradigme de Shannon), diff\u00e9rencie la source, le canal de transmission et le r\u00f4le du bruit dans la d\u00e9gradation de l\u2019information. Surtout, il d\u00e9montre la possibilit\u00e9 paradoxale d\u2019une communication sans erreur malgr\u00e9 la pr\u00e9sence de bruit affectant la transmission, pourvu qu\u2019un code appropri\u00e9 soit employ\u00e9. L\u2019article apporte un nombre impressionnant de nouvelles id\u00e9es, chacune d\u2019entre elles donnant naissance \u00e0 une branche des t\u00e9l\u00e9communications. Le lecteur pr\u00e9f\u00e9rant une introduction plus litt\u00e9raire \u00e0 la notion d\u2019information pourra se reporter aux premiers chapitres de \u00ab\u00a0l\u2019\u0153uvre ouverte\u00a0\u00bb d\u2019Umberto Eco.<\/p>\n Entre 1947 et 1948, il se passe beaucoup de choses aux \u00ab\u00a0Bell Telephone Laboratories\u00a0\u00bb d\u2019AT&T, dans le New Jersey. A quelques mois (et quelques bureaux) d\u2019intervalle, Shockley, Brattain et Bardeau vont inventer le transistor et plus tard obtenir le prix Nobel de physique pour cette d\u00e9couverte, Claude Shannon va inventer la th\u00e9orie de l\u2019information et Richard Hamming d\u00e9couvrir les premiers codes correcteurs d\u2019erreurs.<\/p>\n Figure 1\u00a0: paradigme de Shannon<\/p><\/div>\n Dans son article fondateur, Shannon d\u00e9montre le th\u00e9or\u00e8me du codage de canal permettant th\u00e9oriquement de transmettre des donn\u00e9es dans un canal avec une probabilit\u00e9 d\u2019erreur aussi petite que l\u2019on veut, quel que soit le niveau de bruit dans le canal, pourvu que le d\u00e9bit de transmission reste inf\u00e9rieur \u00e0 un seuil th\u00e9orique donn\u00e9\u00a0: la limite de Shannon. Mais le th\u00e9or\u00e8me ne donne pas de m\u00e9thode de construction et depuis soixante-dix ans, les ing\u00e9nieur.es et chercheur.es en th\u00e9orie de l’information s’efforcent de d\u00e9couvrir ces codes et d’atteindre au plus pr\u00e8s la limite de Shannon.<\/p>\n Avant de coder le message \u00e0 transmettre, il faut exprimer celui-ci dans un alphabet adapt\u00e9 au canal de transmission. Le t\u00e9l\u00e9graphe de Chappe (1794) utilise un alphabet compos\u00e9 des diff\u00e9rentes positions possibles des bras du t\u00e9l\u00e9graphe\u00a0; apr\u00e8s l\u2019invention de l\u2019\u00e9lectricit\u00e9 le code de Samuel Morse (1832) utilise un alphabet ternaire form\u00e9 de \u00ab\u00a0point\u00a0\u00bb, \u00ab\u00a0trait\u00a0\u00bb et \u00ab\u00a0espace\u00a0\u00bb. Avec l\u2019invention de l\u2019informatique et surtout celle du transistor, l\u2019alphabet binaire s\u2019impose rapidement. Le symbole de base est le \u00ab\u00a0bit\u00a0\u00bb (pour binary digit<\/em>, d\u00e9nomm\u00e9 ainsi par Tuckey en 1943) qui prend deux valeurs, typiquement 0 ou 1. Mais on peut tr\u00e8s bien d\u00e9finir des symboles appartenant \u00e0 des alphabets pouvant prendre beaucoup plus de deux valeurs. En fait, plus les symboles qui composent l\u2019alphabet peuvent prendre de valeurs diff\u00e9rentes, moins le message \u00e0 transmettre sera long. Par exemple, les symboles peuvent \u00eatre choisis dans un corps fini, qui est une structure alg\u00e9brique d\u00e9couverte et \u00e9tudi\u00e9e initialement par Evariste Galois (1812-1832). Les corps finis peuvent contenir beaucoup d\u2019\u00e9l\u00e9ments, mais dans une structure contrainte\u00a0: le nombre d\u2019\u00e9l\u00e9ments est forc\u00e9ment la puissance d\u2019un nombre premier et la stabilit\u00e9 de l\u2019ensemble par addition et multiplication impose des contraintes fortes entre les \u00e9l\u00e9ments. La th\u00e9orie de Galois a longtemps \u00e9t\u00e9 consid\u00e9r\u00e9e comme une curiosit\u00e9 math\u00e9matique n\u2019int\u00e9ressant que les math\u00e9maticien.nes pur.es\u00a0et les amateurs et amatrices d\u2019arithm\u00e9tique ; elle est aujourd\u2019hui au c\u0153ur des modulations cod\u00e9es utilis\u00e9es quotidiennement en t\u00e9l\u00e9communications.<\/p>\n Figure 2. Un t\u00e9l\u00e9graphe de Chappe \u00e0 Saint-Marcan, Ille et Vilaine<\/p><\/div>\n Les premiers codes sont construits de fa\u00e7on alg\u00e9brique\u00a0: c\u2019est la redondance d’information qui permet de prot\u00e9ger les messages des erreurs de transmission. Le message \u00e0 transmettre est transform\u00e9 en un \u00ab\u00a0mot de code\u00a0\u00bb par adjonction de combinaisons lin\u00e9aires des bits initiaux. Ceci a pour effet de rendre les symboles du message d\u00e9pendants les uns des autres. Le mot de code sera donc plus long que le message initial, mais cette redondance est justement ce qui va permettre de d\u00e9tecter et de corriger d\u2019\u00e9ventuelles erreurs au cours de la transmission.<\/p>\n Lorsque les aviateurs communiquaient jadis avec la tour de contr\u00f4le en utilisant un alphabet phon\u00e9tique\u00a0(A comme Aline, L comme Louise, L comme Lucien, O comme Octave), c\u2019est une information redondante qui \u00e9tait transmise afin de s\u2019assurer que le contr\u00f4leur a\u00e9rien allait bien comprendre chaque lettre\u00a0: pour une lettre d\u2019information envoy\u00e9e, c\u2019est un mot entier qu\u2019il fallait transmettre. Le d\u00e9codage est alors effectu\u00e9 par notre cerveau qui retrouve par analogie la premi\u00e8re lettre d\u2019un pr\u00e9nom familier (parce que dans un mot, les lettres ou les syllabes ne sont pas ind\u00e9pendantes). Le principe est le m\u00eame pour un code correcteur lin\u00e9aire. Le mot de code est construit \u00e0 partir du message initial en le multipliant par une matrice caract\u00e9ristique du code (la matrice de codage), qui allonge le message en cr\u00e9ant des bits redondants, puis la d\u00e9tection d\u2019erreur est effectu\u00e9e en multipliant le message re\u00e7u sur le canal par une autre matrice (la matrice de v\u00e9rification). Chaque ligne de la matrice de v\u00e9rification repr\u00e9sente une \u00e9quation liant entre eux les bits transmis. Si un bit est erron\u00e9, l\u2019\u00e9quation correspondante n\u2019est plus satisfaite et en recoupant entre elles toutes les \u00e9quations non satisfaites, il est possible de d\u00e9tecter l\u2019endroit o\u00f9 l\u2019erreur s\u2019est produite. Si l\u2019alphabet binaire est utilis\u00e9, trouver l\u2019endroit o\u00f9 l\u2019erreur s\u2019est produite est \u00e9quivalent \u00e0 corriger cette erreur\u00a0: il suffit de remplacer le 0 par 1 et vice-versa\u00a0!<\/p>\n Les deux premiers exemples de codes correcteurs sont dus \u00e0 Richard Hamming et Marcel Golay. Richard Hamming travaillait avec Claude Shannon en 1947. Avant chaque week-end, il lan\u00e7ait ses calculs sur l\u2019ordinateur du laboratoire et revenait en d\u00e9but de semaine suivante pour s\u2019apercevoir que l\u2019ordinateur avait souvent arr\u00eat\u00e9 l\u2019ex\u00e9cution de son programme suite \u00e0 une erreur. Hamming se disait que si la machine \u00e9tait en mesure de d\u00e9tecter une erreur, elle devait bien pouvoir d\u00e9tecter l\u2019endroit o\u00f9 l\u2019erreur se produisait et, tant qu\u2019\u00e0 faire, la corriger. Le code de Hamming a ainsi \u00e9t\u00e9 invent\u00e9 en 1947 et est r\u00e9f\u00e9renc\u00e9 dans l\u2019article de Shannon de 1948. Marcel Golay a publi\u00e9 en 1949 les caract\u00e9ristiques d\u2019un code d\u2019une longueur de 23 bits, dont 12 bits d\u2019information, capable de corriger 3 erreurs par mot, tandis que celui de Hamming corrigeait une erreur pour une longueur de 7 bits dont 4 d\u2019information. L\u2019article de Hamming n\u2019a \u00e9t\u00e9 publi\u00e9 qu\u2019en 1950, le temps que le d\u00e9p\u00f4t de brevet soit effectu\u00e9\u00a0; s\u2019en suivit une pol\u00e9mique entre Golay et Hamming sur la paternit\u00e9 de l\u2019invention du premier code. Le minitel utilisait un code de Hamming de longueur 128. Le code de Golay a \u00e9t\u00e9 utilis\u00e9 dans les sondes Viking dans leur voyage vers Mars, et par la sonde Voyager, lanc\u00e9e en 1979 en direction de Jupiter. \u00c0 la fin des ann\u00e9es 90, Voyager continuait \u00e0 \u00e9mettre des messages vers la Terre au-del\u00e0 de l\u2019orbite de Pluton.<\/p>\n Le pouvoir de correction d\u2019un code (c\u2019est-\u00e0-dire le nombre d\u2019erreurs qu\u2019il peut corriger) n\u2019est pas la seule caract\u00e9ristique importante. Le rendement (rapport entre le nombre de bits du message initial \u00e0 transmettre et la longueur totale du mot transmis) est un autre facteur important qui caract\u00e9rise son efficacit\u00e9. Dans certains canaux peu brouill\u00e9s (\u00e0 l\u2019int\u00e9rieur d\u2019une fibre optique, par exemple) la probabilit\u00e9 qu\u2019une erreur se produise est tr\u00e8s faible (de l\u2019ordre de 10-8<\/sup> ou 10-9<\/sup>) et l\u2019on peut donc se contenter d\u2019un pouvoir correcteur faible pour privil\u00e9gier le d\u00e9bit de transmission. Par contre, dans certains canaux tr\u00e8s brouill\u00e9s (une communication avec un satellite au fin fond du syst\u00e8me solaire, par exemple) il est pr\u00e9f\u00e9rable d\u2019avoir un pouvoir correcteur fort pour bien prot\u00e9ger la communication.<\/p>\n Le pouvoir correcteur est li\u00e9 \u00e0 la g\u00e9om\u00e9trie du code et \u00e0 la distance entre deux mots (la \u00ab\u00a0distance de Hamming\u00a0\u00bb est le nombre de coordonn\u00e9es dont deux mots diff\u00e8rent). La distance minimale d\u2019un code est la plus petite distance entre deux mots quelconques. Les mots du code sont dilu\u00e9s au sein de l\u2019espace (tr\u00e8s grand) de tous les messages possibles. Plus les mots sont \u00e9loign\u00e9s les uns des autres, meilleur sera le pouvoir correcteur. Un d\u00e9codage simple (mais optimal au sens du maximum de vraisemblance) consiste \u00e0 chercher le mot du code le plus proche du message re\u00e7u apr\u00e8s la transmission. Lorsque la taille des messages est tr\u00e8s petite, c\u2019est facile \u00e0 faire. Mais les codes actuels ont des longueurs de plusieurs dizaines voire plusieurs centaines de milliers de bits et il est alors impossible de proc\u00e9der ainsi\u00a0: le d\u00e9codage alg\u00e9brique est fortement limit\u00e9 par la dimension.<\/p>\n Dans les ann\u00e9es soixante, les math\u00e9maticien.nes ont d\u00e9velopp\u00e9 des codes plus puissants (corrigeant plus d\u2019erreurs pour une longueur et\/ou un rendement donn\u00e9), comme les codes de Reed et Muller (utilis\u00e9s par la sonde Mariner pour envoyer des photos de Mars en 1972) ou les codes de Reed et Solomon dont les symboles appartiennent \u00e0 des corps finis qui peuvent prendre 256, 1024 voire 2048 valeurs diff\u00e9rentes pour chaque symbole. Ils sont utilis\u00e9s dans les disques compacts, dans les DVD, dans les transmissions GSM ou dans le protocole internet ADSL [2]. Ce sont toujours des codes lin\u00e9aires, mais les techniques de d\u00e9codage sont plus \u00e9labor\u00e9es et utilisent la transformation de Fourier dans les corps finis ou des propri\u00e9t\u00e9s alg\u00e9briques des espaces en jeu. Mais ces codes restent loin de la limite th\u00e9orique promise par Shannon et \u00e0 la fin des ann\u00e9es 80, beaucoup de sp\u00e9cialistes pensent que cette limite ne sera jamais atteinte.<\/p>\n Figure 3\u00a0: exemple de l\u2019efficacit\u00e9 d\u2019un code de Reed Solomon (Xiaoli Sun \u2013 Nasa)<\/p><\/div>\n Au d\u00e9but des ann\u00e9es 1990, trois chercheurs de l\u2019\u00e9cole nationale des t\u00e9l\u00e9communications de Bretagne (aujourd\u2019hui l\u2019institut Mines T\u00e9l\u00e9com Atlantique) pr\u00e9sentent des codes dont ils assurent qu’ils sont \u00e0 quelques dixi\u00e8mes de d\u00e9cibels de la limite de Shannon. Apr\u00e8s plusieurs ann\u00e9es de doute, la communaut\u00e9 du codage se rend compte que les \u00ab\u00a0turbocodes\u00a0\u00bb de Claude Berrou, Alain Glavieux et Punya Thitimajshima ont effectivement la puissance de correction annonc\u00e9e et ils deviennent alors les codes les plus utilis\u00e9s de l’industrie (communications satellitaires, hertziennes, radio-t\u00e9l\u00e9phonie, r\u00e9seau 4G, stockage des donn\u00e9es en informatique, etc.). Les techniques de d\u00e9codage associ\u00e9es sont statistiques\u00a0: maximum de vraisemblance, algorithme de Viterbi, utilisation de la notion d\u2019entropie. La qualit\u00e9 du code ne se mesure plus seulement avec la distance minimale, mais en observant le taux d\u2019erreur par bit pour un rapport signal sur bruit donn\u00e9 du canal.<\/p>\n Le principe des turbocodes est le suivant\u00a0: en r\u00e9injectant dans le d\u00e9codeur un message qui a d\u00e9j\u00e0 \u00e9t\u00e9 d\u00e9cod\u00e9 (mais dans lequel peuvent encore rester des erreurs r\u00e9siduelles) on peut b\u00e9n\u00e9ficier d\u2019une information suppl\u00e9mentaire et s\u2019en servir pour am\u00e9liorer le d\u00e9codage ; de la m\u00eame fa\u00e7on que dans un moteur de voiture, le turbo utilise les gaz d\u2019\u00e9chappement afin d\u2019augmenter la puissance du v\u00e9hicule. En \u00e9lectronique, on parle de boucle de r\u00e9troaction. Typiquement, on utilise deux codes diff\u00e9rents dans lesquels on fait circuler alternativement les messages (on dit qu\u2019ils sont entrelac\u00e9s). De la m\u00eame fa\u00e7on que dans les mots crois\u00e9s o\u00f9 le fait de trouver un mot horizontal donne des indications sur les mots verticaux, l\u2019alternance des deux d\u00e9codages permet de gagner de l\u2019information sur les bits et d\u2019am\u00e9liorer le d\u00e9codage, gr\u00e2ce \u00e0 une grandeur appel\u00e9e \u00ab\u00a0information extrins\u00e8que\u00a0\u00bb. Elle r\u00e9sulte de la diff\u00e9rence entre l\u2019information a priori<\/em> disponible en entr\u00e9e du d\u00e9codeur et l\u2019information a posteriori<\/em> calcul\u00e9e apr\u00e8s d\u00e9codage [3]. \u00ab\u00a0Maximum de vraisemblance\u00a0\u00bb, \u00ab\u00a0information a prior<\/em>i\u00a0\u00bb, \u00ab\u00a0a posteriori<\/em>\u00a0\u00bb, tous ces termes nous rappellent les cours de statistiques de l\u2019ENSAE\u2026<\/p>\n En caricaturant un peu, on dispose \u00e0 cette \u00e9poque de codes alg\u00e9briques dont on sait d\u00e9montrer math\u00e9matiquement et rigoureusement qu\u2019ils ne sont pas tr\u00e8s efficaces, et de codes invent\u00e9s par des ing\u00e9nieurs \u00e9lectroniciens de T\u00e9l\u00e9com Brest, qui sont tr\u00e8s efficaces mais on ne sait pas bien encore d\u00e9montrer pourquoi. S\u2019il n\u2019existe pas de d\u00e9monstration rigoureuse de la grande efficacit\u00e9 des turbocodes, les m\u00e9thodes de d\u00e9codage statistique it\u00e9ratives ont des points communs avec les techniques bay\u00e9siennes et des analogies avec les r\u00e9seaux de neurones profonds\u00a0(eux aussi tr\u00e8s efficaces dans la r\u00e9solution de certains probl\u00e8mes, sans qu\u2019on sache exactement ce qui se passe \u00e0 l\u2019int\u00e9rieur du r\u00e9seau) … \u00a0Certains articles de recherche r\u00e9cents s\u2019int\u00e9ressent aux r\u00e9seaux de neurones entra\u00een\u00e9s pour imiter le turbo-d\u00e9codage.<\/p>\n Figure 4 : un exemple de turbo-d\u00e9codage (Claude Berrou et Joseph Boutros, ENST)<\/p><\/div>\n [1] Claude E. Shannon, \u00ab\u00a0A Mathematical Theory of Communication\u00a0\u00bb, Bell System Technical Journal, vol. 27, 1948.\u00a0<\/em><\/p>\n [2] Odile Papini et Jacques Wolfmann, \u00ab\u00a0alg\u00e8bre discr\u00e8te et codes correcteurs\u00a0\u00bb, Math\u00e9matiques et applications, Springer Verlag, 1995.<\/em><\/p>\n [3] Claude Berrou, \u00ab\u00a0Codes et turbocodes\u00a0\u00bb, Springer, 2007.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":" Bref historique et paradigme de Shannon Les codes correcteurs prot\u00e8gent les donn\u00e9es des erreurs de transmission dues au bruit thermique, \u00e0 l\u2019att\u00e9nuation du signal et \u00e0 tout autre type de perturbation. Ils sont utilis\u00e9s dans les t\u00e9l\u00e9phones mobiles, la t\u00e9l\u00e9vision hertzienne, les communications satellitaires, les transmissions par internet ou encore le stockage d\u2019informations num\u00e9riques. S\u2019il […]<\/p>\n","protected":false},"author":312,"featured_media":5266,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_et_pb_use_builder":"","_et_pb_old_content":"","_et_gb_content_width":"","_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[164],"tags":[],"class_list":["post-5260","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-intelligence-artificielle","et-has-post-format-content","et_post_format-et-post-format-standard"],"_links":{"self":[{"href":"https:\/\/variances.eu\/index.php?rest_route=\/wp\/v2\/posts\/5260","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/variances.eu\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/variances.eu\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/variances.eu\/index.php?rest_route=\/wp\/v2\/users\/312"}],"replies":[{"embeddable":true,"href":"https:\/\/variances.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5260"}],"version-history":[{"count":0,"href":"https:\/\/variances.eu\/index.php?rest_route=\/wp\/v2\/posts\/5260\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/variances.eu\/index.php?rest_route=\/wp\/v2\/media\/5266"}],"wp:attachment":[{"href":"https:\/\/variances.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5260"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/variances.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5260"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/variances.eu\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5260"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}![\"\"](\"http:\/\/variances.eu\/wp-content\/uploads\/2020\/09\/g1.png\")
Codage de Canal<\/h3>\n
![\"\"](\"http:\/\/variances.eu\/wp-content\/uploads\/2020\/09\/g2.jpg\")
Les codes lin\u00e9aires<\/h3>\n
![\"\"](\"http:\/\/variances.eu\/wp-content\/uploads\/2020\/09\/G3.jpg\")
L’invention des turbocodes<\/h3>\n
![\"\"](\"http:\/\/variances.eu\/wp-content\/uploads\/2020\/09\/G4.png\")
\nR\u00e9f\u00e9rences<\/em><\/h3>\n