EE7330 Course Information

Table of Contents

Welcome to EE7330 (Network Information Theory). This is a follow-up course to EE 2340 (Information Sciences) and EE 5847 (Information theory). This course will cover the basic concepts of coding for reliable communication over noisy channels. While not a strict prerequisite, it would be helpful if you have already taken EE5390 (Source coding) and/or EE6317 (Channel coding).

This course covers the basics of the fundamental limits of communication over multiuser channels.

Most of our interaction will take place on Piazza and Google classroom. Please send me an email if you have not received an invite.

Classes will be online. We will try a mix of recorded videos (most videos are available here and on piazza), online discussion sessions (on piazza), and online lectures.

Prerequisites

1 Assessment (tentative):

Each student will be expected to

  • attend regular lectures
  • solve short in-class quizzes
  • participate in class and on piazza
  • solve homework assignments (collaboration is fine as long as it is explicitly declared, but you have to write the solutions in your own words)
  • scribe lecture notes
  • present a paper/do a project

2 Instructors:

Name Dr. Shashank Vatedka
Email shashankvatedka@ee.iith.ac.in
Name Dr. Lakshmi Prasad Natarajan
Email lakshminatarajan@ee.iith.ac.in

3 Class timings:

  • Slot: R (Tue 14:30-16:00h, Fri 16:00-17:30h)
  • Class venue: Google meet

4 Textbook and references:

Primarily, the material will be drawn from

  1. Network Information Theory, (NIT) Abbas El Gamal and Young Han Kim, Cambridge University Press. Most of the material will be drawn from this book.
  2. Lecture notes and slides, uploaded here and piazza.
  3. Elements of Information Theory, (EIT) Thomas M Cover and Joy A Thomas, second edition, Wiley inc. (Amazon link). Limited number of copies available in the university library. This book covers the prerequisites/basics needed for the course.

