Bit-wise Unequal Error Protection for Variable Length Block Codes with Feedback

The bit-wise unequal error protection problem, for the case when the number of groups of bits $\ell$ is fixed, is considered for variable length block codes with feedback. An encoding scheme based on fixed length block codes with erasures is used to establish inner bounds to the achievable performance for finite expected decoding time. A new technique for bounding the performance of variable length block codes is used to establish outer bounds to the performance for a given expected decoding time. The inner and the outer bounds match one another asymptotically and characterize the achievable region of rate-exponent vectors, completely. The single message message-wise unequal error protection problem for variable length block codes with feedback is also solved as a necessary step on the way.


I. INTRODUCTION
In the conventional formulation of digital communication problem, the primary concern is the correct transmission of the message; hence there is no distinction between different error events. In other words, there is a tacit assumption that all error events are equally undesirable; incorrectly decoding to a messagem when a messagem is transmitted, is as undesirable as incorrectly decoding to a messagem when a messagem is transmitted, for anym other thanm andm other thanm. Therefore the performance criteria used in the conventional formulation (minimum distance between codewords, maximum conditional error probability among messages, average error probability, etc.) are oblivious to any precedence order that might exist among the error events.
In many applications, however, there is a clear order of precedence among the error events. For example in Internet communication, packet headers are more important than the actual payload data. Hence, a code used for Internet communication, can enhance the protection against the erroneous transmission of the packet headers at the expanse of the protection against the erroneous transmission of payload data. In order to appreciate such a coding scheme, one may analyze error probability of the packet headers and error probability of payload data separately, instead of analyzing the error probability of the overall message composed of packet header and payload data. Such a formulation for Internet communication is an unequal error protection (UEP) problem, because of the separate calculation of the error probabilities of the parts of the messages.
Problems capturing the disparity of undesirability among various classes of error events, by assigning and analyzing distinct performance criteria for different classes of error events, are called unequal error protection (UEP) problems. UEP problems have already been studied widely by researchers in communication theory, coding theory, and computer networks from the perspectives of their respective fields. In this paper we enhance the information theoretic perspective on UEP problems [5], [2] for variable length block codes by generalizing the results of [2] to the rates below capacity.
In information theoretic UEP, error events are grouped into different classes and the probabilities associated with these different classes of error events are analyzed separately. In order to prioritize protection against one or the other class of error events, corresponding error exponent is increased at the expense of the other error exponents. This paper was presented in part at ISIT 2010, [6]. Authors acknowledge the support of the NSF through the NSF Cyberphysical Systems Program (NSF0932410) and the NSF Science & Technology Center (CCF-0939370) and support of DARPA through the ITMANET program (W911NF-07-  There are various ways to choose the error event classes but two specific choices of error event classes stand out because of their intuitive familiarity and practical relevance; they correspond to the message-wise UEP and the bit-wise UEP. Below, we first describe these two types of UEP then specify the UEP problems we are interested in this manuscript.
In the message-wise UEP, the message set M is assumed to be the union of ℓ disjoint sets for some fixed ℓ, i.e., M = ∪ ℓ j=1 M j where M i ∩M j = ∅ for all i = j. For each set M j , the maximum error probability 1  In the above discussion the UEP problems are described for fixed length block codes for the sake of simplicity. One can, however, easily define the corresponding problems for various families of codes:with or without feedback, fixed or variable length, by modifying the definitions of the error probability, the rate and the error exponent appropriately. Furthermore parameter ℓ representing the number of groups of bits or messages is assumed to be fixed in the above discussion for simplicity. However, both the message-wise and the bit-wise UEP problems can be defined for ℓ's that are increasing with block length n in fixed length block codes and for ℓ's that are increasing with expected block length E[T] in variable length block codes. In fact Csiszár's result discussed above, [5,Theorem 5], is proved not only for constant ℓ but also for any ℓ n sequence satisfying lim n→∞ ln ℓn n = 0. In this manuscript we consider two closely related UEP problems for variable length block codes over a discrete memoryless channels with noiseless feedback: the bit-wise UEP problem and the single message message-wise UEP problem.
• In the bit-wise UEP problem there are ℓ sub-messages each with different priority and rate. For all fixed values of ℓ we characterize the trade-off between the rates and the error exponents of these sub-messages by revealing the region of achievable rate vector, exponent vector pairs. For fixed ℓ this problem is simply the variable length code version of the above described bit-wise UEP problem. • In the single message message-wise UEP problem, we characterize the trade-off between the exponents of the minimum and the average conditional error probability. Thus this problem is similar to the above described message-wise UEP problem for the case ℓ = 2 and M 1 = {1}. But unlike that problem we work with variable length codes and average conditional error probability rather than fixed length codes and the maximum error probability. The bit-wise UEP problem for fixed number of groups of bits, i.e., fixed ℓ, and the single message message-wise UEP problem were first considered in [2], for the case when the rate is (very close to) the channel capacity; we solve both of these problems for all achievable rates.
In fact, in [2] single message message-wise UEP problem is solved not only at capacity, but also for all the rates below capacity both for fixed length block codes without feedback and for variable length block codes with feedback, but only for case when overall error exponent is zero (see [2,Appendix D]). Recently Wang, Chandar, Chung and Wornell [11] put forward a new proof based on method of types for the same problem. 6 Nazer, Shkel and Draper [9], on the other hand, investigated the problem for fixed length block codes on additive white Gaussian noise channels at zero error exponent and derived the exact analytical expression in terms of rate and power constraints.
Before starting our presentation, let us give a brief outline of the paper. In Section II, we specify the channel model and make a brief overview of stopping times and variable length block codes. In Section III, we first present the single message message-wise UEP problem and fixed ℓ version of the bit-wise UEP problem for variable length block codes; then we state the solutions of these two UEP problems. In Section IV we present inner bounds for both the single message message-wise UEP problem and the bit-wise UEP problem. In Section V we introduce a new technique, Lemma 5, for deriving outer bounds for variable length block codes and apply it to the two UEP problems we are interested in. Finally in Section VI we discuss the qualitative ramifications of our results in terms the design of communication systems with UEP and the limitations of our analysis. The proofs of the propositions in Sections III, IV, V are deferred to the Appendices.

II. PRELIMINARIES
As it is customary we use upper case letters, e.g., M, X, Y, T for random variables and lower case letters, e.g., m, x, y, t for their sample values.
We denote discrete sets by capital letters with calligraphic fonts, e.g., M, X , Y and power sets of discrete sets by ℘(·), e.g., ℘(M), ℘(X ), ℘(Y). In order to denote the set of all probability distributions on a discrete set we use P(·), e.g., P(M), P(X ), P(Y).

A. Channel Model
We consider a discrete memoryless channel (DMC) with input alphabet X , output alphabet Y and |X | − by − |Y| transition probability matrix W . Each row of W corresponds to a probability distribution on Y, i.e., W x ∈ P(Y) for all x ∈ X . For the reasons that will become clear shortly, in Section II-D, we assume that W x (y) > 0 for all x ∈ X and y ∈ Y and denote the smallest transitions probability by λ: λ min The input and output letters at time τ , up to time τ and between time τ 1 and τ 2 are denoted by X τ , Y τ , X τ , Y τ , X τ 2 τ 1 and Y τ 2 τ 1 respectively. DMCs are both memoryless and stationary, hence the conditional probability of Y τ = y given (X τ , Y τ −1 ) is given by P Y τ = y| X τ , Y τ −1 = W Xτ (y).

B. Stopping Times
Stopping times are central in the formal treatment of variable length codes; it is not possible to define or comprehend variable length codes without a solid understanding of stopping times. For those readers who are not already familiar with the concept of the stopping times, we present a brief overview in this section.
In order to make our presentation more accessible, we use the concept of power sets, rather than sigma-fields in the definitions. We can do that only because the random variables we use to define stopping times are discrete random variables. In the general case, when the underlying variables are not necessarily discrete, one needs to use the concept of sigma fields instead of power set.
Let us start with introducing the concept of Markov times. For an infinite sequence of random variables Z 1 , Z 2 , . . ., a positive, integer * valued 7 function T defined on Z ∞ is a Markov time, if for all positive integers τ it is possible determine whether T = τ or not by considering Z τ only, i.e., if 1 {T=τ } is not only a function of Z ∞ but also a function of Z τ for all positive integers τ . The formal definition is given below.
Definition 3 (Markov Time): Let Z ∞ 1 be an infinite sequence of Z valued random variables Z τ for τ ∈ {1, 2, . . .} and T be a function of Z ∞ which takes values from the set {1, 2, . . . , ∞}. Then the random variable T is a Markov time with respect to Z τ if where ℘(Z τ ) × {Z ∞ τ +1 } is the Cartesian product of the power set of Z τ and the one element set {Z ∞ τ +1 }. We denote Z τ 's from τ = 1 to τ = T by Z T and their sample values by z t . The set of all sample values of Z T such that T = τ , on the other hand, is denoted by Z τ {T=τ } . We denote union of all Z τ {T=τ } 's for finite τ 's by Z T * and the union of all Z τ {T=τ } 's by Z T , i.e., For an arbitrary, positive, integer * valued function T of Z ∞ , however, one can not talk about Z T , because the value of T can in principle depend on Z ∞ T+1 . For a Markov time T, however, the value of T does not depend on Z ∞ T+1 . That is why we can define Z T , Z τ {T=τ } , Z T * and Z T for any Markov time T. Given an infinite sequence of z τ 's, i.e., z ∞ , either z ∞ ∈ Z ∞ {T=∞} or z ∞ has a unique subsequence z τ that is in Z T * .
In most practical situations, one is interested in Markov times that are guaranteed to have a finite value; those Markov times are called Stopping times.
Note that if T is a stopping time then P Z T ∈ Z T * = 1. Furthermore unlike Z T , Z T * is a countable set for all stopping times T because |Z| is finite. 8

C. Variable Length Block Codes
A variable length block code on a DMC is given by a random decoding time T, an encoding scheme Φ and a decoding rule Ψ satisfying P[T < ∞] = 1.
• Decoding time T is a Markov time with respect to the receiver's observation Y τ , i.e., given Y τ receiver knows whether T = τ or not. Hence T is a random quantity rather than a constant, thus neither the decoder nor the receiver knows the value of T a priori. But as time passes, both the decoder and the encoder (because of feedback link) will be able to decide whether T has been reached or not, just by considering the current and past channel outputs. • Encoding scheme Φ is a collection of mappings which determines the input letter at time (τ + 1) for each message in the finite message set M, for each y τ ∈ Y τ such that T > τ , Φ(·, y τ ) : M → X ∀y τ : T > τ .
• Decoding Rule is a mapping from the set of output sequences y τ such that T = τ to the finite message set M which determines the decoded message, M. With a slight abuse of notation we denote the set of all, possibly infinite, output sequences y τ such that {T = τ if Y τ = y τ } by 9 Y T and write the decoding rule Ψ as, • Note that because of the condition P[T < ∞] = 1, decoding time is not only a Markov time, but also a Stopping time. 10 At time zero the message M chosen uniformly at random from M is given to the transmitter; the transmitter uses the codeword associated M, i.e., Φ(M, ·), to convey the message M until the decoding time T. Then the receiver chooses the decoded message M using its observation Y T and the decoding rule Ψ, i.e.,M = Ψ(Y T ). The error probability, the rate and the error exponent of a variable length block code are given by Indeed one can interpret the variable length block codes on DMCs as trees, for a more detailed discussion of this interpretation readers may go over [1, Section II]. 8 Z T * is a countable set even when |Z| is countably infinite. 9 See equation (6). 10 Having a finite decoding time with probability one, i.e., P[T < ∞] = 1, does not imply having a finite expected value for the decoding time, i.e., E[T] < ∞. Thus a variable length code can, in principle, have an infinite expected decoding time.

D. Reliable Sequences for Variable Length Block Codes
In order to suppress the secondary terms while discussing the main results, we use the concept of reliable sequences. In a sequence of codes we denote the error probability and the message set of the κ th code of the sequence by P e (κ) and M (κ) , respectively. Definition 5 (Reliable Sequence): A sequence of variable length block codes Q is reliable if the error probabilities of the codes vanish and the size of the message sets of the codes diverge: 11 where P e (κ) and M (κ) are the error probability and the message set for the κ th code of the reliable sequence, respectively.
Note that in a sequence of codes, each code has an associated probability space. We denote the random variables in these probability spaces together with a superscript corresponding to the code. For example the decoding time of the κ th code in the sequence is denoted by T (κ) . The expected value of random variables in the probability space associated with the κ th code in the sequence is denoted 12 Definition 6 (Rate of a Reliable Sequence): The rate of a reliable sequence Q is the limit infimum of the rates of the individual codes,

Definition 7 (Capacity):
The capacity of a channel for variable length block codes is the supremum of the rates of the all reliable sequences.
The capacity of a DMC for variable length block codes is identical to the usual channel capacity, [3]. Hence, whereμ(y) = x µ(x)W x (y).

Definition 8 (Error Exponent of a Reliable Sequence):
The error exponent of a reliable sequence Q is the limit infimum of the error exponents of the individual codes,

Definition 9 (Reliability Function):
The reliability function of a channel for variable length block codes at rate R ∈ [0, C ] is the supremum of the exponents of all reliable sequences whose rate is R or higher.
Burnashev [3] analyzed the performance of variable length block codes with feedback and established inner and outer bounds to their performance. Results of [3] determine the reliability function of variable length block codes on DMCs for all rates. According to [3]: 11 Recall that the decoding time of a variable length block code is finite with probability one. Thus P (κ) T (κ) < ∞ = 1 for all κ for a reliable sequence. 12 Evidently it is possible to come up with a probability space that includes all of the codes in a reliable sequence and invoke independence between random quantities associated with different codes. We choose the current convention to emphasize independence explicitly in the notation we use.
• If all entries of W are positive then 13 where D is maximum Kullback Leibler divergence between the output distributions of any two input letters: • If there are one or more zero entries 14 in W , i.e., if there are two input letters x,x and an output letter y such that, W x (y) = 0 and Wx(y) > 0, then for all R < C , for large enough E[T] there are rate R variable length block codes which are error free, i.e., P e = 0. When P e = 0 all error events can have zero probability at the same time. Consequently all the UEP problems are answered trivially when there is a zero probability transition. This is why we have assumed that W x (y) > 0 for all x ∈ X and y ∈ Y.
We denote the input letters that get this maximum value of Kullback Leibler divergence by 15 a and r:

A. Problem Statement
For each m ∈ M, the conditional error probability is defined as, 16 In the conventional setting we are interested in either the average or the maximum of the conditional error probability of the messages. The behavior of the minimum conditional error probability is scarcely investigated. Single message message-wise UEP problem attempts to answer that question by determining the trade-off between exponential decay rates of P e and min m∈M P e|m . The operational definition of the problem in terms of reliable sequences is as follows.
Definition 10 (Single Message Message-wise UEP Problem): For any reliable sequence Q the missed detection exponent of the reliable sequence Q is defined as where P (κ) e|m is the conditional error probability of the message m for the κ th code of the reliable sequence Q. For any rate R ∈ [0, C ] and error exponent 17 13 Problem is formulated somewhat differently in [3], as a result [3] did not deal with the case E[T] = ∞. The bounds in [3] does not guarantee that the error probability of a variable length code with infinite expected decoding time is greater than zero, however this is the case if all the transition probabilities are positive. To see that consider a channel with positive minimum transition probability λ, i.e., λ = minx,y Wx(y) > 0. In such a channel any variable length code satisfies Pe ≥ |M|−1 |M| E λ 1−λ T , then Pe > 0 as λ > 0 and P[T < ∞] = 1. Consequently both the rate and the error exponent are zero for variable length block codes with infinite expected decoding time. A more detailed discussion of this fact can be found in Appendix H1.
14 Note that in this situation D = ∞. 15 This particular naming of letters is reminiscent of the use of these letters in Yamamoto Itoh scheme [12]. Although they are named differently in [12], a is used for accepting and r is used for rejecting the tentative decision in Yamamoto Itoh scheme. 16 Later in the paper we consider block codes with erasures. The conditional error probabilities, P e|m for m ∈ M, are defined slightly differently for them, see equation (24). 17 Burnashev's expression for error exponent of variable length block codes is used explicitly in the definition because we know, as a result of [3], that the error exponents of all reliable sequences are upper bounded by Burnashev's exponent. An alternative definition oblivious to Burnashev's result can simply define Emd(R, E) for all rates-exponents vectors that are achievable. That definition is equivalent to Definition 10, because of [3].
In variable length block codes with feedback, the single message message wise UEP problem not only answers a curious question about the decay rate of the minimum conditional error probability of a code, but also plays a key role in the bit-wise UEP problem, which is our main focus in this manuscript.
Though they are central in the message-wise UEP problems, the conditional error probabilities of the messages are not relevant in the bit-wise UEP problems. In the bit-wise UEP problems we analyze the error probabilities of groups of sub-messages. In order to do that, consider a code with a message set M of the form where M j , M j ∈ M j for all j = 1, 2, . . . , ℓ. Furthermore M j and M j are called j th transmitted sub-message and j th decoded sub-message, respectively. The error probabilities we are interested in correspond to erroneous transmission of certain parts of the message. In order to define them succinctly let us define M j , M j and M j for all j between one and ℓ as follows: Then P e (j) is defined 18 as the probability of the event that M j = M j P e (j) P M j = M j for j = 1, 2, . . . , ℓ.
Note that if M j = M j then M i = M i for all i greater than j. Thus A rates-exponents vector ( R, E) is achievable if and only if there exists a reliable sequence Q such that ( R, E) = ( R Q , E Q ). This definition of the bit-wise UEP problem is slightly different than the one described in the introduction, because P e (j) is defined as consequently P M j = M j ≥ P M j = M j for all j's. In addition, if we assume without loss of generality that Thus for the case when ℓ is fixed, both formulations of the problem result in exactly the same achievable region of rates-exponents vectors.
The achievable region of rates-exponents vectors could have been defined as the closure of the points of the form ( R Q , E Q ) for some reliable sequence Q. Using the definition of ( R Q , E Q )'s one can easily show that, in this case too both definitions result in exactly the same achievable region of rates-exponents vectors.

B. Main Results
For variable length block codes with feedback, the results of both the single message message-wise UEP problem and the bit-wise UEP problem are given in terms of the J (R) function defined below. The J (R) function is first introduced by 19 Kudryashov [7, equation (2.6)] while describing the performance of non-block variable length codes with feedback and delay constraints. Later the J (R) function is used in [2] for describing the performance of block codes in single message message-wise UEP problem. It is shown in [2, Appendix D] that for both fixed length block codes without feedback and variable length block codes with feedback on DMCs satisfy, Recently Nazer, Shkel and Draper obtained the closed form expression for E md (R, 0) for fixed length block codes on the Additive White Gaussian Noise channel, under certain average and peak power constraints [9, Theorem 1]. Curiously equality given in (16) holds in that case too. 20 Definition 12: We have plotted the J (R) function for Binary Symmetric Channels 21 (BSCs) with various cross over probabilities in Figure 1. Note that as the channel becomes noisier, i.e., as the crossover probability becomes closer to 1/2, the value of J (R) function decreases at all values of rate where it is positive. Furthermore the highest value of rate where it is positive, i.e., the channel capacity, decreases. 19 In [7, equation (2.6)] there is no optimization over the parameter α. Thus strictly speaking, what is introduced in [7, equation (2.6)] is j (R) given in equation (64) rather than J (R) given in (17). 20 Unlike DMC for these channels it is possible to obtain a closed form expression in terms of the rate and the power constraints. 21 Recall that in a binary symmetric channel with crossover probability probability p, where C , D and J (·) are given in equations (8), (9) and (17), respectively. Furthermore E md (R, E) is jointly concave in (R, E) pairs. We have plotted E md (R, E) as a function of rate, for various values of E in Figure 2. When rate is zero, the exponent of the average error probability can be made as high as D. Thus all the curves meet at (0, D ) point. But for all positive rates the exponent of the average error probability makes a difference; as E increases E md (R, E) decreases. Furthermore for any given rate R the exponent of the average error probability can only be as high as This is why the curves corresponding to higher values of E have smaller support on rate axis. Proof of Theorem 1 is presented in Appendix I. Similar to the single message message-wise UEP problem, the solution of the bit-wise UEP problem is given in terms of the J (R) function. 22 For the case when R = 0 and where C , D and J (·) are given in equations (8), (9) and (17), respectively. Furthermore the set of all achievable rates-exponents vectors is convex. Proof of Theorem 2 is presented in Appendix J. For the special case when there are only two sub-messages the condition given in Theorem 2 for the achievablity of a rate vector error exponent vector pair can be turned into an analytical expression for the optimal E 1 in terms of R 1 , R 2 and E 2 . In order to see why, note that revealing the region of achievable (R 1 , R 2 , E 1 , E 2 ) vectors is equivalent to revealing the region of achievable (R 1 , R 2 , E 2 )'s and the value of the maximum achievable E 1 for all the (R 1 , R 2 , E 2 )'s in the achievable region.
Corollary 1: For any rate pair )D , the optimal value of E 1 is given by 24 where C , D and J (·) are given in equations (8), (9) and (17), respectively. Furthermore 23 For the case when Rj = 0 and ηj = 0 the ηjJ 24 For the case when R2 = 0 and E2 = (1 − R 1 C )D, the second term on the right hand side of equation (20) should be interpreted as zero, i.e., Note that for the E 1 (R 1 , R 2 , E 2 ) given in equation (20), Furthermore inequality is strict as long as R 2 > 0. We have drawn Figure 3.

