# An Information-Spectrum Approach to the Capacity Region of the Interference
Channel

Authors  Xiao Ma, Lei Lin, Chulong Liang, Xiujie Huang, and Baoming Bai This
paper was presented in part at the 2012 IEEE International Symposium on
Information Theory. This work was supported by the 973 Program
(No.2012CB316100) and the NSFC (No.61172082).X. Ma, and C. Liang are with the
Department of Electronic and Communication Engineering, Sun Yat-sen
University, Guangzhou 510006, Guangdong, China (email:
maxiao@mail.sysu.edu.cn).L. Lin is with the Department of Applied Mathematics,
Sun Yat-sen University, Guangzhou 510006, Guangdong, China (email:
linlei2@mail2.sysu.edu.cn).X. Huang is with the Department of Electrical
Engineering, University of Hawaii, Honolulu 96822, HI, USA.B. Bai is with the
State Lab. of ISN, Xidian University, Xi’an 710071, Shaanxi, China.

###### Abstract

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.

###### Index Terms:

Capacity region, interference channel, information spectrum, limit
superior/inferior in probability, spectral inf-mutual information rate.

##  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 fixed-code 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 $\mathcal{X}$,
respectively. The sequence of random variables with length $n$ are denoted by
$X^{n}$, while its realization is denoted by ${\bf x}\in\mathcal{X}^{n}$ or
$x^{n}\in\mathcal{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.

Figure 1: General interference channel ${\bf W}$.

##  II Basic Definitions And Problem Statement

###  II-A General IC

Let $\mathcal{X}_{1}$, $\mathcal{X}_{2}$ be two finite input alphabets and
$\mathcal{Y}_{1}$, $\mathcal{Y}_{2}$ be two finite output alphabets. A general
interference channel ${\bf W}$ (see Fig. 1) is characterized by a sequence
${\bf W}=\\{W^{n}(\cdot,\cdot|\cdot,\cdot)\\}_{n=1}^{\infty}$, where
$W^{n}:\mathcal{X}_{1}^{n}\times\mathcal{X}_{2}^{n}\rightarrow\mathcal{Y}_{1}^{n}\times\mathcal{Y}_{2}^{n}$
is a probability transition matrix. That is, for all $n$,

$\displaystyle W^{n}({\bf y}_{1},{\bf y}_{2}|{\bf x}_{1},{\bf x}_{2})$
$\displaystyle\geq$ $\displaystyle 0$ $\displaystyle\sum\limits_{{\bf
y}_{1}\in\mathcal{Y}_{1}^{n},{\bf y}_{2}\in\mathcal{Y}_{2}^{n}}W^{n}({\bf
y}_{1},{\bf y}_{2}|{\bf x}_{1},{\bf x}_{2})$ $\displaystyle=$ $\displaystyle
1.$

The marginal distributions $W_{1}^{n},W_{2}^{n}$ of the $W^{n}$ are given by

$\displaystyle W_{1}^{n}({\bf y}_{1}|{\bf x}_{1},{\bf x}_{2})$
$\displaystyle=$ $\displaystyle\sum_{{\bf
y}_{2}\in\mathcal{Y}_{2}^{n}}W^{n}({\bf y}_{1},{\bf y}_{2}|{\bf x}_{1},{\bf
x}_{2}),$ (1) $\displaystyle W_{2}^{n}({\bf y}_{2}|{\bf x}_{1},{\bf x}_{2})$
$\displaystyle=$ $\displaystyle\sum_{{\bf
y}_{1}\in\mathcal{Y}_{1}^{n}}W^{n}({\bf y}_{1},{\bf y}_{2}|{\bf x}_{1},{\bf
x}_{2}).$ (2)

###### Definition 1

An $(n,M_{n}^{(1)},M_{n}^{(2)},\varepsilon_{n}^{(1)},\varepsilon_{n}^{(2)})$
code for the interference channel ${\bf W}$ consists of the following
essentials:

  * a)

message sets:

$\displaystyle\mathcal{M}_{n}^{(1)}=\\{1,2,\ldots,M_{n}^{(1)}\\},\,\,\,$
$\displaystyle{\rm for\,\,\,Sender~{}1}$
$\displaystyle\mathcal{M}_{n}^{(2)}=\\{1,2,\ldots,M_{n}^{(2)}\\},\,\,\,$
$\displaystyle{\rm for\,\,\,Sender~{}2}$

  * b)

sets of codewords:

$\begin{array}[]{ll}\\{{\bf x}_{1}(1),{\bf x}_{1}(2),\ldots,{\bf
x}_{1}(M_{n}^{(1)})\\}\subseteq\mathcal{X}_{1}^{n},&{\rm
for\,\,\,Encoder~{}1}\\\ \\{{\bf x}_{2}(1),{\bf x}_{2}(2),\ldots,{\bf
x}_{2}(M_{n}^{(2)})\\}\subseteq\mathcal{X}_{2}^{n},&{\rm
for\,\,\,Encoder~{}2}\end{array}$

For Sender 1 to transmit message $i$, Encoder 1 outputs the codeword ${\bf
x}_{1}(i)$. Similarly, for Sender 2 to transmit message $j$, Encoder 2 outputs
the codeword ${\bf x}_{2}(j)$.

  * c)

collections of decoding sets:

$\begin{array}[]{ll}\mathcal{B}_{1}=\\{\mathcal{B}_{1i}\subseteq\mathcal{Y}_{1}^{n}\\}_{i=1,...,M_{n}^{(1)}},&{\rm
for\,\,\,Decoder~{}1}\\\
\mathcal{B}_{2}=\\{\mathcal{B}_{2j}\subseteq\mathcal{Y}_{2}^{n}\\}_{j=1,...,M_{n}^{(2)}},&{\rm
for\,\,\,Decoder~{}2}\end{array}$

where
$\mathcal{Y}_{1}^{n}=\bigcup\limits_{i=1}^{M_{n}^{(1)}}\mathcal{B}_{1i},\,\,\mathcal{B}_{1i}\bigcap\mathcal{B}_{1i^{\prime}}=\emptyset$
for $i\neq i^{\prime}$ and
$\mathcal{Y}_{2}^{n}=\bigcup\limits_{j=1}^{M_{n}^{(2)}}\mathcal{B}_{2j},\,\,\mathcal{B}_{2j}\bigcap\mathcal{B}_{2j^{\prime}}=\emptyset$
for $j\neq j^{\prime}$. That is, $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$ are
the disjoint partitions of $\mathcal{Y}_{1}^{n}$ and $\mathcal{Y}_{2}^{n}$
determined in advance, respectively. After receiving ${\bf y}_{1}$, Decoder 1
outputs $\hat{i}$ whenever ${\bf y}_{1}\in\mathcal{B}_{1\hat{i}}$. Similarly,
after receiving ${\bf y}_{2}$, Decoder 2 outputs $\hat{j}$ whenever ${\bf
y}_{2}\in\mathcal{B}_{2\hat{j}}$.

  * d)

probabilities of decoding errors:

$\begin{array}[]{ll}&\varepsilon_{n}^{(1)}=\frac{1}{M_{n}^{(1)}M_{n}^{(2)}}\sum\limits_{i=1}^{M_{n}^{(1)}}\sum\limits_{j=1}^{M_{n}^{(2)}}W_{1}^{n}(\mathcal{B}^{c}_{1i}|{\bf
x}_{1}(i),{\bf x}_{2}(j)),\\\
&\varepsilon_{n}^{(2)}=\frac{1}{M_{n}^{(1)}M_{n}^{(2)}}\sum\limits_{i=1}^{M_{n}^{(1)}}\sum\limits_{j=1}^{M_{n}^{(2)}}W_{2}^{n}(\mathcal{B}^{c}_{2j}|{\bf
x}_{1}(i),{\bf x}_{2}(j)),\end{array}$

where $``c"$ denotes the complement of a set. Here we have assumed that each
message of $i\in\mathcal{M}_{n}^{(1)}$ and $j\in\mathcal{M}_{n}^{(2)}$ is
produced independently with uniform distribution.

Remark: The optimal decoding to minimize the probability of errors is defining
the decoding sets $\mathcal{B}_{1i}$ and $\mathcal{B}_{2j}$ according to the
the maximum likelihood decoding [22]. That is, the two receivers choose,
respectively,

$\hat{i}=\arg\max_{i}{\rm Pr}\\{{\bf y}_{1}|{\bf x}_{1}(i)\\}$

and

$\hat{j}=\arg\max_{j}{\rm Pr}\\{{\bf y}_{2}|{\bf x}_{2}(j)\\}$

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}^{(1)},M_{n}^{(2)},\varepsilon_{n}^{(1)},\varepsilon_{n}^{(2)})$
codes such that

$\displaystyle\lim_{n\rightarrow\infty}\varepsilon_{n}^{(1)}=0$
$\displaystyle{\rm and}$
$\displaystyle\lim_{n\rightarrow\infty}\varepsilon_{n}^{(2)}=0,$
$\displaystyle\liminf_{n\rightarrow\infty}\frac{\log M_{n}^{(1)}}{n}\geq
R_{1}$ $\displaystyle{\rm and}$
$\displaystyle\liminf_{n\rightarrow\infty}\frac{\log M_{n}^{(2)}}{n}\geq
R_{2}.$

