Dr. Te Su Han accepted the invitation on 9 January 2010 (self-imposed deadline: 9 August 2010).

Dr. Te Sun Han, Waseda University, was invited on 7 January 2010.

Dr. Kingo Kobayashi accepted the invitation on 4 November 2008 (self-imposed deadline: 4 May 2009) .

## Introduction

The classical communication channel is an input-output probabilistic model with only one message sender and the corresponding receiver. An important quantity featuring this model is the maximum rate at which we can transmit information through the channel with asymptotically negligible error probability. Shannon gave the answer for this problem in 1948 (S48). The maximum rate, called the capacity, is expressed as the maximum of mutual information $$I(X; Y)$$ with respect to the channel input $$X$$ where $$Y$$ is the channel output. One of the modern channel models in multi-user communication circumstances is the interference channel where several classical channels are active in parallel, but the data flows of each channel influence each other. Most simple model is endowed with two inputs and two outputs constituting two transmission paths interfering each other. Here, we need to consider two transmission rates $$R_1$$ and $$R_2$$ to be maximized with asymptotically negligible error probability. Thus, we want to determine the capacity region $${\mathcal C}_{\rm IC}$$ of the interference channel as the set of all simultaneously achievable rate pairs $$(R_1, R_2)\ .$$ This problem was also presented by Shannon (S61). To date, this problem has not yet been solved in general since the seventies, and is currently one of long-standing open problems in information theory. On the other hand, researchers have attacked this problem by restricting to special subclasses of interference channels, and in some cases have succeeded to obtain the capacity region for the subclass (refer to (B79),(HK81),(S81),(GC82),(CG87),(AC06),(MYK07),(SLSS08),(LU),(CM09)), or got new outer regions for the interference channel (refer to (K04),(ETW08),(XKC09)).

Specifically, let $$\omega(y_1 y_2 | x_1 x_2)$$ be the probability of outputs $$y_1, y_2$$ when the inputs are $$x_1, x_2$$ (see the left of Figure 1). Two message senders use this channel $$n$$ times to transmit their messages $$m_1 \in {\mathcal M}_1, m_2 \in {\mathcal M}_2$$ to the corresponding receivers, by encoding $$m_1, m_2$$ into input sequences $${\boldsymbol x}_1(m_1) = x_{11}^{(m_1)} x_{12}^{(m_1)} \dots x_{1n}^{(m_1)}, {\boldsymbol x}_2(m_2) = x_{21}^{(m_2)}x_{22}^{(m_2)} \dots x_{2n}^{(m_2)}\ ,$$ respectively. Here, we assume the memoryless condition on the channel, that is, $$\omega^n({\boldsymbol x}_1, {\boldsymbol x}_2) = \prod_{i=1}^n \omega(y_{1i} y_{2i} | x_{1i} x_{2i})\ .$$ Usually, the synchronization of letters is assumed to make the problem simple.

Since each receiver can see only his/her output sequence from which he/she has to decide the sent message, the relevant channels are actually the marginal distributions $$\omega_1$$ and $$\omega_2$$ (see the right of Figure 1): $\begin{array}{rcl} \omega_1(y_1 | x_1 x_2) & = & \sum_{y_2} \omega(y_1 y_2 | x_1 x_2) ,\\ \omega_2(y_2 | x_1 x_2) & = & \sum_{y_1} \omega(y_1 y_2 | x_1 x_2) . \end{array}$

By giving good codes $${\mathcal C}_1 = \{ {\boldsymbol x}_1 = \varphi_1(m_1) : m_1 \in {\mathcal M}_1 \}, {\mathcal C}_2 = \{ {\boldsymbol x}_2 = \varphi_2(m_2) : m_2 \in {\mathcal M}_2\}\ ,$$ we want to enlarge the cardinalities $$M_1 = |{\mathcal M}_1|$$ and $$M_2 = |{\mathcal M}_2|$$ of the message sets $${\mathcal M}_1, {\mathcal M}_2$$ as far as messages can be transmitted with asymptotically negligible error probability (see Figure 2). More precisely, we call an rates pair $$(R_1, R_2) = \lim_{n \rightarrow \infty} ( \frac{1}{n} \log M_1, \frac{1}{n} \log M_2 )$$ achievable if there is a sequence of coding systems $$\{ \varphi_1^n, \varphi_2^n ; \psi_1^n, \psi_2^n \}$$ such that the average decoding error probability goes to zero, that is, $\begin{array}{rcl} \frac{1}{M_1 M_2} \sum_{i=1}^{M_1} \sum_{j=1}^{M_2}\left\{1- \omega_1^n((\psi_1^n)^{-1}(i)|\varphi_1^n(i), \varphi_2^n(j)) \right\} \rightarrow 0 , \\ \frac{1}{M_1 M_2} \sum_{i=1}^{M_1} \sum_{j=1}^{M_2}\left\{1- \omega_2^n((\psi_2^n)^{-1}(j)|\varphi_1^n(i), \varphi_2^n(j)) \right\} \rightarrow 0 , \end{array}$ when $$n$$ tends to the infinity, where $$(\psi_1^n)^{-1}(i)$$ is the domain of the map $$\psi_1^n$$ for $$i\ ,$$ etc. The closure of the set of all achievable rates pairs is called the capacity region $${\mathcal C}_{\rm IC}$$ of the interference channel $$\omega\ .$$

