Lectures on Information Theory and Coding

Digital classroom blackboard illustrating key concepts of Information Theory and Coding, including Shannon's Information Theory, Source Coding, and Channel Coding, ideal for students and professionals seeking comprehensive lecture notes and foundational knowledge in Information Theory and Coding

Course Overview

Welcome to the « Lectures on Information-Theory and Coding » webpage, where we delve into the intricacies of information theory and coding, offering a comprehensive exploration of fundamental concepts and practical applications.

Part I — Information Theory for Discrete Alphabets

1. Coding Problem, Entropy and Mutual Information

Lecture 1 Coding Problem in Claude Shannon Information-Theory

🎬 Vidéo (FR) 📄 PDF
In Claude Shannon’s seminal work on information theory, the coding problem stands as a fundamental challenge in the efficient transmission of information. In this lecture on « Coding problem in Claude Shannon information-theory », we delve into the intricacies of this problem, exploring its components: source coding, channel coding, and the integration of both in joint source-channel coding, aiming to provide a comprehensive understanding of coding strategies in information theory.
  1. Coding Problem: At the heart of information theory lies the source-channel coding problem, a fundamental concept crucial in designing efficient communication systems. Within this realm, we delve into the intricacies of both source coding and channel coding. Source coding deals with the challenge of efficiently representing information from the source. It encompasses various elements such as source words, messages, source coding rates, compression rates, bit rates, and source coding error probabilities. Understanding these components is essential for optimizing the utilization of available bandwidth and resources.
  2. Source Coding: Source coding focuses on the task of compressing data efficiently while preserving its essential information. Here, we encounter the source coding problem, which involves converting a message into a sequence of symbols or bits. Key aspects include source words representing the original data, the message itself, source coding rates determining the compression level, and error probabilities associated with source coding. Effective source coding techniques are pivotal in reducing redundancy and maximizing the utilization of available resources in data transmission.
  3. Channel Coding: Channel coding addresses the challenge of transmitting data reliably across noisy communication channels. It involves encoding the message in a way that enhances its resilience to channel-induced errors. Central to channel coding are concepts such as emitted words, channel transition probabilities, channel coding rates, coder efficiency, and error probabilities. By employing sophisticated encoding schemes, we aim to mitigate the effects of noise and interference, thereby improving the overall reliability and robustness of the communication system.
  4. Joint Source-Channel Coding: Bridging the realms of source and channel coding, joint source-channel coding aims to optimize the overall performance of communication systems. It considers the combined effects of source and channel coding on transmission efficiency and error resilience. Parameters such as source-channel coding rates and error probabilities become crucial in this context, as they directly influence the system’s performance. By integrating source and channel coding strategies seamlessly, we strive to achieve optimal utilization of resources while maintaining high levels of data integrity and reliability in communication systems.

Course Outline:

  1. Coding problem
  2. Source coding
  3. Channel coding
  4. Source-channel coding

Lecture 2 Shannon's Entropy and Conditional Entropy

📄 PDF
Embarking on a captivating exploration of information theory, this lecture titled « Shannon’s Entropy and Conditional Entropy » delves into the foundational concepts that underpin the quantification of uncertainty in data. Structured into four illuminating sections, this lecture offers a comprehensive examination of Shannon’s entropy and conditional entropy, shedding light on their theoretical underpinnings and practical implications across various domains.
  1. Entropy: The lecture commences with an in-depth analysis of entropy, a cornerstone concept in information theory introduced by Claude Shannon. Participants will delve into Shannon’s entropy and its significance in measuring uncertainty within a system, alongside exploring applications such as the entropy of Bernoulli distribution and the Gibbs inequality. Through elucidative examples and mathematical insights, attendees will gain a profound understanding of entropy’s role in quantifying information.
  2. Conditional Entropy: Transitioning seamlessly, the lecture progresses to unravel the intricacies of conditional entropy. Attendees will delve into Bayes’ rule for conditional entropy, which provides a framework for understanding the uncertainty of a random variable given the knowledge of another. Additionally, the lecture explores the chain rule for conditional entropy, shedding light on the interplay between multiple variables and their associated uncertainties.
  3. Fano’s Inequality: This section introduces Fano’s inequality as a powerful tool for understanding the limits of estimation in the context of information theory. Participants will explore the interpretation of Fano’s inequality in terms of estimation, gaining insights into the trade-offs between the accuracy of estimation and the complexity of the underlying system.
  4. Entropy Rate: Concluding the lecture, participants delve into the concept of entropy rate, particularly focusing on its application in analyzing the information content of sequences generated by Markov chains. Through a comprehensive examination of entropy rate in the context of Markov chains, attendees will gain a deeper understanding of the dynamic nature of uncertainty in sequential data. Through this structured exploration, participants will emerge equipped with a thorough understanding of Shannon’s entropy and conditional entropy, empowering them to apply these concepts in diverse real-world scenarios.

