Coding theory designs codes to detect and correct errors over noisy channels. Core ideas include Hamming distance, redundancy vs rate, and fundamental bounds relating code length, alphabet, distance, and size.
Details
Concepts
Block codes over alphabet Σ with length n, size M, minimum distance d; capability: detect d−1 errors, correct ⌊(d−1)/2⌋.
Hamming distance/balls; Hamming bound (sphere packing) and Singleton bound; rate R = (log_2 M)/n.
Linear codes over GF(q): k-dimensional subspace; parameters [n, k, d]; generator matrix G, parity-check matrix H.
Hamming codes: perfect single-error-correcting codes; BCH and Reed–Solomon codes (MDS) for burst errors and erasures.
Decoding: syndrome decoding for linear codes; Berlekamp–Massey/Euclid for RS/BCH; soft decoding (Viterbi for convolutional codes LDPC/Turbo iterative).
Applications: storage (RAID/erasure coding), communications, QR codes, distributed systems, CDNs.
Exercises
Hands-on
For a code with minimum distance d, prove it can correct t = ⌊(d−1)/2⌋ errors.
Construct a [7,4,3] Hamming code: give G and H, encode a message, and decode from a 1-bit error.
Show that Reed–Solomon codes meet the Singleton bound (MDS) and compute parameters for given n,k over GF(2^m).