The operational efficiency is measured by the rates pair $$(R_1, R_2)\ .$$ We want to achieve the best efficiency, that is, to realize the maximal rates pair. However, there is a tradeoff between the rates $$R_1$$ and $$R_2$$ in the best operational condition. If we would increase the rate $$R_1$$ for receiver 1, then we should decrease the rate $$R_2$$ at the expense of sacrificing the efficiency for receiver 2 in order to keep the achievability.

## Strong Interference Channel

One of the early epoch-making results of the interference channel is the realization of the fact that strong interference can be less harmful than weak interference, or very intense interference can be as innocuous as no interference at all (from (C75)). This interesting phenomenon that is today called as the strong or very strong interference, came from the study of Gaussian interference channel which we will argue in the section 4. Here, we give only its discrete version of this result:

Theorem(CG87) If the interference channel $$\omega$$ satisfies the strong interference conditions, that is, $$I(Y_1; X_1 | X_2) \leq I(Y_2; X_1 | X_2)$$ and $$I(Y_2; X_2 | X_2) \leq I(Y_1; X_2 | X_1)$$ for any independent input random variables $$X_1, X_2\ ,$$ then the capacity region of the channel is the closure of the union of the regions defined by

$\tag{1} \left\{ \begin{array}{rcl} 0 & \leq & R_1 \ \leq I( Y_1 ; X_1 | X_2 Q) , \\ 0 & \leq & R_2 \ \leq I( Y_2 ; X_2 | X_1 Q) , \\ 0 & \leq & R_1 + R_2 \ \leq \min \{ I( Y_1 ; X_1 X_2 | Q), I( Y_2 ; X_1 X_2 | Q) \} , \end{array} \right.$

where $$X_1, X_2$$ is independent given $$Q\ .$$

## Han-Kobayashi Achievable Region and its Simple Expression

The largest inner bound for the capacity of interference channel, called now the Han-Kobayashi achievable region, is expressed as follows. At first, let us introduce the test channel $$Z = Q U_1 W_1 U_2 W_2 X_1 X_2 Y_1 Y_2$$ (see Figure 3). Here, the auxiliary random variables $$U_1, W_1, U_2, W_2$$ are independent each other given the time-sharing variable $$Q\ .$$ The inputs $$X_1$$ and $$X_2$$ of the channel $$\omega$$ are deterministic functions $$f_1(U_1, W_1, Q)\ ,$$ $$f_2(U_2, W_2, Q)$$ of $$U_1, W_1, Q$$ and $$U_2, W_2, Q\ ,$$ respectively; $$Y_1$$ and $$Y_2$$ are the outputs of the channel $$\omega\ .$$ Denote the whole set of test channels by $${\mathcal P}\ .$$ For convenience, we call the channel depicted as in Figure 3 simply the test channel $$Z$$

Then, we can define conditional mutual informations among these random variables defining the test channel as follows:

$\left\{ \begin{array}{ccl} a_1 & = & I(Y_1 ; U_1 | W_1 W_2 Q), \\ b_1 & = & I(Y_1 ; W_1 | U_1 W_2 Q), \\ c_1 & = & I(Y_1 ; W_2 | U_1 W_1 Q), \\ d_1 & = & I(Y_1 ; U_1 W_1 | W_2 Q), \\ e_1 & = & I(Y_1 ; U_1 W_2 | W_1 Q), \\ f_1 & = & I(Y_1 ; W_1 W_2 | U_1 Q), \\ g_1 & = & I(Y_1 ; U_1 W_1 W_2 | Q), \end{array} \right.$

$\left\{ \begin{array}{ccl} a_2 & = & I(Y_2 ; U_2 | W_2 W_1 Q), \\ b_2 & = & I(Y_2 ; W_2 | U_2 W_1 Q), \\ c_2 & = & I(Y_2 ; W_1 | U_2 W_2 Q), \\ d_2 & = & I(Y_2 ; U_2 W_2 | W_1 Q), \\ e_2 & = & I(Y_2 ; U_2 W_1 | W_2 Q), \\ f_2 & = & I(Y_2 ; W_2 W_1 | U_2 Q), \\ g_2 & = & I(Y_2 ; U_2 W_2 W_1 | Q). \end{array} \right.$

Using these quantities, let us define the $${\mathcal R}_{\rm CMGE}(Z)$$ as the whole set of rates pair $$(R_1, R_2)$$ satisfying the inequalities (see Figure 4):

$\tag{2} \left\{ \begin{array}{rcl} R_1 & \leq & d_1 ,\\ R_2 & \leq & d_2 ,\\ R_1 + R_2 & \leq & a_1 + g_2 ,\\ R_1 + R_2 & \leq & a_2 + g_1 ,\\ R_1 + R_2 & \leq & e_1 + e_2 ,\\ 2 R_1 + R_2 & \leq & a_1 + g_1 + e_2 ,\\ R_1 + 2 R_2 & \leq & a_2 + g_2 + e_1 ,\\ R_1 & \geq & 0 ,\\ R_2 & \geq & 0 . \end{array} \right.$

Then, the Han-Kobayashi region $${\mathcal R}_{\rm HK}$$(HK81) is the closure of $$\displaystyle \bigcup_{Z \in {\mathcal P}} {\mathcal R}_{\rm CMGE}(Z)$$(cf. (CMGE08)), and it holds

Theorem(HK81),(CMGE08) Any rates pair $$(R_1, R_2)$$ contained in $${\mathcal R}_{\rm HK}$$ is achievable, that is, $\begin{array}{rcl} {\mathcal C}_{\rm IC} &\supset& {\mathcal R}_{\rm HK}. \end{array}$

This formula using (2) for the HK region(HK81) was introduced by the paper (CMGE08). This form is the simplest to date. The original proof on achievability of rates pair $$(R_1, R_2)$$ contained in $${\mathcal R}_{\rm HK}$$ was started by introducing an intermediate region $${\mathcal S}_{\rm HK}(Z)$$ of rates quadruples $$(S_1, T_1, S_2, T_2)$$ that satisfy two sets of the inequalities induced by the test channel $$Z \in {\mathcal P}\ :$$

$\tag{3} \left\{ \begin{array}{ccl} S_1 & \leq & a_1 ,\\ T_1 & \leq & b_1 ,\\ T_2 & \leq & c_1 ,\\ S_1 + T_1 & \leq & d_1 ,\\ S_1 + T_2 & \leq & e_1 ,\\ T_1 + T_2 & \leq & f_1 ,\\ S_1 + T_1 + T_2 & \leq & g_1 ,\\ S_1 & \geq & 0 ,\\ T_1 & \geq & 0 , \end{array} \right.$

and $\tag{4} \left\{ \begin{array}{ccl} S_2 & \leq & a_2 ,\\ T_2 & \leq & b_2 ,\\ T_1 & \leq & c_2 ,\\ S_2 + T_2 & \leq & d_2 ,\\ S_2 + T_1 & \leq & e_2 ,\\ T_2 + T_1 & \leq & f_2 ,\\ S_2 + T_2 + T_1 & \leq & g_2 , \\ S_2 & \geq & 0 ,\\ T_2 & \geq & 0 . \end{array} \right.$

Here, $$S_1, S_2$$ are the rates of private messages intended to be transmitted only to the corresponding receivers from the senders, and $$T_1, T_2$$ are the rates of common messages to both of receivers. Any rates quadruple $$(S_1, T_1, S_2, T_2)$$ contained in $${\mathcal S}_{\rm HK}(Z)$$ is proved to be achievable for the test channel $$Z\ .$$ Then, using the Fourier-Motzkin method, we can project the four-dimensional region $${\mathcal S}_{\rm HK}(Z)$$ to the two-dimensional region $${\mathcal R}_{\rm HK}(Z)$$ with $$R_1 = S_1 + T_1, R_2 = S_2 + T_2$$ through subtle discussions removing redundant inequalities. It should be noted here that $$(R_1, R_2)$$ is achievable for the original interference channel ( Figure 2) if $$(S_1, T_1, S_2, T_2)$$ is achievable for the test channel (Figure 3). The two-dimensional region $${\mathcal R}_{\rm HK}(Z)$$ turns out to be the same set (2) of inequalities plus the extra two inequalities:

$\tag{5} \left\{ \begin{array}{rcl} R_1 & \leq & a_1 + c_2 ,\\ R_2 & \leq & a_2 + c_1 . \end{array} \right.$

Therefore, apparently, $${\mathcal R}_{\rm CMGE}(Z) \supset {\mathcal R}_{\rm HK}(Z)\ .$$ However, it can be also shown that $${\mathcal R}_{\rm CMGE}(Z) \subset {\mathcal R}_{\rm HK}(Z) \cup {\mathcal R}_{\rm HK}(Z') \cup {\mathcal R}_{\rm HK}(Z'')$$ by suitably choosing other test channels $$Z', Z''\ .$$ Thus, $$\displaystyle \bigcup_{Z \in {\mathcal P}} {\mathcal R}_{\rm CMGE}(Z) = \bigcup_{Z \in {\mathcal P}} {\mathcal R}_{\rm HK}(Z)\ .$$ Here, we should notice that both sets of inequalities, (3) and (4), define polymatroids due to the assumption on the test channel $$Z \in {\mathcal P}\ .$$ Thus, it holds that for $$a_i, \dots, g_i, i= 1, 2\ ,$$ $\left\{ \begin{array}{ccl} a_i, b_i \leq & d_i & \leq a_i + b_i, \\ a_i, c_i \leq & e_i & \leq a_i + c_i, \\ b_i, c_i \leq & f_i & \leq b_i + c_i, \\ d_i, e_i, f_i \leq & g_i & \leq c_i + d_i, b_i+e_i, a_i + f_i, \\ a_i + g_i & \leq & d_i + e_i, \\ b_i + g_i & \leq & f_i + d_i, \\ c_i + g_i & \leq & e_i + f_i . \end{array} \right.$ These conditions are used to remove redundant inequalities in applying the Fourier-Motzkin method to project $${\mathcal S}_{\rm HK}(Z)$$ to $${\mathcal R}_{\rm HK}(Z)\ .$$

## Gaussian Interference Channel

The Gaussian interference channel is shown in Figure 5, and is mathematically expressed as $\tag{6} \left\{ \begin{array}{rcl} Y_1 & = & a X_1 + b X_2 + n_1^* \\ Y_2 & = & c X_1 + d X_2 + n_2^* , \end{array} \right.$

where $$Y_1$$ is the output from the input $$X_1$$ with interference from the unintended input $$X_2$$ plus the Gaussian noise $$n_1^*$$ with the expectation 0, variance $$N_1\ .$$ Similarly, $$Y_2$$ is the same.

Usually, setting $$\sqrt{a_{12}} = \frac{b}{d}\,\sqrt{ \frac{N_2}{N_1}}$$ and $$\sqrt{a_{21}} = \frac{c}{a}\,\sqrt{ \frac{N_1}{N_2}}\ ,$$ we discuss the capacity problem with the canonical model (see Figure 6) converted from (6): $\tag{7} \left\{ \begin{array}{rcl} Y_1 & = & X_1 + \sqrt{a_{12}}X_2 + n_1 \\ Y_2 & = & \sqrt{a_{21}} X_1 + X_2 + n_2 , \end{array} \right.$

where $$n_1, n_2$$ are Gaussian noises with expectation $$0\ ,$$ and variance $$1\ ,$$ and the inputs $$X_1, X_2$$ are subject to the average power constraints when the channel is used $$n$$ times: $\frac{1}{n} \sum_{k=1}^n \left( x_{ik}^{(m_i)} \right)^2 \leq P_i\ \ (i = 1,2) ,$ where we notice that we have set ${\boldsymbol x}_i(m_i) = x_{i1}^{(m_i)} \dots x_{in}^{(m_i)} \ (i = 1,2).$

For the case of strong interference, we have

Theorem(HK81),(S81) The capacity region of Gaussian interference channel with $$a_{12} \geq 1, a_{21} \geq 1$$ is the set of rates pair $$(R_1, R_2)$$ satisfying the inequalities: $\tag{8} \left\{ \begin{array}{rcccl} 0 & \leq & R_1 & \leq & \frac{1}{2} \log (1 + P_1),\\ 0 & \leq & R_2 & \leq & \frac{1}{2} \log (1 + P_2),\\ 0 & \leq & R_1 + R_2 & \leq & \min \left\{ \frac{1}{2} \log (1 + P_1 + a_{12} P_2), \right.\\ & & & & \left. \ \ \ \ \ \ \ \frac{1}{2} \log (1 + P_2 + a_{21} P_1) \right\} \end{array} \right.$

Especially, we have

Theorem(C75) In case of very strong interference, that is, when $$a_{12} \geq 1+P_1, a_{21} \geq 1+P_2\ ,$$ the capacity region is identical to the case of no interference: $\tag{9} \left\{ \begin{array}{rcccl} 0 & \leq & R_1 & \leq & \frac{1}{2} \log (1 + P_1),\\ 0 & \leq & R_2 & \leq & \frac{1}{2} \log (1 + P_2) . \end{array} \right.$

Since the first paper(Carleial(C75)) on the interference channel, a lot of people have focused on developing better inner bounds and/or better outer bounds on the capacity region $${\mathcal C}_{\rm IC}\ .$$ As for the inner bounds, surprisingly enough, there has been found no progress since Han and Kobayashi(HK81).

On the other hand, as for the outer bounds, there have been ever appeared several significant improvements such as … Among others, ...

To see how large $${\mathcal R}_{\rm HK}$$ is in the Gaussian case, set the time-sharing variable $$Q$$ to a constant; set the auxiliary variables to Gaussian, and set the deterministic functions to the simple addition. Thus, the HK achievable regions $${\mathcal G}_{\rm HK}(Z)$$ corresponding to the Han-Kobayashi regions $${\mathcal R}_{\rm HK}(Z)$$ are plotted in Figure 7 for symmetric Gaussian interference channels ($$P=P_1=P_2, a=a_{12} = a_{21}$$) parametrized by the interference coefficient $$a\ .$$

The paper (ETW08) shows that the above Han-Kobayashi's simple scheme can achieve, to within a single bit, the capacity of the general Gaussian interference channel even in cases of weak interference. The simple strategy is that the power allocation should be to balance the interference $$|a|^2 P_u$$ due to the private message $$P_u$$ equal to the noise power $$N\ ,$$ where the total restricted power $$P$$ is partitioned for the private message and the common message as $$P = P_u + P_w\ .$$ By applying the simple scheme, the whole quantities of conditional mutual information for the HK region expression can be expressed by only two quantities, that is, the signal-to-noise ratio $${\rm SNR} = |a|^2 P/N$$ and the interference-to-noise ratio $${\rm INR} = |b|^2 P/N$$ for the symmetric Gaussian interference channel where $$a$$ is the direct coefficient, and $$b$$ is the cross-over coefficient. We write as $$R_{\rm HK}^{\rm sym}$$ for the maximum rate $$R$$ such that $$(R,R)$$ is achievable by the simple HK scheme. Then, we have the formula for this quantity: $\tag{10} R_{\rm HK}^{\rm sym} = \min \left\{ \begin{array}{l} \frac{1}{2} \log \left( 1 + {\rm SNR} + {\rm INR} \right) + \frac{1}{2} \log \left( 2 + \frac{ {\rm SNR}}{{\rm INR} } \right) - 1 , \\ \log \left( 1 + {\rm INR} + \frac{ {\rm SNR}}{{\rm INR} } \right) - 1 . \end{array} \right.$

The first term in "$$\min$$" corresponds to the upper bound of inequalities $$R_1 + R_2 \leq a_1 + g_2 = a_2 + g_1\ ,$$ and the sencond term to that of inequality $$R_1 + R_2 \leq e_1 + e_2$$ in (2). Comparing $$R_{\rm HK}^{\rm sym}$$ with the capacity $$C_{\rm AWGN} = \log (1 + {\rm SNR})$$ of the canonical additive Gaussian noise channel, we obtain an interesting two modes behavior depending on the interference level $$0 \leq \alpha = \frac{\log {\rm INR}}{\log {\rm SNR}} \leq 1$$ in an asymptotic condition of $${\rm SNR} \gg 1, {\rm INR} \gg 1, {\rm SNR} \gg {\rm INR}$$ with weak interference( Figure 8).

Summarizing the above results due to Etkin, et.al.,

Theorem(ETW08) $\tag{11} \frac{R_{\rm HK}^{\rm sym}}{C_{\rm AWGN}} \approx \min \left\{ \begin{array}{l} 1 - \frac{1}{2} \alpha , \\ \max \left\{ \alpha, 1-\alpha \right\} . \end{array} \right.$