Information Theory and Coding > Data Compression > What do you mean by "Codes" in data compression?
Definition of Codes: ‘Encoding’ or ‘Enciphering’ is a procedure for associating words constructed from a finite alphabet of a language with given words of another language in a one-to- one manner.
Let the source be characterized by the set of symbols S= {s1, s2... sq} We shall call ‘ S’ as the “Source alphabet”. Consider another set, X, comprising of ‘ r’ symbols. X={x1, x2…xr }
We will call ‘ X’ as the “code alphabet”. We define “coding” as the mapping of all possible sequences of symbols of S into sequences of symbol of X. In other words “coding means representing each and every symbol of S by a sequence of symbols of X such that there shall be a one-to-one relationship”
Any finite sequence of symbols from an alphabet will be called a “Word”. Thus any sequence from the alphabet ‘X’ forms a “ code word”. The total number of symbols contained in the ‘ word’ will be called “ word length”.
Example: The sequences { x1 ; x1x3x4 ; x3x5x7x9 ; x1x1x2x2x2} form code words. Their word lengths are respectively 1; 3; 4; and 5. The sequences {100001001100011000} and {1100111100001111000111000} are binary code words with word lengths 18 and 25 respectively.
Source Code:
Suppose X is a random variable and it has a domain e.i. set of values. Let C is the code to denote the values of X using the alphabet D* which is the set of finite-length strings of symbols from D-ary alphabet then C is called a source code for the random variable X.
Example: Let X={‘Red’, ‘Green’}, D={0,1} we may define source code C like C(Red)=00, C(Green)=11
Expected Length:
Expected length L(C) of a source code C(x) for a random variable X with probability mass function p(x) is given by
where l(x) is the length of the codeword associated with x.
Example: Let X be a random variable with the following distribution and codeword assignment:
Pr(X = 1) = 1/2 , codeword C(1) = 0
Pr(X = 2) = 1/4 , codeword C(2) = 10
Pr(X = 3) = 1/8 , codeword C(3) = 110
Pr(X = 4) = 1/8 , codeword C(4) = 111.
Entropy H (X)= - ½ * log ½ - ¼ * log ¼ - 1/8 * log 1/8 – 1/8 * log 1/8 = 1.75 bits
Expected length L(C) = El(X) = ½ *1 + ¼ * 2 + 1/8 * 3 + 1/8 * 3 = 1.75 bits
Note: Since Entropy and Expected length are same, any sequence of bits can be uniquely decoded into a sequence of symbols of X. The bit string 0110111100110 is decoded as 134213.
Example: Suppose the code for a random variable X are :
Pr(X = 1) = 1/3 , codeword C(1) = 0
Pr(X = 2) = 1/3 , codeword C(2) = 10
Pr(X = 3) = 1/3 , codeword C(3) = 11.
Entropy H(X) = -1/3 * log 1/3 * 3= 1.585 El(x)= 1/3 *(1+2+2)=5/3= 1.66 . Here El(X) > H (X)
Feedback
ABOUT
Statlearner
Statlearner STUDY
Statlearner