18-07-2012, 10:44 AM
Compression and Decompression
compression.pptx (Size: 428.17 KB / Downloads: 27)
Why Data Compression?
Make optimal use of limited storage space
Save time and help to optimize resources
If compression and decompression are done in I/O processor, less time is required to move data to or from storage subsystem, freeing I/O bus for other work
In sending data over communication line: less time to transmit and less storage to host.
And Decompression is reversal process of compression
Lossy Compression Methods-:
Used for compressing images and video files (our eyes cannot distinguish subtle changes, so lossy data is acceptable).
These methods are cheaper, less time and space.
Several methods:
JPEG: compress pictures and graphics
MPEG: compress video
MP3: compress audio
Run-length Encoding
Simplest method of compression.
How: replace consecutive repeating occurrences of a symbol by 1 occurrence of the symbol itself, then followed by the number of occurrences.
The method can be more efficient if the data uses only 2 symbols (0s and 1s) in bit patterns and 1 symbol is more frequent than another.
Huffman Coding
Assign fewer bits to symbols that occur more frequently and more bits to symbols appear less often.
There’s no unique Huffman code and every Huffman code has the same average code length.
Algorithm:
Make a leaf node for each code symbol
Add the generation probability of each symbol to the leaf node
Take the two leaf nodes with the smallest probability and connect them into a new node
Add 1 or 0 to each of the two branches
The probability of the new node is the sum of the probabilities of the two connecting nodes
If there is only one node left, the code construction is completed. If not, go back to (2)
JPEG Encoding- DCT
DCT: Discrete Concise Transform
DCT transforms the 64 values in 8x8 pixel block in a way that the relative relationships between pixels are kept but the redundancies are revealed.
Example:
A gradient grayscale
JPEG Encoding
Used to compress pictures and graphics.
In JPEG, a grayscale picture is divided into 8x8 pixel blocks to decrease the number of calculations.
Basic idea:
Change the picture into a linear (vector) sets of numbers that reveals the redundancies.
The redundancies is then removed by one of lossless compression methods.
Audio Compression
Used for speech or music
Speech: compress a 64 kHz digitized signal
Music: compress a 1.411 MHz signal
Two categories of techniques:
Predictive encoding
Perceptual encoding
Audio Encoding
Predictive Encoding
Only the differences between samples are encoded, not the whole sample values.
Several standards: GSM (13 kbps), G.729 (8 kbps), and G.723.3 (6.4 or 5.3 kbps)
Perceptual Encoding: MP3
CD-quality audio needs at least 1.411 Mbps and cannot be sent over the Internet without compression.
MP3 (MPEG audio layer 3) uses perceptual encoding technique to compress audio.