Course Outline:

  1. Entropy
  2. Conditional entropy
  3. Fano’s inequality
  4. Entropy rate

Lecture 3 Mutual Information and Kullback-Leibler Divergence

📄 PDF
This lecture on « Mutual information and Kullback-Leibler divergence », serves as an enlightening exploration into the pivotal concept of mutual information, which stands as a cornerstone in the realm of information theory. With its ability to precisely quantify the shared information between random variables, mutual information holds profound significance across a spectrum of fields including statistics, machine learning and cryptography. The lecture unfolds into three meticulously crafted sections, each offering a comprehensive examination of distinct facets of mutual information.
  1. Kullback-Leibler Divergence: Exploring the foundational concept of Kullback-Leibler divergence, this section serves as a cornerstone in understanding information theory. We meticulously dissect its properties, including non-negativity, convexity, and continuity, revealing the profound implications it holds across various disciplines. Through rigorous examination, we elucidate how this metric quantifies the dissimilarity between probability distributions, offering invaluable insights into the comparative analysis of information content.
  2. Mutual Information: Within the realm of information theory, mutual information emerges as a pivotal concept, epitomizing the essence of shared information between random variables. In this section, we embark on a comprehensive exploration of its definition and properties, laying bare its profound implications for understanding the interplay of uncertainty and information transmission. Furthermore, we delve into the intricacies of the data processing inequality, a fundamental constraint that governs the flow of information within complex systems.
  3. Conditional Mutual Information: Building upon the foundational principles established earlier, we delve into the realm of conditional mutual information, a nuanced concept that elucidates the dependencies between random variables under specific conditions. This section serves as a deep dive into the complexities of information theory, as we meticulously examine the definition and properties of conditional mutual information. Through the exploration of Kolmogorov’s formula, the chain rule for mutual information, and the Csiszar sum identity, we unravel the intricate relationships between conditional probabilities and mutual information. By illuminating these connections, we unlock new avenues for understanding complex systems and harnessing the power of information to drive innovation and discovery.

Course Outline:

  1. Kullback-Leibler divergence
  2. Mutual information
  3. Conditional mutual information

2. Source Coding

Lecture 4 Source Coding Theorem

📄 PDF
In this lecture on « Source coding theorem », we delve into the foundational concept of source coding theorem within information theory. Understanding the source coding theorem is pivotal in elucidating the fundamental limits and possibilities of data compression in information theory. We begin by exploring the notion of source coding capacity and its characterization, leading to Shannon’s source coding theorem. We then analyze the compression perspective and typical sequences, followed by a rigorous proof of the source coding theorem.
  1. Source Coding Capacity: The source coding capacity is defined as the infimum of achievable rates for encoding a source. It is characterized by Shannon’s source coding theorem, which establishes that the coding capacity of an i.i.d. source equals its entropy. The set of achievable rates encompasses the range of encoding efficiencies attainable for a given source.
  2. Source Coding Theorem: Shannon’s source coding theorem asserts that the coding capacity of an i.i.d. source aligns with its entropy. From a compression standpoint, an i.i.d. source generating a sequence of symbols, with uniform distribution, is inherently incompressible. We explore the notion of typical sequences, including strongly-typical sequences, typical average lemma, asymptotic equipartition property, and entropy-typicality, shedding light on the fundamental properties of source coding.
  3. Source Coding Theorem Proof: The proof of the source coding theorem is divided into achievability and converse aspects. To demonstrate achievability, we construct a coder and decoder based on typical sets, leveraging the properties of typical sequences. The proof of converse relies on the Typicality lemma, providing insights into the necessity of typicality in achieving optimal encoding efficiency.

