Redundancy and Efficiency

Redundancy and Efficiency: What Makes Compression Possible

Every time you compress a file, stream a video, or make a phone call, you are exploiting redundancy — predictable patterns in data that can be removed without losing information. Redundancy is the gap between the maximum possible information a source could carry and the information it actually carries. Understanding redundancy explains why ZIP files are smaller than originals, why JPEG compresses photos, and why you can usually predict the next word in a sentence.

What Is Redundancy?

Think of it this way: imagine a book written using only the letter "A" repeated 100,000 times. Despite being a large book, it carries almost zero information because every letter is perfectly predictable. The book is almost entirely redundant — you only need to say "A repeated 100,000 times" to capture all its information in a few bytes.

Now imagine a book where each letter is chosen by rolling a 26-sided die. This book has zero redundancy — no pattern, no prediction possible, no compression possible. Every letter must be stored explicitly.

Real data falls between these extremes. The redundancy measures where on this spectrum a source lies.

Mathematical Definition

For a source producing symbols from an alphabet of size N:

Maximum possible entropy: Hmax = log₂(N) bits/symbol (achieved when all N symbols are equally likely)

Actual source entropy: H(X) = -Σ p(xᵢ) log₂(p(xᵢ))

Absolute redundancy: D = Hmax - H(X) bits/symbol

Relative redundancy: r = D/Hmax = 1 - H(X)/Hmax

Coding efficiency: η = H(X)/Hmax = 1 - r

Example: English alphabet (26 letters):

• Hmax = log₂(26) = 4.70 bits/letter
• Actual entropy (accounting for letter frequencies): H ≈ 4.03 bits/letter
• With digram statistics: H ≈ 3.32 bits/letter
• Full language model (sequences): H ≈ 1.0-1.5 bits/letter
• Redundancy: r ≈ 1 - 1.3/4.7 ≈ 72%

This means approximately 72% of English text is redundant — which is why English text compresses to about 25-30% of its original size.

Sources of Redundancy

1. Unequal Symbol Probabilities When some symbols are more likely than others, the source has lower entropy than maximum. In English: E(12.7%), T(9.1%), A(8.2%) vs. Z(0.07%), Q(0.10%).

Compression technique: Huffman coding, arithmetic coding (assign shorter codes to frequent symbols)

2. Sequential Dependencies (Correlation) In most real sources, the next symbol is partially predictable from previous symbols. In English: after "Q" almost certainly comes "U"; after "TH" likely comes "E" or "A."

Compression technique: Predictive coding, Markov models, LZ77/LZ78 dictionary methods

3. Structural Patterns Data often has repetitive structure: headers in files, repeated phrases in text, periodic patterns in signals.

Compression technique: Run-length encoding, pattern matching, template subtraction

Coding Efficiency

When we encode a source using a particular code, the coding efficiency measures how well we exploit available redundancy:

Coding efficiency: η_code = H(X) / L̄

Where L̄ is the average codeword length of the actual code used.

Example: Source with entropy H = 2.5 bits/symbol:

• Fixed-length code using 3 bits/symbol: η = 2.5/3 = 83%
• Huffman code achieving L̄ = 2.6 bits/symbol: η = 2.5/2.6 = 96%
• Arithmetic coding achieving L̄ = 2.51 bits/symbol: η = 2.5/2.51 = 99.6%

The source coding theorem guarantees that no lossless code can achieve L̄ < H(X), making entropy the absolute efficiency ceiling.

Redundancy in Different Sources

Why Some Redundancy Is Intentionally Added

While source coding removes redundancy to save bandwidth, channel coding deliberately adds it back:

Source coding (compression): Removes natural redundancy → minimum bit rate Channel coding (FEC): Adds structured redundancy → enables error correction

The total system first removes inefficient natural redundancy, then adds back efficient engineered redundancy. The result is a signal that is both compact and robust.

Practical Implications

Compression ratios: The maximum achievable compression ratio for lossless coding is approximately:

• Ratio = 1/η = Hmax/H(X) = 1/(1-r)
• For English (r ≈ 0.72): maximum ratio ≈ 3.6:1
• For speech (r ≈ 0.75): maximum ratio ≈ 4:1

Communication bandwidth: A 64 kbps PCM voice channel can be compressed to approximately 8-16 kbps using redundancy removal — enabling 4-8× more calls on the same bandwidth.

Storage: A raw 700 MB CD audio can be compressed to ~200 MB (FLAC lossless) or ~50 MB (MP3 lossy) by exploiting redundancy in music.

Measuring Redundancy in Practice

Practical methods to estimate source redundancy:

1. Compression test: Apply a strong compressor (gzip, bzip2) — compression ratio estimates redundancy
2. N-gram statistics: Compute letter/word frequencies and conditional probabilities
3. Prediction game: Have humans predict next characters; their success rate indicates redundancy
4. Entropy estimation: Compute empirical entropy at various context depths

Key Takeaways

1. Redundancy is the gap between maximum possible entropy (log₂N) and actual source entropy — it represents predictable, compressible content.
2. English text is approximately 72% redundant, which is why text compresses to about 25-30% of original size.
3. Coding efficiency η = H/L̄ measures how close a code comes to the theoretical entropy limit.
4. Sources of redundancy include unequal probabilities, sequential dependencies, and structural patterns — each exploited by different compression algorithms.
5. Source coding removes redundancy to minimize bit rate; channel coding adds structured redundancy for error protection — opposite goals serving the same system.
6. The maximum lossless compression ratio is approximately 1/(1-r), making redundancy measurement directly predictive of achievable compression.