UNIT-II Source Coding

[Audio] UNIT-II Source Coding From a transmitters point of view data of the source is compressed in a source encoder. For efficient compression we need the knowledge of entropy or the statistics of the source. For an example, we can assign short code to frequent source codes and longer code to infrequent one – this is called variable length code..

[Audio] Requirement of Efficient Source Coding… The primary requirement for a efficient source encoder is that – The code words produced by the encoder is in binary form. The source code is uniquely decodable, so that the original source sequence can be reconstructed perfectly from the encoded binary sequence..

[Audio] Coding Efficiency We have the following source encoder – Sk bk Binary sequence the above source is having an alphabet with K different symbols and kth symbol sk occures with probability pk, k=0,1,2,3…K-1. let the binary codeword assigned to symbol sk by the encoder have length lk, measured in bits. Discrete Memory less Source Source Encoder.

[Audio] So the average codeword length of the source encoder as – in physical terms it represents the average no of bits per source symbol. if Lmin the minimum possible value for , then coding efficiency of the source encoder is given by- with we have . encoder is said to be efficient when efficiency approaches unity..

[Audio] Shannon’s First Theorem Shannon’s first theorem on coding efficiency gives the idea to calculate . It is stated as – Given a discrete memory less source of entropy , the average codeword length for any distortion less source coding scheme is bounded as So, according to the source coding theorem, the entropy represents a fundamental limit on the average no of bits per source symbol necessary to represent a discrete memory less source in that it can be made as small as, but no smaller that the entropy, so with ,.

[Audio] For efficient transmission redundant data should be removed from the signal prior to transmission. This operation with no loss of information is performed in digital form and is called as data compaction or lossless data compression. This operation provides the source output with average no of bits/symbol and also original data could be reconstructed from these data with no loss of information. So short descriptions are provided to the most frequent outcomes and longer for the less frequent ones..

[Audio] As a measure of the variability in code-word lengths of a source code, we define the variance of the average code-word length over the ensemble of source symbols as It is usually found that when a combined symbol is moved as high as possible, the resulting Huffman code has a significantly smaller variance than when it is moved as low as possible. On this basis, it is reasonable to choose the former Huffman code over the latter..

[Audio] Shannon Fano Algorithm List the source symbols in the order of decreasing probabilities. Partition this ensemble into almost two equi p robable groups. Assign ‘0’ to one group and a ‘1’ to the other group. These form the starting code symbols of the codes. Repeat step 2 on each of the subgroups contain only one source symbol, to determine the succeeding code symbols of the code words. Read code directly..

[Audio] Consider the message ensemble S= with P=.

[Audio] Shannon Fano Algorithm. Step 1 16 16 16 16 Step 2 16 16 16 Step 3 oo 01 16 16 16 16 11 Step 4 16 16 16 16 Step 5 100 101 16 16 111 1100 1101 1110 Fig 6.3 Box Diagram.ror Example 5.10.

[Audio] Shannon Fano Coding Consider the message ensemble S= with P=.Construct Shannon Fano Code. Case of different solutions. Refer Notes..

[Audio] Huffman Coding The source symbols are listed in order of decreasing probability. The two source symbols of lowest probability are assigned a 0 and a 1. This part of the step is referred to as a splitting stage. These two source symbols are regarded as being combined into a new source symbol with probability equal to the sum of the two original probabilities. (The list of source symbols, and therefore source statistics, is thereby reduced in size by one.) The probability of the new symbol is placed in the list in accordance with its value. 3. The procedure is repeated until we are left with a final list of source statistics (symbols) of only two for which a 0 and a 1 are assigned..

[Audio] Q) The five symbols of the alphabet of a discrete memory less source and their probabilities are shown below: Using Huffman algorithm derive the code words and hence calculate the average length and entropy of the discrete memoryless source..

[Audio] Solution:. Symbol 0.2 0.2 0.2 Stage 0.4 0.2 0.2 oti 0.1 Stage II 0.4 Stage 0.4 0.4 0.2 Stage IV 0.6 0.4.

[Audio] Cont…. Cont….

[Audio] Cont… Average code word length: Entropy:.