IV. ACHIEVABLITY
In both the single message message-wise UEP problem and the bit-wise UEP problem, the codes that achieve the optimal performance employ a number of different ideas at the same time. In order to avoid introducing all of those ideas at once, we first describe two families of codes and analyze the probabilities of various error events in those two families of codes. Later we use those two families of codes as the building blocks for the codes that achieve the optimal performance in the UEP problems we are interested in. Before going into a more detailed description and analysis of those codes let us first give a birds eye plan for this section. (a) A Single Message Message-wise UEP Scheme without Feedback: First in Section IV-A, we consider a family of fixed length codes without feedback. We prove that these codes can achieve any rate R less than channel capacity, with vanishing 25 error probability P e while having a minimum conditional error probability, min m P e|m , as low as e −nJ(R) . The main drawback of this family of codes is that the decay rate of the average error probability P e has to be subexponential in this family of codes. (b) Control Phase and Error-Erasure Decoding: In Section IV-B in order to obtain non-zero exponential decay for the average error probability, we use a method introduced by Yamamoto and Itoh in [12]. We append the fixed length codes described in Section IV-A with a control phase and use an error-erasure decoder. This new family of codes with control phase and error-erasure decoding are shown, in Section IV-B, to achieve any rate R less than the channel capacity C with exponentially decaying average error probability P e , exponentially decaying minimum conditional error probability min m P e|m and vanishing erasure probability, P x . (c) Single Message Message-wise UEP for Variable Length Codes: In Section IV-C we obtain variable length codes for single message message-wise UEP problem using the codes described in Section IV-B. In order to do that we use the fixed length codes with feedback and erasures described in Section IV-B, repetitively until a non-erasure decoding happens. This idea too, was employed by Yamamoto and Itoh in [12]. (d) Bit-wise UEP for Variable Length Codes: In Section IV-D we first use the codes described in Section IV-A and the control phase discussed in Section IV-B to obtain a family of fixed length codes with feedback and erasures which has bit-wise UEP, i.e., which has different bounds on error probabilities for different sub-messages. While using the codes described in Section IV-A we employ an implicit acceptance explicit rejection scheme first introduced in [7] by Kudrayshov. Once we obtain a fixed length code with erasures and bit-wise UEP, we use a repeat at erasures scheme like the one described in Section IV-C to obtain a variable length code with bit-wise UEP. The achievablity results we derive in this section are revealed to be the optimal ones, in terms of the decay rates of error probabilities with expected decoding time E[T], as a result of the outer bounds we derive in Section V.

