Syllabus
Week 1
Intro - some examples of codes, basic probability
- 9/24: Lecture 1, Some basic definitions and motivation, source coding vs. channel coding
- 9/26: Lecture 2, Intro to moise models (binary symmetric channel) error correction, statement of Noisy Coding Theorem
Homework 1 due 9/29: click here
Week 2
Source coding intro - instantaneous and uniquely decodable codes
- 9/29: Lecture 3, Uniquely decodable codes and instantaneous codes,
decoding trees, and Kraft's Theorem for instantaneous codes
- 10/1: Lecture 4: Kraft's Theorem (cont.) and McMillan's Ineq., Shannon-Fano Coding, Huffman coding
- 10/3 *** Rosh Hashannah - no class ***
Homework 2 due 10/6: click here
Week 3
Huffman coding, JPEG, MPEG, The Noiseless Coding Theorem
- 10/6: Lecture 5: Proof of optimality of Huffman coding
- 10/8: Lecture 6: JPEG, MPEG
- 10/10: Lecture 7: The Noiseless Coding Theorem
Homework 3 due 10/13: click here
Week 4
Markov sources, Arithmetic coding, Lempel-Ziv coding
- 10/13: Lecture 8: Markov sources - conditional information, adjoint source
- 10/15: Lecture 9: Noiseless coding theorem for Markov sources
- 10/17: Lecture 10: Arithmetic coding, Lempel-Ziv coding
Homework 4 due 10/20: click here
Week 5
Equivocation, Mutual Information
- 10/20: Lecture 11: Equivocation
- 10/22: Lecture 12: Mutual Information
- 10/24: Lecture 13: Mutual Information, Channel Capacity, Conditional Max-likelihood decoding
Homework 5 due 10/27: click here
Week 6
Shannon's Noisy Coding Theorem (BSC case), Error correction
- 10/27: Lecture 14: Max-likelihood decoding, Shannon-Fano bound
- 10/29: Lecture 15: Rate, Hamming distance, NCT
- 10/30: Lecture 16: Proof of NCT (random codes)
Homework 6 due 11/3: click here
Week 7
Linear Codes - Introduction
- 11/3: Lecture 17: spherical designs, linear codes intro
- 11/5: Lecture 18: generator matrix, parity check matrix
- 11/7: Lecture 19: standard array, coset leaders, decoding
Homework 7 due 11/10: click here
Week 8
Linear Codes, Cyclic Codes
- 11/10: Lecture 20: Syndromes, standard forms
- 11/12: Lecture 21: Cyclic codes, generator polynomials
- 11/14: Lecture 22: More on generator polynomials, check polynomials
Homework 8 due 11/17: click here
Week 9
The group of a code, quadratic residue codes
- 11/17: Lecture 23: Decoding of cyclic codes
- 11/19: Lecture 24: The group of a code
- 11/21: Lecture 25: Quadratic residue codes
Homework 9 due 11/24: click here
Week 10
Finish up QR codes
- 11/24: Lecture 26: More quadratic residue codes, arithmetic over finite fields
- 11/26 T-giving No class
- 11/28 T-giving No class
Week 11
Expander codes, student lecture on cryptography
- 12/1: Lecture 27: Expander Codes
- 12/3: Lecture 28: Shannon, Info Theory and Cryptography (C. Paya)