Module 114 – Codage chiffrage

Tout le monde sait que les ordinateurs et les transmission informatiques sont basées sur un codage de l’information faites de 0 et de 1. Un code binaire. Mais quel est ce code ?

En fait il y a de nombreux codes possibles, et même plusieurs couches de codes différents imbriqués pour coder une information, pour la transmettre de façon adaptée au moyen de transmission et pour éviter, voir même corriger les erreurs.

Histoire

Nous sommes entouré de code, il suffit de regarder autour de toi, et je suis certain qu’il y a un code barre pas loin….

C’est une suite de barre de largeur différente qui code de l’information numérique.

Depuis des millénaires les humains codent de l’information.

C’est le cas des tablettes d’argile utilisées depuis au moins -3200 … Mais probablement avant…

Avant les tablettes, il y avait les calculi, des petits jetons d’argile permettant de faire de la comptabilité.

Codage d’un fichier informatique

Un fichier informatique n’est qu’un tas de bits… des 0 et des 1… comment reconnaitre le contenu ?

Voici des petits logiciel capable de voir le contenu brut d’un fichier:

• HexEd.it… afficher le contenu d’un fichier sous forme hexadécimale. App web
• HxD une application Windows.

Ou tout simplement en ligne de commande:

xxd filename | less

Exercices:

Ouvrir différents fichiers (jpg, png, wave, mp3, txt, php, .exe, html, svg, pdf etc…) et cherchez à décoder leur structures.

Est-ce des fichiers binaires ? texte ? est-ce qu’il y a une entête ? est-ce qu’il y a des métadonnées ?

Que-ce qu’un nombre magique ?

Le format de Métadonnées EXIF est utilisé par les appareils photo pour enregistrer les paramètres de l’appareil au moment de la prise de vue. (Ouverture, temps de pose, date heure, GPS… Ce qui peut jouer des tours…)

Codage en télécommunication

=> Support de cours pdf: Transmission de données_MButty

Il existe deux grandes famille de code:

• le code de source => décrit l’information => ASCII, UTF-8
• le code de voie => réduit la sensibilité au bruit, ajoute de la redondance et adapte le signal au média utilisé. (niveau électrique et/ou phases pour les 1 et 0) => AMI, Manchester, NRZ

Codage de source

• Code morse => clé codage décodage morse à imprimer
• Code Baudot entre téléscripteurs.
• Code ASCII
• Code EBCDIC utilisé par IBM pour les cartes perforées.
• ISO 8859 Latin 1
• Combinaison de touche ALT
• Code UTF-8
• Base64 et Quoted-Printable.

Coder de l’information

Ici même j’utilise du texte basé sur un alphabet, mais comment faire le lien entre un dessin et un octet binaire ?

C’est ici que l’on utilise un code. Chaque lettre correspond à un numéro qui est représenté en binaire. Ex: a = 110 0001 (0x61)

Il y a donc évidemment des caractères graphiques “imprimables” qui représentent des lettres, mais aussi des caractères de contrôle, “non imprimable” pour signaler le début et la fin de la transmission, pour émettre un son “Bell” pour la fin de ligne (LF) et retour chariot (CR).

Exercice pratique

Exercice pratique de transmission morse avec des fanions (des feuilles de papier suffisent).

Voici un document pdf à imprimer avec une clé de décodage morse et la base des code de contrôle de transmission.

Code ASCII

Le code ASCII est le plus connu pour coder du texte. Chaque caractère tient sur 7 bits. Ce qui permet d’utiliser le dernier bit disponible d’un octet comme bit de parité pour détecter les erreurs de transmission. (voir plus loin pour plus d’info)

Le code ASCII a l’inconvénient de ne pas supporter les caractères accentués !

