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.