1. [35 points] A source is represented by a random variable S that takes values in M = {1, 2, 3, 4, 5, 6, 7, 8}. The probability mass function (pmf) pS (k) is generated by the Matlab command pS = 1/8 + [4 3 2 1 -1 -2 -3 -4]'*0.01; such that pS (k) is the kth entry of the variable pS for k = 1, . . . , 8. Complete the following questions and submit all your Matlab scripts as well as all required answers. (a) Compute the entropy H(S). (b) Construct the Huffman codebook for S. How many bits, on average, will be required to encode the source S using the constructed codebook? (c) A message generated by the random source S is encoded by the Huffman codebook constructed in part (b), and then passed through a binary symmetric channel with bit flip probability p = 0.1. The bit sequence received at the other end of the channel is then decoded using the Huffman codebook. Denote the decoded value as a random variable R, whose randomness is derived from the random source S and the binary symmetric channel. Apparently R can only take values in M . Write a Matlab script to compute the conditional pmf pR|S (r|s) for all r M, s M . Arrange your answers into an 8 8 likelihood matrix whose rows are indexed by s M and columns indexed by r M . Format your answer such that each entry of the matrix has four digits after the decimal point. (d) Write a Matlab script to compute the marginal pmf pR (r) for R. Output pR as a vector of length 8. Format your answer such that each entry of the vector has four digits after the decimal point. (e) Write a Matlab script to compute the posterior pmf pS|R (s|r) for all r M, s M . Arrange your answers into a 8 8 posterior matrix whose rows are indexed by r M and columns indexed by s M . Format your answer such that each entry of the matrix has four digits after the decimal point. (f) A reasonable strategy to infer the source message from observing R = r is to find the s M that maximizes the posterior pmf pS|R (s|r) for fixed r. This is known as maximum a posteriori (MAP) estimation in statistics. Based on the computed posterior probabilities in part (e), explain how MAP would estimate s from an observation R = r. (g) Compute the probability that the MAP estimation makes an error. (h) To find the error probability in part (g) empirically, simulate one million times the process of generating a message from S, transmiting it through the binary symmetric channel, and decoding and inferring the transmitted message using MAP. Output the simulated probablity of error. What is the absolute difference between the probability of error computed in part (g) and the simulated probability of error? (i) What is the (approximate) probability that the simulated probability of error will be off by more than 0.001, i.e., the absolute difference between the probability of error computed in part (g) and the simulated probability of error in part (h) will be greater than 0.001? Run the simulation in part (g) a dozen times and see whether this (approximate) probability is consistent with the simulation results. 2