Interference Alignment and Degrees of Freedom of the K-User(5)

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.