Information theory and coding

In short

Information theory measures how much information a source actually produces (entropy), how much a channel can reliably carry (capacity), and codes are the practical means of hitting those two limits - source codes squeeze out redundancy, channel codes add it back in a controlled way to beat noise. Claude Shannon's 1948 results set the hard ceilings: you cannot compress below the entropy, and you cannot transmit error-free above the capacity. Every modern Indian network relies on this - 4G used turbo codes, 5G NR uses LDPC and polar codes, DTH satellites use LDPC with BCH, UPI QR codes use Reed-Solomon. It is a heavily weighted GATE EC area (entropy, capacity, Huffman, Hamming, cyclic codes) and a standard interview topic at Qualcomm, Samsung R&D, Nokia, Ericsson, Sasken, Tejas Networks, C-DOT, ISRO and DRDO.

Explained

Information, entropy and source models

• Self-information of a symbol of probability p is I = log₂(1/p) bits - rarer symbols carry more information. A certain event (p = 1) carries zero information.
• Entropy H(X) = Σ pᵢ log₂(1/pᵢ) is the average information per symbol, in bits/symbol. It is the theoretical minimum average codeword length.
• Bounds: 0 ≤ H(X) ≤ log₂ M for M symbols. H = 0 for a deterministic source; H is maximum (= log₂ M) when all symbols are equiprobable.
• Binary entropy function H(p) = −p log₂p − (1−p)log₂(1−p); peaks at 1 bit when p = 0.5, zero at p = 0 or 1, and is symmetric about 0.5.
• Information rate R = r·H bits/second, where r is symbols/second. This is what must be matched against channel capacity.
• Joint and conditional entropy: H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y) (chain rule). H(X|Y) ≤ H(X) - conditioning never increases uncertainty.
• Mutual information I(X;Y) = H(X) − H(X|Y) = H(Y) − H(Y|X) = H(X)+H(Y)−H(X,Y). It is symmetric, non-negative, and zero iff X and Y are independent. H(X|Y) is called equivocation (information lost in the channel).
• Extension of a source: the n-th extension groups n symbols; H(Xⁿ) = n·H(X) for a memoryless source. Coding the extension drives the average length per symbol down towards H.
• Markov source: symbol probabilities depend on the previous state; entropy is computed as the state-probability weighted average of per-state entropies, and is lower than that of a memoryless source with the same symbol frequencies (memory = redundancy).

Source coding (data compression)

• Goal: represent the source with the fewest bits, losslessly. Average length L = Σ pᵢ nᵢ bits/symbol; efficiency η = H/L; redundancy = 1 − η.
• Prefix (instantaneous) code: no codeword is a prefix of another, so decoding needs no lookahead. All prefix codes are uniquely decodable.
• Kraft–McMillan inequality: a prefix code with lengths n₁…n_M exists iff Σ 2^−nᵢ ≤ 1. Necessary for any uniquely decodable code.
• Shannon's source coding theorem: H ≤ L < H + 1 bits/symbol; coding the n-th extension gives H ≤ Lₙ/n < H + 1/n, so L/n → H as n → ∞. You can never go below H.
• Shannon–Fano coding: sort by probability, split the list into two groups of nearly equal probability, assign 0 and 1, recurse. Simple but not always optimal.
• Huffman coding: repeatedly merge the two least-probable symbols into one node, assign 0/1 on the two branches, read codewords from root to leaf. Optimal (minimum L) for symbol-by-symbol coding with known probabilities. Neither the codewords nor even the set of lengths is unique when probabilities tie; the minimum average length L is.
• Other practical coders: arithmetic coding (codes a whole message as a fractional interval, beats Huffman when probabilities are skewed), LZW/LZ77 dictionary coding (ZIP, GIF, modems - no prior statistics needed), run-length encoding (fax, bilevel images), and lossy transform coding (JPEG, MP3, H.264) which is outside the lossless bound.
• Limitation: Huffman needs an integer number of bits per symbol, so it wastes up to ~1 bit/symbol; for a highly skewed binary source it is useless unless extended.

Channels, mutual information and capacity