A. A Single Message Message-wise UEP Scheme without Feedback
In this subsection we describe a family of fixed length block codes without feedback that achieves any rate R less then capacity with small error probability while having an exponentially small min m P e|m , for sufficiently large block length n. We describe these codes in terms of a time sharing constant α ∈ [0, 1], two input letters x 1 , x 2 ∈ X and two probability distributions on the input alphabet, µ 1 , µ 2 ∈ P(X ).
In order to point out that certain sequence of input letters is a codeword or part of a codeword for message m, we put (m) after it. Hence we denote the codeword for m by x n (m) in a given code and by X n (m) in a code ensemble, as a random quantity.
Let us begin the description of the decoding scheme, by specifying the decoding region of the first message G [1]: it is the set of all output sequences y n whose the empirical distribution is not typical with (α,μ 1 ,μ 2 ). More precisely, the decoding region of the first message, G [1], is given by, where ∆ is the total variation distance defined in equation (1), Q {y nα 1 } and Q {y n nα+1 } are the empirical distributions of y nα 1 and y n nα+1 defined in equation (4) andμ 1 andμ 2 are probability distributions on Y, i.e.,μ 1 , For other messages, m = 1, decoding regions G[m] are the set of all output sequences for which Q {x n (m),y n } is typical with (α, µ 1 W , µ 2 W ) and Q {x n ( m),y n } is not typical with (α, µ 1 W , µ 2 W ) for any m = m. To be precise the decoding region of the messages other than the first message are where for all x n ∈ X n , B[x n ] is the set of all y n 's for which (x n , y n ) is typical with (α, µ 1 W , µ 2 W ): where ∆ is the total variation distance defined in equation (1), Q {x nα 1 ,y nα 1 } and Q {x n nα+1 ,y n nα+1 } are the empirical distributions of (x nα 1 , y nα 1 ) and (x n nα+1 , y n nα+1 ) defined in equation (4) and µ 1 W and µ 2 W are probability distributions on X × Y, i.e., µ 1 W ∈ P(X × Y) and µ 2 W ∈ P(X × Y).
In Appendix B we have analyzed the conditional error probabilities, P e|m for the above described code and proved Lemma 2 given below.
Lemma 2: For any block length n, time sharing constant α ∈ [0, 1], input letters x 1 , x 2 ∈ X and input distributions µ 1 , µ 2 ∈ P(X ) there exists a length n block code such that Given the channel W , if we discard the error terms ε n , for a given value of rate, 0 ≤ R ≤ C , we can can optimize exponent of P e|1 over the time sharing constant α, the input letters x 1 , x 2 and input distributions µ 1 , µ 2 . Evidently the optimization problem we get is the one given for the definition of J (R), in equation (17). Thus Lemma 2 implies that for any R ∈ [0, C ] and block length n there exists a length n code such that |M| ≥ e n(R−εn) , P e|m ≤ ε n for m = 2, 3, . . . , |M| and P e|1 ≤ e −n(J(R)−εn) .
One curious question is whether or not the exponent of P e|1 can be increased by including more than two phases. Carathéodory's Theorem answers that question negatively, i.e., to obtain the largest value of J (R) one doesn't need to do time sharing between more than two input-letter-input-distribution pairs.

