Shannon Fano

ELEC3028 Digital Transmission – Overview & Information Theory

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....