Capacity of a Class of Diamond ChannelsWei Kang Sennur UlukusDepartment of Electrical and Computer EngineeringUniversity of Maryland, College Park, MD [email protected] [email protected]—We study a special class of diamond channelswhich was introduced by Schein in 2001. In this special class,each diamond channel consists of a transmitter, a noisy relay,a noiseless relay and a receiver. We prove the capacity of thisclass of diamond channels by providing an achievable schemeand a converse. The capacity we show is strictly smaller thanthe cut-set bound. Our result also shows the optimality of acombination of decode-and-forward (DAF) and compress-and-forward (CAF) at the noisy relay node. This is the first examplewhere a combination of DAF and CAF is shown to be capacityachieving. Finally, we note that there exists a duality betweenthis diamond channel coding problem and the Kaspi-Bergersource coding problem.I. PROBLEM STATEMENT AND THE RESULTThe diamond channel was first introduced by Schein in2001 [1]. The diamond channel consists of one transmitter,two relays and a receiver, where the transmitter and the tworelays form a broadcast channel as the first stage and thetwo relays and the receiver form a multiple access channelas the second stage. The capacity of the diamond channel inits most general form is open. Schein explored several specialcases of the diamond channel, one of which [1, Section 3.5]is specified as follows (see Figure 1). The multiple accesschannel consists of two orthogonal links with rate constraintsR1and R2, respectively. The broadcast channel contains anoisy branch and a noiseless branch, i.e., with input X andtwo outputs X and Y . We refer to the relay node receivingY as the noisy relay and the relay node receiving X as thenoiseless relay. Schein provided two achievable schemes forthis class of diamond channels. In this paper, we will provethe capacity of this special class of diamond channels.The formal definition of the problem is as follows. Con-sider a channel with input alphabet X and output alphabet Y,which is characterized by the transition probability p(y|x).Assume an n-length block code consisting of (f, g, h, ϕ)wheref :{1, 2, . . . , M} 7→ Xn(1)g :Yn7→ {1, 2, . . . , |g|} (2)h :{1, 2, . . . , M } 7→ {1, 2, . . . , |h|} (3)ϕ :{1, 2, . . . , |g|} × {1, 2, . . . , |h|} 7→ {1, 2, . . . , M } (4)Here f denotes the encoding function at the transmitter, g andh denote the processing functions at the noisy and noiselessThis work was supported by NSF Grants CCF 04-47613, CCF 05-14846,CNS 07-16311 and CCF 07-29127.(Relay 2)XnYnR1R2Noisy relay(Relay 1)DecoderEncoderNoiseless relayXnFig. 1. The diamond channel.relays, respectively, and ϕ denotes the decoding function atthe receiver.The encoder sends xn= f (m) into the channel, wherem ∈ {1, 2, . . . , M}. The decoder reconstructs ˆm =ϕ(g(Yn), h(m)). The average probability of error is definedasPe,1MMXm=1P r( ˆm 6= m|m is sent) (5)The rate triple (R, R1, R2) is achievable if for every 0 <ǫ < 1, η > 0 and every sufficiently large n, there exists ann-length block code (f, g, h, ϕ), such that Pe≤ ǫ and1nln M ≥ R − η (6)1nln |g| ≤ R1+ η (7)1nln |h| ≤ R2+ η (8)The following theorem characterizes the capacity of theclass of diamond channels considered in this paper.Theorem 1 The rate triple (R, R1, R2) is achievable in theabove channel if and only if the following conditions aresatisfiedR ≤ I(U; Y ) + H(X|U) (9)R1≥ I(Z; Y |U, X) (10)R2≥ H(X|Z, U) (11)R1+ R2≥ R + I(Y ; Z|X, U ) (12)for some joint distributionp(u, z, x, y) = p(u, x)p(y|x)p(z|u, y) (13)with cardinalities of alphabets satisfying|U| ≤ |X | + 4 (14)|Z| ≤ |U||Y| + 3 ≤ |X ||Y| + 4|X | + 3 (15)II. THE ACHIEVABILITYAssume a given joint distributionp(u, z, x, y) = p(u, x)p(y|x)p(z|u, y) (16)and consider that the information theoretic quantities on theright hand sides of (9), (10), (11) and (12) are evaluated withthis fixed joint probability distribution.Consider a message W with rate R. If R ≤ H(X|Z, U ),reliable transmission can be achieved by letting g(Yn) = φ(constant) and h(W ) = W , i.e., by sending the messagethrough the noiseless relay. Thus, we will only consider thecase whereH(X|Z, U ) < R ≤ I(U; Y ) + H(X|U) (17)We will show that the message can be reliably transmittedwith a pair of functions (g, h) such that (1nln |g|,1nln |h|)lies in the inverse pentagon1with corners a and b in Figure2. However, we instead prove reliable transmission with(1nln |g|,1nln |h|) lying in the inverse pentagon with cornersa′and b′, which contains the inverse pentagon with cornersa and b and thus imposes a stronger condition to prove. Itis straightforward to have reliable transmission with the ratepair at point b′by letting g(Yn) = φ (constant) and h(W ) =W . Thus, it remains to prove that reliable transmission ispossible with the rate pair at point a′, i.e.,R1= I(U ; Y ) + I(Y ; Z|U) (18)R2= R − I(U; Y ) − I(X; Z|U) (19)Let us assume that the message W is decomposed as W =(Wa, Wb, Wc). For a positive number ǫ, let us defineMa, |Wa| = exp(n(I(U; Y ) − 3ǫ)) (20)Mb, |Wb| =MMaMc= exp(ln M − n(I(U; Y ) + I(X; Z|U) + 6ǫ)) (21)Mc, |Wc| = exp(n(I(X; Z|U ) − 3ǫ)) (22)Random codebook generation: We use a superpostion codestructure. The size of the inner code is Ma. For each innercodeword, we independently generate Mbouter codes. Thesize of each outer code is Mc.• Independently generate Masequences,un(1), un(2), . . . , un(Ma), according toQni=1p(ui)where p(ui) = p(u), for i = 1, 2, . . . , n.• For un(j), j = 1, 2, . . . , Ma, independently generateMbcodebooks, C(j, 1), C(j, 2), . . . , C(j, Mb).• In the codebook C(j, k), j = 1, 2, . . . , Ma, k =1, 2, . . . , Mb, independently generate Mccodewords1By “inverse pentagon” with corner points a and b, we mean the region inthe (R1, R2) space that is to the “north-east” of line segment [a, b]. Morespecifically, this is the region described by inequalities in (10), (11) and(12).xn(j, k, 1), xn(j, k, 2), . . . , xn(j, k, Mc) according toQni=1p(xi|Ui= ui(j)), where p(xi|U = ui(j)) =p(x|u), for i = 1, 2, . . . , n , j = 1 , 2, . . . , Ma, k =1, 2, . . . , Mb.There will be no overlapping codebooks with high probabilitywhen n is sufficiently large, because1nln MbMc< H(X|U ) (23)Encoding at the transmitter: Let W = (Wa, Wb, Wc) bethe message. We send codeword Xn= f(Wa, Wb, Wc) ,xn(Wa, Wb, Wc) into the channel.Processing at the noisy relay: First,