B. Control Phase and Error-Erasure Decoding:
The family of codes described in Lemma 2 has a large exponent for the conditional error probability of the first message, i.e., P e|1 . But the conditional error probabilities of other messages, P e|m for m = 1, decay subexponentially. In order to facilitate an exponential decay of P e|m for m = 1 with block length, we append the codes described in Lemma 2 with a control phase and allow erasures. The idea of using a control phase and an error-erasure decoding, in establishing achievablity results for variable length code, was first employed by Yamamoto and Itoh in [12].
In order explain what we mean by the control phase, let us describe our encoding scheme and decoding rule briefly. First a code from the family of codes described in Section IV-A is used to transmit M and the receiver makes a tentative decision t M using the decoder of the very same code. The transmitter knows t M because of the feedback link. In the remaining time instances, i.e., in the control phase, the transmitter sends the input letter a if t M = M, the input letter r if t M = M. The input letters a and r are described in equation (10). At the end of the control phase, the receiver checks whether or not the output sequence in the control phase is typical with W a , if it is then M = t M otherwise an erasure is declared. Lemma 3 given below states the results of the performance analysis of the above described code. In order to understand what is stated in Lemma 3 accurately, let us make a brief digression and elaborate on the codes with erasure. We have assumed in our models until now that M ∈ M. However, there are many interesting problems in which this might not hold. In codes with erasures for example, we replace M ∈ M with M ∈ M where M = M ∪ {x} and x is the erasure symbol. Furthermore in codes with erasures for each m ∈ M the conditional error probability P e|m and conditional erasure probability, P x|m are defined as follows.
Note that definitions of P e|m and P x|m given above can be seen as the generalizations of the corresponding definitions in block codes without erasures. In erasure free codes above definitions are equivalent to corresponding definitions there. Lemma 3: For any block length n, rate 0 ≤ R ≤ C and error exponent 0 there exists a length n block code with erasures such that, Proof of Lemma 3 is given in Appendix C.
Note that in Lemma 3, unlike P e|m 's which decrease exponentially with n, P x|m 's decays as ln n √ n . It is possible to tweak the proof so as to have a non-zero exponent for P x|m 's, see [8]. But this can only be done at the expanse of P e|m 's. Our aim, however, is achieving the optimal performance in variable length block codes. As we will see in the following subsection, for that what matters is exponents of error probabilities and having vanishing erasure probabilities. The rate at which erasure probability decays does not effect the performance of variable length block codes in terms of error exponents.

C. Single Message Message-Wise UEP Achievablity:
In this section we construct variable length block codes for the single message message-wise UEP problem using Lemma 3. In first n time units the variable length encoding scheme uses a fixed length block code with erasures which has the performance described in Lemma 3. If the decoded message of the fixed length code is in the message set, i.e., if M ∈ M then decoded message of the fixed length code becomes the decoded message of the variable length code. If the decoded message of the fixed length code is the erasure symbol, i.e., if M = x, then the encoder uses the fixed length code again in the second n time units. By repeating this scheme until the decoded message of the fixed length code is in M, i.e., M ∈ M, we obtain a variable length code.
Let L be the number of times the fixed length code is used until a M ∈ M is observed. Then given the message M, L is a geometrically distributed random variable with success probability (1 − P x|M ) where P x|M is the conditional erasure probability of the fixed length code given the message M. Then the conditional probability distribution and the conditional expected value of L given M are Furthermore the conditional expected value of decoding time and the conditional error probability given the message M are where n is the block length of the fixed length code and P e|M is the conditional error probability given the message M for the fixed length code. Thus as result of equations (25b), (26) and Lemma 3 we know that for any rate We show in Section (V-C) that for any reliable sequence Q with rate R Q = R and error exponent E Q = E, E md,Q is upper bounded by the expression on the right hand side of equation (27).

D. Bit-Wise UEP Achievablity:
In this section we first use the family of codes described in Section IV-A and the control phase idea described in Section IV-B to construct fixed length block codes with erasures which have bit-wise UEP. Then we use them with a repeat until non-erasure decoding scheme, similar to the one described in Section IV-C, to obtain variable length block codes with bit-wise UEP.
Let us start with describing the encoding scheme for the fixed length block code with bit-wise UEP. If there are ℓ sub-messages, i.e., if M = (M 1 × M 2 × · · · × M ℓ ), then the encoding scheme has ℓ + 1 phases with lengths n 1 , n 2 , . . ., n ℓ+1 such that n 1 + n 2 + . . . + n ℓ+1 = n • In the first phase a length n 1 code from the family of codes described in Section IV-A is used. The message set of the code t M 1 is M 1 ∪ {|M 1 | + 1} and the message t M 1 of the code is determined by the first sub-message: At the end of first phase receiver uses the decoder of the length n 1 code to get a tentative decision t M 1 which is known by the transmitter at the beginning of the second phase because of the feedback link. • In the second phase a length n 2 code from the family of codes described in Section IV-A, with the message set t M 2 = M 2 ∪ {|M 2 | + 1}, is used. If t M is decoded correctly at the end of the first phase then the message t M 2 of the code used in the second phase is determined by the second sub-message as t M 2 = M 2 + 1, else t M 2 = 1. At the end of the second phase the receiver uses the decoder of the second phase code to get the tentative decision t M 2 which is known by the transmitter at the beginning of the third phase because of the feedback link.. • In phases 3 to ℓ above described scheme is used. In phase i, a length n i code, with the message set • The last phase is a n ℓ+1 long control phase, i.e., a n ℓ+1 long code with the message set t M ℓ+1 = {1, 2} is used in the last phase. The codewords for the first and second messages are n ℓ+1 long sequences of input letters r and a respectively, where r and a are described in equation (10). The tentative decision in the last phase t M ℓ+1 is equal to the first message if the output sequence in the last phase is not typical with W a , the second message otherwise. The message of the n ℓ+1 long code t M ℓ+1 is equal to 2 if t M ℓ = t M ℓ , 1 otherwise. Note that if we define t M 0 , t M 0 and M ℓ+1 all to be 1, i.e., t M 0 = t M 0 = M ℓ+1 = 1 we can write the following rule for determining the t M i 's for i = 1 to ℓ + 1.
It is important however to keep in mind that the last phase is a control phase and the codes in the first ℓ phases are from the family of codes described in Section IV-A. Note that during the phases i = 2 to ℓ erroneous transmission of t M i−1 is conveyed using t M i = 1, hence the transmission of M i through t M i , i.e., t M i = 1 + M i , is a tacit approval of the tentative decision t M i−1 . Because of this, the above encoding scheme is said to have an implicit acceptance explicit rejection property. The idea of implicit acceptance explicit rejection was first introduced by Kudryashov in [7] in the context of non-block variable length codes with feedback and delay constraints.
After finishing the description of the encoding scheme, we are ready to describe the decoding scheme. The receiver determines the decoded message using the tentative decisions, t M i for i = 1 to ℓ + 1. If one or more of the tentative decisions are equal to 1, then an erasure is declared. If all ℓ + 1 tentative decision are different from 1 then M i = t M i − 1 for all i = 1, 2, . . . , ℓ. Hence the decoding rule is For bit-wise UEP codes with erasure, the definition of P e (i) is slightly different from the original one given in equation (14) P With this alternative definition in mind let us define P e|m (i) as the conditional probability of the erroneous transmission any one of the first i sub-message when M = m: The error analysis of the above described fixed length codes, presented in Appendix D, leads to Lemma 4 given below.
Lemma 4: For block length n, any integer ℓ ≤ n ln(1+n) , rate vector R, and time sharing vector η such that there exists a length n block code such that: Recall the repeat at erasures scheme described in Section IV-C. If we use that scheme to obtain a variable length code from the fixed length bit-wise UEP code described in Lemma 4, we obtain a variable length code with UEP such that As result of equation (33) and Lemma 4 we know that for any rate vector R, error exponent vector E and time sharing vector η such that there exists a reliable sequence Q such that ( R Q , E Q ) = ( R, E). Thus the existence of the time sharing vector η satisfying the constraints given in (34) is a sufficient condition for the achievablity of a rates-exponents vector ( R, E). We show in Section (V-D) that the existence of a time sharing vector η satisfying the constraints given in (34) is also a necessary condition for the achievablity of a rates-exponents vector ( R, E).

