Interference Alignment and Degrees of Freedom of the K-User Interference Channel

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.

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.

CADAMBE AND JAFAR: INTERFERENCE ALIGNMENT AND DEGREES OF FREEDOM OF THE-USER INTERFERENCE CHANNEL3427reconstruct a new received signal that is statistically equivalent to the received signal of receiver 2. This implies that receiver 1 can decode both messages. Thus, the sum rate achieved by users 1 and 2 cannot be more than the sum-capacity of the two-user multiple access channel to receiver 1. But this . multiple-access channel (MAC) has sum capacity Similarly, considering any two users we nd that their sum rate . Adding all these bounds is bounded above by together, we nd that the outerbound on the sum-rate of all users in the interference channel is . Since this is achievable with interference alignment, it is also the capacity of this -user interference channel. This is true at any SNR value. One particularly interesting aspect of this example is that while the capacity achieving scheme uses Gaussian inputs, they are not circularly symmetric Gaussians. This is remarkable because for Gaussian point to point (MIMO), multiple access, broadcast channels with complex channel coef cients, the inputs (even if they are correlated and have different powers) are individually (element-wise) circularly symmetric Gaussian. B. Other Examples Interference alignment examples similar to the ones presented above can also be constructed in other dimensions such as space (beamforming across multiple antennas), time (either through propagation delays or through coding across time-varying channels), frequency (either through doppler-shifts or by coding across multiple-carriers with frequency selective coef cients) and codes (through lattice or multilevel codes that align interference within signal levels). Appendix I provides a simple example of interference alignment when each channel has a delay associated with it. As another example, consider two parallel interference channels (for example over two orthogonal carriers). On the rst carrier suppose all channel coef cients are equal to , while on the second carrier suppose all desired channels are equal to . one and the interfering channel coef cients are equal to Then it is easily seen that by spreading the signal over the all interference is two carriers with the spreading code aligned. This example is presented in [20] to establish the result that parallel interference channels are inseparable, i.e., joint coding across parallel channels is necessary to achieve capacity (unlike Gaussian multiple access and broadcast channels where separate coding with optimal power allocation across carriers suf ces to achieve capacity). Interference alignment is achieved through lattice codes in the context of many-to-one and one-to-many interference channels in [21] and for certain fully connected interference channels in [22], which also draws an interesting analogy between the propagtion delay example provided in Appendix I and the alignment of signal levels through multilevel codes. Quite simply, a multiplication of the transmitted signal with the channel coef cient (say ) leads ary representation (i.e., the to a decimal-point shift of the base- representation) of the transmitted signal value which is similar to a propagation delay in time. The enabling premise for interference alignment in all the preceding examples is the relativity of alignment—i.e., the alignment of signal vector spaces is relative to the observer (the receiver). Two transmitters may appear to be accessingthe channel simultaneously to one receiver while they appear to be orthogonal to another receiver. Since each receiver has a different view, there exist scenarios where each receiver, from its own perspective, appears to be privileged relative to others. The goal of interference alignment is to create such scenarios in a wireless network. Speci cally, interference alignment refers to a construction of signals in such a manner that they cast overlapping shadows at the receivers where they constitute interference while they remain distinguishable at the receivers where they are desired. The idea of interference alignment evolved out of the degrees channel of freedom investigations on the two-user MIMO [19], [23], [24] and the compound broadcast channel [25]. The two-user channel is a communication system with two transmitters, two receivers, and four independent messages, one from each transmitter to each receiver. Taking advantage of the MAC and the broadcast channel (BC) components contained within the channel, Maddah-Ali, Motahari, and Khandani proposed an elegant coding scheme (the MMK scheme) in [23] for the two-user MIMO channel. The MMK scheme naturally combines successive decoding and dirty paper coding, the optimal schemes for the constituent MAC and BC. Interestingly, the degrees of freedom on the twoMMK scheme achieves user channel when all nodes are equipped with antennas. The key to this result is the implicit interference alignment that is facilitated by the iterative optimization of transmit precoding and receive combining vectors. The rst explicit interference alignment scheme is presented in [24] where it is shown that dirty paper coding and successive decoding are not required to achieve the maximum degrees of freedom on the two-user degrees of freedom MIMO channel. The achievability of and the converse are established in [19]. Interference alignment is used in [19], [26] to obtain innerbounds on the degrees of channel. Interference alignfreedom region of the MIMO ment is also a key ingredient of the degrees of freedom characterization of the compound broadcast channel in [25]. C. Degrees of Freedom of the User Interference ChannelIn this paper we establish that the user time-varying indegrees of terference channel de ned in Section II has freedom. Equivalently, at high SNR, every user is (simultaneously and almost surely) able to achieve reliable communication at rates approaching one half of the capacity that he could achieve in the absence of all interference. An interesting implication of this result is that time-varying interference networks are not fundamentally interference-limited. The result has the same avor as the toy examples presented earlier in this section. In both cases the conclusion is that everyone gets half the cake. While the toy examples represent contrived scenarios where the channel parameters are carefully selected to facilitate interference alignment, the degrees of freedom result is for channels whose coef cients are random, i.e., selected by nature. There is a penalty involved with random SNR , i.e., it channel coef cients, but the penalty is becomes a negligible fraction of the users’ rates at high SNR. Indeed, we expect that the rate penalty will increase with the number of users, so that it will take higher and higher SNR to approach half of each user’s capacity as the number of usersAuthorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.

