Master I : Systèmes de Télécomm. /Réseaux de Télécomm.
Codage et Compression
TP 1 : Entropie, Codage Huffman
But :
Observer le déroulement de l’algorithme du codage Huffman et son implémentation sur
matlab.
1) Entropie :
Ecrire une fonction matlab de l’entropie dont le nom est :
function H = entropy(p)
Ajouter la condition ‘if’ N est égale à 1 ou non.
N=sum(sum(p)); % si p est le vecteur probabilités
Snz=nonzeros(p);
H=-sum(Snz.*log2(Snz));
2) Création du Dictionnaire Huffman : Le dictionnaire permet d’associer les symboles aux
mots de code de Huffman (Arbre du code).
1) Exécuter ce programme. Commenter les différentes sorties.
symbols = [1:5];
p = [.3 .3 .2 .1 .1];
[dict,avglen] = huffmandict(symbols,p)
samplecode = dict{:,:}
2) Donner l’entropie et le dictionnaire de cette source et vérifier dict{1, :}.
symbols = [1 2 3];
p = [0.1 0.1 0.8];
3) Codeur Huffman :
1) Exécuter ce programme. Comparer ‘hcod’ au signal source. Commenter et
interpréter.
symbols = [1:6];
p = [.5 .125 .125 .125 .0625 .0625];
sig = randsrc(100,1,[symbols; p]);.
hcod = huffmanenco(sig,dict);
2) Calculer la longueur moyenne et vérifier l’existence du code.
3) Calculer l’entropie de la source. Est-il optimal.
4) Donner l’arbre du code
4) Décodeur Huffman :
1) Exécuter ce programme. Commenter et interpréter.
sig = repmat([3 3 1 3 3 3 3 3 2 3],1,10);
symbols = [1 2 3];
p = [0.1 0.1 0.8];
dict = huffmandict(symbols,p);
hdec = huffmandeco(hcod,dict);
isequal(sig,hdec)
2) Calculer la longueur moyenne. Est-il optimal.
3) Donner l’arbre du code
Mr. A. Seddiki & Mr. Aek. Ghaz
Master I : Systèmes de Télécomm. /Réseaux de Télécomm. Codage et Compression
TP 2 : Codage Shannon-Fano
But :
-Observer le déroulement de l’algorithme du codage de Shannon-Fano et son
implémentation sur matlab.
-Comparaison avec le codage de Huffman point de vue optimalité.
-Application des deux algorithmes à l’image.
Algorithme de Shannon-Fano :
Cet algorithme ainsi que celui de Huffman transforme un signal aléatoire constitué
d’évenements représentés par des code de longueur n(bits), n étant fixe, en un signal
d’évenements codés par un VLC (variable length coding) : un code à longueur variable. La
compression réside dans la petitesse des codes de sortie par rapport aux codes d’entrées : on
code les évenements les plus fréquents avec un code très court et les évenements les moins
fréquents avec un code plus long.
VLC préfixé :
Le code de sortie est composé de nombres binaires de longeur variable mis bout à bout sans
aucun délimiteur. Il n’y a rien pour indiquer qu’on passe d’un code à l’autre. Comment
extraire les codes sans connaître leur longueur ?
Voici un signal en exemple: 00010100101110001010010111. Voici une liste des codes qui
ont été employés dans ce signal : A=01 B=010 C=101 D=0 (la convention est de s’arrêter de
décoder quand on trouve un code inconnu). Quel est le message contenu dans la chaine
précédente ?
Il est impossible de proposer une solution unique, parceque le codage est mal fait : les codes
sont ambigus. Quand on voit 01, on ne sait pas si c’est A seulement ou le début de B ou un D
suivi d’un C.
La bonne méthode est de construire des codes non ambigus, qu’on appelle ‘préfixés’ : on
fait en sorte que chaque code ne puisse pas être le début d’un autre code. Dans l’exemple
précédent, A est le début de B, D est le début de A et B, et donc celui-là n’est pas préfixé.
Voici un code préfixé correct : A=101, L=001, S=000, T=11, U=01. Pour le message
précédent, il faut commencer par le premier bit, 0 c’est soit un S soit un L, ensuite un 0 il reste
S ou L puis un 0, c’est donc un S. ensuite on trouve un 1 : A ou T, puis un 0 donc c’est un A,
il faut consommer le 1 suivant ; et ainsi de suite.
Arbre binaire de code préfixés :
Les deux algorithmes (Shannon-Fano et Huffman) construisent chacun un codage optimal
(H<= R<=H+1) pour la compression mais de manière différente : on aboutit à des codes
différents, mais au même taux de compression, très proche de ce qu’indique le théorème de
l’entropie pour un signal aléatoire.
Pour constriure ce code, les deux algorithmes utilisent un arbre binaire qui fabrique
automatiquement un code préfixé. C’est tout simple : un arbre binaire est un arbre dont les
nœuds sont soit réduit à des feuilles (pas de sous-branches), soit comptent exactement deux
branches. les branches sont marquées 0 et 1.
Pour décoder un signal, il suffit de lire évenement par évenement (bit par bit) et de choisir la
branche qui correspond au bit lu. Quand on arrive à une feuille (pas de branches), on affiche
cette feuille et on retourne à la racine. Evidement, il faut que l’arbre binaire soit le même entre
le codeur et le décodeur.
Mr. A. Seddiki & Mr. Aek. Ghaz
Master I : Systèmes de Télécomm. /Réseaux de Télécomm. Codage et Compression
Exemple :
1) Codeur Shannon-Fanon :
La fonction suivante permet de simuler le codage de Shannon-Fano en fonction des
probabilités d’une source aléatoire.
a) Exécuter cette fonction et vérifier le résultat avec la théorie pour les deux sources :
p = [0.25, 0.25, 0.125, 0.125, 0.0625, 0.0625, 0.0625, 0.0625];
[codex,T]=sfencoder(p); %fonction du codeur Shannon-fano
b) Donner l’entropie de la source et vérifier que ce codeur est optimal.
c) Donner l’arbre du code et son efficacité.
d) Comparer avec Huffman.
2) Codage d’une séquence de texte :
En utilisant le codage de Shannon-Fano, On veut représenter le texte suivant en
séquence binaire.
INFORMATION CALCUL ET COMMUNICATION
a) Combien de bits par lettre en moyenne sont nécessaires pour coder ce texte.
b) Donner l’entropie de cette source. Le code est-il optimal.
c) Si on ne tient pas compte des probabilités d’occurrence, et qu’on veut utiliser un
codeur qui code avec le même nombre de bits pour chaque lettre. Combien de bits sont
nécessaires pour coder ce texte. Comparer avec le code Shannon-Fano.
Mr. A. Seddiki & Mr. Aek. Ghaz
Master I : Systèmes de Télécomm. /Réseaux de Télécomm. Codage et Compression
3) Codage appliquée à l’image :
a) Taper ce programme et voir la démarche entrepris pour appliquer le codage Huffman à
l’image.
clc;
clear all;
close all;
A1 = imread('8.tif');figure, imshow(A1);
s=wkeep(A1,[32 32]);imshow(s); % on prend une partie de l’image
A1=s;
[M N]=size(A1);
A = A1(:);
count = [0:1:255]; % Distinct data symbols appearing in sig
cou = imhist(A1);
p = cou / numel(A1);
[dict,avglen]=huffmandict(count',p)
comp= huffmanenco(A,dict);
compression_factor= (M*N*8)/length(comp) %computing the compression factor
%(comp ratio=1/comp_factor)
Idec = huffmandeco(comp,dict);
Idec=uint8(Idec);
decomp=reshape(Idec,M,N);
figure,imshow(decomp);
Mr. A. Seddiki & Mr. Aek. Ghaz
Master I : Systèmes de Télécomm. /Réseaux de Télécomm. Codage et Compression
TP 3 : CODAGE DE CANAL
Partie A :
L'objectif de ce TP est la mise en œuvre des codeurs de canal pour simuler leur
capacité de correction et en cerner les limites. Pour cela nous utiliserons le logiciel MATLAB
avec le 'Communication Toolbox' et l'outil de simulation intégré SIMULINK.
Nous allons étudier une des grandes familles de codeurs de canal :
- les codes blocs pour lesquels des blocs de K symboles d'information sont protégés
indépendamment les uns des autres par M symboles d'informations pour former des mots
codes de N symboles.
1) CODES BLOCS
MATLAB propose deux fonctions encode et décode permettant d'implanter des
codeurs/décodeurs de canal basés sur une matrice de contrôle ou sur un polynôme générateur,
avec en particulier les codeurs de Hamming et les codeurs BCH.
Les codes linéaires (dont celui de Hamming) sont définis par une matrice de contrôle H (en
anglais parity check matrix). Si v est un mot-code alors :
H .v t 0 (1)
Cette opération appliquée sur le mot-code reçu v' permet de calculer le correcteur (ou
syndrome) et de détecter les erreurs si :
H .v' t z 0 (2)
Pour l'opération de codage, on peut utiliser la matrice génératrice G qui est liée à la matrice de
contrôle H par la relation suivante :
G.H t 0 (3)
où G et H peuvent s'écrire sous leur forme canonique :
: :
G Ik : Ak ,r et H
A t
k ,r : Ir
(4)
: :
On obtient alors le mot-code v en fonction des caractères d'information i par la relation
suivante :
v i.G (5)
MATLAB donne la fonction gen2par qui permet de passer de G à H.
2 ) Codage de Hamming
Le codeur de Hamming permet de corriger une erreur parmi n. Le nombre de caractère
de contrôle m est lié au nombre de caractère d'information k par la relation suivante :
2m n 1 m k 1 (6)
MATLAB gère automatiquement le codeur de Hamming dans le cas où 2m = n+1. Les
fonctions proposées par MATLAB sont hammgen, htruthtb.
D’une manière générale, on associe à un message de k bits, m bits de contrôle de
parité, ce qui totalise m+k bits à transmettre. Pour un message de k=4bits (b1,b2,b3,b4),il faut
donc au moins m=3bits de parité pour distinguer m+k=7 occurrences d’erreur et 1 absence
d’erreur. Le message codé peut être représenté sous le format suivant :
Mr. A. Seddiki & Mr. Aek. Ghaz
Master I : Systèmes de Télécomm. /Réseaux de Télécomm. Codage et Compression
h1 h2 h3 b1 b2 b3 b4
Chaque bit de Hamming contrôle la parité d’un groupe de 3 bits. Le traitement de
données sous Matlab adopte la convention suivante :
h1 examine la parité de (b1,b3,b4) ; h2 examine la parité de (b1,b2,b3); h3 examine la parité
de (b2,b3,b4)
2.1) En utilisant la fonction hammgen, tracer la courbe donnant le taux d'émission en
fonction du nombre de symboles d'information pour un codeur de Hamming. Qu'en concluez-
vous ?
3) Manipulation
1) Exécuter ce programme 1 et justifier le résultat donné en C en calculant les bits de parité.
Comparer les vecteurs C1 et C2 par le fonction Corr.
1clc,
2m=3;k=4;n=k+m;%n=2^m-1-k
3M=randint(k,1,2)
4[H,G]=hammgen(m)
6C=zeros(,1); C1=zeros(n,1); C2=zeros(n,1); %% Codage et Décodage
8 C=G'*M; %-----> Codage du message M
9 C1=mod(C,2) ;
10C2=encode(M,n,k,'hamming') ;
11Rd=decode(C2,n,k,'hamming') ; %----> Decodage et récupération du M
Programme 1
2) Exécuter le programme 2 et relever la valeur du syndrome Z. Que représente ce syndrome.
Commentaires.
%% Détéction d'érreur , Syndrome
15Z=zeros(m,1); Zn=zeros(m,n);
16Z=H*C %----> Détection d'err
17Z=mod(Z,2) %---> Vecteur Syndrome
%% Simulons l'Occurence d'1 erreur sur chaque bit du message code C1 ou C2
for i= 1: length(C1) % ou C2
22 C1(i)= mod(C1(i)+1,2) ;
23 Z=mod(H*C1,2); %----> Comparer
chaque Z avec les colonnes de H
26 Zn(:,i)=Z;
27 C1(i)= mod(C1(i)+1,2);
end;
Programme 2
3) Nous souhaitons simuler l’occurrence d’une erreur sur chaque bit du message codé C1 ou
C2 (Programme 2)
Quelle opération est réalisée à la ligne 22.
Que représente le vecteur Z à chaque itération.
Quelle est la différence entre les lignes 22 et 27.
Comparer Zn et H.
Mr. A. Seddiki & Mr. Aek. Ghaz
Master I : Systèmes de Télécomm. /Réseaux de Télécomm. Codage et Compression
4) Supposons l’arrivé du code C avec une erreur évidente en b2 que nous souhaitons
intercepter. Exécuter le programme 3.
Quelle est la valeur enregistrée par test.
Compléter la syntaxe de la ligne 39. Comparer R et C_Corrected. Commentaires
%% Exemple de détection et de correction
%[h1 h2 h3 b1 b2 b3 b4]
C=[1 0 1 1 1 0 1]'; % erreur en b2
%C1(7:7)=0;
C_corrected = C;
Z=mod(H*C1,2)
for i= 1: length(C)
test=symerr(Z,H(1:m,i));
if (test == 0)
38 i
39 C_corrected(i)= mod(…….,2); %---> Completer la syntaxe
end
end
C_corrected
R = decode(C,n,k,'hamming'); %-----> Vérification de C_corrected
Programme 3
Partie B :
4) On veut simuler une chaine de transmission avec calcul du taux d’erreur.
4.1) Charger le programme du répertoire hammingcode. Executer la fonction ‘main’ en
prenant comme source d’entrée la séquence binaire issue du codage de Huffman (message :
informationetcalcul…).
Comparer la séquence décodée après correction de hamming.
4.2) Charger la fonction Hamming_BER et exécuter. Conclusion
4.3) Simulation de la chaine en utilisant le Simulink dans un canal bruité.
Réaliser les modèles suivants.
Mr. A. Seddiki & Mr. Aek. Ghaz
Master I : Systèmes de Télécomm. /Réseaux de Télécomm. Codage et Compression
1. Changer le Initial seed dans le modele ou bien executer la simulation pour different
temps de simulation. Quelle est le taux d’erreur affiché.
2. Pourquoi le taux est toujours approximativement à 0.001quand l’erreur du canal est
0.01?
3. Changer la probabilité d’erreur du canal: 0.02, 0.03…. Tracer le taux d’erreur et
Comparer les résultats de simulation avec les résultats théoriques.
Travail à faire:
Refaire le travail pour un canal Gaussien (AWGN) et Tracer le taux d’erreur en fonction du
rapport Eb/No ?
Mr. A. Seddiki & Mr. Aek. Ghaz
Master I : Systèmes de Télécomm. /Réseaux de Télécomm. Codage et Compression
TP 4 : Compression des Images (DCT, JPEG)
BUT :
Comprendre le déroulement de la compression (JPEG) et l’utilité de la DCT.
1ère étape:
On divise l'image en blocs de 8x8 pixels.
2ème étape:
On applique une Transformée en Cosinus Discrète à chacun des blocs. On obtient alors des
coefficients représentant les différentes fréquences de l'image pour un canal donné. En haut à
gauche se trouve les basses fréquences, en bas à droite les hautes fréquences.
3ème étape:
On quantifie différemment les coefficients suivant la fréquence. Dans la norme JPEG il existe
4 tables de quantification différentes suivant la compression voulue. Cette technique a pour
but de supprimer les hautes fréquences, qui sont moins visibles par l'œil humain.
4ème étape:
On classe les coefficients suivant un ordre en zig-zag.
5ème étape:
On procède au codage entropique, c'est à dire que l'on passe d'une suite de coefficients à une
suite de zéros et de uns.
Manipulation :
1) Taper les instructions suivantes et commenter.
clc;close all;
i=imread('cameraman.tif');i=double(i);
figure;imshow(i/255);
figure;mesh(double(i));colormap(jet);
%appliquer la dct à l'image %
d=dct2(i);
figure;imshow(log(abs(d)),[]);
Mr. A. Seddiki & Mr. Aek. Ghaz
Master I : Systèmes de Télécomm. /Réseaux de Télécomm. Codage et Compression
% dct sur des blocs à 8x8
d1=blkproc(i,[8 8],'dct2');
figure;imshow(d1,gray(256)); %
% on filtre avec un FPB pour garder que DC
% function z=filtpb(x)
% z=zeros(8,8);
% z(1,1)=x(1,1); % seul premier composant DC
% end
d2=blkproc(d1,[8 8],'filtpb');
d3=blkproc(d2,[8 8],'idct2'); % dct inverse
figure;imshow(d3,gray(256));
%on mesure l'energie moy
% function z=energie(x)
% xcarr=x.^2;
% z=mean(mean(xcarr %moyenne du carré de l'entree
% end
d3=blkproc(d1,[8 8],'energie');
cofACDC=mean(mean(d3))
%on mesure l'energie DC
d4=blkproc(d2,[8 8],'energie');
cofDC=mean(mean(d4))
%energie en %
Ppourcentag=cofDC*100/cofACDC
%on affiche l'energie au fur à mesure avec plus de détail
mask = [1 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0];
d5=blkproc(d1,[8 8],'P1.*x',mask');
d6=blkproc(d5,[8 8],'idct2');
figure;imshow(d6,gray(256));
d7=blkproc(d5,[8 8],'energie');
cofDC3AC=mean(mean(d7))
%qualité de l'image
Ppourcentag=cofDC3AC*100/cofACDC
2) L'étape suivante est celle de la quantification. Elle consiste à donner les valeurs
approximatives de la matrice DCT. Pour cela, on remplace chaque valeur par le quotient de la
division euclidienne de cette valeur par le pas de quantification. La matrice de quantification
Q est donnée par la relation suivante : Q(i,j) = 1 + F.(1 + i + j), où F est le facteur de
quantification.
Mr. A. Seddiki & Mr. Aek. Ghaz
Master I : Systèmes de Télécomm. /Réseaux de Télécomm. Codage et Compression
On divise notre matrice DCT par la table de quantification donnée dans la figure.
Pour comprendre l’effet de la quantification (nombre de bits, nombre de niveaux ‘N’); utiliser
les fonctions ‘quantiz’ et lloyd_max (optimal).
3) Refaire le chemin en inverse et mesurer la qualité de l’image décompressée (N,eqm, psnr).
4) Exécuter l’application VCdemo pour explorer la compression JPEG 2000 (EZW).
Mr. A. Seddiki & Mr. Aek. Ghaz
