I Introduction
Noiseless feedback does not increase the capacity for communications over discrete memoryless channels (DMC) [1]. Furthermore, Dobrushin [4] and later Haroutunian [5] showed that feedback does not improve the error exponent of symmetric channels when fixedlength codes are used. Nevertheless, feedback can be very useful in the context of variablelength codes.
In a remarkable work, Burnashev [2] demonstrated that the error exponent improves for DMCs with feedback and variablelength codes. The error exponent has a simple form
(1) 
where is the (average) rate of transmission, is the capacity of the channel, and is the maximal relative entropy between conditional output distributions. Berlin et al [6] have provided a simpler derivation of the Burnashev bound that emphasizes the link between the constant and the binary hypothesis testing problem. Yamamoto and Itoh [7] introduced a coding scheme that its error exponent achieves in (1). Their scheme consists of two distinct transmission phases that we called the data and the confirmation phase, respectively. In the data stage the message is encoded using a capacity achieving fixed blocklength code. During the confirmation phase, the transmitter sends one bit of information to the receiver. The decoder performs a binary hypothesis test to decide if or is transmitted.
In the context of communications over multiuser channels, the benefits of feedback are more prominent. For instance, Gaarder and Wolf [8] showed that feedback can expand the capacity region of discrete memoryless multipleaccess channels (MAC). Willems [9] derived the feedbackcapacity region for a class of MACs. Characterizing the capacity region and the error exponent for general MACs remains an open problem. Using directed information measures, Kramer [10] was able to characterize the feedbackcapacity region of twouser MAC with feedback. However, the characterization is in the form of infinite letter directed information measures which is not computable in general. The error exponent for discrete memoryless MAC without feedback is studied in [13, 14].
In this paper, we study the error exponent of discrete memoryless MAC with noiseless feedback. In particular, we derive an upperbound and a lowerbound. For that, let denote the polar coordinate of in . In this setting, the upperbound is
(2) 
where is the point of the capacity frontier at the angle determined by . The lowerbound is the same as but with different constant . The constants and are determined by the relative entropy between the conditional output distributions. We show that for a class of MACs the two bounds coincide.
The paper is organized as follows: In Section II, basic definitions and the problem formulation are provided. In Section III, we derive a lowerbound for the reliability function. In Section IV, we characterize an upperbound for the reliability function. In Section V, we compare the lower and upperbound and explore examples for the tightness of the bounds. Finally, Section VI concludes the paper.
Ii Problem Formulation and Definitions
Consider a discrete memoryless MAC with input alphabets , and output alphabet
. The channel conditional probability distribution is denoted by
for all . Such setup is denoted by . Let and , be the channel output and the inputs sequences after uses of the channel, respectively. Then, the following condition is satisfied:(3) 
We assume that the output of the channel as a feedback is available at the encoders with one unit of delay.
Definition 1.
An  variablelength code (VLC) for a MAC with feedback is defined by

Two sequences of encoding functions
one for each transmitter.

A sequence of decoding functions

