TE [E&TC] Sinhgad Institute of Technology, Lonavala DC
Name of the Student : ____________________________________ Roll No : _____
Class : T.E. [E&TC] Division : _______ Course : DC
Experiment No. 9
**SIMULATION STUDY OF SOURCE CODING TECHNIQUE.**
Marks: /10
Date of Performance: / /20 Sign with Date
Aim: To Implement the algorithm of generation of Variable Length Source coding using Huffman
Coding Algorithm
Objectives : Understand the Importance of generation of n source coding using Huffman
algorithm.
Verify the result
Outcomes: At the end of this experiment students should be able to:
1. Generate the source code using Matlab code
PEOs ,POs, PSOs and COs satisfied:
PEOs: I,-V POs: 1,2,3,4,5,6,7,10,12 PSOs: 1,2 COs:1,4
Software used: MATLAB 7
Problem statement:
From the given probabilities p=[0. 4 0.2 0.1 0.1 0.2] of symbols=[A, B, C, D, E]. Find the
codewords by using Huffman coding algorithm, also find source efficiency and redundancy
Theory : In communication system efficient representation of data for a discrete source is
obtained by source coding. Our aim is develop an efficient encoder for this there are 2
requirements. Source encoding aims to convert information waveforms (text, audio, image, video,
etc.) into bits, the universal currency of information in the digital world. The three major steps are:
• Sampling: convert the continuous-time analog waveform to discrete-time sequence (but still
continuous-valued).
• Quantization: convert each continuous-valued symbol to discrete-valued representatives.
1 DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION ENGG
TE [E&TC] Sinhgad Institute of Technology, Lonavala DC
• Data compression: remove the redundancy in the data and generate roughly i.i.d. uniformly
distributed bits. Source decoding does the reverse of encoding
From Shannon’s coding theorem we can state that Coding Efficiency cam be increased if less
number of bits are assigned to more probably occurring messages.
Huffman coding is a very efficient way of compressing data. It can be used to compress all sorts
of data, including text, images, and audio. Huffman coding can be especially beneficial when
compressing large files.
Huffman coding is a lossless data compression algorithm. The idea is to assign variable-length
codes to input characters, lengths of the assigned codes are based on the frequencies of
corresponding characters.
The variable-length codes assigned to input characters are Prefix Codes, means the codes (bit
sequences) are assigned in such a way that the code assigned to one character is not the prefix of
code assigned to any other character. This is how Huffman Coding makes sure that there is no
ambiguity when decoding the generated bit stream.
Let us understand prefix codes with a counter example. Let there be four characters a, b, c and
d, and their corresponding variable length codes be 00, 01, 0 and 1. This coding leads to
ambiguity because code assigned to c is the prefix of codes assigned to a and b. If the
compressed bit stream is 0001, the de-compressed output may be “cccd” or “ccb” or “acd” or
“ab”.
There are mainly two major parts in Huffman Coding
1. Build a Huffman Tree from input characters.
2. Traverse the Huffman Tree and assign codes to characters.
Algorithm:
1. Accept symbols and their probabilities from user.
2. Arrange all the symbols in descending order of their probabilities.
3. Consider the last two symbols in the sequence and assign ‘0’ to the second last and ‘1’ to
the last, respectively.
4. Add last two symbol probabilities and place the sum after addition in the list; as per its
value giving highest priority.
5. Repeat the steps 5 & 6; till only two symbol probabilities are left, to which also bit 0 & are
assigned.
6. Trace backward to form the codeword.
7. Calculate codeword length of each symbol.
2 DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION ENGG
TE [E&TC] Sinhgad Institute of Technology, Lonavala DC
8. Find average codeword length, entropy & efficiency of the code
Conclusion :
A. Write short answer of following questions : (4-5 Max)
1. Explain types of channel?
2. Enlist various source coding techniques.
3. Explain need of source coding with example
4. State objectives of source coding
5. Write the procedure for Huffman coding.
B. Viva Questions: (8-10)
1. Define source entropy, average codeword length, coding efficiency,
2. Why Huffman code is called optimum code
3. What is difference between Shannon Fano and Huffman code
A. Design Experiments/ Lab innovations ( over and above )
1. Solve the following numerical on your own and then verify your output with program output.
Attach solution with manual.
Form the given probabilities p=[0. 4 0.2 0.1 0.1 0.2] of symbol s=[1,2, 3, 4,5]. Find the codewords by
using Huffman coding algorithm, also find source efficiency and redundancy.
3 DEPARTMENT OF ELECTRONICS AND TELECOMMUNICATION ENGG