{'fraction_non_alphanumeric': 0.05499887833694758, 'fraction_numerical': 0.022021984595827413, 'mean_word_length': 3.974335131114004, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An information spectrum approach to the capacity region of GIFC

In this paper, we present a general formula for the capacity region of a general interference channel with two pairs of users. The formula shows that the capacity region is the union of a family of rectangles, where each rectangle is determined by a pair of spectral inf-mutual information rates. Although the presented formula is usually difficult to compute, it provides us useful insights into the interference channels. In particular, when the inputs are discrete ergodic Markov processes and the channel is stationary memoryless, the formula can be evaluated by BCJR algorithm. Also the formula suggests us that the simplest inner bounds (obtained by treating the interference as noise) could be improved by taking into account the structure of the interference processes. This is verified numerically by computing the mutual information rates for Gaussian interference channels with embedded convolutional codes. Moreover, we present a coding scheme to approach the theoretical achievable rate pairs. Numerical results show that decoding gain can be achieved by considering the structure of the interference.


I. INTRODUCTION
The interference channel (IC) is a communication model with multiple pairs of senders and receivers, in which each sender has an independent message intended only for the corresponding receiver. This model was first mentioned by Shannon [1] in 1961 and further studied by Ahlswede [2] in 1974. A basic problem for the IC is to determine the capacity region, which is currently one of long-standing open problems in information theory. Only in some special cases, the capacity regions are known, such as strong interference channels, very strong interference channels and deterministic interference channels [3][4][5][6]. For a general IC, various inner and outer bounds of the capacity region have been obtained. In 2004, Kramer derived two outer bounds on the capacity region of the general Gaussian interference channel (GIFC) [7]. The first bound for a general GIFC unifies and improves the outer bounds of Sato [8] and Carleial [9]. The second bound follows directly from the outer bounds of Sato [10] and Costa [11], which is derived by considering a degraded GIFC and is even better than the first one for certain weak GIFCs. The best inner bound (the so-called HK region) is that proposed by Han and Kobayashi [4], which has been simplified by Chong et al. and Kramer in their independent works [12] and [13]. In recent years, Etkin, Tse and Wang [14] showed by introducing the idea of approximation that HK region [4] is within one bit of the capacity region for the GIFC.
In [15], the authors proposed a new computational model for the two-user GIFC, in which one pair of users (called primary users) are constrained to use a fixed encoder and the other pair of users (called secondary users) are allowed to optimize their code. The maximum rate at which the secondary users can communicate reliably without degrading the performance of the primary users is called the accessible capacity of the secondary users. Since the structure of the interference from the primary link has been taken into account in the computation, the accessible capacity is usually higher than the maximum rate when treating the interference as noise, as is consistent with the spirit of [16] [17]. However, to compute the accessible capacity [15], the primary link is allowed to have a non-neglected error probability. This makes the model unattractive when the capacity region is considered. For this reason, we will relax the fixedcode constraints on the primary users in this paper. In other words, we will compute a pair of transmission rates at which both links can be asymptotically error-free.
In this paper, we consider a more general interference channel which is characterized by a sequence of transition probabilities. By the use of the information spectrum approach [18] [19], we present a general formula for the capacity region of the general interference channel with two pairs of users. The formula shows that the capacity region is the union of a family of rectangles, in which each rectangle is determined by a pair of spectral inf-mutual information rates. The information spectrum approach, which is based on the limit superior/inferior in probability of a sequence of random variables, has been proved to be powerful in characterizing the limit behavior of a general source/channel. For instance, in [18] and [20], Han and Verdú proved that the minimum compression rate for a general source equals its spectral sup-entropy rate and the maximum transmission rate for a general point-to-point channel equals its spectral inf-mutual information rate with an optimized input process. Also the information spectrum approach can be used to derive the capacity region of a general multiple access channel [21]. For more applications of the information spectrum approach, see [19] and the references therein.
The rest of the paper is structured as follows. Sec. II introduces the definition of a general IC and the concept of the spectral inf-mutual information rate. In Sec. III-A, a general formula for the capacity region of the general IC is proposed; while, in Sec. III-B, a trellis-based algorithm is presented to compute the pair of rates for a stationary memoryless IC with discrete ergodic Markov sources. In Sec. III-C, numerical results are presented for a GIFC with binary-phase shift-keying (BPSK) modulation. Sec. IV provides the detection and decoding algorithms for channels with structured interference. Sec. V concludes this paper.
In this paper, a random variable is denoted by an upper-case letter, say X, while its realization and sample space are denoted by x and X , respectively. The sequence of random variables with length n are denoted by X n , while its realization is denoted by x ∈ X n or x n ∈ X n . We use P X (x) to denote the probability mass function (pmf) of X if it is discrete or the probability density function (pdf) of X if it is continuous.

A. General IC
Let X 1 , X 2 be two finite input alphabets and Y 1 , Y 2 be two finite output alphabets. A general interference channel W (see Fig. 1) is characterized by a sequence W = {W n (·, ·|·, ·)} ∞ n=1 , where W n : X n 1 × X n 2 → Y n 1 × Y n 2 is a probability transition matrix. That is, for all n, The marginal distributions W n 1 , W n 2 of the W n are given by n , M n , ε n , ε n ) code for the interference channel W consists of the following essentials: a) message sets: n }, for Sender 2 b) sets of codewords: for Encoder 2 For Sender 1 to transmit message i, Encoder 1 outputs the codeword x 1 (i). Similarly, for Sender 2 to transmit message j, Encoder 2 outputs the codeword x 2 (j). c) collections of decoding sets: where "c" denotes the complement of a set. Here we have assumed that each message of n and j ∈ M (2) n is produced independently with uniform distribution.