V. CONVERSE
Berlin et. al. [1] used the error probability of a random binary query posed at a stopping time for bounding the error probability of a variable length block code. Later similar techniques have been applied in [2] for establishing outer bounds in UEP problems. Our approach is similar to that of [1] and [2]; we, too, use error probabilities of random queries posed at stopping times for establishing outer bounds. Our approach, nevertheless, is novel because of the error events we choose to analyze and the bounding techniques we use. Furthermore, the relation we establish in Lemma 5 between the error probabilities and the decay rate of the conditional entropy of the messages with time is a brand new tool for UEP problems.
For rigorously and unambiguously generalizing the technique used in [1] and [2] we introduce the concept of anticipative list decoders in Section V-A. Then in Section V-B we bound the probabilities of certain error events associated with anticipative list decoders from below. This bound, i.e., Lemma 5, is used in Sections V-C and V-D to derive tight outer bounds for the performance of variable length block codes in the single message message-wise UEP problem and in the bit-wise UEP problem, respectively.

A. Anticipative List Decoders
In this section we first introduce the concepts of anticipative list decoders and non-trivial anticipative list decoders. After that we show that for a given variable length code, any non-trivial anticipative list decoder ( T, A) can be used to define a probability distribution, P • or T is a stopping time, which is smaller than T with probability one, and A is a ℘(M) valued function defined on Y T , i.e., Definition of ALD does not require A to be of some fixed size, nor it requires A to include more likely or less likely messages. Thus for certain values of Y T , A might not include any m ∈ M with positive posterior probability. In other words for some values of Y T we might have The ALD's in which such yt's have zero probability are called nontrivial ALD's.
Definition 14 (Nontrivial ALD): An anticipative list decoder ( T, A) is called a nontrivial anticipative list decoder (NALD) if P M ∈ A(Y T ) Y T > 0 with probability one, i.e., Below, for any variable length code and an associated nontrivial anticipative list decoder ( T, A) we define a probability distribution P {A} on M × Y T * and a probability measure P {A} [·] for the events in ℘(M × Y T ). For doing that first note that the probability measure generated by the code, i.e., P[·], can be used to define a probability distribution P on M × Y T * as follows: where Y T * is a countable set for any stopping time, given in equation (6b). As T is a stopping time, the probability of any event Γ in ℘(M × Y T ) under P[·], i.e., P[Γ], is equal to Evidently we can extend the definition of P and assume that P is zero whenever y t is in Y ∞ {T=∞} , i.e.,  26 There is a slight abuse of notation in equation (39); if T is not a stopping time but rather a constant random variable T = 0, P {A} (m, y t ) should be interpreted as Using the parametric definition of probability distribution P {A} on M × Y T * we define a probability measure P {A} [·] for the events in ℘(M × Y T ) as follows: Evidently we can extend the definition of P {A} to M × Y T by defining it to be zero on M × Y ∞ {T=∞} , i.e., As in the case of P, this extension is neither necessary nor relevant for calculating the probabilities P {A} [Γ] given in equation (41).

B. Error Probability and Decay Rate of Entropy:
In this section we lower bound the probability of the event that the decoded message M is in A under the probability measure P {A} [·], i.e., P {A} M / ∈ A(Y T ) . The bounds we derive depend on the decay rate of the conditional entropy of the messages in the interval between T and T. Before even stating our bound, we need to specify what we mean by the conditional entropy of the messages. While defining the conditional entropy, many authors do take an average over the sample values of the conditioned random variable and obtain a constant. We, however, do not take an average over the conditioned random variable and define conditional entropy as a random variable itself, which is a function of the random variable that is conditioned on: 27 Using the probability distribution P defined in equation (36) we see that the conditional entropy defined in (43) is equal to, Lemma 5: For any variable length block code with finite expected decoding time, Then for all i in {1, 2, . . . , k} such that P M ∈ A i (Y Ti ) + P e ≤ 1/2 we have where T 0 = 0, T k+1 = T and for all j in {1, 2, . . . , (k + 1)}, r j 's are given by Proof of Lemma 5 is presented in Appendix E. Before presenting the application of Lemma 5 in UEP problems, let us elaborate on its hypothesis and ramifications. We assumed that (T i , A i ) are all NALD. Thus for each (T i , A i ) the set of all y ti ∈ Y Ti such that the 27 Recall the standard notation in probability theory about the conditional expectations and conditional probabilities: Let H be a real valued random variable and G be a random quantity that takes values from a finite set G, such that P[G and P e . But the particular choice of A j 's for j = i has no effect on the bound. This feature of the bound is its main merit over bounds resulting from the previously suggested techniques.

C. Single Message Message-Wise UEP Converse:
In this section we bound the conditional error probabilities of the messages, i.e., P e|m 's, from below uniformly over the message set M in a variable length block code with average error probability P e , using Lemma 5. Resulting outer bound reveals that the inner bound we obtained in Section IV-C for the single message messagewise UEP problem is tight.
Consider a variable length block code with finite expected decoding time, i.e., E[T] < ∞. In order to bound P e|m , defined in equation (11), from below we apply Lemma 5 for k = 2 with (T 1 , A 1 ), (T 2 , A 2 ) given below.
• Let T 1 be zero and A 1 be {m}, i.e., • Let T 2 be the first time instance before T such that one message, not necessarily the one chosen for A 1 , i.e., m, has a posteriori probability 1 − δ or higher, Let A 2 be the set of all messages whose posterior probability at time T 2 is less then (1 − δ), We apply Lemma 5 for (T 1 , A 1 ) and (T 2 , A 2 ) given in equations (48), (49), (50) and (51). Then using the fact that J (·) ≤ D we get, is roughly equal to P e /δ. Thus inequality in (52b) becomes a lower bound on E[T − T 2 ] in terms of P e . It can be shown that the lower bound (52a) takes its smallest value for the smallest value of E[T − T 2 ]. Then using Fano's inequality for E H(M|Y T2 ) we obtain Lemma 6 given below.
A complete proof of Lemma 6 for variable length block codes with finite expected decoding time is presented in Appendix F. For variable length block codes with infinite expected decoding time, Lemma 6 follows from the lower bounds on P e and P e|m derived in Appendix H1 and Appendix H2.
Lemma 6: For any variable length block code and positive δ such that P e + δ + Pe .  Lemma 1] are tight only when the error exponent is very close to zero. While deriving the bound given in Lemma 6, on the other hand, the variation in the rate the conditional entropy decreases in different intervals is taken into account. Hence the outer bound given in Lemma 6 matches the inner bound given in Section IV-C for all achievable values of error exponent, 0 ≤ E ≤ (1 − R C )D . Consider a reliable sequence of codes Q with rate R Q and error exponent E Q . Then if we apply Lemma 6 with δ = 1 ln(1/Pe) we get Note that the upper bound on E md,Q 's given in equation (54) is achievable by at least one Q described in Section IV-C.

