Technopedia

The technologist’s encyclopedia

Compression

Compression reduces the number of bits needed to represent data, either losslessly (exact reconstruction) or lossily (controlled distortion). It is relevant whenever storage or bandwidth is limited: text and binaries on disk, images, audio, video. Compression and channel coding are complementary stages: compression removes the redundancy the source contains, while channel coding (see Communication) adds controlled redundancy to protect the remaining bits from noise.

Authoritative sources

Lossless compression

The source coding theorem (Shannon, 1948) states that no lossless code can have expected length below the entropy HH of the source, and this bound is asymptotically achievable. All the algorithms below approach this fundamental limit. See Coding and entropy for the full statement and proof.

Run-length encoding (RLE): replace runs of identical symbols with a count. AAAAABBBCC→5A  3B  2CAAAAABBBCC \to 5A\;3B\;2C. Effective for data with long runs; expands data with no runs.

LZ77 (backreference): replace repeated substrings with a (offset, length) pair pointing to the previous occurrence. Sliding window of size WW; maximum match length LL. Basis of DEFLATE, gzip, zstd, Brotli.

LZW (dictionary): build a dictionary of previously seen strings; emit dictionary indices. The dictionary grows during encoding. Used in GIF, TIFF.

Huffman coding: assign shorter codewords to more probable symbols. Optimal among prefix-free codes for a known distribution (see Coding and entropy). Used in JPEG, MP3, DEFLATE.

DEFLATE (RFC 1951): combines LZ77 (backreferences) with Huffman coding. The basis of gzip, ZIP, PNG.

Arithmetic coding: encodes the entire message as a single fraction in [0,1)[0,1) whose interval shrinks by the probability of each symbol. Achieves entropy more closely than Huffman (which is limited to integer bit lengths).

Modern general-purpose formats: bzip2 applies the Burrows–Wheeler transform (a reversible permutation that clusters repeated contexts into runs) before entropy coding — strong ratio, slow. zstd (RFC 8878) pairs LZ77-style matching with FSE (finite-state entropy, an arithmetic-coding relative) and Huffman coding, tuned for very high speed. Brotli (RFC 7932) adds a built-in static dictionary of common web strings to a DEFLATE-like core, for HTTP content encoding.

Details

LZ77 example: encoding “ABRACADABRA” with window W=12W = 12, max match L=4L = 4, minimum match 3:

A backreference may overlap the lookahead: “AAAAAA” encodes as A then (1, 4), because the match source keeps re-reading the just-written As. Try it in the interactive LZ77 matcher below.

Huffman construction: repeatedly merge the two least-probable symbols until one node remains. The depth of each leaf is its codeword length. For probabilities A 0.4, B 0.3, C 0.15, D 0.1, E 0.05: merge E+D → 0.15, then 0.15+C → 0.30, then 0.30+B → 0.60, then 0.60+A → 1.0.

01 01 01 01 1.00A 0.60B 0.30C 0.15D E

Codewords: A = 0, B = 10, C = 110, D = 1110, E = 1111. Expected length L=0.4⋅1+0.3⋅2+0.15⋅3+0.1⋅4+0.05⋅4=1.95L = 0.4 \cdot 1 + 0.3 \cdot 2 + 0.15 \cdot 3 + 0.1 \cdot 4 + 0.05 \cdot 4 = 1.95 bits, against an entropy H≈1.92H \approx 1.92 bits — the gap is under 1 bit because Huffman cannot use fractional lengths.

Arithmetic coding example: with p(A)=p(B)=0.5p(A) = p(B) = 0.5, start with the interval [0,1)[0,1). Encoding A shrinks it to [0,0.5)[0, 0.5); encoding B shrinks it to its second half, [0.25,0.5)[0.25, 0.5). Any value in [0.25,0.5)[0.25, 0.5) — say 0.375 = binary 0.011 — decodes to “AB”. The interval width is 0.250.25, i.e. −log⁡20.25=2-\log_2 0.25 = 2 bits of information, and the 3 emitted bits come within the usual sub-bit overhead.

Authoritative source: RFC 1951 (DEFLATE: LZ77 + Huffman as used in gzip, ZIP, PNG).

Example problem

