5. (40 points) Program HW. Huffman source compression for two sequences. (a) (5 points) Generate Source...

 

Transcribed Image Text:

5. (40 points) Program HW. Huffman source compression for two sequences. (a) (5 points) Generate Source A with length 1000 which is an IID sequence, each with X~ Bern(1/4) for Vt (b) (5 points) Generate Source B with length 1000, which is an Markov source gen- erated with transition probabilities po,o = 3/4, po,1 = 1/4, p1,0 = 1/4, and P1,1 = 3/4. Use an uniform distribution for the initial distribution. (c) (10 points) Write a computer program to compress and decompress the source of A using Huffman coding. Encode 4 bits at a time, i.e., there are 4-bit sym- bols. Print out the pseudo code and the output of the encoder as a binary string. What is the compression ratio? (Hint: You need to compute p(0000), ..., p(1111).) (d) (10 points) Repeat 1 for Source Y. (Hint: You need steady state distribution) (e) (10 points) Compare two results. 5. (40 points) Program HW. Huffman source compression for two sequences. (a) (5 points) Generate Source A with length 1000 which is an IID sequence, each with X~ Bern(1/4) for Vt (b) (5 points) Generate Source B with length 1000, which is an Markov source gen- erated with transition probabilities po,o = 3/4, po,1 = 1/4, p1,0 = 1/4, and P1,1 = 3/4. Use an uniform distribution for the initial distribution. (c) (10 points) Write a computer program to compress and decompress the source of A using Huffman coding. Encode 4 bits at a time, i.e., there are 4-bit sym- bols. Print out the pseudo code and the output of the encoder as a binary string. What is the compression ratio? (Hint: You need to compute p(0000), ..., p(1111).) (d) (10 points) Repeat 1 for Source Y. (Hint: You need steady state distribution) (e) (10 points) Compare two results.