Mã nén Lecture_1

5
Entropy for binary source: N=2
))1(log)1(log(
22
ppppH
−⋅−+⋅−=
S={0,1}
p
0
=p
p
1
=1-p
0 1
p
1-p
H=1 bit for p
0
=p
1
=0.5
6
Entropy for uniform distribution: p
i
=1/N
Uniform distribution of probabilities: p
i
=1/N:
)(log)/1(log)/1(
2
1
2
NNNH
N
i
∑
=
=⋅−=
Examples:
N= 2: p
i
=0.5; H=log
2
(2) = 1 bit
N=256: p
i
=1/256; H=log
2
(256)= 8 bits
P
i
=1/N
s
1
s
2
s
N
7
How to get the probability distribution?
1) Static modeling:
a) The same code table is applied to all input data.
b) One-pass method (encoding)
c) No side information (không cần thông tin phụ)
2) Semi-adaptive modeling:
a) Two-pass method: (1) analysis and (2) encoding.
b) Side information needed (model, code table)
3) Adaptive (dynamic) modeling:
a) One-pass method: analysis and encoding
b) Updating the model during encoding/decoding
c) No side information
8
Static vs. Dynamic: Example
S = {a,b,c}; Data: a,a,b,a,a,c,a,a,b,a.
1) Static model: p
i
=1/10
H = -log
2
(1/10)=1.58 bits
2) Semi-adaptive method: p
1
=7/10; p
2
=2/10; p
3
=1/10;
H = -(0.7*log
2
0.7 + 0.2*log
2
0.2 + 0.1*log
2
0.1)=1.16 bits
9
3) Adaptive method: Example
S = {a,b,c}; Data: a,a,b,a,a,c,a,a,b,a.
Symbol 1 2 3 4 5 6 7 8 9 10
a 1 2 3 3 4 5 5 6 7 7
b 1 1 1 2 2 2 2 2 2 3
c 1 1 1 1 1 1 2 2 2 2
Pi 1/3 2/4 1/5 3/6 4/7 1/8 5/9 6/10 2/11 7/12
0.33

0.5 0.2 0.5 0.57 0.13 0.56 0.60 0.18 0.58
H 1.58 1.0 2.32 1.0 0.81 3.0 0.85 0.74 2.46 0.78
H=(1/10)(1.58+1.0+2.32+1.0+0.81+3.0+0.85+0.74+2.46+0.78)
=1.45 bits/char
1.16 < 1.45 < 1.58
S Ad. Ad. Static
10
Shannon-Fano Code: A top-down approach
1) Sort symbols according their probabilities:
p
1
≤ p
2
≤ … ≤ p
N
2) Recursively divide into parts, each with approx. the same
number of counts (probability)
11
Shannon-Fano Code: Example (1 step)
s
i
p
i
A - 15/39
B - 7/39
C - 6/39
D - 6/39
E - 5/39
A,B, C,D,E
15,7, 6,6,5
A,B
15+7 =22
C,D,E
6+6+5=17
0 1
12
Shannon-Fano Code: Example (2 step)
s
i
p
i
A - 15/39
B - 7/39
C - 6/39
D - 6/39
E - 5/39
A,B, C,D,E
15,7, 6,6,5
A,B
15+7 =22
C,D,E
6+6+5=17
A
15
B
7
C
6
D,E
6+5=11
0 1
0 01 1
13
Shannon-Fano Code: Example (3 step)
s
i
p
i
A - 15/39
B - 7/39
C - 6/39
D - 6/39
E - 5/39
A,B, C,D,E
15,7, 6,6,5
A,B
15+7 =22
C,D,E
6+6+5=17
A
15
B
7
C
6
D,E
6+5=11
D
6
E
5
0 1
0 1 0 1
0
1
14
Shannon-Fano Code: Example (Result)
Symbol p
i
-log
2
(p
i
) Code Subtotal
A 15/39 1.38 00 2*15
B 7/39 2.48 01 2*7
C 6/39 2.70 10 2*6
D 6/39 2.70 110 3*6
E 5/39 2.96 111 3*5
Total: 89 bits
0
1
0
11 0
10
A
C
B
D
E
89/39=2.28 bits
Binary tree

Xem chi tiết: Mã nén Lecture_1