It assignment 1

Information Theory

Assignment-1

1)What is entropy ?give an example and what are the properties of entropy ?

Ans::

Entropy::

		The average amount of information conveyed is called as entropy
			H(X) = 
		where p(x) is probability of particular random variable in a random space x and
log p(x) is the self information for that paricular random variable.

Properties of entropy::

2)What is chain rule ?explain with relative entropy,entropy and mutual information ?

Ans::

 friends answer is there in our facebook group 
/Click here for the ans



 3)State and prove krafts inequality theorem and explain optimal codes ?
Ans::
Kraft inequality: 
			For any instantaneous code (prefix code) over an alphabet of size D, the
codeword lengths *** must satisfy the inequality

Conversely, 
	given a set of codeword lengths that satisfy this inequality, there exists an instantaneous
 code with these word lengths. 

Proof::
	Consider a D-ary tree in which each node has D children. 

Let the branches of the tree represent the symbols of the codeword. 

The prefix condition on the codewords implies that no codeword is an ancestor 
of any other codeword on the tree. Hence, each codeword eliminates its descendants
as possible codewords. 

Let lmax be the length of the longest codeword of the set of codewords. 

Consider all nodes of the tree at level lmax.

Some of them are codewords, some are descendants of codewords, and some are neither. 

A codeword at level li has **** descendants at level lmax Each of these descendant sets must be disjoint.

Also,the total number of nodes in these sets must be less than or equal to Dlmax. 

Hence, summing over all the codewords, we have 

{
**************
}

Conversely,
given any set of codeword lengths ***** which satisfy the Kraft inequality,
we can always construct a tree and we have instantaneous code at each level




 Optimal codes :: 


 4)Explain arithmetic code with an example ?

 5)What is shannon fano elias code ?