CO 331 - Winter 2011

Coding Theory

Instructor: David Jao
Office hours: Mon. & Wed. 2-3

Teaching Assistant: Andrew Brown, a29brown, DC 3144
Office hours: Tue. & Thurs. 2:30-3:30 (effective Feb. 15)

Course materials

• Course outline (https:../../wiki/images/a/a1/Co331-2011-outline.pdf)
• Textbook: An Introduction to Error Correcting Codes with Applications, by S. A. Vanstone and P. C. van Oorschot.
• Lecture notes (https:../../wiki/images/b/bc/Co331-2011-notes.pdf) (updated Apr. 11 with examples in last two sections)

Exams

• The midterm examination is scheduled for Tuesday, March 8 from 4:30 to 6:30 pm in MC 4058.
  • Past midterm problems (https:../../wiki/images/8/89/Co331-midterm-problems.pdf)
• The final examination is scheduled for Wednesday, April 13 from 12:30 to 3:00 pm in RCH 112.
  • Past final exam problems (https:../../wiki/images/7/76/Co331-sample-final.pdf)
  • Practice problems from the textbook:
    • 1.4, 1.13, 1.14, 1.16, 1.17, 1.18
    • 2.1, 2.2, 2.6
    • 3.2(a), 3.3, 3.4, 3.5, 3.11, 3.16, 3.23, 3.25, 3.29, 3.34, 3.38, 3.41, 3.42, 3.46, 3.52, 3.68, 3.69
    • 4.12, 4.14, 4.15, 4.24
    • 5.3, 5.5, 5.8, 5.11, 5.15, 5.22, 5.25, 5.35, 5.36, 5.37, 5.38, 5.40, 5.46, 5.54
    • 6.7, 6.11, 6.21, 6.25

Assignments

• Assignment 1 (https:../../wiki/images/4/4d/Co331-a1-2011.pdf) (due January 21)
  • Solutions (https:../../wiki/images/0/04/Co331-s1-2011.pdf) for assignment 1
• Assignment 2 (https:../../wiki/images/9/99/Co331-a2-2011.pdf) (due February 11)
  • Solutions (https:../../wiki/images/7/7f/Co331-s2-2011.pdf) for assignment 2
• Assignment 3 (https:../../wiki/images/c/ce/Co331-a3-2011.pdf) (due March 4)
  • Solutions (https:../../wiki/images/c/cb/Co331-s3-2011.pdf) for assignment 3
• Assignment 4 (https:../../wiki/images/8/8b/Co331-a4-2011.pdf) (due March 18)
  • Solutions (https:../../wiki/images/2/2c/Co331-s4-2011.pdf) for assignment 4
• Assignment 5 (https:../../wiki/images/8/89/Co331-a5-2011.pdf) (due April 1)
  • Solutions (https:../../wiki/images/b/b1/Co331-s5-2011.pdf) for assignment 5

Lectures

• Jan. 5 - Introduction (book: § 1.1-1.2; notes: § 0)
• Jan. 7 - Basic definitions (book: § 1.3; notes: § 1.1-1.2)
• Jan. 10 - Decoding strategies (book: § 1.3; notes: § 1.3-1.4)
• Jan. 12 - IMLD and MED, error correction and detection (book: § 1.3; notes: § 1.4-1.5)
• Jan. 14 - Error correction; Shannon's noisy channel coding theorem (book: § 1.3-1.4; notes: § 1.5-1.6)
• Jan. 17 - Introduction to finite fields (book: § 2.1; notes: § 2.1)
• Jan. 19 - Classification of finite fields (book: § 2.1; notes: § 2.1-2.2)
• Jan. 21 - Polynomial rings (book: § 2.1-2.2; notes: § 2.3-2.5)
• Jan. 24 - Finite fields (book: § 2.2 & 2.5; notes: § 2.5-2.6)
• Jan. 26 - Orders and generators (book: § 2.3; notes: § 2.7)
• Jan. 28 - Linear codes (book: § 3.1-3.2; notes: § 3.1)
• Jan. 31 - Dual codes (book: § 3.2-3.3; notes: § 3.2)
• Feb. 2 - Hamming codes (book: § 3.4; notes: § 3.3)
• Feb. 4 - Decoding single-error correcting codes (book: § 3.5; notes: § 3.4)
• Feb. 7 - Group theory (book: § 3.6; notes: § 3.5.1)
• Feb. 9 - Standard array decoding (book: § 3.6; notes: § 3.5.2)
• Feb. 11 - Syndrome decoding (book: § 3.6; notes: § 3.5.3)
• Feb. 14 - Decoding the extended binary Golay code (book: § 4.3; notes: § 4)
• Feb. 16 - Cyclic subspaces (book: § 5.1-5.3; notes: § 5.1)
• Feb. 18 - Generator matrices for cyclic subspaces (book: § 5.4; notes: § 5.2)
• Feb. 28 - The dual code of a cyclic code (book: § 5.4; notes: § 5.2)
• Mar. 2 - Computing syndromes for cyclic codes (book: § 5.6; notes: § 5.3)
• Mar. 4 - Burst error correction (book: § 5.7; notes: § 5.4)
• Mar. 9 - Error trapping (book: § 5.6; notes: § 5.5)
• Mar. 11 - Interleaving (book: § 7.5; notes: § 5.6)
• Mar. 14 - Minimal polynomials (book: § 2.4; notes: § 6.1)
• Mar. 16 - Constructing minimal polynomials (book: § 2.4; notes: § 6.1)
• Mar. 18 - Factoring xⁿ − 1 (book: § 5.8; notes: § 6.2)
• Mar. 21 - BCH codes (book: § 6.1-6.2; notes: § 6.3)
• Mar. 23 - BCH bound (book: § 6.2; notes: § 6.4)
• Mar. 25 - C₁₅ decoding algorithm (book: N/A; notes: § 6.5)
• Mar. 28 - BCH decoding algorithm (book: § 6.4; notes: § 6.6)
• Mar. 30 - Proof of BCH decoding algorithm (book: § 6.4; notes: § 6.6)
• Apr. 1 - Reed Solomon codes, erasures, CD audio (book: § 7.2, 7.3, 7.6; notes: N/A)