Course Outline:

  1. Source coding capacity
  2. Source coding theorem
    2.1 Compression point of view
    2.2 Typical sequences
  3. Source coding theorem proof
    3.1 Proof of achievability
    3.2 Proof of converse

Lecture 5 Error-Free Source Coding

📄 PDF
In this lecture on « Error-free source coding », we delve into the fundamental principles and techniques underlying the efficient encoding of information without loss. Beginning with an exploration of variable-length source coding and coding rates, we establish the groundwork for understanding error-free encoding methods. Through the elucidation of uniquely decipherable codes, including codebooks and codewords, we highlight the importance of unambiguous decoding in information transmission. Building upon these concepts, we examine the application of codes on trees and delve into Kraft’s inequality as a crucial tool for assessing code efficiency. Finally, we culminate with an in-depth analysis of the error-free source coding theorem, addressing optimization challenges, average codeword length bounds, and the significance of Kraft’s code in achieving error-free encoding solutions.
  1. Error-free source coding: This section introduces the concept of variable-length source coding, where the length of codewords varies based on the probability distribution of the source symbols. We discuss coding rates, which measure the efficiency of encoding information with variable-length codes. Understanding these fundamentals is essential for designing efficient encoding schemes that minimize redundancy while maintaining fidelity in data transmission.
  2. Uniquely decipherable codes: Here, we delve into the properties of uniquely decipherable codes, which ensure unambiguous decoding of encoded messages. Exploring terms such as code, codeword, codebook, and the significance of prefix-free codes, we elucidate the importance of designing codes that facilitate error-free decoding. By grasping these concepts, one can appreciate the critical role of uniquely decipherable codes in reliable information transmission.
  3. Codes on trees and Kraft’s inequality: In this segment, we extend our discussion to codes represented by trees and delve into Kraft’s inequality—a fundamental theorem governing the feasibility of prefix-free codes. By understanding the structure of D-ary trees associated with codes and the implications of Kraft’s inequality, we gain insights into the constraints and possibilities of constructing efficient error-free codes.
  4. Error-free source coding theorem: Concluding our lecture, we explore the error-free source coding theorem, which formalizes the optimization problem of source coding. We investigate bounds on the average codeword length, essential for evaluating the efficiency of encoding schemes. Furthermore, we discuss the practical application of Kraft’s code as a method for achieving optimal error-free encoding solutions, thus tying together the theoretical underpinnings with real-world implementation considerations.

Course Outline:

  1. Error-free source coding
  2. Uniquely decipherable codes
  3. Codes on trees and Kraft’s inequality
  4. Error-free source coding theorem

Lecture 6 Optimal Source Codes

📄 PDF
In this lecture on « Optimal source codes », we delve into two key methodologies: Huffman’s optimal code and the Shannon-Fano-Elias code. These techniques are pivotal for designing efficient codes that facilitate data compression without loss. By exploring the principles underlying these approaches, we gain valuable insights into creating highly efficient encoding schemes for various data sources.
  1. Huffman’s optimal code: This section explores the concept of optimal codes, aiming to minimize the average code word length while ensuring uniqueness in decoding. We dissect Huffman’s algorithm, uncovering how it constructs codes that achieve optimal code word lengths. Through an in-depth examination of the algorithm’s mechanics and design rationale, we develop a nuanced understanding of Huffman’s optimal code and its significance in data compression.
  2. Shannon-Fano-Elias code: Shifting our focus, we investigate the Shannon-Fano-Elias code, another crucial technique in optimal source coding. Developed by Shannon and further refined by Elias, this method offers an alternative approach to efficient encoding. We explore the underlying principles of the Shannon-Fano-Elias algorithm, its partitioning of symbols based on probabilities, and resulting code word assignments. By comparing and contrasting this approach with Huffman’s method, we grasp the diverse strategies available for designing optimal source codes, enriching our toolkit for data compression endeavors.

Course Outline:

  1. Huffman’s optimal code
    1.1 Optimal code
    1.2 Huffman’s code
    1.3 Optimality of the Huffman’s code
  2. Shannon-Fano-Elias code

