ELEC1010 Chap.9 Source Coding and Compression
Source Coding and Compression
Use probability without losing decodability
A fixed-length code assigns the same number of bits to every source symbol. It is simple to parse but ignores unequal probabilities. A variable-length code can reduce average length by assigning short words to common symbols and longer words to rare symbols.
The saving must be calculated as the probability-weighted average codeword length, not by inspecting the shortest word alone.
Decodability constrains which words may be combined. In a prefix code, no valid codeword begins another, so the decoder can stop as soon as it reaches a leaf. Distinct codewords are not enough if one can be mistaken for the start of a longer word.
Test a proposed set by comparing every short word with the beginnings of all longer words.
Huffman coding builds a prefix tree by repeatedly combining the two smallest current probabilities. Replace that pair with their sum, re-sort the current weights, and continue until one root remains.
Assigning zero and one to left and right branches is conventional; reversing branch labels changes the bit patterns but not their lengths or average performance.
Audit the finished tree in three ways. Every source symbol should occupy one leaf, the leaf probabilities should sum to one, and the weighted average length should be no smaller than the entropy lower bound. Compare the result with a fixed-length baseline.
A tree that looks balanced can still be inefficient if it gives a frequent symbol an unnecessarily deep path.
Lossless compression permits exact reconstruction of the original symbols. Lossy compression deliberately discards selected information to obtain a greater size reduction.
In image, audio or video systems, transforms, prediction and perceptual models expose redundancy, while quantization is commonly the irreversible stage. Entropy coding can then compress the resulting symbols without introducing additional loss.
Revision should combine construction and decoding.
Build a tree from probabilities, encode a short message, decode a concatenated stream, and compute average length in one exercise. Then identify the irreversible step in a media pipeline and distinguish compression ratio from reconstruction fidelity. This keeps source coding, probability, prefix structure and perceptual loss connected without treating all smaller files as equivalent.
What this chapter covers
- 01
Fixed-length code baseline
- 02
Prefix-code condition
- 03
Huffman merging
- 04
Average code length
- 05
Lossless and lossy contracts
- 06
JPEG and MPEG stages
Worked example · free
Construct a Huffman code
- 5Combine the two least likely items repeatedly.
- 3Assign branch bits and list codes.
- 4Calculate probability-weighted length.
Key terms
- Source Coding
- Representation designed to use bits efficiently for source information.
- Prefix Code
- A code in which no valid word begins another valid word.
- Huffman Code
- A prefix code built from repeated least-probability merges.
- Lossless Compression
- Compression that reconstructs the exact original data.
- Lossy Compression
- Compression that discards selected information for greater size reduction.
Source Coding and Compression FAQ
Why must codewords end at leaves?
A leaf marks a complete symbol. If a valid codeword stopped at an internal node, it would begin every descendant word and create ambiguity in the concatenated stream.
Can different Huffman trees be equally good?
Yes. Equal-probability merges or swapped branch labels can create different codewords with the same length pattern and average. Efficiency depends on depths, not on whether a branch is called zero or one.
Which step makes JPEG lossy?
Quantizing or rounding transformed coefficients discards precision. The transform can be reversible before that step, and later Huffman coding is also reversible for the symbols it receives.
Can two different Huffman trees both be valid?
Yes. Swapping left and right labels or resolving equal weights differently can change the bit patterns while preserving codeword lengths, the prefix property and the same average length.
Exam move
Build a tree, decode a stream with it, and calculate its average length in one sitting. Compare that result with a fixed-length baseline and the entropy lower bound. For media compression, label transform, quantization, prediction and entropy coding separately so the exact irreversible stage remains visible. Audit a code before praising its compression.
Verify the prefix property, decode a concatenated test stream and calculate probability-weighted average length. A short word for one common symbol is not enough if another assignment creates ambiguity or increases the overall average. For a media pipeline, add a reversibility audit: identify which stage discards information and which later stage only codes symbols more compactly.
This explains why entropy coding can be lossless even when the complete JPEG or MPEG process is lossy, and why file size alone cannot establish reconstruction quality.
Working through Source Coding and Compression in ELEC1010? Sia is AskSia’s AI Electrical Engineering tutor — ask any ELEC1010 Source Coding and Compression question and get a clear, step-by-step explanation grounded in how ELEC1010 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.