###### Definition 3

The set of all achievable rates is called the capacity region of the
interference channel ${\bf W}$, which is denoted by $\mathcal{C}({\bf W})$.

###  II-B Preliminaries of Information-Spectrum Approach

The following notions can be found in [19].

######  Definition 4 (liminf in probability)

For a sequence of random variables $\\{Z^{n}\\}_{n=1}^{\infty}$,

$p\textrm{-}\liminf_{n\rightarrow\infty}Z^{n}\overset{\triangle}{=}\sup\\{\beta|\lim_{n\rightarrow\infty}{\rm
Pr}\\{Z^{n}<\beta\\}=0\\}.$

###### Definition 5

If two random variables sequences ${\bf
X}_{1}=\\{{X}_{1}^{n}\\}_{n=1}^{\infty}$ and ${\bf
X}_{2}=\\{{X}_{2}^{n}\\}_{n=1}^{\infty}$ satisfy that

$P_{{X}_{1}^{n}{X}_{2}^{n}}({\bf x}_{1},{\bf x}_{2})=P_{{X}_{1}^{n}}({\bf
x}_{1})P_{{X}_{2}^{n}}({\bf x}_{2})$ (3)

for all ${\bf x}_{1}\in\mathcal{X}_{1}^{n}$, ${\bf
x}_{2}\in\mathcal{X}_{2}^{n}$ and $n$, they are called independent and denoted
by ${\bf X}_{1}\bot{\bf X}_{2}$.

Similar to [18], we have

###### Definition 6

Let $S_{I}\stackrel{{\scriptstyle\triangle}}{{=}}\\{({\bf X}_{1},{\bf
X}_{2})|{\bf X}_{1}\bot{\bf X}_{2}\\}$. Given an $({\bf X}_{1},{\bf X}_{2})\in
S_{I}$, for the interference channel ${\bf W}$, we define the spectral inf-
mutual information rate by

$\displaystyle\underline{I}({\bf X}_{1};{\bf Y}_{1})$ $\displaystyle\equiv$
$\displaystyle
p\textrm{-}\liminf_{n\rightarrow\infty}\frac{1}{n}\log\frac{P_{Y_{1}^{n}|X_{1}^{n}}({Y}_{1}^{n}|{X}_{1}^{n})}{P_{{Y}_{1}^{n}}({Y}_{1}^{n})},$
(4) $\displaystyle\underline{I}({\bf X}_{2};{\bf Y}_{2})$
$\displaystyle\equiv$ $\displaystyle
p\textrm{-}\liminf_{n\rightarrow\infty}\frac{1}{n}\log\frac{P_{Y_{2}^{n}|X_{2}^{n}}({Y}_{2}^{n}|{X}_{2}^{n})}{P_{{Y}_{2}^{n}}({Y}_{2}^{n})},$
(5)

where

$\displaystyle P_{Y_{1}^{n}|X_{1}^{n}}({\bf y}_{1}|{\bf x}_{1})$
$\displaystyle=$ $\displaystyle\sum_{{\bf x}_{2},{\bf
y}_{2}}P_{X_{2}^{n}}({\bf x}_{2})W^{n}({\bf y}_{1},{\bf y}_{2}|{\bf
x}_{1},{\bf x}_{2}),$ (6) $\displaystyle P_{Y_{2}^{n}|X_{2}^{n}}({\bf
y}_{2}|{\bf x}_{2})$ $\displaystyle=$ $\displaystyle\sum_{{\bf x}_{1},{\bf
y}_{1}}P_{X_{1}^{n}}({\bf x}_{1})W^{n}({\bf y}_{1},{\bf y}_{2}|{\bf
x}_{1},{\bf x}_{2}).$ (7)

##  III The Capacity Region of General IC

In this section, we derive a formula for the capacity region $\mathcal{C}({\bf
W})$ of the general IC.

###  III-A The Main Theorem

###### Theorem 1

The capacity region $\mathcal{C}({\bf W})$ of the interference channel ${\bf
W}$ is given by

$\mathcal{C}({\bf W})=\bigcup_{({\bf X}_{1},{\bf X}_{2})\in
S_{I}}\mathcal{R}_{\bf W}({\bf X}_{1},{\bf X}_{2}),$ (8)

where $\mathcal{R}_{\bf W}({\bf X}_{1},{\bf X}_{2})$ is defined as the
collection of all $(R_{1},R_{2})$ satisfying that

$\displaystyle 0\leq R_{1}$ $\displaystyle\leq$
$\displaystyle\underline{I}({\bf X}_{1};{\bf Y}_{1}),$ (9) $\displaystyle
0\leq R_{2}$ $\displaystyle\leq$ $\displaystyle\underline{I}({\bf X}_{2};{\bf
Y}_{2}).$ (10)

To prove Theorem 1, we need the following lemmas.

###### Lemma 1

Let

$({\bf X}_{1}=\\{{X}_{1}^{n}\\}_{n=1}^{\infty},{\bf
X}_{2}=\\{{X}_{2}^{n}\\}_{n=1}^{\infty})$

be any channel input such that $({\bf X}_{1},{\bf X}_{2})\in S_{I}$. The
corresponding output via an interference channel ${\bf W}=\\{W^{n}\\}$ is
denoted by $({\bf Y}_{1}=\\{{Y}_{1}^{n}\\}_{n=1}^{\infty},{\bf
Y}_{2}=\\{{Y}_{2}^{n}\\}_{n=1}^{\infty})$. Then, for any fixed $M_{n}^{(1)}$
and $M_{n}^{(2)}$, there exists an
$(n,M_{n}^{(1)},M_{n}^{(2)},\varepsilon_{n}^{(1)},\varepsilon_{n}^{(2)})$ code
satisfying that

$\varepsilon_{n}^{(1)}+\varepsilon_{n}^{(2)}\leq{\rm
Pr}\\{T^{c}_{n}(1)\\}+{\rm Pr}\\{T^{c}_{n}(2)\\}+2e^{-n\gamma},$ (11)

where

$\begin{array}[]{l}T_{n}(1)=\\{({\bf x}_{1},{\bf
y}_{1})|\frac{1}{n}\log\frac{P_{Y_{1}^{n}|X_{1}^{n}}({\bf y}_{1}|{\bf
x}_{1})}{P_{{Y}_{1}^{n}}({\bf y}_{1})}>\frac{1}{n}\log
M_{n}^{(1)}+\gamma\\},\\\ T_{n}(2)=\\{({\bf x}_{2},{\bf
y}_{2})|\frac{1}{n}\log\frac{P_{Y_{2}^{n}|X_{2}^{n}}({\bf y}_{2}|{\bf
x}_{2})}{P_{{Y}_{2}^{n}}({\bf y}_{2})}>\frac{1}{n}\log
M_{n}^{(2)}+\gamma\\}\end{array}$

and $\gamma>0$ is an arbitrarily small number.

###### Proof:

The proof is similar to that of [18, Lemma 3].

Codebook generation. Generate $M_{n}^{(1)}$ independent codewords ${\bf
x}_{1}(1),...,{\bf x}_{1}(M_{n}^{(1)})\in\mathcal{X}_{1}^{n}$ subject to the
probability distribution $P_{X_{1}^{n}}$. Similarly, generate $M_{n}^{(2)}$
independent codewords ${\bf x}_{2}(1),...,{\bf
x}_{2}(M_{n}^{(2)})\in\mathcal{X}_{2}^{n}$ subject to the probability
distribution $P_{X_{2}^{n}}$.

Encoding. To send message $i$, Sender 1 sends the codeword ${\bf x}_{1}(i)$.
Similarly, to send message $j$, Sender 2 sends ${\bf x}_{2}(j)$.

Decoding. Receiver 1 chooses the $i$ such that $({\bf x}_{1}(i),{\bf
y}_{1})\in T_{n}(1)$ if such $i$ exists and is unique. Similarly, Receiver 2
chooses the $j$ such that $({\bf x}_{2}(j),{\bf y}_{2})\in 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

$E_{1i}=\\{({\bf x}_{1}(i),{\bf y}_{1})\in T_{n}(1)\\},\,\,E_{2j}=\\{({\bf
x}_{2}(j),{\bf y}_{2})\in T_{n}(2)\\}.$

For Receiver 1, an error occurs if $({\bf x}_{1}(1),{\bf y}_{1})\notin
T_{n}(1)$ or $({\bf x}_{1}(i),{\bf y}_{1})\in T_{n}(1)$ for some $i\neq 1$.
Similarly, for Receiver 2, an error occurs if $({\bf x}_{2}(1),{\bf
y}_{2})\notin T_{n}(2)$ or $({\bf x}_{2}(j),{\bf y}_{2})\in T_{n}(2)$ for some
$j\neq 1$. So the ensemble average of the error probabilities of Decoder 1 and
Decoder 2 can be upper-bounded as follows:

$\begin{array}[]{l}\overline{{\varepsilon}_{n}^{(1)}+{\varepsilon}_{n}^{(2)}}=\overline{\varepsilon_{n}^{(1)}}+\overline{\varepsilon_{n}^{(2)}}\\\
\leq{\rm Pr}\\{E_{11}^{c}\\}+{\rm Pr}\\{\bigcup\limits_{i\neq 1}E_{1i}\\}+{\rm
Pr}\\{E_{21}^{c}\\}+{\rm Pr}\\{\bigcup\limits_{j\neq 1}E_{2j}\\}.\end{array}$