D. Bit-Wise UEP Converse:
In this section we apply If we apply Lemma 5 for (T 1 , A 1 ),. . .,(T ℓ , A ℓ ) defined in equations (55) and (56), we obtain lower bounds on P {Ai} M / ∈ A i (Y Ti ) 's in terms of P M ∈ A i (Y Ti ) 's and r j 's and E[T j − T j+1 ]'s for j > i. In order to turn these bounds into bounds on P e (i)'s we bound P {Ai} M / ∈ A i (Y Ti ) 's and P M ∈ A i (Y Ti ) 's from above.
• The posterior probability of a message at time τ + 1 can not be smaller than λ times its value at time τ because min x∈X ,y∈Y W x (y) = λ. Thus if δ < 1/2 one can bound P {Ai} M / ∈ A i (Y Ti ) 's from above: Using these facts one can bound P M ∈ A i (Y Ti ) from above: More detailed derivations of the inequalities given in (57) and (58) can be found in Appendix G.
Using equations (57) and (58) together with Lemma 5 we can conclude that, provided that P e + δ + P e /δ ≤ 1/2, where r j 's are defined in (47). Note that the lower bound on P e (i)'s given in equation (59) takes different values depending on the rate of decrease of the conditional entropy of the messages in different intervals, i.e., r j 's, and the expected duration of different intervals, i.e., E[T j − T j−1 ]'s. Making a worst case assumption on the rate of decrease of entropy and the durations of the intervals one can obtain Lemma 7 given below.
A complete proof of Lemma 7 for variable length block codes with finite expected decoding time is presented in Appendix G. For variable length block codes with infinite expected decoding time, Lemma 7 follows from the lower bounds on P e and P e (i)'s derived in Appendix H1 and Appendix H3.
Lemma 7: For any variable length block code with feedback with a message set M of the form 29 M = M 1 × M 2 × . . . , M ℓ and for any positive δ such that P e + δ + Pe δ ≤ 1 5 , we have for some time sharing vector η such that .
For any reliable sequence Q whose message sets M (κ) are of the form − ln Pe Lemma 7 implies that there exists a η such that 30 Recall that a rates-exponents vector ( R, E) is achievable only if there exists a reliable code sequence Q such that ( R Q , E Q ) = ( R, E). Thus a rates-exponents vector ( R, E) is achievable only if there exists a time sharing vector η satisfying equation (34). In other words the sufficient condition for the achievablity of ( R, E) we have derived in Section IV-D is also a necessary condition.

VI. CONCLUSIONS
We have considered the single message message-wise and the fixed ℓ bit-wise UEP problems and characterized the achievable rate error exponent regions completely for both of the problems.
In bit-wise UEP problem we have observed that encoding schemes decoupling the communication and bulk of the error correction both at the transmitter and at the receiver can achieve optimal performance. This result is extending the similar observations made for conventional variable length block coding schemes without UEP. However, for doing that one needs to go beyond the idea of communication phase and control phase introduced in [12], and harness the implicit confirmation explicit rejection schemes, introduced by Kudryashov in [7].
For the converses results, we have introduced a new technique for establishing outer bounds to the performance of the variable length block codes, that can be use in both message-wise and bit-wise UEP problems. 31 We were only interested in bit-wise UEP problem in this paper. We have analyzed single-message message-wise UEP problem, because it is closely related to bit-wise UEP problem and its analysis allowed us to introduce the ideas we use for bit-wise UEP, gradually. However it seems using the technique employed in [2, Theorem 9] on the achievablity side and Lemma 5 on the converse side, one might be able to determine the achievable region of rates-exponents vectors for variable length block codes in message-wise UEP problem. Such a work would allow us to determine the gains of feedback and variable length decoding, because Csiszár [5] had already solved the problem for fixed length block codes.
Arguably, the most important shortcoming of our bit-wise UEP result is that it only addresses the case when the number of groups of bits ℓ is a fixed integer. However this has more to do with the formal definition of the problem we have chosen in Section III than our analysis and non-asymptotic results given in Sections IV and V, i.e., Lemma 4 and Lemma 7.
Using the rates-exponents vectors for representing the performance of a reliable sequence with bit-wise UEP, is apt only when the number of groups of bits are fixed or bounded. When the number of groups of bits ℓ in a reliable sequence diverge with increasing κ, i.e., when lim κ→∞ ℓ κ = ∞, the rates-exponents vector formulation becomes fundamentally inapt. Consider, for example, a reliable sequence in which |M The rate of this reliable sequence is R, yet the rate of all of the sub-messages are zero. Thus when ℓ κ diverges the rate vector does not have the same operational relevance or meaning it has when ℓ κ is fixed or bounded. In order to characterize the change of error performance among sub-messages in the case when ℓ κ diverges, one needs to come up with an alternative formulation of the problem, in terms of cumulative rate of sub-messages.
Our non-asymptotic results are useful to some extend even when ℓ κ diverges. Although infinite dimensional ratesexponents vectors falls short of representing all achievable performances one can still use Lemma 4 of Section IV and Lemma 7 of Section V to characterize the set of achievable rate vector error exponent vector pairs.
• As a result of Lemma 7 the necessary condition given in equation (19) is still a necessary condition for the achievablity of rates-exponents vector. • Using Lemma 4 we see that the sufficient condition given in equation (19) is still a sufficient condition as long as the number of sub-messages in the reliable sequence satisfy lim sup n→∞  (19) is still a necessary and sufficient condition for the achievablity of a rates-exponents vector.

ACKNOWLEDGMENT
Authors would like to thank Gerhard Kramer and Reviewer II for pointing out the importance of the case of varying the number of groups of bits with expected block length. Reviewer II has also coined the term ratesexponents vector which replaced authors' previous attempt: rate vector error exponent vector pair. Authors would also like to thank all of the reviewers for their meticulous reviews and penetrating questions.

A. Proof of Lemma 1
Proof: Note that J (R) defined in equation (17) is also equal to where j (R) is given by j (R) max α,x,µ: Note that j (R) is a bounded real valued function of a real variable. Therefore, Carathéodory's Theorem implies that considering two point convex combinations suffices in order make j (R) a concave function. In other words for any k we have, max α,R1,R2: Then the concavity of J (R) follows from the equations (63), (64) and (65).
Evidently if the constraint set in a maximization is curtailed than resulting maximum value can not increase. Hence J (R) function defined in equation (17) is a decreasing function of R.
As a result of the definition of D given in equation (9) and the convexity of Kullback-Leibler divergence, we have D ≥ J (0). On the other hand D (μ W x ) = D and I (µ, W ) ≥ 0 for x = r and µ(·) = 1 {·=a} where a and r described in equation (10). Therefore we have j (0) ≥ D. Using the fact that J (R) ≥ j (R) we conclude that J (0) = j (0) = D.

B. Proof of Lemma 2
Proof: We prove the lemma for a slightly more general setting and establish a result that will be easier to make use of in the proofs of other achievablity results.
Inequality (a) follows from the non-negativity of the Kullback Leibler divergence. In order to see why (b) holds, first recall that min x,y W x (y) = λ. Hence |lnμ 1 (y) Wx 1 (y) | ≤ ln 1 λ and |lnμ 2 (y) Wx 2 (y) | ≤ ln 1 λ . Then the inequality (b) follows from the definitions of total variation ∆ and G γ [1], given in equations (1) and (66a) and the fact that y n / ∈ G γ [1]. Note that the conditional error probability of the first message is given by Recall that, the codeword of the message M = 1 is the concatenation of n α x 1 's and (n − n α ) x 2 's where n α = ⌊nα⌋. Hence the probability of all y n 's whose empirical distribution in first n α times instances is Q {y nα 1 } and whose empirical distribution in Furthermore, there are less than (n α + 1) |Y| distinct empirical distributions in the first phase and there are less than (n − n α + 1) |Y| distinct empirical distributions in the second phase. Thus where ε 2 (γ,n) = −2γ ln λ+D+2|Y| ln(n+1) n . The codewords and the decoding regions of the remaining messages are specified using a random coding argument together with an empirical typicality decoder. Consider an ensemble of codes in which first n α entries of all the codewords are independent and identically distributed (i.i.d.) with input distribution µ 1 and the rest of the entries are i.i.d. with the input distribution µ 2 .
For any message m other than the first one, i.e., m = 1, the decoding region is G γ [m] given in (66b). In other words for any message m, other than the first one, the decoding region is the set of output sequences for which (x n (m), y n ) is typical with (α, µ 1 W , µ 2 W ), i.e., y n ∈ B γ [x n (m)], and (x n ( m), y n ) is not typical with (α, µ 1 W , µ 2 W ), i.e., y n ∈ B γ [x n ( m)], for any m = m.
Since the decoding regions of different messages are disjoint, above described code does not decode to more than one message. Disjointness of decoding regions of messages 2,3,. . .,|M| follows from the definitions of G γ [2],G γ [3],. . .,G γ [|M|], given in equation (66b). In order to see why G γ [1] ∩ (∪ m =1 G γ [m]) = ∅ holds, note that for any pair probability of distributions, the total variation between them is lower bounded by the total variation between their marginals. In particular, Then for m ∈ {2, 3, . . . , |M|} the average of the conditional error probability of m th message over the ensemble is upper bounded as Let us start with bounding P[Y n / ∈ B γ [X n (m)]| M = m]. Let S 1 (x, y) and S 2 (x, y) be As a result of the definition of total variation distance given in equation (1) and above definitions we have Thus the definition of B γ [x n (m)] given in equation (66c) implies that If for all x ∈ X , y ∈ Y and j ∈ {1, 2}, S j (x, y) ≤ γ|X | −1 |Y| −1 then x,y [S 1 (x, y) + S 2 (x, y)] ≤ 2γ. Thus if Y / ∈ B γ [X n (m)] then for at least one (x, y, j) triple S j (x, y) ≥ γ|X | −1 |Y| −1 . Using the union bound we get For bounding P S j (x, y) ≥ γ |X ||Y| M = m , we can simply use Chebyshev's inequality, however in order to get better error terms we use a standard concentration result about the sums of bounded random variables, [4, Theorem 5.3].