Lecture 7 Parsing-Translation and Tunstall’s Codes

📄 PDF
In this lecture on « Parsing-translation and Tunstall’s codes », we delve into innovative techniques for achieving equally small coding rates by optimally grouping source symbols into variable-length blocks, a process known as parsing, and subsequently encoding these blocks with simple, non-optimized codes. This concept, pioneered by Tunstall’s code in 1967, exemplifies a broader class of codes involving parsing followed by translation. Through a detailed exploration of parsing-translation codes and Tunstall’s methodology, we will gain insights into the principles underlying efficient encoding strategies and their practical applications.
  1. Parsing-translation code: This section introduces the concept of parsing-translation codes, where source symbols are grouped into variable-length blocks before encoding. We delve into the mechanics of this process, highlighting how optimal grouping can lead to equally small coding rates compared to traditional encoding methods. By understanding the fundamentals of parsing and translation, we will grasp the significance of this approach in achieving efficient data compression and transmission.
  2. Valid parsing book: Here, we examine the notion of a valid parsing book, a crucial component in the implementation of parsing-translation codes. A valid parsing book defines the allowable parsing structures for encoding source symbols into variable-length blocks. We explore the characteristics of valid parsing books and discuss strategies for constructing them to ensure optimal compression performance. Through concrete examples and illustrations, you will gain a deeper understanding of the role of parsing books in efficient encoding schemes.
  3. Mean formulae for a valid parsing book: In this segment, we delve into the mean formulae associated with a valid parsing book, providing insights into the statistical properties and efficiency metrics of parsing-translation codes. These formulae offer quantitative measures for evaluating the performance of encoding schemes based on parsing and translation. By understanding the mathematical underpinnings of mean formulae, one can assess the effectiveness of different parsing strategies and optimize the encoding processes accordingly.
  4. Tunstall’s code: Concluding our lecture, we explore Tunstall’s code, a seminal example of parsing-translation codes that revolutionized data compression techniques. We delve into the methodology behind Tunstall’s approach, which involves constructing an optimal parsing book followed by simple encoding using fixed-length codes. Through a detailed examination of Tunstall’s algorithm and its practical applications, we will gain valuable insights into the power and versatility of parsing-translation codes in achieving efficient data compression and transmission.

Course Outline:

  1. Parsing-translation code
  2. Valid parsing book
  3. Mean formulae for a valid parsing book
  4. Tunstall’s code

Lecture 8 Universal Source Coding

📄 PDF
In this lecture on « Universal Source Coding », we delve into the fascinating realm of data compression and encoding, exploring the concept of universal source coding and its implications. Universal source coding seeks to develop methods that can efficiently compress any type of data without prior knowledge of its statistical properties. The lecture is structured into three distinct sections:
  1. Universal Source Coding: Universal source coding is introduced with a comprehensive definition, elucidating its fundamental principles and objectives. This section provides insights into the overarching goal of developing encoding schemes that can effectively compress diverse data types without tailored encoding algorithms for each source.
  2. Empirical Distributions: Delving deeper, we explore empirical distributions, examining the statistical properties of real-world data sources. Understanding these distributions is crucial for developing universal source coding techniques that can adapt to varying data characteristics. This section lays the groundwork for the subsequent proof of universal source coding.
  3. Proof of Universal Source Coding: Finally, we present the proof of universal source coding, demonstrating the existence of encoding schemes that can efficiently compress any source without loss of information. Through mathematical analysis and theoretical constructs, we unravel the intricacies of how universal source coding transcends the limitations of traditional coding methods, offering a groundbreaking approach to data compression.
This structured lecture equips participants with a comprehensive understanding of universal source coding, from its conceptual underpinnings to its practical implications, fostering a deeper appreciation for the intricacies of data compression in diverse contexts.

Course Outline:

  1. Universal source coding
  2. Empirical distributions
  3. Proof of universal source coding

Lecture 9 Lempel-Ziv Source Code

