Time It

Can *** speakers talk for **-minutes each

in one room within one hour and with zero interference

to each other s audience?

Viveck R. Cadambe, Syed A. Jafar

Electrical Engineering and Computer Science

University of California Irvine,

Irvine, California, 92697, USA

Email: ********@***.***, ****@***.***

Abstract

While the best known outerbound for the K user interference channel states that there cannot be more than K/2

degrees of freedom, it has been conjectured that in general the constant interference channel with any number of

users has only one degree of freedom. In this paper, we provide a toy example (with carefully selected propagation

delays) to show how regardless of the number of interfering users K, each user can access 1/2 of the degrees of

freedom available to him in the absence of interference. To answer the question in the title, each of the 100 speakers

can talk for half the time with no interference to each other s audience. For the classical interference channel model

without delays and with constant channel coef cients randomly drawn from a continuous distribution, we show that

the 3 user interference channel with M > 1 antennas at each node almost surely has 3M/2 degrees of freedom.

I. T OY E XAMPLE

Consider the following toy problem motivated by the wireless interference channel. We wish to organize a

conference in a room with K speakers who will present their talks to their disjoint audiences. Each audience

member must be able to hear his desired speaker with absolutely no interference from other speakers. Everyone

is within earshot of each other so that if one person speaks he will be heard by everyone in the room. To be fair

we require that each speaker should be allowed equal amount of time to talk to his audience. Then the question is

the following: What is the maximum amount of time that each speaker can talk while causing no interference to

another speaker s audience?

The best solution, according to conventional wisdom is to let each speaker talk for 1/K fraction of the total

session time. This corresponds to the philosophy of time division multiple access (TDMA) in wireless networks.

However, we claim that each speaker can (in theory) talk for 1/2 of the total time without causing any interference

to each other s audience.

The key to the solution lies in the propagation delay between the time a speaker speaks and an audience member

is able to hear the speaker s voice, and the ability of the conference organizers to con gure the locations for

the audience members and the locations of the speakers. Suppose the locations of the speakers and the audience

members are chosen such that the propagation delay between each speaker and his desired audience members is an

even multiple of a basic time unit T o and the propagation delay between each speaker and each of his unintended

audience members is an odd multiple of T o . Assuming such a seating arrangment is possible, the communication

scheme is quite simple. Suppose time is slotted with each slot having width T o . Starting with the 0 th time slot,

all speakers talk simultaneously over all even time slots. All audience members listen only in even time slots as

well. Now, because the delay between an audience member and an undesired speaker is an odd multiple of T o and

the speaker speaks only on even time instants, the undesired speakers voice reaches the audience member only

over odd time slots when he is not listening. However, the desired speakers voice reaches the audience member in

an even slot when he is listening. Thus, each audience member is able to hear only his desired speaker with zero

interference from other speakers. Also, since each speaker talks during all even time slots, each speaker talks for

half the time. Thus, in theory one could have a 1 room, 1 hour conference with any number (e.g. 100) of concurrent

talks of 30 minutes each where all speakers are heard without interference by their intended disjoint set of audience

members.

The toy example serves to illustrate the important principle of interference alignment recently discovered for

wireless networks [1] [5]. Because all the interference signals overlap as heard by each audience member it is as

if there is only one interferer and one desired signal which can be orthogonalized by a 1/2 time sharing.

II. C LASSICAL MIMO I NTERFERENCE C HANNEL

Moving on from the toy example to the communication channel behind it, we are interested in the interference

channel. While the toy example uses the propagation delay to achieve interference alignment we are now interested

in the information theoretic Gaussian interference channel model where delay is ignored. In other words, all

simultaneously transmitted signals arrive simultaneously at all receivers. Speci cally, consider the K = 3 user

interference channel, comprised of 3 transmitters and 3 receivers. Each node is equipped with M antennas. The

channel output at the k th receiver over the t th time slot is described as follows:

