3
7.2kviews
Calculate the efficiency of Huffman code for the following symbol whose probability of occurrence is given below Explain Huffman code with example

Subject: Digital Image Processing

Marks: 10,M

Difficulty: Medium / High

0
206views

Solution:

$\begin{array}{cc} \text { Symbol } & \text { Huffman code. } \\ a_1 & 1 \\ a_2 & 01 \\ a_3 & 001 \\ a_4 & 000. \end{array}$

\begin{aligned} \text { Length } &=\sum(\text { number of bits for each symbol }) \times \text { probabit } \\ &=1 \times 0.9+2 \times 0.06+3 \times 0.02+3 \times 0.02 \\ &=0.9+0.12+0.06+0.06 \\ &=1.14 \text { bits. } \end{aligned}

Entropy:-

\begin{aligned} H(s)=&-\sum_{k=0}^{N-1} P_k \log _2 P_k \\ =&-\left[0.9 \log _2 0.9+0.06 \log _2 0.06+0.02 \log _2 0.02\right.\\ &\left.\quad+0.02 \log _2 0.02\right] \\ =&-[-0.1368-0.2435-0.1128-0.1128] \\ =& 0.6046 \end{aligned}

\begin{aligned} \text { Efficiency } &=\frac{H(S)}{L}=\frac{\text { Entropy }}{\text { Average length }} \\ &=\frac{0.6046}{1.14}=0.5303 \\ &=53.03 \% . \end{aligned}

Run length coding:-

It is the simplest dictonary-based data compression technique.

• Image files frequently contain the same character repeated many times in a row.

Images particularly. those having very few gray levels often contain regions of adjacent pixels, all with the same gray level.

Each row of such images can have long runs of the same gray value.

• In such cases, one can store a code specifying the value of the gray level, followed by the length of the run, rather than storing the same value many times over.

For example, Consider the first row of an image that has the following gray levels.

This row of an image has 15 gray values.

Using RLE.

Hence RLE of this row is

$2 3 5 8 6 4 \text {. }$

The RLE eliminates Inter -pixel redundancies.