3426IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 8, AUGUST 2008interfering users, the sum capacity (per user) is SNR SNR —i.e., everyone gets half the cake. The key to this result is an achievable scheme called interference alignment that is especially relevant to the interference channel with more than two users. We begin with the system model.de ne the degrees of freedom region ence channel as follows:for theuser interfer-II. SYSTEM MODEL user interference channel, comprised of Consider the transmitters and receivers. Each node is equipped with only one antenna (multiple antenna nodes are considered later in this paper). The channel output at the th receiver over the th time slot is described as follows: (1)III. OVERVIEW OF MAIN RESULTS The main insight offered in this paper is how the idea of interference alignment can be applied to the user interference channel to restrict all interference at every receiver to approximately half of the received signal space, leaving the other half interference-free for the desired signal. We present a toy example to illustrate this key concept. A. Interference Alignment—Toy Example Consider the constant -user interference channel de ned by (2) where at the th channel use, are the th receiver’s output symbol and zero mean, unit variance, complex circularly symmetric additive white Gaussian noise (respecis the th transmitter’s input symbol. All tively) and direct channel coef cients are equal to while all cross channel . The (carrying interference) coef cients are equal to channel coef cients are xed for all channel uses. All symbols are complex and all transmitted signals are subject to a power . In the absence of interference, constraint , so that and the optimal any user can achieve a capacity input distribution is circularly symmetric complex Gaussian. users present the optimal (sum-capacity With all achieving) scheme is as follows. Each transmitter sacri ces half the signal space and only sends a real Gaussian signal with power . Each receiver discards the imaginary part of the received signal that contains all the interference and is able to decode the desired signal free from interference at a rate , where the factor of shows up in the denominator because only the “real” part of ) is relevant. Thus, the the additive noise (which has power . sum rate with interference alignment is Interestingly, the sum capacity of this channel is also , which means that for this symmetric channel interference alignment is capacity optimal at any SNR. The converse argument is as follows. Consider any two users, say users 1 and 2 and eliminate all other users. This cannot hurt the users being considered. Consider any reliable coding scheme for this two user interference channel. Because the coding scheme is reliable by assumption, user 1 can successfully decode his message and subtract it out from the received signal. Now he can add back a phase-shifted version of his signal towhere, is the user index, is the is the output signal of the th receiver, time slot index, is the input signal of the th transmitter, is the channel fade coef cient from transmitter to receiver over the th time-slot and is the additive white Gaussian noise (AWGN) term at the th receiver. We assume all noise terms are independent identically distributed (i.i.d.) zero-mean complex Gaussian with unit variance. To avoid degenerate channel conditions (e.g., all channel coef cients are equal or channel coef cients are equal to zero or in nity) we assume that the channel coef cient values are drawn i.i.d. from a continuous distribution and the absolute value of all the channel coef cients is bounded between a nonzero minimum value and a . nite maximum value, We assume that channel knowledge is causal and globally available, i.e., at time slot each node knows all channel coef cients . Remark: For the purpose of this work there is no fundamental distinction between time and frequency dimensions. The channel-use index in the model described above could equivalently be used to describe time-slots, frequency slots or a time-frequency tuple if coding is performed in both time and frequency. The varying nature of the channel coef cients from one channel-use to another is, however, an important assumption. We also de ne the term “constant” channel, as the case . where all channel coeffcients are xed We assume that transmitters have independent intended for receivers , messages respectively. The total power across all transmitters is assumed to be equal to . We indicate the size of the message set by . For codewords spanning channel uses, the rates are achievable if the probability of error for all messages can be simultaneously made arbitrarily small by of choosing an appropriately large . The capacity region the user interference channel is the set of all achievable rate . tuples A. Degrees of Freedom Similar to the degrees of freedom region de nition for the multiple-input–multiple-output (MIMO) channel in [19] weAuthorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.