octave-communications-common 1.2.1-1build1 / usr / share / octave / packages / communications-1.2.1 / shannonfanodeco.m

This file is indexed.

/usr/share/octave/packages/communications-1.2.1/shannonfanodeco.m is in octave-communications-common 1.2.1-1build1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below. 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
## Copyright (C) 2006 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 3 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, see <http://www.gnu.org/licenses/>.

## -*- texinfo -*-
## @deftypefn {Function File} {} shannonfanodeco (@var{hcode}, @var{dict})
##
## Returns the original signal that was Shannon-Fano encoded. The signal
## was encoded using @code{shannonfanoenco}. This function uses
## a dict built from the @code{shannonfanodict} and uses it to decode a signal
## list into a Shannon-Fano list. Restrictions include hcode is expected to be a binary code;
## returned signal set that strictly belongs in the @code{range [1,N]},
## with @code{N = length (dict)}. Also dict can only be from the
## @code{shannonfanodict (...)} routine. Whenever decoding fails,
## those signal values are indicated by -1, and we successively
## try to restart decoding from the next bit that hasn't failed in
## decoding, ad-infinitum.
##
## An example use of @code{shannonfanodeco} is
## @example
## @group
## hd = shannonfanodict (1:4, [0.5 0.25 0.15 0.10]);
## hcode = shannonfanoenco (1:4, hd)
##     @result{} hcode = [0 1 0 1 1 0 1 1 1 0]
## shannonfanodeco (hcode, hd)
##     @result{} [1 2 3 4]
## @end group
## @end example
## @seealso{shannonfanoenco, shannonfanodict}
## @end deftypefn

function sig = shannonfanodeco (hcode, dict)

  if (nargin != 2 || ! iscell (dict))
    print_usage ();
  endif
  if (max (hcode) > 1 || min (hcode) < 0)
    error ("shannonfanodeco: all elements of HCODE must be in the range [0,1]");
  endif

  ## FIXME:
  ## 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
  ##

  ## FIXME: 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;
    endif
    if (t > lenH)
      lenH = t;
    endif
  endfor

  ##
  ## 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;
      endif

      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;
        endif
      endfor

      if (flag == 1)
        break; # also need to break_ above then.
      endif

    endfor


    ## could not decode
    if (flag == 0)
      itr = itr + 1;
      sig = [sig -1];
    endif

  endwhile

endfunction

%!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)

%% Test input validation
%!error shannonfanodeco ()
%!error shannonfanodeco (1)
%!error shannonfanodeco (1, 2, 3)
%!error shannonfanodeco (1, 2)
%!error shannonfanodeco (2, {})

APT Browse - Built by Thomas Orozco.