3428IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 8, AUGUST 2008Fig. 1. Interference alignment on the three-user interference channel to achieve 4=3 degrees of freedom.increases. The degrees of freedom perspective is too coarse to capture this penalty and therefore does not reveal this competition among users. In this sense, the picture presented by the degrees of freedom result is optimistic. The degrees of freedom for the constant interference channel (with the exception of certain MIMO scenarios) remains an open problem for more than two users. The interference alignment schemes used in this paper are based on beamforming over multiple symbol extensions of the time-varying channel. These schemes do not exactly achieve the outerbound on the degrees of freedom for a nite symbol extension. Instead, by using longer symbol extensions we are able to approach arbitrarily close to the outerbound. Intuitively, this can be degrees understood as follows. In order to achieve exactly of freedom (per user) over a nite symbol extension, every receiver must be able to partition its observed signal space into two subspaces of equal size, one of which is meant for the desired signals and the other is the “waste basket” for all the interference terms. Moreover, the vector spaces corresponding to the interference contributed by all undesired transmitters must exactly align at every receiver within the waste basket which has the same size as each of the interference signals. It turns out this problem is overconstrained and does not admit a solution. We circumvent this problem by allowing some over ow space (a few extra symbols) for interference terms that do not align perfectly. Fortunately, we nd that the size of the over ow space becomes a negligible fraction of the total number of dimensions as we increase the size of the signal it is possible to align interference space. Thus, for any to the extent that the achieved degrees of freedom are within an fraction of the outerbound. The tradeoff is that the smallerthe value of , the larger the number of symbols (time slots) of the outerbound value per needed to recover a fraction user interference symbol. As an example, consider the channel. We are able to achieve degrees of freedom over symbol extension of the channel so that the degrees a , for any positive integer of freedom per symbol equal . By choosing large enough we can approach arbitrarily close to the outerbound of degrees of freedom. The case of is shown in Fig. 1. The gure illustrates how degrees of freedom are achieved over a symbol single antenna users, so extension of the channel with that a total of degrees of freedom are achieved per channel use. User 1 achieves degrees of freedom by transmitting two independently coded streams along the beamforming vectors while users 2 and 3 achieve one degree of freedom by sending their independently encoded data streams along the , respectively. Let us pick beamforming vectors be the vector of all ones.The remaining beamforming vectors are chosen as follows. At receiver 1, the interference from transmitters 2 and 3 are perfectly aligned At receiver 2, the interference from transmitter 3 aligns itself along one of the dimensions of the two-dimensional interference signal from transmitter 1Authorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.

CADAMBE AND JAFAR: INTERFERENCE ALIGNMENT AND DEGREES OF FREEDOM OF THE-USER INTERFERENCE CHANNEL3429 Similarly, at receiver 3, the interference from transmitter 2 aligns itself along one of the dimensions of interference from transmitter 1To obtain the converse result of Theorem 1, simply add all the inequalities from Lemma 1. This gives us (5)Remark: Note that noncausal channel knowledge is not required because of the diagonal nature of the channel matrices resulting from symbol extensions over parallel channels. Remark: Also note that in order to deliver a capacity that , i.e., in order to carry one degree of freedom, it grows as is not necessary for a beamforming vector to be orthogonal to the interference. It suf ces if the beamforming vector is linearly independent of the basis vectors of the interference signal space. Remark: Finally, note that the construction of beamforming vectors for interference alignment is not unique. For example, could be any random vector instead of the all ones vector. Moreover, at receiver 2, the interference from transmitter 3, does not necessarily have to align with one of the beams received from transmitter 1. It only needs to lie within the two-dimensional (2-D) space spanned by the two beams received from transmitter 1.(6) The Proof of Lemma 1 (for the general case where all nodes antennas) is provided in Appendix II. A sketch of the have proof is provided here. Without loss of generality, let us focus . In order to obtain the corresponding on case outerbound, consider any reliable coding scheme for the user interference channel. Now, suppose we eliminate messages , i.e., we use a pre-determined sequence of bits known to all the transmitters and receivers in place of . Then all these messages so that receivers can subtract out the signals received from transmit. This is equivalent to a two user interference ters channel, where receiver 1 and 2 receive signals only from and , respectransmitters 1, 2, and decode messages tively. Next we argue that this two user interference channel can only have one degree of freedom. This argument proceeds as follows. to receiver 2. Because receiver Let us provide message 2 has complete knowledge of all channel coef cients and the , we can eliminate the channel between transmitter message 1 and receiver 2. Because the coding scheme is a reliable coding scheme by assumption, receiver 1 is also capable (with high , its desired message. In that case, probability) of decoding we can also eliminate the channel from transmitter 1 to receiver 1. Then we end up with each receiver seeing only transmitter 2’s signal with noise. For each channel use, we make sure that receiver 1 has the better channel by reducing noise variance if necessary. Thus, the signal at receiver 2 is a degraded version of the signal at receiver 1. We argue that if receiver 2 can de, receiver 1 must also be able to decode code its message with a high probability. Finally, the closing argument is that since receiver 1 (with possibly reduced noise) is able to decode for any reliable coding scheme, the rates both messages must lie in the capacity region of the multiple access channel from transmitters 1, 2 to receiver 1 with reduced noise at the receiver. But since this receiver has only one antenna and reducing the noise variance (by a nite amount that depends only on the channel coef cients and not on the SNR ) does not affect the degrees of freedom, the total degrees of freedom cannot be more than . This gives us the desired outer. bound of (4) for the case B. Achievability Proof for Theorem 1 With The achievability proof is presented next. Since the proof is rather involved, we present rst the constructive proof for . The proof for general is then provided in Appendix III. We show that lies in . Since the degrees of the degrees of freedom region freedom region is closed, this automatically implies thatSimilarly, at receiver 3, we only needSince in this work our interest is only in the degrees of freedom we do not consider the optimization of beamforming vectors over these possibilities. IV. DEGREES OF FREEDOM FOR THE CHANNEL USER INTERFERENCEThe following theorem presents the main result of this section. Theorem 1: The number of degrees of freedom per user for the user interference channel (de ned in Section II) is (3) A. Converse for Theorem 1 The converse argument for the theorem is a simple extension of the outerbounds presented in [18], [27] which are themselves based on Carleial’s outerbound [2]. However, because we assume that the channel coef cients are time-varying our model is different from these works which focus on constant channel coef cients. For the sake of completeness we derive the converse in this section. The converse follows from the following lemma which provides an outerbound on the degrees of freedom region of the user interference channel. Lemma 1:(4)Authorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.

