{'fraction_non_alphanumeric': 0.04453543080846173, 'fraction_numerical': 0.012857809862442985, 'mean_word_length': 4.089380369219521, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Binary Fading Interference Channel with No CSIT

We characterize the capacity region of the two-user Binary Fading Interference Channel where the transmitters have no knowledge of the channel state information. We show that the entire capacity region is achieved by applying point-to-point erasure codes with appropriate rates at each transmitter, and using either treat-interference-as-erasure or interference-decoding at each receiver, based on the channel parameters. The result is obtained by developing a novel outer-bound that has three main steps. We first create a contracted channel that has fewer states compared to the original channel, in order to make the analysis tractable. Using a Correlation Lemma, we then show that an outer-bound on the capacity region of the contracted channel also serves as an outer-bound for the original channel. Finally, using a Conditional Entropy Leakage Lemma, we derive our outer-bound on the capacity region of the contracted channel, and show that it coincides with the achievable region by either treat-interference-as-erasure or interference-decoding at each receiver. We also show that having access to delayed local knowledge of the channel state information, does not enlarge the capacity region.


I. INTRODUCTION
The two-user Interference Channel (IC) introduced in [2], is a canonical example to study the impact of interference in communication networks. There exists an extensive body of work on this problem (e.g., [3]- [5]). In this work, we focus on a specific configuration of this network, named the two-user Binary Fading Interference Channel (BFIC) as depicted in Fig. 1, in which the channel gains at each time instant are either 0 or 1 according to some distribution. The input-output relation of this channel at time instant t is given by  The motivation for studying the Binary Fading Interference Channel is twofold. First, as demonstrated in [6], it provides a simple, yet useful physical layer abstraction for wireless packet networks in which whenever a collision occurs, the receiver can store its received analog signal and utilize it for decoding the packets in future (for example, by successive interference cancellation techniques). In this context, the binary fading model is motivated by a shadow fading environment, in which each link is either "on" or "off" (according to the shadow fading distribution), and the multiple access (MAC) is modeled such that if two signals are transmitted simultaneously, and the links between the corresponding transmitters and the receiver are not in deep fade, then a linear combination of the signals is available to the receiver. The study of the BFIC in [6] has led to several coding opportunities that can be utilized by the transmitters to exploit the available signal at the receivers for interference management.
The second motivation for studying the BFIC is that it can be a first step towards understanding the capacity of the fading interference channels with no knowledge of the channel state information at the transmitters (CSIT). This model was used in [7], [8] to derive the capacity of the one-sided interference channel (also known as Z-Channel). Motivated by the deterministic approach [9], a layered erasure broadcast channel model was introduced in [10] to approximate the capacity of fading broadcast channels. One can view our Binary Fading model as the model introduced in [8], [10] with one layer.
In this work, we consider the two-user BFIC, and we consider two scenarios about the available channel state information at the transmitters (CSIT). In the no CSIT case, the transmitters are only aware of the distributions of the channel gains but not the actual realizations; and in the delayed local CSIT case, we assume that each transmitter learns the channel realization to its corresponding receiver with unit delay. We characterize the capacity region of this problem, and we show that under the two assumptions, the capacity region remains the same.
To derive the outer-bound, we incorporate two key lemmas. The first lemma, the Conditional Entropy Leakage Lemma, establishes how much information is leaked from each transmitter to the unintended receiver. The second lemma, the Correlation Lemma, shows that if the channel gains are correlated under a given set of conditions, the capacity region cannot be smaller than the case of independent channel gains. Using the Correlation Lemma, we create a contracted channel that has fewer states as opposed to the original channel and hence, the problem becomes tractable. Then, using the Conditional Entropy Leakage Lemma, we derive an outer-bound on the capacity region of the contracted channel which in turn, serves as an outer-bound for the original channel.
For the achievability, we show that the entire capacity region is achieved by applying point-to-point erasure codes with appropriate rates at each transmitter, and using either treat-interference-as-erasure or interference-decoding at each receiver, based on the channel parameters. Thus, message splitting (such as Han-Kobayashi scheme) is not required. We further prove that the achievable region under no CSIT assumption, matches the outer-bound on the capacity region with delayed local CSIT. Thus, the capacity region under the two models would be identical.
The rest of the paper is organized as follows. In Section II, we formulate our problem. In Section III, we present our main results. Section IV is dedicated to deriving the outer-bound for the no CSIT assumption. We describe our achievability strategy in Section V. In Section VI, we show that delayed local knowledge of the CSI, does not enlarge the capacity region. Section VII concludes the paper and describes future directions.

II. PROBLEM SETTING
We consider the two-user Binary Fading Interference Channel (BFIC) as illustrated in Fig. 1. The channel gain from transmitter Tx i to receiver Rx j at time instant t, is denoted by G ij [t], i, j ∈ {1, 2}. We assume that the channel gains are either 0 or 1 (i.e. G ij [t] ∈ {0, 1}), and they are distributed as independent Bernoulli random variables (independent from each other and over time). Furthermore, we consider the symmetric setting where We use the following notations in this paper. We use capital letters to denote random variables (RVs), e.g. G ij [t] is a random variable at time instant t, and small letters denote the realizations, e.g.
For a natural number k, we set Finally, we set In this paper, we assume that receiver i has instantaneous knowledge of G ii [t] and Gī i [t] (i.e. the incoming links to receiver i), i = 1, 2. Furthermore, we consider two models for the available channel state information at the transmitters: 1) No CSIT: In this model, we assume that transmitters only know the distribution from which the channel gains are drawn, but not the actual realizations of them; 2) Delayed Local CSIT: In this model, we assume that at time instant t, transmitter i has access to G t−1 ii besides the distribution from which the channel gains are drawn, i = 1, 2. Consider the scenario in which Tx i wishes to reliably communicate message W i ∈ {1, 2, . . . , 2 nRi } to Rx i during n uses of the channel, i = 1, 2. We assume that the messages and the channel gains are mutually independent and the messages are chosen uniformly. For each transmitter Tx i , let message W i be encoded as X n i using the encoding function f i (.) that depends on the available CSIT. Receiver Rx i is only interested in decoding W i , and it will decode the message using the decoding function W i = ϕ i (Y n i ) that depends on the available channel state information at that receiver. An error occurs when W i = W i . The average probability of decoding error is given by and the expectation is taken with respect to the random choice of the transmitted messages W 1 and W 2 . A rate tuple (R 1 , R 2 ) is said to be achievable, if there exists encoding and decoding functions at the transmitters and the receivers respectively, such that the decoding error probabilities λ 1,n , λ 2,n go to zero as n goes to infinity. The capacity region C (p d , p c ) is the closure of all achievable rate tuples. In the next section, we present the main results of the paper.

