Information Theory §
Information theory studies the mathematical limits of encoding, compression, transmission, and protection of data. It is relevant whenever information must be stored compactly, sent reliably over a noisy channel, or kept secret from an adversary.
Utility §
- It bounds the minimum number of bits needed to represent a source.
- It designs codes that achieve those bounds (compression, error correction).
- It provides the mathematical foundation for cryptography.
Details
Information theory sits between algorithmics and the physical world: it takes the abstract data produced by an algorithm and asks how many bits are truly needed, how to pack them efficiently, and how to protect them from noise or eavesdroppers. The key insight is that the limits are mathematical (entropy, channel capacity) and are independent of the particular hardware or protocol used to implement them.
History §
- 1948: Shannon publishes “A Mathematical Theory of Communication,” defining entropy and channel capacity.
- 1952: Huffman publishes optimal prefix-free codes.
- 1960s: Reed-Solomon codes and convolutional codes mature for error correction.
- 1976: Diffie and Hellman publish “New Directions in Cryptography,” founding public-key cryptography.
Classes §
| Page | Core object | Key metric | Boundary |
|---|---|---|---|
| Coding and entropy | Alphabets, encodings, entropy measures | Bits per symbol, entropy, redundancy | How to represent data compactly; does not model the channel or the adversary |
| Compression | Lossless and lossy codecs | Compression ratio, distortion, bitrate | How to reduce the number of bits; does not model the transmission channel |
| Communication | Error-correcting codes, channel models | Bit error rate, code rate, channel capacity | How to transmit reliably over a noisy channel; does not model the source or the adversary |
| Cryptography | Ciphers, hashes, key exchange | Key size, advantage, security parameter | How to protect data from an adversary; does not model the physical channel |
Authoritative sources