Y [k] (t) = H [k1] X [1] (t) + H [k2] X [2] (t) + H [k3] X [3] (t) + Z [k] (t)

[k ]

where, k {1, 2,, K } is the user index, t N is the time slot index, Y (t) is the M 1 output signal vector

th [k ] th

transmitter, H [kj ] is the M M channel

(t) is the M 1 input signal vector of the k

of the k receiver, X

fade coef cient matrix from transmitter j to receiver k and Z [k] (t) is the additive white Gaussian noise (AWGN)

vector at the k th receiver. The channel coef cients are assumed constant in time. We assume all noise terms are

i.i.d. (independent identically distributed) zero mean complex Gaussian with unit variance. We assume all channel

coef cients H [kj ] are known a-priori to all transmitters and receivers. To avoid degenerate channel conditions (e.g.

all channel coef cients are equal or channel coef cients are equal to either zero or in nity) we assume that the

channel coef cient values for each frequency slot are drawn i.i.d. from a continuous distribution and the absolute

value of all the channel coef cients is bounded between a non-zero minimum value and a nite maximum value.

Note that since the channel values are assumed constant in time, the time index t is sometimes suppressed for

compact notation.

We assume that transmitters 1, 2, 3 have independent messages W 1, W2, W3 intended for receivers 1, 2, 3, respec-

tively. The total power across all transmitters is assumed to be equal to . We indicate the size of the message set

log Wi

by Wi . For codewords spanning t 0 channel uses, the rates R i = are achievable if the probability

t0

of error for all messages can be simultaneously made arbitrarily small by choosing an appropriately large t 0 .

The capacity region C of the three user interference channel is the set of all achievable rate tuples R =

(R1, R2, R3 .

Like the toy example we want to nd out how many links can be established without making the system

interference limited, i.e., each transmitter receiver pair must be unaffected by the interference power. The appropriate

tool for this purpose is the number of degrees of freedom.

A. Degrees of Freedom Region

Similar to the degrees of freedom region de nition for the MIMO X channel in [4] we de ne the degrees of

freedom region D for the 3 user interference channel as follows:

(d1, d2, d3 ) R3 : (w1, w2, w3 ) R3

D= + +

1

w1 d1 + w2 d2 + w3 d3 lim sup sup [w1 R1 + w2 R2 + w3 R3 ] (1)

log R C Note that the total number of degrees of freedom measures the number of interference free links that can be created

between the 3 sources and the 3 destinations.

For K = 2 users it is known that the interference network has only 1 degree of freedom [6], [7] per orthogonal

time and frequency dimesion. There are no known results to show that more than 1 degree of freedom is achievable

on the interference channel with any number of users. It is conjectured in [8] that the K user interference channel

(with only one frequency slot) has only 1 degree of freedom. Yet, the best known outerbound for the number of

degrees of freedom with K interfering nodes is K/2, also presented in [8]. The unresolved gap between the inner

and outerbounds highlights our lack of understanding of the capacity of wireless networks because even the number

of degrees of freedom, which is the most basic characterization of the network capacity, remains an open problem.

It is this open problem that we pursue in this paper, speci cally for the case when K = 3 and all transmitters

and receivers have M > 1 antennas. Note that for K = 2 interfering users with M antennas at each node, the

maximum number of degrees of freedom is only M, which is the same as with K = 1, i.e. if only one user is

allowed to transmit at a time in the manner of TDMA. However, as we show in this paper, for K = 3 and M > 1

the situation is remarkably different as the maximum number of degrees of freedom is 3M/2 and not just M .

The following theorem presents the main result of this paper.

Theorem 1: The number of degrees of freedom for the 3 user interference channel with M > 1 antennas at all

nodes is 3M/2 with probability 1.

max d1 + d2 + d3 = 3M/2 (2)

d D

The outerbound is straightforward - adding the degrees of freedom outerbounds d i + dj M (for i = j ) obtained

by considering two users at a time we obtain max d D d1 + d2 + d3 3M/2. The achievability proof is as follows.

III. P ROOF OF T HEOREM 1 FOR M EVEN

Proof:

To prove achievability we rst consider the case when M is even. Through an achievable scheme, we show that

there are M/2 non-interfering paths between transmitter i and receiver i for each i = 1, 2, 3 resulting in a total of

3M/2 paths in the network.

Transmitter i transmits message W i for receiver i using M/2 independently encoded streams over vectors v [i]

i.e

M/2

[i]

x[i] (t)vm] = V[i] Xi (t), i = 1, 2, 3