It can be seen that

$\begin{array}[]{ll}&{\rm Pr}\\{\bigcup\limits_{i\neq
1}E_{1i}\\}\leq\sum\limits_{i\neq 1}{\rm Pr}\\{E_{1i}\\}\\\
&=\sum\limits_{i\neq 1}{\rm Pr}\\{({\bf x}_{1}(i),{\bf y}_{1})\in
T_{n}(1)\\}\\\ &\stackrel{{\scriptstyle(a)}}{{=}}\sum\limits_{i\neq
1}\sum\limits_{({\bf x}_{1},{\bf y}_{1})\in T_{n}(1)}P_{X_{1}^{n}}({\bf
x}_{1})P_{Y_{1}^{n}}({\bf y}_{1})\\\
&\stackrel{{\scriptstyle(b)}}{{\leq}}\sum\limits_{i\neq 1}\sum\limits_{({\bf
x}_{1},{\bf y}_{1})\in T_{n}(1)}P_{X_{1}^{n}}({\bf
x}_{1})P_{Y_{1}^{n}|X_{1}^{n}}({\bf y}_{1}|{\bf
x}_{1})\frac{e^{-n\gamma}}{M_{n}^{(1)}}\\\ &\leq\sum\limits_{i\neq
1}\frac{e^{-n\gamma}}{M_{n}^{(1)}}=(M_{n}^{(1)}-1)\frac{e^{-n\gamma}}{M_{n}^{(1)}}\leq
e^{-n\gamma},\end{array}$

where $(a)$ follows from the independence of ${\bf x}_{1}(i)~{}(i\neq 1)$ and
${\bf y}_{1}$ and $(b)$ follows from the definition of $T_{n}(1)$. Similarly,
we obtain

${\rm Pr}\\{\bigcup\limits_{j\neq 1}E_{2j}\\}\leq e^{-n\gamma}.$ (12)

Combining all inequalities above, we can see that there must exist at least
one $(n,M_{n}^{(1)},M_{n}^{(2)},\varepsilon_{n}^{(1)},\varepsilon_{n}^{(2)})$
code satisfying (11). ∎

###### Lemma 2

For all $n$, any
$(n,M_{n}^{(1)},M_{n}^{(2)},\varepsilon_{n}^{(1)},\varepsilon_{n}^{(2)})$ code
satisfies that

$\begin{array}[]{l}\varepsilon_{n}^{(1)}\geq{\rm
Pr}\\{\frac{1}{n}\log\frac{P_{Y_{1}^{n}|X_{1}^{n}}({Y}_{1}^{n}|{X}_{1}^{n})}{P_{{Y}_{1}^{n}}({Y}_{1}^{n})}\leq\frac{1}{n}\log
M_{n}^{(1)}-\gamma\\}-e^{-n\gamma},\\\ \varepsilon_{n}^{(2)}\geq{\rm
Pr}\\{\frac{1}{n}\log\frac{P_{Y_{2}^{n}|X_{2}^{n}}({Y}_{2}^{n}|{X}_{2}^{n})}{P_{{Y}_{2}^{n}}({Y}_{2}^{n})}\leq\frac{1}{n}\log
M_{n}^{(2)}-\gamma\\}-e^{-n\gamma},\end{array}$ (13)

for every $\gamma>0$, where $X_{1}^{n}~{}({\rm resp.,}\,X_{2}^{n})$ places
probability mass $1/M_{n}^{(1)}~{}({\rm resp.,}\,1/M_{n}^{(2)})$ on each
codeword for Encoder 1 (resp., Encoder 2) and (3), (6), (7) hold.

###### Proof:

The proof is similar to that of [18, Lemma 4]. By using the relation

$\frac{P_{Y_{1}^{n}|X_{1}^{n}}({\bf y}_{1}|{\bf x}_{1})}{P_{{Y}_{1}^{n}}({\bf
y}_{1})}=\frac{P_{X_{1}^{n}|Y_{1}^{n}}({\bf x}_{1}|{\bf
y}_{1})}{P_{{X}_{1}^{n}}({\bf x}_{1})}$

and noticing that $P_{{X}_{1}^{n}}({\bf x}_{1})=\frac{1}{M_{n}^{(1)}}$, we can
rewrite the first term on the right-hand side of the first inequality of (13)
as

${\rm Pr}\\{P_{X_{1}^{n}|Y_{1}^{n}}(X_{1}^{n}|Y_{1}^{n})\leq e^{-n\gamma}\\}.$

By setting

$L_{n}=\\{({\bf x}_{1},{\bf y}_{1})|P_{X_{1}^{n}|Y_{1}^{n}}({\bf x}_{1}|{\bf
y}_{1})\leq e^{-n\gamma}\\},$

the first inequality of (13) can be expressed as

${\rm Pr}\\{L_{n}\\}\leq\varepsilon_{n}^{(1)}+e^{-n\gamma}.$ (14)

In order to prove this inequality, we set

$\mathcal{A}_{i}=\\{{\bf
y}_{1}\in\mathcal{Y}_{1}^{n}|P_{X_{1}^{n}|Y_{1}^{n}}({\bf x}_{1}(i)|{\bf
y}_{1})\leq e^{-n\gamma}\\}.$

It can be seen that

$\begin{array}[]{l}{\rm
Pr}\\{L_{n}\\}=\sum\limits_{i=1}^{M_{n}^{(1)}}P_{X_{1}^{n}Y_{1}^{n}}({\bf
x}_{1}(i),\mathcal{A}_{i})\\\
=\sum\limits_{i=1}^{M_{n}^{(1)}}P_{X_{1}^{n}Y_{1}^{n}}({\bf
x}_{1}(i),\mathcal{A}_{i}\bigcap\mathcal{B}_{1i})+\sum\limits_{i=1}^{M_{n}^{(1)}}P_{X_{1}^{n}Y_{1}^{n}}({\bf
x}_{1}(i),\mathcal{A}_{i}\bigcap\mathcal{B}_{1i}^{c})\\\
\leq\sum\limits_{i=1}^{M_{n}^{(1)}}P_{X_{1}^{n}Y_{1}^{n}}({\bf
x}_{1}(i),\mathcal{A}_{i}\bigcap\mathcal{B}_{1i})+\sum\limits_{i=1}^{M_{n}^{(1)}}P_{X_{1}^{n}Y_{1}^{n}}({\bf
x}_{1}(i),\mathcal{B}_{1i}^{c})\\\
=\sum\limits_{i=1}^{M_{n}^{(1)}}\sum\limits_{{\bf
y}_{1}\in\mathcal{A}_{i}\bigcap\mathcal{B}_{1i}}P_{X_{1}^{n}Y_{1}^{n}}({\bf
x}_{1}(i),{\bf y}_{1})+\varepsilon_{n}^{(1)}\\\
=\sum\limits_{i=1}^{M_{n}^{(1)}}\sum\limits_{{\bf
y}_{1}\in\mathcal{A}_{i}\bigcap\mathcal{B}_{1i}}P_{X_{1}^{n}|Y_{1}^{n}}({\bf
x}_{1}(i)|{\bf y}_{1})P_{Y_{1}^{n}}({\bf y}_{1})+\varepsilon_{n}^{(1)}\\\
\stackrel{{\scriptstyle(a)}}{{\leq}}e^{-n\gamma}\sum\limits_{i=1}^{M_{n}^{(1)}}\sum\limits_{{\bf
y}_{1}\in\mathcal{B}_{1i}}P_{Y_{1}^{n}}({\bf y}_{1})+\varepsilon_{n}^{(1)}\\\
=e^{-n\gamma}P_{Y_{1}^{n}}(\bigcup\limits_{i=1}^{M_{n}^{(1)}}\mathcal{B}_{1i})+\varepsilon_{n}^{(1)}\leq
e^{-n\gamma}+\varepsilon_{n}^{(1)},\end{array}$

where $\mathcal{B}_{1i}$ is the decoding region corresponding to codeword
${\bf x}_{1}(i)$ and $(a)$ follows from the definition of $\mathcal{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:

1) To prove that an arbitrary rate pair $(R_{1},R_{2})$ satisfying (9) and
(10) is achievable, we define

$M_{n}^{(1)}=e^{n(R_{1}-2\gamma)}\,\,\,{\rm
and}\,\,\,M_{n}^{(2)}=e^{n(R_{2}-2\gamma)}$

for an arbitrarily small constant $\gamma>0$. Lemma 1 guarantees the existence
of an
$(n,M_{n}^{(1)},M_{n}^{(2)},\varepsilon_{n}^{(1)},\varepsilon_{n}^{(2)})$ code
satisfying