De nos jours nous utilisons avantageusement le code UTF-8 pour coder l’information textuelle. Son grand avantage est d’être compatible avec l’ASCII. La base est la même puis, le dernier bit de l’octet sert à indiquer si le caractère est codé sur un octet supplémentaire. On peut ainsi chainer de nombreux octets et créer un très grand nombres de glyphes et symboles. Par ex des hiéroglypes.

Analogie biologique

• ADN n’est pas codée en binaire 0 et 1, mais avec les bases ACGT adénine (A), cytosine (C), guanine (G) ou thymine (T) (et U uracile qui remplace le T pour l’ARN)
• L’équivalent de l’octet 8 bits est le codon, soit une séquence de 3 bases (nucléotides).
• avec 6 bits on a 64 possibilités, avec un codon de 3 bases on a 64 possibilités.
• Chaque codon est traduit en acide aminés protéinogènes. (voir tableau) Ex: GAG = acide glutamique
• Il existe 22 acides aminés protéinogènes sur les 64 possibilités. On a donc des synonymes. On peut écrire de plusieurs manières la génération d’un même acide aminé. Est-ce l’ouverture à la possibilité d’un code de canal (modulation) ?

Voici une explication destiné aux informaticiens qui explique la création du vaccin à ARN message contre le SarsCov.

• ancien lien qui ne répond plus…

• L’ADN, c’est le disque dure
• L’ARN c’est la mémoire vive
• L’ARN messager c’est des “trames”, “paquets” qui sont envoyés

• Le code du virus SarsCov-2 et les explications de la structure… (pdf)

Pour en savoir plus, voici aussi la biologie de synthèse qui permet de créer des organismes à partir d’un code source d’ordinateur et d’une imprimante à ADN…

Codage de voie

L’information à transmettre est codée en binaire à l’aide d’un code. Le code PCM suffit à être enregistré sur un CD.

Mais dans le monde des télécommunications, on va utiliser des codes de voie (aussi appelé code de canal).

C’est une manière de coder les 1 et les 0 sur un canal de communication. C’est une manière de s’adapter au milieu pour éviter une mauvaise communication.

La transmission simple en “bande de base” des 1 et de 0 comme on le montre dans la vulgarisation ne fonctionne pas très bien. Donc voici des code de voie utilisés:

• Code Manchester → détecte les flancs montants (0) et descendants (1). Conserve une synchronisation d’horloge.
• Code NRZ → un niveau haut et bas très loin. ex: +12V et -12V
• Code AMI → 3 niveaux de tensions possibles. Le 0 est à 0V le 1 est à une tension haute mais le 1 suivant à la même tension mais inversée (ex: +3V et -3V). On évite ainsi qu’une composante continue du signal ne décale les valeurs et brouille le 0.

Redondance

Voici des phrases:

• Les oiseaux chantent dans les arbres.
• Non ! Je ne peux pas…

Dans la première phrase, on constate que le pluriel est indiqué avant le mot et à la fin du mot par la marque du nombre. La même information se trouve donc deux fois.

Dans la seconde phrase, la négation est signalée plusieurs fois par des mots différents.

Dans la langue courante, il n’est pas rare de trouver de la redondance d’information. Cette répétition de la même information permet de confirmer le sens de la phrase. Si un mot est perdu à cause d’une perturbation, le sens général de la phrase reste.

Compression de données

La fréquence d’apparition des lettres dans une phrase ne sont de loin pas identiques. En français on trouvera beaucoup plus souvent la lettre “e” que la lettre “k”.

George Kingsley Zipf a entrepris le livre James Joyce, Ulysse, et d’en compter les mots distincts, puis de les présenter par ordre décroissant du nombre d’occurrences.

La légende dit que Zipf a obtenu un résultat du type:

• le mot le plus courant revenait 8 000 fois
• le dixième mot 800 fois
• le centième, 80 fois
• et le millième, 8 fois

C’est devenu la Loi de Zipf.

Compression non destructive de données

En s’inspirant de la loi de Zipf, l’idée principale de la compression (non destructive) de données, c’est d’attribuer un code court aux lettres fréquentes.