Remark:
The optimal decoding to minimize the probability of errors is defining the decoding sets B 1i and B 2j according to the the maximum likelihood decoding [22]. That is, the two receivers choose, respectively,î as the estimates of the transmitted messages.
Definition 2: A rate pair (R 1 , R 2 ) is achievable if there exists a sequence of (n, M n , M n , ε n , ε n ) codes such that

Definition 3:
The set of all achievable rates is called the capacity region of the interference channel W, which is denoted by C(W).

B. Preliminaries of Information-Spectrum Approach
The following notions can be found in [19].
for all x 1 ∈ X n 1 , x 2 ∈ X n 2 and n, they are called independent and denoted by X 1 ⊥X 2 . Similar to [18], we have Given an (X 1 , X 2 ) ∈ S I , for the interference channel W, we define the spectral inf-mutual information rate by where III. THE CAPACITY REGION OF GENERAL IC In this section, we derive a formula for the capacity region C(W) of the general IC.

A. The Main Theorem
Theorem 1: The capacity region C(W) of the interference channel W is given by where R W (X 1 , X 2 ) is defined as the collection of all (R 1 , R 2 ) satisfying that To prove Theorem 1, we need the following lemmas.

Lemma 1:
Let be any channel input such that (X 1 , X 2 ) ∈ S I . The corresponding output via an interference Then, for any fixed M n , ε (1) n , ε (2) n ) code satisfying that where n + γ} and γ > 0 is an arbitrarily small number.
Proof of Lemma 1: The proof is similar to that of [18,Lemma 3].
subject to the probability distribution P X n 1 . Similarly, generate M (2) n independent codewords n ) ∈ X n 2 subject to the probability distribution P X n 2 . Encoding. To send message i, Sender 1 sends the codeword x 1 (i). Similarly, to send message j, Sender 2 sends x 2 (j).
Decoding. Receiver 1 chooses the i such that (x 1 (i), y 1 ) ∈ T n (1) if such i exists and is unique.
Similarly, Receiver 2 chooses the j such that (x 2 (j), y 2 ) ∈ T n (2) if such j exists and is unique.
Otherwise, an error is declared.
Analysis of the error probability. By the symmetry of the random code construction, we can assume that (1, 1) was sent. Define For Receiver 1, an error occurs if (x 1 (1), y 1 ) / ∈ T n (1) or (x 1 (i), y 1 ) ∈ T n (1) for some i = 1.
Similarly, for Receiver 2, an error occurs if (x 2 (1), y 2 ) / ∈ T n (2) or (x 2 (j), y 2 ) ∈ T n (2) for some j = 1. So the ensemble average of the error probabilities of Decoder 1 and Decoder 2 can be upper-bounded as follows: It can be seen that where (a) follows from the independence of x 1 (i) (i = 1) and y 1 and (b) follows from the Combining all inequalities above, we can see that there must exist at least one (n, M n ) code satisfying (11).

