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

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.