Le morse applique clairement cette idée en utilisant le point: “.” comme code pour le “e”.

C’est ainsi qu’est né le format ZIP de compression sans perte (et archivage) de fichiers.

Le format ZIP se base sur l’algorithme du codage de Huffman.

Cet algorithme est un code à longueur variable. Au lieu d’avoir toujours le même nombre de bit par caractère. (ex: 8 bits par caractère) Le codage de Huffman va établir un “dictionnaire” de codes de longueur variable. La taille du code binaire dépend de la fréquence d’apparition du caractère dans le contenu.

Par exemple un “e” – lettre la plus fréquente en français – va être codée avec un code cours. Par exemple: “1” et la lettre K plus rare sera par exemple codée avec un code plus long, par ex: 1001

Pour déterminer le code binaire et sa longueur on va utiliser une structure de donnée en arbre, et suivre un petit algorithme de construction:

• Chaque lettre d’une suite de caractère est associée à son nombre d’occurrence. ex: a:10 fois, c:4, f:8
• Ceci nous donnes les feuilles d’un arbre (vert)
• L’arbre est construit des feuilles à la racine par association de “feuille” (ou branche) de valeurs “similaires”.
  • On choisi les deux valeurs les plus petites. (ex: b:7 et d:5 ou encore c:4 et e:4)
  • On relie les deux feuilles par un embranchement libellé avec la sommes de deux feuilles. (ex: b:7 + d:5 = :12) et (c:4 + e:4 = 8)
  • On recommence l’opération jusqu’à obtenir une racine unique.
• On associe ensuite un code binaire à chaque embranchement de l’arbre.
• Comme c’est du binaire, il suffit d’associer 0 à un embranchement et 1 à l’autre.
• La lecture du code associé à chaque caractère se lit en suivant les embranchement de l’arbre de la racine à la feuille dont on cherche le code.
• ex: racines- 0-1-0 nous mène à la feuille b : 7. Donc b → 010

Pour l’arbre présenté dans la vidéo ci-dessus on obtient un “dictionnaire” de code suivant:

• a : 00
• b : 010
• c : 100
• d : 011
• e : 101
• f : 11

Le décodage se fait tout simplement en suivant la suite des nombre binaires sur l’arbre associé. A chaque fois qu’on arrive sur une feuille, on note la lettre trouvée et on recommence depuis la racine.

C’est quasi “magique”, car malgré la longueur variable du code on retrouve chaque lettre sans savoir où sont les séparations. (il faut quand même connaitre l’arbre !!)

C’est typiquement le genre d’algorithmes de compressions sans perte utilisés pour les formats Zip, RAR, gzip, 7-Zip, xz…

En savoir plus sur la compression de données sans perte.

Compression destructive

Les données brut d’un enregistrement continent parfois plus d’information que nécessaire pour une bonne expérience de visualisation.

Ce genre d’algorithme est basé sur les perceptions humaines. Par exemple, l’oeil humain est peu sensible aux forts contrastes dans une image.

Ainsi il est possible d’atténuer ces contrastes pour diminuer la taille des données.

Algorithme JPEG

C’est ce que pratique par exemple l’algorithme du jpeg. En pratique, un fort contraste, c’est une haute fréquence dans la représentation spectrale des données. Donc cet algorithme va transformer les données en représentation spectrale, supprimer les hautes fréquences et revenir en représentation spatiale.

Voici une bonne description de cet algorithme du JPG…

Les étapes de l’algorithme jpeg:

• Conversion de l’image dans la représentation Y’CbCr (luminance + Chrominance (y -bleu et y -rouge) )
• Sous-échantillonnage de la chrominance
• Transformée en cosinus discrète (une sorte de transformée de Fourrier discrète)
• Quantification
• Parcours en zigzag du quadrillage de données
• Algorithme de Huffman pour compresser sans perte le tout

