Coding and Compression Principles
What this domain tests
Why compression is possible at all, the families of technique, and the metrics used to judge them. Items ask you to compute entropy or a compression ratio, choose an appropriate coder for a data type, or explain where a hybrid codec puts its loss.
Core rules and concepts
- Information entropy H = −Σ p·log2 p gives the minimum average bits per symbol for a source with independent symbols. Redundancy is the gap between the raw and entropy-based rate; compression exploits statistical redundancy, perceptual irrelevance, or both.
- Lossless techniques: run-length encoding for repeated runs (fax, bitmap regions); Huffman coding, an optimal prefix code when code lengths must be integers; arithmetic coding, which assigns fractional bits and approaches entropy; dictionary methods such as LZW (used in GIF and TIFF); predictive coding (DPCM) for smooth signals.
- Lossy techniques: transform coding (DCT, wavelet) concentrating energy into few coefficients; quantisation, which is the only intentionally irreversible step in most standards; perceptual coding exploiting psychoacoustic masking and the absolute threshold of hearing, or contrast-sensitivity limits for images; subband decomposition; motion compensation for video.
- Practical architecture is hybrid: prediction (DPCM or motion compensation) followed by a transform, quantisation and entropy coding.
- Metrics: compression ratio, output bit rate, PSNR = 10·log10(255²/MSE) for 8-bit data, and SSIM for structural similarity. Codecs are also classed as symmetric/asymmetric and scalable in SNR, spatial or temporal layers.
Worked example
Source symbols A, B, C, D with probabilities 0.5, 0.25, 0.125, 0.125. Entropy = 0.5+0.5+0.375+0.375 = 1.75 bits/symbol. Huffman construction: merge C and D (0.25), merge that node with B (0.5), merge with A (1.0). Codes A=0, B=10, C=110, D=111 give an average length of 1×0.5 + 2×0.25 + 3×0.125 + 3×0.125 = 1.75 bits, exactly the entropy. Against a fixed 2-bit code the ratio is 2 : 1.75 ≈ 1.14, a modest but real gain - the answer to "why only 14%?" is that the distribution is close to uniform over four symbols.
Traps that cost marks
- Claiming a lossless coder can beat entropy; it cannot, only approach it.
- Confusing compression ratio definitions: original/compressed versus the saving percentage.
- Assuming high PSNR guarantees good perceived quality; blurring can raise PSNR while looking worse.
- Forgetting that quantisation, not the transform, destroys information.