1## Copyright (C) 2006 Muthiah Annamalai <muthiah.annamalai@uta.edu>
2##
3## This program is free software; you can redistribute it and/or modify
4## it under the terms of the GNU General Public License as published by
5## the Free Software Foundation; either version 2 of the License, or
6## (at your option) any later version.
7##
8## This program is distributed in the hope that it will be useful,
9## but WITHOUT ANY WARRANTY; without even the implied warranty of
10## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11## GNU General Public License for more details.
12##
13## You should have received a copy of the GNU General Public License
14## along with this program; If not, see <http://www.gnu.org/licenses/>.
15##
16
17## -*- texinfo -*-
18## @deftypefn {Function File} {} arithmetic_decode (@var{tag_message}, @var{symbol_probabilites_list})
19##
20## Computes the message from arithmetic code given  with symbol
21## probabilities. The arithmetic decoding procedure assumes
22## that @var{message} is a list of numbers and the symbol probabilities
23## correspond to the index. The message is returned. For example
24##
25## @example
26## @group
27##          symbols=[1,2,3,4]; sym_prob=[0.5 0.25 0.15 0.10];
28##          message=[1, 1, 2, 3, 4];
29##          arithmetic_encode(message,sym_prob) ans=0.18078
30##          arithmetic_decode(0.18078,sym_prob) ans=[1 1 2 3 4];
31## @end group
32## @end example
33## @end deftypefn
34## @seealso{arithmetic_encode}
35
36% FIXME
37% -----
38% Limits on floating point lengths. Not fool proof
39% (interval doubling? not implemented). Maynot converge!
40%
41% First assume that the list is in symbolic-order
42% (sorting not necessary).
43%
44% Tag is a floating point thing generated by the
45% encoder.
46%
47% Message is an array of symbols (numbers).
48%
49function message=arithmetic_decode(tag,problist,tolerance)
50  if nargin < 2
51    error("Usage: arithmetic_decode(tag,problist,tolerance=1e-8)");
52  elseif nargin < 3
53    tolerance=1e-8;
54  end
55
56  %start from the extreme extents & find the sweet-spot.
57  Up=1.0;
58  Lo=0.0;
59  L_SYM=length(problist);
60
61  mytag=0;
62  message=[];
63
64  while (mytag~=tag)
65    % initial guess for the sweet-spot.
66
67    %some loop-invariants.
68    found=0;
69    T1=Lo;
70    T2=+(Up-Lo);
71
72    for itr=1:L_SYM
73      T3=sum(problist(1:itr));
74      tL=T1+T2*(T3-problist(itr));
75      tU=T1+T2*T3;
76
77      %identify the correct spot.
78      if((tL < tag) && (tag < tU))
79	found=1;
80	break;
81      end
82    end
83
84    if(~found)
85      warning("Cannot decode letter. Defaults to max symbol.\n");
86    end
87
88    Up=tU;
89    Lo=tL;
90    mytag=0.5*(tL+tU);
91    message=[message itr];
92    if(abs(tag-mytag)<tolerance)
93      break;
94    end
95  end
96  return;
97end
98%!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)
99