Information Theory and Digital Communications: Entropy, Capacity, PCM, Detection and Coding

A channel takes an input X and delivers an output Y that is not always X. The quantity that measures how much of X survives is the mutual information I(X;Y) = H(X) − H(X|Y) — the uncertainty about the input, minus the uncertainty that remains after you have seen the output. It is symmetric, I(X;Y) = I(Y;X) = H(Y) − H(Y|X), which is worth knowing because one of the two forms is always the easier to compute. It is zero when input and output are independent, and equal to H(X) when the channel is noiseless. Channel capacity is then defined as the maximum of I(X;Y) over all input distributions: C = max_(p(x)) I(X;Y), in bits per channel use. The maximisation matters — capacity is a property of the channel alone, and finding it means choosing the best possible way to drive that channel. The channel coding theorem is the payoff: for any rate R < C there exist codes with arbitrarily small error probability, and for R > C there are none. Note what it does not say. It gives no construction, and it says nothing about delay or complexity, both of which grow as you approach C.

For a continuous channel of bandwidth B limited by additive white Gaussian noise, the capacity is the Shannon–Hartley result C = B log₂(1 + S/N) bit/s. Two readings of it are examinable. Read left to right and it prices bandwidth against power: a 3 kHz telephone channel at an SNR of 30 dB, that is S/N = 1000, has C = 3000 × log₂(1001) = 3000 × 9.967 = 29.9 kbit/s — which is why voiceband modems stalled just above that figure and why anything faster needed a wider channel rather than a better modem. Read the other way and it shows the two are not interchangeable. Capacity grows linearly with bandwidth but only logarithmically with power, so doubling B roughly doubles C while doubling S adds only about one bit per hertz. And bandwidth cannot be traded without limit either, because widening B at fixed transmitted power admits more noise: as B → ∞, C tends to 1.44 S/N₀, and the corresponding limit on energy per bit is Eb/N₀ ≥ ln 2 = 0.693, that is −1.59 dB. That number is the Shannon limit, and it is the floor no modulation and no code will ever get under.

Pulse code modulation is three operations in a row: sample at f_s ≥ 2W, quantise each sample to one of L = 2ⁿ levels, and encode the level as n bits. The bit rate is R_b = n f_s, and for telephone speech with W = 4 kHz, f_s = 8 kHz and n = 8, that is the familiar 64 kbit/s. Sampling is exact — the sampling theorem promises perfect reconstruction if f_s ≥ 2W and the signal is band-limited — so the only irreversible loss in PCM is quantisation. Model it as noise. A uniform quantiser of step Δ rounds each sample to within ±Δ/2, and if the error is taken as uniformly distributed over that interval its mean square is Δ²/12. That is the quantisation noise power, and it depends on the step size and on nothing else — not on the signal, not on the sampling rate.

Differential PCM attacks the redundancy that PCM ignores. Successive samples of speech or video are strongly correlated, so a great deal of each sample is predictable from the ones before it — and sending a predictable quantity is spending bits on nothing. DPCM predicts each sample from past reconstructed samples (reconstructed, not original, so that encoder and decoder track each other exactly and errors do not accumulate), and quantises only the prediction error. Because the error has a smaller variance than the signal, the same quantiser step gives a better SQNR — or equivalently, fewer bits give the same SQNR. Take a first-order predictor on a source with adjacent-sample correlation coefficient ρ = 0.9. The optimal predictor is x̂[n] = ρ x[n−1], and the residual variance is σ_e² = σ_x²(1 − ρ²) = 0.19 σ_x². The prediction gain is therefore 10 log₁₀(1/0.19) = 7.21 dB, and at 6.02 dB per bit that is 1.20 bits per sample saved — so 8-bit PCM quality is reached at about 6.8 bits, and the 64 kbit/s link becomes about 54 kbit/s for the same perceived quality. Push the predictor order up and the gain grows; delta modulation is the limiting case with a one-bit quantiser and a very high sampling rate, which trades quantisation noise for two new defects — slope overload when the signal rises faster than Δf_s, and granular noise when it is nearly flat.

Every digital modulation in the syllabus is a choice of points in a signal space, and once you write the points down as coordinates the rest is geometry. The basis is one or two orthonormal carriers — φ₁(t) = √(2/T) cos 2πf_c t and, where needed, φ₂(t) = √(2/T) sin 2πf_c t — and a symbol is a pair of numbers giving how much of each. Distances in that space are measured in √(energy), and the single number that controls error rate is the minimum distance d_min between any two points, because the noise does not care which two points you are confusing. The table below gives the four schemes as coordinates, with everything expressed in units of √E_b so that they can be compared at equal energy per bit — the only fair comparison, and the one every question makes.

Two practical points close this section. First, non-coherent detection removes the need for a carrier phase reference and costs a little performance: non-coherent BFSK has P_b = ½ e^(−Eb/2N₀), which at Eb/N₀ = 10 dB gives 3.37 × 10⁻³ against the coherent 7.83 × 10⁻⁴ — a factor of four in error rate, about 1 dB in required energy, in exchange for deleting the carrier recovery loop entirely. Second, bandwidth efficiency is what QAM is bought for. A scheme with M points carries log₂ M bits per symbol, so at a fixed symbol rate the bit rate scales as log₂ M while the bandwidth does not move at all — the bandwidth is set by the symbol rate, and that is the subject of the next section. The whole family therefore lies on one trade curve: BPSK and QPSK are power-efficient and bandwidth-hungry; 16-QAM and above are bandwidth-efficient and power-hungry, and which end of the curve a system sits on is decided by whether spectrum or transmitter power is the scarcer resource.