III. MAIN RESULTS
The following theorem states our main contribution. Theorem 1: The capacity region of the two-user BFIC with no and delayed local CSIT, C (p d , p c ), is given by As mentioned before, the achievability of Theorem 1 is obtained by applying point-to-point erasure codes with appropriate rates at each transmitter, and using either treat-interference-as-erasure or interference-decoding at each receiver, based on the channel parameters. More precisely, for 0 ≤ p c < p d / (1 + p d ) (i.e. β > 1), the capacity region is obtained by treating interference as erasure, while for p d / (1 + p d ) ≤ p c ≤ 1 (i.e. β = 1), the capacity region is obtained by interference-decoding (i.e. the intersection of the capacity regions of the two multiple access channels at receivers). The detailed proof of achievability can be found in Section V.
In this case (i.e. p d = 1), considering the maximum achievable sum-rate (or sum-capacity), for small values of p c , the interference cannot be decoded and as p c increases, the sum-capacity decreases as depicted in Fig. 3. However, when p d / (1 + p d ) ≤ p c , the cross link is strong enough to decode both the intended signal and the interference. We note that compared to the famous "W" curve for the Gaussian interference channel with perfect CSIT [11], here, we only observe a "V" curve. As mentioned before and depicted in Fig. 3, for 0 ≤ p c < p d / (1 + p d ), the capacity region is obtained by treating interference as erasure, while for p d / (1 + p d ) ≤ p c ≤ 1, the capacity region is obtained by interference-decoding. From (8) and Fig. 2(b), we conclude that unlike the case in Fig. 2(a), decreasing p c does not necessarily enlarge the capacity region. In fact, for p d = 0.5, we have Remark 1: Using Theorem 1 and the results of [12], we have plotted the capacity region of the two-user Binary Fading IC for p d = p c = 0.5 under three different scenarios in Fig. 4. Under the delayed CSIT, we assume that transmitters become aware of all channel realizations with unit delay and receivers have access to instantaneous CSI; and under instantaneous CSIT model, we assume that at time instant t, transmitters and receivers have access to G t . As we can see in Fig To derive the outer-bound, we incorporate two key lemmas as discussed in Section IV-A. The first step in obtaining the outer-bound is to create a "contracted" channel that has fewer states compared to the original channel. Using the Correlation Lemma, we show that an outer-bound on the capacity region of the contracted channel also serves as an outer-bound for the original channel. Finally, using the Conditional Entropy Leakage Lemma, we derive this outer-bound.
Rest of the paper is dedicated to the proof of Theorem 1. We provide the converse proof for the no CSIT case in Section IV, and we present our achievability strategy in Section V. Then in Section VI, we show that same outer-bounds also apply to the case of delayed local CSIT.

