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 pXY be any joint distribution on X ΛY. For any 0 and positive integer n, define the jointly typical set q β !
where Β΅xnynpa,bq is the number of locations i P t1,2,…,nu for which xi β a and yi β b.
Let Xn,Y n be jointly distributed such that Xi,Yi β pXY for all i whereas pXi,Yiq is independent of all other pXj,Yjq for all j β° i.
- Prove that limnΓ8 Prrpqs β 0
- Show that for all g : X Λ Y Γ R and all pxn,yn T pnq pXY q,
q
- 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.
- 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.
- 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.
- Use the designed codes to compress the attached file.
- Decode the compressed file, and verify that you get back the original file
- 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.