3430IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 8, AUGUST 2008This result, in conjunction with the converse argument proves the theorem. lies in , we construct an To show that interference alignment scheme using only time slots. We symbols transmitted over collectively denote the time slots as a supersymbol. We call this the symbol extension of the channel. With the extended channel, the signal vector at the th user’s receiver can be expressed asIn this achievable scheme, receiver eliminates interference to decode . At receiver 1, by zero-forcing all desired streams are decoded after zero-forcing the interference to achieve degrees of freedom. To obtain interfer-dimensional received signal ence free dimensions from a , the dimension of the interference should be not vector more than . This can be ensured by perfectly aligning the interference from transmitters 2 and 3 as follows: (7) At the same time, receiver 2 zero-forces the interference from and . To extract interference-free dimensions from -dimensional vector, the dimension of the interference a . For instance has to be not more thanwhereis a column vector representing the symbol extension of the transmitted symbol , i.e.. . . This can be achieved by choosing Similarly and represent symbol extensions of and , respectively. is a diagonal the matrix representing the symbol extension of the channel as shown in the equation at the bottom of the page. is achievable on We show that lies in this extended channel implying that the degrees of freedom region of the original channel. is encoded at In the extended channel, message transmitter 1 into independent streams sent along vectors so that is and so that (8) where , means that the set of column vectors of matrix is a subset of the set of column vectors of matrix . Similarly, at receiver 3, we wish to choose and so to decode that (9) , and so that (7), Thus, we wish to pick vectors (8), (9) are satis ed. Note that the channel matrices have a almost surely. Since multiplying by a full rank full rank of matrix (or its inverse) does not affect the conditions represented by (7), (8), and (9), they can be equivalently expressed as (10) (11) (12) where (13) (14) (15) (16) The received signal at the th receiver can then be written as Note that is a matrix. and are matrices. Since all channel matrices are invertible, we and so that they satisfy (10)–(12) and then can choosewherecolumn vector and is a -dimensional matrix. Similarly and are each encoded into independent streams by transmitters 2 and , respectively. and 3 asis a. . ..... . .Authorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.