$\begin{array}[]{ll}\varepsilon_{n}^{(1)}+\varepsilon_{n}^{(2)}&\leq{\rm
Pr}\\{\frac{1}{n}\log\frac{P_{Y_{1}^{n}|X_{1}^{n}}({Y}_{1}^{n}|{X}_{1}^{n})}{P_{{Y}_{1}^{n}}({Y}_{1}^{n})}\leq
R_{1}-\gamma\\}\\\ &\,\,\,\,\,\,+{\rm
Pr}\\{\frac{1}{n}\log\frac{P_{Y_{2}^{n}|X_{2}^{n}}({Y}_{2}^{n}|{X}_{2}^{n})}{P_{{Y}_{2}^{n}}({Y}_{2}^{n})}\leq
R_{2}-\gamma\\}+2e^{-n\gamma}\\\ &\leq{\rm
Pr}\\{\frac{1}{n}\log\frac{P_{Y_{1}^{n}|X_{1}^{n}}({Y}_{1}^{n}|{X}_{1}^{n})}{P_{{Y}_{1}^{n}}({Y}_{1}^{n})}\leq\underline{I}({\bf
X}_{1};{\bf Y}_{1})-\gamma\\}\\\ &\,\,\,\,\,\,+{\rm
Pr}\\{\frac{1}{n}\log\frac{P_{Y_{2}^{n}|X_{2}^{n}}({Y}_{2}^{n}|{X}_{2}^{n})}{P_{{Y}_{2}^{n}}({Y}_{2}^{n})}\leq\underline{I}({\bf
X}_{2};{\bf Y}_{2})-\gamma\\}+2e^{-n\gamma}.\end{array}$

From the definition of the spectral inf-mutual information rate, we have

$\lim_{n\rightarrow\infty}\varepsilon_{n}^{(1)}=0\,\,\,{\rm
and}\,\,\,\lim_{n\rightarrow\infty}\varepsilon_{n}^{(2)}=0.$

2) Suppose that a rate pair $(R_{1},R_{2})$ is achievable. Then, for any
constant $\gamma>0$, there exists an
$(n,M_{n}^{(1)},M_{n}^{(2)},\varepsilon_{n}^{(1)},\varepsilon_{n}^{(2)})$ code
satisfying

$\frac{\log M_{n}^{(1)}}{n}\geq R_{1}-\gamma\,\,\,{\rm and}\,\,\,\frac{\log
M_{n}^{(2)}}{n}\geq R_{2}-\gamma$ (15)

for all sufficiently large $n$ and

$\lim_{n\rightarrow\infty}\varepsilon_{n}^{(1)}=0\,\,\,{\rm
and}\,\,\,\lim_{n\rightarrow\infty}\varepsilon_{n}^{(2)}=0.$

From Lemma 2, we get

$\begin{array}[]{l}\varepsilon_{n}^{(1)}\geq{\rm
Pr}\\{\frac{1}{n}\log\frac{P_{Y_{1}^{n}|X_{1}^{n}}({Y}_{1}^{n}|{X}_{1}^{n})}{P_{{Y}_{1}^{n}}({Y}_{1}^{n})}\leq
R_{1}-2\gamma\\}-e^{-n\gamma}\\\ \varepsilon_{n}^{(2)}\geq{\rm
Pr}\\{\frac{1}{n}\log\frac{P_{Y_{2}^{n}|X_{2}^{n}}({Y}_{2}^{n}|{X}_{2}^{n})}{P_{{Y}_{2}^{n}}({Y}_{2}^{n})}\leq
R_{2}-2\gamma\\}-e^{-n\gamma}\end{array}.$ (16)

Taking the limits as $n\rightarrow\infty$ on both sides, we have

$\begin{array}[]{l}\lim\limits_{n\rightarrow\infty}{\rm
Pr}\\{\frac{1}{n}\log\frac{P_{Y_{1}^{n}|X_{1}^{n}}({Y}_{1}^{n}|{X}_{1}^{n})}{P_{{Y}_{1}^{n}}({Y}_{1}^{n})}\leq
R_{1}-2\gamma\\}=0\\\ \lim\limits_{n\rightarrow\infty}{\rm
Pr}\\{\frac{1}{n}\log\frac{P_{Y_{2}^{n}|X_{2}^{n}}({Y}_{2}^{n}|{X}_{2}^{n})}{P_{{Y}_{2}^{n}}({Y}_{2}^{n})}\leq
R_{2}-2\gamma\\}=0\end{array}.$ (17)

From the definitions of $\underline{I}({\bf X}_{1};{\bf Y}_{1})$ and
$\underline{I}({\bf X}_{2};{\bf Y}_{2})$, we can see that
$R_{1}-2\gamma\leq\underline{I}({\bf X}_{1};{\bf Y}_{1})$ and
$R_{2}-2\gamma\leq\underline{I}({\bf X}_{2};{\bf Y}_{2})$, which completes the
proof since $\gamma$ is arbitrary.

∎

###  III-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

$W^{n}({\bf y}_{1},{\bf y}_{2}|{\bf x}_{1},{\bf
x}_{2})=\prod_{i=1}^{n}W(y_{1,i},y_{2,i}|x_{1,i},x_{2,i});$

  * 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

$\displaystyle\underline{I}({\bf X}_{1};{\bf Y}_{1})$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{1}{n}I({X}_{1}^{n};{Y}_{1}^{n}),$
(18) $\displaystyle\underline{I}({\bf X}_{2};{\bf Y}_{2})$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{1}{n}I({X}_{2}^{n};{Y}_{2}^{n}),$
(19)

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 ${\bf x}_{1}$ can be specified by a
trellis $\mathcal{T}_{1}$ as follows.

  * •

Both the left and right states are selected from the set
$\mathcal{S}_{1}=\\{0,1,...,|\mathcal{S}_{1}|-1\\}$;

  * •

Each branch is represented by a three-tuple
$b=(s_{1}^{-}(b),x_{1}(b),s_{1}^{+}(b))$, where $s_{1}^{-}(b)$ is the left
state, $s_{1}^{+}(b)$ is the right state, and the symbol
$x_{1}(b)\in\mathcal{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}\in\mathcal{S}_{1}$. If at
time $t-1~{}(t>0)$, the source is in the state $s_{1,t-1}\in\mathcal{S}_{1}$,
then at time $t~{}(t>0)$, the source generates a symbol
$x_{1,t}\in\mathcal{X}_{1}$ according to the conditional probability
$P(x_{1,t}|s_{1,t-1})$ and goes into a state $s_{1,t}\in\mathcal{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

$P(x_{1,1},x_{1,2},...,x_{1,n}|s_{1,0})=\prod\limits_{t=1}^{n}P(x_{1,t}|s_{1,t-1}).$

Similarly, we can represent ${\bf x}_{2}$ by a trellis $\mathcal{T}_{2}$ with
the state set $\mathcal{S}_{2}=\\{0,1,...,|\mathcal{S}_{2}|-1\\}$. Each branch
is denoted by $b=(s_{2}^{-}(b),x_{2}(b),s_{2}^{+}(b))$, where $s_{2}^{-}(b)$
is the left state, $s_{2}^{+}(b)$ is the right state and the symbol
$x_{2}(b)\in\mathcal{X}_{2}$ is the associated label. Assume that source ${\bf
x}_{2}$ starts from the state $s_{2,0}\in\mathcal{S}_{2}$. If at time
$t-1~{}(t>0)$, the source is in the state $s_{2,t-1}\in\mathcal{S}_{2}$, then
at time $t~{}(t>0)$, the source generates a symbol $x_{2,t}\in\mathcal{X}_{2}$
according to the conditional probability $P(x_{2,t}|s_{2,t-1})$ and goes into
a state $s_{2,t}\in\mathcal{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})=\prod\limits_{t=1}^{n}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\limits_{n\rightarrow\infty}\frac{1}{n}I({X}_{1}^{n};{Y}_{1}^{n})$, while
$\lim\limits_{n\rightarrow\infty}\frac{1}{n}I({X}_{2}^{n};{Y}_{2}^{n})$ can be
estimated similarly. Specifically, we can express the limit as

$\lim_{n\rightarrow\infty}\frac{1}{n}I({X}_{1}^{n};{Y}_{1}^{n})=\lim_{n\rightarrow\infty}\frac{1}{n}H(Y_{1}^{n})-\lim_{n\rightarrow\infty}\frac{1}{n}H(Y_{1}^{n}|X_{1}^{n}),$
(20)

where $\lim\limits_{n\rightarrow\infty}\frac{1}{n}H(Y_{1}^{n})$ and
$\lim\limits_{n\rightarrow\infty}\frac{1}{n}H(Y_{1}^{n}|X_{1}^{n})$ can be
estimated by similar methods111For continuous ${\bf y}_{1}$, the computations
of $\lim\limits_{n\rightarrow\infty}\frac{1}{n}h(Y_{1}^{n})$ and
$\lim\limits_{n\rightarrow\infty}\frac{1}{n}h(Y_{1}^{n}|X_{1}^{n})$ can be
implemented by substituting pdf for pmf.. As an example, we show how to
compute $\lim\limits_{n\rightarrow\infty}\frac{1}{n}H(Y_{1}^{n})$. According
to the Shannon-McMillan-Breiman theorem [27], it can be seen that, with
probability 1,

$\lim_{n\rightarrow\infty}-\frac{1}{n}\log
P(y_{1}^{n})=\lim_{n\rightarrow\infty}\frac{1}{n}H(Y_{1}^{n}),$

where $y_{1}^{n}$ stands for $(y_{1,1},y_{1,2},...,y_{1,n})$. Then evaluating
$\lim\limits_{n\rightarrow\infty}\frac{1}{n}H(Y_{1}^{n})$ is converted to
computing