📄 PDF
In this lecture on « Lempel-Ziv Source Code », we delve into the intricacies of the Lempel-Ziv algorithm, a pivotal method for encoding arbitrary source sequences without errors, thereby achieving error-free universal source coding. Through a structured exploration, we unravel the algorithm’s mechanics, discuss its extensions, analyze its efficiency through coding automat theory, and establish its optimality in comparison to other encoding techniques.
  1. Lempel-Ziv Algorithm: The core of our discussion revolves around the Lempel-Ziv algorithm, comprising both its coding and decoding processes. We elucidate the step-by-step procedures of encoding and decoding, highlighting its adaptive nature in handling finite input sequences. Additionally, we delve into the necessity and formulation of an extended version of the algorithm to tackle scenarios where certain sequences lack prefixes in the parsing book, ensuring robustness in encoding and decoding operations.
  2. Coding Automat: This section introduces the concept of coding automat, emphasizing its significance in achieving uniquely decodable and information lossless encoding. We define the properties of uniquely decodable and information lossless coding automats through lemmas, shedding light on their fundamental characteristics and implications for efficient encoding processes.
  3. Parsing-Entropy: Parsing-entropy emerges as a pivotal metric for assessing the efficiency of Lempel-Ziv coding against finite coding automats. We elucidate the concept of parsing-entropy, framing it as a measure of parsing complexity for deterministic source sequences. Through rigorous analysis, we establish bounds on parsing-complexity, providing insights into the achievable coding rates within the framework of finite automats.
  4. Optimality of Lempel-Ziv Coding: In this conclusive segment, we ascertain the optimality of Lempel-Ziv coding by juxtaposing it against the coding rates achievable by finite automats. We demonstrate that parsing-entropy serves as a lower bound for source coding rates attainable by information lossless finite automats. Furthermore, we establish the equivalence of Lempel-Ziv coding rate to Shannon’s entropy for i.i.d. source symbols, solidifying its optimality. Through theorems, we provide formal proofs of the algorithm’s optimality for both deterministic and i.i.d. sequences, culminating in a comprehensive understanding of its superiority in universal source coding.

Course Outline:

  1. Lempel-Ziv algorithm
  2. Coding automat
  3. Parsing-entropy
  4. Optimality of Lempel-Ziv coding
    4.1 Coding-rates of IL finite automats
    4.2 Optimality theorems of Lempel-Ziv

3. Channel Coding

Lecture 10 Channel Information Capacity

📄 PDF
In this lecture on « Channel Information Capacity », we delve into the fundamental concepts surrounding the capacity of communication channels to transmit information reliably. Beginning with an exploration of channel basic properties, we establish the foundational understanding necessary to comprehend the intricacies of information capacity. Moving forward, we define information capacity and examine its theoretical underpinnings. Finally, we illustrate these concepts through examples of specific channels, shedding light on how capacity manifests in real-world communication scenarios.
  1. Channel Basic Properties: Understanding the behavior of communication channels is paramount to grasping their information capacity. We dissect the fundamental properties that characterize channels: memorylessness, lack of feedback, and absence of anticipation. Through these properties, we define the notion of a time-invariant channel and explore the concept of channel transition probability. Leveraging a lemma, we establish the significance of product-form transitions and introduce the concept of a time-invariant product-form channel, laying the groundwork for a deeper understanding of information capacity.
  2. Information Capacity: Central to our discourse is the concept of information capacity, defined as the supremum of mutual information between the input and output of a channel, providing a rigorous framework for assessing communication performance. (We will show in the next lecture that it represents the maximum rate at which information can be reliably transmitted over a channel.) Through key lemmas, we establish the concavity and continuity of entropy and mutual information in the discrete case, elucidating the mathematical foundations underlying capacity determination. Additionally, we explore the achievability of capacity in finite scenarios, offering insights into the practical limits of information transmission.
  3. Examples of Channel’s Information Capacity: To solidify our understanding, we examine concrete examples that demonstrate the application of information capacity principles to specific channel models. By scrutinizing the Binary Symmetric Channel and the Binary Erasure Channel, we elucidate how varying channel characteristics influence information capacity. Through these examples, we observe the interplay between channel parameters and capacity, providing valuable insights into the design and optimization of communication systems. Ultimately, these case studies serve to contextualize theoretical concepts within real-world communication scenarios, highlighting the practical relevance of channel information capacity analysis.

