# NME130/Information theory

From MurrayWiki

### Michelle

- Tried to figure out what people wanted to see
- Decided that the way to go is to pull out a small piece that can be done in its entirety, but gives a sense of the point of view

#### Outline

- Assumptions underlying information theory
- Convenient versus critical

- Heart of the matter
- Long sequences of random variables are "easy" to predict (weak law, AEP)
- This piece current takes 3.5 lectures * 1.5 hours = ~ 6 hours

- Example: achievability (in sketch form) of the channel coding theorem
- Can probably be done in 1-2 lectures of 1.5 hours each

- Long sequences of random variables are "easy" to predict (weak law, AEP)

- Entropy will have be introduced, but probably not entropy rate
- Should be enough to touch on Bode/Shannon pictures
- Should also be able to talk about stochastic versus worst case

### Tracey

#### Error correction coding

- Coverage

- High level concetnrs, framework, assumptions
- Connections with other fields
- Details of a few illustrative results

- Avoid excessive dpulication of material covered in EE 127, 127

- Want to impart a basic knowledge of what are some connections between them and other fields, so that students will have a basis for deciding if they want to go deeper

#### Topics

- Framework and assumptions (1 hr)
- Differences between information theory and coding theory
- Differences between stoachastic and adversarial noise
- Block length, complexity, etc (coding theory works with constraints, etc)

- Upper bounds on codes (2 hr)
- Classes of codes: random codes, algebraic coes, sparse graph codes (2-3 hr)
- Decoding techniques (algebraic, sum product algorithm aand special cases, LP decoding) (2-3hr)
- Networking coding and its relation to network information theory, coding thoery and networking optimization (2-3 hr)
- Connections with other fields (learning, cryptography) (2-3 hr)

### Discussion

- Linkage to optimization
- How could we tune optimization or information theory to streamline the two
- In information theory, we engineer the optimization problem so that certain techniques will be able to find a solution
- So: talk more about the
*design*of optimization problems (could also hit mechanism design, protocol design)

- Another approach: set a big goal that requires all of the tools
- Eg, design of a large network
- Layer as optimization versus information theory

- Eg, design of a large network

- Linkages to CS
- Chernoff theory
- Could also link to ACM/EE 116a

- "Shape" of the course
- There are conceptual things that take a while to sink in
- Probably better spread out, but could be taught quickly

- Some key concepts
- The notion of typical (and how to think about that)
- Design oriented optimization

- Textbooks
- Cover and Thomas for the information theory part
- McEliece, McKay, A & Richardson for coding theory part