octave_packages/communications-1.1.1/shannonfanodeco.m

   1 ## Copyright (C) 2006 Muthiah Annamalai <muthiah.annamalai@uta.edu>
   2 ##
   3 ## This program is free software; you can redistribute it and/or modify it under
   4 ## the terms of the GNU General Public License as published by the Free Software
   5 ## Foundation; either version 3 of the License, or (at your option) any later
   6 ## version.
   7 ##
   8 ## This program is distributed in the hope that it will be useful, but WITHOUT
   9 ## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  10 ## FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
  11 ## details.
  12 ##
  13 ## You should have received a copy of the GNU General Public License along with
  14 ## this program; if not, see <http://www.gnu.org/licenses/>.
  15
  16 ## -*- texinfo -*-
  17 ## @deftypefn {Function File} {} shannonfanodeco (@var{hcode},@var{dict})
  18 ##
  19 ## Returns the original signal that was Shannonfano encoded. The signal
  20 ## was encoded using @code{shannonfanoenco}. This function uses
  21 ## a dict built from the @code{shannonfanodict} and uses it to decode a signal
  22 ## list into a shannonfano list. Restrictions include hcode is expected to be a binary code;
  23 ## returned signal set that strictly belongs in the @code{range [1,N]},
  24 ## with @code{N=length(dict)}. Also dict can  only be from the
  25 ## @code{shannonfanodict(...)} routine. Whenever decoding fails,
  26 ## those signal values are indicated by -1, and we successively
  27 ## try to restart decoding from the next bit that hasnt failed in
  28 ## decoding, ad-infinitum.
  29 ##
  30 ## An example use of @code{shannonfanodeco} is
  31 ## @example
  32 ## @group
  33 ##          hd=shannonfanodict(1:4,[0.5 0.25 0.15 0.10])
  34 ##          hcode=shannonfanoenco(1:4,hd) #  [ 1   0   1   0   0   0   0   0   1 ]
  35 ##          shannonfanodeco(hcode,hd) # [1 2 3 4]
  36 ##
  37 ## @end group
  38 ## @end example
  39 ## @end deftypefn
  40 ## @seealso{shannonfanoenco, shannonfanodict}
  41
  42 function sig=shannonfanodeco(hcode,dict)
  43   if ( nargin < 2 || strcmp(class(dict),"cell")~=1 )
  44     error('usage: shannonfanoenco(sig,dict)');
  45   end
  46   if (max(hcode) > 1 || min(hcode) < 0)
  47     error("hcode has elements that are outside alphabet set ...
  48         Cannot decode.");
  49   end
  50
  51 # TODO:
  52 # O(log(N)) algorithms exist, but we need some effort to implement those
  53 # Maybe sometime later, it would be a nice 1-day project
  54 # Ref: A memory efficient Shannonfano Decoding Algorithm, AINA 2005, IEEE
  55 #
  56
  57 # TODO: Somebody can implement a 'faster' algorithm than O(N^3) at present
  58 # Decoding Algorithm O(N+k*log(N)) which is approximately O(N+Nlog(N))
  59 #
  60 # 1.  Separate the dictionary  by the lengths
  61 #     and knows symbol correspondence.
  62 #
  63 # 2.  Find the symbol in the dict of lengths l,h where
  64 #     l = smallest cw length ignoring 0 length CW, and
  65 #     h = largest cw length , with k=h-l+1;
  66 #
  67 # 3.  Match the k codewords to the dict using binary
  68 #     search, and then you can declare decision.
  69 #
  70 # 4.  In case of non-decodable words skip the start-bit
  71 #     used in the previous case, and then restart the same
  72 #     procedure from the next bit.
  73 #
  74   L=length(dict);
  75   lenL=length(dict{1});
  76   lenH=0;
  77
  78 #
  79 # Know the ranges of operation
  80 #
  81   for itr=1:L
  82     t=length(dict{itr});
  83     if(t < lenL)
  84       lenL=t;
  85     end
  86     if(t > lenH)
  87       lenH=t;
  88     end
  89   end
  90
  91 #
  92 # Now do a O(N^4) algorithm
  93 #
  94   itr=0; #offset into the hcode
  95   sig=[]; #output
  96   CL=length(hcode);
  97
  98   %whole decoding loop.
  99   while ( itr <  CL )
 100     %decode one element (or just try to).
 101     for itr_y=lenL:lenH
 102       %look for word in dictionary.
 103       %with flag to indicate found
 104       %or not found. Detect end of buffer.
 105
 106       if ( (itr+itr_y) > CL )
 107         break;
 108       end
 109
 110       word=hcode(itr+1:itr+itr_y);
 111       flag=0;
 112
 113       %word
 114
 115       %search loop.
 116       for itr_z=1:L
 117         if(isequal(dict{itr_z},word))
 118           itr=itr+itr_y;
 119           sig=[sig itr_z];
 120           flag=1;
 121           break;
 122         end
 123       end %for_ loop breaker
 124
 125       if( flag == 1 )
 126         break; %also need to break_ above then.
 127       end
 128
 129     end %for_ loop
 130
 131
 132     #could not decode
 133     if( flag == 0 )
 134       itr=itr+1;
 135       sig=[sig -1];
 136     end
 137
 138   end  %while_ loop
 139 end
 140 %!
 141 %! 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)
 142 %!