basic concepts

Basic Concepts in Data Compression
In this section the basic concepts of data compression are shown:-

The Unary Code
The unary code of the non-negative integer n is defined as n-1 ones followed by one zero or, alternatively, as n-1 zeros followed by a single one.

Table : Some Unary Codes
n Code Alt. Code
1 0 1
2 10 01
3 110 001
4 1110 0001
5 11110 00001


Entropy Coding
We can define the entropy of a signal symbol ai as –Pi log2Pi. This is the smallest number of bits needed, on the average, to represent the symbol.
The amount of information contained in one, base-n symbol is:


This quantity is called the entropy of the data being transited.
The entropy of the data depends on the individual probabilities Pi, and is smallest when all n probabilities are equal.
Data Compression Strategies
There are different ways that data compression techniques can be categorized, smith gives a compression classification as below:

a. Lossless or Lossy
Lossless Lossy
RLE JPEG
Huffman MPEG
Arithmetic Vector quantization
Quadtree

b. Fixed or variable group size
Method Group Size
Input Output
Huffman Fixed Variable
Arithmetic Variable Variable
RLE, LZW Variable Fixed

Most data compression programs operate by taking a group of data from the original file and compressed it in some way, and then writing the compressed group to the output file.