Information Theory and Coding > Data Compression > State Kraft Inequality with example

The basic objective is to construct instantaneous codes of minimum expected length to describe a given source. It is true that we cannot assign short codewords to all source symbols and still be prefix-free. The necessary and sufficient conditions for the existence of such a code are provided by the ‘Kraft Inequality’:

Given a source S = {s₁, s₂, …. s_q}, X = {x₁, x₂ … x_r}, let the word lengths of the codes corresponding to these symbols be l₁, l₂ …….l_q. Then, an instantaneous code for the source exists that must satisfy the inequality:

This inequality is called kraft inequality

 

Example: A six symbol source is encoded into Binary codes shown below.

Kraft Inequality test for Code A is:

X={0,1} hence R=2;  L ={2,2,2,3,4,4}

Which satisfy kraft inequality. So code A is an instantaneous code

Prev

How to construct an Instantaneous Codes?

Next

Explain Shannon – Fano Binary Encoding Method

Feedback

Submit