Source Coding

Source Coding: Compressing Information to Its Essence

Source coding — also called data compression — is the process of representing information using fewer bits than the original representation, by removing redundancy from the data. Every time you send a WhatsApp photo, stream Netflix, or download a ZIP file, source coding is working behind the scenes to save bandwidth and storage. It is the practical application of Shannon's insight that most real-world data contains far more bits than actually needed to represent the information.

The Fundamental Goal

Think of it this way: if you need to describe a white wall, you do not say "white pixel, white pixel, white pixel..." a million times. You simply say "all white." Source coding finds these patterns and shortcuts in data, expressing the same information more concisely.

Shannon's Source Coding Theorem establishes the absolute limit:

No lossless compression can achieve an average rate below H(X) bits per source symbol.

Where H(X) is the source entropy. Conversely, rates arbitrarily close to H(X) are achievable with sufficiently clever codes.

Lossless vs. Lossy Compression

Lossless compression: The original data is perfectly reconstructed from the compressed version. Not a single bit is lost.

• Used for: text, code, databases, medical images, executables
• Algorithms: Huffman, arithmetic coding, LZ77/LZ78, DEFLATE, bzip2
• Typical ratios: 2:1 to 5:1

Lossy compression: Some information is permanently discarded, accepting controlled quality loss for much higher compression.

• Used for: photos, video, audio, streaming media
• Algorithms: JPEG, HEVC/H.265, MP3/AAC, Opus
• Typical ratios: 10:1 to 100:1

The choice depends on whether the application can tolerate any distortion. You cannot lossy-compress a bank's database, but you can lossy-compress a cat video.

Lossless Compression Techniques

1. Entropy Coding (Variable-Length Codes) Assigns shorter codes to frequent symbols, longer codes to rare ones:

• Huffman coding: Optimal prefix code for known probabilities
• Arithmetic coding: Achieves fractional bits per symbol, truly optimal
• ANS (Asymmetric Numeral Systems): Modern alternative to arithmetic coding

2. Dictionary Methods (LZ Family) Replaces repeated patterns with references to earlier occurrences:

• LZ77: Sliding window, back-references (used in gzip, DEFLATE)
• LZ78/LZW: Builds dictionary on-the-fly (used in GIF)
• Achieves compression without knowing source statistics in advance

3. Transform Methods Transform data to expose redundancy, then entropy code:

• Burrows-Wheeler Transform (BWT): Rearranges data for better compression (bzip2)
• Move-to-Front: Converts spatial locality to frequency skew
• Run-Length Encoding: Compresses sequences of identical symbols

4. Prediction + Residual Coding Predict the next value, then code only the prediction error:

• DPCM: Differential coding of audio/image samples
• PPM: Prediction by Partial Matching (text compression)
• LZMA: Sophisticated prediction + range coding (7-zip, xz)

Lossy Compression: Rate-Distortion Theory

Shannon's Rate-Distortion Theory provides the theoretical framework for lossy compression:

R(D) = minimum bit rate to achieve distortion ≤ D

The rate-distortion function defines the trade-off: less distortion requires more bits.

For a Gaussian source with variance σ²:

• R(D) = (1/2) × log₂(σ²/D) for D ≤ σ²
• R(D) = 0 for D > σ²

Lossy Compression Techniques

Transform Coding (JPEG, HEVC):

1. Divide image/frame into blocks
2. Apply transform (DCT, wavelet) to concentrate energy into few coefficients
3. Quantize coefficients (this is where information is lost)
4. Entropy code the quantized values

Predictive Coding (ADPCM, G.726):

1. Predict current sample from previous samples
2. Quantize the prediction error (smaller dynamic range = fewer bits)
3. Adaptive step size tracks signal dynamics

Analysis/Synthesis (CELP, LPC vocoders):

1. Analyze input to extract parameters (pitch, formants, energy)
2. Transmit only parameters (very compact)
3. Receiver synthesizes signal from parameters
4. Used in speech coding (8 kbps → toll quality speech)

Source Coding in Communication Systems

In a complete communication system, source coding is the FIRST processing step:

Source → Source Encoder → Channel Encoder → Modulator → Channel → ...

Source coding output should be:

• As compact as possible (approach entropy)
• Free of exploitable redundancy (otherwise channel coding efficiency drops)
• The output bits appear random and equally likely to be 0 or 1

This last point is important: a well-compressed signal looks like random noise — no patterns left to exploit. Any remaining redundancy represents wasted channel bandwidth.

Joint Source-Channel Coding

Shannon's separation theorem says that separate source and channel coding is optimal (no loss from separating them). However, in practice:

• Joint design can reduce latency (important for real-time communication)
• Unequal error protection: More important bits get stronger coding
• Graceful degradation: Quality degrades smoothly as channel worsens

Practical Examples

MP3 Audio Compression:

• Input: 1411 kbps (CD audio: 44.1 kHz, 16 bit, stereo)
• Output: 128-320 kbps (10-90% compression)
• Technique: Psychoacoustic model + MDCT + Huffman
• Exploits: Human hearing limitations (masking, frequency sensitivity)

H.265/HEVC Video:

• Input: 1.5 Gbps (4K raw video)
• Output: 5-20 Mbps (99% compression!)
• Technique: Motion prediction + DCT + entropy coding
• Exploits: Temporal redundancy (frames are similar) + spatial redundancy

Key Takeaways

1. Source coding removes redundancy to represent information with minimum bits — the entropy H(X) is the absolute lower bound for lossless compression.
2. Lossless coding preserves all information using entropy codes (Huffman, arithmetic) and dictionary methods (LZ77) — typical ratios 2:1 to 5:1.
3. Lossy coding accepts controlled distortion for dramatic compression (10:1 to 100:1) using transforms, quantization, and perceptual models.
4. Rate-distortion theory R(D) defines the fundamental trade-off between bit rate and quality in lossy compression.
5. Well-compressed output appears random (maximum entropy) — no exploitable patterns remain for further compression.
6. Source coding is always the first step in a communication system, reducing data to its essential information before channel coding adds protective redundancy.