• A discrete memoryless channel (DMC) is defined by the transition probability matrix P(y|x); output depends only on the current input.
• Channel capacity C = max over input distributions of I(X;Y), in bits per channel use; C·(symbol rate) gives bits/second.
• Binary symmetric channel (BSC): each bit is flipped with probability p. C = 1 − H(p) bits/use. C = 1 at p = 0 or 1 (a fully inverting channel is perfectly usable), and C = 0 at p = 0.5 - the output is then independent of the input.
• Binary erasure channel (BEC): a bit is erased with probability ε, never flipped. C = 1 − ε.
• Lossless, deterministic, noiseless and useless channels are the standard special cases: a noiseless channel has C = log₂M; a useless channel has I(X;Y) = 0.
• Shannon–Hartley (AWGN, band-limited): C = B log₂(1 + S/N) bits/s. Capacity rises linearly with bandwidth but only logarithmically with SNR - bandwidth is cheaper than power.
• Bandwidth–SNR trade-off: the same C can be had with wide band/low SNR or narrow band/high SNR; spread spectrum and OFDM exploit the first, higher-order QAM the second.
• Shannon limit: as B → ∞, C → (S/N₀)·log₂e, giving minimum Eb/N₀ = ln 2 = 0.693 = −1.59 dB. No system can operate error-free below this.
• Channel coding theorem: if R < C, codes exist with arbitrarily small error probability; if R > C, the error probability cannot be made small. It is an existence proof - it does not tell you the code.

Linear block codes

• An (n, k) block code maps k message bits to n coded bits; code rate R = k/n, redundancy = n − k parity bits.
• Linear: the modulo-2 sum of any two codewords is a codeword; the all-zero word is always a codeword.
• Generator matrix G (k × n), systematic form G = [Iₖ | P]; codeword c = m·G, so the message appears unchanged in the first k bits.
• Parity check matrix H = [Pᵀ | I_(n−k)]; G·Hᵀ = 0 and c·Hᵀ = 0 for every valid codeword.
• Syndrome s = r·Hᵀ for received word r. s = 0 means no detectable error; s ≠ 0 equals the syndrome of the error pattern, and is independent of which codeword was sent. Decoding = table lookup of the coset leader (standard array).
• Hamming distance d(x,y) = number of differing positions; minimum distance d_min = minimum weight of a non-zero codeword (true for linear codes).
• Capability: detects up to d_min − 1 errors; corrects up to t = ⌊(d_min − 1)/2⌋ errors; or corrects t and detects d while d_min ≥ t + d + 1.
• Hamming codes: (2^m − 1, 2^m − 1 − m), d_min = 3 - single-error correcting, double-error detecting (SECDED with an extra overall parity bit, used in ECC RAM). (7,4), (15,11), (31,26). They are perfect codes (meet the Hamming bound with equality).
• Bounds: Hamming (sphere-packing) bound 2^k ≤ 2ⁿ / Σ_{i=0..t} C(n,i); Singleton bound d_min ≤ n − k + 1 (codes meeting it are MDS, e.g. Reed–Solomon).
• Other simple codes: repetition code (n,1), single-parity-check (n, n−1) with d_min = 2 (detect only), Hadamard, Golay (23,12) with d_min = 7.

Cyclic codes, CRC and burst-error codes

• A cyclic code is a linear block code in which any cyclic shift of a codeword is also a codeword. Words are treated as polynomials over GF(2).
• Generator polynomial g(x) of degree n − k must divide xⁿ + 1. Non-systematic encoding: c(x) = m(x)·g(x).
• Systematic encoding: c(x) = x^n−k·m(x) + remainder of [x^n−k·m(x) ÷ g(x)] - shift the message left by n−k, divide, append the remainder as parity.
• Decoding: the syndrome is the remainder of r(x) ÷ g(x); zero means accepted. Hardware is a simple shift register with XOR taps - cheap in VLSI, which is why cyclic codes dominate.
• CRC is cyclic coding used for detection only: a 16- or 32-bit remainder appended as a frame check sequence. CRC-32 (Ethernet), CRC-16-CCITT (HDLC), CRC-24 in 5G NR transport blocks. A CRC of r bits detects all bursts up to r bits, all single/double-bit errors and all odd-weight errors with a suitable generator.
• BCH codes: cyclic, multiple-error correcting, with designed distance - flexible (n, k, t). Used as an outer code in DVB-S2.
• Reed–Solomon (RS): non-binary, symbols from GF(2^m); RS(n, k) corrects t = (n − k)/2 symbol errors, hence excellent against bursts. RS(255,223) and RS(255,239) in deep-space/CCSDS and optical links, RS(204,188) in DVB-T/DVB-C, and RS inside every QR code (including UPI payment QRs, which stay scannable when partly damaged).
• Interleaving spreads a burst across many codewords so each sees only a few random errors; block and convolutional interleavers are standard in GSM, CD audio (CIRC) and satellite links. Cost: added latency.

