[Solved] EE5390 Homework1

The following videos might be useful for problem 1: https://www.youtube.com/watch?v=ew_CbNkxzYg and https://www.youtube.com/watch?v=ywduYSla88k.

Exercise 1.1 (Jointly typical sets). Let p_XY be any joint distribution on X Y. For any 0 and positive integer n, define the jointly typical set q !

where _xn_ynpa,bq is the number of locations i P t1,2,,nu for which x_i a and y_i b.

Let Xⁿ,Y ⁿ be jointly distributed such that X_i,Y_i p_XY for all i whereas pX_i,Y_iq is independent of all other pX_j,Y_jq for all j i.

1. Prove that lim_n8 Prrpqs 0
2. Show that for all g : X Y R and all pxⁿ,yⁿ T ^pnq p_XY q,

q

3. Use the above to obtain upper and lower bounds on |.

Exercise 1.2 (Implementing compression). The shared folder contains files with characters randomly drawn from the set ta,b,c,d,eu. You must write a program to compress and decompress this file.

1. Write a program to compute the empirical type of the file, i.e., the fraction of occurrence of various symbols in the file. Also compute the entropy.
2. Using the above type, design the Shannon, Huffman and Shannon-Fano-Elias codes for this file. You can compute these on paper. Show all the steps.
3. Use the designed codes to compress the attached file.

4. Decode the compressed file, and verify that you get back the original file
5. Find the length of the compressed sequence, and compare this with the entropy.

Exercise 1.3. Repeat the same as in Problem 2 for the corresponding file in the folder for problem 3.