# NME130/Information theory

### 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

1. Assumptions underlying information theory
• Convenient versus critical
2. 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
• 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

1. Coverage
• High level concetnrs, framework, assumptions
• Connections with other fields
• Details of a few illustrative results
1. 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

1. 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)
2. Upper bounds on codes (2 hr)
3. Classes of codes: random codes, algebraic coes, sparse graph codes (2-3 hr)
4. Decoding techniques (algebraic, sum product algorithm aand special cases, LP decoding) (2-3hr)
5. Networking coding and its relation to network information theory, coding thoery and networking optimization (2-3 hr)
6. Connections with other fields (learning, cryptography) (2-3 hr)

### Discussion

• 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