[i

X (t) = m

m=1

The signal received at receiver i can be written as

Y[i] (t) = H[i1] V[1] X1 (t) + H[i2] V[2] X2 (t) + H[i3] V[3] X3 (t) + Zi (t)

All receivers cancel the interference by zero-forcing and then decode the desired message. To decode the M/2

streams along the column vectors of V [i] from the M components of the received vector, the dimension of the

interference has to be less than or equal to M/2. The following three interference alignment equations ensure that

the dimension of the interference is equal to M/2 at all the receivers.

span(H[12] V[2] ) = span(H[13] V[3] ) (3)

H[21] V[1] = H[23] V[3] (4)

H[31] V[1] = H[32] V[2] (5)

where span(A) represents the vector space spanned by the column vectors of matrix A We now wish to choose

V[i], i = 1, 2, 3 so that the above equations are satis ed. Since H [ij ], i, j {1, 2, 3} have a full rank of M almost

surely, the above equations can be equivalently represented as

span(V[1] ) = span(EV[1] ) (6)

V[2] FV[1]

= (7)

[3] [1]

V = GV (8)

where

= (H[31] ) 1 H[32] (H[12] ) 1 H[13] (H[23] ) 1 H[21]

E

F = (H[32] ) 1 H[31]

G = (H[23] ) 1 H[21]

Let e1, e2, . . . eM be the M eigenvectors of E. Then we set V 1 to be

V[1] = [e1 . . . e(M/2) ]

Then V[2] and V[3] are found using equations (6)-(8). Clearly, V [i], i = 1, 2, 3 satisfy the desired interference

alignment equations (3)-(5). 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 need the columns of

H[11] V[1] to be linearly independendent with the columns of H [21] V[2] almost surely. i.e we need the matrix below

to be of full rank almost surely

H[11] V[1] H[12] V[2]

Substituting values for V [1] and V[2] in the above matrix, and multiplying by full rank matrix (H [11] ) 1, the linear

independence condition is equivalent to the condition that the column vectors of

e1 e2 . . . e(M/2) Ke1 . . . Ke(M/2)

are linearly independent almost surely, where K = (H [11] ) 1 H[12] F.

This is easily seen to be true because K is a random (full rank) linear transformation. To get an intuitive

understanding of the linear independence condition, consider the case of M = 2. Let L represent the line along

which lies the rst eigenvector of the random 2 2 matrix E. The probability of a random rotation (and scaling)

K of L being collinear with L is zero.

Using a similar argument, we can show that matrices

H[22] V[2] H[21] V[1] H[33] V[3] H[31] V[1]

and

have a full rank of M almost surely and therefore receivers 2 and 3 can decode the M/2 streams of V [2] and

V[3] using zero-forcing. Thus, a total 3M/2 interference free transmissions per channel-use are achievable with

probability 1 and the proof is complete.

IV. P ROOF OF T HEOREM 1 FOR M ODD

Proof: Consider a two time-slot symbol extension of the channel. It can be expressed as

Y[k] = H[k1] X[1] + H[k2] X[2] + H[k3] X[3] + Z[k] i = 1, 2, 3

where X[i] is a 2M 1 vector that represents the two symbol extension of the transmitted M 1 symbol symbol

X[k], i.e

X[k] (2t + 1)

X[k] (t) =

X[k] (2t + 2)

where X[k] (t) is an M 1 vector representing the vector transmitted at time slot t by transmitter k . Similarly Y[k]

and Z[k] represent the two symbol extensions of the the received symbol Y [k] and the noise vector Z [k] respectively

at receiver i. H[ij ] is a 2M 2M block diagonal matrix representing the extension of the channel.

H[ij ] 0

H[ij ] =

H[ij ]

0

We will now show (M, M, M ) lies in the degrees of freedom region of this extended channel channel with an

achievable scheme, implying that that a total of 3M/2 degrees of freedom are achievable over the original channel.

Transmitter k transmits message W i for receiver i using M independently encoded streams over vectors v [k] i.e

M

X[k] = x[k] vm] = V[k] X[k]

