IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-19, NO. 2, MARCH 1973 197 Random Coding Theorem for Broadcast Channels With Degraded Components PATRICK P Absfroct-This paper generalizes Cover’s results on broadcast chan- nels with two binary symmetric channels (BSC) to the class of degraded channels with N components. A random code, and its associated decoding scheme, is shown to have expected probability of error going to zero for all components simultaneously as the codeword length goes to infinity, if the point representing the rates to the various receivers falls in the set of achievable rates described by this paper. A procedure to expurgate a good random broadcast code is given, leading to a bound on the maximum probability of error. Binary symmetric broadcast channels always fall in the class of de- graded broadcast channels. The results of the paper are applied to this class of channels of potential practical importance. I. INTRODUCTION I N a recent paper [I], Cover introduced the notion of a broadcast cham~el, through which one source sends information to two or more receivers. One of the results of Cover’s paper is that in some situations there exists a coding scheme allowing the transmission of information to the different users at better rates than the so-called time- sharing rates. The present paper generalizes those results, and gives a rigorous proof of the coding theorem for degraded broadcast channels. The notion of a degraded broadcast channel is introduced in Section II, together with the definitions of the various quantities used in the paper. In Section III, we exhibit a random coding scheme, describe the associated decoding rule, and find a set of sufficient conditions to guarantee that the expected probability of error goes to zero for all channels simultaneously when the length of the code goes to co. The rigorous proof of this statement is given in Appendix A. In Appendix B, we show that uniformly good broadcast codes exist, and that we can upperbound the maximum probability of error for all channels simultaneously. Some of the results of Section III were conjectured by Cover [l]. In Section IV, we introduce simple upper bounds to the capacity region, and discuss a generalized definition of broadcast rates. Finally, the case of the binary symmetric broadcast channel (BSBC) is treated in Section V. II. DEFINITIONS AND PRELIMINARIES A. Broadcast Channels The most general representation of a discrete memoryless broadcast channel is given in Fig. I. The input alphabet is Manuscript received September 13, 1971; revised March 31, 1972. This work was supported by Air Force Contract AF 49(638)1517 and NSF Contract GK-34363. The author was with Stanford University, Stanford, Calif. He is now with the Department of Electrical Engineering, Cornell University, Ithaca, N.Y. BERGMANS 43 y1 x BROADCAST u, CHANNEL . . . YN Fig. 1. Broadcast channel. d, and the output alphabet of thejth terminal is gj. The transition probability of the broadcast channel is P(YILh? - * * ?YN I 4. We impose a “no-collaboration” restriction between the receivers connected to the different terminals of the broad- cast channel. Without this restriction, there is no real broadcast situation. The no-collaboration restriction allows us to factor the broadcast channel into its N component channels, since possible dependence between the Yj con- ditioned on X is irrelevant. Hence, we need consider only the marginal transition probabilities p(y, 1 x), p(y, ( x); * * of the component channels A,,A,; * .,A, (Fig. 2), and all broadcast channels with same marginals will be equivalent in this context. Cj, the capacity of the jth component channel, is defined in the usual way as the maximum mutual information between the random variables X and Yj. Without loss of generality, we shall assume that c, > c, > . ‘. > c,. (1) There are no equalities in (I), but we shall show later that this is not a restriction. We now wish to use this broadcast channel with N components to transmit the output of N independent sources s,,s,,. -. ,S, to N users, connected to the outputs of the component channels, on a one-to-one basis. By this, we mean that the output of the jth source is intended to be received by the jth receiver (Fig. 3). Subsequent arguments in Section IV will remove this restriction in interpretation. B. Broadcast Codes Let Zj be the set of possible outcomes of source Sj and let all the elements of Zj have same probability. This is not a loss of generality in a channel coding theorem, and, in fact, represents the worst case. The length of the code is n. The size of Zj is Mj, and the rate of source Sj is given by Rj = ! log, Mj (2) n198 n Fig. 2. Considering components only. SOURCES BROAKAST CECODERS CHANNEL Fig. 3. Broadcast communication system. For notational convenience, we define i = (il,i,; 3 .,iN) z = I, x I, x **. x I, R = (R,,R,,. * *,RN) A-z = w&f,,. * .,MN) A4 = 111 = I”i. Mj. j=l A broadcast code consists of an encoding function x:z+JzP and N decoding functions gj: kzaj” -+ zj. (3) (4) (5) When the source output is i = (il,i2; * a,&), the jth receiver is in error if gj(yj) # ij. The probability of this event will be denoted A;(i) = Pr [gj(yj) # ij 1 x(i) has been sent]. (6) We introduce the following notation for the maximum and average probability of error Ai = max Ai (7) iEI and (8) Again, for notational convenience, let 3, = (fw,; * *A> IEEE TRANSACTIONS ON INFORMATION THEORY, MARCH 1973 Using Wolfowitz’ notation, we define a (M&)-code as a code of length n, size M, and maximum probability of error II. R is an achievable rate if there exists a sequence of (M,n,rZ@‘)-codes, with Mj = Lexp, (nRj)J, such that 1’“’ + 0 when IZ -+ co. The set of achievable rates, or