$\lim_{n\rightarrow\infty}-\frac{1}{n}\log
P(y_{1}^{n})\approx-\frac{1}{n}\log\left(\prod_{t=1}^{n}P(y_{1,t}|y_{1}^{t-1})\right)=-\frac{1}{n}\sum_{t=1}^{n}\log
P(y_{1,t}|y_{1}^{t-1})$

for a sufficiently long typical sequence $y_{1}^{n}$. Here, the key is to
compute the conditional probabilities $P(y_{1,t}|y_{1}^{t-1})$ for all $t$.
Since both ${\bf y}_{1}$ and ${\bf 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
$\mathcal{S}=\mathcal{S}_{1}\times\mathcal{S}_{2}$, where “$\times$” denotes
Cartesian product.

  * •

Each branch is represented by a four-tuple
$b=(s^{-}(b),x_{1}(b),x_{2}(b),s^{+}(b))$, where
$s^{-}(b)=(s_{1}^{-}(b),s_{2}^{-}(b))$ is the left state,
$s^{+}(b)=(s_{1}^{+}(b),s_{2}^{+}(b))$ is the right state. Then
$x_{1}(b)\in\mathcal{X}_{1}$ and $x_{2}(b)\in\mathcal{X}_{2}$ are the
associated labels in branch $b$ such that
$(s_{1}^{-}(b),x_{1}(b),s_{1}^{+}(b))$ and
$(s_{2}^{-}(b),x_{2}(b),s_{2}^{+}(b))$ are branches in $\mathcal{T}_{1}$ and
$\mathcal{T}_{2}$, respectively.

  * •

At time $t=0$, the sources start from state
$s_{0}=(s_{1,0},s_{2,0})\in\mathcal{S}$. If at time $t-1~{}(t>0)$, the sources
are in the state $s_{t-1}=(s_{1,t-1},s_{2,t-1})\in\mathcal{S}$, then at time
$t~{}(t>0)$, the sources generate symbols
$(x_{1,t}\in\mathcal{X}_{1},x_{2,t}\in\mathcal{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})\in\mathcal{S}_{2}$ such that
$(s_{t-1},x_{1,t},x_{2,t},s_{t})$ is a branch.

Given the received sequence ${\bf 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

$\displaystyle\rho(b_{t})$ $\displaystyle\overset{\triangle}{=}$
$\displaystyle P(b_{t}|s_{t-1})P(y_{1,t}|x_{1,t}x_{2,t})$ (21)
$\displaystyle=$ $\displaystyle
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}),$ (22)

In the computation of
$\lim\limits_{n\rightarrow\infty}\frac{1}{n}H(Y_{1}^{n}|X_{1}^{n})$, 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

$\displaystyle\gamma_{t}(s_{t-1},s_{t})$ $\displaystyle\overset{\triangle}{=}$
$\displaystyle P(s_{t},y_{1,t}|s_{t-1})$ (23) $\displaystyle=$
$\displaystyle\sum_{b_{t}:s^{-}(b_{t})=s_{t-1},s^{+}(b_{t})=s_{t}}\rho(b_{t}).$
(24)

  * •

Forward recursion variables: We define the _a posteriori_ probabilities

$\alpha_{t}(s_{t})\overset{\triangle}{=}P(s_{t}|y_{1}^{t}),\,\,\,t=0,1,...n.$
(25)

Then

$P(y_{1,t}|y_{1}^{t-1})=\sum_{s_{t-1},s_{t}}\alpha(s_{t-1})\gamma_{t}(s_{t-1},s_{t}),$
(26)

where the values of $\alpha_{t}(s_{t})$ can be computed recursively by

$\alpha_{t}(s_{t})=\frac{\sum_{s_{t-1}}\alpha_{t-1}(s_{t-1})\gamma_{t}(s_{t-1},s_{t})}{\sum_{s_{t-1},s_{t}}\alpha_{t-1}(s_{t-1})\gamma_{t}(s_{t-1},s_{t})}.$
(27)

In summary, the algorithm to estimate the entropy rate
$\lim\limits_{n\rightarrow\infty}\frac{1}{n}H(Y_{1}^{n})$ is described as
follows.

###### Algorithm 1

  1. 1.

Initializations: Choose a sufficiently large number $n$. Set the initial state
of the trellis to be $s_{0}=0$. The forward recursion variables are
initialized as $\alpha_{0}(s)=1$ if $s=0$ and otherwise $\alpha_{0}(s)=0$.

  2. 2.

Simulations for Sender 1: Generate a Markov sequence ${\bf
x}_{1}=(x_{1,1},x_{1,2},...,x_{1,n})$ according to the trellis
$\mathcal{T}_{1}$ of source ${\bf x}_{1}$.

  3. 3.

Simulations for Sender 2: Generate a Markov sequence ${\bf
x}_{2}=(x_{2,1},x_{2,2},...,x_{2,n})$ according to the trellis
$\mathcal{T}_{2}$ of source ${\bf x}_{2}$.

  4. 4.

Simulations for Receiver 1: Generate the received sequence ${\bf y}_{1}$
according to the transition probability $W^{n}({\bf y}_{1},{\bf y}_{2}|{\bf
x}_{1},{\bf x}_{2})$.

  5. 5.

Computations:

     * a)

For $t=1,2,...,n$ , compute the values of $P(y_{1,t}|y_{1}^{t-1})$ and
$\alpha_{t}(s_{t})$ recursively according to equations (26) and (27).

     * b)

Evaluate the entropy rate

$\lim_{n\rightarrow\infty}\frac{1}{n}H(Y_{1}^{n})=-\frac{1}{n}\sum_{t=1}^{n}\log
P(y_{1,t}|y_{1}^{t-1}).$

Similarly, we can evaluate the entropy rate
$\lim\limits_{n\rightarrow\infty}\frac{1}{n}H(Y_{1}^{n}|X_{1}^{n})$.
Therefore, we obtain the achievable rate $\underline{I}({\bf X}_{1};{\bf
Y}_{1})=\lim\limits_{n\rightarrow\infty}\frac{1}{n}I({X}_{1}^{n};{Y}_{1}^{n})$.

###  III-C Numerical Results

Figure 2: Symmetric Gaussian interference channel.

We consider the model as shown in Fig. 2, where the channel inputs ${\bf
x}_{1}(i)$ and ${\bf x}_{2}(j)$ are BPSK sequences with power constraints
$P_{1}$ and $P_{2}$, respectively; the additive noise ${\bf n}_{1}$ and ${\bf
n}_{2}$ are sequences of independent and identically distributed (i.i.d.)
standard Gaussian random variables; the channel outputs ${\bf y}_{1}$ and
${\bf y}_{2}$ are

$\displaystyle{\bf y}_{1}$ $\displaystyle=$ $\displaystyle{\bf
x}_{1}(i)+\sqrt{a}{\bf x}_{2}(j)+{\bf n}_{1},$ (28) $\displaystyle{\bf y}_{2}$
$\displaystyle=$ $\displaystyle{\bf x}_{2}(j)+\sqrt{a}{\bf x}_{1}(i)+{\bf
n}_{2}.$ (29)

We assume that ${\bf x}_{1}$ and ${\bf 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.

Fig. 3 shows the trellis representation of the signal model when Sender 1 uses
CcBPSK and Sender 2 uses UnBPSK. Fig. 4 shows the numerical results. There are
three rectangles, OECH, ODBG and OFAI, each of which is determined by a pair
of spectral inf-mutual information rates. Specifically, the rectangle OECH
corresponds to the case when both senders use UnBPSK as inputs; the rectangle
ODBG corresponds to the case when Sender 1 uses UnBPSK as input and Sender 2
uses CcBPSK as input; and the rectangle OFAI corresponds to the case when
Sender 1 uses CcBPSK as input and Sender 2 uses UnBPSK as input. The point “A”
can be achieved by a coding scheme, in which Sender 1 uses a binary linear
(coset) code concatenated with the convolutional code and Sender 2 uses a
binary linear code, and the point “B” can be achieved similarly; while the
points on the line “AB” can be achieved by time-sharing scheme. 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.

Figure 3: The trellis section of (CcBPSK, UnBPSK) with 32 branches. For each
branch $b$, $s^{-}(b)$ and $s^{+}(b)$ are the left state and the right state,
respectively; while the associated symbols $x_{1}(b)$ and $x_{2}(b)$ are the
transmitted signals at Sender 1 and Sender 2, respectively.
Figure 4: The evaluated achievable rate pairs of a specific GIFC, where
$P_{1}=P_{2}=7.0~{}{\rm dB}$ and $a=0.5$. The rectangle OECH with legend
“(UnBPSK, UnBPSK)” corresponds to the case when both senders use UnBPSK as
inputs; the rectangle ODBG with legend “(UnBPSK, CcBPSK)” corresponds to the
case when Sender 1 uses UnBPSK as input and Sender 2 uses CcBPSK as input; and
the rectangle OFAI with legend “(CcBPSK, UnBPSK)” corresponds to the case when
Sender 1 uses CcBPSK as input and Sender 2 uses UnBPSK as input.

##  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.

###  IV-A A Coding Scheme

We design a coding scheme using Kite codes222The 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].. Kite
codes are a class of low-density parity-check (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 ${\bf H}_{1}$) and
Sender 2 uses a Kite code (with a parity-check matrix ${\bf H}_{2}$)
concatenated with the convolutional code with the generator matrix