[k

m

m=1

where V[k] is a 2M M matrix and X[ k ] is a M 1 vector representing M independent streams. The following

three interference alignment equations ensure that the dimension of the interference is equal to M at receivers 1,2

and 3.

rank[H[21] V[2] ] = rank[H[31] V[3] ] (9)

H[12] V[1] = H[32] V[3] (10)

[13] [1] [23] [2]

H V =H V (11)

The above equations imply that

span(V[1] ) = span(EV[1] ) (12)

V[2] FV[1]

= (13)

V[3] GV[1]

= (14)

where

= (H[13] ) 1 H[23] (H[21] ) 1 H[31] (H[32] ) 1 H[12]

E

F = (H[13] ) 1 H[23]

G = (H[12] ) 1 H[32]

and E, F and G are 2M 2M block-diagonal matrices representing the 2M symbol extension of E, F and G

respectively. Let e 1, e2, . . ., eM, be the eigen vectors of E. Then, we pick V[1] to be

e1 0 e3 0 eM

...

V[1] = (15)

0 e2 0 . . . e M 1 eM

As in the even M case, V[2] and V[3] are then determined by using equations (12)-(14).

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(V[1] ) span(KV[1] ) = {0}

where K = (H11 ) 1 H[21] (F) 1 and K is the two-symbol diagonal extension of K. Notice that K is an M M

matrix. The linear independence condition is equivalent to saying that all the columns of the following 2M 2M

matrix are independent.

e1 0 e3 0 eM Ke1 0 Ke3 0 KeM

... ...

(16)

0 e2 0 . . . e M 1 eM 0 Ke2 0 . . . KeM 1 KeM

We now argue that the probability of the columns of the above matrix being linearly dependent is zero. Let

ci, i = 1, 2 . . . 2M denote the columns of the above matrix. Suppose the columns c i are linearly dependent, then

2M

i i ci = 0

s.t

i=1

Let

P= {e1, e3 . . . eM 2, Ke1, . . . KeM 2 }

Q= {e2, e4 . . . eM 1, Ke2, . . . KeM 1 }

Now, there are two possibilities

1) M = 2M = 0. This implies that either one of the following sets of vectors is linearly dependent. Note that

both sets are can be expressed as the union of

a) A set of (M/2) eigen vectors of E

b) A random transformation K of this set.

An argument along the same lines as the even M case leads to the conclusion that the probability of the union

of the two sets listed above being linearly dependent in a M dimensional space is zero.

2) 2M = 0 or M = 0 This implies that

M eM + 2M KeM span(P) span(Q)

span({KeM, eM }) span(P) span(Q) = {0}

Also

rank(span(P) span(Q)) = rank(P) + rank(Q) rank(P Q)

rank(P Q) = 2M 2 rank(span(P) span(Q))

Note that P and Q are M 1 dimensional spaces. (The case where their dimensions are less than M 1 is

handled in the rst part). Also, P and Q are drawn from completely different set of vectors. Therefore, the

union of P, Q has a rank of M almost surely. Equivalently span(P) span(Q) has a dimension of M 2

almost surely. Since the set {e M, KeM } is drawn from an eigen vector e M that does not exist in either P

or Q, the probability of the 2 dimensional space span({e, Ke M }) intersecting with the M 2 dimensional

space P Q is zero. For example, if M = 3, let L indicate the line formed by the intersection of the the