Proof of Lemma 2:
The proof is similar to that of [18,Lemma 4]. By using the relation , we can rewrite the first term on the right-hand side of the first inequality of (13) as By setting the first inequality of (13) can be expressed as In order to prove this inequality, we set It can be seen that where B 1i is the decoding region corresponding to codeword x 1 (i) and (a) follows from the definition of A i . Therefore, the first inequality of (13) is proved. Similarly, we can obtain the second inequality of (13).
Now we prove Theorem 1.

Proof of Theorem 1:
1) To prove that an arbitrary rate pair (R 1 , R 2 ) satisfying (9) and (10) is achievable, we define for an arbitrarily small constant γ > 0. Lemma 1 guarantees the existence of an (n, M From the definition of the spectral inf-mutual information rate, we have lim n→∞ ε (1) n = 0 and lim n→∞ ε (2) n = 0.
2) Suppose that a rate pair (R 1 , R 2 ) is achievable. Then, for any constant γ > 0, there exists for all sufficiently large n and Taking the limits as n → ∞ on both sides, we have From the definitions of I(X 1 ; Y 1 ) and I(X 2 ; Y 2 ), we can see that R 1 − 2γ ≤ I(X 1 ; Y 1 ) and , which completes the proof since γ is arbitrary.

B. The Algorithm to Compute Achievable Rate Pairs
Theorem 1 provides a general formula for the capacity region of a general IC. However, it is usually difficult to compute the spectral inf-mutual information rates given in (9) and (10). In order to get insights into the interference channels, we make the following assumptions: 1) the channel is stationary and memoryless, that is, the transition probability of the channel can be written as 2) sources are restricted to be stationary and ergodic discrete Markov processes.
With the above assumptions, the spectral inf-mutual information rates are reduced as which can be evaluated by the Monte Carlo method [23][24] [25] using BCJR algorithm [26] over a trellis. Actually, any stationary and ergodic discrete Markov source can be represented by a time-invariant trellis and (hence) is uniquely specified by a trellis section. A trellis section is composed of left (or starting) states and right (or ending) states, which are connected by branches in between. For example, Source x 1 can be specified by a trellis T 1 as follows.
• Both the left and right states are selected from the set is the right state, and the symbol x 1 (b) ∈ X 1 is the associated label. We also assume that a branch b is uniquely determined by s − 1 (b) and x 1 (b); • At time t = 0, the source starts from state s 1,0 ∈ S 1 . If at time t − 1 (t > 0), the source is in the state s 1,t−1 ∈ S 1 , then at time t (t > 0), the source generates a symbol x 1,t ∈ X 1 according to the conditional probability P (x 1,t |s 1,t−1 ) and goes into a state s 1,t ∈ S 1 such that (s 1,t−1 , x 1,t , s 1,t ) is a branch. Obviously, when the source runs from time t = 0 to t = n, a sequence x 1,1 , x 1,2 , ..., x 1,n is generated. The Markov property says that P (x 1,t |x 1,1 , ..., x 1,t−1 , s 1,0 ) = P (x 1,t |s 1,t−1 ).
So the probability of a given sequence x 1,1 , x 1,2 , ..., x 1,n with the initial state s 1,0 can be factored as Similarly, we can represent x 2 by a trellis T 2 with the state set is the right state and the symbol x 2 (b) ∈ X 2 is the associated label. Assume that source x 2 starts from the state s 2,0 ∈ S 2 . If at time t−1 (t > 0), the source is in the state s 2,t−1 ∈ S 2 , then at time t (t > 0), the source generates a symbol x 2,t ∈ X 2 according to the conditional probability P (x 2,t |s 2,t−1 ) and goes into a state s 2,t ∈ S 2 such that (s 2,t−1 , x 2,t , s 2,t ) is a branch. The probability of a given sequence x 2,1 , x 2,2 , ..., x 2,n can be factored as P (x 2,1 , x 2,2 , ..., x 2,n |s 2,0 ) = n t=1 P (x 2,t |s 2,t−1 ).
In what follows, we have fixed the initial states as s 1,0 = 0 and s 2,0 = 0, and removed them from the equations for simplicity.
Next we focus on the evaluation of lim n→∞ 1 n I(X n 1 ; Y n 1 ), while lim n→∞ 1 n I(X n 2 ; Y n 2 ) can be estimated similarly. Specifically, we can express the limit as where lim  [27], it can be seen that, with probability 1, where y n 1 stands for (y 1,1 , y 1,2 , ..., y 1,n ). Then evaluating lim for a sufficiently long typical sequence y n 1 . Here, the key is to compute the conditional probabilities P (y 1,t |y t−1 1 ) for all t. Since both y 1 and y 2 are hidden Markov sequences, this can be done by performing the BCJR algorithm over the following product trellis.
• The product trellis has the state set S = S 1 × S 2 , where "×" denotes Cartesian product.
• Each branch is represented by a four-tuple b = (s − (b), ) are branches in T 1 and T 2 , respectively. the sources generate symbols (x 1,t ∈ X 1 , x 2,t ∈ X 2 ) according to the conditional probability P (x 1,t |s 1,t−1 )P (x 2,t |s 2,t−1 ) and go into a state s t = (s 1,t , s 2,t ) ∈ S 2 such that (s t−1 , x 1,t , x 2,t , s t ) is a branch.
Given the received sequence y 1 , we define • Branch metrics: To each branch b t = {s t−1 , x 1,t , x 2,t , s t }, we assign a metric = P (x 1,t |s 1,t−1 )P (x 2,t |s 2,t−1 )P (y 1,t |x 1,t x 2,t ), In the computation of lim n→∞ 1 n H(Y n 1 |X n 1 ), the metric is replaced by P (b t |s t−1 , x 1,t )P (y 1,t |x 1,t x 2,t ). • State transition probabilities: The transition probability from s t−1 to s t is defined as • Forward recursion variables: We define the a posteriori probabilities Then P (y 1,t |y t−1 1 ) = where the values of α t (s t ) can be computed recursively by In summary, the algorithm to estimate the entropy rate lim

