Sunday, December 11, 2016

Huffman coding in Matlab

The following code of huffman produces a variable length code for every symbol ever encountered in the input based on its probability of occurrence since the beginning. It constructs a dictionary and uses function huffmanenco and huffmandeco.

%Author Name:Falak Shah
%Target: To huffman encode and decode user entered string
%--------------------------------------------------------------------------
string=input('enter the string in inverted commas');         %input string
symbol=[];                                %initialise variables
count=[];
j=1;
%------------------------------------------loop to separate symbols and how many times they occur
for i=1:length(string)                  
  flag=0;  
  flag=ismember(symbol,string(i));      %symbols
      if sum(flag)==0
      symbol(j) = string(i);
      k=ismember(string,string(i));
      c=sum(k);                         %no of times it occurs
      count(j) = c;
      j=j+1;
      end
end  
ent=0;
total=sum(count);                         %total no of symbols
prob=[];                                        
%-----------------------------------------for loop to find probability and
%entropy
for i=1:1:size((count)');                   % This loop finds the probabilities and entropy
prob(i)=count(i)/total;                     % using formula entropy=sum over all symbols(p(i)/log(p(i))
ent=ent-prob(i)*log2(prob(i));          
end
var=0;
%-----------------------------------------function to create dictionary
[dict avglen]=huffmandict(symbol,prob);  
% print the dictionary.
         temp = dict;
         for i = 1:length(temp)
         temp{i,2} = num2str(temp{i,2});
         var=var+(length(dict{i,2})-avglen)^2;  %variance calculation
         end
         temp
%-----------------------------------------encoder  and decoder functions          
sig_encoded=huffmanenco(string,dict)
deco=huffmandeco(sig_encoded,dict);
equal = isequal(string,deco)
%-----------------------------------------decoded string and output
%variables
str ='';
for i=1:length(deco)  
str= strcat(str,deco(i));
end
str
ent
avglen
var

MATLAB PROMPT:

>> huffman
enter the string in inverted commas'hello how are you my darling?'

temp =

    [104]    '0  1  1  1'  
    [101]    '0  1  1  0'  
    [108]    '0  0  0  0'  
    [111]    '1  0  1'    
    [ 32]    '1  1'        
    [119]    '0  1  0  0  1'
    [ 97]    '1  0  0  1'  
    [114]    '1  0  0  0'  
    [121]    '0  0  0  1'  
    [117]    '0  1  0  0  0'
    [109]    '0  1  0  1  1'
    [100]    '0  1  0  1  0'
    [105]    '0  0  1  0  1'
    [110]    '0  0  1  0  0'
    [103]    '0  0  1  1  1'
    [ 63]    '0  0  1  1  0'
sig_encoded =
  Columns 1 through 14
     0     1     1     1     0     1     1     0     0     0     0     0     0     0
  Columns 15 through 28
     0     0     1     0     1     1     1     0     1     1     1     1     0     1
  Columns 29 through 42
     0     1     0     0     1     1     1     1     0     0     1     1     0     0
  Columns 43 through 56
     0     0     1     1     0     1     1     0     0     0     1     1     0     1
  Columns 57 through 70
     0     1     0     0     0     1     1     0     1     0     1     1     0     0
  Columns 71 through 84
     0     1     1     1     0     1     0     1     0     1     0     0     1     1
  Columns 85 through 98
     0     0     0     0     0     0     0     0     0     1     0     1     0     0
  Columns 99 through 111
     1     0     0     0     0     1     1     1     0     0     1     1     0
equal =
     1
str =
hellohowareyoumydarling?
ent =
    3.7849
avglen =
    3.8276
var =
   15.1998

No comments:

Post a Comment