August 2024
This course is an introduction to algebraic methods for devising error-correcting codes. These codes are used, for example, in satellite broadcasts, CD/DVD/Blu-ray players, memory chips, two-dimensional bar codes (including QR codes), and digital video broadcasting. The mathematical ingredients for the course are linear algebra, elementary number theory (integers modulo n and congruences), and abstract algebra (groups, rings, ideals, and finite fields). The necessary abstract algebra will be introduced as needed.
Learning outcomes
On successful completion of this course, students will be able to:
- Demonstrate a fundamental understanding of the binary symmetric channel, decoding strategies, and the challenges with designing good codes;
- Construct codes, and devise efficient encoding and decoding algorithms for them as a means of gaining exposure to the applications of linear algebra and abstract algebra;
- Analyze the properties of major families of algebraic codes including linear codes, Hamming codes, Golay codes, cyclic codes, BCH codes, and Reed-Solomon codes.
Bilibili lectures
Full Playlist (thanks to Zijie Lu and Brandon Shi for uploading the videos to Bilibili)
Short introduction to coding theory
If would like a short introduction to coding theory, it will suffice to view V0, V1a-V1c (Fundamentals), and V3a-V3f (Linear codes).
YouTube Lectures
V0: Introduction
V1: Fundamentals
- V1a: Basic definitions and concepts
- V1b: Decoding strategies
- V1c: Error correcting and detecting capabilities of a code
V2: Finite Fields
- V2a: Introduction to finite fields
- V2b: Non-existence of finite fields
- V2c: Existence of finite fields
- V2d: Construction of finite fields
- V2e: Properties of finite fields
V3: Linear Codes
- V3a: Introduction
- V3b: Dual code and parity-check matrices
- V3c: Distance of a linear code
- V3d: Hamming codes
- V3e: Perfect codes
- V3f: Syndrome decoding
V4: Golay Codes
V5: Cyclic Codes
- V5a: Introduction
- V5b: Ideals of R=F[x]/(xn -1)
- V5c: Dimension and GM of a cyclic code
- V5d: The dual code of a cyclic code
- V5e: Computing syndromes
- V5f: Burst error correction
- V5g: Decoding algorithm for cyclic burst error correcting codes
V6: BCH Codes
- V6a: Minimal polynomials
- V6b: Computing minimal polynomials
- V6c: Factoring xn-1 over GF(q) [Part 1]
- V6d: Factoring xn-1 over GF(q) [Part 2]
- V6e: BCH codes: definition
- V6f: BCH bound
- V6g: Examples of BCH codes
V7: Reed-Solomon (RS) Codes
- V7a: Introduction
- V7b: Alternative view of narrow-sense RS codes
- V7c: Berlekamp-Welch decoding algorithm
V8: Wrap-Up
V9: Linear Algebra Review
Additional Material
Lecture slides
- V0: Introduction
- V1: Fundamentals
- V2: Finite fields
- V3: Linear codes
- V4: Golay codes
- V5: Cyclic codes
- V6: BCH codes
- V7: Reed-Solomon codes
- V8: Wrap-up
- V9: Linear algebra review
References
- An Introduction to Error Correcting Codes (Vanstone and van Oorschot).
- Modern Coding Theory (Richardson and Urbanke).
- Essential Coding Theory (Guruswami, Rudra and Sudan).
- Algebraic Coding Theory (lectures by Mary Wootters).