(a) For a binary source with probabilities p(0)=0.9, p(1)=0.1, design a Huffman

Question

(a) For a binary source with probabilities p(0)=0.9, p(1)=0.1, design a Huffman code for the source obtained by blocking m bits together, m=1,2 and 3. Plot the average lengths versus m. Comment on your result. Additional hint: Consider the alphabet 'a' and 'b'. Using Huffman on these characters is considered as working on blocks of m=1. Next, working on the alphabet 'aa', 'ab' 'bb' is considered as working on blocks of m=2. Finally, working on the alphabet 'aaa', 'aab'....'bbb' is working on blocks of m=3

Explanation / Answer

The source reduction and code assignment procedures just described are implemented by using the following M function.

function CODE = huffman(p)
%HUFFMAN Builds a variable-lenght Huffman code for a symbol source.
%CODE = HUFFMAN(P) returns a huffman code as binary strings in cell
%array CODE for input symbol probability vector P. Each word in CODE
%corresponds to a symbol whose probability is at the corresponding index
% of P.
%
%check the input arguments for reasonableness.
error(nargchk(1,1,nargin));
if (ndims(p) ~= 2) | (min(size(p))>1) | ~isreal(p) | ~isnumeric(p)
error(‘P must be a real numeric vector.’);
end
% Global variable surviving all recursions of function ‘makecode’
global CODE
CODE = cell(length(p),1);             % Init the global cell array
if length(p) > 1                     % When more than one symbol…
p = p/sum(p);                     % Normalize the input probabilities
s = reduce(p);                    % Do Huffman source symbol reductions
makecode(s, []);                  % Recursively generate the code
else
CODE = {‘1’};                    % Else, trivial one symbol case!
end
%……………………………………………………………….%
function s = reduce(p);
%Create a Huffman source reduction tree in a MATLAB cell structure by
%performing source symbol reductions until there are only two reduced
%symbols remaining.
s = cell(length(p),1);
%Generate a starting tree with symbol nodes 1,2,3,.. to reference the
%symbol probabilities.
for i = 1:length(p)
s{i} = i;
end
while numel(s) > 2
[p,i] = sort(p);             % Sort the symbol probabilities
p(2) = p(1) + p(2);          % Merge the 2 lowest probabilities
p(1) = [];                  % and prune the lowest one
s = s(i);                    % Reorder tree for new prbabilities.
s{2} = {s{1},s{2}};          % and merge & prune its nodes
s(1) = [];                  % to match the probabilities
end

%……………………………………………………………….%
function makecode(sc, codeword)
% Scan the nodes of a Huffman source reduction tree recursively to
% generate the indicated variable length code words.
% Global variable surviving all the recursive calls
global CODE
if isa(sc,’cell’)                                          % For cell array nodes,
makecode(sc{1},[codeword 0]);         % add 0 if the 1st element,
makecode(sc{2}, [codeword 1]);        % or a 1 if the 2nd
else                                                            % For leaf (numeric) nodes,
CODE{sc} = char(‘0’ + codeword);     % create a char code string
end

Just save this above code as “huffman.m” file.

After creating the M file for implementing the huffman code. Now we’ll test this huffman function. we’ll do it by making another M file named as example.m

clc
% provide the input vector to create the huffman code
f = [0.1875 0.5 0.125 0.1875];
c = huffman(f) %calling the huffman function

Just save and run the above code and output will b shown.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.