Algorithme PNG

L’algorithme de compression jpeg fonctionne bien pour les photos. Il “adoucis” les photos en lissant les contrastes.

Par contre si l’image contient de forts contrastes, comme pour une image d’un texte, ou pour un logo. L’algorithme jpeg va créer des bavures.

Ainsi on va utiliser un autre algorithme. Une des caractéristiques d’un texte ou d’un logo c’est de comporter très peu de couleur. Donc pourquoi utiliser 32 bits d’information par pixel quand seulement 1 bits suffit à coder noir ou blanc ?

L’algorithme du format PNG va donc réduire l’espace des couleurs à disposition pour compresser l’image.

Principe de codage des couleurs d’un pixel

Pour bien comprendre, revenons sur le principe de codage d’une image.

Une image c’est une grille de pixels, on parle d’image “matricielle”. Chaque pixel représente une couleur. Cette couleur doit être codée en bit d’information.

Généralement on code les couleurs en représentation RVB, soit un mélange de proportion de Rouge, Vert et Bleu.

Chaque pixel est codé sur 32 bits. (4 octets) Mais très souvent seuls 24 des 32 bits sont utilisés, comme c’est le cas pour le format bitmap .BMP

Les 24 bits (3 octets) sont décomposée en 3 fois 8 bits:

• 8 bits de rouge
• 8 bits de vert
• 8 bits de bleu

Soit 2⁸ = 256 niveaux par couleur primaire.
Ce qui nous donne 2²⁴ ou 16 777 216 couleurs différentes possible pour chaque pixel.

La représentation des couleurs se fait souvent en hexadécimal (c’est trop long et source d’erreur d’utiliser la notation binaire). Donc chaque couleur primaire est exprimée par 2 caractères.

FF FF FF → 100% Rouge + 100% Vert + 100% Bleu = Blanc
00 00 00 → 0% Rouge + 0% vert + 0% Bleu = Noir
FF FF 00 → 100% Rouge + 100% Vert + 0% Bleu = jaune
66 DD AA → 20.69% Rouge + 44.83% Vert + 34.48% Bleu = Medium Aquamarine

Dans les caractéristiques des images, on parle de profondeur pour indiquer le nombre de bits sur lesquels une couleur est codées.

En PNG, il existe donc plusieurs profils de représentation des couleurs:

• 1 bit donc deux couleurs
• 2 bits en 4 couleurs basiques
• 4 bits permettant de choisir parmi une palette de maximum 16 couleurs contenues dans le fichier
• 8 bits en niveaux de gris (256 niveaux)
• 8 bits permettant de choisir parmi une palette de maximum 256 couleurs contenues dans le fichier (équivalent au format GIF)
• 24 bits, soit 2²⁴ ou 16 777 216 couleurs (couleurs vraies, 256 couleurs par canal RVB).
• 32 bits, soit 2³² ou 4 294 967 296 couleurs.
• 48 bits, soit 2⁴⁸ ou 281 474 976 710 656 couleurs.

Les trois derniers ne sont plus tellement de la compression de données, mais juste une codage d’image.

Si seuls 3 octets sur les 4 octets sont utilisés, pour coder une image, il est assez aisé de réduire la taille d’un fichier BMP. En revanche, le format PNG utiliser le dernier octet pour coder une notion de transparence.

Mais.. on peut aussi faire d’autres choses avec un octet inutilisé par pixel…

Compression de données Audio

Dans le domaine de l’audio, les principes sont similaires à ceux du domaines de l’image.

On a des fichiers WAV, AIFF, qui sont non compressé. (du PCM brut voir plus bas pour le détail de la conversion de son analogique en numérique).

Nous avons aussi le format Flac qui est compressé mais de façon non destructive. Le FLAC obtient des taux de compression des données PCM de 30 à 70 %. C’est mieux que de juste appliquer une compression ZIP qui atteint 20 à 40 %.

