[SOLVED] EE5390- Homework 1

Description

Instructions: You are encouraged to discuss and collaborate with your classmates. However, you must explicitly mention at the top of your submission who you collaborated with, and all external resources (websites, books) you used, if any. Copying is NOT permitted, and solutions must be written independently and in your own words.

Please scan a copy of your handwritten assignment as pdf with filename ăyour IDą HWăhomework noą.pdf. Example: EE19BTECH00000 HW1.pdf.

For programming questions, create separate files. Please use the naming convention ăyour IDą HWăhomework noą problemăproblem noą.*. Example: EE19BTECH00000 HW1 problem1.c. You may upload c,cpp,py or m files only. No other format will be allowed.

Finally, upload your submission as separate files on Google classroom. Please do not upload zip files.

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_nÑ8 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.

1-1

1-2                                                                                                                                                      Homework 1: 3rd Mar 2021

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.