Other references:

  • Information theory: coding theorems for discrete memoryless systems, Imre Csiszar and Janos Korner. A slightly advanced textbook, but this is the foundation of all the results we will cover in this course.
  • Lecture notes on information theory, Yury Polyanskiy and Yihong Wu. An excellent resource, but follows a different approach that is more oriented towards considering delay constraints.
  • A student's guide to coding and information theory, Stefan Moser (amazon link).
  • "A mathematical theory of communication", Claude Shannon, Bell systems Tech Journal, 1948. The classic paper that started this field.
  • Information theory, inference, and learning algorithms, David MacKay (soft copy available for free on the author's website). A very nice book, but gives a very different flavour that what will be covered in the course. Suggested for additional reading.

Light reading on information theory:

5 Tentative list of topics and resources:

All video lectures can be accessed via this YouTube playlist.

5.0.1 Introduction (Class 1)

  • Motivation for network information process
  • Modeling, problem formulation, and flavour of the course
  • How joint coding helps: orthogonal versus non-orthogonal multiple access as an example

5.0.2 Mathematical preliminaries

  1. Limits (Class 1)
    • sequences, limit superior and inferior
    • existence of limits
  2. Convexity (Class 2)
    • convex, compact, bounded sets
    • convex functions
    • necessary and sufficient conditions for a function to be convex
  3. Probability (Class 2-3)
    • Bounds: union bound, Markov, Chebyshev inequalities, Chernoff bounds
    • convergence of sequences of random variables
    • weak law of large numbers
    • functional representation lemma

5.0.3 Fundamental information theoretic tools and lemmas

  1. Review of information theoretic quantities (Class 4-5)
    • Entropy, conditional entropy, KL divergence and mutual information
    • Continuous random variables, differential entropy and mutual information
    • Chain rules, data processing inequality
    • degraded channels and capacity
  2. Tools for proving converse results (Class 6-7)
    • Fano's inequality
    • Mrs Gerber's lemma
    • Maximum entropy and maximum differential entropy
    • Entropy power inequalities
    • Csiszar sum identity
    • Comments on more powerful techniques for proving converse results
  3. Tools for proving achievability results (Class 8-9)
    • Typical sequences, jointly typical sequences
    • Typical average lemma
    • Conditional typicality lemma
    • Joint typicality lemma
    • Properties of jointly typical sequences
    • Comments on more powerful tools for proving achievability results
  4. Discrete memoryless channels (Class 10-12)
    • Review of the channel coding theorem
    • Packing lemma and achievability proof of the channel coding theorem
    • Channels with input cost constraints
    • Gaussian channels, parallel Gaussian channels and waterfilling
  5. Source coding (Class 13-15)
    • Review of lossless source coding
    • The lossy source coding problem
    • Covering lemma and achievability proof of the lossy source coding theorem
    • Converse of the lossy source coding theorem
    • Special case of Gaussian lossy source coding with MSE distortion, joint source-channel coding
    • Source coding with side information, distributed source coding

5.0.4 Multiple access channels

  1. Discrete memoryless multiple access channels (Class 15-18)
    • Achievable rate region and capacity region
    • Simple bounds on capacity region
    • Time sharing and convexity of the capacity region
    • Single letter characterization of the capacity region
    • Proof of achievability
    • Proof of converse
    • Gaussian multiple access channels
  2. Gaussian fading channels and capacity (Class 19)
    • point-to-point slow and fast fading channels
    • Gaussian fading MAC

5.0.5 Broadcast channels (Class 20-24)

  • Discrete memoryless broadcast channels, degraded broadcast channels
  • Bounds on the capacity region
  • Superposition coding inner bound
  • Outer bounds on the capacity region
  • Gaussian broadcast channels

5.0.6 Other topics

  • Lattice codes, compute-and-forward
  • Information-theoretic security
  • Dirty paper coding

6 Topics for final paper/project presentation

You may work in groups of at most 2 people each You must work individually. You may either present a research paper (with proofs) or do a programming project, where you run simulations. The final deliverables will be as follows:

  1. A 2-3 page proposal report (deadline 15th Nov) which contains the following: formal/mathematical statement of the problem addressed, references, and a short summary of the results. While the report must be mathematical, you do not have to go into the technical details here.
  2. A final report (around 10 pages, written using LaTeX) describing, in your own words, the main contributions of the papers, main ideas/techniques used in the paper, why do you think this was an interesting paper, and what you learnt from it.
  3. A final presentation (roughly 20-25mins) with Q&A. Details regarding this will be shared later.

You may not copy text/proofs verbatim from the papers. It is important that you demonstrate an understanding of the results and techniques used in the papers.

Good sources for the latest work on network information theory can be found in the IEEE Transactions on Information Theory, IEEE Transactions on Communications, various IEEE conferences including the annual IEEE International Symposium on Information Theory (ISIT), Information Theory Workshop (ITW). Several good preprints are made available online on the Arxiv preprint server.

Here are some suggested topics. You are recommended to go through multiple topics before zeroing in on one:

6.1 Rate splitting multiple access

Unlike what we have seen in class, it is in fact possible to achieve the capacity region for DM-MACs using capacity-achieving codes designed for point-to-point channels. This is a technique called rate-splitting multiple access, and generalizes many known popular techniques such as SDMA, OMA, NOMA, etc. See this paper and this one.

6.2 Physical layer network coding

In class, we only see simple network topologies: corresponding to multiple access and broadcast channels. However, for multi-hop networks, things can get more complicated. For noiseless (and to some extent, noisy) networks with multiple sources and destinations with the connectivity described by a directed acyclic graph, network coding has been proposed as a solution that outperforms routing. For wireless multi-hop networks, there are similar analogues wherein intermediate nodes can compute linear combinations of messages of various users and forward these to the destination. If the destination has ``enough'' linear combinations, it can decode the desired messages. This is called physical layer network coding. See this paper and this one. See various references here for various communication-theoretic and implementation related papers on physical layer network coding.

6.3 Lattice codes

For binary-input discrete memoryless symmetric channels, it is known that linear codes can achieve capacity. For Gaussian channels, lattice codes (ref1, ref2) are the analogues of linear codes. Lattices codes achieve the capacity of the AWGN channel, are good covering codes, good packings, good quantizers, and can also be used for physical layer network coding. See this reference and this one.

Lattice codes are also used for interference channels, using a very interesting technique called interference alignment. See this paper and this one.

6.4 MIMO channels, multiuser diversity

For many channel coding problems, the relationship between reliability and rate shows a sharp transition: exponentially decaying probability of error is achievable at rates below capacity, whereas the probability of error approaches 1 (or at least bounded away from 0) at rates outside the capacity region. However for wireless fading channels with multiple antennas, the probability of error decays only polynomially in \(n\). There is a fundamental tradeoff between the exponent and the rate for asymptotic SNRs, and this is called the diversity-multiplexing tradeoff. See this paper and you may also look for related topics in this book. See this paper for the capacity of the MIMO channel.

6.5 Wireless network information flow

Finding the capacity region for a general multiuser channel is a very hard problem, and most of these are open. This paper gives a general approach by reducing a channel to a deterministic rate-limited network which can be analyzed easily.

6.6 Duality results

At times, finding the capacity regions of one class of channels can be hard, but this problem can be shown to be equivalent to finding the capacity region of another ``dual'' class of channels. See this paper and the references therein.

6.7 Multiterminal source coding problems

Suppose that two users observe correlated binary sequences. These need to be independently compressed and sent to a receiver, who wants to compute the bitwise XOR of the two. What are the best rates that can be achieved? See this seminal paper for hints. Obtaining a complete solution is a long-standing open problem.

There are other various problems in multiterminal source coding including this, this, and many others. You can take a look at the textbook and the associated references.

6.8 Wiretap channels and secrecy

Consider a broadcast channel where there is sender, a legitimate receiver and an eavesdropper. How do we ensure that legitimate receiver can recover the intended message while the eavesdropper can not? This is an old problem, but interest in this exploded in recent years. See this, this, and this paper for the original works. These results have been strengthened greatly in recent years. See this paper and this one.

7 General comments regarding presentations/reports

In addition to learning cool stuff in information theory, you should also learn to present your work. The final report and presentation are opportunities to develop your writing and presenting skills. It is absolutely essential that you be able to convey your ideas and thoughts clearly to another person. Here are some general comments on making good presentations:

  • Make sure that you acknowledge all the references/material that you used (papers/code/etc.) While it does not matter much for the purposes of this class, this is very important to keep in mind when you are delivering presentations at bigger venues
  • In a presentation, always introduce yourself and your team members/collaborators in the very beginning.
  • If much of the presentation is based on on one/two papers/references, explicitly state which references you are using in the first/second slide.
  • Avoid saying "We did this/we showed that…" when you are in fact talking about some other authors' work. Unless you have derived something/programmed something yourself, always say "they/the authors did/showed/observed that…"
  • A presentation/report is like telling a story: even before preparing the slides/document, imagine that you want to explain the work to a friend in 15-20 mins, identify exactly what you want to convey, and only then proceed.
  • Make sure that you explain the problem clearly.
  • When reading a paper, you should first fully understand what the problem is, what makes it challenging, and why it is worthwhile solving the problem. Then, you should identify what is new about the paper, and what the contributions are. To understand the rest of the paper, you should then try to understand the constructions/proof techniques/ideas.
  • There is no single best rule for presentations, but generally in any presentation, the viewer/audience's attention is maximum in the first 5-10 minutes and then gradually decreases. So it is helpful to get to the punchline in the first few minutes.
  • Citations should be treated differently in papers and slides. When you are making a reference to a particular paper/book/website (for e.g., when you say that result A can be found in paper B) in your slides, mention the paper/book/website as a footnote rather than saying [1], and putting the reference in the last slide. 
  • Do not put too much text on your slides. This is bad practice. Each slide should contain at most 3-5 points. You should absolutely avoid long sentences. 
  • Do not copy text directly from the paper.
  • Do not read out your slides word-to-word.
  • Similarly, do not put too many lemmas in a slide. Each slide should convey a single idea. Unless very important, do not put too much math/long derivations in a short presentation. It is more important to convey ideas/intuition. But at the same time, there should be a significant amount of technical content. It is therefore very useful to instead explain using examples.
  • Make sure that the fonts/diagrams/labels/plots are clear. Label all the axes on your plots.
  • Speak clearly, and make sure that the audio quality is fine. Check your mic volume. Do a couple of dry runs.
  • If you are using Google meet to record, then make sure that you "pin" the slides since meet might automatically switch displaying you/your icon instead of the presentation. 
  • Make sure that you check, and double check the slides and report for typos, technical and grammatical errors.

Author: Shashank Vatedka

Created: 2021-10-14 Thu 15:05