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