The Hong Kong University of Science and Technology · FACULTY OF ELECTRICAL ENGINEERING

ELEC1010 Chap.9 Source Coding and Compression

- one subject, every graph, every model, every mark
6 Chapters4-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 9 of 10 · ELEC1010

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.

In this chapter

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

Q [12 marks]. Symbols have probabilities 0.4, 0.3, 0.2 and 0.1. Build one Huffman tree and calculate average length. The marks shown are an AskSia study allocation, not the University's published marking scheme.
A prefix tree makes the boundary rule visible.A prefix tree makes the boundary rule visible. The common symbol A uses one branch, while B and C use two, and every valid codeword ends at a leaf.Common symbols sit closer to the rootA: 0B: 10C: 110101no leaf codebegins another
A prefix tree makes the boundary rule visible. The common symbol A uses one branch, while B and C use two, and every valid codeword ends at a leaf.
  • 5Combine the two least likely items repeatedly.
  • 3Assign branch bits and list codes.
  • 4Calculate probability-weighted length.
One valid code is A=0, B=10, C=110 and D=111. The weighted average is 0.4x1 + 0.3x2 + 0.2x3 + 0.1x3 = 1.9 bits per symbol.
Sia tip — Finish the probability tree before writing zero and one labels on its branches.
Glossary

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.
FAQ

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.

Study strategy

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.

A+Everything unlocked
Unlocks this Bible + all 13 of your subjects at The Hong Kong University of Science and Technology, plus 1,000+ more Bibles across the AskSia library.
Sia - your ELEC1010 tutor, unlimited, worked the way the exam marks it
The full 4-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works