Interference Alignment and Degrees of Freedom of the K-User

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 8, AUGUST 20083425Interference Alignment and Degrees of Freedom of the -User Interference ChannelViveck R. Cadambe, Student Member, IEEE, and Syed Ali Jafar, Member, IEEEKAbstract—For the fully connected K user wireless interference channel where the channel coef cients are time-varying and are drawn from a continuous distribution, the sum capacity is characterized as C (SNR) = K log(SNR) + o(log(SNR)). Thus, the K 2 user time-varying interference channel almost surely has K=2 degrees of freedom. Achievability is based on the idea of interference alignment. Examples are also provided of fully connected K user interference channels with constant (not time-varying) coef cients where the capacity is exactly achieved by interference alignment at all SNR values. Index Terms—Capacity, degrees of freedom, interference alignment, interference channel, multiple-input–multiple-output (MIMO), multiplexing.I. INTRODUCTION NFORMATION theorists have pursued capacity characterizations of interference channels for over three decades [1]–[16]. These efforts have produced an extensive array of interesting results that shed light on various aspects of the problem. Recently, a special case of the Han–Kobayashi scheme [3] is shown in [10] to achieve the capacity of the two-user interference channel within one bit. Reference [10] also provides a generalized degrees of freedom characterization that identi es different operational regimes for the two-user interference channel. For optimal wireless network design, the natural question is whether the insights from the two-user interference channel generalize to interference channel scenarios with more than two users. Unfortunately, for more than two users, even degrees of freedom characterizations are not known. At a coarse level, some of the interference management approaches used in practice and their information theoretic basis may be summarized as follows: Decode: If interference is strong, then the interfering signal can be decoded along with the desired signal—the tradeoff is that while decoding the interference may improve the rates for the desired signal, the decodability of the interfering signals limits the other users’ rates.IManuscript received July 16, 2007; revised March 19, 2008. This work was supported in part by the National Science Foundation under CAREER Grant 0546860 and by DARPA under ITMANET Grant UTA06-793. The material in this paper was presented in part at the 45th Annual Allerton Conference on Communications, Control, and Computing, Monticello, IL, September 2007. The authors are with the Center of Pervasive Communications and Computing (CPCC), Department of Electrical Engineering and Computer Science, University of California Irvine, Irvine, CA 92697 USA (e-mail: vcadambe@uci.edu; syed@uci.edu). Communicated by P. Viswanath, Associate Editor for Communications. Color version of Figure 2 in this paper is available online at http://ieeexplore. . Digital Object Identi er 10.1109/TIT.2008.926344While less common in practice due to the complexity of multi-user detection, this approach is supported by the capacity results on the “very strong interference” [1], and “strong interference” [3], [4] scenarios in the context of the two-user interference channel. The extension of “strong interference” results to more than two users is not straightforward in general. Treat as Noise: If interference is weak, then the interfering signal is treated as noise and single user encoding/ decoding suf ces. This approach has been used in practice for a long time, e.g., for frequency-reuse in cellular systems. However, information theoretic validation for this approach has only recently been obtained through several concurrent works [10], [13], [14], [17]. While treating weak interference as noise may be natural from an engineering standpoint, it is somewhat surprising from an information theoretic perspective that introducing structure into the interference signals is not useful in this regime. This result has been established for more than two users as well. Orthogonalize: If the strength of interference is comparable to the desired signal, then interference is avoided by orthogonalizing the channel access. This is the basis for time (frequency) division medium access schemes that avoid interference between coexisting wireless systems by dividing spectrum in a cake-cutting fashion. Information-theoretic validation for this approach comes from the capacity pre-log (degrees of freedom) characterizations.1 Considering only single-antenna nodes, the single user AWGN channel capacity in the absence of interferSNR SNR so ence may be expressed as that in the absence of interference the Gaussian channel has degree of freedom. The sum capacity (per user) of the two-user interference channel is known to be SNR SNR so that each user gets only half the degrees of freedom. It is conjectured in [18] that user interference the sum capacity (per user) for the SNR SNR . Orthogonal access channel is schemes can be used to divide the degree of freedom among the users such that each user gets a fraction and the sum of these fractions is equal to . We refer to this approach as the “cake-cutting” approach. In this paper, we explore the regime identi ed with the “orthogonalize” approach above, where all desired and interfering signals are of comparable strength. We show that, for a broad class of wireless networks, even when there are more than two1If the capacity can be expressed as C (SNR) = d log(SNR) + o(log(SNR)) then we say the channel has d degrees of freedom (also known as the capacity pre-log or the multiplexing gain).0018-9448/$25.00 © 2008 IEEEAuthorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.