octave_packages/communications-1.1.1/lz77deco.m

   1 ## Copyright (C) 2007 Gorka Lertxundi
   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} {@var{m} =} lz77deco (@var{c}, @var{alph}, @var{la}, @var{n})
  18 ## Lempel-Ziv 77 source algorithm decoding implementation. Where
  19 ##
  20 ## @table @asis
  21 ## @item @var{m}
  22 ## message decoded (1xN).
  23 ## @item @var{c}
  24 ## encoded message (Mx3).
  25 ## @item @var{alph}
  26 ## size of alphabet.
  27 ## @item @var{la}
  28 ## lookahead buffer size.
  29 ## @item @var{n}
  30 ## sliding window buffer size.
  31 ## @end table
  32 ## @seealso{lz77enco}
  33 ## @end deftypefn
  34
  35 function m = lz77deco(c, alph, la, n)
  36   if (la <= 0 || n <= 0)
  37     error("lz77deco: Lookahead buffer size and window size must be higher than 0.");
  38   endif
  39   if n - la < la
  40     error("lz77deco: Unreachable configuration: n - la >= la.");
  41   endif
  42   if alph < 2
  43     error("lz77deco: Alphabet size within less than 2 symbols? Is that possible?.");
  44   endif
  45   if columns(c) != 3
  46     error("lz77deco: Encoded message must be a Nx3 matrix.");
  47   endif
  48
  49   window = zeros(1,n);
  50   x = length(c);
  51   len = length(c);
  52
  53   for x=1:len
  54     ## update window
  55     temp = n-la+c(x,2)-c(x,1);
  56     for y=1:temp
  57       window(n-la+y) = window(c(x,1)+y);
  58     endfor
  59     window(n-la+c(x,2)+1) = c(x,3);
  60
  61     ## decoded message
  62     m_deco = window(n-la+1:n-la+c(x,2)+1);
  63     if x == 1
  64       m = m_deco;
  65     else
  66       m = [m m_deco];
  67     endif
  68
  69     ## CCW shift
  70     temp = c(x,2)+1;
  71     window(1:n-la) = window(temp+1:n-la+temp);
  72   endfor
  73
  74 endfunction
  75
  76 %!demo
  77 %! lz77deco([8 2 1 ; 7 3 2 ; 6 7 2 ; 2 8 0],3,9,18)