Shannon Fano
S Chen
Example 1
1. A source emits symbols Xi, 1 ≤ i ≤ 6, in the BCD format with probabilities P (Xi)
as given in Table 1, at arate Rs = 9.6 kbaud (baud=symbol/second).
State (i) the information rate and (ii) the data rate of the source.
2. Apply Shannon-Fano coding to the source signal
Xi
characterised in Table 1. Arethere any disadvantages
A
in the resulting code words?
B
3. What is the original symbol sequence of the Shannon- C
Fano coded signal 110011110000110101100?
D
E
4. What is the data rate of thesignal after Shannon-Fano
F
coding? What compression factor has been achieved?
Table 1.
P (Xi) BCD word
0.30
000
0.10
001
0.02
010
0.15
011
0.40
100
0.03
101
5. Derive the codingefficiency of both the uncoded BCD signal as well as the
Shannon-Fano coded signal.
6. Repeat parts 2 to 5 but this time with Huffman coding.
72
ELEC3028 Digital Transmission – Overview &Information Theory
S Chen
Example 1 - Solution
1. (i) Entropy of source:
6
X
P (Xi ) · log2 P (Xi ) = −0.30 · log2 0.30 − 0.10 · log2 0.10 − 0.02 · log2 0.02
H=−
i=1
−0.15 · log2 0.15 − 0.40· log2 0.40 − 0.03 · log2 0.03
=
0.52109 + 0.33219 + 0.11288 + 0.41054 + 0.52877 + 0.15177
=
2.05724 bits/symbol
Information rate: R = H · Rs = 2.05724 [bits/symbol] · 9600[symbols/s] = 19750 [bits/s]
(ii) Data rate = 3 [bits/symbol] · 9600 [symbols/s] = 28800 [bits/s]
2. Shannon-Fano coding:
X P (X ) I (bits)
steps
code
E
A
D
B
F
C
Disadvantage: the rare code wordsbuffer of 5 bit is required.
0.4
1.32
0
0.3
1.74
1
0.15
2.74
1
0.1
3.32
1
0.03
5.06
1
0.02
5.64
1
have maximum possible
0
10
11
11
11
length of
0
1
1
q
0
10110
1110
0 11110
1 11111
− 1 = 6 − 1 = 5, and a
73
ELEC3028 Digital Transmission – Overview & Information Theory
S Chen
˛
˛˛
˛˛˛˛
˛˛
˛0˛11110˛0˛0˛0˛110˛10˛110˛0 = DEFEEEDADE
3....
Regístrate para leer el documento completo.