$G(D)=[1+D+D^{2}\,\,\,1+D^{2}].$

Figure 5: A coding scheme for the two-user GIFC.

_Encoding_ : For Sender 1, a binary sequence ${\bf
u}_{1}=(u_{1,1},u_{1,2},...,u_{1,L_{1}})$ of length $L_{1}$ is encoded by a
Kite code into a coded sequence ${\bf c}_{1}=(c_{1,1},c_{1,2},...,c_{1,N})$ of
length $N$. For Sender 2, a binary sequence ${\bf
u}_{2}=(u_{2,1},u_{2,2},...,u_{2,L_{2}})$ of length $L_{2}$ is firstly encoded
by a Kite code into a sequence ${\bf
v}_{2}=(v_{2,1},v_{2,2},...,v_{2,N^{\prime}})$ of length $N^{\prime}$ and then
the sequence ${\bf v}_{2}$ is encoded by the convolutional code with the
generator matrix $G(D)$ into a coded sequence ${\bf
c}_{2}=(c_{2,1},c_{2,2},...,c_{2,N})$ of length $N$.

_Modulation_ : The codewords ${\bf c}_{k}$ are mapped into the bipolar
sequences ${\bf x}_{k}=(x_{k,1},x_{k,2},...,x_{k,N})$ with
$x_{k,i}=\sqrt{P_{k}}(1-2c_{k,i})$ ($k=1,2$), where $P_{k}$ is the power. Then
we transmit ${\bf x}_{k}$ for $k=1,2$ over the interference channel.

_Decoding_ : After receiving ${\bf y}_{1}$, Receiver 1 attempts to recover the
transmitted message ${\bf u}_{1}$. Similarly, after receiving ${\bf y}_{2}$,
Receiver 2 attempts to recover the transmitted message ${\bf u}_{2}$. We will
consider several decoding algorithms in the next subsection to recover the
transmitted messages.

###  IV-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 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.333There is no
decoding scheme “Knowing the CC” for User 2 because User 1 has no
convolutional structure. All these decoding algorithms will be described as
_message processing/passing_ algorithms over normal graphs [32].

####  IV-B1 Message processing/passing algorithms over normal graphs

Figure 6: A normal graph of a general (sub)system.

