Interference Channel
From Scholarpedia
| This article has not been published yet; It may be unfinished, contain inaccuracies or unapproved changes. | |||||||||||||||||||||
Author: Dr. Kingo Kobayashi, National Institute of Information and Communications Engineering, Japan
Author: Dr. Te Sun Han, Waseda University
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) .
Contents |
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
with respect to the channel input
where
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
and
to be maximized with asymptotically negligible error probability.
Thus, we want to determine the capacity region
of the interference channel as the set of all simultaneously achievable rate pairs
.
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
be the probability of outputs
when the inputs are
(see the left of Fig.1). Two message senders use this channel
times to transmit their messages
to the corresponding receivers, by encoding
into input sequences
, respectively.
Here, we assume the memoryless condition on the channel, that is,
. 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
and
(see the right of Fig. 1):
By giving good codes
, we want to enlarge the cardinalities
and
of the message sets
as far as messages can be transmitted with asymptotically negligible error probability (see Fig. 2).
More precisely, we call an rates pair
achievable
if there is a sequence of coding systems
such that the average decoding error probability goes to zero, that is,
when
tends to the infinity, where
is the domain of the map
for
, etc.
The closure of the set of all achievable rates pairs is called the capacity region
of the interference channel
.
The operational efficiency is measured by the rates pair
.
We want to achieve the best efficiency, that is, to realize the maximal rates pair.
However, there is a tradeoff between the rates
and
in the best operational condition.
If we would increase the rate
for receiver 1, then we should decrease the rate
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
satisfies the strong interference conditions, that is,
and
for any independent input random variables
,
then the capacity region of the channel is the closure of the union of the regions defined by
- (1)
where
is independent given
.
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
(see Fig. 3).
Here, the auxiliary random variables
are independent each other given the time-sharing variable
.
The inputs
and
of the channel
are deterministic functions
,
of
and
, respectively;
and
are the outputs of the channel
.
Denote the whole set of test channels by
.
For convenience, we call the channel depicted as in Fig.3 simply the test channel
Then, we can define conditional mutual informations among these random variables defining the test channel as follows:
Using these quantities, let us define the
as
the whole set of rates pair
satisfying the inequalities (see Fig. 4):
- (2)
Then, the Han-Kobayashi region
(HK81) is the closure of
(cf. (CMGE08)), and it holds
Theorem(HK81),(CMGE08) Any rates pair
contained in
is achievable, that is,
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
contained in
was started by
introducing an intermediate region
of rates quadruples
that satisfy
two sets of the inequalities induced by the test channel
:
- (3)
and
- (4)
Here,
are the rates of private messages intended to be transmitted only to
the corresponding receivers from the senders,
and
are the rates of common messages to both of receivers.
Any rates quadruple
contained in
is proved to be achievable
for the test channel
.
Then, using the Fourier-Motzkin method, we can project the four-dimensional region
to the two-dimensional region
with
through subtle discussions removing redundant inequalities.
It should be noted here that
is achievable for the original interference channel (Fig. 2)
if
is achievable for the test channel (Fig.3).
The two-dimensional region
turns out to be the same set (2) of inequalities
plus the extra two inequalities:
- (5)
Therefore, apparently,
.
However, it can be also shown that
by suitably choosing other test channels
.
Thus,
.
Here, we should notice that both sets of inequalities, (3) and (4), define polymatroids due to
the assumption on the test channel
.
Thus, it holds that for
,
These conditions are used to remove redundant inequalities in applying the Fourier-Motzkin method to project
to
.
Gaussian Interference Channel
The Gaussian interference channel is shown in Fig. 5, and is mathematically expressed as
- (6)
where
is the output from the input
with interference from the unintended input
plus the Gaussian noise
with the expectation 0, variance
. Similarly,
is the same.
Usually, setting
and
,
we discuss the capacity problem with the canonical model (see Fig. 6) converted from (6):
- (7)
where
are Gaussian noises with expectation
, and variance
, and the inputs
are subject to the average power constraints when the channel is used
times:
where we notice that we have set
For the case of strong interference, we have
Theorem(HK81),(S81) The capacity region of Gaussian interference channel with
is the set of rates pair
satisfying the inequalities:
- (8)
Especially, we have
Theorem(C75)
In case of very strong interference, that is, when
,
the capacity region is identical to the case of no interference:
- (9)
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
.
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
is in the Gaussian case, set the time-sharing variable
to a constant;
set the auxiliary variables to Gaussian, and set the deterministic functions to the simple addition.
Thus, the HK achievable regions
corresponding to the Han-Kobayashi regions
are plotted in Fig. 7 for symmetric Gaussian interference channels (
)
parametrized by the interference coefficient
.
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
due to
the private message
equal to the noise power
, where the total restricted power
is partitioned for
the private message and the common message as
.
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
and
the interference-to-noise ratio
for the symmetric Gaussian interference channel
where
is the direct coefficient, and
is the cross-over coefficient.
We write as
for the maximum rate
such that
is achievable by the simple HK scheme. Then, we have the formula for this quantity:
- (10)
The first term in "
" corresponds to the upper bound of inequalities
,
and the sencond term to that of inequality
in (2).
Comparing
with the capacity
of the canonical additive Gaussian noise channel, we obtain an interesting two modes behavior depending on the interference level
in an asymptotic condition of
with weak interference(Fig. 8).
Summarizing the above results due to Etkin, et.al.,
Theorem(ETW08)
- (11)
References
- Shannon, C. E. (1948). A mathematical theory of communication. Bell Syst. Tech. J. 27: 379-423, 623-656.
- Shannon, C. E. (1961). Two-way communication channels. In Proc. 4th Berkeley Symp. Math. Stat. and Prob. 1: 611-644.
- Ahlswede, R. (1974). The capacity region of a channel with two senders and two receivers. Ann. Prob. 2: 805-814.
- Carleial, A. B. (1975). A case where interference does not reduce capacity. IEEE Trans. Inform. Theory 21 (5): 569-570.
- Sato, H. (1977). Two-user communication channels. IEEE Trans. Inform. Theory 23 (3): 295-304.
- Carleial, A. B. (1978). Interference Channels. IEEE Trans. Inform. Theory 24 (1): 60-70.
- Sato, H. (1978). On the capacity region of a discrete two-user channel for strong interference. IEEE Trans. Inform. Theory 24 (3): 377-379.
- Benzel, R. (1979). The capacity region of a class of discrete additive degraded interference channels. IEEE Trans. Inform. Theory 25 (2): 228-231.
- Csisz\'ar , I and K\"orner, J K (1981). Information Theory: Coding Theorems for Discrete Memoryless Systems Academic Press, New York.
- Han, T. S. and Kobayashi, K. (1981). A new achievable rate region for the interference channel. IEEE Trans. Inform. Theory 27 (1): 49-60.
- Sato, H (1981). The capacity of the Gaussian interference channel under strong interference. IEEE Trans. Inform. Theory 27 (6): 786-788.
- El Gamal, A A and Costa, M H M (1982). The capacity of a class of deterministic interference channels. IEEE Trans. Inform. Theory 28 (2): 343-346.
- Costa, M H M (1985). On the Gaussian interference channel. IEEE Trans. Inform. Theory 31 (5): 607-615.
- Costa, M H M and El Gamal, A A (1987). The capacity region of the discrete memoryless interference channel with strong interference. IEEE Trans. Inform. Theory} 33 (5): 710-711.
- van der Meulen, E C (1994). Some reflections on the interference channel. In Communications and Cryptography: Two Sides of One Tapestry R.E. Blahut, D.J. Costello, U. Maurer and T. Mittelholzer. Kulwer, Boston, MA. 409-421
- Kramer, G (2004). Outer bounds on the capacity of Gaussian interference channels. IEEE Trans. Inform. Theory 50: 581-586.
- Sason, I (2004). On achievable rate regions for the Gaussian interference channels. IEEE Trans. Inform. Theory 50: 1345-1356.
- Ahlswede, R and Cai, N (2005). Codes with the identifiable parent property and the multiple-access channel. LNCS 4123: 249-257.
- Chong, H F; Motani, M and Garg, H K (2006). A comparison of two achievable rate regions for the interference channel. Proc. ITA Workshop none: -.
- Kramer, G (2006). Review of rate regions for interference channels. International Zurich Seminar none: -.
- Devroye, N; Mitran, P and Tarokh, V (2006). Achievable rates in cognitive channels. IEEE Trans. Inform. Theory 52: 1813-1827.
- Kobayashi, K. and Han, T. S. (2007). A further consideration of the HK and CMG regions for the interference channel Proc. ITA Workshop VOLUMEWITHNUMBER: -.
- Mari\'c, I.; Yates, R. D. and Kramer, G. (2007). Capacity of interference channels with partial transmitter cooperation IEEE Trans. Inform. Theory 53: 3535-3548.
- Jiang, J.; Xin, Y. and Garg, H. K. (2008). Interference channels with common information IEEE Trans. Inform. Theory 54: 171-187.
- Sung, S. W.; Lui, K. W. K.; Shum, K. W. and So, H. C. (2008). Sum capacity of one-sided parallel Gaussian interference channels IEEE Trans. Inform. Theory 54: 468-472.
- Chong, H-F.; Motani, M.; Garg, H. K. and El Gamal, H. (2008). On the Han-Kobayashi Region for the Interference Channel. IEEE Trans. Inform. Theory 54 (7): 3188-3195.
- Liu, N and Ulukus, S (2008). The capacity region of a class of discrete degraded interference channels. IEEE Trans. Inform. Theory 54 (9): 4372-4378.
- Etkin, R H; Tse, D N C and Wang, H (2008). Gaussian interference channel capacity to within one bit. IEEE Trans. Inform. Theory 54 (12): 5534-5562.
- Chong, H-F and Motani, M (2009). The capacity region of a class of semideterministic interference channels. IEEE Trans. Inform. Theory 55 (2): 598-603.
- Shang, X; Kramer, G and Chen, B (2009). A new outer bound and the noisy-interference sum-rate capacity for Gaussian interference channes. IEEE Trans. Inform. Theory 55 (2): 689-699.
| Suggested by: | Dr. Kingo Kobayashi, National Institute of Information and Communications Engineering, Japan |
| Invited by: | Dr. Roberto Padovani, Qualcomm Inc., San Diego, CA |

.