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

• 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

• 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