Data Compression -LEC#4

The 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.
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.
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).