Matlab Scripts for Huffman Encoding of text files

Dear All,

I am desperately in need of help.

I have a matlab .m file for huffman Text file compression and I wanna change it to VHDL using accelDSP .I tried a lot but can't do it.

Please help me in doing that.

here is the matlab m file

function HL = hufflen(S)
% Based on probability (or number of occurences) of each symbol 
% the length for the Huffman codewords are calculated.
% HL = hufflen(S);

% ------------------------------------------------------------------
% Arguments:
%  S  a vector with number of occurences or probability of each  symbol
% Only positive elements of S are used, zero (or negative)
% elements get length 0.
%  HL length (bits) for the codeword for each symbol 
% --------------------------------------------------------------
% Example:
% hufflen([1,0,4,2,0,1])  =>  ans = [3,0,1,2,0,3]
% hufflen([10,40,20,10])  =>  ans = [3,1,2,3]

S=[1,0,4,2,0,1];
if nargin<1
   error('hufflen: see help.')
end

HL=zeros(size(S));  
S=S(:);
Ip=find(S>0);       % index of positive elements
Sp=S(Ip);           % the positive elements of S

N=length(Sp);       % elements in Sp vector
HLp=zeros(size(Sp));    
C=[Sp(:);zeros(N-1,1)];  % count or weights for each "tree"
Top=1:N;                 % the "tree" every symbol belongs to
[So,Si]=sort(-Sp);       % Si is indexes for descending symbols
last=N;                  % Number of "trees" now
next=N+1;                % next free element in C 
while (last > 1)
   % the two smallest "trees" are put together
   C(next)=C(Si(last))+C(Si(last-1));
   I=find(Top==Si(last));
   HLp(I)=HLp(I)+1;   % one extra bit added to elements in "tree"
   Top(I)=next;
   I=find(Top==Si(last-1));
   HLp(I)=HLp(I)+1;   % and one extra bit added to elements in "tree"
   Top(I)=next;
   last=last-1;                 
   Si(last)=next;
   next=next+1;
   % Si shall still be indexes for descending symbols or nodes
   count=last-1;
   while ((count> 0) && (C(Si(count+1)) >= C(Si(count))))
      temp=Si(count);
      Si(count)=Si(count+1);
      Si(count+1)=temp;
      count=count-1;
   end
end

HL(Ip)=HLp;
return;

function HK = huffcode(HL,Display)
% Based on the codeword lengths this function find the Huffman codewords
%
% HK = huffcode(HL,Display);
% HK = huffcode(HL);
% ------------------------------------------------------------------
% Arguments:
%  HL     length (bits) for the codeword for each symbol 
%         This is usually found by the hufflen function
%  HK     The Huffman codewords, a matrix of ones or zeros
%         the code for each symbol is a row in the matrix
%         Code for symbol S(i) is: HK(i,1:HL(i))
%         ex: HK(i,1:L)=[0,1,1,0,1,0,0,0] and HL(i)=6 ==> 
%             Codeword for symbol S(i) = '011010'
%  Display==1  ==> Codewords are displayed on screen, Default=0
% ------------------------------------------------------------------

if nargin<1
   error('huffcode: see help.')
end
if nargin<2
  Display = 0;
end
if (Display ~= 1)
   Display = 0;
end

N=length(HL);
L=max(HL);
HK=zeros(N,L);
[HLs,HLi] = sort(HL);
Code=zeros(1,L); 
for n=1:N
   if (HLs(n)>0)
      HK(HLi(n),:) = Code;
      k = HLs(n);
      while (k>0)                 % actually always!  break ends loop
         Code(k) = Code(k) + 1;
         if (Code(k)==2)
            Code(k) = 0;
            k=k-1;
         else
            break
         end
      end
   end
end

if Display
   for n=1:N
      Linje = ['  Symbol ',int2str(n)];
      for i=length(Linje):15
         Linje = [Linje,' '];
      end
      Linje = [Linje,'  gets code: '];
      for i=1:HL(n)
         if (HK(n,i)==0)
            Linje = [Linje,'0'];
         else
            Linje = [Linje,'1'];
         end
      end
      disp(Linje);
   end
end         

return;