Build the Huffman code for the distribution A 0.5, B 0.25, C 0.125, D 0.125. What is the expected code length, and how does it compare to the entropy?

Solution

Merge D+C → 0.25, then 0.25+B → 0.5, then 0.5+A → 1.0. Codewords: A = 0, B = 10, C = 110, D = 111. Expected length L=0.5⋅1+0.25⋅2+0.125⋅3+0.125⋅3=1.75L = 0.5 \cdot 1 + 0.25 \cdot 2 + 0.125 \cdot 3 + 0.125 \cdot 3 = 1.75 bits. The entropy is H=−(0.5log⁡20.5+0.25log⁡20.25+2⋅0.125log⁡20.125)=1.75H = -(0.5\log_2 0.5 + 0.25\log_2 0.25 + 2 \cdot 0.125\log_2 0.125) = 1.75 bits: the distribution is dyadic (every probability is a power of 1/21/2), so Huffman reaches the entropy exactly.

Lossy compression: the common pattern

All lossy codecs follow the same three-stage structure:

  1. Transform — rewrite the signal in a domain where perception is simple (spatial frequencies for images, time–frequency for audio). Reversible: no information is lost.
  2. Quantize — round each coefficient to a multiple of a step size, using a perceptual model to choose coarse steps where the senses are insensitive. This is the only lossy stage: it discards information below the perceptual threshold.
  3. Entropy-code — compress the quantized coefficients losslessly (Huffman, arithmetic, or run-length + Huffman), exploiting the many zeros the quantizer produced.
only stage 2 discards information — stages 1 and 3 are reversible 1 · Transform signal → perceptual domain 2 · Quantize discard below perceptual threshold 3 · Entropy-code lossless, exploits the zeros

The sections below differ only in the transform (DCT for images, MDCT for audio, DCT + motion compensation for video) and the perceptual model (visual vs. auditory masking).

Details

Worked mini-example: take a 2-sample block of pixel values [64,72][64, 72] and run it through the three stages with a toy transform (the Haar step, which is the simplest orthogonal transform: it replaces a pair by its scaled sum and scaled difference).

  1. Transform: a=(64+72)/2≈95.2a = (64+72)/\sqrt{2} \approx 95.2 (the average, i.e. the DC term) and d=(64−72)/2≈−5.7d = (64-72)/\sqrt{2} \approx -5.7 (the detail, i.e. the AC term). All the energy now sits in one coefficient.
  2. Quantize: keep aa exactly, but divide dd by the step 16 and round: −5.7/16≈−0.35→0-5.7 / 16 \approx -0.35 \to 0. The detail is discarded — the eye barely notices a 4-level difference inside a smooth pair.
  3. Entropy-code: emit aa (~7 bits) plus a 1-bit flag “AC = 0”, instead of the raw 16 bits.
  4. Decode: invert the transform with d=0d = 0: both samples become a/2≈68a/\sqrt{2} \approx 68. Error: 4 per sample, invisible on a smooth gradient.

This is exactly what JPEG does to an 8×8 block, and what MP3 does to a frame of audio — only the transform and the perceptual model change.

Authoritative source: ITU-T T.81 (JPEG) — the canonical instance of the three-stage pattern.

Example problem

Run the same pipeline on the block [64,96][64, 96] with quantization step 16 on the AC term. What are the transformed coefficients, the quantized AC value, and the decoded samples?

Solution

