% Huffman Coding Algorithm
%
% By: Wiwat Tharateeraparb
%     October 2000
% 
% Note: 1. Read #2.
%       2. Mess-Them-Up part is intended to vary the values
%          in P vector (to P_mod) in order to avoid two or 
%          more identical prob. values which can corrupt 
%          or lead to wrong results.
%       3. With Mess-Them-Up algorithm makes this program ROBUST!
%       4. Program tested with
%          - {0.3,0.25,0.2,0.12,0.08,0.05}-->{00,01,11,101,1000,1001} 
%          - {1/2,1/4,1/8,1/16,1/16}      -->{0,10,110,1110,1111}
%          - {0.25,0.25,0.25,0.25}        -->{00,01,10,11}
%       5. This algorithm based on the book "Analog and Digital Comm"
%          by Hwei P. Hsu. PLEASE note that in some books(such as 
%          "Digital Comm." by Sklar) use different "sort" algorithms
% ------------------------------------------------------------------
clear;clc;
P         = []; % Probability vector
P_mod     = []; % Modified prob. vector
P_org     = []; % Original prob. vector
P_history = [];
codes     = {}; % Cell to store codewords

disp('Huffman Coding');
disp('--------------');
N = input('Enter the number of symbols:');
disp(' ');
disp('Enter the probabilities coresponding to symbols:');
disp(' ');

for i = 1:N
   p = input(['P(X',num2str(i),') = ']);
   P = [P;p];
end;

if sum(P) ~= 1.0000
	error('Cummulative probability NOT equal to unity');   
end;   
P_org     = flipud(sort(P)); 
P         = P_org;
P_mod     = P_org;
P_history = [P_history;P];

for iii = N:-1:3, 
   p = P(iii) + P(iii-1);
   P = flipud(sort([P(1:iii-2);p]));
   P_history = [P_history [P;zeros(N-iii+1,1)]];
end;   
P_history

%-------------Mess-Them-Up Part----------------------
P_history = [];
for index = 1:N
	P_mod(index) = P_mod(index) - 0.0001*index; 	% messing   
end;   
P = P_mod;
P_history = [P_history;P_mod];
for iii = N:-1:3, 
   p = P(iii) + P(iii-1);
   P = flipud(sort([P(1:iii-2);p]));
   P_history = [P_history [P;zeros(N-iii+1,1)]];
end;  
%--------------------------------------------------

%--Coding Algorithm--
for iiii = 1:N,
   code = '';
   runner = P_history(iiii,1);
   for k=1:N-1,
      if runner == P_history(N-k,k),
      		code = ['0' code];
       	runner = runner + P_history(N-k+1,k);
               
      elseif runner == P_history(N-k+1,k),
          code = ['1' code];
          runner = runner + P_history(N-k,k);
      end;   
   end;      
codes = [codes;{code}];   
end;  

%--Display Phase--
disp('-----------------------------------------');
disp('Probabilities of symbols       Codewords ');
disp('-----------------------------------------');
for v = 1:N,
	fprintf('%0.4f                  --->',P_org(v));disp(codes(v));   
end;   
disp('-----------------------------------------');

%---------------EOF------------