two planes span({e1, Ke1 }) and span({e2, Ke2 }). The probability that line L lies in the plane formed by

span({e3, Ke3 }). 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 (M, M, M ) is achievable over the two-symbol extended channel. Thus 3M/2

degrees of freedom are achievable over the 3 user interference channel with M antenna at each transmitting

and receiving node.

From a communications system design perspective consider the problem of coexistence of interfering communi-

cation systems. Suppose the goal is that the two interfering systems with M > 1 antennas at each node are to be

operated such that neither system is interference limited. In other words the rates of the two users should scale as

their individual capacities in the absence of interference, i.e. R 1 = R2 = M log + o(log(SN R)). Then the users

must be protected from interference from each other. This essentially requires orthogonalization of the two users

so that, for example, their transmissions occur over 2 non-overlapping frequency slots. Thus, 2 orthogonal channel

resources are necessary for two interfering systems to coexist such that neither system is interference limited. Now

consider K = 3 interfering users. Theorem 1 implies that only 2 orthogonal channels are required to support these 3

users such that each user is able to achieve his full M degree of freedom. In other words, 3 wireless communication

systems can coexist over 2 orthogonal channels without being interference limited. Surprisingly this can be done

without any cooperation between the users in the form of shared messages. Since current wireless interference

networks are designed such that M K degrees of freedom are only achieved over K orthogonal channels, Theorem

1 suggests the possibility that we can improve the network capacity by a factor of 3/2 without any message sharing.

Note that it has been shown previously for the 2 user interference channel that unidirectional message sharing (e.g.

from transmitter 1 to transmitter 2) does not allow higher degrees of freedom [4], [9] and even bi-directional message

sharing (through full duplex noisy channels between the transmitters and full duplex noisy channels between the

receivers) will not increase the degrees of freedom if the cost of message sharing is considered [8], [10]. Therefore

it is quite surprising that the 3 user interference channel has 3M/2 degrees of freedom even without any message

sharing. To summarize, Theorem 1 shows that only half the degrees of freedom are lost due to distributed processing

at the transmitters and receivers on the 3 user MIMO interference channel.

R EFERENCES

[1] M. Maddah-Ali, A. Motahari, and A. Khandani, Communication over X channel: Signalling and multiplexing gain, in Tech. Report.

UW-ECE-2006-12, University of Waterloo, July 2006.

[2] S. Jafar, Degrees of freedom on the MIMO X channel- optimality of the MMK scheme, Tech. Report, Sep. 2006, arXiv:cs.IT/0607099v2.

[3] M. Maddah-Ali, A. Motahari, and A. Khandani, Communication over X channel: Signaling and performance analysis, in Tech. Report.

UW-ECE-2006-27, University of Waterloo, December 2006.

[4] S. Jafar and S. Shamai, Degrees of freedom region for the MIMO X channel, in arXiv:cs.IT/0607099v3, May 2007.

[5] H. Weingarten, S. Shamai, and G. Kramer, On the compound MIMO broadcast channel, in Proceedings of Annual Information Theory

and Applications Workshop UCSD, Jan 2007.

[6] A. Host-Madsen, Capacity bounds for cooperative diversity, IEEE Trans. Inform. Theory, vol. 52, pp. 1522 1544, April 2006.

[7] S. Jafar and M. Fakhereddin, Degrees of freedom for the MIMO interference channel, in Proc. of ISIT, 2006.

[8] A. Host-Madsen and A. Nosratinia, The multiplexing gain of wireless networks, in Proc. of ISIT, 2005.

[9] N. Devroye and M. Sharif, The multiplexing gain of MIMO X-channels with partial transmit side information, in IEEE Int. Symp. on

Info. Theory (ISIT), 2007. Preprint available at the authors website.

[10] A. Host-Madsen and Z. Yang, Interference and cooperation in multi-source wireless networks, in IEEE Communication Theory Workshop,

June 2005.

on.dvi

Contact this candidate