Supplementary material on information theory. This document collects the proofs of key theorems and derivation details referenced in the main text, organized into five sections: Mathematical Tools, Channel, Rate-Distortion Function, Source Coding, and Channel Coding. All conclusions marked “see Appendix for proof” in the main text can be found here.
– “What is this all about? Can’t we just have coding schemes with no redundancy at all?”
– “Page after page, this is no different from lossy source coding. We have to account for noise, understand?”
Before delving into channel coding, the author feels it is necessary to clarify the relationship between source coding and channel coding. While reading the material in this section, the author often found it puzzling: the source coding process can be abstracted as a form of generalized transmission, so why must we spare a precious four lecture hours out of an eight-week course to study channel coding? In the preceding chapters, the author painstakingly attempted to remove redundancy from information, yet the purpose of channel coding is precisely to add redundancy?
First, source coding and channel coding do not describe the same thing in information theory – they actually address two independent problems in the field: leaving aside the channel, how should we compress information? Leaving aside the source, since noise is inevitable in a channel, how should we resist its interference? Source coding achieves a transmission rate close to the entropy of the source by compressing its redundant parts to the utmost; channel coding, on the other hand, introduces redundancy to counteract noise, thereby bringing the transmission rate close to the channel capacity. Thus, source coding and channel coding are two independent areas of research in information theory.
In fact, a unified theory does exist – joint source-channel coding. However, the Shannon separation theorem shows that, under lossless conditions, source coding and channel coding can be performed separately without any loss of performance. Since theory supports this decoupling, why not consider the two problems independently to achieve greater generality? Engineers working on the H.265 algorithm need not know whether the data stream they encode will be transmitted via optical disc or 5G, and 5G communications engineers need not know whether the data they transmit is a livestream of a SJTU premium course or a popular forum post. Such decoupling makes system development more flexible and efficient.
With that motivation, we arrive at this chapter: Channel Coding. In this chapter, we study errors in channel transmission, how to decode in order to minimize the probability of errors, how the channel coding theorem proves the existence of error-free coding schemes under certain conditions, and the construction and performance analysis of several classical linear block codes. In the analysis of linear block codes, we will employ some elegant properties of linear spaces and cyclic polynomials.
“Information has three great desires: compression rate, efficiency, and accuracy. Among these three desires, compression rate satisfies the need for compression survival, so the pursuit of compression rate takes the highest priority. If effective compression can be achieved during transmission, it also makes channel transmission extremely efficient. In real life, there exist codes that persistently pursue such efficiency. We usually refer to this type of code as an optimal code, and the encoder is specifically tailored for those channels weary of transmission distortion, providing source coding that matches their channel capacity.”
The role of source coding can be summarized as follows: - Symbol Transformation: To match the output symbols of the source with the input symbols of the channel; - Information Matching: To match the information output by the source with the transmission capability of the channel; - Redundancy Compression: To reduce redundant information in the source output, thereby improving transmission efficiency.
In the discussions on the source and the channel, we typically consider distortionless communication systems, i.e., systems where the messages produced by the source are transmitted to the receiver without error. However, in practical communication systems, completely distortionless transmission is often infeasible. Therefore, we need to introduce the concept of distortion to describe the information loss in communication systems.
Nevertheless, the distortion discussed in this section differs from noise. Noise refers to random interference introduced by the channel, whereas distortion refers to the discrepancy between output and input caused by deliberate compression during encoding or transmission due to excessive message length.
The concept and properties of channels, and channel capacity.
This section introduces the classification of sources and their mathematical models, and defines basic concepts such as self-information, mutual information, entropy, and relative entropy for both discrete and continuous sources.
This is the note of CS3321 Database System
Technology(数据库技术), a course offered to Grade 3 Computer
Science undergraduates at SJTU focusing on mathematical principle of
relational normalizations and design theory of database instead usage of
database. If you focus on practical usage of database systems such as
writing SQL queries and building database applications, you may consider
NIS3351
Database Principle and Security (unavailable) instead.
Sacastically, NIS3351 has nothing to do with database security.
Some pictures and content in this note are taken from slides, which can be checked at course homepage or homepage of Qiang Yin, the lecturer.
This blog, run by GitHub Actions and Hexo, is regularly updated. Although git commit messages provide some insight into the changes made, this log offers a more detailed overview of significant updates and modifications.
Root repository of this blog locates at Github - MingchenDai/mingchendai.github.io. You can check the changes there directly, or refer to this log for a summarized view of the updates in reverse chronological order.
Update logs are edited manually since February 2nd, 2026. Normal update of this post (including adding new update message and modifying existing commit ids) and About page will not be recorded here.
Counted by a VSCode plugin, the platform I spent the most time on is Debian via SSH remote connection from MacOS. However, Windows is still an important platform I use frequently, especially for some specific software that only runs on Windows or have requirements for a powerful GPU. This post records some issues I encountered when using Windows 11 on my Lenovo laptop, and their solutions.
As my computer is a dual-booting system with Arch Linux, some issues are related to dual-booting systems. These issues and their solutions will not appear in this post - please check Arch Linux - Windows Dual-Booting System Installation Guide for details.
This is a note of MATH1207 Probability and Mathematical Statistics (概率论与数理统计) taught at SJTU. It is originally written in Chinese to keep consistency with lecture language and translated into English later.
The note covers all contents of the course taught in 2025-2026-1 semester, including random events and probability, random variables and their distributions, numerical characteristics of random variables, joint distributions of multiple random variables, random samples and sampling distributions, estimation, and hypothesis testing.
Quick Navigation to check Common Discrete Random Variables and Their Properties and Common Continuous Random Variables and Their Properties.