C. Proof of Lemma 3
Proof: Let n 1 be On the other hand as a result of equation (78) and the definition of J (·) given in equation (17), for any positive integer n 1 , positive real number γ 1 , rate R ≤ C there exists a length n 1 code such that, where ε 1 (γ1,n1), ε 2 (γ1,n1), ε 3 (γ1,n1) are given in equation (79). We use such a code in the first phase with R = n n1 R and call its decoded message t M, the tentative decision. Then as a result of equation (81) and the fact that 32 The transmitter knows what the tentative decision is and determines the channel inputs in the last (n − n 1 ) time instances depending on its correctness. If t M = M the channel inputs in the last (n − n 1 ) time instances are all a, if t M = M the channel inputs in the last (n − n 1 ) time instances are all r.

D. Proof of Lemma 4
Proof: Note that given the encoding scheme summarized in equation (28) and the decoding rule given in equation (29), if M = x then there is a i ≤ ℓ + 1 such that t M j = t M j for all j < i and t M i = t M i . Thus the conditional erasure probability P x|m is upper bounded as Similarly if M = x and M i = M i then for all j > i, t M j = 1 and t M j = 1; furthermore there is a k ≤ i such that t M j = t M j for all j < k and t M k = t M k . Hence one can bound P e|m (i) as In the first ℓ phases, we use n i = ⌊η i n⌋ long codes with rate Ri ηi with the performance given in equation (81). Thus for 1 ≤ i ≤ ℓ we have, where ε 1 (γi,ni), ε 2 (γi,ni), ε 3 (γi,ni) are given in equation (79).
In order derive bounds corresponding to the ones given in equation (90) for the last phase let us give the decoding regions for 1 and 2 for the length n ℓ+1 code employed between (n + 1 − n ℓ+1 ) and n.
Following an analysis similar to the one leading to equations (83) and (84) we get Using equations (88), (89), (90) and (91) we get, If we set γ i = |X ||Y| 4n i ln(1 + n) for i = 1, 2, . . . , (ℓ + 1) for ε 1 (γi,ni), ε 2 (γi,ni) and ε 3 (γi,ni) given in equation (79) we have n i ε 1 (γi,ni) + C ≤ 2|X ||Y|(ln(n i + 1) − 4n i ln(1 + n) ln λ) + 2 ln(1 + n) + C n i ε 2 (γi,ni) + D ≤ 2|X ||Y|(ln(n i + 1) − 4n i ln(1 + n) ln λ) + 2D Using the concavity of √ z function we can conclude that, For P {A} defined in equation (39) as a result of equation (41) we have Using equations (94) and (95) together with the data processing inequality for Kullback-Leibler divergence, we get . . (96) Since the binary entropy function h(·) is increasing on the interval [0, 1/2] if P e +P M ∈ A i (Y Ti ) ≤ 1/2 equations (96) and (97) imply Let B, B * and B τ be where T ∧ τ is the minimum of T and τ . Note that as τ goes to infinity, B τ → B and B τ → B * with probability one. Since |B τ | ≤ T ln 1 λ and E[T] < ∞, we can apply the dominated convergence theorem [10, Theorem 3 p 187] to obtain Finally for B and B * defined in equation (99) we have Thus as a result of equations (100) and (101) we have Furthermore using the definition of P {Ai} given in equation (39) we get where for all i ≥ 1 and j > i Assume for the moment that, where T k+1 = T and r j is defined in equation (47). Then Lemma (5) (105) is equivalent to 0 ≤ 0J (0) which holds trivially. Thus we assume hence forth that Let us consider the stochastic sequence where I M; Y k Y k−1 is the conditional mutual information between M and Y k given Y k−1 , defined as Note that as it was the case for conditional entropy, while defining the conditional mutual information we do not take the average over the conditioned random variable. Thus I M; Y k Y k−1 is itself a random variable.
For U τ defined in equation (106) we have Conditioned on Y τ random variables M − X τ +1 − Y τ +1 form a Markov chain: thus as a result of the data processing inequality for the mutual information we have I (X τ +1 ; Y τ +1 |Y τ ) > I (M; Y τ +1 |Y τ ). Since J (·) is a decreasing function this implies that Furthermore, because of the definitions of J (·), P and P {A} given in equations (17), (36) and (39), the convexity of Kullback Leibler divergence and Jensen's inequality we have Using equations (107), (108) and (109) we get Recall that min x,y W x (y) = λ and |J (·) | ≤ D. Thus as a result of equation (107) we have As a result of (110), (111) and the fact that U 0 = 0, U τ is a submartingale. Recall that we have assumed that P[T j+1 ≤ T] = 1 and E[T] < ∞; consequently Because of (111) and (112) we can apply a version of Doob's optional stopping theorem [10,Theorem 2,p 487] to the submartingale U τ and the stopping time Note that as a result of the concavity of J (·) and Jensen's inequality we have In order to calculate the argument of J (·) in (114) consider the stochastic sequence Clearly Recall that we have assumed that P[T j ≤ T j+1 ≤ T] = 1 and E[T] < ∞; consequently As a result of equations (116) and (117) we can apply Doob's optimal stopping theorem, [10, Theorem 2, p 487] to V τ both at stopping time T j and at stopping time T j+1 , i.e., Using equations (113), (114) and (118) Hence inequality given in (105) not only when P[T j+1 = T j ] = 1 but also when P[T j+1 = T j ] < 1.
We start with bounding P {A2} M / ∈ A 2 (Y T2 ) from above and P M / ∈ A 2 (Y T2 ) from below.
• Since min x∈X ,y∈Y W x (y) = λ the posterior probability of a message at time τ + 1 can not be smaller than λ times the posterior probability of the same message at time τ . Hence for the stopping time T 2 defined in equation (50), random 33 set A 2 defined in equation (51) and δ < 1 2 we have 33 The set A2 is random in the sense that it depends on previous channel outputs.
As a result of the definition of P {A2} (m, y t ) given in equation (39) we have, If the decoded message M(y t ) is not in A 2 (y t2 ) and message m is in A 2 (y t2 ) then M(y t ) = m: Using equations (122) and (123) we get If we sum over all (m, y t )'s in M × Y T * and use equations (37) and (41) we get, • The probability of an event Γ 1 is lower bounded by the probability of its intersection with any event Γ 2 , i.e., : Note that if A 2 (y t2 ) = M then T is reached before any of the messages reach a posterior probability of 1 − δ.
Thus as a result of equations (126) and (127) we have On the other hand if A 2 (y t2 ) = M, then the most likely message with a probability at least (1 − δ) is excluded from A 2 (y t2 ). Thus Using equations (128) and (129) together with total probability formula we get We plug the bounds on P {A2} M / ∈ A 2 (Y T2 ) and P M / ∈ A 2 (Y T2 ) given in equations (125) and (130) in equation (120) to get provided thatǫ 1 ≤ 1/2 whereǫ 1 = P e + δ + Pe δ + |M| −1 . Now we bound E H(M|Y T2 ) from below. Note that 1 {M∈A2(Y T 2 )} is a discrete random variable that is either zero or one; its conditional entropy given Y T2 is given by Furthermore since 1 {M∈A2(Y T 2 )} is a function of Y T2 and M, chain rule entropy implies that Since A 2 (Y T2 ) has at most |M| elements and its complement, M \ A 2 (Y T2 ), has at most one element, we can bound the conditional entropy of the messages as follows Thus using equations (132), (133) and (134) we get Then using concavity of the binary entropy function h(·) together with equations (130) and (135) we get provided that δ + Pe δ ≤ 1/2. If we plug in equation (136) and the identity H(M) = ln |M| in equation (131) we get, . Note that the inequality given in equation (137b) bounds the value of η from above, . Furthermore for any η 1 ≤ η 2 ≤ R C as a result of concavity of J (·) we have Using equations (138), (139) we see that the bound in equation (137a) is lower bounded by its value at η = 1 − (1−ǫ1)E−ǫ2 D if E ≥ǫ 2 1−ǫ1 and by its value at η = 1 otherwise, i.e., ln Pe|m Then, for the case E ≥ǫ 2 1−ǫ1 Lemma 6 follows from the fact that J (·) is a non-negative decreasing function. For the case E <ǫ 2 1−ǫ1 in Lemma 6 follows from the fact that J (·) is a concave non-negative decreasing function.