IV. CONVERSE
In this section, we provide the converse proof of Theorem 1 for the no CSIT assumption. We incorporate two lemmas in order to derive the outer-bound that we describe in the following subsection.
A. Key Lemmas 1) Entropy Leakage Lemma: Consider a broadcast channel as depicted in Fig. 5 where a transmitter is connected to two receivers through binary fading channels.
In this channel the received signals are given as where We further define Then, for the channel described above, we have the following lemma. Lemma 1: [Conditional Entropy Leakage Lemma] For the channel described above with no CSIT, and for any input distribution, we have be distributed as B(p 2 /p 1 ), and be independent of all other parameters in the network. Let where (a) holds since G t−1 H is independent of all other parameters in the network; (b) is true due to (63); (c) follows from (d) holds since the transmit signal is independent of the channel realizations; (e) follows from the fact that Y t−1 H is statistically the same as Y t−1 2 ; (f ) holds since conditioning reduces entropy; (g) is true since (h) follows from the fact that H is independent of all other parameters in the network. Thus, summing all terms for t = 1, . . . , n, we get which implies hence, completing the proof. Remark 2: In [12], we drived the Entropy Leakage Lemma for the case where the transmitter has the CSI with delay. We observe that, with delayed CSIT, the constant on the RHS of (15) would be smaller, meaning that the transmitter can further favor the stronger receiver.
Remark 3: A similar leakage lemma has also been developed in [13], in the case that there are two distributed transmitters employing linear schemes. In this case, a "Rank Ratio Inequality", is developed that bounds the maximum ratio of the dimensions of received linear-subspaces (at the two receivers) that are createdby distributed transmitters with delayed CSIT.
2) Correlation Lemma: Consider again a binary fading interference channel similar to the channel described in Section II, but where channel gains have certain correlation. We denote the channel gain from transmitter Tx i to receiver Rx j at time instant t byG ij [t], i, j ∈ {1, 2}. We distinguish the RVs in this channel, using (.) notation (e.g.,X 1 [t]). The input-output relation of this channel at time instant t is given bỹ We assume that the channel gains are distributed independent over time. However, they can be arbitrary correlated with each other subject to the following constraints.
In other words, the channel gains corresponding to incoming links at each receiver are still independent. Similar to the original channel, we assume that the transmitters in this BFIC have no knowledge of the CSI. We have the following result. Lemma 2: [Correlation Lemma] For any BFIC that satisfies the constraints in (24), we have Proof: Suppose in the original BFIC messages W 1 and W 2 are encoded as X n 1 and X n 2 respectively, and each receiver can decode its corresponding message with arbitrary small decoding error probability as n → ∞. Now, we show that if we use the same transmission scheme in the BFIC that satisfies the constraints in (24), i.e.
then the receivers in this BFIC can still decode W 1 and W 2 .
In the original two-user binary fading IC as described in Section II, Rx i uses the decoding function W i = ϕ i (Y n i , G n ii , G n ii ). Therefore, the error event W i = W i , only depends on the choice of W i and marginal distribution of the channel gains G n ii and G n ii . Define then, the probability of error is given by where p error andp error are the decoding error probability at Rx 1 in the original and the BFIC satisfying the constraints in (24) respectively; and (a) holds since according to (24), the joint distribution of G n 12 and G n 22 is the same asG n 12 andG n 22 and the fact that, as mentioned above, the error probability at receiver one only depends on the marginal distribution of these links. Similar argument holds for Rx 2 .

