2017/2018 Winter Semester
|When:||Wednesday 14:30–16:30 (lecture) 16:30–17:30 (recitation class)|
|Instructor:||Ronny Roth, Taub 637, ronny(at)cs.technion.ac.il|
|Teaching assistant:||Matthias Bonne, Taub 212, matt.technion.236309(at)gmail.com|
Error-correcting codes are methods for protecting transmitted or stored data against errors that are caused by factors such as noise, failing nodes in a network, physical defects in a storage medium, or malfunctioning of a memory device. Reed–Solomon codes and BCH codes are examples of error-correcting codes that are widely used in applications such as computer memories, disks, solid-state drives (flash memories), optical storage (DVD, Blu-ray), disk arrays (RAID), and bar codes (QR code, PDF417). Numerous other applications of error-correcting codes can be found in other branches of computer science.
The course provides the basics of the theory of error-correcting codes. The topics to be covered include the following:
- Basic concepts: error correction, error detection, and erasure correction
- Linear error-correcting codes; Hamming codes
- Introduction to finite fields
- Specific constructions: Reed–Solomon codes, BCH codes, and alternant codes
- Decoding algorithms
- Bounds on the parameters of error-correcting codes
Knowledge of basic terms in linear and modern algebra is assumed (but will nevertheless be recapped in the recitation class during the first few weeks of the semester). Examples of such terms include: vector spaces, groups, and rings.
- The q-ary symmetric channel
- Maximum-likelihood decoding
- Error correction, error detection, and erasure correction
- Linear codes
- Representation through generator and parity-check matrices
- Syndrome decoding
- Hamming codes
- Introduction to finite fields and double-error-correcting codes
- Irreducible polynomials
- Double-error-correcting codes
- Bounds on the parameters of codes
- The Singleton bound; MDS codes
- The Hamming sphere-packing bound; perfect codes
- The Gilbert–Varshamov bound
- Reed–Solomon and related codes
- Generalized Reed–Solomon (GRS) codes
- BCH codes and alternant codes as subfield subcodes of GRS codes
- Concatenated codes
- Decoding GRS codes using Euclid’s algorithm
- Structure of finite fields and cyclic codes
- Minimal polynomials
- Cyclic codes
- BCH codes as cyclic codes
- The BCH bound
- R.M. Roth,
Introduction to Coding Theory,
Cambridge University Press, Cambridge, UK, 2006.
Books for further reading
- R.E. Blahut,
Algebraic Codes for Data Transmission,
Cambridge University Press, Cambridge, UK, 2003.
- S. Lin, D.J. Costello, Jr.,
Error Control Coding: Fundamentals and Applications,
Prentice-Hall, Upper Saddle River, New Jersey, 2004.
- F.J. MacWilliams, N.J.A. Sloane,
The Theory of Error-Correcting Codes,
North-Holland, Amsterdam, 1977.
- R.J. McEliece,
The Theory of Information and Coding,
Cambridge University Press, Cambridge, 2002.
- Soft copies of the course material (the first eight chapters of the textbook) will be provided to students who are enrolled to the course. To obtain the material, please send an email to Matthias with the subject “textbook” and include in that email your name and ID number. Enrolled students will be mailed back a pdf copy of the relevant chapters of the textbook.
Topics covered in the course are as follows:
- Introduction (25 Oct through 08 Nov 17)
- Linear codes (08 and 15 Nov 17)
- Introduction to finite fields (15 through 29 Nov 17)
- Bounds on the parameters of codes (29 Nov and 06 Dec 17)
- GRS and related codes (06 and 13 Dec 17)
- Decoding of GRS codes (13 and 27 Dec 17)
- Structure of finite fields (03 and 10 Jan 18)
- Cyclic codes (starting 10 Jan 18)
- Homework assignment 1:
Problems 1.1 (optional), 1.10, 3.3, 3.13, A.1 (parts 1–3), A.2 (part 1).
Due date: 23 Nov 2017.
- Homework assignment 2:
Problems 2.4, 2.6, 2.7, 2.13 (parts 5–6 are optional), 2.14.
Due date: 07 Dec 2017.
- Homework assignment 3:
Problems 3.4, 3.5, 3.22, 3.23 (parts 1–4), 3.24 (parts 1–2).
Due date: 28 Dec 2017.
- Homework assignment 4:
Problems 3.32, 3.33 (optional), 3.34 (optional), 4.8, 4.9, 4.13 (parts 1–3), 4.14.
Due date: 11 Jan 2018.
- Homework assignment 5:
Problems 5.2, 6.3, 6.11, 7.11, 8.11 (parts 1–4).
Due date: 25 Jan 2018.
- There will be five home assignments which will constitute 20% of the final grade. The remaining 80% will be determined by a final exam.