Transform: a=160/2≈113.1a = 160/\sqrt{2} \approx 113.1, d=(64−96)/2≈−22.6d = (64-96)/\sqrt{2} \approx -22.6. Quantize: −22.6/16≈−1.41→−1-22.6/16 \approx -1.41 \to -1, dequantized d′=−16d' = -16. Decode: x0=(a+d′)/2≈68.7x_0 = (a + d')/\sqrt{2} \approx 68.7, x1=(a−d′)/2≈91.3x_1 = (a - d')/\sqrt{2} \approx 91.3. Both samples are off by ≈ 4.3 — the quantization error of 16−22.6=6.616 - 22.6 = 6.6 in the AC term, split evenly across the pair by the inverse transform.

Lossy image compression

An image is a 2D array of pixels, each with RGB (or YCbCr) values. Lossy compression exploits the fact that the human visual system is insensitive to high-frequency spatial detail.

Pipeline (JPEG):

RGB→YCbCr 4:2:0 chroma 8×8 blocks DCT Quantize Huffman bitstream
  1. Convert RGB → YCbCr (luma + chroma).
  2. Downsample chroma (4:2:0: quarter the chroma resolution).
  3. Split into 8×8 blocks.
  4. Apply DCT (Discrete Cosine Transform) to each block: F(u,v)=14C(u)C(v)∑x=07∑y=07f(x,y)cos⁡(2x+1)uπ16cos⁡(2y+1)vπ16F(u,v) = \frac{1}{4} C(u) C(v) \sum_{x=0}^{7} \sum_{y=0}^{7} f(x,y) \cos\frac{(2x+1)u\pi}{16} \cos\frac{(2y+1)v\pi}{16} where C(0)=1/2C(0) = 1/\sqrt{2} and C(k)=1C(k) = 1 for k>0k > 0.
  5. Quantize: divide each DCT coefficient by a quantization step (larger steps for high frequencies).
  6. Encode the quantized coefficients with Huffman or arithmetic coding.

DCT vs FFT: this page uses the DCT (and its audio cousin, the MDCT), not the FFT. The DCT is the real-valued, even-symmetric variant of the DFT: the DCT of NN real points equals the DFT of the 2N2N-point even extension of the signal, and it needs no complex arithmetic. The FFT is the fast O(Nlog⁡N)O(N \log N) algorithm that computes DFTs — and, via that even-extension trick, DCTs as well.

Details

Why DCT?: Natural images have most of their energy in low-frequency DCT coefficients. The top-left coefficient (DC) captures the average; the rest (AC) capture detail. Quantizing AC coefficients to zero discards detail the eye barely notices.

DCAC1AC2 AC3AC4AC5 AC6AC7 typical 8-point DCT spectrum of a natural image block: energy concentrates at low frequencies

Quantization table: 8×8 matrix of divisors. The JPEG standard provides a default table; the quality parameter scales it. Higher quality → smaller divisors → less distortion.

PNG is lossless: it uses a filter (predict each row from the previous) followed by DEFLATE. No DCT, no quantization.

Modern lossy image formats: WebP (VP8 intra prediction + DCT) and AVIF (AV1 intra frames) keep the same transform → quantize → entropy-code pattern but add richer spatial prediction and better entropy coders, typically halving the bitrate of JPEG at equal quality.

Authoritative source: ITU-T T.81 (JPEG).

Example problem

An 8×8 block is constant, every pixel equal to 100. What are its 64 DCT coefficients, and why does this make smooth regions so cheap to encode?

Solution

Every AC coefficient is 0: the block has no variation, so all the cosine terms sum to zero. The DC coefficient alone carries the average: with the orthonormal scaling, F(0,0)=18∑x,yf(x,y)=64008=800F(0,0) = \frac{1}{8}\sum_{x,y} f(x,y) = \frac{6400}{8} = 800. The whole block therefore reduces to one number plus 63 zeros — which the entropy coder represents with a single “all AC zero” code. Smooth regions of natural images are close to this extreme, which is why JPEG spends most of its bits on edges and texture.

Lossy audio compression

Sound is a pressure wave. The Nyquist–Shannon sampling theorem states that a bandlimited signal with maximum frequency fmaxf_{max} can be perfectly reconstructed from samples at rate fs>2fmaxf_s > 2 f_{max}.

Human hearing spans 20 Hz20 \text{ Hz} to 20 kHz20 \text{ kHz}, so fs=44.1 kHzf_s = 44.1 \text{ kHz} (CD) or 48 kHz48 \text{ kHz} suffices.

MP3 / AAC pipeline:

  1. Split the signal into frames (MPEG-1 Layer III: 1152 samples = 2 granules of 576 samples, each granule transformed by 18 MDCT blocks of 32 coefficients; AAC: 1024 samples = one long MDCT, or 8 short windows of 128 for transients).
  2. Apply the MDCT (Modified DCT) to each frame: overlapping windows avoid the block-boundary artifacts a plain DCT would cause.
  3. Apply a psychoacoustic model: compute the masking threshold per frequency band (loud sounds mask nearby quiet sounds).
  4. Quantize spectral coefficients below the masking threshold to zero, and allocate the remaining bits across bands.
  5. Encode the quantized coefficients with Huffman coding.
frequency → level → loud tone masked → discarded above threshold → kept
Details

Perceptual coding exploits three phenomena:

Bit reservoir: MP3 main data is Huffman-coded and need not fit in its own frame. A frame that needs fewer bits than its allotment deposits the surplus into a bit reservoir; a frame facing a difficult passage borrows from it. Quality is thereby smoothed across frames instead of dipping exactly on the hard parts.

AAC profiles: AAC-LC (Low Complexity) is the plain MDCT + Huffman scheme described above. HE-AAC adds SBR (Spectral Band Replication): the encoder transmits only the low half of the spectrum plus a small parametric description, and the decoder reconstructs the high frequencies by transposing the low ones — roughly doubling the effective bandwidth at low bitrates. HE-AAC v2 adds parametric stereo on top.

Opus (RFC 6716) switches between two internal codecs according to content and bitrate: SILK (linear prediction, speech-oriented) at low rates and CELT (MDCT-based) at high rates, which is why one codec covers everything from narrowband speech to full-band music.

Bitrate: MP3 at 128 kbps total for stereo allocates 64 kbps per channel, yielding ≈64000/44100≈1.45\approx 64000 / 44100 \approx 1.45 bits per sample per channel. The psychoacoustic model decides how to distribute these bits across frequency bins.

Authoritative source: ISO/IEC 11172-3 (MPEG-1 Audio).

Example problem

A recording contains no energy above 15 kHz. What is the minimum sampling rate that preserves it exactly, and why does a 20 kHz sampling rate fail?

Solution

Nyquist–Shannon requires fs>2fmax=30f_s > 2 f_{max} = 30 kHz; 32 kHz suffices, and CD’s 44.1 kHz leaves margin for real filters. At fs=20f_s = 20 kHz, all energy between 10 and 15 kHz exceeds the Nyquist frequency fs/2=10f_s/2 = 10 kHz and aliases: it folds back into 5–10 kHz, corrupting frequencies that were correctly sampled. This is why decoders must low-pass filter before downsampling.

Lossy video compression

Video is a sequence of frames at a framerate (24, 30, 60 fps). Lossy video compression exploits both spatial redundancy (within a frame) and temporal redundancy (between frames).

Frame types (H.264/AVC, H.265/HEVC):

I B B P B B I P and B frames store only motion-compensated differences from their reference frames (arrows)

Motion compensation: divide the frame into 16×16 or 8×8 blocks; for each block, search a reference frame for the best-matching block; store the motion vector (offset) and the residual (difference).

Details

GOP (Group of Pictures): the sequence of frames between two I-frames. A longer GOP means fewer I-frames (smaller file) but longer error propagation if a frame is corrupted — and a longer seek time, since a player must start decoding at an I-frame.

Rate-distortion optimization: the encoder chooses quantization parameters to minimize D+λRD + \lambda R where DD is distortion (MSE) and RR is bitrate. This is a Lagrangian relaxation of the rate-distortion function.

H.265/HEVC improves on H.264 with larger CTUs (up to 64×64), more prediction modes, and a more parallelizable CABAC implementation (reduced context models, bin grouping). AV1 (open) and H.266/VVC push further with neural-network-based tools.

Authoritative source: ITU-T H.264 (AVC).

Example problem

A 30 fps video uses a GOP of 30. Each I-frame compresses to 60 kB and each P-frame to 6 kB (B-frames are folded into the P-frame budget for this estimate). Estimate the bitrate.

Solution

One GOP per second contains 1 I-frame and 29 P-frames: 60+29×6=23460 + 29 \times 6 = 234 kB/s ≈234,000×8=1.87\approx 234{,}000 \times 8 = 1.87 Mbps. The single I-frame is ~26% of the budget despite being 1/30 of the frames — which is why encoders place I-frames at scene cuts, where temporal prediction fails anyway.

Interactive exploration

The simulation below steps through LZ77: at each position, the encoder searches the sliding window for the longest match with the lookahead, emitting either a literal or an (offset, length) backreference. Try “ABRACADABRA” (the worked example above), then “AAAAAA” to see an overlapping match, then shrink the window to see matches lost.

Quizz

Problem: A 1920×1080 image has 2,073,600 pixels, each 24-bit RGB. What is the file size in bits? If JPEG compresses it to a quality where the DCT coefficients are quantized to 8 bits each (64 coefficients per 8×8 block), what is the compressed size before entropy coding?

Solution

Uncompressed: 2,073,600×24=49,766,4002{,}073{,}600 \times 24 = 49{,}766{,}400 bits ≈6.22\approx 6.22 MB.

Compressed (before entropy coding):

This is before Huffman/arithmetic coding, which would further reduce the size (many quantized coefficients are zero and can be run-length encoded). The actual JPEG file would be well under 2 MB at this quality.

Compression reduces the number of bits needed to represent data, either losslessly (exact reconstruction) or lossily (controlled distortion). It is relevant whenever storage or bandwidth is limited. Compression and channel coding (see Communication) are complementary stages: compression reduces the number of bits to send, while channel coding protects them from noise.

Authoritative sources

Lossless text compression

The source coding theorem (Shannon, 1948) states that no lossless code can have expected length below the entropy HH of the source, and this bound is asymptotically achievable. All the algorithms below approach this fundamental limit. See Coding and entropy for the full statement and proof.

Run-length encoding (RLE): replace runs of identical symbols with a count. AAAAABBBCC→5A  3B  2CAAAAABBBCC \to 5A\;3B\;2C. Effective for data with long runs; expands data with no runs.

LZ77 (backreference): replace repeated substrings with a (offset, length) pair pointing to the previous occurrence. Sliding window of size WW; maximum match length LL. Basis of DEFLATE and gzip.

LZW (dictionary): build a dictionary of previously seen strings; emit dictionary indices. The dictionary grows during encoding. Used in GIF, TIFF.

Huffman coding: assign shorter codewords to more probable symbols. Optimal among prefix-free codes for a known distribution (see Coding and entropy). Used in JPEG, MP3, DEFLATE.

DEFLATE (RFC 1951): combines LZ77 (backreferences) with Huffman coding. The basis of gzip, ZIP, PNG.

Arithmetic coding: encodes the entire message as a single fraction in [0,1)[0,1) whose interval shrinks by the probability of each symbol. Achieves entropy more closely than Huffman (which is limited to integer bit lengths).

Details

LZ77 example: Encoding “ABRACADABRA” with window 12, max match 4:

Huffman construction: repeatedly merge the two least-probable symbols until one node remains. The depth of each leaf is its codeword length. The resulting code is optimal among all prefix-free codes for the given distribution.

Arithmetic coding: maintain an interval [low,high)[low, high). For each symbol ss with cumulative probability [F(s),F(s)+p(s))[F(s), F(s)+p(s)), subdivide the current interval proportionally. After nn symbols, any value in the final interval decodes to the original message. The interval width is ∏p(si)\prod p(s_i), so the code length approaches −log⁡2∏p(si)=∑−log⁡2p(si)-\log_2 \prod p(s_i) = \sum -\log_2 p(s_i). By the law of large numbers, the expected code length per symbol approaches HH (the entropy of the source).

Lossy compression: the common pattern

All lossy codecs follow the same high-level structure: transform the signal into a perceptually-relevant domain → quantize using a perceptual model (discard components below the perceptual threshold) → entropy-code the residuals. The sections below differ only in the transform (DCT for images, MDCT for audio, DCT + motion compensation for video) and the perceptual model (visual vs. auditory masking).

Lossy image compression

An image is a 2D array of pixels, each with RGB (or YCbCr) values. Lossy compression exploits the fact that the human visual system is insensitive to high-frequency spatial detail.

Pipeline (JPEG):

  1. Convert RGB → YCbCr (luma + chroma).
  2. Downsample chroma (4:2:0: quarter the chroma resolution).
  3. Split into 8×8 blocks.
  4. Apply DCT (Discrete Cosine Transform) to each block: F(u,v)=14C(u)C(v)∑x=07∑y=07f(x,y)cos⁡(2x+1)uπ16cos⁡(2y+1)vπ16F(u,v) = \frac{1}{4} C(u) C(v) \sum_{x=0}^{7} \sum_{y=0}^{7} f(x,y) \cos\frac{(2x+1)u\pi}{16} \cos\frac{(2y+1)v\pi}{16} where C(0)=1/2C(0) = 1/\sqrt{2} and C(k)=1C(k) = 1 for k>0k > 0.
  5. Quantize: divide each DCT coefficient by a quantization step (larger steps for high frequencies).
  6. Encode the quantized coefficients with Huffman or arithmetic coding.
Details

Why DCT?: Natural images have most of their energy in low-frequency DCT coefficients. The top-left coefficient (DC) captures the average; the rest (AC) capture detail. Quantizing AC coefficients to zero discards detail the eye barely notices.

Quantization table: 8×8 matrix of divisors. The JPEG standard provides a default table; the quality parameter scales it. Higher quality → smaller divisors → less distortion.

PNG is lossless: it uses a filter (predict each row from the previous) followed by DEFLATE. No DCT, no quantization.

Lossy audio compression

Sound is a pressure wave. The Nyquist–Shannon sampling theorem states that a bandlimited signal with maximum frequency fmaxf_{max} can be perfectly reconstructed from samples at rate fs>2fmaxf_s > 2 f_{max}.

Human hearing spans 20 Hz20 \text{ Hz} to 20 kHz20 \text{ kHz}, so fs=44.1 kHzf_s = 44.1 \text{ kHz} (CD) or 48 kHz48 \text{ kHz} suffices.

MP3 / AAC pipeline:

  1. Split the signal into short frames (MP3: 1152 samples = 3 subframes of 384; AAC: 1024 samples = 4 subframes of 256).
  2. Apply MDCT (Modified DCT) to each frame.
  3. Map frequencies to Mel scale (perceptual frequency: m=2595log⁡10(1+f/700)m = 2595 \log_{10}(1 + f/700)).
  4. Apply a psychoacoustic model: compute the masking threshold (loud sounds mask nearby quiet sounds).
  5. Quantize spectral coefficients below the masking threshold to zero.
  6. Encode the remaining coefficients with Huffman coding.
Details

Mel spectrogram: a time-frequency representation where the frequency axis is in Mel units. It is the input to many speech recognition and audio classification models.

Bitrate: MP3 at 128 kbps total for stereo allocates 64 kbps per channel, yielding ≈64000/44100≈1.45\approx 64000 / 44100 \approx 1.45 bits per sample per channel. The psychoacoustic model decides how to distribute these bits across frequency bins.

Perceptual coding exploits three phenomena:

Lossy video compression

Video is a sequence of frames at a framerate (24, 30, 60 fps). Lossy video compression exploits both spatial redundancy (within a frame) and temporal redundancy (between frames).

Frame types (H.264/AVC, H.265/HEVC):

Motion compensation: divide the frame into 16×16 or 8×8 blocks; for each block, search a reference frame for the best-matching block; store the motion vector (offset) and the residual (difference).

Details

GOP (Group of Pictures): the sequence of frames between two I-frames. A longer GOP means fewer I-frames (smaller file) but longer error propagation if a frame is corrupted.

Rate-distortion optimization: the encoder chooses quantization parameters to minimize D+λRD + \lambda R where DD is distortion (MSE) and RR is bitrate. This is a Lagrangian relaxation of the rate-distortion function.

H.265/HEVC improves on H.264 with larger CTUs (up to 64×64), more prediction modes, and a more parallelizable CABAC implementation (reduced context models, bin grouping). AV1 (open) and H.266/VVC push further with neural-network-based tools.

Interactive exploration

Example problem

Problem: A 1920×1080 image has 2,073,600 pixels, each 24-bit RGB. What is the file size in bits? If JPEG compresses it to a quality where the DCT coefficients are quantized to 8 bits each (64 coefficients per 8×8 block), what is the compressed size before entropy coding?

Solution

Uncompressed: 2,073,600×24=49,766,4002{,}073{,}600 \times 24 = 49{,}766{,}400 bits ≈6.22\approx 6.22 MB.

Compressed (before entropy coding):

This is before Huffman/arithmetic coding, which would further reduce the size (many quantized coefficients are zero and can be run-length encoded). The actual JPEG file would be well under 2 MB at this quality.