Department of Computer Engineering
University of California at Santa Cruz
Data Compression (2)
Hai Tao
Department of Computer Engineering
University of California at Santa Cruz
Pulse code modulation
The process of digitizing audio signal is called pulse code
modulation
• Sampling the analog waveform at a minimum rate
• Each sample is quantized using a fixed number of bits
To reduce the amount of data, we can
• Reduce the sampling rate (e.g 8k for telephone )
• Reduce the number of bit per sample (8 bits vs. 16 bits)
Department of Computer Engineering
University of California at Santa Cruz
Differential Pulse Code Modulation (DPCM)
Encode the changes between consecutive samples
Example
f (n) f (n)
n n
f (n) 156,157,158,158,156,156,154,154,155 f (n) 156,1,1,0, 1,0, 1,0,1
The value of the differences between samples are much
smaller than those of the original samples. Less bits are
used to encode the signal (e.g. 7 bits instead of 8 bits)
Department of Computer Engineering
University of California at Santa Cruz
DPCM decoding
The difference is added to the previous sample to obtain
the value of the current sample. Lossless coding is
achieved
In DPCM, the number of bits per sample needs to
accommodate the largest value changes between samples,
both in positive and negative direction. For an original
sequence of 8bit PCM, to tolerate ¼ of changes in both
direction, 7 bits are needed to code the differences
Department of Computer Engineering
University of California at Santa Cruz
Adaptive DPCM (ADPCM)
One observation is that small difference between samples
happens more often than large changes
Entropy coding method such the Huffman coding scheme
can be used to encode the difference for additional
efficiency
• The probabilities of occurrence of different differences are first
obtained using a large data base
• Huffman coding method is used to determine the codeword for
each difference
• The codeword is fixed and made available to decoders
Department of Computer Engineering
University of California at Santa Cruz
Linear Predictive Coding (LPC)
In DPCM, the value of the current sample is guessed based
on the previous sample. Can a better prediction be made ?
The answer is yes. For example, we can use the previous
two samples to predict the current one
f (n) 2 f (n 1) f (n 2)
f ( n ) f ( n ) f ( n )
LPC is more general than DPCM. It exploit the correlation
between multiple consecutive samples
Department of Computer Engineering
University of California at Santa Cruz
Image Compression
From the 1D case, we observe that data compression can
be achieved by exploiting the correlation between samples.
This idea is applicable to 2D signals as well.
Instead of predicting sample values, we can use the so
called transformation method to obtain a more compact
representation of the data
Department of Computer Engineering
University of California at Santa Cruz
Discrete Cosine Transform (DCT)
DCT is the real part of the 2D Fourier transform
The inverse DCT is
Department of Computer Engineering
University of California at Santa Cruz
DCT Transform of 2D Images
DCT Example
DCT of images can also be considered as the projection of
the original image into the DCT basis functions. Each
basis function is in the form of
2 y 1 2x 1
cos(v ) cos(u )
2N 2N
Department of Computer Engineering
University of California at Santa Cruz
DCT Basis Functions
The basis functions for a 8x8 DCT Transform
u
Department of Computer Engineering
University of California at Santa Cruz
DCT Compression
After DCT compression, only a few DCT coefficients have
large values
We need to
• Quantize the DCT coefficients
• Encode the position of the large coefficients
• Compress the value of the coefficients