Bonjour à tous,
Dans le cadre d'un projet de cours, on nous a donné l'algorithme de huffman à implémenter. Cependant, les consignes sont larges et j'ai l'impression qu'elles contiennent des contradictions... Mais enfin j'ai réussi à faire le codage et décodage en bidouillant un truc à ma sauce. Mon codage me satisfait (environ 5sec pour 16000 valeurs échantillonnées) mais mon décodage prend 1min40 ce qui m'agace ^^
J'ai passé des heures à fouiller sur le net mais je ne trouve rien de concluant.

Pour notre projet on utilise un huffman simplifié c'est à dire que la valeur qui revient le plus souvent est codée "1" puis celle d'après "01" puis "001" ect. Le tout sur 12bits, la valeur la moins fréquente étant donc "0000...000" de taille 2^12-1

Voici ma fonction actuelle de décodage :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function recover_symbs = huff_decode(bitstream,binqvalues)
 
%binqvalues est un vecteur similaire à qvalues mais contient les "mots codes binaires" correspondants.
%remplit un vecteur avec toutes les valeurs de quantification possibles.
qvalues = -1:2/(2^12):1;
%déclaration de vecteurs vides pour préalocation mémoire.
signal_words{1,16000}={};
recover_symbs = zeros(1,16000);
 
%trouve l'ensemble des '1' dans le bitstream
result = strfind(bitstream,'1');
%le premier "mot" du signal va du début du stream jusqu'au premier '1' inclu
signal_words{1} = bitstream(1:result(1));
%les autres vont du '1' précédant exclu au '1' suivant inclu
for k = 2:size(result,2)
    signal_words{k} = bitstream(result(k-1)+1:result(k));
end;
 
%une fois tous ces mots isolés, il ne reste plus qu'à les retranscrire en
%leur valeure quantifiée correspondante
for i = 1:size(result,2)
    for j = 1:2^12
        if size(signal_words{i},2) == size(binqvalues{j},2)
        recover_symbs(i) = qvalues(j);
        end
    end
end
end
Il y a donc 2 problèmes : le mot "00...000" correspondant à la valeur la moins fréquente n'est pas géré...
La durée (1min40 pour décoder 16000 valeurs quantifiées).

Pour nous aider la "piste" suivante nous est donnée :
Decoding:
- Parse the received binary stream bincode and check each time when a new bit is read if
a codeword is formed. If yes, place the corresponding symbol in the output vector
Sachant que je ne connais pour l'instant rien ou presque à matlab... ça ne m'a pas beaucoup aidé ! C'est pourquoi je me tourne vers vous :) En espérant que vous pourrez me mettre sur la voie.

P.S. la source du codage :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
function [binqvalues, trans_bits_source] = huff_code2(symbs_quant)
 
%definit des vecteurs vides et un vecteur avec toutes les valeurs
%quantifiées.
freq = zeros(1,2^12);
dico{1,4096} = {};
binqvalues{1,4096} = {};
dico2{1,size(symbs_quant,2)} = {};
qval = -1:2/2^12:1;
 
%replit le vecteur freq par le nombre d'occurence de chaque valeur dans le
%signal.
for i = 1:2^12
    ind = find(symbs_quant==qval(i));
    freq(i) = size(ind,2);
end;
%ajuste ce dernier afin de ne pas avoir deux valeurs identiques.
for i = 2:2^12
    for j = 1:(i-1)
        if freq(i) == freq(j)
            freq(i) = freq(i)+0.0001;
        end;
    end;
end;
 
%trie de la plus fréquente à la moins fréquente.
freqsorted = sort(freq,'descend');
 
%crée un tableau avec les "mots binaires" (1,01,001,0001,...)
for k = 1:2^12-1
     dico{k} = sprintf('%d',[zeros(1,k-1),1]);
end
dico{2^12} = sprintf('%d',[zeros(1,2^12-1)]);
 
%crée un tableau qui reprend dans le même ordre chaque valeur de
%quantification mais en "mot binaire" cette fois.
for i = 1:2^12
    ind = find(freqsorted == freq(i));
    binqvalues{i} = dico{ind};
end
 
%parcourt le signal et remplit un tableau avec les "mots binaires"
%correspondants au valeurs prises par celui-ci
for i = 1:size(symbs_quant,2)
    ind = find(qval==symbs_quant(i));
    dico2(i) = binqvalues(ind);
end
 
%transforme ce tableau de "mots" en un seul (stream)
trans_bits_source = cell2mat(dico2);
end