octave_packages/communications-1.1.1/huffmandeco.m

   1 ## Copyright (C) 2006 Muthiah Annamalai <muthiah.annamalai@uta.edu>
   2 ## Copyright (C) 2011 Ferran Mesas Garcia <ferran.mesas01@gmail.com>
   3 ##
   4 ## This program is free software; you can redistribute it and/or modify it under
   5 ## the terms of the GNU General Public License as published by the Free Software
   6 ## Foundation; either version 3 of the License, or (at your option) any later
   7 ## version.
   8 ##
   9 ## This program is distributed in the hope that it will be useful, but WITHOUT
  10 ## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11 ## FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
  12 ## details.
  13 ##
  14 ## You should have received a copy of the GNU General Public License along with
  15 ## this program; if not, see <http://www.gnu.org/licenses/>.
  16
  17 ## -*- texinfo -*-
  18 ## @deftypefn {Function File} {@var{sig} =} huffmandeco (@var{hcode}, @var{dict})
  19 ## Decode signal encoded by @code{huffmanenco}.
  20 ##
  21 ## This function uses a dict built from the
  22 ## @code{huffmandict} and uses it to decode a signal list into a huffman
  23 ## list. A restriction is that @var{hcode} is expected to be a binary code
  24 ##
  25 ## The returned @var{sig} set that strictly belongs in the range @code{[1,N]}
  26 ## with @code{N = length(@var{dict})}. Also @var{dict} can only be from the
  27 ## @code{huffmandict} routine. Whenever decoding fails, those signal values a
  28 ## re indicated by @code{-1}, and we successively try to restart decoding
  29 ## from the next bit that hasn't failed in decoding, ad-infinitum. An example
  30 ## of the use of @code{huffmandeco} is:
  31 ##
  32 ## @example
  33 ## @group
  34 ## hd    = huffmandict (1:4, [0.5 0.25 0.15 0.10]);
  35 ## hcode = huffmanenco (1:4, hd);
  36 ## back  = huffmandeco (hcode, hd)
  37 ##       @result{} [1 2 3 4]
  38 ## @end group
  39 ## @end example
  40 ## @seealso{huffmandict, huffmanenco}
  41 ## @end deftypefn
  42
  43 function symbols = huffmandeco (hcode, dict)
  44
  45   if (nargin != 2)
  46     print_usage();
  47   elseif (!all((hcode == 1) + (hcode == 0)) || !isvector(hcode))
  48     error ("first argument must be a binary array");
  49   elseif (!strcmp (class (dict), "cell"))
  50     error ("second argument must be of the class dict (from `huffmandict')");
  51   end
  52
  53   ## Convert the Huffman Dictionary to a Huffman Tree represented by
  54   ## an array.
  55   tree = dict2tree(dict);
  56
  57   ## Traverse the tree and store the symbols.
  58   symbols = [];
  59   pointer = 1; # a pointer to a node of the tree.
  60   for i = 1:length (hcode);
  61     if (tree(pointer) != -1)
  62       symbols = [symbols, tree(pointer)];
  63       pointer = 1;
  64     endif
  65     pointer = 2 * pointer + hcode(i);
  66   endfor
  67
  68   ## Check if decodification was successful
  69   if (tree(pointer) == -1)
  70     warning ("could not decode last symbol.")
  71   endif
  72   symbols = [symbols, tree(pointer)];
  73 endfunction
  74
  75 function tree = dict2tree (dict)
  76   L = length(dict);
  77   lengths = zeros(1,L);
  78
  79   ## the depth of the tree is limited by the maximum word length.
  80   for i = 1:L
  81     lengths(i) = length (dict{i});
  82   endfor
  83   m = max (lengths);
  84
  85   tree = zeros(1,2^(m+1)-1)-1;
  86
  87   for i = 1:L
  88     pointer = 1;
  89     word    = dict{i};
  90     for bit = word
  91       pointer = 2 * pointer + bit;
  92     endfor
  93     tree(pointer) = i;
  94   endfor
  95 endfunction
  96
  97 %!assert(huffmandeco(huffmanenco(1:4, huffmandict(1:4,[0.5 0.25 0.15 0.10])), huffmandict(1:4,[0.5 0.25 0.15 0.10])), [1:4],0)
  98 %!assert(huffmandeco(huffmanenco([1:100 100:-1:1], huffmandict(1:100,ones(1,100)/100)), huffmandict(1:100,ones(1,100)/100)), [1:100 100:-1:1],0)
  99 %!assert(huffmandeco([huffmanenco(1:4, huffmandict(1:4,[0.5 0.25 0.15 0.10])) 0], huffmandict(1:4,[0.5 0.25 0.15 0.10])), [1:4 -1],0)
 100 %!fail('huffmandeco([huffmanenco(1:4, huffmandict(1:4,[0.5 0.25 0.15 0.10])) 0], huffmandict(1:4,[0.5 0.25 0.15 0.10]))','warning')
 101 %!fail('huffmandeco(''this is not a code'',huffmandict(1:4,[0.5 0.25 0.15 0.10]))')
 102 %!fail('huffmandeco([1 0 1 0],''this is not a dictionary'')')