Course Outline:

  1. Channel basic properties
  2. Information capacity
  3. Examples of channel’s information capacity

Lecture 11 Channel Coding Theorem

📄 PDF
In this lecture on the Channel Coding Theorem, we delve into fundamental concepts in information theory, particularly focusing on the relationship between achievable rates and a channel’s coding capacity. Beginning with the foundational statement of the theorem, we explore the mechanisms through which transmission rates can be optimized within the constraints of noisy channels. We then proceed to establish the groundwork for the proof by introducing typical sequences for two random variables and essential inequalities for mutual information.
  1. Channel Coding Theorem Statement: We start by defining achievable rates and a channel’s coding capacity, laying the groundwork for understanding the set of achievable rates. Central to this discussion is Shannon’s Noisy-Channel Coding Theorem, which asserts that transmission rates below the channel’s capacity are attainable with arbitrarily small error probabilities. We prepare for the proof by introducing preliminary results, including an extension of typical sequences to pairs of random variables and essential inequalities for mutual information.
  2. Typical Sequences for Two Random Variables: Expanding upon the notion of typical sequences, we define jointly typical sequences and establish their properties. Understanding these sequences is crucial for the subsequent proof, as they form the basis for encoding and decoding schemes that achieve optimal transmission rates.
  3. Inequalities for Mutual Information: We delve into key inequalities for mutual information, particularly focusing on their application in product-form channels. These inequalities play a pivotal role in establishing the achievability and converse parts of the channel’s coding theorem. Additionally, we reformulate Fano’s inequality within the context of our discussion.
  4. Proof of Achievability: The proof of the achievability part of the channel’s coding theorem relies on a random coding argument and decoding based on jointly typical sequences. Through a detailed examination of these mechanisms, we illustrate how optimal transmission rates can be achieved despite the presence of noise in the communication channel.
  5. Proof of Converse: Finally, we tackle the converse part of the channel’s coding theorem, demonstrating how previously established inequalities for mutual information inform this aspect of the proof. By leveraging these inequalities, we establish the limits of achievable transmission rates within the constraints of noisy channels, providing a comprehensive understanding of the theorem’s implications.

Course Outline:

  1. Channel coding theorem statement
  2. Typical sequences for two random variables
  3. Inequalities for mutual information
  4. Proof of achievability
  5. Proof of converse

Exercises with Solutions

You’ll find a curated collection of problems designed to reinforce your understanding of information theory concepts. Each exercise is accompanied by a detailed solution, providing step-by-step guidance to ensure you grasp the practical applications of the theory. Whether you’re a student, educator, or enthusiast, these exercises will help solidify your knowledge and enhance your analytical skills in this fascinating field. 

  1. Exercises 1, Solutions 1 for Lecture 2 « Shannon’s Entropy and Conditional Entropy »: These exercises delve into key concepts such as the entropy of the geometric distribution, the demonstration of how the geometric distribution maximizes entropy, and the application of Boltzmann’s principle in Thermodynamics, alongside the exploration of the Gibbs distribution.
  2. Exercises 2, Solutions 2 for Lecture 5 « Error-free source coding »: These exercises encompass a range of essential concepts, including the establishment of prefix-free codes as uniquely decipherable, the derivation of the law of large numbers from Chebyshev’s inequality, an extension of Kraft’s lemma, and the interpretation of entropy through questionnaire analysis. 
  3. Exercises 3, Solutions 3 for Lecture 6 « Optimal source codes »: These exercises encompass fundamental concepts such as Kraft’s code and its implications for the cost of using an incorrect distribution, the proof of a lemma crucial for establishing the optimality of Huffman’s code, and practical examples illustrating the optimality of Huffman’s code. Additionally, learners engage with the application of Huffman’s optimal code specifically for the Bernoulli distribution. Furthermore, the last exercise explores scenarios where the most probable sequence may deviate from typical ones. 
  4. Exercises 4, Solutions 4 for Lecture 6 « Optimal source codes »: These exercises cover a diverse array of essential topics, including methods for determining expected values utilizing cumulative distribution functions (CDFs), techniques for characterizing independence within probabilistic systems, strategies for identifying a counterfeit coin through information-theoretic analysis, and the implementation of D-ary Huffman’s code for efficient data compression.
  5. Exercises 5, Solutions 5 for Lecture 7 « Parsing-translation and Tunstall’s codes »: These exercises encompass a variety of fundamental concepts, including Wald’s formula, the proof that the parsing sequence is independent and identically distributed (i.i.d), the exploration of convexity of the function x log(x/y), and the study of the notion of Tunstall parsing book.
  6. Exercises 6, Solutions 6 for Lecture 8 « Universal source coding »: The exercises address the cardinality of the set of empirical distributions, encoding Bernoulli source-symbols, and exploring the continuity of Kullback-Leibler divergence.
  7. Exercises 7, Solutions 7 for Lecture 9 « Lempel-Ziv source code »: The exercises include « Set Associated to Shannon’s Entropy, » « Parsing-Entropy Lower Bound, » « Parsing-Entropy Upper Bound, » « Coding Automat Information Lossless but Not Uniquely Decodable, » and « Coding automat properties. »
  8. Exercises 8, Solutions 8 for Lecture 9 « Lempel-Ziv source code ».
  9. Exercises 9, Solutions 9 for Lecture 3 « Mutual Information and Kullback-Leibler Divergence ».
  10. Exercises 10, Solutions 10 for Lecture 3 « Mutual Information and Kullback-Leibler Divergence ».
  11. Exercises 11, Solutions 11 for Lecture 10 « Channel information capacity ».
  12. Exercises 12, Solutions 12 for Lecture 10 « Channel information capacity ».

