The Central Idea
A code maps source symbols to codewords.
If common symbols receive shorter codewords and rare symbols receive longer codewords, the average representation can be shorter than a fixed-length code.
The central optimization problem is:
\[ \boxed{\text{represent information using as few resources as possible while preserving what must be recovered}}. \]Source Symbols
A source alphabet is the collection of symbols that may need to be encoded.
For example,
\[ \mathcal{A}=\{A,B,C,D\}. \]A source emits symbols from this alphabet according to some probability distribution.
Codewords
A codeword is the representation assigned to a source symbol.
In a binary code, codewords are strings of \(0\)s and \(1\)s.
For example:
| Symbol | Codeword |
|---|---|
| A | 0 |
| B | 10 |
| C | 110 |
| D | 111 |
Codeword Length
If symbol \(i\) receives a codeword containing \(\ell_i\) bits, then \(\ell_i\) is its codeword length.
In the preceding example,
\[ \ell_A=1,\qquad \ell_B=2,\qquad \ell_C=3,\qquad \ell_D=3. \]Fixed-Length Codes
A fixed-length code assigns every symbol the same number of bits.
If there are \(n\) possible symbols, a binary fixed-length representation requires at least
\[ \boxed{\lceil \log_2 n\rceil} \]bits per symbol.
Example: Four Symbols
Four symbols can be represented using two bits each:
| Symbol | Fixed-Length Code |
|---|---|
| A | 00 |
| B | 01 |
| C | 10 |
| D | 11 |
Every symbol uses exactly
\[ \boxed{2\text{ bits}}. \]Variable-Length Codes
A variable-length code allows different symbols to use different numbers of bits.
This becomes useful when some source symbols occur much more often than others.
Frequent symbols can receive shorter codewords.
Expected Code Length
If symbol \(i\) occurs with probability \(p_i\) and has codeword length \(\ell_i\), the expected code length is
\[ \boxed{ \bar L=\sum_i p_i\ell_i }. \]This is the long-run average number of bits used per source symbol under the model.
Example: Expected Code Length
Suppose:
| Symbol | Probability | Code Length |
|---|---|---|
| A | 0.50 | 1 |
| B | 0.25 | 2 |
| C | 0.125 | 3 |
| D | 0.125 | 3 |
Then
\[ \bar L = 0.50(1)+0.25(2)+0.125(3)+0.125(3). \] \[ =0.5+0.5+0.375+0.375. \] \[ \boxed{\bar L=1.75\text{ bits per symbol}}. \]Compression Comes from Unequal Probabilities
A fixed-length four-symbol code uses two bits per symbol.
The variable-length example uses only
\[ 1.75 \]bits per symbol on average.
The savings come from assigning the shortest codeword to the most probable symbol.
Decodability
A useful code must allow the receiver to determine which source-symbol sequence produced the encoded bit string.
Compression is not useful if different messages become impossible to distinguish.
Uniquely Decodable Codes
A code is uniquely decodable if every encoded message has only one valid decoding into source symbols.
Unique decodability is a fundamental requirement for ordinary lossless coding.
Prefix Codes
A prefix code is a code in which no codeword is the prefix of another codeword.
For example,
\[ 0,\qquad10,\qquad110,\qquad111 \]form a prefix code.
Why Prefix Codes Are Convenient
Prefix codes can be decoded from left to right without waiting for future bits to resolve an ambiguity.
As soon as a valid codeword is reached, the corresponding source symbol can be emitted.
This property is sometimes called instantaneous decodability.
Example: Decoding a Prefix Code
Use
| Symbol | Codeword |
|---|---|
| A | 0 |
| B | 10 |
| C | 110 |
| D | 111 |
Decode
\[ 010111. \]Read from left to right:
\[ 0\mid10\mid111. \]Therefore,
\[ \boxed{010111\longrightarrow ABD}. \]Binary Tree Representation
Prefix codes can be represented using binary trees.
Each left or right branch corresponds to a binary choice, often labeled \(0\) and \(1\).
Source symbols appear at leaves.
The depth of a leaf equals the length of its codeword.
Kraft's Inequality
For binary prefix-code lengths
\[ \ell_1,\ell_2,\ldots,\ell_n, \]Kraft's inequality requires
\[ \boxed{ \sum_{i=1}^{n}2^{-\ell_i}\le1 }. \]This gives a structural test for whether a collection of lengths can be realized by a binary prefix code.
Example: Check Kraft's Inequality
Consider lengths
\[ 1,\qquad2,\qquad3,\qquad3. \]Then
\[ 2^{-1}+2^{-2}+2^{-3}+2^{-3} \] \[ =\frac12+\frac14+\frac18+\frac18 \] \[ =\boxed{1}. \]These lengths exactly fill a binary prefix tree.
Entropy as a Compression Benchmark
For source probabilities \(p_i\), entropy is
\[ \boxed{ H(X)=-\sum_i p_i\log_2 p_i }. \]Entropy describes the fundamental average information content of the source.
Entropy and Average Code Length
For an optimal binary prefix code for a memoryless source, the expected code length can be chosen so that
\[ \boxed{ H(X)\le \bar L<H(X)+1 }. \]This places average code length close to the entropy limit.
Example: Entropy of the Four-Symbol Source
Use probabilities
\[ 0.5,\qquad0.25,\qquad0.125,\qquad0.125. \]Then
\[ H(X) = -0.5\log_2(0.5) -0.25\log_2(0.25) -2(0.125\log_2(0.125)). \] \[ =0.5+0.5+0.75. \] \[ \boxed{H(X)=1.75\text{ bits}}. \]The earlier prefix code also had average length \(1.75\), so it reaches the entropy exactly for this distribution.
Ideal Code Length
Self-information suggests an idealized code length
\[ \boxed{ \ell_i\approx-\log_2 p_i }. \]More probable symbols receive shorter ideal lengths.
Real binary codeword lengths must be integers, which is one reason average length may sit slightly above entropy.
Huffman Coding
Huffman coding is a constructive method for building an optimal binary prefix code when symbol probabilities or frequencies are known.
The method repeatedly combines the two least probable remaining items.
Basic Huffman Procedure
- List all symbols with their probabilities or frequencies.
- Select the two smallest values.
- Combine them into one node whose weight is their sum.
- Return that combined node to the list.
- Repeat until one root remains.
- Label branches \(0\) and \(1\).
- Read each symbol's codeword along the path from root to leaf.
Example: Huffman Inputs
Suppose
\[ P(A)=0.40,\qquad P(B)=0.30,\qquad P(C)=0.20,\qquad P(D)=0.10. \]The two smallest probabilities are
\[ 0.10\qquad\text{and}\qquad0.20. \]Combine them:
\[ 0.10+0.20=0.30. \]Continue the Huffman Construction
The remaining weights are
\[ 0.30,\qquad0.30,\qquad0.40. \]Combine two \(0.30\) nodes:
\[ 0.30+0.30=0.60. \]Finally combine
\[ 0.40+0.60=1. \]A valid resulting code can give lengths
\[ 1,\qquad2,\qquad3,\qquad3. \]Average Length of the Huffman Code
Using lengths
\[ \ell_A=1,\quad \ell_B=2,\quad \ell_C=3,\quad \ell_D=3, \]the expected length is
\[ \bar L = 0.40(1)+0.30(2)+0.20(3)+0.10(3). \] \[ =0.4+0.6+0.6+0.3. \] \[ \boxed{\bar L=1.9\text{ bits per symbol}}. \]Redundancy
One measure of coding redundancy is the gap between average code length and entropy:
\[ \boxed{ R=\bar L-H(X) }. \]Smaller redundancy means the code is closer to the entropy benchmark.
Coding Efficiency
A simple coding efficiency measure is
\[ \boxed{ \eta=\frac{H(X)}{\bar L} }. \]For a well-designed code,
\[ 0<\eta\le1. \]Efficiency closer to \(1\) means less average overhead relative to entropy.
Block Coding
Instead of encoding one source symbol at a time, we can encode blocks of several symbols together.
This allows code lengths to approximate ideal noninteger information values more closely on a per-symbol basis.
Example: Pairing Symbols
If individual source symbols are grouped into pairs, the code operates on outcomes such as
\[ AA,\ AB,\ AC,\ \ldots \]rather than on single symbols.
The block has more possible outcomes, but coding efficiency per original source symbol can improve.
Compression Ratio
A common practical measure is the compression ratio.
One convention is
\[ \boxed{ \text{Compression Ratio} = \frac{\text{Original Size}}{\text{Compressed Size}} }. \]A ratio of \(4\) means the original representation is four times as large as the compressed one.
Space Savings
Another common measure is the fraction of storage eliminated:
\[ \boxed{ \text{Savings} = 1- \frac{\text{Compressed Size}}{\text{Original Size}} }. \]Multiplying by \(100\%\) expresses the savings as a percentage.
Example: Compression Ratio and Savings
Suppose a file decreases from \(800\) MB to \(200\) MB.
The compression ratio is
\[ \frac{800}{200}=4. \]The savings are
\[ 1-\frac{200}{800} =1-0.25 =0.75. \]Therefore,
\[ \boxed{75\%\text{ space savings}}. \]Lossless Compression
Lossless compression preserves enough information to reconstruct the original data exactly.
It is appropriate when exact recovery matters, such as:
- program code;
- text;
- financial records;
- scientific data requiring exact preservation;
- archival data where no alteration is acceptable.
Lossy Compression
Lossy compression deliberately discards some information in exchange for a smaller representation.
The decoded output approximates the original rather than reproducing it exactly.
Why Lossy Compression Can Work
Not every feature of a signal may matter equally.
A compression system may discard details that are:
- perceptually insignificant;
- redundant;
- below measurement precision;
- unnecessary for the intended task.
The acceptable amount of loss depends on the application.
Distortion
Lossy compression requires a way to measure how different the reconstruction is from the original.
A distortion measure may be written
\[ \boxed{d(x,\hat x)}. \]Smaller distortion means the reconstruction is closer to the source under the chosen measure.
Rate-Distortion Tradeoff
Lossy compression balances two competing goals:
- use fewer bits;
- preserve higher fidelity.
Lower bit rate generally requires accepting more distortion.
This tradeoff is formalized in rate-distortion theory.
Compression Depends on Structure
Data can be compressed when their representation contains predictable or repeated structure.
Useful structure may include:
- unequal symbol frequencies;
- repeated sequences;
- correlation between neighboring values;
- patterns that can be modeled more compactly.
Highly Random Data Are Hard to Compress
When a sequence behaves like a high-entropy source with little exploitable structure, lossless compression opportunities become limited.
Compression does not create predictability that is absent from the source.
Run-Length Encoding
A simple compression idea is run-length encoding.
Repeated symbols are replaced by a symbol and a count.
For example,
\[ AAAAAABB \]may be represented conceptually as
\[ A6B2. \]This is effective when long repeated runs occur frequently.
Dictionary-Based Compression
Dictionary methods replace repeated strings or patterns with shorter references to previously stored entries.
The general idea is to avoid retransmitting the same structure repeatedly.
Predictive Coding
If neighboring values are strongly related, it can be more efficient to encode prediction errors than raw values.
Instead of coding
\[ x_t, \]code the residual
\[ e_t=x_t-\hat x_t. \]If predictions are good, residuals may have lower entropy.
Compression and Probability Models
Good compression depends on assigning short representations to events the model regards as probable.
Poor probability models can lead to inefficient codes.
This connects coding directly to cross-entropy and log loss.
Cross-Entropy and Coding Cost
If the true distribution is \(p\) but a code is designed according to model \(q\), the expected idealized coding cost is related to
\[ \boxed{ H(p,q) = -\sum_x p(x)\log_2 q(x) }. \]Using the wrong probability model increases expected coding length.
KL Divergence as Extra Coding Cost
Since
\[ H(p,q)=H(p)+D_{\mathrm{KL}}(p\|q), \]the KL divergence measures the additional idealized coding cost caused by using \(q\) rather than the true distribution \(p\).
Compression and Decision Making
Compression is not only a storage problem.
Decisions may depend on:
- how much information can be transmitted;
- how quickly it can be transmitted;
- which details are preserved;
- which details are discarded;
- how errors affect downstream actions.
Loss Functions Matter in Lossy Compression
A lossy system must decide which differences between original and reconstruction matter most.
That choice is encoded by a distortion or loss function.
Two compression systems can produce the same file size while optimizing different notions of fidelity.
Common Error: Assigning Short Codes to Rare Symbols
If a rare symbol receives a very short codeword while a common symbol receives a long one, average code length may increase.
Efficient variable-length coding generally gives shorter codewords to more probable symbols.
Common Error: Ignoring Decodability
Short codewords are useless if the resulting encoded stream cannot be decoded uniquely.
Efficiency and decodability must be satisfied together.
Common Error: Confusing Code Length with Information Content
A codeword length is an integer number of symbols or bits in a specific code.
Self-information
\[ -\log_2 p \]can be noninteger.
The two are related, but they are not identical.
Common Error: Expecting Every File to Compress
Some data are already compressed or contain little exploitable redundancy.
Applying another lossless compressor can yield little improvement and may even increase the file size because metadata must also be stored.
Common Error: Comparing Compression Ratios with Different Conventions
Some sources define compression ratio as
\[ \frac{\text{Original}}{\text{Compressed}}, \]while others report
\[ \frac{\text{Compressed}}{\text{Original}}. \]Always state the convention being used.
Common Error: Treating Lossy Compression as Automatically Inferior
Lossy compression is not inherently bad.
It is appropriate when exact recovery is unnecessary and substantial size reduction is more valuable than preserving every detail.
The key question is whether the discarded information matters for the intended use.
A Reliable Procedure for Evaluating a Code
- List the source symbols and their probabilities.
- Record the codeword assigned to each symbol.
- Check whether decoding is unambiguous.
- Check the prefix property when a prefix code is intended.
- Find each codeword length.
- Compute expected code length.
- Compute source entropy.
- Compare average length with the entropy benchmark.
- Compute redundancy or efficiency if useful.
A Reliable Procedure for Compression Decisions
- Determine whether exact reconstruction is required.
- Identify repeated or predictable structure in the data.
- Choose a lossless or lossy method appropriate to the application.
- Define the relevant distortion or error criterion when loss is allowed.
- Measure compressed size and reconstruction quality.
- Include processing, latency, and storage constraints where relevant.
- Compare the compression benefit with the cost of lost information.
Practice 1: Fixed-Length Coding
How many bits are needed per symbol in a binary fixed-length code for eight possible symbols?
Practice 2: Expected Code Length
Two symbols have probabilities
\[ 0.75,\qquad0.25 \]and codeword lengths
\[ 1,\qquad3. \]Find the expected code length.
Practice 3: Kraft's Inequality
Check whether lengths
\[ 1,\qquad2,\qquad2 \]satisfy Kraft's inequality for a binary prefix code.
Practice 4: Entropy Benchmark
A source has entropy
\[ H(X)=2.4 \]bits and a code has average length
\[ \bar L=2.7. \]Find the redundancy
\[ \bar L-H(X). \]Practice 5: Coding Efficiency
Using Practice 4, find
\[ \eta=\frac{H(X)}{\bar L}. \]Practice 6: Compression Ratio
A file decreases from \(900\) MB to \(300\) MB.
Using
\[ \frac{\text{Original Size}}{\text{Compressed Size}}, \]find the compression ratio.
Practice 7: Space Savings
Using the sizes from Practice 6, find the percentage space savings.
Practice 8: Lossless or Lossy?
A database backup must be restored bit-for-bit exactly.
Should the compression method be lossless or lossy?
Practice 9: Prefix-Code Decoding
Use
| Symbol | Codeword |
|---|---|
| A | 0 |
| B | 10 |
| C | 110 |
| D | 111 |
Decode
\[ 110010. \]Practice 10: Ideal Code Length
A symbol has probability
\[ p=\frac18. \]Find its ideal information-based code length
\[ -\log_2 p. \]Practice Answers
Practice 1
\[ \log_2 8=3. \]Therefore,
\[ \boxed{3\text{ bits per symbol}}. \]Practice 2
\[ \bar L = 0.75(1)+0.25(3) \] \[ =0.75+0.75 \] \[ \boxed{1.5\text{ bits per symbol}}. \]Practice 3
\[ 2^{-1}+2^{-2}+2^{-2} \] \[ =\frac12+\frac14+\frac14 \] \[ =1. \]Therefore the lengths satisfy Kraft's inequality:
\[ \boxed{\text{yes}}. \]Practice 4
\[ R=2.7-2.4 \] \[ \boxed{0.3\text{ bits per symbol}}. \]Practice 5
\[ \eta=\frac{2.4}{2.7} \] \[ \approx0.889. \]Therefore,
\[ \boxed{\eta\approx88.9\%}. \]Practice 6
\[ \frac{900}{300} \] \[ =\boxed{3}. \]Practice 7
\[ 1-\frac{300}{900} \] \[ =1-\frac13 \] \[ =\frac23. \]Therefore,
\[ \boxed{66.7\%\text{ savings approximately}}. \]Practice 8
Exact reconstruction is required, so use
\[ \boxed{\text{lossless compression}}. \]Practice 9
Parse the bits as
\[ 110\mid0\mid10. \]Therefore,
\[ \boxed{110010\longrightarrow CAB}. \]Practice 10
\[ -\log_2\left(\frac18\right) \] \[ =\boxed{3\text{ bits}}. \]What to Remember
Coding and compression turn probability structure into more efficient representations.
- Codes map source symbols to codewords.
- Fixed-length codes use the same number of bits for every symbol.
- Variable-length codes can exploit unequal symbol probabilities.
- Expected code length is the probability-weighted average codeword length.
- Prefix codes allow immediate unambiguous decoding.
- Kraft's inequality constrains valid prefix-code lengths.
- Entropy provides a fundamental benchmark for average lossless code length.
- Huffman coding constructs optimal binary prefix codes for known symbol probabilities.
- Lossless compression preserves exact reconstruction.
- Lossy compression trades fidelity for smaller representation.
The key principle is: efficient codes spend the shortest representations on the most probable or most predictable information.
Where We Go Next
Coding theory shows how probability and entropy govern efficient representation. The next lesson returns to uncertain systems themselves and asks how likely they are to continue functioning.
The next lesson, Reliability and Failure Probability, develops mathematical models for component reliability, system failure, series and parallel structures, and the probability that systems remain operational.