4) Simulations for Receiver 1:
Generate the received sequence y 1 according to the transition probability W n (y 1 , y 2 |x 1 , x 2 ).

C. Numerical Results
We consider the model as shown in Fig. 2, where the channel inputs x 1 (i) and x 2 (j) are BPSK sequences with power constraints P 1 and P 2 , respectively; the additive noise n 1 and n 2 are sequences of independent and identically distributed (i.i.d.) standard Gaussian random variables; the channel outputs y 1 and y 2 are We assume that x 1 and x 2 are the outputs from two (possibly different) generalized trellis encoders driven by independent and uniformly distributed (i.u.d.) input sequences, as proposed in [15]. As examples, we consider two input processes. One is referred to as "UnBPSK", standing for an i.u.d. BPSK sequence; the other is referred to as "CcBPSK", standing for an output sequence from the convolutional encoder with the generator matrix G(D) = [1+D +D 2 1+D 2 ] driven by an i.u.d. input sequence. The point "C" represents the limits when the two senders use binary linear codes but regard the interference as an i.u.d. additive (BPSK) noise. It can be seen that the area of the pentagonal region ODBAI is greater than that of the rectangle OECH, which implies that knowing the structure of the interference can be used to improve potentially the bandwidth-efficiency.

IV. DECODING ALGORITHMS FOR CHANNELS WITH STRUCTURED INTERFERENCE
The purpose of this section has two-folds. The first is to present a coding scheme to approach the point "B" in Fig. 4. The second is to show the decoding gain achieved by taking into account the structure of the interference.

A. A Coding Scheme
We design a coding scheme using Kite codes 2 . Kite codes are a class of low-density paritycheck (LDPC) codes, which can be decoded using the sum-product algorithm (SPA) [30,31].
As shown in Fig. 5, Sender 1 uses a Kite code (with a parity-check matrix H 1 ) and Sender 2 2 The main reason that we choose Kite codes is that it is convenient to set up the code rates. Actually, given data length, the code rates of Kite codes can be "continuously" varying from 0.1 to 0.9 with satisfactory performance, as shown in [28] [29].
where P k is the power. Then we transmit x k for k = 1, 2 over the interference channel.
Decoding: After receiving y 1 , Receiver 1 attempts to recover the transmitted message u 1 .
Similarly, after receiving y 2 , Receiver 2 attempts to recover the transmitted message u 2 . We will consider several decoding algorithms in the next subsection to recover the transmitted messages.

