Théorie du codage essentielle [pdf]

• Ce livre présente de manière exhaustive les concepts fondamentaux de la théorie du codage et ses développements modernes
• Il couvre les principes de base des codes correcteurs d’erreurs, la structure et les limites de différents codes, ainsi que leurs domaines d’application concrets
• Il explique en détail, entre autres, la théorie de Shannon et les codes de Hamming, ainsi que des codes largement utilisés en pratique comme Reed-Solomon
• Il propose également de façon structurée des cas d’usage dans les systèmes informatiques récents, comme le hachage, les tests groupés et la protection des données biométriques
• Avec ses annexes, exercices et références bibliographiques, l’ouvrage est conçu comme une ressource efficace à la fois pour les apprenants et les praticiens

---

Préface

• Ce livre s’appuie sur les notes de cours de théorie du codage de Venkatesan Guruswami, Atri Rudra et Madhu Sudan
• Il est fondé sur des enseignements donnés à l’University of Washington, à CMU, à l’University at Buffalo SUNY, à Harvard, au MIT, etc.
• Il a bénéficié du soutien de la subvention NSF CAREER grant CCF-0844796
• Les opinions et résultats des auteurs ne représentent pas la position officielle de la NSF
• Il est disponible sous licence Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Résumé de la table des matières

Chapitre 1 : Questions fondamentales

• Objectif de la théorie du codage, définitions de base et codes
• Correction d’erreurs, notion de distance des codes, codes de Hamming et bornes
• Classification des familles de codes, avec exercices et références bibliographiques

Partie I : Fondements

• Introduction de structures mathématiques comme les codes linéaires, les corps finis et les espaces vectoriels
• Explication du décodage efficace des codes de Hamming et des codes duaux
• Exercices et références bibliographiques inclus

Chapitre 3 : Probabilités et fonction d’entropie q-aire

• Bases des probabilités, méthode probabiliste, compréhension de la fonction d’entropie q-aire
• Exercices et références associées

Partie II : Combinatoire

• Présentation des bornes des codes et de leurs limites, notamment Hamming, Gilbert-Varshamov, Singleton et Plotkin
• Codes de Reed-Solomon, polynômes et applications des corps finis
• Modèle de bruit de Shannon et limites de la transmission d’information, avec comparaison avec Hamming
• Extensions comme le list decoding, la borne de Johnson et la capacité du list decoding
• Nouvelles théories des limites comme Elias-Bassalygo et les bornes de programmation linéaire

Partie III : Diverses structures de codes

• Codes fondés sur les polynômes, applications aux corps binaires et structures générales de codes
• Concaténation de codes, borne de Zyablov, techniques avancées de concaténation et synthèse
• Graphes expandeurs, codes expandeurs, amplification de distance et cas d’application

Partie IV : Algorithmes

• Méthodes de décodage efficaces pour Reed-Solomon, Reed-Muller et les codes concaténés
• Méthodes pour atteindre la capacité du canal BSCp et structures de codes internes/externes
• Codes polaires, principe de polarisation, implémentation des encodeurs/décodeurs, capacité de list decoding
• Présentation de codes à encodage en temps linéaire et à récupération locale

Partie V : Applications

• Théorie du hachage et prévention des collisions, fonctions de hachage presque universelles, preuve de possession de données
• Concept de Fuzzy Vault pour la protection de l’authentification biométrique (empreintes digitales)
• Formalisation des tests groupés (Group Testing), bornes et applications aux algorithmes de flux de données
• Complexité des problèmes de codage : problème du mot de code le plus proche, décodage avec prétraitement, approximation, problème de distance minimale, etc.
• Thèmes de soutien en complexité computationnelle : complexité de communication, randomisation, pseudorandomness, hardcore predicates, problèmes de difficulté moyenne, etc.

Annexes

• Tableau des symboles, inégalités et égalités utiles, notation asymptotique, bases sur les algorithmes et la complexité
• Algorithmes algébriques, introduction aux corps finis et aux opérations sur les polynômes
• Principaux concepts de la théorie de l’information : entropie, entropie conditionnelle, information mutuelle, etc.

Caractéristiques et valeur d’usage

• Il fournit de manière complète le socle théorique et les méthodes d’application pratique des algorithmes de correction d’erreurs, indispensables dans les télécommunications modernes, le stockage de données et les systèmes cryptographiques
• Des concepts de base aux tendances récentes et aux applications concrètes, il transmet un large éventail de connaissances aux développeurs débutants, chercheurs et professionnels de l’IT
• Chaque chapitre inclut des exercices et des références bibliographiques, ce qui favorise l’apprentissage et l’autoformation
• Conformément à la licence Creative Commons, il peut être librement utilisé à des fins académiques et non commerciales

[GN⁺]

Avis Hacker News

• Je voudrais souligner que The Mathematical Theory of Communication de Claude Shannon est un texte fondamental de la théorie de l’information, expliqué de façon suffisamment accessible pour être lu même sans bagage mathématique approfondi lien

  • Je voudrais aussi dire que Shannon est une excellente porte d’entrée vers la pensée mathématique. Il a d’abord dérivé le concept d’entropie de l’information sans lui attribuer de signification particulière, uniquement à partir des propriétés requises. De façon remarquable, cette définition obtenue presque par hasard coïncide presque avec l’entropie thermodynamique en physique, ce que Von Neumann a signalé en lui donnant son nom. Les mathématiques avancent souvent par un raisonnement du type « si cela doit satisfaire telles règles », ce qui explique en partie pourquoi beaucoup les trouvent difficiles. L’article de Shannon n’a fait qu’établir l’ossature de la théorie du codage, sans en proposer d’implémentation concrète. J’ai autrefois animé dans une startup un club de lecture autour de la version livre de cet article, et je le recommande vraiment comme excellente expérience pour comprendre la théorie de l’information et les mathématiques en général