CADAMBE AND JAFAR: INTERFERENCE ALIGNMENT AND DEGREES OF FREEDOM OF THE-USER INTERFERENCE CHANNEL3431use (13)–(16) to nd follows. Let be the,and. are picked as column vector. . . We now choose and asis a root of the linear equation. 1) are 2) All the coef cients forming the linear equation in equal to , so that the singularity condition is trivially satis ed for all values of . is a random variable drawn from a continuous distriSince bution, the probability of taking a value which is equal to the root of this linear equation is zero. Therefore, the second event happens with probability greater than , and we can writeIt can be easily veri ed that , and satisfy the three equaand satisfy the intertions (10)–(12). Therefore, ference alignment equations in (7), (8) and (9). Now, consider the received signal vectors at Receiver 1. The vectors while desired signal arrives along the and the the interference arrives along the vectors vectors . As enforced by (7) the interference vectors are perfectly aligned. Therefore, in order to prove that there are interference free dimensions it suf ces to show that the -dimensional matrix columns of the square, (17) are linearly independent almost surely. Multiplying by the full and substituting the values of , rank matrix equivalently, we need to show that almost surely (see (18) at the bottom of the page) has linearly independent column vecis a diagonal matrix. In other tors where with probability 1. The words, we need to show proof is obtained by contradiction. If possible, let be singular . Furwith nonzero probability. For instance, and the ther, let the diagonal entries of be be . Then the equation diagonal entries of shown at the bottom of the page is true with nonzero probaindicate the cofactor of the th row and th column bility.Let of . Expanding the determinant along the rst row, we getConsider the equationSince the terms do not depend on , the above equation is a polynomial of degree in . Again, as before, there are two possibilities. The rst possibility is that takes a value equal to one of the roots of the above equation. Since is drawn from a continuous distribution, the probability of this event happening is zero. The second possibility is that all the coef cients of the above polynomial are zero with nonzero probability and we can writeWe have now shown that if the determinant of the matrix is equal to with nonzero probability, then the determinant of following: matrix (obtained by stripis equal to with ping off the rst row and last column of nonzero probability as shown in the equation at the bottom of the following page with probability greater than . Repeating the above argument and eliminating the rst row and last column at each stage, we get . . . . . . . . . .. . . . .with probability greater than . But this is a Vandermonde matrix and its determinantNone of “cofactor” terms in the above expansion depend and . If all values other than are given, then the on above is a linear equation in . Now, implies one of the following two events:is equal to only if for some . Since are drawn independently from a continuous distribution, they are . all distinct almost surely. This implies that(18). . .. . .. . ..... . .. . .. . ..... . .Authorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.

3432IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 8, AUGUST 2008Thus, the vectors carrying the desired signal at receiver 1 are linearly independent of the interference vectors which allows the receiver to zero force interference and obtain interference free dimensions, and therefore degrees of freedom for its message. At receiver 2 the desired signal arrives along the vectors while the interference arrives along the vectors and the vectors . As enforced by (8) the are perfectly aligned within the interference vectors . Therefore, in order to prove that interference vectors there are interference free dimensions at receiver 2 it suf ces to show that the columns of the square, -dimensional matrix (19) are linearly independent almost surely. This proof is quite similar to the proof presented above for receiver 1 and is therefore omitted to avoid repetition. Using the same arguments we can show that both receivers 2 and 3 are able to zero force the interference vectors and obtain interference free dimensions for their respective desired signals so that they each achieve degrees of freedom. Thus we established the achievability of for any . This scheme, along with the converse automatically imply thatFig. 2. Degrees of Freedom Region for the three-user interference channel.achievability as follows. Let be the degrees of freedom region of the three-user interference channel. We need to prove . We show that which along with the conthat verse proves the stated result. The points can be veri ed to lie in through trivial achievable schemes. Also, lies in (Note that Theorem 1 implies that this is the only point which achieves a total of degrees of freedom and satis es the inequalities in (20).)f Consider any as de ned by the statement of the thepoint can then be shown to lie in a convex orem. The point , J, K, L, and N. For inregion whose corner points are stance, can be expressed as a convex combination of the end points (see Fig. 2)C. The Degrees of Freedom Region for the 3 User Interference Channel Theorem 2: The degrees of freedom region of the three-user interference channel is characterized as follows:(20) Proof: The converse argument is identical to the converse argument for Theorem 1 and is therefore omitted. We showwhere the constants are de ned as shown in the table at the bottom of the page. are nonnegative for It is easily veri ed that the values of and that they add up to one. Thus, all points all in are convex combinations of achievable points. . .. . .. . ..... . .. . .. . ..... . .Authorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.

CADAMBE AND JAFAR: INTERFERENCE ALIGNMENT AND DEGREES OF FREEDOM OF THE-USER INTERFERENCE CHANNEL3433and . Since convex combinations are achievable by time . Tosharing between the end points, this implies that and the proof is gether with the converse, we have complete. The assumption of time varying channels is intriguing degrees of freedom will be because it is not clear if achieved with constant channels. Therefore, the validity of the Host–Madsen–Nosratinia conjecture [18] remains unknown. On the one hand the number of degrees of freedom is a discontinuous measure as evident from the point to point channel where it represents the rank of the channel matrix. Therefore the constant coef cient case may be of limited signi cance. On the other hand, the constant channel case may shed light on novel interference alignment schemes such as interference alignment in the signal “level” dimension as demonstrated for certain special cases in [22] and interference alignment through lattice codes as demonstrated for the one-sided interference channel in [21]. Next we discuss the relationship between degrees of freedom capacity characterization. and an D. The Capacity Approximation provide a capacity approximation , i.e. (21) is more accuIn general, a capacity approximation within . However, it turns rate than an approximation within out that in many cases the two are directly related. For example, it is well known that for the full rank MIMO channel with input antennas and output antennas, transmit power and i.i.d. zero mean unit variance additive white Gaussian noise may be expressed (AWGN) at each receiver, the capacity as (22) A similar relationship between the degrees of freedom and the capacity characterization also holds for the MIMO multiple access channel, the MIMO broadcast channel, and the twouser MIMO interference channel. For the MIMO, MAC, and BC, the outerbound on sum capacity obtained from full cooper. The ination among the distributed nodes is nerbound obtained from zero forcing is also so that we can write . For the two user MIMO interference channel and the two-user MIMO channel the outerbound is obtained following an extension of Carleial’s outerbound [2] which results in a MIMO MAC channel. The innerbound is obtained from zero forcing. Since of we can both of these bounds are within . However, consider similarly write user interference channel with single antennas at each the node. In this case, we have only shown (23) To claim that capacity of the user interference channel is within we need to show an innerbound. Since our achievable schemes of are based on interference alignment and zero forcing, the natural question to ask is whether an interference alignment and degrees of zero forcing based scheme can achieve exactly case to freedom. The following explanation uses the suggest that the answer is negative. symbol exConsider an achievable scheme that uses a tension of the channel. Now, consider a point that can be achieved over this extended channel using interference alignment and zero-forcing alone. If possible, let the total de. For ingrees of freedom over this extended channel be stance, . It can be argued along the is same lines as the converse part of Theorem 1 that achievable in the two-user interference channel for . ThereforeThe degrees of freedom that is accurate withinIt can be easily seen that the only point that satis es the above inequalities and achieves a total of degrees . Therefore, any scheme that achieves of freedom is degrees of freedom over the extended channel a total of . achieves the point We assume that the messages are encoded along independent streams similar to the coding scheme in the proof of Theorem 1, i.e.Now, at receiver 1, to decode an -dimensional signal using zero-forcing, the dimension of the interference has to be at most . For instance (24) Note that since column vectors and has linearly independent is full rank with probability , . Similarly, the dimension of the . Therefore, interference from transmitter 3 is also equal to the two vector spaces on the left-hand side of (24) must have full intersection, i.e., span span span span span span At receiver At receiver (25) (26) (27)represents the space spanned by the column vecwhere span tors of matrix The above equations imply that span span span spanwhere . The above equation implies that there exists at least one . Note that since all channel eigenvector of in matrices are diagonal, the set of eigenvectors of all channelAuthorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.

3434IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 8, AUGUST 2008matrices, their inverses and their products are all identical to the set of column vectors of the identity matrix. For instance, . Therefore is an vectors of the form eigenvector for all channel matrices. Since lies in span , (25)–(27) imply that, span span spanantennas and constant channel coef cients. It is not with users. However, known if the result can be extended to with time-variations it is easy to nd the degrees of freedom for antennas at each node. the user interference channel with The result follows directly from Theorem 1 and is presented in the following Corollary. user interference channel Corollary 1: The time-varying antennas at each node has degrees of freedom. with Proof: The converse for Corollary 1 is already derived in Appendix 1 in (31). Achievability of Corollary 1 is also straightforward. Suppose colocated antennas at a node as a sepwe view each of the arate node. In other words we do not allow joint processing of signals obtained from the co-located antennas. Then, instead of user interference channel with antenna nodes we oba user interference channel with single antenna nodes. tain a degrees of But the result of Theorem 1 establishes that freedom are achievable on this interference channel. Thus, we degrees of freedom on the user incan also achieve antenna nodes. terference channel with Last, let us consider the most general user interference channel where each node is equipped with possibly different number of antennas. In this case also a lower bound on the degrees of freedom is directly established from the result of Theorem 1. The following Corollary states this result. user Corollary 2: The total degrees of freedom for the antennas and interference channel where transmitter has receiver has antennas is bounded below asTherefore, at receiver 1, the desired signal is not lin. Therefore, early independent with the interference completely by merely zero-forcing receiver 1 cannot decode the interference signal. Evidently, interference alignment in the degrees of manner described above cannot achieve exactly freedom on the 3 user interference channel with a single antenna at all nodes. We explore this interesting aspect of the three-user interference channel further in the context of multiple antenna nodes. degrees of freedom Our goal is to nd out if exactly antennas at each node. As shown by may be achieved with the following theorem, indeed we can achieve exactly degrees of freedom so that the capacity characterization is indeed related to the degrees of freedom as for . V. DEGREES OF FREEDOM FOR THE INTERFERENCE CHANNEL WITH MULTIPLE ANTENNA NODES A. The Three-User Interference Channel With Antennas at Each Node and Constant Channel Coef cients The three-user MIMO interference channel is interesting bedecause in this case we show that we can achieve exactly grees of freedom with constant channel matrices, i.e., time-variations are not required. This gives us a lowerbound on sum ca. Since the outerbound on pacity of we have an sum capacity is also approximation to the capacity of the three-user MIMO interferantennas at all nodes. ence channel with Theorem 3: In a three-user interference channel with antennas at each transmitter and each receiver and constant comay be characterized (almost ef cients, the sum capacity surely) as (28) The outerbound follows directly from [27] which shows that the two-user interference channel with antennas at each node and constant channel coef cients has only degrees of freedom. In the three-user case, we eliminate one message at a time to obtain . Adding inequalities up all three inequalities we obtain the converse. The proof is presented in Appendices IV and V. B. The Nodes User Interference Channel With Multiple Antenna(29) Thus, no more than half the degrees of freedom are lost on the user interference channel with multiple antenna nodes. Proof: The achievability proof is straightforward as, once again, the th transmitter receiver pair can be replaced single antenna transmitter and receiver with nodes by only allowing distributed processing of signals at each antenna and discarding the remaining antennas. Thus, we obtain an interference channel with transmitters and receivers, each equipped with only a single antenna. The achievability of degrees of freedom on this interference channel then follows from the result of Theorem 1. Note that Corollary 2 only establishes an innerbound and is not always tight. For example, consider the two-user interference channel where each transmitter has two antennas while each receiver has only 1 antenna. While Corollary 2 only shows achievability of degree of freedom for this channel, it is known that this interference channel has degrees of freedom [27]. However, Corollary 2 is interesting because it shows that interference cannot reduce the degrees of freedom of the interference channel by more than half compared to when each transmitter and receiver is able to operate without interference from other users.Theorem 3 in the preceding section shows that degrees of freedom are achievable on the three-user interference channelAuthorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.

CADAMBE AND JAFAR: INTERFERENCE ALIGNMENT AND DEGREES OF FREEDOM OF THE-USER INTERFERENCE CHANNEL3435Fig. 3. Interference Alignment: Everyone gets half the cake.VI. CONCLUSION We have shown that with perfect channel knowledge the user interference channel has (almost surely) degrees of freedom when the channel coef cients are time-varying and are generated from a continuous distribution. The key idea is interference alignment which maximizes the overlap between the signal spaces of all interference signals at each receiver so that the size of the interference-free space is maximized for the desired signal. Due to relativity of alignment, it is possible that signals align at the receivers where they are not desired and remain distinguishable at the receivers where they are desired. Somewhat surprisingly it is shown that all the interference can be concentrated roughly into one half of the signal space at each receiver, leaving the other half available to the desired signal and free of interference. The alignment can be accomplished for any number of users but as the number of users increases a larger signal space is needed for each user to recover nearly half of it. While this work shows the potential bene ts of interference alignment, several challenges must be overcome before these bene ts translate into practice. One key issue is the assumption of global channel knowledge. While a node may acquire channel state information for its own channels, it is much harder to learn the channels between other pairs of nodes with which this node is not directly associated. On the other hand, global channel knowledge may not be necessary if there is a feedback channel through which the receivers can guide the transmitters into aligned con gurations in real time by applying incremental corrections. Also iterative algorithms based on channel reciprocity may be able to align interference in a distributed fashion [28]. The key insight of this paper is the role of interference alignment in a wireless network. From a capacity perspective the idea of interference alignment reaf rms the need for structured codes in wireless networks, also pointed out by [29]. For the single user point to point Gaussian channel it is well known that the capacity can be achieved through random (Gaussian) codebooks as well as through structured (lattice) codes. There is a growing realization that structured codes, optional for the single user case, may be necessary for approaching the capacityof networks. In an interference network when we design one user’s codebook we are also designing the interference/noise that will be seen by other users. Having structure in the interference may therefore be necessary. It is the structure imposed on the transmitted signals that facilitates interference alignment in this work. The intuition from this work is that since random codes will not automatically align themselves, structured codes will be necessary for wireless networks. Indeed interference alignment at the codeword level has been shown to be optimal in the capacity sense in [21] and in the degrees of freedom sense in [22] for some interesting cases. A combination of Han–Kobayashi [3] type achievable schemes and structured codes is a promising avenue in the quest for the capacity of wireless networks. APPENDIX I EXAMPLE: INTERFERENCE ALIGNMENT VIA DELAY OFFSETS Consider the -user interference network shown in Fig, 3, where there is a propagation delay associated with each channel. In particular, let us assume that the propagation delay is equal to one symbol duration for all desired signal paths and two symbol durations for all paths that carry interference signals. is de ned as The channel output at receiver (30) where during the th time slot (symbol duration) transmitter sends symbol and is i.i.d. zero mean unit variance Gaussian noise (AWGN). All inputs and outputs are complex. The transmit power at each transmitter is E . In the absence of interference, each user . Now, with all would achieve a capacity of the interferers present, suppose each transmitter transmits only ) and is silent during the during odd time slots (with power even time slots. Let us consider what happens at receiver 1. The symbols sent from its desired transmitter (transmitter 1) are received free from interference during the even time slots and all the undesired (interference) transmissions are received simultaneously during the odd time slots. Thus, each user is able to access the channel one-half of the time with no interference from other users. Each user achieves a rateAuthorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.

3436IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 8, AUGUST 2008where the pre-log factor of denotes the degrees of freedom is also found achieved by each user. The sum-rate to be the capacity by a converse argument that is nearly identical to the converse for the phase-alignment example. APPENDIX II CONVERSE FOR LEMMA 1 We present the proof for the case that all nodes are equipped antennas. In this case the statement of the lemma bewith comesis strictly positive with probability . Here refers to are the smallest eigenvalue of matrix . mutually independent and jointly Gaussian. Consider any reliable coding scheme for this interference channel, spanning channel uses. We use the notation to indicate the vector of values taken by variable for . Starting from Fano’s inequality, we have(31) and eliminate messages We consider the case , leaving us with a two-user MIMO interference channel. The following converse holds for both time-varying and constant channel coef cients. The channel input-output equations are written equivalently as: (32) (33) With probability one the channel matrices are invertible. So we can equivalently write (34) (44)(43)(35) where (36) (45) (37) Since the capacity of the interference channel depends only on the noise marginals, we assume without loss of generality that (38) (39) where (40) (41) where the last step follows from the known result that the sum capacity of a multiple access channel with an andegrees of tenna receiver can only contribute at most . Similarly, for any freedom. Thus, we have we obtain . Finally, adding up all the outerbounds in (4), we obtain the converse statement for the degrees of freedom of the user interference antennas at each node channel with (48) APPENDIX III ACHIEVABILITY FOR THEOREM 1 FOR ARBITRARY Let . We show that lies in the degrees of freedom (46) (47)(42) andAuthorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.

CADAMBE AND JAFAR: INTERFERENCE ALIGNMENT AND DEGREES OF FREEDOM OF THE-USER INTERFERENCE CHANNEL3437region of theuser interference channel for anywhereencoded intoindependent streams by transmitter asThe received signal at the th receiver can then be written as This implies thatWe provide an achievable scheme to show that lies in the degrees of freedom region symbol extension of the original of an channel which automatically implies the desired result. In the extended channel, the signal vector at the th user’s receiver can be expressed asAll receivers decode the desired signal by zero-forcing the interferinterference vectors. At receiver 1, to obtain ence free dimensions corresponding to the desired signal from -dimensional received signal vector an , the dimension of the interference should be not more than . This can be ensured by perfectly aligning the interference as follows: from transmitters(49) At the same time, receiver 2 zero-forces the interference from . To extract interference-free dimensions from a -dimensional vector, the dimension of . the interference has to be not more than so that This can be achieved by choosingwhere is an column vector representing the symbol extension of the transmitted symbol , i.e.. . .. . . (50) Notice that the above relations align the interference from transmitters within the interference from transmitter 1 at receiver 2. Similarly, to decode at receiver when we so that the following relations are wish to choose satis ed. (51) so that (49), We now wish to pick vectors have a (50), and (51) are satis ed. Since channel matrices almost surely, (49), (50) and (51) can be equivfull rank of alently expressed asSimilarly and represent symbol extensions of the and , respectively. is a diagonal masymbol extension of the channel as trix representing the shown in the equation at the bottom of the page. Recall that the are drawn independently from a condiagonal elements of tinuous distribution and are therefore distinct with probability . case, message is In a manner similar to the encoded at transmitter 1 into independent streams along vectors so that iswhereis a column vector and -dimensional matrix. Similarlyis a isAt receiver (52). . ..... . .Authorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.

3438IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 8, AUGUST 2008For example, if . . . At receiver (53) aswe get.andare chosen. . . At receiver where . . . (54) where (55)To clarify the notation further, consider the case where . consists of exactly one element, i.e., Assuming . The set consists of all column vectors of the form where all take values 0, 1. and can be veri ed to have and elements, respectively. are chosen using (52). Clearly, forNow, for(56)(57) , the identity matrix. We now Note that choose and so that they satisfy the relations in (53)–(54) and then use equations in (52) to . Thus, our goal is to nd madetermine and so that tricesfor all Letbe the. column vector. . .We need to choose for . The sets of column vectors of and where be equal to the sets andcolumn vectors are chosen toThus, the interference alignment conditions (52)–(54) are satis ed. Through interference alignment, we have now ensured that the dimension of the interference is small enough. We now need to verify that the components of the desired signal are linearly independent of the components of the interference so that the signal stream can be completely decoded by zero-forcing the interference. Consider the received signal vectors at receiver 1. vectors . The desired signal arrives along the As enforced by (52), the interference vectors from transmitare perfectly aligned with the interference from ters transmitter 2 and therefore, all interference arrives along the vectors . In order to prove that there are interference free dimensions it suf ces to show that the columns -dimensional matrix of the square, (58) are linearly independent almost surely. Multiplying the above matrix with and substituting for and , we get a matrix whose th row has entries of the formsandwhereand and are drawn independently from a continuous distribution. The same iterative argument as in Section IV-B can be used. For instance, expanding the corresponding determinantAuthorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.

CADAMBE AND JAFAR: INTERFERENCE ALIGNMENT AND DEGREES OF FREEDOM OF THE-USER INTERFERENCE CHANNEL3439along the rst row, the linear independence condition boils down to one of the following occurring with nonzero probability: being equal to one of the roots of a linear equation; 1) 2) the coef cients of the above mentioned linear equation being equal to zero. Thus the iterative argument can be extended here, stripping the last row and last column at each iteration and the linear independence condition can be shown to be equivalent to the linear matrix whose rows are of the form independence of a where . Note that this matrix is a more general version of the Vandermonde matrix obtained in Section IV-B. So the argument for case does not extend here. However, the iterative prothe cedure which eliminated the last row and the last column at each iteration, can be continued. For example, expanding the determinant along the rst row, the singularity condition simpli es to one of the following: being equal to one of the roots of a nite degree poly1) nomial; 2) the coef cients of the above mentioned polynomial being equal to zero Since the probability of condition 1 occurring is , condition 2 must occur with nonzero probability. Condition 2 leads to a and thus the iterpolynomial in another random variable ative procedure can be continued until the linear independence macondition is shown to be equivalent almost surely to a trix being equal to . Assuming, without loss of generality, that we placed the in the rst row (this corresponds to the term ), the linear independence condition boils with nonzero probability—an down to the condition that obvious contradiction. Thus, the matrixThe signal received at receiver can be written asAll receivers cancel the interference by zero-forcing and then streams along decode the desired message. To decode the from the components of the rethe column vectors of ceived vector, the dimension of the interference has to be less . The following three interference alignthan or equal to ment equations ensure that the dimension of the interference is at all the receivers. equal to span span (59) (60) (61)where span represents the vector space spanned by the column vectors of matrix We now wish to choose so that the above equations are satis ed. Since have a full rank of almost surely, the above equations can be equivalently represented as span span (62) (63) (64)whereLet to be can be shown to be nonsingular with probability 1. Similarly, the desired signal can be chosen to be linearly independent of the interference at all other receivers almost lies surely. Thus in the degrees of freedom region of the user interference channel and therefore, the user interference channel has degrees of freedom. Then andbe theeigenvectors of. Then we setare found using (62)–(64). Clearly, satisfy the desired interference alignment (59)–(61). Now, to decode the message using zero-forcing, we need the desired signal to be linearly independent of the interference at the receivers. For example, at receiver 1, we to be linearly independendent need the columns of almost surely. i.e., we need the with the columns of matrix below to be of full rank almost surelyAPPENDIX IV PROOF OF THEOREM 3 FOREVEN Substituting values for and in the above matrix, and , the linear indepenmultiplying by full rank matrix dence condition is equivalent to the condition that the column vectors of are linearly independent almost surely, where . is a random (full This is easily seen to be true because rank) linear transformation. To get an intuitive understanding of . the linear independence condition, consider the case of Let represent the line along which lies the rst eigenvectorProof: To prove achievability we rst consider the case is even. Through an achievable scheme, we show that when noninterfering paths between transmitter and there are receiver for each resulting in a total of paths in the network. for receiver using Transmitter transmits message independently encoded streams over vectors , i.e.,Authorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.