G. Proof of Lemma 7 for The Case E[T] < ∞
Proof: We start with proving the bounds given in equations (57) and (58).
• Let us start with the bound on P {Ai} M / ∈ A i (Y Ti ) given in equation (57). Since min x∈X ,y∈Y W x (y) = λ, the posterior probability of a m i ∈ M i at time τ + 1 can not be smaller than λ times its value at time τ . Hence for δ < 1/2, as a result definitions of T i and A i (Y Ti ) given in equations (55) and (56), we have Then as a result of the definition of P {Ai} (m, y t ) given in equation (39) we have, For A i (y ti ) given in equation (56), if the decoded message M(y t ) is not in A i (y ti ) but m is in A i (y ti ) then M i (y t ) = m i : Using equations (140) and (141) we get If we sum over all (m, y t )'s in M × Y T * and use equations (37) and (41) we get, • Let us now prove the bound on P M ∈ A i (Y Ti ) given in equation (58).
As a result of total probability formula for P M = M we have If use the total probability formula for P M ∈ A i (Y Ti ) together with equations (143) and (145) we get We apply Lemma 5 for (T 1 , A 1 ),. . .,(T k , A k ) defined in equations (55) and (56); use the bounds on and P M ∈ A i (Y Ti ) given in (57) and (58). Then we can conclude that if P e + δ + P e /δ ≤ 1/2 then where R i , E i ,ǫ 3 andǫ 5 are defined in Lemma 7, r j 's are defined in equation (47) of Lemma 5 and ν j 's are defined as follows 34 Depending on the values of ν j and r j the bound in equation (146) takes different values. However ν j and r j are not changing freely. As a result of equation (118) and the fact that I M; Y t+1 Y t ≤ C we have In addition ν j 's and r j 's are constrained by the definitions of T j and A j (Y Tj ) given in equations (55) and (56). At T j with high probability one element of M j has a posterior probability (1 − δ). Below we use this fact to bound E H(M|Y Tj ) from above. Then we turn this bound into a constraint on the values of ν j 's and r j 's and use that constraint together with equations (146), (148) to bound E i 's from above. For all j in {1, 2, . . . , ℓ}, 1 {M∈Aj(Y T j )} is a discrete random variable that is either zero or one; its conditional entropy given by Furthermore since 1 {M∈Ai(Y T i )} is a function of Y Ti and M, the chain rule entropy implies that Note that A i (Y Ti ) has at most |M| elements and its complement, M \ A i (Y Ti ), has at most |M| |M i | elements. We can bound the conditional entropy of the messages H(M|Y Ti , 1 {M∈Ai(Y T i )} ) as follows Thus using equations (149), (150) and (151) we get If we take the expectation of both sides of the inequality (152) and use the concavity of the binary entropy function we get ln |M i | Using the inequality given (58) and the fact that binary entropy function is an increasing function on the interval [0, 1/2] we see that provided that P e + δ + Pe δ ≤ 1/2. Note that as a result of Fano's inequality for E H(M|Y T ) we have If we divide both sides of the inequalities (153) and (154) Note that Using equations (155) and (156) we get, where r j 's and ν j 's given in equation (47) and (147) respectively. Thus using equations (47), (146), (147), (148) and (157) we reach the following conclusion. For any variable length block code satisfying the hypothesis of the Lemma 7 and for any positive δ such that P e + δ + Pe for some (ν ℓ+1 1 ,r ℓ+1 1 ) such that r i ∈ [0, C ] i =1, 2, . . . , (ℓ + 1) (159a) ν i ≥ 0 i =1, 2, . . . , (ℓ + 1) We show below if the constraints given in equation (158) is satisfied for some (ν ℓ+1 1 ,r ℓ+1 1 ) satisfying (159), constraints given in (60) is satisfied for some (η ℓ 1 ) satisfying (61). One can confirm numerically that Recall that we have assumed that P e + δ + Pe δ ≤ 1 5 , i.e.,ǫ 3 ≤ 1 5 . Thus, Let η 1 , r 1 , ν 2 and r 2 be Note that (η 1 , ν 2 , ν ℓ+1 3 , r 1 , r 2 , r ℓ+1 3 ) satisfies (158b), (158c) and (159) by construction. Furthermore as a result of concavity of J (·) we have, ν 1 J (r 1 ) + ν 2 J (r 2 ) ≤ η 1 J ( r 1 ) + ν 2 J ( r 2 ) .

H. Codes with Infinite Decoding Time on Channels with Positive Transition Probabilities
In this section we consider variable length block codes on discrete memoryless channels with positive transition probabilities, i.e., min x∈X ,y∈Y W x (y) > 0, and derive lower bounds to the probabilities of various error events. These bounds, i.e., equations (166), (172) and (175), enable us to argue that Lemma 6 and Lemma 7 hold for variable length block codes with infinite expected decoding time, i.e., E[T] = ∞.
1) P e > 0: On discrete memoryless channel such that min x∈X ,y∈Y W x (y) = λ the posterior probability of any message m ∈ M at time τ is lower bounded as Then conditioned on the event {T = τ } the probability of erroneous decoding is lower bounded as (164) Note that since P[T < ∞] = 1, the error probability of any variable length code satisfies Using equation (164) and (165)  (166) Note that equation (166) implies that for a variable length code with infinite expected decoding time not only the rate R but also the error exponent E is zero.
2) If P e + 1 |M| < 1 then min m P e|m > 0 : Note that since P[T < ∞] = 1 and |M| < ∞, For any variable length block code such that P e + 1 |M| < 1, let τ * be τ * = min τ : max Since P[T < ∞| M = m] = 1 for all m in M and M is finite, τ * is finite. Note that for any τ , m and m we have, Then using equation (168) Note that as a result of equation (167) where τ * is a finite integer defined in equation (167). Then conditioned on the event {T = τ } the probability of decoding the i th sub-message erroneously is lower bounded as Since P[T < ∞] = 1, P e (i) satisfies Using equation (173) and (174) Equation (175) implies that for any variable length code with infinite expected decoding time on a DMC without any zero probability transition, not only the rates but also the error exponents of the sub-messages are zero.

I. Proof of Theorem 1
Proof: In Section IV-C it is shown that for any rate R ∈ [0, C ], error exponent E ∈ [0, (1 − R C )D ] there exists a reliable sequence Q such that R Q = R, E Q = E, E md,Q = E + (1 − E D )J R 1−E/D . Thus as a result of the definition of E md (R, E) given in equation (13) we have In Section V-C we have shown that any reliable sequence of codes Q with rate R Q and error exponent E Q satisfies Thus, using the fact that J (·) is a decreasing concave function we can conclude that max Q: Consequently as a result of the definition of E md (R, E) given in equation (13) we have Thus using equations (176) and (177) we can conclude that In order to prove the concavity of E md (R, E) in (R, E) pair, let (R a , E a ) and (R b , E b ) be two pairs such that Then for any α ∈ [0, 1] let R α and E α be From equations (179) and (180) we have Furthermore using the concavity of J (·) we get, Thus E md (R, E) is jointly concave in rate exponent pairs.

J. Proof of Theorem 2
Proof: In Section IV-D it is shown that for any positive integer ℓ a rates-exponents vector ( R, E) is achievable if there exists a time sharing vector η such that, Note that as a result of equation (184) all members of the sequence η κ are from a compact metric space. 36 Thus there exists a convergent subsequence, converging to a η. Using equation (184), definitions of R Q,i and E Q,i given in Definition 11 we can conclude that η satisfies According to Definition 11 describing the bit-wise UEP problem a rates-exponents vector ( R, E) is achievable only if there exists a reliable code sequence Q such that ( R Q , E Q ) = ( R, E). Consequently the existence of a time sharing vector satisfying (183) is also a necessary condition for the achievablity of a rates-exponents vector ( R, E) Thus we can conclude that a rates-exponents vector ( R, E) is achievable if and only if there exists a η satisfying (183).
In order to prove the convexity of region of achievable rates-exponents vectors, let ( R a , E a ) and ( R b , E b ) be two achievable rates-exponents vectors. Then there exist triples ( R a , E a , η a ) and ( R b , E b , η b ) satisfying (183).
For any α ∈ [0, 1] let R α , E α and η α be As J (·) is concave and the triples ( R a , E a , η a ) and ( R b , E b , η b ) satisfy the constraints given in (183), the triple ( R α , E α , η α ) also satisfies the constraints given in (183). Consequently the rates-exponents vector ( R α , E α ) is achievable and the region of achievable rates-exponents vectors is convex.