B. Deriving the Outer-bounds
The key to derive the outer-bound is the proper application of the two lemmas introduced in Section IV-A. More precisely, we need to find a channel that satisfies the constraints in (24) such that the outer-bound on its capacity region, coincides with the achievable region of the original problem. We provide the proof for three separate regimes.
The derivation of the individual bounds, e.g., R 1 ≤ p d , is straightforward and omitted here. We focus on where Due to symmetry, the derivation of the other bound is similar. The first step is to define the appropriate channel that satisfies the constraints in (24). The idea is to construct a channel such thatG ii [t] = 1 wheneverG iī [t] = 1, i = 1, 2. We construct such channel with only five states rather than 16 states and thus, we refer to it as "contracted" channel. The five states are denoted by states A, B, C, D, and E with corresponding probabilities p d p c , (p d − p c ) , q d p c , q d p c , and q d q c . These states are depicted in thus, this channel satisfies the conditions in (24). From Lemma 2, we have C (p d , p c ) ⊆C (p d , p c ), thus, any outerbound on the capacity region of the contracted channel, provides an outer-bound on the capacity region of the original channel. We defineX where 1 {state A occurs at time t} is equal to 1 when at time t state A occurs. Similarly, we defineX . Therefore, we havẽ Suppose in the contracted channel, there exist encoders and decoders at transmitters and receivers respectively, such that each receiver can decode its corresponding message with arbitrary small decoding error probability as n → 0. The derivation of the outer-bound is given in (35) for n → 0 as n → ∞; and We have ≤ I X n 1 ;Ỹ n 1 |G n + βI X n 2 ;Ỹ n 2 |G n where (a) follows from Fano's inequality and data processing inequality; (b) follows from the definition of the contracted channel and the chain rule; (c) is true since from Claim 1 below, we have I X n 1 ;X n 2 |G n = 0, which results in and the fact that conditioning reduces entropy; (d) follows from the chain rule; (e) holds since using Lemma 1, we have and (f ) follows since from applying Lemma 1, we have and (g) follows from the fact that entropy of a binary random variable is maximized by i.i.d. Bernoulli distribution with success probability of half. Dividing both sides by n and let n → ∞, we get the desired result. Claim 1: Proof: 0 ≤ I X n 1 ;X n 2 |G n ≤ I W 1 ,X n 1 ;W 2 ,X n 2 |G n = I W 1 ;W 2 |G n = 0 sinceW1⊥W2⊥G n + I W 1 ;X n 2 |W 2 ,G n = 0 sinceX n 2 =f2(W2,G n ) • Regime II: p d / (1 + p d ) ≤ p c ≤ p d : In this regime, the capacity region would be equal to the intersection of capacity regions of the two multiple-access channels (MACs) formed at the receivers. Thus, we need to show that We use the same contracted channel as for the case of Regime I. Let G S [t] be distributed as i.i.d. Bernoulli RV and and for i = 1, 2, we defineX We have where n → 0 as n → ∞; (a) follows from Fano's inequality and data processing inequality; (b) holds due to the definition of the contracted channel; (c) follows from the chain rule; (d) is true since from Claim 1, we have We use our definition in (44) for the rest of the proof.
where (e) follows from (44) and the fact thatX n 1A andX n 1B are statistically the same (the reason is thatX 1A [t] andX 1B [t] only depend on W 1 andG t−1 11 ), thus, and similar statement is true forX n 2A andX n 2B ; (f ) holds since from Lemma 1, we have and as a result, we have we then use the fact thatX n 2A andX n 2B are statistically the same; (i) holds sinceX n 2A andX n 2B are statistically the same; and (j) holds since • Regime III: p d ≤ p c ≤ 1: In this regime, again we have β = 1, and the capacity region would be equal to the intersection of capacity regions of the two MACs formed at the receivers. Under no CSIT assumption, we do not need to create a contracted channel. However, since we need a contracted channel for the delayed local CSIT assumption, we present the proof using a contracted channel. We consider a contracted channel with five states denoted by A, B, C, D, and E with corresponding probabilities p d p c , (p c − p d ) , p d q c , p d q c , and q d q c . These states are depicted in Table III with the exception of state E which corresponds to the case where all channel gains are 0. We assume thatG n ii = G n ii . Here, we have thus, this channel satisfies the conditions in (24). Since from Lemma 2, we have C (p d , p c ) ⊆C (p d , p c ), any outerbound on the capacity region of the contracted channel, provides an outer-bound on the capacity region of the original problem. The derivation of the outer-bound is easier compared to the other regimes. Basically, Rx i after decoding and removing its corresponding signal, has a stronger channel from Txī compared to Rxī, and thus it must be able to decode bothW i andWī, i = 1, 2. Thus, we have  In this section, we provide the achievability proof for Theorem 1. We show that the entire capacity region is achieved by applying point-to-point erasure codes with appropriate rates at each transmitter, using either treatinterference-as-erasure or interference-decoding at each receiver, based on the channel parameters.
Each transmitter applies a point-to-point erasure random code as described in [14]. On the other hand, at each receiver we have two options: (1) interference-decoding; and (2) treat-interference-as-erasure. When a receiver decodes the interference alongside its intended message, the achievable rate region is the capacity region of the multiple-access channel (MAC) formed at that receiver as depicted in Fig. 6. The MAC capacity at Rx 1 , is given by  Fig. 6. The multiple-access channel (MAC) formed at Rx1.
As a result, Rx 1 can decode its message by interference decoding, if R 1 and R 2 satisfy the constraints in (55). On the other hand, if Rx 1 treats interference as erasure, it basically ignores the received signal at time instants where G 21 [t] = 1, and p d q c fraction of the time, it receives the transmit signal of Tx 1 . Thus, Rx 1 can decode its message by treat-interference-as-erasure, if R 1 ≤ p d q c .
Similarly, Rx 2 can decode its message by treat-interference-as-erasure, if R 2 ≤ p d q c . Also, Rx 2 can decode its message by interference decoding, if R 1 and R 2 are inside the capacity region of the multiple-access channel (MAC) formed at Rx 2 , i.e.,      Therefore, the achievable rate region by either treat-interference-as-erasure or interference-decoding at each receiver is the convex hull of (57) In the remaining of this section, we show that the convex hull of R matches the outer-bound of Theorem 1, i.e.
First, it is easy to verify that the region described in (58), is the convex hull of the following corner points: Now, when 0 ≤ p c ≤ p d / (1 + p d ), the rate region R (as defined in (57)) and its convex hull are shown in Fig. 7. As we can note from Fig. 7(b), in this case the convex hull of R is indeed the convex hull of the corner points in (60). On the other hand, when p d / (1 + p d ) < p c ≤ 1, the rate region R (as defined in (57)) is depicted in Fig. 8, which is the convex hull of the first five corner points in (60). In this case, the last point in (60) is strictly inside the region in Fig. 8, hence again, R coincides with the convex hull of the corner points in (60), and this completes the proof of Theorem 1 under no CSIT assumption.