3440IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 54, NO. 8, AUGUST 2008(72)matrix . The probability of a random of the random of being collinear with is zero. rotation (and scaling) Using a similar argument, we can show that matrices The above equations imply that and span span(66) (67)(68) (69) (70)have a full rank of almost surely and therefore receivers 2 streams of and using zeroand 3 can decode the interference free transmissions per forcing. Thus, a total channel-use are achievable with probability and the proof is complete. APPENDIX V PROOF OF THEOREM 3 FORwhereODDProof: Consider a two time-slot symbol extension of the channel, with the same chanel coef cients over the two symbols. It can be expressed asand and are block-diagonal matrices representing the symbol extension of and , respectively. be the eigen vectors of . Then, we pick Let to be (71)where is a vector that represents the two symbol symbol symbol , i.e. extension of the transmittedcase, and are then determined by As in the even using (68)–(70). Now, we need the desired signal to be linearly independent of the interference at all the receivers. At receiver 1, the desired linear independence condition boils down to span where and is the two-symbol diis an matrix. agonal extension of . Notice that The linear independence condition is equivalent to saying that matrix are indeall the columns of the following pendent as shown in (72) at the top of the page. We now argue that the probability of the columns of the above matrix being denote the linearly dependent is zero. Let columns of the above matrix. Suppose the columns are linearly dependent, thenwhere is an vector representing the vector transmitted at time slot by transmitter . Similarly and represent the two symbol extensions of the received symbol and the noise vector respectively at receiver . is block diagonal matrix representing the extension a of the channelWe will now show lies in the degrees of freedom region of this extended channel channel with an achievable degrees of freedom scheme, implying that that a total of are achievable over the original channel. Transmitter transfor receiver using independently encoded mits message , i.e. streams over vectorsLetwhere is a matrix and is a vector independent streams. The following three inrepresenting terference alignment equations ensure that the dimension of the at receivers 1, 2, and 3 interference is equal to (65)Now, there are two possibilities . This implies that either one of the fol1) lowing sets of vectors is linearly dependent. Note that both sets are can be expressed as the union of eigen vectors of a) A set of b) A random transformation of this set.Authorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.