Pulses sent at a symbol rate R_s through a channel of finite bandwidth spread in time, so each pulse still has energy at the instants when its neighbours are being sampled. That leakage is intersymbol interference, and it is not a noise — it is a deterministic, signal-dependent error that gets worse as you send faster and cannot be removed by increasing power. The Nyquist criterion for zero ISI states the condition for escape: the overall pulse must be zero at every sampling instant other than its own, and the minimum bandwidth in which such a pulse can exist is B = R_s/2, the Nyquist bandwidth. Equivalently, a channel of bandwidth B supports at most R_s = 2B symbols per second without ISI. The pulse that achieves the bound exactly is the sinc, whose spectrum is a brick wall of width R_s/2 and whose zero crossings fall precisely on the neighbouring sampling instants.

Given a known pulse s(t) of duration T buried in white noise of two-sided PSD N₀/2, which linear filter maximises the signal-to-noise ratio at the sampling instant? The answer is the matched filter, whose impulse response is the time-reversed pulse, h(t) = s(T − t), and whose output at t = T is ∫₀ᵀ r(t)s(t) dt — the correlation of the received waveform with the known pulse. Two things about the result are worth stating precisely because both are examined. The maximum achievable ratio is SNR_max = 2E/N₀, where E = ∫s²(t)dt is the pulse energy — note that it depends on the energy only, and not on the pulse shape at all, so a rectangle, a triangle and a raised cosine of equal energy all perform identically. And the convention matters: this 2E/N₀ assumes N₀/2 is the two-sided PSD, and the same physical noise expressed as a one-sided N₀ gives the same number. A filter matched to the wrong pulse, or sampled at the wrong instant, does worse, and the amount by which it does worse is computable.

The matched filter reduces the received waveform to one number; the detector then decides which symbol was sent. Maximum a posteriori (MAP) detection chooses the symbol with the greatest posterior probability P(s_i | r), which by Bayes' rule means maximising p(r | s_i) P(s_i) — the likelihood weighted by the prior. Maximum likelihood (ML) detection drops the prior and maximises p(r | s_i) alone. MAP is optimal in the sense of minimising the probability of error, always. ML is optimal only when the priors are equal, in which case the two rules are identical because the common factor P(s_i) does not affect which likelihood is largest. That equivalence is why ML gets used almost everywhere in practice — source coding has already made the symbols nearly equiprobable — and why a question that gives you unequal priors is testing whether you noticed. Geometrically, MAP moves the decision threshold: for binary antipodal signalling the threshold sits at r_th = (σ²/2√E) ln[P(0)/P(1)] rather than at zero, biased towards the more likely symbol, so that the receiver requires more evidence before declaring the rare one.

A block code takes k message bits and appends redundancy to make n transmitted bits, at rate k/n. Its power to detect and correct is governed by one number, the minimum Hamming distance d_min, meaning the fewest bit positions in which any two distinct codewords differ. From it, two counts follow directly: the code detects up to d_min − 1 errors, and corrects up to ⌊(d_min − 1)/2⌋. The reasoning is spatial. To detect t errors, no t-bit corruption of a codeword may land on another codeword. To correct t errors, the corrupted word must still be nearer to the sent codeword than to any other, which needs twice the separation. So detection is cheap and correction is expensive, and a code can be operated either way — d_min = 4 corrects one error, or detects three, but not both at full strength simultaneously.

A cyclic redundancy check is error detection only, and its whole mechanism is polynomial division modulo 2. Treat the message as the coefficients of a polynomial M(x), choose a generator G(x) of degree r, shift the message up by r bits (which is multiplying by xʳ), divide by G(x) using XOR in place of subtraction, and transmit the message with the r-bit remainder appended. The transmitted frame is then exactly divisible by G(x), so the receiver simply divides again: a zero remainder means accept, anything else means a detected error. What makes CRC worth its arithmetic is the guarantee list that follows from the choice of G(x). A generator with more than one term detects every single-bit error. A generator with a non-zero constant term detects every burst of length r or less, which matters because real channel errors arrive in bursts rather than independently. A generator that has (x + 1) as a factor detects every odd-weight error pattern. And a primitive generator of degree r detects all double-bit errors within a frame of 2ʳ − 1 bits.

More marks are lost in this half of Section 7 to unstated conventions than to genuine ignorance, because most of the results are ratios and a ratio can be defined two ways. The EC paper's structure — 65 questions, 100 marks, 180 minutes, with General Aptitude at 10 questions for 15 marks — leaves under three minutes a question on average, and a candidate who has to reason out whether Eb/N₀ or SNR was meant has already spent that budget. So settle the conventions in advance. The marking asymmetry then decides your policy on the ones you cannot settle: a wrong MCQ costs one third of the question's value, so an MCQ narrowed to two options is worth taking and a four-way guess is not, while MSQ and NAT carry no negative marking, so every numerical-answer question is worth an attempt even from a bound rather than a full solution.