B. Decoding Algorithms
In this subsection, depending on the knowledge about the interference, we present four decoding schemes, including "knowing only the power of the interference", "knowing the signaling Fig. 6. A normal graph of a general (sub)system. of the interference", "knowing the CC" and "knowing the whole structure". We focus on the decoding of Receiver 1, while the decoding of Receiver 2 can be implemented similarly. 3 All these decoding algorithms will be described as message processing/passing algorithms over normal graphs [32].
1) Message processing/passing algorithms over normal graphs: As shown in Fig. 6, a normal graph consists of edges and vertices, which represent variables and subsystem constraints, respectively. Let Z = {Z 1 , Z 2 , · · · , Z n } be n distinct random variables that constitute a subsystem S (0) . This subsystem can be represented by a normal subgraph with edges representing Z and a vertex S (0) representing the subsystem constraints. Each half-edge (ending with a dongle) may potentially be coupled to some half-edge in other subsystems. For example, Z 1 and Z m are shown to be connected to subsystems S (1) and S (m) , respectively. In this case, the corresponding edge is called a full-edge. Associated with each edge is a message that is defined in this paper as the pmf/pdf of the corresponding variable. As in [33], we use the notation P (S (i) →S (0) ) Z i (z) to denote the message from S (i) to S (0) . In particular, we use the notation P (|→S (0) ) Z i (z) to represent the initial messages "driving" the subsystem S (0) . For example, such initial messages can be the a priori probabilities from the source or the a posteriori probabilities computed from the channel observations. Assume that all messages to S (0) are available. The vertex S (0) , as a message processor, delivers the outgoing message with respect to any given Z i by computing Fig. 7. The normal graphs: (a) stands for the normal graph of "knowing only the power of the interference" and "knowing the signaling of the interference" for Decoder 1; (b) stands for the normal graph of "knowing the CC" and "knowing the whole structure" for Decoder 1.
the likelihood function by considering all the available messages as well as the system constraints. We claim that is exactly the so-called extrinsic message because the computation of the likelihood function is irrelevant to the incoming message P 2) Knowing only the power of the interference: The decoding scheme for "knowing only the power of the interference" is the simplest one, which can be described as a message processing/passing algorithm over the normal graph as shown in Fig. 7(a). In this scheme, the interference from Sender 2 is treated as a Gaussian distribution with mean zero and variance aP 2 , where "P 2 " is the power and "a" is the square of interference coefficient. That is, Receiver 1 assumes that X 2,j ∼ N (0, aP 2 ) for j = 1, 2, · · · , N. Since N 1,j ∼ N (0, 1) for j = 1, 2, · · · , N, the decoding algorithm is initialized by the initial messages as follows for j = 1, 2, · · · , N. Then the decoding algorithm uses SPA to compute iteratively the extrinsic messages P . Once these are done, we make the following decisions: for i = 1, 2, · · · , L 1 and j = 1, 2, · · · , N. The details about the decoding algorithm are shown as below.
3) Set a maximum iteration number J and iteration variable j = 1.
3) Knowing the signaling of the interference: The decoding algorithm for this scheme is almost the same as Algorithm 2, see Fig. 7(a). The difference is that X 2,j ∼ B(1/2) (Bernoulli-1/2 distribution 4 ) for j = 1, 2, · · · , N. So the computation of P Then the decoding algorithm of "knowing the signaling of the interference" can be shown as below.
3) Set a maximum iteration number J and iteration variable j = 1.
• End decoding. 4) Knowing the CC: "Knowing the CC" means that Decoder 1 knows the structure of the convolutional code. This scheme can be described as a message processing/passing algorithm over the normal graph as shown in Fig. 7(b). Actually, the vertex T 1 is a combination of three subsystems, convolutional encoder, modulation and GIFC constraint, which can be specified by a trellis T with parallel branches [15]. Therefore, the BCJR algorithm can be used to compute the extrinsic messages P (T 1 →K 1 ) C 1,j (c) for j = 1, 2, · · · , N over the trellis T . Since the structure of Kite code for Sender 2 is unknown, the constraint of vertex K 2 is inactive. In this case, the pmf of variable V 2,k (k = 1, 2, · · · , N ′ ) is assumed to be Bernoulli-1/2 distribution. There are two strategies to implement the BCJR algorithm. One is called "BCJR-once", in which the BCJR algorithm is performed only once. The other strategy is called "BCJR-repeat", in which the BCJR algorithm is performed more than once. In this scheme, the decoding decisions on C 1,j are modified intô for j = 1, 2, · · · , N. These two decoding procedures are described in Algorithm 4 and Algorithm 5, respectively.
3) Set a maximum iteration number J and iteration variable j = 1.
• End Decoding 5) Knowing the whole structure: The scheme "knowing the whole structure" for Receiver 1 can also be described as a message processing/passing algorithm over the normal graph shown in Fig. 7(b). Since knowing the whole structure of the interference, Receiver 1 can decode iteratively utilizing the structure of both users. Using the BCJR algorithm, P are computed simultaneously over the parallel branch trellis T . The iterative decoding algorithm is presented in Algorithm 6.
• End Decoding