A stopping time with respect to (w.r.t) the filtration defined as the algebra of for . Furthermore, it is assumed that satisfies .
For each , given a message , the th output of Transmitter is denoted by .
Let . Then, the decoded messages at the decoder are denoted by , and . In what follows, for any VLC, we define average ratepair, error probability, and error exponent. Average rates for an VLC are defined as
The probability of error is defined as
The error exponent of a VLC with probability of error and stopping time is defined as .
Definition 2.
A reliability function is said to be achievable for a given MAC, if for any and there exists an VLC such that
where , and is the error probability of the VLC.
Definition 3.
The reliability function of a MAC with feedback is defined as the supremum of all achievable reliability functions .
Iia The FeedbackCapacity Region of MAC
We summarize Kramer’s results presented in [10] for the feedback capacity of MAC. We use directed information and conditional directed information as defined in [10]. The normalized directed information from a sequence to a sequence when causally conditioned on is denoted by
(4) 
The feedbackcapacity region of a discrete memoryless MAC with feedback is denoted by , and is the closure of the set of all ratepairs such that
where is a positive integer, and factors as
(5) 
Definition 4.
Fact 1.
The feedbackcapacity of a discrete memoryless MAC with feedback is the same as the closure of the set of ratepairs such that the inequality
holds for all , with .
IiB Notational Conventions
For more convenience, we denote a ratepair by , where . For a MAC we use the following notational convenience
(6)  
(7)  
(8) 
The Kullback–Leibler divergence for the MAC with transition probability matrix
is defined aswhere . For notational convenience we denote
Iii A LowerBound for the Reliability Function
We build upon YamamotoItoh transmission scheme for pointtopoint (ptp) channel coding with feedback [7]. The scheme sends the messages through blocks of length . The transmission process is performed in two stages: 1) The “data transmission” stage taking up to channel uses, 2) The “confirmation” stage taking up to channel uses, where is a design parameter taking values from .
Stage 1
For the first stage, we use any coding scheme that achieves the feedbackcapacity of the MAC. The length of this coding scheme is at most . Let
denote the decoder’s estimation of the messages at the end of the first stage. Define the following random variables:
Because of the feedback, and are known at each transmitter. Therefore, at the end of the first stage, transmitter has access to , and , where .
Stage 2
The objective of the second stage is to inform the receiver whether the hypothesis or is correct. For that, each transmitter employs a code of size two and length . The codewords of such codebooks are denoted by two pairs of sequences and each with elements belonging to . Fix a jointtype defined over the set and for sequences of length . The sequences are selected randomly among all the sequences with jointtype . During this stage and given , Transmitter sends . Similarly, Transmitter 2 sends .
Decoding
Upon receiving the channel output, the receiver estimates . Denote this estimation by . If , then the hypothesis is declared. Otherwise, is declared. Because of the feedback, is also available at each encoders. If , then transmission stops and a new data packet is transmitted at the next block. Otherwise, the message is transmitted again at the next block. The process continues until occurs.
The confirmation stage in the proposed scheme can be viewed as a decentralized binary hypothesis problem in which a binary hypothesis is observed partially by two distributed agents and the objective is to convey the true hypothesis to a central receiver. This problem is qualitatively different from the sequential binary hypothesis testing problem as identified in [6] for ptp channel. Note also that in the confirmation stage we use a different coding strategy than the one used in YamamotoItoh scheme [7]. Here, all four codewords have a jointtype . It can be shown that repetition codes, and more generally, constant composition codes are strictly suboptimal in this problem.
Theorem 1.
The following is a lowerbound for the reliability function of any discrete memoryless MAC:
(9) 
where,
(10) 
and the supremum is taken over all probability distributions defined over .
Proof:
The proof is given in Appendix A. ∎
Iv An Upperbound for the Reliability Function
In this part of the paper, we establish an upperbound for the reliability function of any discrete memoryless MAC. Define
(11) 
Theorem 2 (Upperbound).
For any VLC with probability of error , and any , there exists a function such that the following is an upperbound for the reliability function of the VLC
(12) 
where is the rate pair of the VLC and satisfies
Corollary 1.
Proof:
The proof is given in Appendix E. ∎
Iva Proof of the UpperBound
Consider any VLC with probability of error , and stopping time . Suppose the message at Encoder 2, , is made available to all terminals. For the new setup, as is available at the Decoder, the average probability of error is . Note that . We refer to such setup as assisted MAC. For a maximum a posteriori decoder, after uses of the channel and assuming the realization and , define
where is a fixed real number. Also, let . Note that is a stopping time w.r.t the filtration . The following lemma provides a lowerbound on the probability of error for such setup.
Lemma 1.
The probability of error, , for a hypothesis testing over a assisted MAC and variable length codes satisfies the following inequality
where are the two hypothesizes and is the stopping time of the variable length code.
Lemma 2.
For a given MAC with finite the following holds
where .
The above lemmas are extensions of Lemma 1 and Proposition 2 in [6] for MAC. The proofs follow from similar arguments and are omitted.
Lemma 3.
Given a MAC with , and for any VLC with probability of error the following holds
(13) 
where .
Proof:
Suppose the VLC is used for a assisted MAC. As discussed before, . We modify the encoding and the decoding functions of the VLC used for the MAC. Let be a subset of the message set . The subset is to be determined at time . The new decoding function, at time , decides whether the message belongs to . The new encoding functions are the same as the original one until the time . Then, after , the transmitters perform a VLC to resolve the binary hypothesis and . This hypothesis problem is performed from to . With these modifications, the error probability of this binary hypothesis problem is a lowerbound on . In what follows, we present a construction for . Then, we apply Lemma 1 to complete the proof.
Let The quantity can be calculated at all terminals. By definition, at time , the inequality holds almost surely for all . This implies that . Hence, by Lemma 2 at time the inequality holds almost surely. We consider two cases and , where is the constant used in the definition of . For the first case, is the set consisting of the message with the highest a posteriori probability. Since , then . In addition, as , then . For the second case, set to be a set of messages such that and . Such set exists, since holds for all messages .
Note that by the above construction, for each case, . Thus, from Lemma 1 and the argument above, the inequality
holds almost surely. Next, we take the expectation of the above expression. The lemma follows by the convexity of and Jensen’s inequality.
∎
Next, we apply the same argument for the case where is available at all the terminals. For that define
and let . By symmetry, Lemma 3 holds for this case and we obtain
(14) 
Next, define the following stopping times:
Also, let . using a similar argument as in the above, we can show that
(15) 
For that, after time , we formulate a binary hypothesis problem in which the transmitters determine whether or not. Here, is a subset which is constructed using a similar method as for in the proof of Lemma 3. We further allow the transmitters to communicate with each other after . The maximum of the righthand sides of (13), (14) and (15) gives a lowerbound on . The lowerbound depends on the expectation of the stopping times . In what follows, we provide a lowerbound on . Define the following random processes.
Lemma 4.
Proof:
The proof is provided in Appendix B. ∎
We need the following lemma to proceed. The lemma is a result of Lemma 4 in [2], and we omit its proof.
Lemma 5.
For any and , the following inequality holds almost surely w.r.t
From Lemma 4 and the fact that , the processes are submartingales for . In addition, from Lemma 5 and the inequalities , we can apply Doob’s Optional Stopping Theorem for each submartingale . Then, we get:
(16) 
where .
Lemma 6.
The following inequality holds for each
Proof:
We prove the lemma for the case . The proof for follows from a similar argument. For , we obtain
(17) 
Note that the event implies that , and for all . Hence, this event is included in the event . Thus, applying Markov inequality gives
As a result of the above argument, the righthand side of (17) does not exceed the following
From Fano’s inequality we obtain
The proof is complete from the above inequality. ∎
IvB An Alternative Proof for the UpperBound
In this part of the paper, we provide a series of Lemmas that are used to prove the Theorem. Define the following random processes.
Lemma 7.
For an VLC with probability of error the following inequality holds
Proof:
The proof follows from Fano’s Lemma as in [2]. ∎
Lemma 8.
Proof:
The proof is given in Appendix C. ∎
Lemma 9.
For , define random process as
(18) 
where the function is defined as Then, there exists such that is a submartingale w.r.t .
Proof:
Suppose for some . Given this event and using the same argument as in the proof of Theorem 1 in [2] we can show that is a submartingale for all . More precisely, the inequality
holds almost surely w.r.t . Taking the expectation of the both sides in the above inequality gives
Thus, is a submartingale for and w.r.t . ∎
Corollary 2.
Suppose are nonnegative numbers such that . Define . Then, is a submartingale w.r.t .
The Theorem follows from the above lemma, and the proof is given in Appendix D.
V The Shape of the Lower and Upper Bounds
In this Section, we point out a few remarks on and the lowerbound defined in Theorem 1. Furthermore, we provide an alternative representation for the bounds and show that the lower and upperbounds match for a class of MACs.
Comments
There are no comments yet.