Source Coding for a Simple Network

1.1 Informal statement of the problem To fix ideas, let us consider the following problem. Suppose that we are given a data source whose output is a sequence Ui, t/ 2 , · · ·, that appears at the source output at the rate of 1 per second. The {Uk} f is a sequence of independent copies of the discrete random variable U, with probability distribution Pr { U ~ u = Q(w), w £ 11 a finite set. Our task is to transmit this data sequence over a communication channel having a capacity of C bits per second so that it is represented at the output as Ui, Z/2, · · ·, E l l . We assume that the data are transThe work of R. M. Gray was supported in part by N S F Grants GK-5452 and GK-31630 and by the Joint Services Program at Stanford Electronics Laboratory and U.S. Navy Contract N0014-67-A-l 12-004. Parts of this work were performed while A. D. Wyner was visiting Stanford University with the partial support of the ISL Stanford Affiliates. 1681 mitted over the channel in blocks of length n, and allow processing at both the channel input and output (encoding and decoding). We define the "error rate" as A = E- t d,,{Uk, Uk), n 1 where (la)