function Htree = hufftree(HL,HK)
% make Huffman-tree from HL, length of Huffman codes
% The Huffman codes are also needed, and if they are known
% they can be given as an extra input argument
%
% Htree = hufftree(HL,HK);
% Htree = hufftree(HL);
% ------------------------------------------------------------------
% Arguments:
%  HL     length (bits) for the codeword for each symbol 
%         This is usually found by the hufflen function
%  HK     The Huffman codewords, a matrix of ones or zeros
%         the code for each symbol is a row in the matrix
%  Htree  A matrix, (N*2)x3, representing the Huffman tree, 
%         needed for decoding. Start of tree, root, is Htree(1,:).
%         Htree(i,1)==1 indicate leaf and Htree(i,1)==0 indicate branch
%         Htree(i,2) points to node for left tree if branching point and
%         symbol number if leaf. Note value is one less than symbol number.
%         Htree(i,2) points to node for right tree if branching point
%         Left tree is '0' and right tree is '1'

 %----------------------------------------------------------------
if nargin<1
   error('hufftree: see help.');
end
if nargin<2
  HK = huffcode(HL);
end
N=length(HL);       % number of symbols

Htree=zeros(N*2,3);
root=1;
next=2;
for n=1:N
   if HL(n)>0
      % place this symbol correct in Htree
      pos=root;
      for k=1:HL(n)
         if ((Htree(pos,1)==0) && (Htree(pos,2)==0)) 
            % it's a branching point but yet not activated
            Htree(pos,2)=next;
            Htree(pos,3)=next+1;
            next=next+2;
         end
         if HK(n,k)
            pos=Htree(pos,3);     % goto right branch
         else
            pos=Htree(pos,2);      % goto left branch 
         end
      end
      Htree(pos,1)=1;   % now the position is a leaf
      Htree(pos,2)=n;   % and this is the symbol number it represent  
   end
end

return

[Walter Roberson]

You have given us the .m source file, but you have not told us anything about the problems you are encountering in converting it to VHDL. What have you tried, and what problems do you see?

[Walter Roberson]

Thanks for cleaning up the source. Unfortunately this posting doesn't say anything about the errors. Was this the one where it was complaining about not knowing how to strcat?

[Tadele Gerem]

Dear Walter Roberson,

1.I have written the following script file

clear all;

close all

%Define constants

%Streaming Loop

S=[1,0,4,2,0,1];

for i= 1:length(S)

%Design Function

HL = All_in_one(S)

for i= 1:length(S)

%Design Function

HK = huffcode(HL)

end

for i= 1:length(S)

%Design Function

Htree = hufftree(HL,HK)

end

end

2.I have given the above function file for accelDSP

I have got the following error

I-MAT-0027): C:\Program Files\MATLAB\R2009b\toolbox\matlab\strfun\int2str.m(48): The following non-synthesizable statement has been automatically ignored: 'precision_string = sprintf( '%%%d.0f', d );'

#( I-MAT-0027): C:\Program Files\MATLAB\R2009b\toolbox\matlab\strfun\int2str.m(48): The following non-synthesizable statement has been automatically ignored: 't = sprintf( precision_string, x( i, : ) );'

#(E-MAT-0198): The following functions are unknown or unsynthesizable and could not be resolved:

File: 'C:\Xilinx\10.1\DSP_Tools\AccelDSP\Examples\Huffman\done1\All_in_one.m' Function Name: 'find'

#File: 'C:\Xilinx\10.1\DSP_Tools\AccelDSP\Examples\Huffman\done1\All_in_one.m' Function Name: 'sort'

# File: 'C:\Program Files\MATLAB\R2009b\toolbox\matlab\strfun\int2str.m' Function Name: 'isfinite'

# File: 'C:\Program Files\MATLAB\R2009b\toolbox\matlab\strfun\int2str.m' Function Name: 'numel'

# File: 'C:\Program Files\MATLAB\R2009b\toolbox\matlab\strfun\int2str.m' Function Name: 'cell'

# File: 'C:\Program Files\MATLAB\R2009b\toolbox\matlab\strfun\int2str.m' Function Name: 'char'

#

# Remedy: Please check to make sure the function is in the MATLAB path. If possible, replace with an AccelWare function.

#

#( E-ANALYZE-0013): Finished analysis of full design. Some problems were encountered please correct.

[Walter Roberson]

In huffcode(), you have a line,

Linje = [' Symbol ',int2str(n)];

I would suggest trying to change that to

Linje = [' Symbol ', sprintf('%d',n)];

I don't promise that it will work, but it will remove some of the warnings, such as about isfinite(); it might say that it is non-synthesizable, though.

[Walter Roberson]

Better yet, that call to int2str() occurs within an "if Display" block, but in your circumstances, Display can never be true. You can comment out the entire "if Display" block and then there would be no need to call int2str() or equivalent.

Answer 1

[Kaustubha Govind]

Since you are using AccelDSP, it may be best to contact Xilinx Support for help. Most of us here have no experience with the capabilities/limitations of the MATLAB features that AccelDSP supports.