Convolutional codes and capacity-approaching codes

• A convolutional encoder has memory: output depends on the current input and K−1 previous bits. Described by rate k/n, constraint length K, and generator polynomials in octal (e.g. rate 1/2, K = 3, generators (7, 5)₈).
• Representations: generator/impulse response, state diagram, tree diagram and trellis (the one used for decoding). Number of states = 2^K−1.
• Free distance d_free governs performance - the analogue of d_min for block codes.
• Viterbi decoding: maximum-likelihood decoding on the trellis - at each node keep only the surviving path of least path metric, then trace back. Complexity grows as 2^K−1, so K ≈ 7–9 in practice. Soft-decision Viterbi (using analogue confidence, Euclidean metric) gains about 2 dB over hard-decision (Hamming metric).
• Sequential decoding (Fano, stack) suits large K but has variable decoding time; tail biting avoids flush bits and is used in LTE control channels.
• Puncturing deletes selected coded bits to raise the rate (1/2 → 2/3, 3/4) using the same encoder and decoder - standard in Wi-Fi and satellite modems.
• Concatenated coding: outer RS + interleaver + inner convolutional - the classic CCSDS/DVB-S arrangement used for satellite telemetry including ISRO missions.
• Turbo codes (1993): two recursive systematic convolutional encoders separated by a pseudo-random interleaver, decoded iteratively with soft-in soft-out (BCJR/MAP) decoders exchanging extrinsic information. Within ~0.5 dB of the Shannon limit. Rate-1/3 turbo code was the 3G/4G (LTE) data code.
• LDPC codes: very sparse parity-check matrix, decoded by iterative belief propagation (message passing) on a Tanner graph. Near-capacity, highly parallel. Used in 5G NR data channels (two base graphs with rate matching), Wi-Fi 6, DVB-S2 DTH and 10G Ethernet.
• Polar codes (Arıkan, 2009): channel polarisation makes some synthetic sub-channels nearly noiseless and others nearly useless; information is placed on the good ones, frozen bits on the rest. Provably capacity-achieving; decoded by successive cancellation list decoding with CRC aid. Used for 5G NR control channels (PDCCH, PBCH).
• ARQ and hybrid ARQ: detection plus retransmission - stop-and-wait, go-back-N, selective repeat. HARQ (used in LTE and 5G NR) combines FEC with retransmission, either chase combining (resend the same bits) or incremental redundancy (send extra parity); soft bits from failed attempts are retained and combined.
• Coding gain is the dB saving in Eb/N₀ for the same BER versus uncoded transmission, after accounting for the bandwidth expansion 1/R.

Key points

• Entropy H(X) - average bits of information per symbol; the floor for lossless compression.
• Maximum entropy - log₂M bits, reached only when all M symbols are equally likely.
• Information rate - R = r·H bits/s; reliable transmission needs R < C.
• Kraft inequality - Σ2^−nᵢ ≤ 1 is the test for the existence of a prefix code.
• Huffman code - optimal prefix code; efficiency H/L, always ≥ H/(H+1).
• Mutual information - I(X;Y) = H(X) − H(X|Y); information actually delivered by the channel.
• Capacity - C = max I(X;Y); BSC: 1 − H(p); BEC: 1 − ε; AWGN: B log₂(1+S/N).
• BSC at p = 0.5 - capacity zero, the worst possible channel; p = 1 is as good as p = 0.
• Shannon limit - Eb/N₀ ≥ −1.59 dB for error-free communication, at vanishing spectral efficiency.
• Code rate - R = k/n; lower rate means more protection and more bandwidth or lower throughput.
• d_min - detects d_min − 1 errors, corrects ⌊(d_min−1)/2⌋; equals the minimum non-zero codeword weight for linear codes.
• Syndrome - s = rHᵀ depends only on the error pattern, not the transmitted codeword.
• Hamming code - (2^m−1, 2^m−1−m), d_min = 3, perfect single-error-correcting code.
• Cyclic code - g(x) must divide xⁿ+1; encode/decode with shift registers; CRC is its detection-only form.
• Reed–Solomon - non-binary and MDS; corrects (n−k)/2 symbol errors, so it is the burst-error workhorse.
• Viterbi - maximum-likelihood trellis decoding; soft decision buys about 2 dB over hard decision.
• Turbo / LDPC / polar - iterative, near-capacity codes: LTE used turbo; 5G NR uses LDPC for data and polar for control.
• Interleaving - converts burst errors into scattered random errors at the cost of latency.

