Difficulty: Introductory | Prerequisites: Basic probability and statistics
Big Picture: Information theory and coding theory form the mathematical backbone of how we store, compress, and transmit data. These topics sit at the foundation of CS 101 and connect outward to networking, cryptography, data compression, and error correction. You should be comfortable with basic probability before diving in. If terms like "random variable" or "probability distribution" are unfamiliar, review your statistics notes first.
Information theory, developed by Claude Shannon, gives us the mathematics for measuring how much "information" a message carries and the limits on how efficiently we can compress or transmit it. Coding theory studies the design of codes (schemes for converting data from one form to another) and how well they perform for tasks like compression, error detection, encryption, and steganography.
Information theory
The mathematical study of quantifying, storing, and communicating information. Developed by Claude Shannon in his landmark 1948 paper. In simple terms, it answers the question: "How much data can we push through a channel, and what are the hard limits?"
Entropy (Shannon entropy)
A measure of the average uncertainty or "surprise" in a random variable's outcomes. Higher entropy means more unpredictability. Think of it as: the more unpredictable your data source is, the more bits you need to represent each message.
Coding theory
The study of the properties of codes (systematic rules for converting information from one representation to another) and how well they suit a given application. In simple terms, this is the science of designing efficient and reliable ways to encode data.
Data compression (source coding)
Reducing the number of bits needed to represent data. Lossless compression keeps everything intact; lossy compression discards some information for a smaller file. Think of it as: squeezing a file down so it takes less space or bandwidth.
Error detection and correction (channel coding)
Adding redundancy to transmitted data so the receiver can detect, and sometimes fix, errors introduced during transmission. Think of it as: building a safety net into your data so flipped bits do not ruin the message.
Cryptanalysis
The study of breaking or analysing cryptographic systems. Coding theory contributes the mathematical tools that underpin both making and breaking ciphers.
Steganography
Hiding information within other data (an image, audio file, or video) so that the existence of the hidden message is not apparent. A more recent application area for coding theory.
Channel capacity
The theoretical maximum rate at which information can be reliably transmitted over a communication channel. Shannon's noisy-channel coding theorem sets this upper bound.
Claude Shannon published "A Mathematical Theory of Communication" in 1948, founding the field
The core insight: information can be quantified mathematically, independent of its meaning
Shannon showed there are fundamental limits on how much data can be compressed (source coding theorem) and how fast it can be sent over a noisy channel (noisy-channel coding theorem)
Information theory is closely related to probability and statistics; it uses probabilistic models to describe data sources and communication channels
A code is a systematic arrangement for converting information from one form to another
Codes are not just about secrecy; they serve several distinct purposes:
Data compression: reducing storage or bandwidth requirements (e.g. ZIP, MP3, JPEG)
Error detection and correction: enabling reliable communication over unreliable channels (e.g. checksums, Hamming codes, Reed-Solomon codes)
Cryptography: securing data against unauthorised access
Steganography: concealing the existence of a message within another medium
Information theory sets the theoretical limits; coding theory designs practical schemes that approach those limits
Shannon proved that codes exist which can transmit data at rates up to the channel capacity with arbitrarily low error, but did not specify how to build them
Much of coding theory since 1948 has been about constructing codes that come close to Shannon's theoretical bounds
Information can take the form of text, speech, sound, images, or other multimedia
Signal processing studies how to manipulate these forms of information algorithmically, regardless of whether the data carrier is electrical, mechanical, or biological
Key application areas include telecommunications, medical imaging, speech synthesis, and data science
An open problem in theoretical CS: what is the lowest possible complexity for a fast Fourier transform algorithm?
Shannon entropy for a discrete random variable X with possible outcomes x₁, x₂, ..., xₙ:
H(X) = -\sum_{i=1}^{n} p(x_i) \log_2 p(x_i)Measured in bits when using log base 2. A fair coin has entropy of 1 bit; a biased coin has less.
Channel capacity (Shannon-Hartley theorem for a continuous channel with additive white Gaussian noise):
C = B \log_2\left(1 + \frac{S}{N}\right)Where B is bandwidth in Hz, S/N is the signal-to-noise ratio. This gives the maximum data rate in bits per second for error-free transmission.
Every time you stream a video, make a phone call, or send a file over Wi-Fi, information theory and coding theory are at work behind the scenes. Data compression (source coding) is why a 4K film fits on a streaming service; error-correcting codes are why your mobile call does not dissolve into static every time you pass a building. QR codes use Reed-Solomon error correction so they still scan even when partially damaged.
Students often think "information" in this context means "meaning" or "knowledge." It does not. Shannon's information is a purely mathematical quantity about uncertainty and probability, with no regard for whether the content is meaningful.
Students sometimes confuse compression (source coding) with encryption. Compression reduces size; encryption provides secrecy. They are different operations that can be applied together.
A common mistake is believing that error-correcting codes can fix unlimited errors. Every code has a correction capacity; beyond that limit, errors go undetected or uncorrected.
Students often assume that channel capacity is just about bandwidth. It is not. It depends on both bandwidth and signal-to-noise ratio together.
⚠️ Know the definition of Shannon entropy and be able to compute it for a simple distribution (e.g. a biased coin or a four-symbol alphabet).
⚠️ Understand the distinction between source coding (compression) and channel coding (error correction). Exams frequently test whether you can identify which type of coding a scenario describes.
⚠️ Be able to state what Shannon's noisy-channel coding theorem guarantees, and what it does not (it proves good codes exist but does not tell you how to construct them).
⚠️ Channel capacity questions may require applying the Shannon-Hartley formula. Know what each variable represents.
True or False: Shannon entropy measures the meaning of a message.
Fill in the blank: A code designed to reduce the size of data is called ______ coding.
True or False: The Shannon-Hartley theorem tells you the maximum error-free data rate for a channel with noise.
Fill in the blank: Hiding a message inside an image file so nobody knows the message exists is called ______.
True or False: Error-correcting codes can always fix any number of bit errors.
Q: What is Shannon entropy, and what does it measure?
A: Shannon entropy is a measure of the average uncertainty in a random variable's outcomes. It quantifies the minimum average number of bits needed to encode each symbol from a source. It is calculated as H(X) = -Σ p(xᵢ) log₂ p(xᵢ).
Q: A source produces four symbols with equal probability (0.25 each). What is its entropy?
A: H(X) = -4 × (0.25 × log₂ 0.25) = -4 × (0.25 × -2) = 2 bits per symbol.
Q: What is the difference between source coding and channel coding?
A: Source coding (data compression) aims to reduce the number of bits needed to represent information. Channel coding (error correction) adds controlled redundancy so that errors introduced during transmission can be detected or corrected.
Q: State Shannon's noisy-channel coding theorem in plain language.
A: For any communication channel, there exists a maximum rate (the channel capacity) at which data can be sent with an error probability as close to zero as desired. Below that rate, reliable communication is possible; above it, errors are unavoidable.
Q: Name three distinct applications of coding theory.
A: Data compression, error detection and correction, and cryptography. Steganography is a fourth, more recent application.
Information theory connects directly to probability and statistics (the mathematical language it is built on) and to data structures and algorithms (since efficient coding schemes are, at heart, algorithmic problems). It also underpins networking and telecommunications, where channel capacity determines design constraints. Cryptography relies on coding theory for both building and analysing ciphers.
Shannon entropy, information entropy, source coding theorem, noisy-channel coding theorem, channel capacity, Shannon-Hartley theorem, data compression, lossless compression, lossy compression, error detection, error correction, Hamming code, Reed-Solomon code, parity check, redundancy, cryptanalysis, steganography, signal processing, Fourier transform, bandwidth, signal-to-noise ratio, bit rate, coding scheme, codec, entropy coding, Huffman coding, arithmetic coding