C. Numerical Results
In this subsection, simulation results of the decoding algorithms are shown and analyzed.
Simulation parameters of Fig. 8 and Fig. 9 are presented in TABLE I. In these two figures, we let the power constraints of two senders be same, that is, P 1 ≡ P 2 = P . Here, "Gaussian" stands for the scheme "knowing only the power of the interference", "BPSK" stands for the scheme "knowing the signaling of the interference", "BCJR1" stands for the scheme "BCJRonce", "CONV" stands for the scheme "BCJR-repeat" and "Know All Structure" stands for the scheme "knowing the whole structure". From Fig. 8 and Fig. 9, we can easily see that the decoding gains get larger as more details of the structure of the interference are known.  8. The error performance of Receiver 1. "Gaussian" stands for the scheme "knowing only the power of the interference", "BPSK" stands for the scheme "knowing the signaling of the interference", "BCJR1" stands for the scheme "BCJR-once", "CONV" stands for the scheme "BCJR-repeat" and "Know All Structure" stands for the scheme "knowing the whole structure". Another objective is to find out a code rate pair nearest to the point "B" in Fig. 4 with bit error rate (BER) performance of 10 −4 . So we do the simulations with different code rate pairs.
In the simulations, we adopt the scheme "knowing the whole structure" and gradually decrease the code rates from the point "B" with a step length 0.01. Simulation parameters for different  9. The error performance of Receiver 2. "Gaussian" stands for the scheme "knowing only the power of the interference", "BPSK" stands for the scheme "knowing the signaling of the interference" and "Know All Structure" stands for the scheme "knowing the whole structure". code rate pairs are listed in TABLE II, while the simulation results are presented using a 3D graph in Fig. 10. From the figure, it is obvious that as the code rates of two users are decreasing, the BER also decreases. Finally, we find out the "best" code rate pair is (0.71, 0.48) for User 1 and User 2. The theoretical value of the point "B" is about (0.878, 0.486). So we can see that the gap between the result using our decoding scheme and the theoretical value is small.

Parameters Values
Square of interference coefficient a 0.5

Maximum iteration number J 200
Code length N of Kite Code of Sender 1 10000 Code length N ′ of Kite Code of Sender 2 5000 Generator matrix G(D) Step length 100 Range of message length L 1 7100 ∼ 8800 Range of message length L 2 4000 ∼ 4900

V. CONCLUSIONS
In this paper, we have proved that the capacity region of the two-user interference channel is the union of a family of rectangles, each of which is defined by a pair of spectral inf-mutual information rates associated with two independent input processes. For the stationary memoryless channel with discrete Markov inputs, the defined pair of rates can be computed, which show us that the simplest inner bounds (obtained by treating the interference as noise) could be improved by taking into account the structure of the interference processes. Also a concrete coding scheme to approach the theoretical achievable rate pairs was presented, which showed that the decoding gain can be achieved by considering the structure of the interference.