/usr/share/octave/packages/communications-1.1.1/shannonfanodeco.m is in octave-communications-common 1.1.1-1.
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 | ## 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 Shannonfano 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 shannonfano 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 hasnt 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) # [ 1 0 1 0 0 0 0 0 1 ]
## shannonfanodeco(hcode,hd) # [1 2 3 4]
##
## @end group
## @end example
## @end deftypefn
## @seealso{shannonfanoenco, shannonfanodict}
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)
%!
|