• Aucun article dans le panier.

Théorie des chiffrements

Généralités

La compression est une opération qui consiste à  réduire la taille occupée par les données numériques, audio ou audio-visuelles. Son principe général consiste à  éliminer les informations redondantes et non significatives des données. La problématique de la compression résulte de la taille limitée de la bande passante du réseau Internet qui n’était pas conçu à  la base pour recevoir un flot incessant d’image, de données audio visuels et de communications téléphoniques. Les critères d’évolution des méthodes de compression sont:

  • La qualité de la reconstitution de la donnée source
  • Le taux de compression.
  • La rapidité du codeur/décodeur (codec).

Les problèmes liés à  la compression

Le contrôle de débit

183
A débit constant, il peut y avoir un risque de débordement si une crise de fluidité intervient dans le réseau.
A débit variable, il peut y avoir un risque de conflit entre le codeur et le décodeur.

Les pertes dans le réseau

La perte de certaines données comme les en-têtes peuvent avoir des conséquences grammatiques sur le comportement du décodeur.

Run Lenght Encoding : RLE

C’est le plus simple des algorithmes de compression, il consiste à  quantifier un seuil S0 fixé.

Exemple

Soit le texte source (P) suivant: [AAAAALBBCCCCDE] taille de (p)=14

  1. Fixons le seuil S0=3, on aura compress_P=[A(5)LBBC(4)DE]
    taille[compress_P] = 9.
    Taux de compression = [taille(P)-taille(compress_p)]/taille(P)
    Taux de compression = (14-9)/14 = 35%
  2. Fixons Seuil: S0=2
    On aura compress_P = [A(5)LB(2)C(4)DE].
    Taille[compress_P] = 9
    Taux de compression = 35%

Exercice:

Décompressez [C(p)], Si C(P)=[00010(00101)01011(0011)10010(00100)10101(00011)11010(00100)]

Solution:

P = [B(5)K(3)R(4)U(3)Z(4)]
P = [BBBBKKKKKKKRRRUUUZZZZ]
Taux de compression = (23-10)/23 = 13/23 = 56,5%

Compression de HUFFMAN

C’est un algorithme de codage utilisé pour la compression des données (caractères, mots) son principe:

  • Connaitre la taille totale du volume des données
  • Affecter des codes inversement proportionnels à  la fréquence des caractères contenus dans les données (haute fréquence implique codage souple)

Exemple

Texte source:
T : [aaakea befafm afakfk kfkede mdakfm]
taille(T) = 30
Fréquence:
a = 8/30 = 27%
k = 6/30 = 20%
e = 4/30 = 13%
b = 1/30 = 3,3%
f = 6/30 = 20%
m = 3/30 = 10%
d = 2/30 = 6,66%
On classe par fréquence croissante:

184

Compression de HUFFMAN pour les caractères

Soit le texte à  compresser: T = [COMMENT_ÇA_MARCHE]
On ava supposer que les caractères de T sont données en ACII, méthode de HUFFMAN:

  1. On classe les caractères par fréquence décroissante
  2. On divise la liste ainsi obtenue en 2 sous groupes S1 et S2 dont la somme des fréquences internes respectives:
185

Application:

CaractèresApparitionsFréquences
c211,6%
O15,88%
M317,64%
E211,76%
N15,88%
T15,88%
_211,76%
A211,75%
R15,88%
H15,88%
Ç15,88%
  1. Construisons une partition en 2 variables:
    Le caractère à plus haute fréquence (M) n’a pas le plus petit codage, car il n’a pas été  initialisé dans le sous groupe de moindre poids.
186

M = [COMMENT_ÇA_MARCHE]
Taux de compression de M:
Chaque caractère codé en ASCII occupe 8 bits.

187
Chaque caractère du texte source a la taille suivante:

X&Taille unitaireTaille totale
X1C12
X2O44
X3M13
X4E24
X5N44
X6T44
X7_24
X8Ç44
X9A36
X10R44
X11H44


Taille (en binaire) du texte source 17×8=136bits

188

Théorème de l’entropie

189

Exemple

Soit le texte en clair « Le_codage_des_informations_utilise_du_binaire »

  1. Classer par ordre d’apparition chaque caractère du texte
  2. Déterminez l’entropie de chaque caractère.

Solution

Classons par ordre d’apparition chaque caractère du texte.

LE_CODAGSINFRMTUB
11111111111111111
111111111111
11111111
111
111
11

Taille totale (en décimal): 45
Donnons l’entropie de chaque caractère:

190

Entropie totale:

Soit (T) un texte en claire utilisant P caractères (X1, X2, X3,… XP) d’occurrence respective n1, n2, n3, … nP alors l’entropie totale du texte (nombre total de digits qu’occupera le texte après compression).

191

Taux moyen de compression

192

Application:

  1. Déterminez le taux de compression de l’exercice précédent
  2. Déterminez les codes de chacun des caractères (ressortir l’arbre pour sortir les codes)

Solution:

193

Compression et décompression d’une matrice : méthode de RLE (Run Lengle Ending)

Objectif

On souhaite décompresser une information en binaire correspondant à  une matrice 16×4 (rouge, noir, gris, blanc)

194
Le wagon chiffrant une case de la matrice est un double mot de 16 bits codé en binaire et divisé en 5 labels ou étiquettes.

195

Etiquette (A): bit (0)

Bit de fin de texte.
A=0 ; le caractère lu est dernier du texte

Etiquette (B): bit 2

Position du caractère sur la colonne de la matrice. Il faut prendre 16 valeurs de 0000 à  1111.

Etiquette (L): bits (6) et bit(7)

Indique la ligne du caractère lu, prend 4 valeurs: L1=00 (première ligne) ; L2=01 ; L4=11

Etiquette (C) : bit(8) et (9)

Indique la couleur du caractère lu, prend =4 valeurs: noir=00 ; blanc=01 ; gris=10 et rouge=11

Etiquette (R) : bits (10) à  (14)

Indique le nombre de répartition du caractère lu en allant vers la droite de la ligne considérée et recommençant à  gauche de la ligne suivante (LK+1).
Il peut prendre 32 valeurs de (00000) à  (11111).

Etiquette (E): bits (15)

Pour les caractères d’ordre 2K-1 on a E=1. Pour les caractères d’ordre 2K on a E=0 et lorsque A=0, on a toujours E=0.
Il indique le nouveau caractère.

Exercice d’application

Soit le train d’information, comprenant un tableau en couleur (4lignes*16colonnes).
NB: On lit ce tableau de bas vers le haut.

260111 11110000 0010
241010 00111100 01101010 10110000 0111
221010 00111000 00101001 01111100 0111
201001 00111000 00101000 10111100 0101
181010 10100000 10001001 01101000 0111
161010 10100000 01101001 01101000 0011
141001 01101100 01101001 00101000 0011
121000 10101100 01001011 10010000 1001
101010 11011000 01101010 10010000 0011
81001 01011000 10101000 10011100 0101
61010 10000000 10001011 01001000 0111
41010 10000000 01101001 01001000 1011
21000 10000100 01001000 00000000 0101



Remplir la matrice originale (M)

L1NNBBGGGGGNNNGGG
L2RRGGGGGNGGGNN
L3NNR
L4
2 décembre 2021
© GoSukulu SARL. Tous droits réservés.
Ouvrir le chat
Besoin d'aide?
Salut👋,
Comment puis-je vous aider?