CADAMBE AND JAFAR: INTERFERENCE ALIGNMENT AND DEGREES OF FREEDOM OF THE-USER INTERFERENCE CHANNEL34412)An argument along the same lines as the even case leads to the conclusion that the probability of the union of the two sets listed above being linearly dependent in a -dimensional space is zero. or . This implies that span span span spanspan Also, spanspanspanspanNote that and are -dimensional spaces. (The is handled case where their dimensions are less than in the rst part). Also, and are drawn from completely has a different set of vectors. Therefore, the union of rank of almost surely. Equivalently, span span has a dimension of almost surely. Since the set is drawn from an eigen vector that does not exist in either or , the probability of the 2-D space span intersecting with the -dimensional is zero. For example, if , let indispace cate the line formed by the intersection of the two planes and . The probability that line lies in the plane formed by . Thus, the probability that the desired signal lies in the span of the interference is zero at receiver 1. Similarly, it can be argued that the desired signal is independent of the interference at receivers 2 and 3 almost surely. Therefore, is achievable over the two-symbol extended degrees of freedom are achievable channel. Thus antenna at over the 3 user interference channel with each transmitting and receiving node. ACKNOWLEDGMENT The authors would like to acknowledge many helpful discussions with Prof. Shlomo Shamai that have guided this work. REFERENCES[1] A. B. Carleial, “A case where interference does not reduce capacity,” IEEE Trans. Inf. Theory, vol. 21, pp. 569–570, 1975. [2] A. B. Carleial, “Interference channels,” IEEE Trans. Inf. Theory, vol. 24, no. 1, pp. 60–70, 1978. [3] T. Han and K. Kobayashi, “A new achievable rate region for the interference channel,” IEEE Trans. Inf. Theory, vol. 27, pp. 49–60, Jan. 1981.[4] H. Sato, “The capacity of the Gaussian interference channel under strong interference,” IEEE Trans. Inf. Theory, vol. 27, pp. 786–788, Nov. 1981. [5] M. Costa, “On the Gaussian interference channel,” IEEE Trans. Inf. Theory, vol. 31, pp. 607–615, Sep. 1985. [6] G. Kramer, “Feedback strategies for white Gaussian interference networks,” IEEE Trans. Inf. Theory, vol. 48, pp. 1423–1438, Jun. 2002. [7] I. Sason, “On the achievable rate regions for the Gaussian interference channel,” IEEE Trans. Inf. Theory, vol. 50, pp. 1345–1356, Jun. 2004. [8] S. Vishwanath and S. Jafar, “On the capacity of vector Gaussian interference channels,” in Proc. IEEE Inf. Theory Workshop, Oct. 2004, pp. 365–369. [9] H. Chong, M. Motani, H. Garg, and H. El Gamal, “On the Han-Kobayashi region for the interference channel,” IEEE Trans. Inf. Theory, submitted for publication. [10] R. Etkin, D. Tse, and H. Wang, “Gaussian interference channel capacity to within one bit,” IEEE Trans. Inf. Theory, Feb. 2007, submitted for publication. [11] M. Charafeddine, A. Sezgin, and A. Paulraj, “Rate region frontiers for n user interference channel with interference as noise,” in Proc. 45th Annu. Allerton Conf. Commun., Contr. Comput., Oct. 2007. [12] C. Rao and B. Hassibi, “Gaussian interference channel at low SNR,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2004. [13] A. Motahari and A. Khandani, “Capacity bounds for the Gaussian interference channel,” IEEE Trans. Inf. Theory, submitted for publication. [14] X. Shang, G. Kramer, and B. Chen, “A new outer bound and the noisy-interference sum-rate capacity for Gaussian interference channels,” IEEE Trans. Inf. Theory, Dec. 2007, submitted for publication. [15] D. Tuninetti, “Progresses on Gaussian interference channels with and without generalized feedback,” in Proc. 2008 Inf. Theory Appl. Workshop, San Diego, CA, Jan. 2008, Univ. of California. [16] S. Yang and D. Tuninetti, “A new achievable region for interference channel with generalized feedback,” in Proc. 42nd Annu. Conf. Inf. Sci. Syst. (CISS), Mar. 2008. [17] V. Annapureddy and V. Veeravalli, “Gaussian interference networks: Sum capacity in the low interference regime and new outer bounds on the capacity region,” IEEE Trans. Inf. Theory, Feb. 2008, submitted for publication. [18] A. Host-Madsen and A. Nosratinia, “The multiplexing gain of wireless networks,” in Proc. ISIT, 2005. [19] S. Jafar and S. Shamai, “Degrees of freedom region for the MIMO X channel,” arXiv:cs.IT/0607099v3, May 2007. [20] V. Cadambe and S. Jafar, “Multiple access outerbounds and the inseparability of parallel interference channels,” IEEE Trans. Inf. Theory, Jul. 2007, submitted for publication. [21] G. Bresler, A. Parekh, and D. Tse, “Approximate capacity of the many-to-one interference channel,” in Proc. Allerton Conf., Sep. 2007. [22] V. Cadambe, S. Jafar, and S. Shamai, “Interference alignment on the deterministic channel and application to Gaussian networks,” arxiv:0711.2547. [23] M. Maddah-Ali, A. Motahari, and A. Khandani, “Signaling over MIMO multi-base systems—Combination of multi-access and broadcast schemes,” in Proc. ISIT, 2006, pp. 2104–2108. [24] S. Jafar, Degrees of Freedom on the MIMO X Channel-Optimality of the MMK Scheme Tech. Report, arXiv:cs.IT/0607099v2, Sep. 2006. [25] H. Weingarten, S. Shamai, and G. Kramer, “On the compound MIMO broadcast channel,” in Proc. Annu. Inf. Theory Appl. Workshop, San Diego, CA, Jan. 2007, Univ. of California. [26] M. Maddah-Ali, A. Motahari, and A. Khandani, Communication Over X Channel: Signaling and Performance Analysis Unive. Waterloo, Waterloo, ON, Canada, Tech. Rep. UW-ECE-2006-27, Dec. 2006. [27] S. Jafar and M. Fakhereddin, “Degrees of freedom for the mimo interference channel,” IEEE Trans. Inf. Theory, vol. 53, pp. 2637–2642, Jul. 2007. [28] K. Gomadam, V. Cadambe, and S. Jafar, “Approaching the capacity of wireless networks through distributed interference alignment,” presented at the GLOBECOM 2008, Mar. 2008. [29] B. Nazer and M. Gastpar, “The case for structured random codes in network communication theorems,” in Proc. IEEE Inf. Theory Workshop, Sep. 2007.Authorized licensed use limited to: Harbin Institute of Technology. Downloaded on June 01,2010 at 01:21:44 UTC from IEEE Xplore. Restrictions apply.

本文来源：https://www.bwwdw.com/article/kog4.html