Introduction to Information Theory

Fundamentals of Information Theory What is Information Theory? Information theory is a mathematical framework that studies how data can be represented, transmitted, and processed. At its core, it answers fundamental questions: How much information does a message contain? What is the smallest amount of data needed to represent information? How reliably can we send information through imperfect channels? These questions are central to modern communication, data storage, and computing, making information theory one of the most important foundations in computer science and engineering. The Bit: Measuring Information The binary digit (or bit) is the fundamental unit of information. It represents a choice between two equally likely outcomes—typically represented as 0 or 1. This choice is intuitive: if you have to distinguish between two equally likely possibilities, one bit of information is exactly what you need. More generally, if a source produces $N$ equally likely symbols, the amount of information needed to specify which symbol occurred is: $$\text{Information} = \log2 N \text{ bits}$$ Example: A fair coin flip produces one of 2 equally likely outcomes, so $\log2 2 = 1$ bit of information. A fair six-sided die produces one of 6 equally likely outcomes, so $\log2 6 \approx 2.58$ bits of information. Entropy and Source Coding Understanding Entropy Most sources in the real world don't produce symbols with equal probability. For example, in English text, the letter 'E' appears much more frequently than the letter 'Z'. This means we should be able to use fewer bits on average to encode common symbols. Entropy ($H$) measures the average amount of information (in bits) produced per symbol from a random source. It accounts for the probability distribution of the symbols—more predictable sources have lower entropy, while more unpredictable sources have higher entropy. The entropy formula is: $$H = -\sum{i=1}^{N} pi \log2 pi$$ where $pi$ is the probability of the $i$-th symbol and $N$ is the total number of possible symbols. Understanding the formula: Each term $pi \log2 pi$ represents the contribution of symbol $i$ to the overall entropy. The negative sign is necessary because logarithms of probabilities (which are less than 1) are negative, and we want entropy to be positive. The sum averages these contributions across all symbols weighted by their probabilities. Intuition for Entropy Consider two extreme cases: Completely predictable source: If one symbol has probability 1 and all others have probability 0, then $H = -1 \cdot \log2(1) = 0$. A completely predictable source carries zero entropy—you learn nothing new. Maximally unpredictable source: If all $N$ symbols are equally likely ($pi = 1/N$ for all $i$), then $H = -N \cdot \frac{1}{N} \log2 \frac{1}{N} = \log2 N$. Maximum entropy occurs when all symbols are equally likely. The Fundamental Limit: The Entropy Bound Here is one of the most important results in information theory: No lossless encoding can use fewer than $H$ bits per symbol on average. This is called the entropy bound. It's a hard theoretical limit—not just a limitation of current compression algorithms, but a mathematical truth about what's possible. What does this mean practically? If a source has entropy $H = 4.5$ bits per symbol, you cannot design any lossless compression algorithm that averages fewer than 4.5 bits per symbol, no matter how clever you are. This is why entropy is so important: it tells us the theoretical best-case performance for any compression algorithm. Huffman Coding: A Practical Approach Huffman coding is a practical algorithm that creates variable-length binary codes based on symbol frequencies. More frequent symbols get shorter codes, and less frequent symbols get longer codes. Example: In English text, 'E' might be coded as "10" (2 bits) while 'Z' might be coded as "11001" (5 bits). Overall, the average code length is much less than a fixed-length code for all 26 letters. Huffman coding is optimal among codes where each symbol has an integer number of bits, but it doesn't always achieve the theoretical entropy bound. This is because symbols sometimes have awkward probabilities that don't divide evenly into powers of 2. <extrainfo> Arithmetic Coding Arithmetic coding is an alternative compression technique that can approach the entropy bound more closely than Huffman coding. Rather than assigning fixed-length codes to each symbol, arithmetic coding represents the entire message as a single fractional number between 0 and 1, refined based on symbol probabilities. This allows it to handle fractional bits more efficiently, achieving compression rates closer to the theoretical limit. However, arithmetic coding is more computationally complex than Huffman coding. </extrainfo> Channel Capacity and Coding Theorem The Problem of Noisy Channels In real communication systems, noise and errors are inevitable. A telephone line might introduce static, a wireless signal might fade, or cosmic rays might flip bits in a memory device. The question becomes: how reliably can we send information through an imperfect channel? Channel capacity is the maximum amount of information (in bits per symbol) that can be transmitted reliably through a noisy communication channel. The capacity depends on the channel's noise characteristics. A cleaner channel with less noise has higher capacity; a noisier channel has lower capacity. Shannon's Channel Coding Theorem This is one of the most profound results in information theory, and it has two parts: Part 1 (Achievability): If the transmission rate is below the channel capacity $C$, there exist error-correcting codes that make the probability of decoding error arbitrarily small. This means we can transmit information reliably through a noisy channel. Part 2 (Converse): If the transmission rate exceeds the channel capacity $C$, no code can make the error probability arbitrarily small. Reliable communication becomes impossible. Why This Matters Shannon's theorem doesn't tell you how to build such codes—it tells you that they exist (or don't exist). It establishes a hard boundary: below capacity, reliable communication is achievable in principle; above capacity, it's impossible in principle. This was revolutionary because it means noise doesn't make reliable communication impossible—you just have to operate below the capacity limit and use appropriate coding strategies. <extrainfo> Error-Detecting and Error-Correcting Codes In practice, engineers use error-detecting codes (like checksums) to identify when errors occur during transmission, and error-correcting codes (like Hamming codes) to actually fix errors. These codes add redundancy to the message—extra bits that allow the receiver to detect or correct errors. The trade-off is that adding this redundancy reduces the effective transmission rate (fewer "useful" bits per transmission), but it ensures reliability. Shannon's theorem guarantees that if we operate below channel capacity with appropriate codes, we can achieve arbitrarily low error rates. </extrainfo> Applications of Information Theory Data Compression Information theory provides the theoretical foundation for modern data compression. Techniques like GZIP (used for text files), JPEG (used for images), and MP3 (used for audio) all rely on information-theoretic principles to reduce file sizes while preserving information. The entropy of a source directly determines how much compression is theoretically possible. By understanding entropy, engineers can design practical compression algorithms that approach theoretical limits. Summary Information theory gives us the mathematical language to understand information, measure it, compress it, and transmit it reliably. The key concepts are: Bits measure information quantitatively Entropy measures average information content per symbol and sets a fundamental limit on compression Channel capacity sets a fundamental limit on reliable transmission through noisy channels Shannon's theorem guarantees that reliable communication is possible below capacity and impossible above it These principles underpin nearly all modern communication and data storage technologies.