#

date

Topics covered; Sections in Roman, Coding Theory

HW due dates

1

Thur. 1/9

1.0 History: Shannon, Bell Labs, 1.1 Overview of Shannon theory; Channels: Source coding and Channel coding,

2

Tues. 1/14

2.1 General coding problem: Source and channel coding, 2.2 Motivating Example: Hamming [7,4, 3]- linear code; 

2.3 Error probabilities for Hamming code, 2.4 Information sources

3

Thur. 1/16

3.1 Discrete probability distributions, bivariate distributions, 3.2 joint probabilities, marginal probabilities, conditional probabilities, 

3.3 Weatherman example

4

Tues. 1/21

4.0 Entropy of source [Sect. 1.1], 4.1 Basic entropy inequalities [Sect. 1.2] 

4.2 Binomial coefficients and entropy [Sect. 1.2]

HW#1 due Tues. 1/21

5

Thur. 1/23

5.0 Entropy properties (cont'd) [Sec. 1.2], 5.1 Binomial coefficients and entropy (cont'd), 

5.2 Shape of binomial distribution, 5.3 Entropy as an expected value [Sec. 1.3]

[5b]

Tues. 1/28

Class Cancelled-Weather

6

Thur. 1/30

6.0 Convexity down of entropy function [Sec. 1.3], 6.1 Source coding: compression [Chap. 2], 

6.2 Variable length codes, uniquely decipherable codes [Sec. 2.1], 6.3 Kraft Inequality Theorem (necessity) [Sec. 2.1]

7

Tues. 2/4

7.0 Instantaneous codes [Sec. 2.1], 7.1 Prefix tree for prefix code, 7.2 Kraft's theorem (sufficiency), 

7.3 Entropy lower bound for average length [Sec 2.3], 7.4 Jensen's convexity inequality (started)

HW#2 due Tues. 2/4

8

Thur. 2/6

8.0 Jensen's convexity inequality (handout), 8.0b Noiseless codes and trees, 

8.1 Huffman coding (N=2) example [Sec. 2.2], 8.2 Huffman coding algorithm (Thm. 2.2.2), proof by trees

9

Tues. 2/11

9.0 Huffmand code, base 3 example [Sec. 2.2], 9.1 Noiseless coding theorem [Sec. 2.3], 

9.2 Extensions of source thm [Sec. 2.3], 9.3 Lempel-Ziv encoding [with handout],

10

Thur. 2/13

10.0 Source coding [Noiseless coding]-review of Chap. 2, 10.1 Discrete memoryless channel, channel matrix [Sec. 3.1] 

10.2 Channel distribution: conditional entropy, 10.3 Mutual information I(X; Y); channel capacity [Sec. 3.2], 

10.4 Types of channels [Sec. 3.1]

11

Tues. 2/18

11.0 Channels and three probability matrices, 11.0b Conditional entropy-review,

11.1 Types of channels [Sec. 3.1]: A. Row symm., column symm., symmetric C. lossless, D. noiseless, E. deterministic, 

11.2 Channel capacity [Sec. 3.2], Lossless capacity, deterministic capacity, 

11.3 Symmetric channel entropy theorem 3.2.3, capacity of binary symmetric channel

12

Thur. 2/20

12.0 Channel capacity-review Sec. 3.2, 12.0b Lossless, noiseless channel, 

12.1 Block codes and their rates [Sec. 3.3], 12.2 Channel transmission and decoding, 12.3 Decoder performance, 

12.4 Ideal observer decoder [Thm. 3.3.1, 3.3.2], 12.5 Noisy coding theorem statement

13

Tues. 2/25

13.0 Row Symmetric channel-review [Sec. 3.1] 13.1 Block codes [Sec. 3.3] 13.2 Decision scheme, error rate, 

13.3 Maximum likelihood decoding

HW#3 due Tues. 2/25

14

Thur. 2/27

14.0 Midterm Exam (in class) [Modified take-home exam, distributed Tues. 2/25]

3/1-3/8

Winter Recess

15

Tues. 3/11

15.1 Noisy coding theorem statement [Sect. 3.3], 15.2 Fano's Inequality [Sect. 3.3], 

15.3 Weak Converse noisy coding theorem [Sect 3.4]

16

Thurs. 3/13

16.1 Noisy Coding Theorem proof for BSC [Sect. 3.4] 16.2 Hamming balls,

16.3 Reduction max error to average error, 16.4 Proof of BSC Noisy coding theorem-average error case

17

Tues. 3/18

17.0a Fano inequality handout [Sect 3.3], 17.0b Noisy coding theorem review [Sect. 3.4] 

17.1 Minimum distance decoding [Sect. 4.2],

17.2 Error detection and correction, 17.3 Packing and covering radii, 17.4 Nonlinear code parameters

18

Thur. 3/20

18.0 General Existence Problems for Codes; [Sect. 4.2] 18.1 Maximal codes, maximal distance decoding [Sect. 4.2] 

18.2 Perfect codes, 18.3 Finite fields versus finite rings, 18.4 Equivalence of codes

19

Tues 3/25

19.0 Scalar multiple equivalence of codes [Sect. 4.3], 19.1 Linear codes, 19.2 cyclic codes, 

19.3 New codes from old ; A. Extending a code, B. Puncturing a code, C. Expunging a code, 

19.3 D. Augmenting a code, E. Shortening a code, F. Direct sum construction

20

Thur. 3/27

20.1 New codes from old. E. (u, u+v) construction [Sect. 4.3], 

20.2 Linear codes: generator matrices [Sect. 5.1] 

20.3 Dual of linear code: dual generator matrix

21

Tues. 4/1

21.0 Linear Codes, Dual Codes, [Sect. 5.1] 21.1 Parity Check Matrix and Minimal distance, 

21.2 Gilbert-Varshamov lower bound, 21.3 Syndrome decoding of linear code 

HW#4 due Tues. 4/1

22

Thur. 4/3

22.1 Hamming codes [Sect. 6.1], 22.2 Simplex Codes [Sect. 6.1], 

22.3 Majority logic decoding [Sect. 5.1], 22.4 Burst Errors [Sect. 5.1]

23

Tues. 4/8

23.0 Burst errors [Sect 5.1], 23.1 Binary Golay code G_{24} [Sect. 6.1],

23.2 Upper Bounds for nonlinear codes [Sect. 4.5], 23.3 Singleton Bound, 

23.4 Sphere-Packing Bound, 23.5 Plotkin Bound, 23.6 Example [n, d] = [8,5] for q=2.

24

Thur. 4/10

24.0 Homework 4 review, 24.1 Asymptotic bounds for codes [Sect. 4.5], 

24.2 Weight enumerators [Sect. 5.2], 24.3 MacWilliams identities (stated)

25

Tues. 4/15

(Harm Derksen) 25.1 MacWilliams Identity I [Sect. 5.2], 

25.2 Krawtchouk Polynomials, 25.3 MacWilliams Identity II, 25.3 Characters on F_q and V(n, F_q), 

26

Thur. 4/17

26.1 Weight enumerators of Perfect codes; Binary Golay code G_{23]. 

26.2 Characters and Linear Codes.

26.3 Proof of MacWilliams I  identity 

HW#5 due Thur. 4/17

27

Tues. 4/22

27.0 Information theory versus coding theory; entropy of source, of channel, of

coding and decoding, 27.1 MacWilliams identities: applications, 

27.2 Singleton bound [Sect. 5.3], 27.3 Minimum distance separable codes 

28

Fri. 4/25

Final Exam (4:00pm-6:00pm)