Part V — MIMO Performance: Link Capacity & Network Dynamics

10. MIMO Channel Capacity: Evaluation and Analysis

🎬 Video (EN) 📄 PDF
This presentation addresses the numerical evaluation of MIMO channel capacity under two channel-knowledge scenarios: CSIR, where only the receiver knows the channel, and CSITR, where transmitter and receiver both do. Three computational methods are compared — direct numerical integration, Monte Carlo simulation, and asymptotic formulas — and applied to assess capacity scaling with antenna count and to quantify the gain from transmitter channel knowledge.

Course Outline:

  1. Goals and Scope
  2. MIMO CSIR with I.I.D. Gaussian Noise
    2.1 Computational Methods for CSIR
    2.2 Asymptotic Formula vs. Simulation for CSIR
    2.3 On the Choice of Computational Method
    2.4 Capacity Analysis with CSIR
  3. MIMO CSITR with I.I.D. Gaussian Noise
    3.1 CSITR and Quasistationary Waterfilling Models
    3.2 Computational Methods for CSITR
    3.3 Asymptotic Formula vs. Simulation for CSITR
    3.4 Capacity Analysis with CSITR
    3.5 Quantifying the Gain from CSITR

About These Topics

Embark on a journey through the fascinating realm of information theory and coding with our comprehensive webpage. Whether you’re a novice or a seasoned professional, our curated collection of lectures, exercises, and solutions provides an invaluable resource for anyone interested in mastering the principles of information transmission and encoding. From exploring Claude Shannon’s seminal work to delving into practical coding techniques, our course covers essential topics such as entropy, mutual information, source coding, and channel coding, offering a rich learning experience for enthusiasts and experts alike. Access our extensive library of PDFs and videos to deepen your understanding and gain practical insights into the theory and application of information theory.

Resources and References

Teaching Information Theory at ENS

Teaching at Computer Science department of Ecole Normale Supérieure  (ULM, Paris) with Bartłomiej Blaszczyszyn :

  • Course title: « Information, coding theories: Source, channel coding, Shannon theorems » (2016-2024). 
  • Course location: ENS, 45, rue d’Ulm 75230 Paris Cedex 05. E. Noether room in the 2nd basement of the “AILE RATAUD” building; cf. ENS map.

Book on Information Theory: Coming Soon on this Webpage

Keep an eye on this page for the upcoming launch of our book:

  • Mohamed Kadhem KARRAY, Bartłomiej BLASZCZYSZYN: « Information Theory for Discrete and General Alphabets, with Applications to Wireless Communications and Networks ». 

Last Updated on 5 mai 2026 by Mohamed Kadhem KARRAY

Laisser un commentaire