1 On the Reliability Function of the Common-Message Broadcast Channel with Variable-Length Feedback Lan V. Truong and Vincent Y. F. Tan Abstract Wederiveupperandlowerboundsonthereliabilityfunctionforthecommon-messagediscretememorylessbroadcastchannel 7 with variable-length feedback. We show that the bounds are tight when the broadcast channel is stochastically degraded. For 1 the achievability part, we adapt Yamamoto and Itoh’s coding scheme by controlling the expectation of the maximum of a set 0 of stopping times. For the converse part, we adapt Burnashev’s proof techniques for establishing the reliability functions for 2 (point-to-point) discrete memoryless channels with variable-length feedback and sequential hypothesis testing. n a Index Terms J Variable-length feedback, Reliability function, Error exponent, Broadcast channel, Stochastic degradation 2 1 I. INTRODUCTION ] T Shannon[1] showedthatnoiselessfeedbackdoesnotincrease the capacityof single-usermemorylesschannels.Despite this I seeminglynegativeresult,feedbacksignificantlysimplifiescodingschemesandimprovestheperformanceintermsoftheerror . s probability [2]–[6]. Burnashev [7] demonstrated that the reliability function for the discrete memoryless channel (DMC) with c feedbackimprovesdramaticallywhen the transmission time is random.This is knownas variable-lengthfeedback.In fact, the [ reliability function of a DMC with variable-length feedback admits a particularly simple expression 2 v R E(R)=B 1 (1) 0 1 − C 3 (cid:18) (cid:19) 5 forallrates0 R C,whereC isthecapacityoftheDMCandB1 isdeterminedbytherelativeentropybetweenconditional ≤ ≤ 1 outputdistributionsofthetwomost“mostdistinguisable”channelinputsymbols[7].YamamotoandItoh[8]proposedasimple 0 and conceptuallyimportanttwo-phase codingscheme that attains the reliability functionin (1). Since these reliability function . 1 (or error exponent) results are of paramount importance in practical single-user feedback communication systems, we are 0 motivated to extend the results to a simple network scenario—namely, the discrete memoryless broadcast channel (DM-BC) 7 with a common message (also known as the common-message DM-BC) [4], [9], [10]. We provide upper and lower bounds 1 on the reliability function and show that the bounds coincide if the DM-BC is stochastically degraded. In this scenario, the : v reliability function is dominated by the “worst branch” of the DM-BC. i X A. Main Contributions r a Our main technical contributions are as follows: Firstly,fortheachievabilitypart,wegeneralizeYamamotoandItoh’scodingscheme[8]sothatitisapplicabletotheDM- • BC with a common message and variable-lengthfeedback. In this enhanced scheme, we supplement some new elements to the original arguments in [8]. These include (i) defining an appropriate set of K stopping times and (ii) proving that the expectation of the maximum of these K stopping times can be appropriately bounded assuming that the individual stopping times’ expectations and variances are also appropriately bounded. This complication of having to control the maximum of a set of stopping times does not arise in single-user scenarios such as [7], [11], [12]. Secondly, for the converse part, we adapt and combine proof techniques introduced by Burnashev for two different • problems—namely,thereliabilityfunctionforDMCswithvariable-lengthfeedbackin[7]andthatforsequentialhypothesis testingin [11]. Thisallowsustoobtainanupperboundforthereliabilityfunctionforthe common-messageDM-BCwith variable-length feedback. There is an alternative and more elegant proof technique to establish the converse part of (1) by Berlin et al. [13] but generalizing the technique therein to our setting does not seem to be feasible. Thirdly, even though the bounds on the reliability function do not match for general DM-BCs, we identify a particular • class of DM-BCs, namely stochastically degraded DM-BCs [14, Sec. 5.6] for which the reliability function is known The authors are with the Department of Electrical and Computer Engineering, National University of Singapore (NUS). V. Y. F. Tan is also with the Department ofMathematics, NUS.Emails:[email protected];[email protected] TheauthorsaresupportedbyanNUSYoungInvestigatorAward(R-263-000-B37-133)andaSingaporeMinistryofEducation(MOE)Tier2grant(R-263- 000-B61-112). 2 exactly. For the less capable DM-BCs (to be defined formally in Definition 3), even though we only have bounds on the reliability function, from these bounds, we can establish the capacity of such channels with variable-length feedback. B. Related Works We summarize some related works in this subsection. In [11], Burnashev extended the ideas in his original paper in DMCs with variable-length feedback [7] to be amenable to the more general problem of sequential hypothesis testing. In particular, he studied the minimum expected number of observations (transmissions) to attain some level of reliability and found the reliabilityfunctionforlargeclassofsingle-userchannels(beyondDMCs),includingtheGaussianchannel[11].Berlinetal.[13] provideda simple converseproof for Burnashev’s reliability function [7]. Their converse proof suggests that a communication and a confirmation phase are implicit in any scheme for which the probability of error decreases exponentially fast with (the optimal) exponent given by (1). Under this viewpoint, this converse proof approach is parallel to the Yamamoto and Itoh’s achievabilityscheme[8].Nakibog˘luandGallager[12]investigatedvariable-lengthcodingschemesfor(notnecessarilydiscrete) memoryless channels with variable-length feedback and with cost constraints and established the reliability function. Their achievability proof is an extension of Yamamoto and Itoh’s [8] and their converse proof uses two boundson the difference of the conditionalentropyrandomvariablesimilarly to [7] with some extraargumentsto accountfor the averagecostconstraints. Chen, Williamson, and Wesel [15] proposed a two-phase stop-feedbackcoding scheme where each phase uses an incremental redundancy scheme achieving Burnashev’s reliability function (1) while maintaining an expansion of the size of the message set that yields a small backoff from capacity. Their coding scheme uses a stop-feedback code [16] for the first-phase and a sequential probability ratio test [17] for the second-phase. We also mention the work by Shrader and Permuter [18] who studied the feedback capacity of compound channels [19], [20].Theauthorsconsideredfixed-lengthfeedbackwhileourfocusisonvariable-lengthfeedback.MahajanandTatikonda[21] consideredthevariable-lengthcaseforthesamechannelandestablishedinnerandouterboundsontheso-callederrorexponent region.While the common-messageDM-BCwe studyis somewhatsimilar tothe compoundchannel[19], [20], the techniques we use are different and we establish the exact reliability function for stochastically degraded DM-BCs. Tchamkerten and Telatar, in a series of elegant works [22]–[24], considered conditions in which one can achieve Burnashev’s exponent in (1) universally, i.e., without precise knowledge of the DMC. Recently, there have also been numerous efforts to establish fundamental limits of single- and multi-user channels with variable-length feedback for non-vanishing error probabilities. See [9], [10], [16], [25], [26] for an incomplete list. However, we are concerned with quantifying the exponential rate of decay of the error probability similarly to (1). C. Paper Organization The rest of this paper is structured as follows: In Section II, we provide the problem formulation for the DM-BC with a common message under variable-length feedback with termination. The main results concerning the reliability function, conditions under which the results are tight, and some accompanyingdiscussions are stated in Section III. In Section IV, we provide the achievability proof. The converse proof is provided in Section V. We also explain the novelties of our arguments relative to existing works at the end of the proofs in Sections IV and V. Auxiliary technical results that are not essential to the main arguments are relegated to the appendices. II. PROBLEM SETTING A. Notational Conventions We use asymptotic notation such as O() in the standard manner; f(n) = O(g(n)) holds if and only if the implied · constant limsup f(n)/g(n) < . Also f(n)=o(g(n)) if and only if lim f(n)/g(n) =0. In this paper, we use lnx to denote thne→n∞at|ural logarit|hm ∞so information units throughout are in natsn.→T∞he|binary ent|ropy function is defined as h(x):= xlnx (1 x)ln(1 x) forx [0,1].We alsodefinethe function(x) :=x1 x a forx,a R. Theminimum a of two nu−mbers−a and−b is den−oted interch∈angeably as min a,b and a b. As is usual i{n in≥form}ation the∈ory Zj denotes the { } ∧ i vector (Z ,Z ,...,Z ). i i+1 j For any discrete product sample space , a sigma-algebra on , two random variables Z,T (not necessary Z ×T F Z ×T 3 measurable with respect to ), and two regular conditional probability measures P( ),Q( ) on , define F ·|F ·|F Z×T (Z ):= P(z )lnP(z ), (2) H |F − |F |F z X∈Z H(Z):= (Z σ( , )), (3) H | ∅ Z ×T P(z,tσ( , )) D(P Q):= P(z,tσ( , ))ln | ∅ Z×T , (4) k | ∅ Z×T Q(z,tσ( , )) (z,t)X∈Z×T | ∅ Z×T P(z,t ) (Z;T ):= P(z,t )ln |F , (5) I |F |F P(z )P(t ) (z,t)X∈Z×T |F |F I(Z;T):= (Z;T σ( , ). (6) I | ∅ Z×T If =σ(Yn) for some vector Yn, we write σ(Yn) as Yn in all above notations (2)–(6) for simplicity [27]. F B. Basic Definitions Definition 1. A (M,N)-variable-length feedback code with termination (VLFT) for a K-user DM-BC P with a common message, where N is a positive real and M is a positive integer, is defined by Y1,Y2,...,YK|X A set of equiprobable messages = 1,2,...,M . •• A sequence of encoders fn :W ×WY1n−{1×Y2n−1×}···×YKn−1 →X,n≥1, defining channel inputs Xn =fn(W,Y1n−1,Y2n−1,··· ,YKn−1). (7) K sequences of decoders g(j) : n ,j =1,2,...,K, providing the best estimate W at time n at the corresponding • n Yj →W decoders. A stopping random variable τ := max τ ,τ ,...,τ , where for each j 1,2,...,K , τ is a stopping time of the 1 2 K j • { } ∈ { } filtration σ(Yn) . Furthermore, τ satisfies the following constraint: { j }∞n=0 E(τ) N. (8) ≤ The final decision at decoder j =1,2,...,K is computed at time τ as follows: j Wˆ =g(j)(Yτj). (9) j τj j The error probability of a given variable-length coding scheme is defined as K P (R,N):=P Wˆ =W . (10) e j { 6 } (cid:18)j=1 (cid:19) [ The rate of the (M,N)-VLFT code (cf. Definition 1) is defined as lnM R := . (11) N N Definition 2. (R,E) R2 is an achievablerate-exponentpair if there exists a family of (M ,N)-VLFT codes (for N ) ∈ + N →∞ satisfying liminfR R, (12) N N ≥ lim P (→R∞,N)=0, (13) e N N →l∞nP (R ,N) liminf e N E, (14) N − N ≥ →∞ where R =N 1lnM . The reliability function of the DM-BC with VLFT is N − N E(R):=sup E :(E,R) is an ach. rate-exp. pair . (15) { } In a VLFT code for the DM-BC, the word “termination” is used to indicate that in order to realize the code in a practical setting, one needs to send a reliable end-of-packet signal by a method other than using the transmission channel. In other words, the encoder decides when to stop the transmission of signals [10], [16]. We now recapitulate a set of orderings of channels [14, Ch. 5]. 4 Definition 3. A DM-BC P is less capable1 [14, Sec. 5.6] (with respect to the first channel P ) if Y1,Y2,...,YK|X Y1|X I(X;Y ) min I(X;Y ) (16) 1 j ≤1 j K ≤ ≤ for all P . A DM-BC P is stochastically degraded[14, Sec. 5.4] (with respect to P ) if there exists a random variableXY˜ such that Y1,Y2,...,YK|X Y1|X 1 Y˜ X =x P ( x), y˜ , and (17) 1|{ }∼ Y1|X ·| ∀ 1 ∈Y1 X Y Y˜ , j =2,3,...,K (18) j 1 − − ∀ A DM-BC P is physically degraded [14, Sec. 5.4] (with respect to P ) if Y1,Y2,...,YK|X Y1|X X Y Y (19) j 1 − − forms a Markov chain for all j =2,...,K. Clearly, the set of all physically degraded DM-BCs contained in the set of all stochastically degraded DM-BCs which is containedinthesetofalllesscapableDM-BCs.Weomitanothercommonly-encounteredsetoforderingsforDM-BCs,namely less noisy DM-BCs [14, Sec. 5.6]. Definition 4. For a DM-BC with a common message and VLFT as in Definition 1 we define for each 1 j K, ≤ ≤ B := max min D(P ( x) P ( x), (20) x,x′ 1 j K Yj|X ·| k Yj|X ·| ′ ∈X ≤ ≤ B := max D(P ( x) P ( x)), (21) j x,x′ Yj|X ·| k Yj|X ·| ′ ∈X B := max B , (22) max j 1 j K ≤ ≤ P (y x) Tj := max Yj|X | , (23) x,x′∈X,y∈Yj PYj|X(y|x′) C :=max min I(X;Y ), (24) j PX 1≤j≤K C :=maxI(X;Y ), (25) j j PX C := min maxI(X;Y ). (26) j 1≤j≤K PX III. MAIN RESULTS We now state boundson the reliability functionof the K-userDM-BC channelP with a commonmessage and with VLFT. Y1,Y2,...,YK|X Theorem 1. For any K-user DM-BC channel P with VLFT (cf. Definition 1) such that B < , Y1,Y2,...,YK|X max ∞ R E(R) B 1 , R<C, (27) ≥ − C ∀ (cid:18) (cid:19) and R E(R) min B 1 , R<C. (28) j ≤1≤j≤K (cid:18) − Cj(cid:19) ∀ Since the reliability function yields bounds on the capacity of the DM-BC, we immediately obtain the following. Corollary 1. Under the condition Bmax < , the capacity of the DM-BC with VLFT, namely CBC-VLFT, satisfies ∞ C CBC-VLFT C. (29) ≤ ≤ Although there is, in general, a gap between the upper and lower boundson the reliability function (and capacity) provided inTheorem1(andCorollary1),undersomeconditionsontheDM-BC,thereliabilityfunction(andcapacity)isknownexactly. Theorem 2. For a less capable DM-BC with VLFT such that B < , max ∞ R R B 1 E(R) B 1 , R<C . (30) 1 1 − C ≤ ≤ − C ∀ (cid:18) 1(cid:19) (cid:18) 1(cid:19) 1Intheliterature [14,Sec.5.6],thetermmorecapable istypically usedwhenY1 isthe“strongest receiver”. However, inourcontext, Y1 isthe“weakest receiver” soweusethe(somewhatatypical) termlesscapablehere. 5 Furthermore, if the DM-BC with VLFT is stochastically degraded (or physically degraded), R E(R)=B 1 , R<C . (31) 1 1 − C ∀ (cid:18) 1(cid:19) Corollary 2. Under the condition B < , the capacity of any less capable DM-BC with VLFT max ∞ CBC-VLFT =C =C1 =C. (32) Proof of Theorem 2 and Corollary 2: For any less capable DM-BC we have I(X;Y ) I(X;Y ) for all P and for all 1 j X ≤ j =2,3,...,K. Hence, C =max min I(X;Y ), (33) j PX 1≤j≤K =maxI(X;Y )=C . (34) 1 1 PX Pluggingthis into (27) establishes the lower boundin (30). For less capable DM-BCs, we also have C =max I(X;Y ) 1 PX 1 ≤ C =max I(X;Y ) for all j =2,3,...,K, hence j PX j C := min maxI(X;Y ) (35) j 1≤j≤K PX =maxI(X;Y )=C . (36) 1 1 PX As a result, for less capable DM-BCs, the capacity is C =C =C, establishing (32). Moreover,from (28) in Theorem 1, for 1 all R<C =C (cf. Eqn. (36)), 1 R R E(R) min B 1 B 1 . (37) j 1 ≤1≤j≤K (cid:18) − Cj(cid:19)≤ (cid:18) − C1(cid:19) This establishes the upper bound in (30). For stochastically degraded DM-BCs, there exists a random variable Y˜ such that X Y Y˜ for all j =1,2,...,K and 1 j 1 − − P =P . Therefore, we have Y˜1|X Y1|X D(PY1|X(·|x)kPY1|X(·|x′))=D(PY˜1|X(·|x)kPY˜1|X(·|x′)). (38) Observe that for any x,x and j 2,3,...,K , we also have ′ ∈X ∈{ } P (y x) D(PY1|X(·|x)kPY1|X(·|x′))=Xy1 PY1|X(y1|x)lnPYY11||XX(y11||x′) (39) P (y y x) =Xy1 Xyj PY˜1Yj|X(y1yj|x)ln PyyjjPY˜Y˜11YYjj||XX(y11yjj||x′) (40) =Xy1 Xyj PYj|X(yj|x)PY˜1|Yj(yP1|yj)ln PyyjjPPYYjj||XX((yyjj||xx′))PPY˜Y˜11||YYjj((yy11||yyjj)) (41) ≤Xy1 Xyj PYj|X(yj|x)PY˜1|Yj(y1|yj)lnPPPYYjj||XX((yyjj||xx′)) (42) P (y x) =Xyj PYj|X(yj|x)lnPYYjj||XX(yjj||x′) Xy1 PY˜1|Yj(y1|yj)! (43) =D(P ( x) P ( x)). (44) Yj|X ·| k Yj|X ·| ′ Here, (41) follows from the Markov chains X Y Y˜ for j =1,2,...,K and (42) follows from the log-sum inequality. j 1 − − It follows that B = max min D(P ( x) P ( x)) (45) x,x′ 1 j K Yj|X ·| k Yj|X ·| ′ ∈X ≤ ≤ = max D(P ( x) P ( x))=B , (46) x,x′ Y1|X ·| k Y1|X ·| ′ 1 ∈X and hence (31) is established. A few remarks concerning Theorem 1 are in order. There is a gap between the lower and upperboundsfor the generalDM-BC. One reason that pertainsto the achievability • part is because each decoderj 1,2,...,K , at time n, only has its own sequence Yn. Thus, it is difficultto establish ∈{ } j 6 an appropriate hypothesis test within the coding scheme by Yamamoto-Itoh [8] such that this hypothesis test works for any possible realization of the other random variables Yn :i=j . { i 6 } For the converse, if we use the same hypothesis test for single-user channels with VLFT as in Berlin et al.’s work [13], • it is challenging to obtain a useful result. The hypothesis test in [13, Prop. 1] involves the sufficient statistic V := n lnPA(Y1n)−lnPN(Y1n). Because Xk dependson (W,Y1k−1,...,YKk−1) for each k ∈N (cf. Eqn. (7)), we cannotsimply append (Yn,...,Yn) to Yn in the expression for V and still obtain the desired upper bound as in [13, Prop. 1]. 2 K 1 n Moreover, if we directly adapt the key ideas in Burnashev’s converse proof for sequential hypothesis testing in [11, • Lemmas 3 and 4], we will only obtain the following almost sure bound for each j 1,...,K : ∈{ } E (W Yn) (W Yn+1)Yn H | j −H | j | j ≤(cid:2)w,mw′a∈xWsunpysjnu−p1D(cid:0)PYj,n|Yjn−1(cid:3),W(·|yjn−1,w)(cid:13)PYj,n|Yjn−1,W(·|yjn−1,w′)(cid:1). (47) (cid:13) This is then insufficient to establish our converse. Our Lemma 6 is stronger than the corresponding one to prove the converse of (1) in Burnashev [7, Lemma 3] since • we do not need to assume that the conditional entropies (W Yn) for j = 1,2,...,K are bounded. Consequently, the H | j construction of submartingales in the proof of Lemma 9 (in the converse proof in Section V) is much simpler. We have a tight reliability functionresult for stochastically degradedDM-BCs in (31). Usually, orderingsof the channels • (less/more capable, less noisy,stochastically and physicallydegraded)are used to obtain tightcapacity or capacity region results for DM-BCs [14, Secs. 3.4 & 3.6]. Here, in contrast, we use the orderings to establish a tight reliability function result. IV. ACHIEVABILITY PROOF OF THEOREM1 In this section, we provide the achievability proof of Theorem 1. We start with a preliminary lemma. Lemma 1 (Expectationof the Maximum of Random Variables). Let (X ,X ,...,X ) be K sequences of random 1L 2L KL L 1 variables satisfying { } ≥ E[X ]=L+o(1), and (48) jL Var(X )=o(1), j =1,2,...,K, (49) jL as L . Then, as L , we have →∞ →∞ E(max X ,X ,...,X )=L+O(√L). (50) 1L 2L KL { } Proof: The proof can be found in Appendix A. The achievability part of Theorem 1 can be stated succinctly as follows. Lemma 2. If B < , max ∞ R E(R) B 1 , R<C. (51) ≥ − C ∀ (cid:18) (cid:19) Proof: The achievability proof is an extension of Yamamoto-Itoh’svariable-length coding scheme [8] for the DMC with noiseless variable-length feedback. However, we devise some additional and crucial ingredients to account for the presence of multiple channel outputs and multiple decoded messages. In the coding scheme, the encoder decides whether or not to stop the transmission. We show that for all L N there exists an ( eRL ,L+O(√L))-VLFT code with achievable exponent ∈ ⌈ ⌉ B(1 R/C). − Choose P :=argmax min I(X;Y ) and x ,x such that X∗ PX 1≤j≤K j c e ∈X (x ,x ):=argmax min D P ( x) P ( x) . (52) c e (x,x′)∈X 1≤j≤K Yj|X ·| k Yj|X ·| ′ (cid:0) (cid:1) Since we assume that B < , we have P (y x)>0 for all y ,x for all j =1,2,...,K. Fix a non-negative number R satisfying 0 mRax<C∞. Yj|X | ∈Yj ∈X ≤ We design a code for each block of L transmissions as per the Yamamoto-Itoh coding scheme with rate R [8]. Let this code length L be divided into two parts, γL for the message mode and (1 γ)L for the control mode. In the message mode, − one of M = eLR messages is transmitted by a random coding scheme with block-length γL [28], and in the control mode ⌈ ⌉ a pair of control signals (c,e) is transmitted by another block code with length (1 γ)L. The control signal c is only sent − when all the K receivers correctly decode the transmitted message in the message mode. Now, the variable-length coding scheme for the DM-BC with a common message is created by repeating the length-L transmission at times n µL : µ = 1,2,3,... and using the same decoding algorithm as in [8] at all the decoders. The ∈ { } decoder j 1,2,...,K defines a stopping time τ as follows: j ∈{ } 7 1) If n µL:µ=2,3,4,... , we define ∈{ } µ 1 1{τj =n}= − 1 gn(j) Yj(,t(−t−11)L)L++LγL+1 =e 1 gn(j) Yjn,(l−1)L+γL+1 =c ; (53) tY=1 n (cid:16) (cid:17) o n (cid:16) (cid:17) o 2) If n=L, we define 1 τ =n =1 g(j) YL =c ; (54) { j } n j,γL+1 3) Otherwise, n (cid:0) (cid:1) o 1 τ =n =1 . (55) j { } {∅} In addition, the estimated message at the stopping time τ has the following form: j Wˆj :=gτ(jj) Yjτ,τjj−−(1L−γ)L , j =1,2,...,K. (56) (cid:16) (cid:17) Since for j 1,2,...,K is finite, for each fixed n Z all the decoding regions at each decoder j are finite sets, j + whichYare Borel∈se{ts in Rn. Co}mbining this fact with the de∈finition of τ , we have 1 τ =n σ(Yn) for all n N. Let j { j }∈ j ∈ q(j) :=P g(j)(YL )=e , j =1,2,...,K. (57) L n j,γL+1 (cid:16) (cid:17) Bytheproposedtransmissionmethod,givenW =w wehavethatY(t−1)L+L fort Nareindependentrandomvectors. ∈W j,(t 1)L+1 ∈ Since the messages in are equiprobable, we obtain − W q(j) l−1 1 q(j) , if n µL:µ=1,2,3,... P(τj =n)= L − L ∈{ }. (58) (0(cid:2), (cid:3) (cid:2) (cid:3) otherwise Hence, we have ∞ P(τj =n)= ∞ qL(j) µ−1 1−qL(j) =1. (59) n=0 µ=1 X X(cid:2) (cid:3) (cid:2) (cid:3) Thus, τ is a stopping time with respect to σ(Yn) . j { j }∞n=0 Now, since we use the same decoding algorithm as [8] for each repeated transmission block of length L at each decoder j, it is easy to see that the error probability for the j-th decoder P(j) :=P(Wˆ =W) and q(j) can be written as follows [8]: E j 6 L P(j) =P(j)P(j), (60) E 1e 2ec q(j) =P(j)(1 P(j))+(1 P(j))P(j). (61) L 1e − 2ec − 1e 2ce Here, P(j), P(j), and P(j) respectively denote the error probability of decoderj in the message mode, the probabilitythat the 1e 2ec 2ce message e is sent at the control mode but the decoder j decodes the message c, the probability that c is sent at the control mode but the decoder j decodes e [8, pp. 730]. Since q(j) is the same for all repeated transmissions, each of blocklength L, we have for all j =1,2,...,K, L ∞ E(τ )= nP(τ =n) (62) j j n=0 X = ∞ µL q(j) µ−1 1 q(j) (63) L − L µ=1 X (cid:2) (cid:3) (cid:2) (cid:3) L = . (64) 1 q(j) − L In addition, we also have L2q(j) Var(τ )= L . (65) j 1 q(j) 2 − L Let l := (1−γ)L. We assign length-l codewords Xcl = (xc(cid:2),xc,...,(cid:3)xc) ∈ Xl and Xel = (xe,xe,...,xe) ∈ Xl to control the signals c and e respectively. Decoding of the control signal is done as follows. Choose an arbitrarily small δ >0. Let us say the number of output symbols y contained in the received sequence Yl =yl equals to l 1,...,l . We suppress ∈Yj j j y ∈{ } the dependence of l on j for notational convenience. If every l satisfies the typicality condition y y l (1 δ)P (y x ) y (1+δ)P (y x ), (66) − Yj|X | c ≤ l ≤ Yj|X | c 8 then yl is decoded to c, otherwise to e. Then, defining F() to be the random coding error exponent for DMCs [28] and j · R :=R/γ <min I(X;Y )=C (since X P ), it follows from [8] that Lγ 1≤j≤K j ∼ X∗ . P(j) exp[ γLF(R )], (67) 1e ≤ − Lγ . P(j) exp[ (1 γ)L(f (δ) o(1))], (68) 2ce ≤ − − j − . where f (δ)>0 for any δ >0. In (67) and (68) we used the usual notation a b to mean that limsup 1 logaL 0. Also, byjStein’s lemma, L ≤ L L→∞ L bL ≤ lnP(j) lim 2ec =D P ( x ) P ( x ) . (69) L −(1 γ)L Yj|X ·| c k Yj|X ·| e →∞ − (cid:0) (cid:1) Moreover from (60) and (67)–(68) we have . q(j) exp( Lc(j)), j =1,2,...,K (70) L ≤ − for some exponent c(j) >0. Consequently, from (64), (65), and (70) we obtain for all j that E(τ )=L+o(1), (71) j Var(τ )=o(1). (72) j From (71), (72), and Lemma 1 we obtain that E(τ)=L+O(√L). (73) Now, since for each j =1,2,...,K, P(j) is kept the same for all repeated transmission blocks of length L, we have E K P (R,L+O(√L)) P(j). (74) e ≤ E j=1 X Moreover, it is easy to see from (60), (67)–(68), and (73) that P(j) 0 for all j = 1,2,...,K as L if 0 R = R/γ <C and 0 γ <1. Combining these requirementsand (74),Ewe→have P (R,L+O(√L)) 0 as L→ ∞ if w≤e chLoγose e ≤ → →∞ 1>γ >R/C. Now, since γ >R/C, a feasible value of γ that we can choose is R γ = , (75) C ε − where ε>0 is chosen small enough so that γ remains smaller than 1. It follows that for any R [0,C), we have ∈ lnP (R,L+O(√L)) ln K P(j) liminf e liminf j=1 E (76) L→∞ − L+O(√L) ≥ L→∞ − L(cid:0)P+O(√L)(cid:1) ln(KP(j)) liminf min E (77) ≥ L (1 j K−L+O(√L)) →∞ ≤ ≤ lnP(j) = min liminf E (78) 1 j K( L −L+O(√L)) ≤ ≤ →∞ lnP(j) min lim 2ec (79) ≥1 j K(L − L ) ≤ ≤ →∞ R = min D(P ( x ) P ( x )) 1 (80) 1 j K Yj|X ·| c k Yj|X ·| e − C ε ≤ ≤ (cid:18) − (cid:19) R =B 1 , (81) − C ε (cid:18) − (cid:19) where (78) follows from the facts that K is a constant and that liminf min a = min liminf a for any L j jL j L jL →∞ { } →∞{ } family of sequences a ; (79) follows from (60); and (80) follows from (69) and (75). jL { } This means that (R,B(1 R/(C ε))) is an achievable rate-exponent pair for any 0 R < C. By the arbitrariness of − − ≤ ε>0, we obtain R E(R) B 1 . (82) ≥ − C (cid:18) (cid:19) 9 Finally, for anyN R chooseL= N O(√N) such thatL+O(√L) N. By usingthe ( eRL ,L+O(√L))-VLFT + ∈ ⌊ − ⌋ ≤ ⌈ ⌉ code constructed above, we conclude that there exists an ( e (N O(√N))R ,N)-VLFT code such that (51) holds. ⌊ − ⌋ ⌈ ⌉ We remark that for the proof of Lemma 2, we extended Yamamoto and Itoh’s coding scheme [8] for the DM-BC with a commonmessage andVLFT.In theproof,we supplementedsomenewelementsto theoriginalargumentin [8].These include defining appropriate stopping times τ ,τ ,...,τ and proving that the expectation of the maximum of these K stopping 1 2 K { } times with expectations and variances respectively bounded by L+o(1) and o(1) is L+O(√L) (cf. Lemma 1). V. CONVERSE PROOF OF THEOREM1 In this section, we provide the converse proof of Theorem 1. We start with a few preliminary lemmas. At the end of the proof(aftertheproofofLemma9),we discussthenovelitesinourconverseproofvis-a`-visBurnashev’sworksin[7]and[11]. Lemma 3. Under the condition that P(τ < )=1 (cf. Definition 1), the following inequalities hold ∞ E (W Yτj) h(P (R ,N))+P (R ,N)ln(M 1), (83) H | j ≤ e N e N − for each 1 j K and N sufficie(cid:2)ntly large. (cid:3) ≤ ≤ Proof: The proof of this Lemma is essentially the same as [11, Lemma 1]. For completeness and compatibility in the notations, we provide the complete proof in Appendix B. Note that the error event here is different from [11, Lemma 1]. It is the union of error events of individual branches of the DM-BC, i.e., K Wˆ =W . ∪j=1{ j 6 } Lemma 4. For any n 0 the following inequalities hold almost surely (cf. Definition 4) ≥ E[ (W Yn) (W Yn+1)Yn] C , 1 j K. (84) H | j −H | j | j ≤ j ≤ ≤ Proof: Observe that E[ (W Yn) (W Yn+1)Yn]=E[ (W Yn) (W Yn+1)Yn] (85) H | 1 −H | 1 | 1 H | 1 −H | 1 | 1 =E[ (W;Y Yn)Yn] (86) I 1,n+1| 1 | 1 = (W;Y Yn) (87) I 1,n+1| 1 (W,X ;Y Yn) (88) ≤I n+1 1,n+1| 1 (X ;Y Yn)+ (W;Y X =x,Yn)P(X =xYn). (89) ≤I n+1 1,n+1| 1 I 1,n+1| n+1 1 n+1 | 1 x X∈X Now, for any fixed Yn =yn, the (random) mutual information in the sum can be expressed as 1 1 (W;Y X =x,Yn =yn) I 1,n+1| n+1 1 1 =I(W;Y X =x,Yn =yn) (90) 1,n+1| n+1 1 1 = P(W =w,Y =y X =x,Yn =yn) 1,n+1 | n+1 1 1 w∈WX,y∈Y1 P(W =w,Y =y X =x,Yn =yn) ln 1,n+1 | n+1 1 1 . (91) × P(W =wX =x,Yn =yn)P(Y =y X =x,Yn =yn) | n+1 1 1 1,n+1 | n+1 1 1 Since(W,Yn,Yn,...,Yn) X (Y ,Y ,...,Y )formsaMarkovchain,weobviouslyalsohavethefollowing 1 2 K − n+1− 1,n+1 2,n+1 K,n+1 Markov chain: (W,Yn) X Y . (92) 1 − n+1− 1,n+1 Hence, we have P(W =w,Y =y X =x,Yn =yn) (93) 1,n+1 | n+1 1 1 =P(W =wX =x,Yn =yn)P(Y =y X =x,Yn =yn,W =w) (94) | n+1 1 1 1,n+1 | n+1 1 1 =P(W =wX =x,Yn =yn)P(Y =y X =x) (95) | n+1 1 1 1,n+1 | n+1 =P(W =wX =x,Yn =yn)P(Y =y X =x,Yn =yn). (96) | n+1 1 1 1,n+1 | n+1 1 1 From (91) we obtain (W;Y X =x,Yn =yn)=0, (x,yn) n. (97) I 1,n+1| n+1 1 1 ∀ 1 ∈X ×Y1 It follows from (89) that E[ (W Yn) (W Yn+1)Yn] (X ;Y Yn) (98) H | 1 −H | 1 | 1 ≤I n+1 1,n+1| 1 C , a.s. (99) 1 ≤ 10 A completely analogous argument goes through to yield the corresponding upper bounds for j =2,3,...,K. We remark that in the above proof, we need to use some additional arguments involving the Markov chain in (92) to show that Lemma 4 holds in the (general DM-BC) case where X is a function of W and all Yn for j = 1,2,...,K. In the n+1 j DMC, X is a function of W and only Yn. n+1 1 The following lemma is a restatement of [7, Lemma 7]. Lemma 5. For arbitrary non-negative numbers p ,f ,β where l = 1,2,...,L and i = 1,2,...,N, we have the following l i il inequality L N L f f p ln i=1 i max p ln i . (100) l=1 l PNi=1βil!≤ i l=1 l βil X X Lemma 6. For any n 0 the following inequalitiesPhold almost surely (cf. Definition 4) ≥ E[ln (W Yn) ln (W Yn+1)Yn] B , 1 j K. (101) H | j − H | j | j ≤ j ≤ ≤ Proof: The proof is based on Burnashev’s argumentsin [7] and [11] with some modifications to account for the fact that at each transmission time n+1, the transmitted signalX is a functionof W and allYn,Yn,...,Yn. We can assume that n+1 1 2 K P (y x)>0 for all x ,y and all j =1,2,...,K, otherwise the inequalities (101) trivially hold since B = . FoYrj|Xeachj|i=1,2,...,M a∈ndXy j ∈Y, jdefine j ∞ 1 ∈Y p :=P(W =iYn), (102) i | 1 p (y):=P(W =iYn,Y =y), (103) i | 1 1,n+1 p(y W =i):=P(Y =y Yn,W =i), (104) | 1,n+1 | 1 p(y W =i):=P(Y =y Yn,W =i), (105) | 6 1,n+1 | 1 6 p(y):=P(Y =y Yn). (106) 1,n+1 | 1 We may assume without loss of generality that p =1 for all i = 1,...,M . Otherwise, again the inequalities in (101) i 6 ∈W { } trivially hold. Using Lemma 5 and the definitions in (102)–(106) we have M p lnp E ln (W Yn) ln (W Yn+1) Yn = p(y)ln − i=1 i i (107) (cid:2) H | 1 − H | 1 (cid:12) 1 (cid:3) yX∈Y1 "− MiP=1pi(y)lnpi(y)# (cid:12) P p lnp max p(y)ln − i i (108) ≤ i yX∈Y1 (cid:20)−pi(y)lnpi(y)(cid:21) Define   p lnp F := p(y)ln − i i (109) i p (y)lnp (y) yX∈Y1 (cid:20)− i i (cid:21) It is easy to see that p(y)=p p(y W =i)+(1 p )p(y W =i), (110) i i | − | 6 p p(y W =i) p (y)= i | , (111) i p(y) and p(y W =i)=P(Y =y Yn,W =i) (112) | 1,n+1 | 1 = P(X =xW =i,Yn)P(Y =y X =x,W =i,Yn) (113) n+1 | 1 1,n+1 | n+1 1 x X∈X = P(X =xW =i,Yn)P(Y =y X =x) (114) n+1 | 1 1,n+1 | n+1 x X∈X =: α P (y x). (115) ix Y1|X | x X∈X Here, (114) follows from the Markovchain (W,Xn,Xn,...,Xn) X (Y ,Y ,...,Y ) and (115) follows 1 2 K − n+1− 1,n+1 2,n+1 K,n+1 from the invariance (stationarity) of the distribution P(Y = y X = x) in n, which is derived from the invariance of 1,n+1 n+1 |