Digital communication system elements; Shannon-Fano coding

Digital communication system

A digital communication system transmits information as discrete symbols (bits) over a channel. Its functional blocks:

 Info    -> Formatter -> Source  -> Channel -> Modulator
 source     (A/D)        encoder    encoder       |
                                                  v
                                               Channel
                                       noise -> (+)
                                                  |
 User    <- Formatter <- Source  <- Channel <- Demodulator
            (D/A)        decoder    decoder    /detector

Basic elements:

1. Information source: produces the message (voice, video, text, data). Analog messages are first converted to digital by the formatter (sampling, quantizing, PCM encoding).
2. Source encoder: removes redundancy and represents the symbols with the fewest bits on average (Huffman, Shannon–Fano). It lowers the bit rate.
3. Channel encoder: adds controlled redundancy (parity bits) so the receiver can detect and correct errors (Hamming, cyclic, convolutional codes).
4. Digital modulator: converts the bits into waveforms suitable for the channel: line coding for baseband, ASK, FSK, PSK or QAM for bandpass.
5. Channel: the physical medium (wire, coaxial cable, optical fibre, radio). It adds noise, attenuation, distortion and interference.
6. Demodulator/detector: recovers the bit sequence from the received waveform, using matched filtering, sampling and decisions.
7. Channel decoder: uses the redundancy to correct errors.
8. Source decoder and formatter: rebuild the original message (D/A conversion) for the user.

Other blocks often included: encryption/decryption, multiplexing, synchronization. Performance is judged by the probability of bit error $P_e$, bandwidth efficiency (bits/s/Hz) and power efficiency ($E_b/N_0$ needed).

Shannon–Fano coding

Shannon–Fano coding is a variable-length source coding method that gives short code words to likely symbols and long ones to unlikely symbols.

Algorithm:

1. List the symbols in decreasing order of probability.
2. Split the list into two groups whose total probabilities are as nearly equal as possible.
3. Assign bit 0 to every symbol of the upper group and 1 to the lower group.
4. Repeat steps 2–3 inside each group until every group has one symbol.
5. The code word of a symbol is the sequence of bits assigned to it.

Example: $P = \{0.4, 0.2, 0.2, 0.1, 0.1\}$ for A–E. First split {A} = 0.4 vs {B, C, D, E} = 0.6.

$$\begin{aligned} \bar L &= 0.4(1)+0.2(2)+0.2(3)+0.1(4)+0.1(4) = 2.2\ \text{bits/symbol} \\ H &= 2.1219\ \text{bits/symbol}, \qquad \eta = \frac{2.1219}{2.2} = 96.45\% \end{aligned}$$

The code is a prefix code (uniquely decodable), but Shannon–Fano is not always optimal; Huffman coding is.