Formulas and examples

Example 1 - entropy, Huffman and efficiency. Source with p = {0.4, 0.2, 0.2, 0.1, 0.1}, 1,000 symbols/s.

• H = 0.4(1.3219) + 2×0.2(2.3219) + 2×0.1(3.3219) = 0.5288 + 0.9288 + 0.6644 = 2.1219 bits/symbol.
• Huffman: merge 0.1+0.1 = 0.2; merge the two 0.2s = 0.4; merge 0.2+0.4 = 0.6; merge 0.6+0.4 = 1.0. Lengths: 2, 2, 2, 3, 3.
• L = 0.4(2) + 0.2(2) + 0.2(2) + 0.1(3) + 0.1(3) = 0.8+0.4+0.4+0.3+0.3 = 2.2 bits/symbol.
• Check Kraft: 3(2⁻²) + 2(2⁻³) = 0.75 + 0.25 = 1 ✓ (a complete code).
• Efficiency η = 2.1219/2.2 = 96.45%, redundancy 3.55%. Information rate R = 1,000 × 2.1219 = 2,122 bits/s; the Huffman stream needs 2,200 bits/s. (Fixed-length coding would need 3 bits, i.e. 3,000 bits/s.)

Example 2 - BSC capacity. p = 0.1, 1,000 binary symbols/s.

• H(0.1) = 0.1(3.3219) + 0.9(0.1520) = 0.3322 + 0.1368 = 0.4690.
• C = 1 − 0.4690 = 0.531 bits/use → 531 bits/s. Any source rate below 531 bits/s can be made arbitrarily reliable; above it, cannot.
• If p rose to 0.5, H(0.5) = 1 and C = 0 - no coding scheme helps.

Example 3 - Shannon–Hartley. (a) A 3.1 kHz telephone channel at 30 dB SNR: S/N = 1000, C = 3100 × log₂(1001) = 3100 × 9.967 = 30.9 kbit/s - which is why 33.6 kbit/s was the practical analogue-modem ceiling. (b) A 20 MHz LTE carrier at 20 dB SNR: C = 20×10⁶ × log₂(101) = 20×10⁶ × 6.658 = 133 Mbit/s. Doubling the bandwidth doubles C; doubling the power adds only about 1 bit/s/Hz at high SNR.

Example 4 - Hamming (7,4): encoding, syndrome and gain. G = [I₄ | P] with P rows 110, 011, 111, 101.

• Message m = 1011 → parity = row1 ⊕ row3 ⊕ row4 = 110 ⊕ 111 ⊕ 101 = 100. Codeword c = 1011100.
• Suppose bit 2 flips: r = 1111100. Syndrome s = rHᵀ = row 2 of P = 011, which points at position 2 → flip it back to recover 1011100.
• Rate = 4/7 = 0.571; d_min = 3 → corrects 1 error, detects 2.
• On a BSC with p = 0.01: block error after decoding = 1 − [(0.99)⁷ + 7(0.01)(0.99)⁶] = 1 − [0.93207 + 0.06590] = 2.03×10⁻³, against an uncoded 4-bit block error of 1 − (0.99)⁴ = 3.94×10⁻² - about 19× better for 75% overhead.

Example 5 - cyclic code and convolutional encoding.

• (7,4) cyclic code, g(x) = x³+x+1 (1011), message 1101. Shift: 1101000. Divide by 1011 mod 2 → remainder 001. Codeword = 1101001. A receiver dividing 1101001 by 1011 gets remainder 0 and accepts it.
• Rate-1/2, K = 3 convolutional encoder, g₁ = 111, g₂ = 101, input 1011 plus two flush zeros, starting in state 00:

in  state  v1 v2   next
1    00    1  1     10
0    10    1  0     01
1    01    0  0     10
1    10    0  1     11
0    11    0  1     01
0    01    1  1     00
output = 11 10 00 01 01 11   (12 bits for 4 information bits)

Where it is used