VI. EXTENSION TO DELAYED LOCAL CSIT
In this section, we complete the proof of Theorem 1 by showing that under delayed local CSIT assumption, the capacity region remains unchanged. We show that same outer-bounds hold under the delayed local CSIT assumption, and as a result, the achievability strategy of Section V suffices.
To prove this result, we first state counterparts of Lemma 1 and Lemma 2 considering the delayed local CSIT. The converse proof then follows exact same step as what we described in Section IV-B, by replacing Lemma 1 and Lemma 2 with Lemma 3 and Lemma 4 respectively.
1) Entropy Leakage Lemma with Delayed Local CSIT: Consider the scenario where a transmitter is connected to two receivers through binary fading channels as in Figure 9. In this channel the received signals are given as where X[t] ∈ {0, 1} is the transmit signal at time instant t. We assume that at each time instant t, one of the three states given in Table IV Fig. 9. A transmitter connected to two receivers through binary fading channels.
We define Set Then, for the channel described above, we have the following lemma. The proof of this lemma is presented in Appendix A.
2) Correlation Lemma with Delayed Local CSIT: Consider again a binary fading interference channel similar to the channel described in Section II, but where channel gains have certain correlation. We denote the channel gain from transmitter Tx i to receiver Rx j at time instant t byG ij [t], i, j ∈ {1, 2}. We distinguish the RVs in this channel, using (.) notation (e.g.,X 1 [t]). In this new channel, the channel gains are distributed independent over time, however, they can be arbitrary correlated as long as and In other words, the channel gains corresponding to incoming links at each receiver are still independent. The input-output relation of the contracted channel at time instant t is given bỹ We assume that the transmitters have access to delayed local knowledge of the channel state information. Similar to the original BFIC, the capacity region for the channel that satisfies (66) and (67) is denoted byC (p d , p c ). We have the following lemma and its proof is presented in Appendix B.
Lemma 4: [Correlation Lemma with Delayed Local CSIT] Consider the two user BFIC with parameters p d and p c as described in Section II and capacity C (p d , p c ). For any BFIC that satisfies (66) and (67) with capacitỹ C (p d , p c ), we have C (p d , p c ) ⊆C (p d , p c ) .
As mentioned before, the converse proof of Theorem 1 under delayed local CSIT assumption follows exact same step as what we described in Section IV-B, by replacing Lemma 1 and Lemma 2 with Lemma 3 and Lemma 4 respectively.

