Scribd
Importer
42 vues342 pages

Crypto Martin

Transféré par

Lionel MVONDO
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
42 vues342 pages

Crypto Martin

Transféré par

Lionel MVONDO
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
COLLECTION TECHNIQUE ET SCIENTIFIQUE DES TELECOMMUNICATIONS Codage, cryptologie FoMAN Tey] eT reMlaca) ie Gf - f oy x 3 et applica ney PRESSES POLYT| COLLECTION TECHNIQUE ET SCIENTIFIQUE DES TELECOMMUNICATIONS Codage, cryptologie et applications Bruno Martin PRESSES POLYTECHNIQUES ET UNIVERSITAIRES ROMANDES Préface ‘Au conrs de nos premiers pas dans le domaine de la eryptologie, nous sommes tous confrontés A la subtile nuance entre “codage” et “chiffrement”. Tlest vrai que Pusoge courant de la langue frangaise nous induit souvent en er- renr. D'un point de vue formel, le “codage” se référe A une représentation, quelle quelle soit, de Pinformation. D’un point de vue plus technique, on cherche & y représenter l'information de manitre aussi efficace que possible pour communi- quer, archiver, calculer. Le “chiffrement” peut étre vu comme un cas particulier du codage : son objectif est également la représentation de l'information. Il est aussi la protection contre I'accés de personnes non habilitées et mal intention- nées. “Chiffre” est par conséquent synonyme de “code secret”. I est done naturel en apparence d’englober la cryptographic dans les sciences des techniques de codage. Ce serait pourtant ignorer leurs différences fondamentales. La cryptographie doit faire face & un adversaire malicicux. On cherche savoir s'il parviendra sans effort A percer le systéme. La théorie de la. complexité permet de quantifier la notion d'effort et joue done un réle central. En revanche, l’adversaire du codage (non cryptographique) est un phénoméne aléatoire : un “bruit”. On cherche done & coder ou & comprimer mieux sur un support donné. C'est ici Ja théorie de Vinformation qui permet de quantifier le bruit, et la capacité & le surmonter. Codage et eryptographie font donc face & des adversaires différents aut moyen de théories différentes. Pourquoi alors traiter ces deux disciplines dans un méme ouvrage? Comme les chapitres suivants le démontrent, ce sont en fait les applications et, leurs ou- tls qui les rassemblent. ‘Tous les systémes de communication (téléphone, cour- rier électronique, Internet ...) et les systtimes de stockage de données (disque compact, DVD, carte & puce ...) utilisent le codage. La phipart utilisent aussi des moyens cryptographiques pour sécuriser les données on protéger la pro- priété intellectuelle. Les outils fondamentanx proviennent de l’algebre discréte ct combinatoire et de Palgorithmique. On utilisera done corps finis, polynémes et espaces vectoriels, mais aussi arbres, graphes et automates. Codage et cryptographie sont aujourd’hui omniprésente. Il est done impor- tant de maitriser ces technologies. Peu de livres les traitent de manitre équili- brée. Le présent ouvrage présente brillamment les deux techniques. Il occulte volontairement, les aspects trop techniques et offre une présentation homogéne sous une forme mathématique. Ce livre est done recommandé aux étudiants en systdimes de communication et en informatiqne qui cherchent & comprendre leurs mécanismes de base, Nous leur souhaitons bonne lecture. Serge Vaudenay Professeur & EPFL Préambule Ce livre présente de fagon accessible & tous deux disciplines : la cryptolo- gie (on science du chiffre) dont Vorigine remontc aux débuts de Phistoire de Thomme et celle des codes correcteurs qui est née pendant la seconde moitié du 20° siécle, aprés l'nvention de Ia théorie de information. Toutes deux traitent ce la transmission sire de Pinformation. La eryptographie (ou Vart de conce- voir de bons chiffres) assure la confidentialité des communications en présence @ennemis. Les codes correcteurs permettent de retirer d’éventnelles erreurs de transmission. ‘Nons avons choisi d'orienter cet ouvrage plutét vers les applications en télé- communications numériques que vers abstraction théorique. Nous avons vo- lontairement simplifié le contenu mathématique de ces disciplines dans le but de mieux comprendre certains aspects du fonctionnement d’appareils que nous utilisons tous les Jonrs comme les Uéléphones cellulaires, les disques compacts ct les ordinateurs. Par exemple, sans codes correcteurs et. sans cryptographie, le développement des réseaux comme Internet ou bientét des réseaux dits «ad. hoc» (il s’agit des réseanx sens fil qui se construisent la demande et qui com- mencent & étre utilisés par les ordinateurs portables, les téléphones cellulaires, les appareils photos numériques ou les imprimantes) ne pourrait avoir lieu. Tl est d’ailleurs intéressant de noter que les différentes notions que nous présentons sont 4 la croisée d’tm grand nombre de disciplines comme Vinforma- lique (lant théorique que pratique), les mathématiques, mois économie et méme le droit. L’économie & cause du développement quasi continu d’Inter- net et de son impact‘social et économique et le droit. qui régit Putilisation des émes de chiffrement. Ce n'est que depuis quelques années que l'utilisation de chiffres est autorisée en France. La taille des clés est toujours limitée, sauf pour Futilisation de signatures électroniques. ance Présentation Cot onvrage est découpé en cing parties. La premiére présente la théorie de Vinformation de Weaver et Shannon dont le but était de quantifier le contenu en information. A ce titre, on Ini doit la notion de bit (pour binary digit). Il s'agit de la théorie qui permet de relier sous 1m cadre commun la compression des données, la théorie des codes et la cryptologie; ces différentes disciplines sont tontes prises en compte dans les problématiqnes de la théorie de information, La deuxiéme partie traite de la compression des données. Celle-ci devient de plus en plus présente dans notre vie quotidieme. C’est grace a la compression viii des domnées que nous pouvons communiquer au moyen de téléphones cellu- laires, regarder des DVD, trausmettre des quantités d’informations toujours plus grandes au moyen d'un modem ou méme d’Internet. Nous nous limitons ici aux seuls algorithmes de compression travaillant conjointement avec les mé- canismes de chiffrement dans les logiciels qui permettent dassurer la sécurité des communications au travers d'Internet. Pour transmettre un message au travers d’un canal de communication qui peut @tre perturbé (ou bruité), on lui ajoute de la redondance pour qu'il soit possible de détecter, voire de corriger des erreurs de transmission. C'est le but de la théorie des codes qui fait l'objet de la troisitme partie de ce livre. Pour présenter cette théorie qui peut devenir assez mathématique, nous avons pri- vilégié le point de vue de Vingénieur en informatique. Notre but est de faire comprendre les algorithmes de codage et de décodage nécessaires an bon fone- tionnement du mécanisine de détection ou de correction des erreurs de différents media de communication. Nous y présentons le principe de fonctionnement du mécanisme de correction des erreurs des disques compacts, celui des téiphones cellulaires de type GSM et ceux qui régissent certaines communications par satellite. Nous nous sommes efforeés de présenter la théorie des codes de Ia. ma- niére la plus intuitive possible, sans trop entrer dans les détails mathématiques. Dans la quatriéme partie, nous rappelons brigvement quelques faits de théo- ric de la complexité initiée par Rabin, McNaughton, Yamada, Hartmanis et Stearns dans les années 1960. Cette théorie est constamment pr p dams la problématique de la cryptographic. En effet, Pusage d’un chiffre est une course cntre les utilisateurs légitimes du systéme de chiffrement et des adversaires qui cherchent & retrouver leurs messages. II faut donc que le temps de calcu! d'une cryptanalyse excéde espéxance de vie de la confidentialité du cryptogramme. La théorie de la complexité permet de ranger des problemes algorithiniques dans différentes classes selon le temps de fonctionnement de leurs algorithmes de résolution. Nous y traitons la complexité de certains problémes liés & le théorie des codes (notamment celui du décodage) et nous présentons quelques problémes algorithmiques qui nous serviront dans la partie sur la cryptographie 8 clé publique, en particulier pour définir la notion de fonction A sens unique. Enfin, nous introduisons la eryptologie ou science du chiffre qui permet de transmettre des messages en préservant leur confidentialité en présence Aadversaires. Cette discipline regronpe A Ia fois Vart de concevoir de bons chiffres (cryptographie) et celle de les cryptanalyser. Dans cette partie nous nous sommes efforeés de respecter cette interaction en proposant pour la. phe part des chiffres présentés, soit leur cryptonalyse lonsque cclle-ci est connue, soit des attaques qui présentent leurs principales faiblesses, tant pour les chiffres clé secréte que pour les chiffres & clé publique. Le choix des méthodes de chiffrement repose d'une part sur leur intérét pédagogique et sur leur intérét «pratique» en extrayant un sous-enscmble consistant des méthodes adoptées par les différents standards. En effet, objectif principal de cette demiére par- tie est d'expliquer le fonctionnement de quelques protocoles sécurisés qui sont utilisés par Internet. Nous présentons notamment le fonctionnement d’un des ix protocoles qui permettent d’assurer la sécurité des échanges du Web en chit frant les communications. Son bon fonctionnement est généralement symbolisé par un petit cadenas verrouillé sur la fenétre de nos navigateurs. Utilisation Le contenu de ce livre provient de différents enseignements dispensés & PEcole Supérieure en Sciences Informatiques de Université de Nice Sophia- Antipolis et a l'Institut Supérieur d'Informatique ct d’Automatique de I’Ecole des Mines de Paris. Il s’inspire également de mon cours du DEA d’Informatique et de celui du DEA de Mathématiques, en collaboration avec 8. Julia. C’est la raison pour laquelle il est divisé en plusieurs parties qui peuvent étre Ines de fagon presque indépendante. Chagne partic est découpée en plusieurs chapitres courts qui présentert une notion précise. De nombreux exemples ct quelques exercices permettent dillustrer les notions introduites et de vérifier leur bonne compréhension. Cet ouvrage peut servir de support de cours pour des enseignements de deuxitme ou de troisitme cycle universitaire ou introduction pour des ingé- nieurs ou des chercheurs qui souhaiteraient se familiariser avec les différentes disciplines qui y sont présentées. Remerciements ‘Tout d'abord, je dois beaucoup A la Maitrise de Mathématiques Discrétes de PUniversité de Lyon 1 et & ses enseignants-chercheurs. Cc sont enx qui mont connaitre, entre autres, Ia théorie des codes et la cryptographic. Je voudrais remercier J. Gruska pour m’avoir suggéré d’écrire ce livre & partir de mes notes de cours, C. Peyrat pour m’en avoir relu des versions préliminaires et H. Ben Azza pour ses cncouragements. Plusicurs personnes ont contribué & cet ouvrage : J. Leroux m’s fourni des explications sur la théorie de l'information ; P. Solé ct Ling San ont répondu aux nombreuses questions que je leur ai posées sur les codes correcteuts, J. Bond, M. Bronstein et M. Santha ont éclairci des points d’algorithmique et de com- plexité. Je remereie également mes étudiants ; c'est grace & leurs questions et & leurs réactions que le contenu de mes notes de cours s’est pet A peu enri Enfin, un grand merci aS. Julia. Son soutien, ses relectures et nos discussions mont permis de mener A bien Pécriture de ce livre. Table des matiéres Préface Préambule ‘Théorie de information 1 Théorie de Vinformation 1.1 Introduction . . 1.2 Information et mesure de l'information 1 1.4 Codage en présence de bruit 15 1.6 Observations ....-.-- Codage pour un canal non bruité ‘héorémes de Shannon. . . Compression de données 2 Compression de données QA Introduction... 5. eee eee 2.2. Types d’algorithmes de compression 23 Définitions 2.4 Techniques de base . - 2.5 Algorithmes statistiques... 0.2... eee ee 2.6 Algorithmes dynamiques 2.02 ee 2.7. Limites de la compression 2.8 Observations Codes correcteurs d’erreurs 3 Généralités sur la théorie des codes 3.1 Distance de Hamming et boules . . Problame du codage & longueur fixe Probléme du décodage ©... ee eee Be » aa we 10 4 15 17 17 18 19 19 21 24 32 33 35 37 37 39 42 xi Codage, cryptologie & applications Codes linéaires 4. 42 4.3 44 45 46 47 48 49 Préambule mathématique Définitions. . 6... Décodage par les classes latérales Exemple de décodage par le tablean standard Codes duaux Décodage par le syndrome - Exemple de décodage par la table des sy) deans Quelques propriétés des codes linéaires . ‘Observations Codes de Hamming Définition Propriétés des codes de — Décodage Codes de Hamming étendus . . Observation .. . Code de Golay étendu 6.1 6.2 6.3 6.4 6.5 Matrice génératrice . Propriétés du code Décodage Exemples Observations Codes de Reed-Muller 71 7.2 a 74 78 nition inductive Matrices génératrices . Propriétés du code Décodage Observations ©... 6. Codes cycliques 8.1 82 8.3, 8.4 85 86 Description Représentation polynomiale Les facteurs de 2” —1 sur Fz - - Implantation du codage par les codes cycliques . Inuplantation du décodage des codes cycliques . - Exemples de codes cycliques 288 65, 65 66 67 68 69 Table des matiéres 9 Codes correcteurs de paquets d’erreurs OF DARMBOEE. . chase ce ene ome d FHOEE 9.2. Vers un nouveau probleme de décodage 9.8 Décodage we aes ae 9.4 Technique dentrelacement 0.5 Technique dentrelacement avee retard ©. 9.6 Technique d’entrelacement croisé 10 Introduction aux codes convolutifs 10.1 Elkéments de base . 10.2 Godage: 0.20.2. see a eed eeeaes 10.3 Capacité de correction... 10.4 Décodage 11 Application des codes correcteurs dans l'industrie 11.1 Code du disque compact ee 11.2 Code des CD-ROM . aww 2 Fine einen w EEE 11.3 Code du mimitel. 0... eee 11.4 Codes des réseaux informatiques ©. 6-6 6 - eeeeee 115 Codage de la paroledu GSM 2... 000.00 11.6 Codes de transmissions satellitaires Complexité 12 Théorie de la complexité 12.1 Problémes de décision, de calcul ct leur codage . . . 12.2 Machines de Turing déterministes ..... 62s e 12.3 Classe du temps polynomial pour les machines déterministes 12.4 Machines de Turing non déterministes ..-. . . « 12.5 Classe du temps polynomial ponr les moddles rion déterministes 12.6 Les langages NP-complets ... 6... - a ahec FD sasnciedt xiii 87 87 88 89 90 91 92 95 95 101 104 107 107 109 110 110 112 116 119 121 121 123 125 126 127 xiv Codage, cryptologie & applications 13 Complexité des problemes de théorie des codes 13.1 Probléme du décodage des codes linéaires 13.2 La NP-complétude du décodage linéaire 13.3 La NP-complétude du problizne de I'existence d’un vecteur de poids donné 13.4 La NP-complétude du problime de la distance minimale sur Fz 13.5 La NP-complétude du probléme de la distance minimale 14 Complexité des problémes de cryptographie 14.1 Probléme de la somme de sous-ensembles 14.2 Probléme de la primalité . 14.3 Une amélioration récente, Primes € P 14.4 Probleme du logarithme discret, Cryptologic 15 Introduction & la cryptologie historique 15.1 Introduction . . 15.2 Chiffres monoalphabétiques 15.3 Cryptanalyse des chiffres monoalphabétiques 15.4 Chiffres polyalphabétiques 15.5 Cryptanal 15.6 Chifires & transposition du chiffre de Vigenére 16 Cryptologic technique A elé secréte 16.1 Chiffre de Vernara 16.2 Machines & rotors 16.3 Chiffres produits et itérés 16:4: DES 2.4 ce eee 17 Cryptanalyses différentielle ect linéaire des chiffres itérés 17.1 Présentation du chiflre utilisé 17.2 Cryptanalyse différentielle . 17.3 Cryptanalyse linéaire . . 133 133 134 135 136 138 139 139 M4 143 145 147 149 149 153 156 158, 161 163 163 164 168 169 Liz LIT 179 184 ‘Table des matiéres 18 Deux chiffres robustes : IDEA et AES 18.1 IDEA 4 18.2 La stlection de AES 18.3 Rijndadl .... 0... -- 19 Différents modes de fonctionnement 19.1 Mode ECB ....-- 19.2 Mode CBC 19.3 Modes OFB et CFB . 19.4 Modification Detection Code et Message Authentication Code 20 Cryptographie & clé publique 20.1 Merkle Hellman... WRIA ae cues oo as 20.3 Le probleme du Iogavithme discret, 20.4 El Gamal 21 Signatures numériques 21.1 Mécanisme général de signature... 21.2 Signature par RSA... 6.6 + 21.3 Signatnre par Fl Gamal 21.4 Digital Signature Standard (DSS) 22 Fonctions de hachage 22.1 Définition d’une fonction de hachage 22.2 Fonctions de hachage & collisions difliciles paps abe ee 22.3 Dimensionnement du nombre de bits d’une fonction de hachage 22.4 Hachage par le logarithme diseret 22.5 Hachage compressif 22.6 Fonction MD5 ~ 22.7 Fonction SHAT... 2... 22.8 Digital Signature Algorithm (DsA) 22.9, Autres applications des fonctions de 23 Sireté des chiffres & clé publique hachage 23.1 Cryptanalyse du chifire de Merkle-Hellman 23.2 Atlaques par factorisation de RSA 23.3 Calcul du logarithme discret . . xv 193 193 197 198 205 205 206 207 208 209 210 213 221 221 223 224 225 227 231 231 232 233 234 235 237 241 244, xvi Codage, cryptologic & applications 24, Génér: n de suites pseudo-aléatoires 24.1 Motivation ... . a hoe 0 Bg 1 ener hoe 24.2 Génération de suites aléatoires 24.3 Génération de suites pseudo-aléatoires 24.4 Générateur RSA 25 Certification 251 Introduction... 2... eis Fel eset en ils bake 25.2 Forme générale d’un certificat 25.3 Utilisation ct réalisation asymétrique 25.4 Utilisation ot réalisetion symétrique 26 Gestion des clés 26.1 Exemple introductif 26.2 Gestion des clés . . 26.3 Distribution des clés publiques ©... ee 26.4 Distribution des clés secrétes 26.5 Mise en accord par Diffie Hellman 26.6 Mise & jour des clés 27 Applications de la cryptographic A la sécurité des réseaux 27.1 Motivation é 27.2 Introduction &. la sécurité 27.3 Introduction aux protocoles réseaux 27.4 Mots de passe jetables : 27.5 Kerberos. . . Sees ae aa re kA P awe 27.6 Sécuriser les courriers électroniques . 27.7 Sécuriser les échanges TCP/IP. 27.8 Sécuriser la couche de transport A Utilisation des registres linéaires A décalage A.1 Arithmétique sur les polyndmes . B Table de polyndmes irréductibles primitifs sur F, C Tables des fréquences relatives des lettres Index Bibliographic 267 267 268 268 271 273 273 274 275 278 281 281 281 283, 284 290 291 291 291 293 298 301 307 314 319 320 325 327 329 339 PREMIERE PARTIE Théorie de l’information CHaPITRE 1 Théorie de information 1.1 Introduction La théorie mathématique de Pinformation est issne des travaux de Wear ver et Shannon [84] publiés en 1964. Ils s’intéressent en particulier & aspect quantitatif de l'information (notion d'entropie). Le schéma de communication proposé par Shannon est décrit par Ia figure 1.1 ot la source d’information produit un message sous la forme dune suite de bits qui est transformée en un signal acceptable pour le canal, medium utilisé pour la transmission comme, par exemple, un réscau hertzien, un cable ethernet ou un bus d’ordinateur. Le signal est alors recu par le récepteur qui effectue en général Popération inverse de T'émetteur, reconstruisant ainsi le message et le délivrant au destinataire. Un tel systéme de communication peut étre scindé en trois catégories : 1, les systémes diserets pour lesquels message et signal sont deux suites de symboles choisis daus un alphabet fini; 2. les systémes continus pour lesquels message et signal sont considérés comme deux fonctions continues; 3. les systtmes mixtes oi on mélange les denx types de systémes précédents, signal SOUPCO | HICSSABS | emetteur] iréceptour|_ SAE? | destinatair info. source dd bruit Fig. 1.1. Schéma de communication. Nons ne nous intéresserons qu’aux systémes discrets pour lesquels on cousi- dére les problemes du canal bruité et du secret. Dans le probleme du canal bruité, le signal peut étre bruité entre Pémetteur et le réceptenr (c’est-A-dire perturbé par un signal al¢atoire). Dans ce cas, pour recouvter le message émis & partir du signal regu, l’émetteur va ajouter des bits de redondance. Ceux-ci vont permetire an récepteur soit de détecter soit de corriger une ou plusieurs erreurs. Dans Je premier cas, il s'agit de codes détecteurs d’erreurs et dans le second de codes correcteurs d’erreurs. Le but 4 Information et mesure de Vinformation de la théorie des codes est de transmettre rapidement et correctement dee messages. Dans la problématique du secret, on se sert dun abruity pour perturber Ie message et en cacher le contenu. Le réle de Pémetteur est alors de construire une perturbation du message dans le but d’empécher un ennemi,le cryptanalyste, de cxyptanalyser le message A partir du signal mais, en revanche, de permetire au destinataire légal de retrouver le message d'origine. 1.2 Information et mesure de l'information. 1.2.1 Information ct quantité d'information Une information désigne par définition un ou plusieurs événements possibles parmi un ensemble fini d’événements. L’information permet de diminer Fin- certitude. Considérons par exemple une source qui peut produire trois symboles A,B et C. Quand Je destinataire attend un symbole, il est dans Vincertitude quant an symbole que la source va engendrer. Lorsque le symbole apparait et qu'il arrive au destinataire, cette incertitude diminue. Le but de la théorie de Finformation est de mesurer cette incertitude avant réception. La manitze la plus simple est de dire que le destinataire a une incertitude de trois symboles Prenons un second exemple. On recherche un fichier daus une arborescence. Si on précise que le fichier se trouve dans le dossier syst?me, on fournit une information qui diminuera le temps de recherche du fait que le nombre de fichiers dans le dossier systéme est plus restreint. Si on ajoute l'information que le fichier est en sus un fichier de police de earactéres, on pourra abréger dantant, plus le temps de la recherche. La quantité d'information est définie comme une fonction croissante de ot —N est le nombre d'événements possibles; ~—n est le cardinal du sous-ensemble dénoté par l'information. Pour mesurer cette quantité (information, on pose N r= ne, (= es (*) Sion dispose de denx informations, 1a quantité d'information globale n’égale pas forcément le somme des quantités information comme en atteste Yexemple Ll: qui est exprimé en logon. o ‘Théorie de Pinformation Exemple 1.1 Soit NV le nombre total de fichiers, n, le nombre de fichiers sys- tame, nz le nombre de fichiers de polices de caractéres et n le nombre de fichiers de polices de caractéres du dossier syst?me. Quand on indique que le fichier re- cherché se trouve dans le dossier systéme, la quantité d'information associée ext de log (2) logons. $'il s'agit d’une police de caractéres, on a logy ( 2 nr 2 \ na logons et dune police de caractéres du dossier systéme, log, () logons. Pour faire intervenir les informations particlles dans information globale, on éerit = N Nm N nm IN ata N logy ~ logy ~."* =logg — + loge “* =logy * + 10g, ea n O82 nm oe m1 +82 n wee Ng 1 loge ne + 108. n of log, (41) donne Vindication police de caractéres quand. on dispose déja de Vinformation dossier syst’me. Avec NV = 5384 fichiers, 71 = 1097 fichiers sys- time, nz = 358 fichiers de police de caracttves dont n = 58 dans le dossier syst2me, information «un fichier systéme» vaut log, ($384) = 2, 3 logons; — «un fichier police de caractdres» vaut, log, (S84) = 3,91 logons ; «un fichier police de caractéres du dossier systémey vaut log, (2334) = 6,54 Jogons ; et non 2,3 +3, 91 = 6,21, somme des deux premitres informations. 1.2.2 Entropie Lentropie va nous permettre de mesurer Ja quantité (information moyenne contenue dans un ensemble de messages et de mesurer ’incertitude a priori. Soit. E un ensemble partitionné en n sous-ensembles Ej, 1 < i ) = =i Du fait que les E; forment une partition de E, 7,1 = 1 et Ventropie correspond A la distribution de probabilité de tous les messages possibles. 6 Information et mesure de Pinformation Exemple 1.2 Soit unc urnc contenant 2 boules blanches ct 6 boules noires. On considére 'expérience qui consiste & tirer une boule. La probabilité de tirer une boule blanche est de 1/4 et celle de tirer unc noire est de 3/4. Tlen résulte que la quantité @’information liée 4 Papparition d’une boule blanche est de log,(4) = 2 logons ot de log, (4/3) = 0, 42 logon pour une noire Le raisonnement ci dese 1¢ permet d’évaluer la quantité d'information fournie par le tirage qu’aprés la réalisation de Pexpérience. Le raisonnement a donc trait an résultat de Vexpérience et non A Pexpérience elle-méme. Pour évaluer Vexpérience a priori, il faut faire appel aux propriétés statistiques des résultats de Vexpérience. Si on réptte wm grand nombre de fois Vexpérience, Ja Joi des grands nombres nous dit que, et moyenne, on tirera une blanche une fois sur quatre et une noire trois fois plus souvent. Dans ces conditions, ka quantité information moyenne par expérience sera, donnée par Pentropic 1 3 4 H = 7 Jows(4) + Flog, (3) = 0,81 logon qui teprésente entropic de la Jol de probabilité donnée ci-dessus. Intuitivement, la quantité d’information obtenue par Fapparition de E; est définie par I(E;) = loga(1/pi) et représente le nombre de bits nécessaires au codage optimal du message Ey, i.e. qui minimise le nombre mayen de bits du signal correspondant:& K;. Cette quantité est maximale quand il y a équidistri- bution des n messages ot l’entropie H vaut alors log,(7) et minimale lorsque Ja, probabilité @un message E est égale A 1, cas pour lequel Ventropie H est nnlle. Tentropie d’nn message mesnre son incertitnde en ce sens qn’elle fonrnit Je nombre de bits d’information qui doivent étre appris lorsque le message a été perturbé en traversant un canal bruité ou masqué dans un cryptogramme. Exemple 1.3 On s‘intéresse au nombre de bits nécesssires an codage des don- nées homme et femme dans une base de données lorsqu’il y a équiprobabilité des données. L’entropie vaut i A H = 5 log, (2) + 5 logy(2) = 1 Dans ce cas, le champ «sexe» de la base de données ne requiert qu'un seul bit d'information pour déterminer le sexe d’un individu. Pour un champ d’infor- mation ayant la méme sémantique mais codé au moyen @’un caractéze alpha numérique, on n’anra pas plus information mais on aura, besoin de plus de bits 1.2.3 Taux On considére, pour une langue naturelle donnée, l'ensemble X des mots de NV lettres et on définit alors r, le taur de la langue pour des mots de longueur NN comme le rapport HRD ~N "Théorie de Vinformation 7 ‘ou, en d’autres termes, le nombre moyen de bits d’information fourni par chaque ceractére. Pour une langue naturelle ot un NV’ suffisamment grand, le taux de Ja langue r est compris entre 1 et 1,5. Le taur absohi R de la langue est alors défini comme le nombre maximal de bits d'information qui peuvent étre codés par chaque caractére sous 'hypothese que ceux-ci sont tous équiprobables. Aiusi, pour un alphabet de L lettres, le taux absolu est Ja quantité logy(L), qui vaut 4,7 pour un alphabet latin. On illustre ainsi le fait que les langues sont redondantes et il est possible de mesurer cette redondance D par D=R-r La redondance de la langue anglaise est, par exemple de 3,7 et le rapport D/R montre que cette redondance est de Pordre de 68%. Exemple 1.4 (Jeu de Shannon) Lors de ses réceptions, Claude Shannon prenait un livre de littérature qu'il ouvrait au hasard. Ensuite, il commen- gait & lire un paragraphe puis s’arrétait. A ce moment précis commengait le jeu qu’il avait imaginé : il épelait lettre apres lettre les mots du paragraphe ‘dans Pordre od ils étaient écrits. Mais, & chaque lettre nommée, il demandait & Tassistance de bien vouloir lui donner la lettre suivante. II notait alors les ré- ponses, bonnes ou mauvaises. Si les invités ne trouvaient pas la lettre suivante, 4] la leur fournissait, En opérant un certain nombre de fois, Shannon a cal- culé expérimentalement 1a proportion de bonnes réponses qui avuisinait 75%. Ten déduisit, que la redondance de la langue anglaise est de 3/4, i.e. que trois lettres sur quatre en moyenne sout inutiles, puisque ses invités parvenaient & reconstruire le texte avee seulement une lettre sur quatre. 1.3 Codage pour un canal non bruité ‘Afin de transmettre un message sous Ja forme de signal, il faut le coder ; c'est ce que ’on nomme également codage de source. Le mode de codage dépend alors du moyen de transmission (écriture, parole, code Morse, code ASCII et unicode sont autant de modes de codage différents). Le plus souvent, on considére des codes binaires i.e. sur Valphabet {0,1}. Les codes peuvent étre définis A l'aide de la théorie des langages. Soit = umn alphabet et. 5* Pensemble des mots finis sur cet alphabet. Un code C= {e1,-..,e) est un sous-ensemble de E*. Les éléments «, € C sont appelés les mols du code. $i tous les mots du code sont de méme longueur, on dit que C est un code @ longueur fixe ou code en bloc. Dans le cas contraire, C est un code a longueur variable. Un code C est appelé préfize si aucun mot du code west le préfixe d’un autre. Exemple 1.5 Pour alphabet, binaire © = {0,1}, ensemble de tous les mots sur © est 5* = {e,0, 1,00, 01, 10, 11, 000, ...}. 8 Godage pour un canal non brnité Cc {010,11} décrit. um code préfixe A longueur variable ={1,01,11} écrit un code non préfixe & longueur variable CC" = {000,101} décrit un code longueur fixe ou code en bloc 1.3.1 Codes optimaux En associant des codes courts aux messages les plus fréquents et des codes longs pour les autres, on peut construire un code optimal, au sens of le nombre moyen de bits par symbole correspond précisément & lentropie de Peusemble des messages possibles. Un premier exemple d’une telle idée est le code morse = AT ]®)- Cy]- ]> E F @)-« |B I - J K L M|-- | NI- oO |---|/P Q R s T|- U ¥v Wi e- X | Y Zz Huffman a proposé un algorithme qui construit un code préfize optimal pour une source S, comprenant r messages sur un alphabet binaire fondé = sur une procédure de réduction qui permet de transformer S, en une source ar —Lsymboles S;—1 pour obtenir finalement une source & deux symboles pour laquelle le code préfixe optimal est {0,1}, et sur une propriété qui permet de construire inductivement un code préfixe en rajoutant les symboles de source retirés précédermment. Le principe de la construction des codes de Huffman sera présenté plus en détail dans la. suite de cet ouvrage dans la section 2.5 du chapitre 2 sur la, compression. 1.3.2 Codes a longuear fixe ‘Dans le cas des codes binaires & longucur fixe, on souhaite coder des messages de longueur k av moyen de mots du code de longueur n. On a ajouté n — k symboles de redondance. Si le code comprend w mots, la quantité dinformation véhiculée est loge) et le rendement du (n, k)-code est logy (w) n 1.3.3 Longueur moyenne d’un code Si S = {s1,52,---,5x} est un alphabet de source tel que p; représente la probabilité (apparition du symbole #, et sie; ++ X; est un code of X, est un mot de longueur [,, on définit la longueur moyenne du code comme : k b= yopili ‘Théorie de Pinformation 9 qui correspond @ Ia somme pondérée des longneurs de tous les mots et qui coincide avec L', rapport entre le nombre de symboles binaires du message codé ct le nombre de symboles de source quand le message est de longueur suffisante pour que tous les symboles apparaissent avec une fréquence relative égale & leur probabilité. On est alors amené a attribuer aux messages les plus fréquents des codes de courte longueur. C'est: cette idée qui a été exploitée par Morse et par Huffman. Exemple 1.60n calcule la longueur moyenne du code A ++ 0, B +> 10 et C1 de probabilités respectives 1/2, 1/4,1/4. 1 1 1 1 sat oe’ atta ta 1,5 1.8.4 Efficacité et redondance Soit Palphabet de source suivant : S = {A, B} tel que pa = 0,8 et pp = 0,2 codé par Ar 0 et B+ 1. Lrentropie de la source est de —0,8logy(0, 8) — 0, 21og,(0, 2) — 0, 72 logon et sa longueur moyenne est 0,8-140,2-1= 1 On définit Vefficacité comme le rapport Dans notre cas, I'efficacité 7 = 0, 72 soit une redondance 7 = 1 —7 de 28%. Autrement dit, méme en choisissant le code le plus court possible, on perd 287% du temps de transmission. Comment peut-on diminuer cette redondance et améliorer Pefficat Une idée est de coder des couples de symboles au lieu des symboles eux-mémes (cf. figure 1.2). On obtient ainsi : symbole | probabilité AA 0 AB ll BA 100 BB 101 Si on calcule I'entropie de la source, on obtient la valeur de 1,45 logon : 0,64 logy (as) +2 (0. 1G logs (ae)) +0, 04 log (au) =1,45 La longueur moyenne de ce code est de 0, 6442-0, 16+3-(0, 16-+0, 04) = 1,56 doi une efficacité 7 de #35 = 0,93 et une redondance de 7% au lieu des 28% préeédents. En revanche, le coat A payer est une complexification des opérations de codage ct de décodage. On montre que, en faisant ercitre le nombre de symboles qu’on code, l'efficacité du codage peut devenir aussi proche que possible de sa limite supérieure (égale A 1). C’est précisément la signification du premier théoreme de Shannon que nous énongons dans In section 1.5, 10 Codage en présence de bruit BR(O,04) RA(O, 16) 1 AB(0,16) BBBA(0,2) 1 0 ABBBBA(0,36) AA(0,64) Fig. 1.2 Arbre associé au code de Hufiman. 1.4 Codage en présence de bruit Lorsqu’un signal est transmis au travers du canal de transmission, il peut @tre perturbé par un bruit. Le but du codage en présence de bruit, aussi appelé codage de canal, permet an récepteur de recouvrer Je signal d'origine méme si celui-ci a été altéré, Bien éviderament, le codage dans ce cas dépend forte- ment dn canal. Aussi, allons-nous coummencer par une modélisation du canal de transtnission. 1.4.1 Canal de transmission On considére Je cas d’un canal binaire symétrique décrit dans la figure 1.3. 0 — @° po ? 1 te! 1-p Fig. 1.3 Canal binaire symetrique. Pour celni-ci, p correspond & la probabilité de recevoir 1 alors que 0 a éé émis ou, symétriquement, de recevoir 0 alors que 1 a été émis. Si on appelle distance entre deux mots binaires le nombre de syniboles ott ils different, la probabilité de recevoir un mot de longueur k qui différe sur d positions du mot envoyé est : K (iyo — py ant ‘Théorie de Vinformation ul Exemple 1.7Si on a émis le signal 11010 ct regu 10011, les mots different en deux positions. En prenant p = 0,1, la probabilité de recevoir un mot pour lequel 2 bits ont été altérés est (5)0,9% - 0,1? = 10 - 0,0073 = 0,073 ct un mot avec une seule erreur est de (°)0,9* 0,1 = 5- 0,06 = 0,3. On voit que, pour ce canal, il est plus probable de recevoir um mot avec une seule erreur de ‘transmission qu’un mot avec deux erreurs de transmission. On souhaite déterminer la quantité d'information transmise par le canal. Lorsque p > 0 et qu’un bit d'information est transmis, si une erreur se pro- duit, la quantité d'information perdue est, par définition, log9(3). En moyenne, plog,(3)- Lorsqwil n’y © pas d’erreur, la quantité d'information perdue est, en moyenne, (1 ~ p)loga(z4)- La quantité totale d’information perdue est plog(4) + (1 —p) loga(q4p) La quantité d'information qui est effectivement transmise par le canal est ln capacité C(p) qui vaut 1 (plows (2) + (L—p) logy (=) =1 + plogg(p) + (1 — p)log2(1 — p) t— Exemple 1.8 Avec une probabilité d’erreur de 1%, la capacité du canal binaire symétrique est: C(O, 01) = 1 — (0,07 + 0, 01) = 0,92. 1.4.2 Equivoque Soit A = {a1,..-,an} les symboles de source ct B = {by,..-,bin} les sysn- boles du code. Tes symboles de A ayant une certaine probabilité, on peut cal culer l’entropie de la source H(A). Cependant, si on considére le code B, on ne connait pas H(A) mais on peut s’en faire une certaine idée en fonetion des bj au moyen des probabilités conditionnelles P(a;/b;) correspondant: ) la probabilité avoir le message a; sachant que le symbole b; a été regu. On peut donc cal- culer H(A/b;), est-a-dire Ventropie de la source connaissant bj. Si on caleule la moyenne des H(A/bj) Glendue & Pensemble des b,, on obtient H(A/#) qui correspond précisément & la notion 4’ équivoque. Etant donné b © B tel que 32”, P(b;) = 1, soit P(@/b) la probabilité conditionnelle que @ ait été codé Jorsqu’on a recn 6 et P(@,b) la probabilité jointe du message a et du symbole b. En rappelant la formule de Bayes P(a, b) = P(a/b)P(b), on caloule Péquiveque comme : H(A/B) = — Xap Pa, 6) logy(P(a/b)) Yap Pl, 0) love per) =¥s (POT. Pl@/!) oral wen)) Un exemple simple de calcul de P’équivoque est Vexemple 1.9. 50 Décodage par les classes latérales Preuve (1) Sia € (Z2)", alos at+0 Ca tC. (2) On considére Vapplication de C+a+C définie par c+ a+ pour a € (Za)". Pour tout mot 2 de C, Papplication est bijective, done ja + C| — |C| = 2. (8) Supposons que a }CNb+C # 2. Alors, il existe v € (Z2)" tel que a+CNb+C contienne l’élément v. Pour = et y éléments de C, 1 =a +2=b ty ce qui implique que b= a+ (zy) €a+C et, par le lemme, b+ C =a+C. a On partitionne alors (Z2)” en (0+C)U(t1 +C)U.. U(us $C) ots = 2"-F=1 ot ott les 0, 11, ...,u, sont des éléments de poids minimal appelés chefs de classe. On peut alors construire le tableau standard de C qui est: une matrice & 27-* lignes et 2* colonnes. I] contient tous les vecteurs de (Z2)". Sa premitre ligne correspond aux mots de C avec le vecteur 0 A gauche; les autres lignes repré- sentent les classes latérales u;+C avec leur chef de classe & gauche. L’algorithme suivant permet de construire le tableau standar (1) on énumére les mots de C en commengant par 0 sur la premiere ligne ; (2) on choisit un vecteur ude poids minimal qui n’apparait pas dans la pre- mitre ligne et on Gnumbre sur la deuxidine ligne les éléments 1 + C en inscrivant au-dessous de 0 le chef de classe 1, ct an-dessons de chaque é6- ment « € C Vélément wi +25 (8) on choisit un vecteur ug de poids minimal qui n’apparait pas dans les pre- mitres lignes et on énumére sur la troisiéme ligne les éléments wz + C en inscrivant au-dessous de 0 le chef de classe uz ct an-dessous de chaque élé- ment x € C l’élément us + #5 (4) on itére ce procédé jusqu’A ce que toutes les classes latérales soient listées ot que tout vecteur de (Z2)" n’apparaisse qu’une seule fois. Le décodeur va, utiliser le tableau standard de la fagon suivante : lorsque le mot y est recu, on recherche sa position dans le tablean standard. Le décodeur décide alors que le vecteur d’erreur e correspond au chef de classe qui est situé dans la premiére colonne de la meme ligne et peut décoder y comme # = y—e on choisissant le mot du code de la premiere ligne sur la meme colonne que y- Les vecteurs d’erreurs qui pourront étre corrigés sont précisément les chefs de classe, quel que soit Je mot du code transmis. En choisissant des vecteurs erreur de poids minimal en tant que chefs de classe, le tableau standard assure un décodage au plus proche voisin. Observons cependant que ce procédé de décodage est trop lent pour de grands codes et trop cotiteux en termes de mémoire. En effet, si le nombre ‘Théorie de Vinformation 13 qui nous intéressent : nom | P(./0) = P(..0)/P() | PC/) = Pl. 0/PO) 0, 64/0, 76 = 0,84 0 0=0 0, 11/0, 76 = 0,14 0,01/0, 76 = 0, 02 ages Et onfin, on caleule Péquivoqne : H(A/B) = Dy, (Po) e P(a/®) or e275)) —P(a/t) logs Pla/6)) 0,21 e = 0, 0,11 0,72- P(Q) = 0,55 0 0,39 0.47 0,37 1,23: P() = 0,84 arerloocode Raeslan cals Done H(A/B) = 0,84 et H(A) = 1,45, H(A) — H(A/B) = 0,61. La connais- sance d'un symbole du code permet de rédnire Vincertitude sur le mot codé & 0,61 logon. 14.3 Vitesse de transmission d?wm message Soit une source qui émet des symbolos binaires de fagon équiprobable an travers d'un canal binaire symétrique de probabilité d'erreur p = 1%, on a vu précédemment que entropic de la source est de 1 logon par symbole et que la capacité du canal est de 0,92. Comme chaque symbole peut étre erroné, on ne peut reconstituer le message transmis. Pour remédier & ce probleme, on peut répéter trois fois le symbole émis (crest le code de répétition) = loi 0+ 000 Dans ces conditions, le récepteur recevra, une suite de trois symboles binaires et pourra, par majorité, déduire quel était le symbole émnis. Plus généralement, si pour chaque symbole 1 & envoyer, on en transmet 2n +1, on réduit la probabilité erreur en méme temps que n croit. Le rapport nombre de signaux hinaires transmis nombre de signanx binaires utilisés est appelé vitesse de transmission du canal et la probabilité d’erreur du déco- dage tend vers 2éro en méme temps que la vitesse de transmission. 4 ‘Théorémes de Shannon 1.4.4 Codage optimal Le codage optimal en présence de brnit a été résolu dans le second théoréme de Shannon qui présente un résultat inattendu. I affirme en effet: qu’il existe des codes conduisant a des vitesses de transmission aussi voisines que voulues de la capacité du canal et qui permettent de rendre la probabilité d'erreur de transmission inférieure & tout nombre fixé. Hélas, ce théor®me est existentiel. Cela signifie qu'il ne contient aucune indication sur la maniére de construire un tel code, A Vheure actuelle, pour tous les codes connus, la vitesse de transmission tend plus ou moins vite vers zéro en méme temps que la probabilité d’errenr de transm 1.5 Théorémes de Shannon (1) Théoréme du codage de source : Sans perturbation, il est possible, & partir d'un alphabet quelconque, de coder les messages émis de telle sorte que Je rendement soit aussi proche que souhaité de la valeur maximate, ie. Ia capacité du canal. (2)'Théoréme fondamental : avec perturbation, il est possible, gréice A un codage adéquat, d'assurer un rendement aussi proche qu'on le souhaite de la valeur maximale, i.e. la capacité du canal bruité, avec une probabilité erreur arbitrairement petite. Le théoréme fondamental peut étre appliqué au cas du canal binaire symé- trique Théoréme 1.1 Soit C(p) la capacité du canal de transmission et soient deux valeurs arbitraires 5 > 0 et R < C(p). Il existe un (n.k)-code de longueur suffisamment grande tel que £ > R et tel que la probabilité de décoder incor recternent un mot recu est strictement inférieure & 5. Coder est une opération efficace an prix dune certaine redondance. Cela justifie Péhide de la construction de codes. 1.6 Observations Pour plus de détails, nous laissons an lecteur le soin de se reporter & des ouvrages sur In théorie de Pinformation, soit généralistes comme [7, 43], soit plus spécialisés comme le livre de Roman [80] qui est beaucoup plus exhaustif. Nous avons également décidé de ne pas présenter plus en détail la probléma- tique du secret et, en particulier, la notion de distance unicité qui permet de mesurer la quantité de cryptogramme nécessaire pour mener & bien certaines cryptanalyses. Pour cet aspect précis, le lecteur intéressé pourra consulter le livre de Robling-Denning (79). DEUXIEME PARTIE Compression de données CHAPITRE 2 Compression de données 2.1 Introduction La compression de données date du 19° sigcle avec V'invention du Braille on 1820 et du code Morse en 1838. Elle a été formalisée erfice a la théorie de Vinformation. En effet, la compression fonctionne «& Vinverse» du codage, une des problématiques de la théorie de information, Si le codage ajoute de la rodondance pour transmettre un signal en tonte sécurité sur un canal bruité, la compression va, elle, tenter de retirer le plus de redondance possible d'une donnée. Les principales applications de la compression coneernent Varchivage des données, que ce soit sur un disque dur, un disque compact ou un DVD. En ef- fet, les supports d’archivage de données se remplissent aussi rapidement que leur taille croit. Ainsi, les mises A jour de logiciels qui, il y @ quelques années étaient enregistrées sur unc simple disquette, sont de plus en plus souvent comprimées, leur taille dépassant Ie contenu maximal d’un CD-ROM. Certains formats de fichiers inttgrent directement de la compression. C’est par exemple le cas pour les fichiers d'images (fichiers gif on jpeg) mais aussi pour certains fichiers texte comme avec le portable document format d’Adobe. Dans le domaine des télé- communications, la compression de données est conramment ntilisée dans le fonctionnement des modems (protocole V42 par exemple) ainsi que pour les transmissions par télécopie [82] ‘Une nouvelle motivation est née avec Pavénement des réseaux : celle d'aug- menter la bande passante en diminuant le nombre de bits émis. D’autant que la compression est de plus en plus souvent couplée a des systemes de chiffrement qui ont tendance, eux, & augmenter la taille des paquets transmis. La compression de données apporte une réponse algorithmique & ces pro- blémes. On cherche une représentation alternative des données qui cst plus cfiicace en espace, souvent au détriment du temps @aceds. Le plus générale ment, cette représentation compacte met en correspondance une donnée avec son code au moyen d'un dictionnaie. Quand on parle de compression de données, on fait implicitement référence deux algorithmes ; ’algorithme de compression qui prend en entrée une chaine de caractéres B (pour donnée brute) et qui caleule une représentation C (pour 18 ‘Types d’algorithimes de compression compression décompression 010010 010010 0010110 0010110 1001001 1001001 1000111 1000111 TOLL A101. a R Fig. 2.1 Compression et décompression. dounée comprimée) plus courte que B et celui de décompression qui prend en ontrée une représentation comprimée C et qui calenle R, une donnée recons- truite & partir de C (voir fignre 2.1). Observons qu'il n'est pes spécifié que ln chaine de caractéres reconstruite R soit identique & B, la donnée brute fournie en entrée. La premiére question qui se pose lorsqu’on parle @algorithmes de compression de données est celle de décider sion veut que R, la donnée reconstruite a partir de C, soit identique la donnée brute B. Dans le vocabulaire de la compression de données, il s'agit: de savoir si on utilise un procédé de compression avec pertes ou sans perte. Lors- qu'on travaille sur des données textuelles ou numériques, il est indispensable que Ia donnée reconstruite soit identique A celle Horigine. Mais quand on traite des signaux andio ou vidéo, on pent tolérer une certaine perte entre la donnée brute et celle reconstruite, pourvu que Putilisateur ne pergoive pas la différence. néraloment, P'ntilisation d'un procédé avec pertes améliore la compression. Dans cet ouvrage, nous ne considérons que les aspects d'un signal numérique et nous nous restreindrons aux seuls algorithmes de compression sans perte. Nous renvoyons le Jectour intéressé par les algorithmes de compression avec pertes & des ouvrages spécialisés sur Ja compression come [82]. Intuitivement, la compression de données est, réalisée en diminuant la re- dondance de lentrée, ce qui a aussi pour effet: de rendre la donnée moins fiable, plus sujette anx erreurs. A contrario, le but des codes correcteurs derreurs que nous aborderons plus tard est de rendre une donnée plus fiable, au prix dune reclondance accrue. 2.2 Types d’algorithmes de compression Bien qu'il y ait un grand nombre d'algorithmes de compression et, pour cha- cun dentre eux, un grand nombre de variantes, on peut les classer en plusicurs catégories [85] : Compression de données. 19 les algorithmes statistiques, tels les codes de Huffman; ils coustruisent un dictionnaire en effectuant une analyse statistique et globale du document ; “les algorithmes dynamiques, corame cenx de Lempel ot Ziv; cowxci constrnisent dynamiquement un dictionnaire et remplacent les données ré- pétées par des liens vers une entrée di dictionnaire ; —les méthodes heuristiques, quant elles, essayent de «deviner» les éléments du bloc de données. Ces derniéres sont Jes plus récentes, 2.3 Définitions Lalgorithme de compression est le programme qui comprime la don- née brute B fournie en entrée et crée en sortie une donnée comprimée C. L'algorithane de décompression efiectue Popération inverse, souvent appelée re- construction. Dans certains cas, Valgorithme de compression et celui de décompression ulilisent le méme programme qui travaille de manidre symétrique (et dans la méme complexité en temps). Dans le cas it ces denx algorithmes n’u pas le méme programme, on parle de méthode asymetrique et Tun ou Veutre des deux algorithmes effectue un travail plus conséquent. C’est en particulier le cas pour les algorithmes utilisés pour la compression des données sur un DVD oit la compression est faite une seule fois & la création et la décompression est utilisée & chaque utilisation. Pour comparer 'efficacité des méthodes de compression, on introduit Jes quantités suivantes [82] : le rapport de compression, {| qui est normalement < 1. Une valeur de 0,6 signific que |B| a été réduit de 40%. le facteur de compression, rapport inverse du rapport de compression, est normalement > 1. Plus la compression est. grande, plus le facteur de com- pression croit. —Fexpression 100 x (1 — rapport de compression) est souvent utilisée, Une valeur de 40 signifie que |B] a été réduit de 40%. Dans la suite de ce chapitre, on présente quelques techniques de base, les codes do Hinffman et ler algorithmos de Lempel-Ziv. On terminera en présentant les limites de la compression. 2.4 Techniques de base Nous allons présenter succinctement deux techniques intuitives avant de présenter la méthode RLE (pour Run Length Encoding) 20 ‘Techniques de base 2.4.1 Méthodes naives Lorsqu’un texte comporte un grand nombre d'espaces qui ne sont pas ad- jacents, il est possible de les retirer en construisant un mot binaire pour lequel un “1” indique la présence d’un espace et un “0” tout caractére qui n'est pas un espace. Ainsi, le mot binaire associé au texte «Pour réduire la longueur» est (000010000000100100000000 et Te texte comprimé devient : 000010000000100100000000|Pourréduirelalongueur Si le nombre d’espaces est faible, le nombre de 1 dans le mot binaire sera petit face au nombre de 0 et le mot binaire pourra étre comprimé, par exemple en 0°1071010* pour quatre répétitions de 0 suivi d’un 1, de sept 0... Si on travaille sur une liste de mots triés dans Vordre lexicographique (ordre du dictionnaire), on peut utiliser la technique de compression de téte. Celle- Gi repose sur Ie principe que deux mots successifs dans notre liste partagent sotivent un méme préfixe p de longueur n. On peut done remplacer les lettres de p dans le second rot par n, longneur du préfixe commun. Exemple 2.1 Cod Coda Code Be Code}Barres 3e-Barres Coder 4r [Cod eur 4ur Codicille Sicille 2.4.2 Méthode RLE Le principe de cette technique de compression est le suivant : si une lettre 4 apparait n fois successivement dans entrée, on peut remplacer les n oceur- rences de @ par le couple na. Lo répétition 1 foin de a est appelée longueur de répétition ou Run length. Cette approche porte le nom anglais de run length encoding. La compression par RLE prend en entrée une chaine comme les chaussettes de I'archiduchesse et la transforme en Jes chau@2se@2tes de |’archiduche@2se Romarquons que dans notre exemple, la chaine de sortie est. plus longue que celle @entrée. En effet, dans Ventrée, se Lrouvent des répétitions de longueur deux qu’on cherche & comprimer avec trois caractéres! Il ne faut donc utili- ser cette technique que lorsqu’an caractére est répété an moins trois fois. En adoptant cette convention, on obtient Palgorithme de compression 2.1. Compression de données 21 Algorithme 2.1 __ répete 0; compteur— 1; RefCare entrée[comptenr] ; CarCour— RefCar; tantque (compteur 8, Palgorithme de compression écrit cce(n — 3). Lorsque Palgorithme de décompression rencontre une suite de trois ¢ consécutifs suivi de N =n —3 > 0, il sait qu'il s’agit de NV répétitions de c. Cest la convention qui est utilisée au sein de la méthode de compression MNP5 des modems [82] 2.5 Algorithmes statistiques Huffman a proposé un algorithme qui permet de construire un code préfive optimal pour une source S, comprenant 7 messages sur un alphabet. binaire fondé sur une procédure de réduction qui permet de transformer S, en une source Ar — 1 symboles S,1 pour obtenir finalement une source & deux symboles pour laquelle le code préfixe optimal est {0,1}, et sur la propriété 2.1 que nous rappelons ci-dessous. 22 Algorithmes statistiques Propriété 2-1 Sur un alphabet binaire, si C = {c1,...,¢,} est un code préfixe optimal pour une source S,, alors C! = {c,...,¢.,¢0) 1} défini par daa 1d 0; le texte restant & traiter s’écrit alors comme f.c.m avec f, le facteur trouvé dans 30 Algorithmes dynamiques Je dictionnairc, ¢ le premier caractire qui différe et m le reste du texte. Lalgorithme renvoie le couple (i, ) et ajoute l'entrée (fc) au dictionnaire Algorithme de compression L278 Algorithme 2.4, —_____ a - mote € dictionnaire|0]— indice—1 répéter lire S, le premier caractére du texte T restant & comprimer {on retire également S de T} ‘si mot.S € dictionnaire alors mot — mot. émis — faux sinon émettre (indice de mot dans le dictionnaire, $) affecte(mot.S) a l’entrée indice du dictionnaire indices— indice+1 mote émis— vrai tsi jusqu’a fin des données & comprimer si émis = faux alors émettre (indice de mot dans le dictionnaire, $) fsi Une implantation rapide de cet algorithme donne lieu & une complexité quadratique sur Ia longueur du texte A comprimer. Cependant, en utilisant des structures de données adéquates, ce temps de caleul peut devenir linéaire. Crest sur ce point précis que de nombreuses variantes de cet algorithme ont été proposées [64] Exemple 2.5 Soit la chaine aabbabnbabbbbabbbabb & comprimer, Dictionnaire | lexéme 0] null 1Ja (0,2) 2| ab (1,6) 3/6 (0,8) 4) aba (2,0) 5 | ba (3,2) 6 | bb (3,6) 7 | bba (6,0) 8 | bbb (6,4) 9 | abb (2,6) ‘Compression de données 31 Au départ, le dictionnaire ne comiporte aucune entrée. Le premier caractire ‘est um factenr. On le code en (0,2), ce qui signifie le factenr vide suivi du mot aet on Fajoute an dictionnaire en position 1. On lt ensuite ab dont la premidre lettre correspond & l’entrée 1 du dictionnaire suivi de la lettre 6, On code donc le factour ab par (1, b) et on ajoute ab en position 2 du dictionnaire. .. Algorithme de décompression La décompression est simple; il suffit de reconstruire le dictionnaire au fur et A mesure du décodage. Les numéros de facteur seront les mémes que pour le codage et les facteurs pourront étre interprétés sans probleme. Algorithme 2.5 mote < dictionnaire|0]— indice—1 répéter lire suivant (i si ind = 0 alors émettre(S) dictionnairefindice]— 5° indice — indice-+1 sinon factenr— conentdne(dictionnairefind],S) émettre(facteur) dictionnaire|indice|— facteur indice « indice} 1 fai jusqu’a fin du texte & décomprimer 5) dans le texte comprimé Une propriété remarquable de cette méthode est que Palgorithme de com- pression et cchti de décompression utilisent le méme dictionnaire sans qne celui- cing soit transmis. Il est entiérement. reconstruit au cours de la décompression. Exemple 2.6 Soit la donnée (0,)(1,6)(0,8)(2, 2)(3, a)(3, 6)(6, a) (6, 6)(2,6) & décomprimer. Elle donne lien A la suite cémissions suivante : a ab b aba ba. bb bba bbb abb 32 Limites de 1a, compression ct reconstruit le dictionnaire obtenu précédemment Dictionnaire | lextme 0 | null lle (0,4) 2) ab (1,6) a/b (0,8) 4| aba (2,a) 5 | ba (3,4) 6 | bo (3,0) 7 | ba (6a) 8 | bbb (6,6) 9 | abb (2,6) L278 en pratique En pratique, LZ78 ne travaille pas, comme ci-dessus, sur 1m dictionnaire de taille arbitraire. Celk est bornée et lorsque le dictionnaire est complétement rempli, celui-ci est effacé et la compression contimne avee un nouveau diction- naire. La. compression sera moins bonne mais cette méthode peut étre employée, méme si le dictionnaire n'est pas de taille suffisante pour contenir ensemble des facteurs du texte. LZ78 a donné lieu & un grand nombre de variantes. Deux: des plus ntilisées sont LZW proposée par 'T. Welch [94] pour les contréleurs de disque dur ainsi qne LZC qui est utilisée dans Putilitaire compress "UNIX. 2.7. Limites de la compression Tl existe des données qui ne peuvent étre comprimées. Pour nous en convaincre, il suffit de faire un peu de combinatoire sur les mots binaires. Pour tout entier n, il existe 2” mots binaires différents de longueur n mais seulement, yoo 2! = 2" —1 descriptions plus courtes (mots comprimés de longueur stric- tement inférieure A n). Pour tout n, il existe donc au moins un mot binaire de longueur n qui ne peut étre comprimé. C’est le cas des suites finies (vraiment) aléatoires [66]. En effet, intuitivernent, on ne peut trouver de régularité dans une suite aléatoire. C’est ce qu’atteste la complexité de Kolnogorov [57]. Pour terminer, nous allons voir comment construire Valgorithme de com- pression Ie plus performant du marché [26]. On suppose disposer de mille algo- rithmes de compression : Cy, C2,... Ciooo et des algorithmes de décompression correspondants 1), Y2,-.., Vi990- On peut alors construire un algorithme de compression capable de comprimer toute suite de symbole aussi bien, & 10 bits prés, que le meilleur des mille algorithmes de compression. En effet, pour comprimer la donnée B, on commence par en effectuer la compression avec chacun des 1000 algorithmes de compression que nous avons & notre disposition. On mémorise k, le numéro de Valgorithme de compression qui nons a fourni le meilleur résultat. II suffit alors de proposer comme donnée Compression de données 33 comprimée la suite CO’ composée du codage en binaire de & suivi du résultat de Yalgorithme de compression Cx appliqué & B. Le codage binaire de k nécessite 10 bits = [log9(1000)| + 1 Lalgorithme de décompression effectiue le travail inverse. I] commence par décoder k, le nombre binaire porté sur les 10 premiers bits de C" puis applique Dy, sur la donnée de C" privé de ses 10 premiers bits. On peut généraliser cette remarque & un nombre N quelconque. Dans ce cas, Palgorithme de compression qu’on construit sera aussi efficace que les N algorithmes de compression & [log,(N)| + 1 bits prés. Il fant cependant remar- quer que le temps de fonctionnement de notre algorithme correspond aux temps cumulés des NV algorithmes de compression que nous avons & notre disposition 2.8 Observations Pour une introduction aux techniques de la compression et & ses utilisations pour le chiffrement, le lecteur pourra se reporter & Pouvrage [69] ¢t pour plus de détails 8. un livre de référence comme eclui de Salomon [82] qui présente la plupart des algorithmes de compression, tant avec pertes que sans pel TROISIEME PARTIB Codes correcteurs d’erreurs CuapiTrs 3 Généralités sur la théorie des codes La théorie des codes, qui date du milieu du XX® siécle, permet de trans- mettre un message au travers d’un canal bruité, comme un réseau hertzien, un cable téléphonique ou ethernet, veire une liaison satellite. A Yorigine, il s'agit d’un résultat existentiel. En effet, le second théoréme de Shannon (énoncé dans le chapitre 1) dit qu'il existe de bons codes. Il a fallu attendre quelques années apres ce résultat avant de voir apparaitre les premiers codes. Dans cette partie, nous commencerons par énoncer quelques généralités sur la théorie des codes puis nous présenterons les codes linéaires (chapitre 4) et quelques exemples de tels codes : les codes de Hamming (chapitre 5), le code de Golay (chapitre 6) ct les codes de Reed-Muller (chapitre 7) Nous présenterons ensuite les principes des codes cycliques (chapitre 8) avant de modifier le probléme du décodage pour présenter les codes correcteurs de paquets d’erreurs qui sont trés utilisés dans le mécanisme de correction des disques compacts (chapitre 9). Dans le chapitre 10, nous introduirons les codes convolutifs sans lesquels il aurait été trés difficile de concevoir les téléphones cellulaires Nous terminerons cette partie par la présentation de quelques applications des codes pour la correction des erreurs des disques compacts, la détection erreurs de transmission dans les réseaux ethernet, la correction des signaux GSM et de certaines transmissions satellites. 3.1 Distance de Hamming et boules Rappelons tont d’abord les caractéristiques dune distance d entre 2 et y : d(x,y) > 0; d(v,y) =Vea=% A(a,y) = ays); (x,y) < a(x, 2) + dlzu) 38 Distance de Hamming et boules Soit B 7 ©, un ensemble fini de lettres appelé alphabet. On définit la distance de Hamsming d su les lettres de B par : Lf. sieey dom = {4 S2t4 pour 2,4 € B. Soit n ¢ Not BY = {x = (1,22,..-@m) 1154 < n,m, € Bh, Yensemble des mots a n lettres. On définit dy la distance de Hamming sur les mots dn lettres comme : dre, 9) = Yeas) = pour 2,4 € BP. Exercice 3.1 Montrer que la distance de Hamming est bien une distance. Corrigé Le sen! point délicat est de véritier Vinégalité triangulaire. Sans perte de généralité, on vérifie que dir(0,z) < di (0,y) + di(z,y) avec 0 le mot 0", a= 10" et y= O° L40°L! avec a+b =¢,¢+d = n—e. Alors d(0,2) =e, dy (0,4) =b+d et dy(x,y) =a+d. Onadonce =a+b du (t,y) 2 2€5" (2)on dit qu’un code CC BY corrige jusqu’a e erreurs si ¥a,y © C2 Ay > du(e,y) 2 2e+1 Fxemple 3.1 Soient A = {x,y} et B= {0.1}, 7 =3 et e = 1. On définit te code C comme : z+ 000 yr LOL Les boules centrées sur x et y sont alors = B,(x) = {000, 100, 010,001} By(y) = {101, 001, 111, 100} On pourrait également consicérer dy(z,y) 2 € +1 mais, en ce cas, on me saurait dire combien derrenrs ill y a eu. 40 Problémo du codage & longueur fixe Les deux boules ne sont pas disjointes car By(x) 0 Bi(y) — {100,001}. Si on regoit les messages 100 ou 001, on ne pent savoir si le message émis était « 6u bien y. En revanche, on peut affirmer qu'il y a eu une erreur de transmission, C est un code deétectant une erreur. On pent interpréter graphiqnement le point (ii) de la définition (fig. 3.1) : en effet, si le point (ii) est vérifié, les boules de rayon € centrées sur les mots de C sont disjointes : soient « et 2 deux mots d’un code C vérifiant le point (ji). mots du code DO) IQ Fig. 3.1 Illustration de la propriété (it). mots du code Supposons qu'un élément y € B” soit & la fois dans Be(z) et dans B.(z’). Alors, par V'inégalité triangulaire, on aurait di(w,2') < dy(x,y) + du(y, 2’) < 2e contradictoire avec V'hypoth’se Va,2' € Cyr # a! => dy(x,2!) > 2e+1 du point (ii). Exemple 3.2 Soient A= {x,y,z} et B = {0,1}, n =5 et e = 1. On définit le code C comme yr 10101 2 010 zt 11011 Les boules centrées sur x,y et z sont alors : By(z) = {01110, 11110, 00110, 01010, 01100, 01111} By(y) = {10101, 00101, 11101, 10001, 10111, 10100} By(z) = {11011, 01011, 10011, 11111, 11001, 11010} et sont deux A deux disjointes. C vérific la condition de décodage d’ordre 1. Un mot recu dans lequel s’est introduit une seule erreur ne peut provenir que d’un unique mot du code. Par exemple, si on regoit 11101 en supposant qu’il n’y ait qu’une seule erreur, ce mot regu peut étre décodé en y = 10101. C est un code corrigeant une erreur. On définit ensuite quelques notions utiles sur les codes. On appelle distance minémale @un code Cla quanti di(C) = minfdar(a,y) : 2,4 € Oye Fy} Généralités sur la théorie des codes at ct poids minimal dun code Ja quantité w(C) = min{w(2) : 2 € C,2 # 0} Exemple 3.3 Pour le code de Pexemple préeédent, on a : dx (01110, 10101) = 4 di(a, z) = dy (01110, 11011 dy(y,2) = dy (10101, 11011) La distance minimale de C'est dyj(C) = 3 et son poids minima) est w(C) du (2,9) B Ta proposition suivante due Hamming nous donne une borne sur Je nombre de mots du code. Proposition 3.3 Soit |B| =2, n.e € N et CC B” un code qui corrige jusqu’a e erreurs. Alors, ICl< sey Tie 0) Preuve D’aprés la preuve du lemme 3.1 appliquée au cas binaire, le nombre d’éléments de chaque boule |fe(¢)] = Tf» (7). On a done antant de mots 2 qui different de ¢ sur au plus e bits. Comme C corrige jusqu’a e erreurs, les boules sont deux A deux disjointes et on obtient : i (1) =|U%0 jeee Doi le résultat. 0 <|B"|=2 La notion de rayon de recorement permet de mesurer & quel point un mot recu z pent différer d'un mot du code ¢ € C. Le rayon de recouurement p(C) est défini par = e(C) = max{min{dy(z,¢) :¢ € C},z © BY Le rayon de reconvrement: est le plus petit p pour lequel les boules Bp(c) pour c€ C recouvrent Vensemble B” en entier. Soit ¢ le plus grand entier tel que les boules B,(c) pour c € C soient disjointes. Si p = f, on dit que le code ‘est parfait. En d'autres termes, on dit aussi qu’un code C C B” de distance minimale h(C') = 2e + 1 est parfait si tout mot 2 de B” est a distance < € dexactement tn mot ¢ du code. On obtient alors la condition dite d’empilement de spheres = si CC Best un code parfait corrigeant ¢ erreurs, alors pour |/3| = 9 0X ({)e-a= qui est obtenue immédiatement & partir du lemme et de la proposition avec, dans ce cas, égalité. 42 Probléme du décodage 3.3 Probléme du décodage On cherche maintenant détecter et 4 corriger des erreurs. 3.3.1 Détection On suppose avoir regu un message qui n’est pas un mot du code. Il est clair quwil y a eu une erreur au cours de la transtnission et nous avons détecté la présence dune (ou de plusieurs) erreur. Si aucune erreur n’a été détectée, on a soit regu un mot du code, soit regu un mot qui comportait. trop d’erreurs et, dans ce dernier cas, le code n’était pas adapté & la capacité du canal. 3.3.2 Correction Le concept de correction est plus subtil. Quand on corige un manuserit, on est tenté de corriger cae en car plutét qu’en val. On 2 supposé que le mot A corriger doit étre le plus proche possible d’un mot correct (ici, un mot du code). Nous illustrons ceci sur quelques exemples. Exemple 3.4 Soit C = {00,01, 10,11}. Chaque mot regu est un mot du code. Cy ne peut done servir & détecter des erreurs. Ci ne corrige pas d’erreurs non plus. Exemple 3.5 On modifie ©; en répétant trois fois chaque mot du code + Cz = (000000, 010101, 191010, 111111} Ce code s'appelle code a répétition. Supposons avoir regu 110101. Il ne s'agit pas d'un mot du code et on peut affirmer qu’an moins une erreur est apparue Ein ne changeant qu’un seul bit, on peut. former le mot du code 010101 mais on peut également obtenir d’autres mots du code en changeant plus d'un bit. On suppose donc que Ie mot du code correct est 010101 et on corrige donc 110101 en 010101. Exemple 3.6 On modifie ©), le code de Yexemple préeédent, en ajoutant un troisiéme bit & chaque mot de fagon a ce que le nombre de 1 des mots soit pair : Cs = {000, 011, 101, 110} Le bit ajouté s'appelle bit de parité. Supposons avoir regu le message 010. Comme 010 n'est. pas un mot du code, on est certain qu’il y a eu une erreur de transmission. Le message peut étre décodé en 110, 000 ou O11 en ne changeant qu’un seul bit du message. Dans les chapitres suivants, nous allons distinguer la manitre de traiter les mots regus les plus proches d’tm seul mot du code. Exercice 3-2 Quelle est la valeur minimale de n pour avoir deux boules dis jointes de rayon 2 et des mots de {0,1}"7 Généralités cur la théorie des codes 43 Corrigé On cherche un code C © B" tel que |C| = 2 et pour ay CC, Bale) 0 Bay) = 2. Par la proposition de Hamming, on obtient : sstgt hls Le plus petit entier n qui vérifie cette inégalité est 5 ct le code C = {00000, 11111} convient.

Vous aimerez peut-être aussi