Digital communication system; Shannon-Fano for six symbols

Digital communication system

A digital communication system sends information as a sequence of discrete symbols (usually bits) from a source to a user.

 Source -> Formatter -> Source  -> Channel -> Modulator
 (analog   (sample,    encoder    encoder        |
 /digital)  quantize)                            v
                                              Channel
                                            (noise added)
                                                 |
 User <- Formatter <- Source  <- Channel <- Demodulator
         (D/A)        decoder    decoder     /detector

• Information source and formatter: produces the message; an analog message is sampled, quantized and coded (A/D conversion) into bits.
• Source encoder: removes redundancy so the average number of bits per symbol is close to the entropy (Huffman, Shannon–Fano). This reduces bit rate and bandwidth.
• Channel encoder: adds controlled redundancy (parity bits) so that errors caused by the channel can be detected or corrected (Hamming, cyclic, convolutional codes).
• Modulator: maps the bits onto waveforms suited to the channel: line codes for baseband, ASK/FSK/PSK/QAM for bandpass.
• Channel: wire, cable, fibre or radio link; it attenuates, distorts (ISI) and adds noise.
• Demodulator/detector: recovers the bit stream from the noisy waveform, usually with a matched filter and a decision device.
• Channel decoder, source decoder, formatter: reverse the encoding steps and deliver the message to the user.

Performance is measured by bit error probability and by bandwidth and power efficiency.

Shannon–Fano code

Probabilities add to 1. Procedure: list symbols in decreasing probability; split the list into two groups of nearly equal total probability; give 0 to the upper group and 1 to the lower group; repeat in each group until each has one symbol.

First split: {0.3, 0.25} = 0.55 and {0.2, 0.12, 0.08, 0.05} = 0.45.

Entropy:

$$H(X) = \sum p_i\log_2\frac{1}{p_i} = 2.3601\ \text{bits/symbol}$$

Average code length:

$$\begin{aligned} \bar L &= \sum p_i l_i = 0.3(2)+0.25(2)+0.2(2)+0.12(3)+0.08(4)+0.05(4) \\ &= 0.6+0.5+0.4+0.36+0.32+0.2 = 2.38\ \text{bits/symbol} \end{aligned}$$

Efficiency and redundancy:

$$\begin{aligned} \eta &= \frac{H}{\bar L} = \frac{2.3601}{2.38} = 0.9917 = 99.17\% \\ \gamma &= 1 - \eta = 0.0083 = 0.83\% \end{aligned}$$

Answer: codes $x_1 = 00$, $x_3 = 01$, $x_2 = 10$, $x_4 = 110$, $x_5 = 1110$, $x_6 = 1111$; $\bar L = 2.38$ bits/symbol, efficiency = 99.17 %, redundancy = 0.83 %.