Logo Search packages:      
Sourcecode: octave-informationtheory version File versions

arithmetic_decode.m

## 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 2 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} {} arithmetic_decode (@var{tag_message}, @var{symbol_probabilites_list})
##
## Computes the message from arithmetic code given  with symbol
## probabilities. The arithmetic decoding procedure assumes
## that @var{message} is a list of numbers and the symbol probabilities
## correspond to the index. The message is returned. For example
##
## @example
## @group
##          symbols=[1,2,3,4]; sym_prob=[0.5 0.25 0.15 0.10];
##          message=[1, 1, 2, 3, 4];
##          arithmetic_encode(message,sym_prob) ans=0.18078
##          arithmetic_decode(0.18078,sym_prob) ans=[1 1 2 3 4];
## @end group
## @end example
## @end deftypefn
## @seealso{arithmetic_encode}

% FIXME
% -----
% Limits on floating point lengths. Not fool proof 
% (interval doubling? not implemented). Maynot converge!
%
% First assume that the list is in symbolic-order 
% (sorting not necessary). 
%
% Tag is a floating point thing generated by the 
% encoder.
%
% Message is an array of symbols (numbers).
%
function message=arithmetic_decode(tag,problist,tolerance)
  if nargin < 2
    error("Usage: arithmetic_decode(tag,problist,tolerance=1e-8)");
  elseif nargin < 3
    tolerance=1e-8;
  end

  %start from the extreme extents & find the sweet-spot.
  Up=1.0;
  Lo=0.0;
  L_SYM=length(problist);

  mytag=0;
  message=;

  while (mytag~=tag)
    % initial guess for the sweet-spot.

    %some loop-invariants.
    found=0;
    T1=Lo;
    T2=+(Up-Lo);
    
    for itr=1:L_SYM
      T3=sum(problist(1:itr));
      tL=T1+T2*(T3-problist(itr));
      tU=T1+T2*T3;

      %identify the correct spot.
      if((tL < tag) && (tag < tU))
      found=1;
      break;
      end
    end

    if(~found)
      warning("Cannot decode letter. Defaults to max symbol.\n");
    end

    Up=tU;
    Lo=tL;
    mytag=0.5*(tL+tU);
    message=[message itr]; 
    if(abs(tag-mytag)<tolerance)
      break;
    end
  end
  return;
end
%!assert(arithmetic_decode(0.18078,[0.5 0.25 0.15 0.10]),[1, 1, 2, 3, 4,1, 4, 4, 2, 4,1],1)

Generated by  Doxygen 1.6.0   Back to index