As shown in Fig. 6, a normal graph consists of edges and vertices, which
represent variables and subsystem constraints, respectively. Let ${\bf
Z}=\left\\{Z_{1},Z_{2},\cdots,Z_{n}\right\\}$ be $n$ distinct random variables
that constitute a subsystem $S^{(0)}$. This subsystem can be represented by a
normal subgraph with edges representing ${\bf 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_{Z_{i}}^{(S^{(i)}\rightarrow S^{(0)})}(z)$ to denote the message
from $S^{(i)}$ to $S^{(0)}$. In particular, we use the notation
$P_{Z_{i}}^{(|\rightarrow S^{(0)})}(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
the likelihood function

$P_{Z_{i}}^{(S^{(0)}\rightarrow
S^{(i)})}(z)\propto\mbox{Pr}\left\\{S^{(0)}\mbox{ is satisfied
}|Z_{i}=z\right\\},z\in\mathcal{Z}$ (30)

by considering all the available messages as well as the system constraints.
We claim that $P_{Z_{i}}^{(S^{(0)}\rightarrow S^{(i)})}(z)$ is exactly the so-
called extrinsic message because the computation of the likelihood function is
irrelevant to the incoming message $P_{Z_{i}}^{(S^{(i)}\rightarrow
S^{(0)})}(z)$.

####  IV-B2 Knowing only the power of the interference

Figure 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 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. 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}\sim\mathcal{N}(0,aP_{2})$ for $j=1,2,\cdots,N$. Since
$N_{1,j}\sim\mathcal{N}(0,1)$ for $j=1,2,\cdots,N$, the decoding algorithm is
initialized by the initial messages as follows

$\begin{split}P_{C_{1,j}}^{(\Sigma_{1}\rightarrow
K_{1})}(c)=\mbox{Pr}\left\\{C_{1,j}=c|\mathbf{y_{1}},X_{2,j}\sim\mathcal{N}(0,aP_{2}),j=1,2,\cdots,N\right\\}\\\
\propto\frac{1}{\sqrt{2\pi(1+aP_{2})}}\exp\left\\{-\frac{[y_{1,j}-\sqrt{P_{1}}(1-2c)]^{2}}{2(1+aP_{2})}\right\\},c\in\mathbb{F}_{2}\end{split}$
(31)

for $j=1,2,\cdots,N$. Then the decoding algorithm uses SPA to compute
iteratively the extrinsic messages $P_{U_{1,i}}^{(K_{1}\rightarrow|)}$ and
$P_{C_{1,j}}^{(K_{1}\rightarrow\Sigma_{1})}$. Once these are done, we make the
following decisions:

$\hat{u}_{1,i}=\left\\{\begin{array}[]{ll}0,~{}\mbox{if}~{}P_{U_{1,i}}^{(|\rightarrow
K_{1})}(0)P_{U_{1,i}}^{(K_{1}\rightarrow|)}(0)>P_{U_{1,i}}^{(|\rightarrow
K_{1})}(1)P_{U_{1,i}}^{(K_{1}\rightarrow|)}(1),\\\
1,~{}\mbox{otherwise}.\end{array}\right.$ (32)

$\hat{c}_{1,j}=\left\\{\begin{array}[]{ll}0,~{}\mbox{if}~{}P_{C_{1,j}}^{(\Sigma_{1}\rightarrow
K_{1})}(0)P_{C_{1,j}}^{(K_{1}\rightarrow\Sigma_{1})}(0)>P_{C_{1,j}}^{(\Sigma_{1}\rightarrow
K_{1})}(1)P_{C_{1,j}}^{(K_{1}\rightarrow\Sigma_{1})}(1),\\\
1,~{}\mbox{otherwise}.\end{array}\right.$ (33)

for $i=1,2,\cdots,L_{1}$ and $j=1,2,\cdots,N$. The details about the decoding
algorithm are shown as below.

######  Algorithm 2 (“knowing only the power of the interference”)

  * •

Initialization:

    1. 1.

Initialize $P_{U_{1,i}}^{(|\rightarrow K_{1})}(u)=\frac{1}{2}$ for
$i=1,2,\cdots,L_{1}$ and $u\in\mathbb{F}_{2}$.

    2. 2.

Compute $P_{C_{1,j}}^{(\Sigma_{1}\rightarrow K_{1})}(c)$ for $j=1,2,\cdots,N$
and $c\in\mathbb{F}_{2}$ according to (31).

    3. 3.

Set a maximum iteration number $J$ and iteration variable $j=1$.

  * •

Repeat while $j\leq J$:

    1. 1.

Compute extrinsic messages $P_{U_{1,i}}^{(K_{1}\rightarrow|)}$ and
$P_{C_{1,j}}^{(K_{1}\rightarrow\Sigma_{1})}$ for $i=1,2,\cdots,L_{1}$ and
$j=1,2,\cdots,N$ using SPA.

    2. 2.

Make decisions according to (32) and (33). Denote
${\bf\hat{u}}_{1}=\left(\hat{u}_{1,1},\hat{u}_{1,2},\cdots,\hat{u}_{1,L_{1}}\right)$
and
${\bf\hat{c}}_{1}=\left(\hat{c}_{1,1},\hat{c}_{1,2},\cdots,\hat{c}_{1,N}\right)$.

    3. 3.

Compute the syndrome ${\bf S}_{1}={\bf\hat{c}}_{1}\cdot{\bf H}_{1}^{T}$. If
${\bf S}_{1}=\mathbf{0}$, output ${\bf\hat{u}}_{1}$ and ${\bf\hat{c}}_{1}$ and
exit the iteration.

    4. 4.

Set $j=j+1$. If ${\bf S}_{1}\neq\mathbf{0}$ and $j>J$, report a decoding
failure.

  * •

End decoding.

####  IV-B3 Knowing the signaling of the interference

The decoding algorithm for this scheme is almost the same as Algorithm 2, see
Fig. 7. The difference is that $X_{2,j}\sim\mathcal{B}(1/2)$ (Bernoulli-1/2
distribution444Strictly speaking, $X_{2,j}$ is a shift/scaling version of
$\mathcal{B}(1/2)$.) for $j=1,2,\cdots,N$. So the computation of
$P_{C_{1,j}}^{(\Sigma_{1}\rightarrow K_{1})}(c)$ is changed into

$\begin{split}P_{C_{1,j}}^{(\Sigma_{1}\rightarrow
K_{1})}(c)=\mbox{Pr}\left\\{C_{1,j}=c|\mathbf{y_{1}},X_{2,j}\sim\mathcal{B}(1/2),j=1,2,\cdots,N\right\\}\\\
\propto\frac{1}{2}\frac{1}{\sqrt{2\pi}}\exp\left\\{-\frac{\left[y_{1,j}-\sqrt{P_{1}}(1-2c)-\sqrt{aP_{2}}\right]^{2}}{2}\right\\}\\\
+\frac{1}{2}\frac{1}{\sqrt{2\pi}}\exp\left\\{-\frac{\left[y_{1,j}-\sqrt{P_{1}}(1-2c)+\sqrt{aP_{2}}\right]^{2}}{2}\right\\},\\\
c\in\mathbb{F}_{2}\end{split}$ (34)

Then the decoding algorithm of “knowing the signaling of the interference” can
be shown as below.

######  Algorithm 3 (“knowing the signaling of the interference”)

  * •

Initialization:

    1. 1.

Initialize $P_{U_{1,i}}^{(|\rightarrow K_{1})}(u)=\frac{1}{2}$ for
$i=1,2,\cdots,L_{1}$ and $u\in\mathbb{F}_{2}$.

    2. 2.

Compute $P_{C_{1,j}}^{(\Sigma_{1}\rightarrow K_{1})}(c)$ for $j=1,2,\cdots,N$
and $c\in\mathbb{F}_{2}$ according to (34).

    3. 3.

Set a maximum iteration number $J$ and iteration variable $j=1$.

  * •

Repeat while $j\leq J$:

    1. 1.

Compute extrinsic messages $P_{U_{1,i}}^{(K_{1}\rightarrow|)}$ and
$P_{C_{1,j}}^{(K_{1}\rightarrow\Sigma_{1})}$ for $i=1,2,\cdots,L_{1}$ and
$j=1,2,\cdots,N$ using SPA.

    2. 2.

Make decisions according to (32) and (33), respectively.

    3. 3.

Compute the syndrome ${\bf S}_{1}={\bf\hat{c}}_{1}\cdot{\bf H}_{1}^{T}$. If
${\bf S}_{1}=\mathbf{0}$, output ${\bf\hat{u}}_{1}$ and ${\bf\hat{c}}_{1}$ and
exit the iteration.

    4. 4.

Set $j=j+1$. If ${\bf S}_{1}\neq\mathbf{0}$ and $j>J$, report a decoding
failure.

  * •

End decoding.

####  IV-B4 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. Actually, the vertex $T_{1}$ is a
combination of three subsystems, convolutional encoder, modulation and GIFC
constraint, which can be specified by a trellis $\mathcal{T}$ with parallel
branches [15]. Therefore, the BCJR algorithm can be used to compute the
extrinsic messages $P_{C_{1,j}}^{(T_{1}\rightarrow K_{1})}(c)$ for
$j=1,2,\cdots,N$ over the trellis $\mathcal{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,\cdots,N^{\prime}$) 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 into

$\hat{c}_{1,j}=\left\\{\begin{array}[]{ll}0,~{}\mbox{if}~{}P_{C_{1,j}}^{(T_{1}\rightarrow
K_{1})}(0)P_{C_{1,j}}^{(K_{1}\rightarrow
T_{1})}(0)>P_{C_{1,j}}^{(T_{1}\rightarrow
K_{1})}(1)P_{C_{1,j}}^{(K_{1}\rightarrow T_{1})}(1),\\\
1,~{}\mbox{otherwise},\end{array}\right.$ (35)

for $j=1,2,\cdots,N$. These two decoding procedures are described in Algorithm
4 and Algorithm 5, respectively.

######  Algorithm 4 (BCJR-once)

  * •

Initialization:

    1. 1.

Initialize pmf $P_{C_{1,j}}^{(K_{1}\rightarrow
T_{1})}\left(c\right)=\frac{1}{2}$ and $P_{C_{2,j}}^{(|\rightarrow
T_{1})}\left(c\right)=\frac{1}{2}$ for $j=1,2,\cdots,N,c\in\mathbb{F}_{2}$ and
$P_{V_{2,k}}^{(|\rightarrow T_{1})}\left(v\right)=\frac{1}{2}$ for
$k=1,2,\cdots,N^{\prime},v\in\mathbb{F}_{2}$.

    2. 2.

Compute extrinsic messages $P_{C_{1,j}}^{(T_{1}\rightarrow
K_{1})}\left(c\right)$ for $j=1,2,\cdots,N$, $c\in\mathbb{F}_{2}$ using BCJR
algorithm over the parallel branch trellis $\mathcal{T}$.

    3. 3.

Set a maximum iteration number $J$ and iteration variable $j=1$.

  * •

Repeat while $j\leq J$:

    1. 1.

Compute extrinsic messages $P_{U_{1,i}}^{(K_{1}\rightarrow|)}$ and
$P_{C_{1,j}}^{(K_{1}\rightarrow T_{1})}$ for $i=1,2,\cdots,L_{1}$ and
$j=1,2,\cdots,N$ using SPA.

    2. 2.

Make decisions according to (32) and (35).

    3. 3.

Compute the syndrome ${\bf S}_{1}={\bf\hat{c}}_{1}\cdot{\bf H}_{1}^{T}$. If
${\bf S}_{1}=\mathbf{0}$, output ${\bf\hat{u}}_{1}$ and ${\bf\hat{c}}_{1}$ and
exit the iteration.

    4. 4.

Set $j=j+1$. If ${\bf S}_{1}\neq\mathbf{0}$ and $j>J$, report a decoding
failure.

  * •

End Decoding

######  Algorithm 5 (BCJR-repeat)

  * •

Initialization:

    1. 1.

Initialize pmf $P_{C_{1,j}}^{(K_{1}\rightarrow
T_{1})}\left(c\right)=\frac{1}{2}$ and $P_{C_{2,j}}^{(|\rightarrow
T_{1})}\left(c\right)=\frac{1}{2}$ for $j=1,2,\cdots,N,c\in\mathbb{F}_{2}$ and
$P_{V_{2,k}}^{(|\rightarrow T_{1})}\left(v\right)=\frac{1}{2}$ for
$k=1,2,\cdots,N^{\prime},v\in\mathbb{F}_{2}$.

    2. 2.

Set a maximum iteration number $J$ and iteration variable $j=1$.

  * •

Repeat while $j\leq J$:

    1. 1.

Compute extrinsic messages $P_{C_{1,j}}^{(T_{1}\rightarrow
K_{1})}\left(c\right)$ for $j=1,2,\cdots,N$, $c\in\mathbb{F}_{2}$ using BCJR
algorithm over the parallel branch trellis $\mathcal{T}$.

    2. 2.

Compute extrinsic messages $P_{U_{1,i}}^{(K_{1}\rightarrow|)}$ and
$P_{C_{1,j}}^{(K_{1}\rightarrow T_{1})}$ for $i=1,2,\cdots,L_{1}$ and
$j=1,2,\cdots,N$ using SPA.

    3. 3.

Make decisions according to (32) and (35).

    4. 4.

Compute the syndrome ${\bf S}_{1}={\bf\hat{c}}_{1}\cdot{\bf H}_{1}^{T}$. If
${\bf S}_{1}=\mathbf{0}$, output ${\bf\hat{u}}_{1}$ and ${\bf\hat{c}}_{1}$ and
exit the iteration.

    5. 5.

Set $j=j+1$. If ${\bf S}_{1}\neq\mathbf{0}$ and $j>J$, report a decoding
failure.

  * •

End Decoding

####  IV-B5 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. Since knowing the whole structure of the interference, Receiver 1 can
decode iteratively utilizing the structure of both users. Using the BCJR
algorithm, $P_{C_{1,j}}^{(T_{1}\rightarrow K_{1})}\left(c\right)$ and
$P_{V_{2,k}}^{(T_{1}\rightarrow K_{2})}\left(v\right)$ are computed
simultaneously over the parallel branch trellis $\mathcal{T}$. The iterative
decoding algorithm is presented in Algorithm 6.

######  Algorithm 6 (“knowing the whole structure”)

  * •

Initialization:

    1. 1.

Initialize pmf $P_{C_{1,j}}^{(K_{1}\rightarrow
T_{1})}\left(c\right)=\frac{1}{2}$ and $P_{C_{2,j}}^{(|\rightarrow
T_{1})}\left(c\right)=\frac{1}{2}$ for $j=1,2,\cdots,N,c\in\mathbb{F}_{2}$ and
$P_{V_{2,k}}^{(K_{2}\rightarrow T_{1})}\left(v\right)=\frac{1}{2}$ for
$k=1,2,\cdots,N^{\prime},v\in\mathbb{F}_{2}$.

    2. 2.

Set a maximum iteration number $J$ and iteration variable $j=1$.

  * •

Repeat while $j\leq J$:

    1. 1.

Compute extrinsic messages $P_{C_{1,j}}^{(T_{1}\rightarrow
K_{1})}\left(c\right)$ for $j=1,2,\cdots,N$, $c\in\mathbb{F}_{2}$ and
$P_{V_{2,k}}^{(T_{1}\rightarrow K_{2})}\left(v\right)$ for
$k=1,2,\cdots,N^{\prime}$, $v\in\mathbb{F}_{2}$ using BCJR algorithm over the
parallel branch trellis $\mathcal{T}$.

    2. 2.

Compute extrinsic messages $P_{U_{1,i}}^{(K_{1}\rightarrow|)}$ and
$P_{C_{1,j}}^{(K_{1}\rightarrow T_{1})}$ for $i=1,2,\cdots,L_{1}$ and
$j=1,2,\cdots,N$ using SPA.

    3. 3.

Compute extrinsic messages $P_{V_{2,k}}^{(K_{2}\rightarrow
T_{1})}\left(v\right)$ for $k=1,2,\cdots,N^{\prime},v\in\mathbb{F}_{2}$ using
SPA.

    4. 4.

Make decisions according to (32) and (35).

    5. 5.

Compute the syndrome ${\bf S}_{1}={\bf\hat{c}}_{1}\cdot{\bf H}_{1}^{T}$. If
${\bf S}_{1}=\mathbf{0}$, output ${\bf\hat{u}}_{1}$ and ${\bf\hat{c}}_{1}$ and
exit the iteration.

    6. 6.

Set $j=j+1$. If ${\bf S}_{1}\neq\mathbf{0}$ and $j>J$, report a decoding
failure.

  * •

End Decoding

###  IV-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 IV-C. In these two figures, we let the power constraints of two senders
be same, that is, $P_{1}\equiv 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 “BCJR-once”, “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.

[!t] Parameters of the BER performance simulations Parameters Values Square of
interference coefficient $a$ 0.5 Maximum iteration number $J$ 200 Kite Code of
Sender 1 $N=10000,L_{1}=8782$ Kite Code of Sender 2
$N^{\prime}=5000,L_{2}=4862$ Generator matrix $G(D)$
$[1+D+D^{2}\,\,\,1+D^{2}]$ Code rate pair $\left(R_{1},R_{2}\right)$
$\left(0.8782,0.4862\right)$

Figure 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”.
Figure 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”.

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 code rate pairs are listed in TABLE IV-C, 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.

[!t] Parameters of the simulations for different code rate pairs. 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^{\prime}$ of Kite Code of Sender 2 $5000$ Generator matrix $G(D)$
$[1+D+D^{2}\,\,\,1+D^{2}]$ Step length $100$ Range of message length $L_{1}$
$7100\sim 8800$ Range of message length $L_{2}$ $4000\sim 4900$

Figure 10: Error performance of two users with different code rate pairs
$(R_{1},R_{2})$. Blue plane represents BER level, green surface stands for the
error performance of Receiver 1 and red surface stands for the error
performance of Receiver 2.

##  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.

## References

  * [1] C. E. Shannon, “Two-way communication channels,” in _Forth Berkeley Symp. on Math. Statist. and Prob._ , J. Neyman, Ed., vol. 1. Statist. Lab. of the University of California, Berkely: University of California Press, Jun. 20 - Jul. 30 1961, pp. 611–644.
  * [2] R. Ahlswede, “The capacity region of a channel with two senders and two receivers,” _The Annals of Probability_ , vol. 2, no. 5, pp. 805–814, Oct. 1974.
  * [3] A. B. Carleial, “A case where interference does not reduce capacity,” _IEEE Trans. Inform. Theory_ , vol. 21, no. 5, pp. 569–570, 1975.
  * [4] T. S. Han and K. Kobayashi, “A new achievable rate region for the interference channel,” _IEEE Trans. Inform. Theory_ , vol. IT-27, no. 1, pp. 49–60, Jan. 1981.
  * [5] A. A. El Gamal and M. H. M. Costa, “The capacity region of a class of deterministic interference channels,” _IEEE Trans. Inform. Theory_ , vol. IT-28, no. 2, pp. 343–346, Mar. 1982.
  * [6] M. H. M. Costa and A. A. El Gamal, “The capacity region of the discrete memoryless interference channel with strong interference.” _IEEE Trans. Inform. Theory_ , vol. IT-33, no. 5, pp. 710–711, Sep. 1987.
  * [7] G. Kramer, “Outer bounds on the capacity of Gaussian interference channels,” _IEEE Trans. Inform. Theory_ , vol. 50, no. 3, pp. 581–586, Mar. 2004.
  * [8] H. Sato, “Two-user communication channels,” _IEEE Trans. Inform. Theory_ , vol. IT-23, no. 3, pp. 295–304, May 1977.
  * [9] A. B. Carleial, “Outer bounds on the capacity of interference channels,” _IEEE Trans. Inform. Theory_ , vol. IT-29, no. 4, pp. 602–606, Jul. 1983\.
  * [10] H. Sato, “On degraded Gaussian two-user channels,” _IEEE Trans. Inform. Theory_ , vol. IT-24, no. 5, pp. 637–640, Sep. 1978.
  * [11] M. H. M. Costa, “On the Gaussian interference channel,” _IEEE Trans. Inform. Theory_ , vol. IT-31, no. 5, pp. 607–615, Sep. 1985.
  * [12] H.-F. Chong, M. Motani, H. K. Garg, and H. E. Gamal, “On the Han-Kobayashi region for the interference channel,” _IEEE Trans. Inform. Theory_ , vol. 54, no. 7, pp. 3188–3195, Jul. 2008.
  * [13] G. Kramer, “Review of rate regions for interference channels,” in _Int. Zurich Seminar on Communications (IZS)_ , Zurich, Feb. 22 - 24 2006, pp. 162–165.
  * [14] R. H. Etkin, D. N. C. Tse, and H. Wang, “Gaussian interference channel capacity to within one bit,” _IEEE Trans. Inform. Theory_ , vol. 54, no. 12, pp. 5534–5562, Dec. 2008.
  * [15] X. Huang, X. Ma, L. Lin, and B. Bai, “Accessible capacity of secondary users over the gaussian interference channel,” in _IEEE International Symposium on Information Theory,_ , St. Petersburg, Russia, Aug. 2011, pp. 811–815.
  * [16] F. Baccelli, A. A. El Gamal, and D. Tse, “Interference networks with point-to-point codes,” _IEEE Trans. Inform. theory_ , vol. 57, no. 5, pp. 2582–2596, May 2011.
  * [17] K. Moshksar, A. Ghasemi, and A. K. Khandani, “An alternative to decoding interference or treating interference as gaussian noise,” in _IEEE International Symposium on Information Theory,_ , St. Petersburg, Russia, Aug. 2011, pp. 1176–1180.
  * [18] T. S. Han and S. Verdú, “Approximation theory of output statistics,” _IEEE Trans. Inform. Theory_ , vol. 39, no. 3, pp. 752–772, May 1993.
  * [19] T. S. Han, _Information-spectrum methods in information theory_. New York: Springer-Verlag Berlin Heidelberg, 2003\.
  * [20] S. Verdú and T. S. Han, “A general formula for channel capacity,” _IEEE Trans. Inform. Theory_ , vol. 40, no. 4, pp. 1147–1157, Jul. 1994.
  * [21] T. S. Han, “An information-spectrum approach to capacity theorems for the general multiple-access channel,” _IEEE Trans. Inform. Theory_ , vol. 44, no. 7, pp. 2773–2795, Nov. 1998.
  * [22] R. H. Etkin, N. Merhav, and E. Ordentlich, “Error exponents of optimum decoding for the interference channel,” _IEEE Trans. Inform. Theory_ , vol. 56, no. 1, pp. 40–56, Jan. 2010.
  * [23] A. Kavčić, “On the capacity of Markov sources over noisy channels,” in _Proc. IEEE GLOBECOM’01_ , vol. 5, San Antonio, TX, USA, Nov. 25-29 2001, pp. 2997–3001.
  * [24] D. M. Arnold and H.-A. Loeliger, “On the information rate of binary-input channels with memory,” in _Proc. 2001 IEEE Int. Conf. Commun._ , vol. 9, Helsinki, Finland, Jun. 2001, pp. 2692–2695.
  * [25] H. D. Pfister, J. B. Soriaga, and P. H. Siegel, “On the achievable information rates of finite state ISI channels,” in _Proc. IEEE GLOBECOM’01_ , vol. 5, San Antonio, Texas, Nov. 25-29 2001, pp. 2992–2996.
  * [26] L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” _IEEE Trans. Inform. Theory_ , vol. IT-20, no. 2, pp. 284–287, Mar. 1974.
  * [27] T. M. Cover and J. A. Thomas, _Elements of Information Theory_. New York: John Wiley and Sons, Inc, 1991.
  * [28] X. Ma, S. Zhao, K. Zhang, and B. Bai, “Kite codes over groups,” in _IEEE Information Theory Workshop_ , Paraty, Brazil, 2011, pp. 481–485.
  * [29] K. Zhang, X. Ma, S. Zhao, B. Bai, and X. Zhang, “A new ensemble of rate-compatible LDPC codes,” in _IEEE International Symposium on Information Theory_ , Cambridge, MA, USA, July 2012.
  * [30] N.Wiberg, H.-A. Loeliger, and R. Kötter, “Codes and iterative decoding on general graphs,” _Europ. Trans. Commun._ , vol. 6, pp. 513 – 526, Sep. 1995\.
  * [31] F. R. Kschischang, B. J. Frey, and H. A. Loeliger, “Factor graphs and the sum-product algorithm,” _IEEE Trans. Inform. Theory_ , vol. 47, no. 2, pp. 498 – 519, Feb. 2001.
  * [32] G. D. Forney, Jr., “Codes on graphs: Normal realizations,” _IEEE Trans. Inform. Theory_ , vol. 47, no. 2, pp. 520–548, Feb. 2001.
  * [33] X. Ma, K. Zhang, H. Chen, and B. Bai, “Low complexity X-EMS algorithms for nonbinary LDPC codes,” _IEEE Trans. Commun._ , vol. 60, no. 1, pp. 9–13, Jan. 2012.