arithmatic_encoding_decoding/static_arith.m at master · asheeshtripathi/arithmatic_encoding_decoding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
clear;
clc;
format long;
%This code takes 4 sybols,alpahabets with predefined probabilities pr.
%N is number of symbols to be encoded, S is random genrated symbols.
alphabet=[0,1,2,3,4,5,6,7,8,9,10];
M = length(alphabet);
pr = rand(1,M);
pr = pr./sum(pr);
c = [0, cumsum(pr)];
N = 100000;
S = round(rand(1,N)*max(alphabet));
ac_encoded_stream = zeros(0, 0, 'uint8');
ac_encoded_stream = arithmetic_encoder(N, S, M, c, ac_encoded_stream);
ac_encoded_stream = double(ac_encoded_stream);
symbol_stream = [];
symbol_stream = arithmetic_decoder(N, M, c,ac_encoded_stream, symbol_stream);
num_bits = 4*length(S); %4 bits reqired to represent 11 symbols.
fprintf(' \n total bits without compression =  %d',num_bits);
fprintf(' \n total bits after compression =  %d',length(ac_encoded_stream));
compression = (1 - (length(ac_encoded_stream)/num_bits)) * 100;
fprintf('\n compression percentage =  %.2f',compression);
if((S-symbol_stream) == 0)
fprintf(' \n no error in encoding and decoding ');
end
function d = arithmetic_encoder(N, S, M, c, d)
b = 0;
l = 1;
t = 0;
for k=1:N
    s_k = S(k);
    [b, l] = interval_update(s_k, b, l, M, c);
    if (b >= 1)
        b = b - 1;
        d = propagate_carry(t,d);
    end
    if (l <= 0.5)
        [b, l, t, d] = encoder_renormalization(b, l, t, d);
    end
end
[d] = code_value_selection(b, t, d);
end

function [b,l] = interval_update(s, b, l, M, c)
if (s == M-1)
    y = b + l;
else
    y = b+l*c(s + 1 + 1);
end
b=b+l*c(s + 1);
l=y-b;
end

function [d] = propagate_carry(t, d)
n = t;
while(d(n) == 1)
    d(n)=0;
    n = n - 1;
end
d(n) = 1;
end

function [b, l, t, d] = encoder_renormalization(b, l, t, d)
while (l <= 0.5)
    t = t+1;
    l = 2*l;
    if (b >= 0.5)
        d(t) = 1;
        b = 2*(b-0.5);
    else
        d(t) = 0;
        b = 2*b;
    end
end
end

function [d] = code_value_selection(b, t, d)
t = t + 1;
if (b <= 0.5)
    d(t) = 1;
else
    d(t) = 0;
    d = propagate_carry(t-1, d);
end
end

function S = arithmetic_decoder(N, M, c, d, S)
b = 0;
l = 1;
% assume P < # bits of in significant/matissa
%P = length(d);
%P = min(length(d), 52);
P = 50;

v = 0;
for n=1:P
    if (n <= length(d))
        v = v + d(n)/(2^n);
    end
end
t = P;
for k=1:N
    [s_k, l, b] = interval_selection(v, b, l, M, c);
    S(k) = s_k;
    if (b>= 1.0)
        b = b - 1;
        v = v - 1;
    end
    if (l <= 0.5)
        [v, b, l, t] = decoder_renormalization(v, b, l, t, d, P);
    end
end
end

function [s, l, b] = interval_selection(v, b, l, M, c)
s = M-1;
x = b + l * c(M);
y = b + l;
while (x > v)
    s = s - 1;
    y = x;
    x = b + l * c(s+1);
end
b = x;
l = y - b;
end

function [v, b, l, t] = decoder_renormalization(v, b, l, t, d, P)
while (l <= 0.5)
    if (b >= 0.5)
        b = 2*(b - 0.5);
        v = 2*(v - 0.5);
    else
        b = 2*b;
        v = 2*v;
    end
    t = t + 1;
    if (t <= length(d))
        v = v + d(t)/(2^P);
    end
    l = 2*l;
end
end