NME130/Information theory

From Murray Wiki
Jump to navigationJump to search


  • 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


  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


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


  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)


  • 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