Mercurial > forge

changeset 2544:0064fb925500 octave-forge

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Adding shannon fano codes on lines of Huffman code, and removing older version of shannonfano_code inline with expectations of the other-lead...
author gnumuthu
date Mon, 02 Oct 2006 06:29:09 +0000
parents 85d419c88555
children d7f4b18f9338
files main/comm/inst/huffmandict.m main/comm/inst/shannonfanodeco.m main/comm/inst/shannonfanodict.m main/comm/inst/shannonfanoenco.m
diffstat 4 files changed, 286 insertions(+), 4 deletions(-) [+]
line wrap: on
line diff
--- a/main/comm/inst/huffmandict.m	Mon Oct 02 06:22:48 2006 +0000
+++ b/main/comm/inst/huffmandict.m	Mon Oct 02 06:29:09 2006 +0000
@@ -75,6 +75,7 @@
     error("Usage: huffman_dict(source_prob,{togglecode 1-0 in code});")
   elseif nargin < 3
     togglecode=0;
+    minvar=0;
   elseif nargin < 4
     minvar=0;
   end
@@ -164,10 +165,6 @@
     I=I+1;
   end
 
-  one_cw="1";
-  zero_cw="0";
-
-
   if (togglecode==0)
       one_cw=1;
       zero_cw=0;
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main/comm/inst/shannonfanodeco.m	Mon Oct 02 06:29:09 2006 +0000
@@ -0,0 +1,136 @@
+## (C) 2006, Sep 30, Muthiah Annamalai, <muthiah.annamalai@uta.edu>
+## 
+## This program is free software; you can redistribute it and/or modify
+## it under the terms of the GNU General Public License as published by
+## the Free Software Foundation; either version 2 of the License, or
+## (at your option) any later version.
+##
+## This program is distributed in the hope that it will be useful,
+## but WITHOUT ANY WARRANTY; without even the implied warranty of
+## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+## GNU General Public License for more details.
+##
+## You should have received a copy of the GNU General Public License
+## along with this program; if not, write to the Free Software
+## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+##
+
+##
+## usage: sig=shannonfanodeco(hcode,dict)
+## The function returns the original signal that was 
+## Shannonfano encoded signal using shannonfanoenco. This function uses
+## a dict built from the shannonfanodict and uses it to decode a signal 
+## list into a shannonfano list.
+## Restrictions include hcode is expected to be a binary code;
+## returned signal set that strictly belongs in the range [1,N]
+## with N=length(dict). Also dict can  only be from the
+## shannonfanodict() routine. Whenever decoding fails,
+## those signal values are indicated by -1, and we successively 
+## try to restart decoding from the next bit that hasnt failed in 
+## decoding, ad-infinitum. 
+##
+## example: hd=shannonfanodict(1:4,[0.5 0.25 0.15 0.10])
+##          hcode=shannonfanoenco(1:4,hd) #  [ 1   0   1   0   0   0   0   0   1 ]
+##          shannonfanodeco(hcode,hd) # [1 2 3 4]
+## 
+function sig=shannonfanodeco(hcode,dict)
+  if ( nargin < 2 || strcmp(class(dict),"cell")~=1 )
+    error('usage: shannonfanoenco(sig,dict)');
+  end
+  if (max(hcode) > 1 || min(hcode) < 0)
+    error("hcode has elements that are outside alphabet set ...
+	Cannot decode.");
+  end
+  
+# TODO:
+# O(log(N)) algorithms exist, but we need some effort to implement those
+# Maybe sometime later, it would be a nice 1-day project
+# Ref: A memory efficient Shannonfano Decoding Algorithm, AINA 2005, IEEE
+#
+
+# TODO: Somebody can implement a 'faster' algorithm than O(N^3) at present
+# Decoding Algorithm O(N+k*log(N)) which is approximately O(N+Nlog(N))
+#
+# 1.  Separate the dictionary  by the lengths
+#     and knows symbol correspondence.
+#
+# 2.  Find the symbol in the dict of lengths l,h where
+#     l = smallest cw length ignoring 0 length CW, and
+#     h = largest cw length , with k=h-l+1;
+#     
+# 3.  Match the k codewords to the dict using binary
+#     search, and then you can declare decision.
+#
+# 4.  In case of non-decodable words skip the start-bit
+#     used in the previous case, and then restart the same
+#     procedure from the next bit.
+#
+  L=length(dict);
+  lenL=length(dict{1});
+  lenH=0;
+
+#  
+# Know the ranges of operation
+#  
+  for itr=1:L
+    t=length(dict{itr});
+    if(t < lenL)
+      lenL=t;
+    end
+    if(t > lenH)
+      lenH=t;
+    end
+  end
+
+#
+# Now do a O(N^4) algorithm
+#
+  itr=0; #offset into the hcode
+  sig=[]; #output
+  CL=length(hcode);
+
+  %whole decoding loop.
+  while ( itr <  CL )
+    %decode one element (or just try to).
+    for itr_y=lenL:lenH
+      %look for word in dictionary.
+      %with flag to indicate found 
+      %or not found. Detect end of buffer.
+    
+      if ( (itr+itr_y) > CL )
+	break;
+      end
+
+      word=hcode(itr+1:itr+itr_y);
+      flag=0;
+      
+      %word
+
+      %search loop.
+      for itr_z=1:L
+	if(isequal(dict{itr_z},word))
+	  itr=itr+itr_y; 
+	  sig=[sig itr_z];
+	  flag=1;
+	  break;
+	end
+      end %for_ loop breaker
+
+      if( flag == 1 )
+	break; %also need to break_ above then.
+      end
+
+    end %for_ loop
+
+
+    #could not decode
+    if( flag == 0 )
+      itr=itr+1;
+      sig=[sig -1]; 
+    end
+
+  end  %while_ loop
+end
+%! 
+%! assert(shannonfanodeco(shannonfanoenco(1:4, shannonfanodict(1:4,[0.5 0.25 0.15 0.10])), shannonfanodict(1:4,[0.5 0.25 0.15 0.10])), [1:4],0)
+%!
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main/comm/inst/shannonfanodict.m	Mon Oct 02 06:29:09 2006 +0000
@@ -0,0 +1,104 @@
+## (C) 2006, September 29, Muthiah Annamalai, <muthiah.annamalai@uta.edu>
+## 
+## This program is free software; you can redistribute it and/or modify
+## it under the terms of the GNU General Public License as published by
+## the Free Software Foundation; either version 2 of the License, or
+## (at your option) any later version.
+##
+## This program is distributed in the hope that it will be useful,
+## but WITHOUT ANY WARRANTY; without even the implied warranty of
+## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+## GNU General Public License for more details.
+##
+## You should have received a copy of the GNU General Public License
+## along with this program; if not, write to the Free Software
+## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+##
+
+## usage: shannonfanodict(symbols,symbol_probabilites)
+##        computes the code words for the symbol probabilities using the
+##        shannon fano scheme. Output is a dictionary cell-array, which 
+##        are codewords, and correspond to the order of input probability.
+##
+##
+## example: CW=shannonfanodict(1:4,[0.5 0.25 0.15 0.1]);
+##          assert(redundancy(CW,[0.5 0.25 0.15 0.1]),0.25841,0.001)
+##
+function [cw_list]=shannonfanodict(symbol,P)
+  DMAX=length(P);
+  S=1:DMAX;
+#
+#FIXME: Is there any other way of doing the
+#topological sort? Insertion sort is bad.
+#
+#Sort the probability list in 
+#descending/non-increasing order.
+#Using plain vanilla insertion sort.
+#
+  for i=1:DMAX
+    for j=i:DMAX
+      
+      if(P(i) < P(j))
+	
+				#Swap prob
+	t=P(i);
+	P(i)=P(j);
+	P(j)=t;
+	
+				#Swap symb
+	t=S(i);
+	S(i)=S(j);
+	S(j)=t;
+      end
+      
+    end
+  end
+  
+  
+  #Now for each symbol you need to
+  #create code as first [-log p(i)] bits of
+  #cumulative function sum(p(1:i))
+  #
+  #printf("Shannon Codes\n");
+  #data_table=zeros(1,DMAX);
+
+   cw_list={};
+   for i=1:DMAX
+     if(P(i)>0)
+       digits=ceil(-log2(P(i))); #somany digits needed.
+     else
+       digits=0; #dont assign digits for zero probability symbols.
+     end
+     
+     Psum = sum([0 P](1:i)); #Cumulative probability
+     s=[];
+     for i=1:digits;
+       Psum=2*Psum;
+       if(Psum >= 1)
+	 s=[s 1];
+	 Psum=Psum-1;
+       else
+	 s=[s 0];
+       end       
+     end
+     cw_list{i}=s;
+   end
+   
+   #re-arrange the list accroding to input prob list.
+   cw_list2={};
+   for i=1:length(cw_list)
+     cw_list2{i}=cw_list{S(i)};
+   end
+   cw_list=cw_list2;
+
+   return;
+end
+
+%!
+%!CW=shannonfanodict(1:4,[0.5 0.25 0.15 0.1]);
+%!assert(redundancy(CW,[0.5 0.25 0.15 0.1]),0.057980,0.001)
+%!CW=shannonfanodict(1:4,[0.5 0.15 0.25 0.1]);
+%!P=[0.5 0.25 0.15 0.1 0];
+%!CW=shannonfanodict(1:5,P);
+%!redundancy(CW,P)
+%!
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main/comm/inst/shannonfanoenco.m	Mon Oct 02 06:29:09 2006 +0000
@@ -0,0 +1,45 @@
+## (C) 2006, Oct 1, Muthiah Annamalai, <muthiah.annamalai@uta.edu>
+## 
+## This program is free software; you can redistribute it and/or modify
+## it under the terms of the GNU General Public License as published by
+## the Free Software Foundation; either version 2 of the License, or
+## (at your option) any later version.
+##
+## This program is distributed in the hope that it will be useful,
+## but WITHOUT ANY WARRANTY; without even the implied warranty of
+## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+## GNU General Public License for more details.
+##
+## You should have received a copy of the GNU General Public License
+## along with this program; if not, write to the Free Software
+## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+##
+
+##
+## usage:shannonfanoenco(sig,dict)
+## The function returns the Shannon Fano encoded signal using dict.
+## This function uses a dict built from the shannonfanodict
+## and uses it to encode a signal list into a shannon fano code.
+## Restrictions include a signal set that strictly belongs
+## in the range [1,N] with N=length(dict). Also dict can
+## only be from the shannonfanodict() routine.
+## 
+## 
+## example: hd=shannonfanodict(1:4,[0.5 0.25 0.15 0.10])
+##          shannonfanoenco(1:4,hd) #  [   0   1   0   1   1   0   1   1   1   0]
+##
+##
+function sf_code=shannonfanoenco(sig,dict)
+  if nargin < 2
+    error('usage: huffmanenco(sig,dict)');
+  end
+  if (max(sig) > length(dict)) || ( min(sig) < 1)
+    error("signal has elements that are outside alphabet set ...
+	Cannot encode.");
+  end
+  sf_code=[dict{sig}];
+  return
+end
+%! 
+%! assert(shannonfanoenco(1:4, shannonfanodict(1:4,[0.5 0.25 0.15 0.10])),[   0   1   0   1   1   0   1   1   1   0],0)
+%!