• Mobile networks: LDPC and polar encoder/decoder design and conformance testing at Qualcomm India, Samsung R&D Bengaluru/Noida, MediaTek, Nokia and Ericsson India; C-DOT and Tejas Networks for the indigenous 4G/5G stack deployed by BSNL.
• Satellite and space: ISRO telemetry and telecommand follow CCSDS practice - concatenated RS + convolutional, and turbo/LDPC on newer links; DTH platforms in India broadcast on DVB-S2 (LDPC + BCH).
• Storage and memory: BCH and LDPC engines inside SSD/NAND controllers, RS in optical discs, SECDED in server ECC DRAM - a core area for VLSI design roles.
• Everyday data integrity: CRC in Ethernet, Wi-Fi, USB and CAN bus (automotive ECUs); Reed–Solomon inside UPI/Bharat QR codes, which keeps them readable when smudged or partly covered.
• Compression products: Huffman and arithmetic coding inside JPEG, MP3, H.264/HEVC and ZIP - relevant to media/codec teams and to any embedded firmware that stores data in flash.
• Job roles: physical-layer/DSP engineer, FPGA-ASIC digital design, modem firmware, VLSI verification, and R&D at DRDO/LRDE and IITs working on channel coding for defence radios.

Interview questions

• Q: What exactly does entropy measure? A: The average information content per symbol of a source, in bits; equivalently the minimum average number of bits needed to represent it losslessly.
• Q: When is the entropy of a discrete source maximum? A: When all symbols are equiprobable, giving H = log₂M; any skew in probabilities reduces it.
• Q: Why is the capacity of a BSC zero at p = 0.5 but maximum at p = 1? A: At p = 0.5 the output is statistically independent of the input, so no information passes; at p = 1 every bit is inverted deterministically, so the receiver just complements it.
• Q: A channel has capacity 1 Mbit/s and you want to send 1.2 Mbit/s reliably. What can coding do? A: Nothing - above capacity the error probability is bounded away from zero, no matter how clever the code.
• Q: Is Huffman coding always optimal? A: It is optimal among symbol-by-symbol prefix codes for a known distribution, but it wastes up to one bit per symbol because lengths are integers; arithmetic coding or coding an extended source does better.
• Q: What is the use of the syndrome? A: It depends only on the error pattern, not the transmitted codeword, so one small lookup table maps syndromes to correctable error patterns regardless of which message was sent.
• Q: How are d_min, detection and correction related? A: A code detects up to d_min − 1 errors and corrects up to ⌊(d_min − 1)/2⌋; you can trade correction for extra detection.
• Q: Why does Reed–Solomon handle burst errors so well? A: It works on multi-bit symbols, so a burst of several consecutive bit errors usually corrupts only one or two symbols, well inside its symbol-error correcting ability.
• Q: What does interleaving achieve, and what does it cost? A: It scatters a burst across many codewords so each sees only random errors; the cost is buffering delay, which matters in voice and URLLC links.
• Q: Difference between soft-decision and hard-decision decoding? A: Hard decision quantises each received sample to 0 or 1 before decoding; soft decision keeps reliability information and uses a Euclidean metric, buying roughly 2 dB of coding gain.
• Q: Why did 5G NR adopt LDPC for data but polar for control? A: LDPC suits long blocks with high throughput and easy rate matching; polar codes perform better at the very short, low-rate block lengths of control channels and work well with CRC-aided list decoding.
• Q: What is the Shannon limit and can we beat it? A: Eb/N₀ = −1.59 dB is the absolute minimum for error-free communication over AWGN; it cannot be beaten, and turbo/LDPC codes merely approach it to within a fraction of a dB.

Common mistakes

• Using S/N in dB directly inside the Shannon–Hartley formula instead of converting to a power ratio first.
• Writing entropy with log₁₀ or ln and reporting the answer as "bits" - log₂ gives bits, ln gives nats, log₁₀ gives hartleys.
• Confusing information rate R = r·H (bits/s) with the symbol rate r, or with code rate k/n.
• Taking d_min as the minimum distance between *message* words instead of the minimum non-zero codeword weight.
• Forgetting to append n−k zeros before dividing by g(x) in systematic cyclic encoding, or choosing a g(x) that does not divide xⁿ+1.
• Using N instead of K−1 for memory elements in a convolutional encoder, or forgetting the flush/tail bits, so the trellis never returns to the all-zero state.
• Claiming a code "corrects" errors when it only detects them - CRC has no correction capability and must be paired with ARQ.
• Treating capacity as achievable throughput in a real design; practical codes run at a rate below C with a finite BER target and finite latency.

Related topics

Random signals and noise analysis · Sampling and digital modulation · Noise in communication systems · Spread spectrum and CDMA · OFDM and MIMO · Telecommunication networks and switching