En effet, le ZIP est un algorithme de compression sans perte généraliste. Il ne tient pas compte de la nature des données compressée. Le FLAC utilise une prédiction linéaire sur des blocs de 100ms, codage par plages qui est efficace pour coder les silences et les blancs. (par ex, en indiquant 1 seule fois le blanc vu qu’ils sont tous identiques et en y faisant juste référence quand on en trouve un.)

Puis nous avons la famille des algorithmes de compression destructive. Le format le plus connus est le MP3.

Les autres formats courants sont le AAC et le Vorbis.

On est dans la même idée qu’avec le jpeg, il s’agit de se baser sur les perceptions acoustiques des humains. Les fréquences qui nous sont moins audibles sont supprimées.

Exercice de récapitulation:

Avec quel algorithme de compression de données faut-il compression un logo en 4 couleurs ?

Avec quel algorithme de compression faut-il compresser une photo ?

A quelle couleur correspond le code binaire: 111110111101000010010111 ?

Compression des fichiers déjà compressés

Est-ce que créer une archive ZIP d’un dossier de photo jpeg va diminuer la taille mémoire de l’archive ?

Une fois qu’une image est déjà compressée, on ne peut théoriquement plus la compresser encore une fois. On va même avoir l’effet inverse, avec toutes les entêtes et dictionnaire créé pour compresser le fichier.

Si c’est une compression destructive, on va même détruire petit à petit un peu plus les données, un peu comme on le faisait en analogique.

C’est l’effet photocopieuse.

Voici un exemple d’une vidéo envoyée sur youtube (donc compressée) puis téléchargée, et remise sur youtube donc compressée à nouveau, et on recommence la boucle un bon millier de fois….

Cette expérience nous montre que youtube recompresse les vidéos à chaque fois.

Correction d’erreur

• Bit de parité → détection d’erreur (somme de contrôle)
  • 7 bits de données + 1 bit de parité.
  • Le nb de bits à 1 de l’octet doit être pair pour que la transmission soi correcte. Le bit de parité est à 0 ou 1 pour ajuster le résultat
  • ex: 11010001 ou 01101001
• Empreinte (Hash) MD5 ou SHA-1
• CRC → Code correcteur d’erreur

Conversion analogique numérique

Le monde à notre échelle est analogique. Pour avoir un signal numérique il est donc nécessaire de le convertir en numérique.

Voici en vidéo les explications de la différence entre l’analogique et le numérique.

Pour convertir un signal analogique en signal numérique, il y a deux étapes importantes:

• l’échantillonnage
• la quantification

Echantillonnage

Pour le convertir en numérique on va échantillonner le signal analogique. C’est à dire qu’on va régulièrement prendre une valeur du signal.

Plus on prend une valeur souvent, plus on va être précisé. Mais grâce au théorème de shannon et nyquist on peut limiter la fréquence d’échantillonnage.

Le théorème de l’échantillonnage nous dit que la fréquence d’échantillonnage doit être d’au moins 2 fois la fréquence maximale du signal.

La bande passante, c’est la largeur de fréquence (de la plus petite à la plus grande) qu’on observe dans le spectre d’un signal.

Dans une téléphone, on fait passer des fréquences de 300 à 3400Hz. Ainsi on a une bande passante de 3100Hz, et une fréquence maximale de 3400Hz.

Donc la fréquence minimale d’échantillonnage pour pouvoir reconstituer une signal sera de 2*3400 = 6800 Hz.

Pour le téléphone, la norme minimale a été placée à 8kHz.

Petit calcul, donc tous les combien de temps on va prélever un échantillon si l’on utilise une fréquence de 8kHz ?

T = 1/f

A propos de Spectre d’un signal… voici le logo de l’entreprise Cisco très active dans les réseau de télécommunication.

Hormis le fait que cette entreprise est basée à San-FranCISCO… est-ce que ça vous rappelle quelques chose ?