VII. CONCLUSION
We characterized the capacity region of the two-user Binary Fading Interference Channel with no CSIT and delayed local. We showed that the entire capacity region is achieved by applying point-to-point erasure codes with appropriate rates at each transmitter, using either treat-interference-as-erasure or interference-decoding at each receiver, based on the channel parameters. We obtained a novel outer-bound that relies on two key lemmas, and we showed that delayed local knowledge of the channel state information, does not enlarge the capacity region.
As mentioned before, the capacity region of the two-user fading Gaussian interference channel with no CSIT remains open. In this work, we considered the two-user Binary Fading Interference Channel with no CSIT, and we observed that in order to achieve the capacity region, message splitting (such as Han-Kobayashi scheme) is not required. One important question then is whether message splitting is required for the two-user fading Gaussian interference channel with no CSIT or not. To answer this question, one path would be to extend the present results to the linear deterministic model (a layered extension of our work, similar to that of [10]) and then, Gaussian model.

APPENDIX B PROOF OF LEMMA 3
Suppose messages W 1 and W 2 are encoded as X n 1 and X n 2 respectively, and each receiver in the original BFIC can decode its corresponding message with arbitrary small decoding error probability as n → ∞.
Now, we show that if we use the same transmission scheme in the BFIC that satisfies (66) and (67), i.e.
Note that X i [t] only depends on W i and G t−1 ii , i = 1, 2. Therefore, the error event W i = W i , depends on the choice of W i , G n ii , and the marginal distribution of the channel gains G n ii and G n ii . Define E W1 = (W 2 , G n 12 , G n 22 ) s.t. W 1 = W 1 , then, the probability of error is given by Pr (W 1 = w 1 ) Pr (E w1 ) = 1 2 nR1 w1 (w2,g n 12 ,g n 22 )∈Ew 1 Pr (w 2 , g n 12 , g n 22 ) (a) = 1 2 nR1 w1 (w2,g n 12 ,g n 22 )∈Ẽw 1 Pr (w 2 ,g n 12 , g n 22 ) =p error , where p error andp error are the decoding error probability at Rx 1 in the original and the BFIC that satisfies (66) and (67) respectively; and (a) holds since according to (24), the joint distribution of G n 12 and G n 22 is the same asG n 12 andG n 22 and the fact that the error probability at receiver one only depends on the marginal distribution of these links. Similar argument holds for Rx 2 .