Basic Concepts in Data Compression

It is important to distinguish the concept of symbolic data alphabet and code. By symbolic data mean a source file consist of symbols from an alphabet. An alphabet is a collection of symbols called letters. The set of binary sequences is called a code, and the individual members of the set are called codewords..
The Unary Code
The unary code of the non-negative integer n is defined as n-1 ones followed by one zero (table 1) or, alternatively, as n-1 zeros followed by a single one.
Table (1): Some Unary Codes
n Code Alt. Code
1 0 1
2 10 01
3 110 001
4 1110 0001
5 11110 00001

Variable length codes
Variable length codes are desirable for data compression because overall savings may be achieved by assigning short codewords to frequently occurring symbols and long codewords to rarely occurring ones. For example, consider a variable length code (0, 100, 101, 110, 111) with lengths of codewords(1, 3, 3, 3, 3) for alphabet (A, B, C, D, E), and a source string BAAAAAAAC with frequencies for each symbol (7, 1, 1, 0, 0). The average number of bits required is

This is almost a saving of half the number of bits compared to 3 bits/symbol using a 3 bit fixed length code. The shorter the codewords, the shorter the total length of a source file. Hence the code would be a better one from the compression point of view.

Prefix codes and binary trees
A prefix is the first few consecutive bits of a codeword. When two codewords are of different lengths, it is possible that the shorter codeword is identical to the first few bits of the longer codeword. In this case, the shorter codeword is said to be a prefix of the longer one.
Example Consider two binary codewords of different length: c1 = 010 (3 bits) and c2 = 01011 (5 bits).
The shorter codeword C1 is the prefix of the longer code c2 as c2= 11.Codeword c2 can be obtained by appending two more bits 11 to Cl.
The prefix property of a binary code is the fact that no codeword is a prefix of another. A prefix code is a code in which no codeword is a prefix of another codeword, It is easy to check whether a binary code is a prefix code by drawing an associated binary tree. Each binary code can correspond to one such binary tree, in which each codeword corresponds to a path from the root to a node with the codeword name marked at the end of the path. Each bit 0 in a codeword corresponds to a left edge and each 1 to a right edge. Recall that, if a prefix code is represented in such an associate binary tree, all the codeword labels will be at its leaves.
Two steps are involved in this approach:
1. Construct the binary tree
First, we create a node as the root of the binary tree. Next, we look at the codewords one by one. For each codeword, we read one bit at a time from the first to the last. Starting from the root, we either draw a new branch or move down an edge along a branch according to the value of the bit. When a bit 0 is read, we draw, if there is no branch yet, a left branch and a new node at the end of the branch. We move down one edge along the left branch otherwise, and arrive at the node at the end of the edge.
Similarly, when a bit 1 is read, we draw if there no branch yet, a right branch, or move down an edge along the right branch otherwise. The process repeats from node to node while reading the bit by bit until the end of the codeword. We mark the codeword after finishing with the whole codeword.
2.Checking codeword position
If all the codeword labels are only associated with the leaves, then the codeword is a prefix code. Otherwise, it is not.
Example:- Decide whether the codes(1,01,001,0000) and (0,10,110,1011) for alphabet (A,B,C,D) are prefix codes. Figure (2.6) show the solution.






Unique decodability
Variable length codes are useful for data compression. However, a variable length code would be useless if the codewords could not be identified in a unique way from the encoded message.

Homework // Determine whether the following codes are uniquely decodable:

(a) {0_ 01_ 11_ 111}
(b) {0_ 01_ 110_ 111}
(c) {0_ 10_ 110_ 111}
(d) {1_ 10_ 110_ 111}