• Comme le domaine de la compression sans perte est étroitement lié à l’IA générative, ce serait intéressant d’ajouter davantage de contenu à ce sujet. Je voudrais recommander une thèse bien faite sur le lien entre compression sans perte et machine learning lien

  • Il n’est d’ailleurs pas nécessaire de limiter cela à la seule compression sans perte. En réalité, presque tout le machine learning peut être compris comme une forme de compression, le plus souvent avec perte. Par exemple, si l’on ne transmet que des embeddings sémantiques via un canal, il reste assez d’information dans ces embeddings pour effectuer la tâche sans disposer du texte original complet. La classification de données revient elle aussi à ne conserver qu’une représentation latente de catégories générales en jetant le reste. Dans le cas de l’IA générative, le fait de pratiquer une « compression avec perte » est précisément ce qui la rend efficace. C’est en supprimant volontairement une partie de l’information et en obligeant le modèle à inférer ce qui manque qu’on ouvre la voie à la généralisation. Un LLM sans perte n’aurait en pratique pas grand intérêt. En revanche, l’article recommandé est très particulier, car il traite de compression sans perte dans un domaine du machine learning où c’est rare

• Parmi les bonnes ressources récentes, il y a le manuel <i>Information Theory: From Coding to Learning</i>. Il existe aussi une version PDF en ligne, à laquelle il peut être utile de se référer lien

  • Je voudrais également recommander <i>Information Theory, Inference, and Learning Algorithms</i> de David MacKay lien

• Pour répondre à la question de savoir ce que signifie « coding » ici, il s’agit de l’acte d’encoder et de décoder une information en la transformant d’une représentation vers une autre. On appelle ces systèmes des codes, et ils sont conçus pour résister aux interférences, aux altérations ou à l’écoute lors de la transmission de l’information. Autrement dit, le codage est utilisé dans de nombreux domaines comme la compression de données, le chiffrement, la détection et la correction d’erreurs, ainsi que la transmission et le stockage de données lien

  • Le livre mentionné se concentre en particulier sur les codes correcteurs d’erreurs (error correcting code). On ajoute des données supplémentaires à un message afin de pouvoir reconstruire les parties perdues lors de la transmission. La difficulté à résoudre consiste à concevoir ces données additionnelles de manière à corriger suffisamment d’erreurs avec un surcoût minimal et dans un temps de calcul raisonnable. Cette technologie est utilisée en pratique dans des domaines très variés, comme le Wi‑Fi, les disques durs, les QR codes et la RAM. Par exemple, le « ECC » de la ECC RAM désigne justement un code correcteur d’erreurs. C’est une technique récemment devenue en partie obligatoire avec la DDR5

• Puisqu’on partage ici des ebooks gratuits de CS, je recommande aussi fortement le livre d’algorithmes de Jeff E. C’est une lecture indispensable pour quiconque veut apprendre les algorithmes ou réviser son niveau lien

• J’ai lu quelques chapitres de ce livre et j’en suis vraiment très satisfait. Je compte continuer à le lire tranquillement au cours des prochaines semaines, voire des prochains mois

• Si vous voulez approfondir la théorie de l’information et la théorie du codage, je recommande aussi les ressources suivantes. Pour les codes correcteurs d’erreurs, Error-Correcting Codes de W. Wesley Peterson et E. J. Weldon, Jr., et pour l’algèbre abstraite, en particulier la théorie des corps, Commutative Algebra de Oscar Zariski et Pierre Samuel sont de bonnes références

  • Les commandes LaTeX ne fonctionnent pas ici

• Si je devais citer quelques livres pour débutants, je recommanderais :

  1. <i>An Introduction to Information Theory, Symbols, Signals and Noise</i> de John R. Pierce — un classique très utile pour comprendre les concepts et développer son intuition. Les autres livres du même auteur sont également excellents
  2. <i>Information Theory: A Tutorial Introduction</i> de James V. Stone — une introduction simple et de qualité. Les autres tutoriels de l’auteur sont eux aussi utiles
  3. <i>A Student's Guide to Coding and Information Theory</i> de Stefan Moser et Po-ning chen — un guide concis et clair, et les autres livres de la même série valent aussi le détour

• Chaque fois que quelqu’un dit que « c’est indispensable », c’est toujours un moment un peu intimidant pour moi, qui n’ai fait qu’effleurer le sujet dans le cursus

  • Ici, « indispensable » ne signifie pas que tous les étudiants en informatique doivent absolument maîtriser ce contenu, mais plutôt que l’ouvrage condense l’essentiel de la théorie du codage. L’un des co-auteurs enseigne ce cours directement dans notre université, et il s’agit d’une option de niveau avancé extrêmement chargée en mathématiques. Dans un cursus de computer science sur quatre ans, seuls un tout petit nombre d’étudiants, généralement en dernière année, la suivent, et parmi mes connaissances, ceux qui l’ont prise étaient tous des personnes qui aiment les démonstrations mathématiques. Ils ont apprécié ce cours

  • Quand un livre est présenté comme « indispensable » ou « introductif », c’est souvent le signe qu’un manuel extrêmement dense vous attend