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()