Quantification

Avec l’échantillonnage on va prélever une information un certain nombre de fois par seconde.

Puis il faut enregistrer sa hauteur, sa valeur. On va donc quantifier la hauteur d’un signal avec un niveau.

Pour ce faire, il nous faut définir une échelle de hauteur. Comme nous travaillons en binaire, la précision de cette échelle va dépendre du nombre de bits utilisés.

Sur le schéma ci-dessus, nous utilisons 3bits pour expliquer le principe.

Combien de niveaux différents peut-on avoir avec une valeur définie sur 8bits ?

Si l’on a une fréquence d’échantillonnage de 8kHz et un niveau de quantification exprimé sur 8 bits, quel est le débit binaire dont nous avons besoin pour transmettre ce signal en numérique ?

Modulation PCM

Une fois que l’on a échantillonné et quantifié le signal, il faut coder l’information. La méthode la plus simple est ce qu’on appelle la PCM, Pulse Code Modulation.

Cette méthode nom compressée, est le format de donnée que l’on retrouve majoritairement dans les fichiers audio de type WAV, AIFF ou BWF.
Attention tout de même, ce genre de fichier sont des conteneurs, ils peuvent contenir aussi d’autres formats, donc il faut lire l’entête du fichier pour savoir quel code est véritablement utilisé.

Le codage PCM est aussi celui qui est utilisé sur les CD audio, avec une fréquence de 44,1kHz et une quantification sur 16 bits.

Ecouter le silence

Expérience de trouver le silence dans le flux RTP d’une conversation VOIP…

Téléchargez un fichier de capture wireshark… conversation G711.pcap

Le silence est représenté sous la forme de l’hexadécimal: D5

Codec

Codage – Decodage

Voici les caractéristiques principales des codes que l’on utilise en téléphonie.

G.711
→ échantillonnage sur 8kHz
→ bande passante 300 – 3400 Hz
→ loi A ou loi mu pour la quantification logarithmique. (13 ou 14 bits ramené à 8)
→ 64 ou 56 kbit/s
→ code PCM (Modulation Impulsion Codées)
→ code Manchester possible pour PCM → on conserve l’horloge. Le flan haut à bas = 1 et bas à haut = 0 (ou l’inverse)
(en ISDN on utilise un code ternaire, à 3 tensions, il y a violation de l’alternance pour indique le début de la trame)

G.722
→ qualité haute définition par rapport à G.711 → On a augmenté la bande passante
→ bande passante 50 – 7000 Hz
→ 16kHz d’échantillonnage
→ ADaptivePCM → MICDA
→ 64 kbits/s

G.722.2
→ 16kHz d’échantillonnage
→ bande passante 50 – 7000 Hz
→ débit réseaux 6,6 à 23,85 bit/s

G.726
→ ADPCM à 40, 32, 24 ou 16 kbit/s.

G.729
→ codage de parole à 8kbit/s par prédiction linéaire avec excitation par séquences codées à structure algébrique conjuguée.
→ débit réseau: 32.8 kbits/s

Pour étudier les réseaux de téléphones de Nouvelle Génération, ainsi qu’écouter les différences de qualité des codec.

Modulation

Le plus simple pour transmettre un signal, c’est de l’envoyer tel quel sur le média. C’est ce qu’on appelle la bande de base.

Mais très souvent ça ne fonctionne pas. Par exemple quand le signal est trop faible pour parcourir une longue distance. (par ex: les 3km entre chez soi et le central téléphonique)

C’est ici que l’on a recours à des modulations. On va moduler une porteuse capable de faire le chemin avec notre petit signal.

C’est exactement ce que fait un Modem (modulation-demodulation) VDSL.

• FSK – Modulation par déplacement de fréquence
• PSK – Modulation par changement de phase
• QAM – Modulation d’amplitude en quadrature

Chiffrement