we talked about Huffman coding and Shannon's source coding theorem for DMS(Q). Both Huffman coding and...

 

Transcribed Image Text:

we talked about Huffman coding and Shannon's source coding theorem for DMS(Q). Both Huffman coding and Shannon's source coding compress an i.i.d. source by using the knowledge of the distribution of the source. In this problem, we consider the case when the true distribution Q of the source is unknown. For such a case, we will design a universal code' with which we can compress the source without the knowledge of the exact distribution Q. To design such a universal code, we first introduce some definitions. Consider an i.i.d. source X₁, X2,..., Xn distributed by distribution Q. An (n, R) block source code of rate R consists of a pair of mappings fn and gn: fn X→ {0, 1}R In: (0,1}"X". The probability of error for the code with respect to the distribution Qis p(n) Q ({z": gn (fn(x")) #x"}). (1) (2) We say that an error exponent E is achievable at rate R if there exists a sequence of (n, R) codes with P(n) e-nE (3) which means 1 lim sup - In P() <-E. (4) 14x n Let's design a universal code (fn, 9n) that enumerates all the sequences in the set A = {r" € X": H(P₂) ≤S} (5) for some constant S > 0, where P is the empirical distribution of each r". The encoder fn maps each sequence z E A to different codewords by one-to-one mapping, and the decoder gn recovers the sequence by the inverse mapping of fn. Note that this code does not assume or use the distribution of the source. Error is claimed whenever r" # A. The error probability of this code for DMS(Q) is thus P(n) Q ({x":" & A}). (6) a) Find the required rate R for the encoder fn to enumerate all the sequences in the set A. (Hint: Find the size |A|.) b) We now show that this encoding scheme is universal. Assume that the distribution of X₁, X2,..., X₂ is Q and H(Q)< S. Find the error exponent of this code, i.e., find E in (4) for P) in (6). (In your answer, if you have any optimization, then just leave it. You don't need to solve the optimization.) we talked about Huffman coding and Shannon's source coding theorem for DMS(Q). Both Huffman coding and Shannon's source coding compress an i.i.d. source by using the knowledge of the distribution of the source. In this problem, we consider the case when the true distribution Q of the source is unknown. For such a case, we will design a universal code' with which we can compress the source without the knowledge of the exact distribution Q. To design such a universal code, we first introduce some definitions. Consider an i.i.d. source X₁, X2,..., Xn distributed by distribution Q. An (n, R) block source code of rate R consists of a pair of mappings fn and gn: fn X→ {0, 1}R In: (0,1}"X". The probability of error for the code with respect to the distribution Qis p(n) Q ({z": gn (fn(x")) #x"}). (1) (2) We say that an error exponent E is achievable at rate R if there exists a sequence of (n, R) codes with P(n) e-nE (3) which means 1 lim sup - In P() <-E. (4) 14x n Let's design a universal code (fn, 9n) that enumerates all the sequences in the set A = {r" € X": H(P₂) ≤S} (5) for some constant S > 0, where P is the empirical distribution of each r". The encoder fn maps each sequence z E A to different codewords by one-to-one mapping, and the decoder gn recovers the sequence by the inverse mapping of fn. Note that this code does not assume or use the distribution of the source. Error is claimed whenever r" # A. The error probability of this code for DMS(Q) is thus P(n) Q ({x":" & A}). (6) a) Find the required rate R for the encoder fn to enumerate all the sequences in the set A. (Hint: Find the size |A|.) b) We now show that this encoding scheme is universal. Assume that the distribution of X₁, X2,..., X₂ is Q and H(Q)< S. Find the error exponent of this code, i.e., find E in (4) for P) in (6). (In your answer, if you have any optimization, then just leave it. You don't need to solve the optimization.)

Answer rating: 100% (QA)

Solution Certainly Let me provide a stepbyste... View the full answer