Introduction

Blind Interference Alignment (BIA) originated in the following paper as the idea that it is possible to align interference in a wireless network without requiring the knowledge of precise channel coefficient values at the transmitter(s), by exploiting the knowledge of channel coherence patterns instead.

Syed A. Jafar, Blind Interference Alignment, IEEE Journal of Selected Topics in Signal Processing, Vol. 6, No. 3, Pages: 216-227, June 2012.

From a practical perspective, BIA is promising because acquiring precise channel state information at the transmitters (CSIT) can be challenging. The potential for BIA exists because in addition to the diversity of coherence patterns that is already present in a wireless network, it may be possible to manipulate coherence patterns through switching patterns of reconfigurable antennas, and intelligent reflecting surfaces. From a theoretical standpoint, it is especially intriguing because it provides us a window through which we can peer into the mysterious role of coherence in a communication network − a topic whose deeper significance goes well beyond wireless networks, and is far from understood.

Remark: Channel uncertainty and coherence in this context should not be confused with non-coherent communication, which typically refers to communication in the absence of channel state information at the receiver(s), i.e., in the absence of CSIR. BIA deals primarily with channel uncertainty on the transmitter side. Indeed, perfect CSIR is assumed throughout this discussion.

How do coherence patterns create opportunities for Blind Interference Alignment?

Let us answer this question with our first toy example. We will cast all toy examples over finite fields for simplicity. The key insights from these examples translate quite robustly to corresponding wireless network settings.

Toy Example 1: Consider the X-channel setting shown below where Transmitter 1 has symbols a₁, b₁ and Transmitter 2 has symbols a₂, b₂. Receiver 1 wants symbols a₁, a₂ and Receiver 2 wants symbols b₁, b₂. Let us assume for simplicity that all symbols and operations are over a finite field \(\mathbb{F}_q\). The optimal solution can deliver all 4 desired symbols within 3 channel uses, using blind interference alignment. Play with this toy example to explore how this is done.

The transmitters know the following coherence pattern: Receiver 1's channel vector \((G_{11}, G_{12})\) changes to a random linearly independent value after the first channel use, and Receiver 2's channel vector \((G_{21}, G_{22})\) changes to a random linearly independent value after the second channel use. For simplicity let us assume that the channel vectors cannot be zero vectors. The actual values of the channel realizations are not known to the transmitters. Each receiver has perfect knowledge of its own channels.

Question 1. On behalf of the transmitters, choose the inputs such that each receiver can recover what it wants over 3 channel uses.

Remark: The solution for Toy Example 1 is capacity achieving, i.e., the sum-capacity of this X-channel is 4/3 (symbols from \(\mathbb{F}\) per channel-use). The same Blind Interference Alignment idea also works in the wireless setting where the field is \(\mathbb{C}\), the inputs are constrained to transmit power P, and there is zero mean unit variance i.i.d. Additive White Gaussive Noise (AWGN) combined with the signals seen at each receiver. The corresponding result in the wireless setting is that this X-channel has 4/3 Degrees of Freedom (DoF). Notably, even if perfect channel state information at the transmitters (CSIT) was available, the X-channel has only 4/3 DoF. Correspondingly, the finite field setting of Toy Example 1 has only capacity 4/3 even with perfect CSIT. That the same capacity is achieved without the knowledge of channel coefficient values at the transmitters, based on the knowledge of coherence patterns alone, makes BIA particularly intriguing. It is also worth noting that there is no further benefit of transmitter cooperation, i.e., even if the two transmitters jointly code their data in Toy Example 1, the capacity of the MISO broadcast channel thus obtained remains 4/3 symbols/channel-use. Evidently, the benefits of zero-forcing are lost when the transmitters do not have perfect CSIT.

Practical relevance of coherence patterns

Let us provide two possible practical motivations for such a coherence pattern.

Coherence Time, Coherence Bandwidth: In a wireless network, different users experience different coherence times (depending on mobility) and different coherence bandwidths (depending on multipath scattering). Suppose Receiver 1 experiences larger coherence time, while Receiver 2 experiences larger coherence bandwidth. Consider transmissions at times t₁ and t₂ over channels at frequencies f₁ and f₂, such that the interval between t₁ and t₂ is within the coherence time of Receiver 1 but exceeds the coherence time of Receiver 2, and the separation between frequencies f₁ and f₂ is within the coherence bandwidth of Receiver 2 but exceeds the coherence bandwidth of Receiver 1. Now, if the three channel uses correspond to (time, frequency) tuples (t₁, f₁), (t₁, f₂), and (t₂, f₂), respectively, then we have precisely the situation of Toy Example 1, where the channel experienced by Receiver 1 changes after the first channel use (because the change in frequency exceeds his coherence bandwidth) but not after the second channel use (because the change in time does not exceed his coherence interval), whereas the channel experienced by Receiver 2 changes after the second channel use (because the change in time exceeds his coherence time) but not after the first channel use (because the change in frequency does not exceed his coherence bandwidth). Evidently different coherence times and coherence bandwidths create opportunities for interference alignment without the need for learning the channel realizations by the transmitters.

Reconfigurable Antennas: Without relying on coherence times and coherence bandwidths (assume they are long enough for both users), suppose each receiver is equipped with a reconfigurable antenna capable of switching modes (conceptually similar to antenna selection). Then if Receiver 1 switches his antenna mode after the first channel use and Receiver 2 switches his antenna mode after the second channel use, then once again we are in the situation of Toy Example 1. The transmitters do not need to know the channel realizations, what they need to know is just the antenna switching pattern which may be predetermined. Thus, once again we have a practical path toward blind interference alignment.

The following paper shows that a \(K_1\times K_2\) X-network, i.e., a wireless network with \(K_1\) transmitters and \(K_2\) receivers where each transmitter has an independent message for each receiver, has \(K_1K_2/(K_1+K_2-1)\) DoF, based on BIA and reconfigurable antennas alone. Again, this matches the maximum DoF possible even with perfect CSIT, and no further improvements are possible even with full cooperation among transmitters (MISO BC setting).

Tiangao Gou, Chenwei Wang, Syed A. Jafar, Aiming Perfectly in the Dark - Blind Interference Alignment through Staggered Antenna Switching, IEEE Transactions on Signal Processing, Vol. 59, No. 6, Pages: 2734-2744, June 2011

The results are generalized to MIMO settings, i.e., where nodes have multiple reconfigurable antennas, in this paper.

Chenwei Wang, Tiangao Gou, Syed A. Jafar, Interference Alignment Through Staggered Antenna Switching for MIMO BC With No CSIT, Proceedings of Asilomar Conference on Signals, Systems and Computers, Nov., 2010.

How much impact can coherence patterns have on network capacity?

The short answer is 'a lot'. To gain some insight let us go to our next toy example.

Toy Example 2: Consider the 4 user Interference Channel shown in the figure below. Suppose you are free to choose the coherence pattern of each of the channel coefficients \(G_{ij}\). For simplicity let us assume that all symbols and operations are over some finite field \(\mathbb{F}\), the receivers know all of their channel coefficients, and the transmitters know only the coherence patterns.

Question 2. With the best choice of coherence patterns, what is the smallest number of channel uses it will take for every Transmitter k, k=1,2,3,4, to successfully deliver its symbol a_k to its corresponding receiver, i.e., Receiver k?

Remark: Toy Example 2 generalizes easily to K users, to show that with the right coherence pattern, a K user interference channel has K/2 DoF without the knowledge of channel coefficient values at the transmitters, due to BIA. Recall that K/2 is also the DoF value of a K user interference channel under perfect (instantaneous and infinite precision) CSIT, as shown in this work.

Viveck R. Cadambe, Syed A. Jafar, Interference Alignment and the Degrees of Freedom of the K User Interference Channel, IEEE Transactions on Information Theory, Aug 2008, Vol. 54, Issue 8, Pages: 3425-3441

As promising as that sounds, note that the coding scheme that promises K/2 DoF with perfect CSIT requires asymptotically long precoding delays, infinite precision CSIT, and that these gains manifest primarily at asymptotically high SNRs, none of which is practical. Albeit, the latter issue of high SNRs can be circumvented through Ergodic Interference Alignment, as shown in this work.

Bobak Nazer, Michael Gastpar, Syed A. Jafar, Sriram Vishwanath, Ergodic Interference Alignment, IEEE Transactions on Information Theory, Vol. 58, No. 10, Pages: 6355-6371, October 2012.

On the other hand, with no CSIT (not even coherence patterns) the K user interference channel has only 1 DoF as shown in this work.

Arash G. Davoodi, Syed A. Jafar, Aligned Image Sets under Channel Uncertainty: Settling Conjectures on the Collapse of Degrees of Freedom under Finite Precision CSIT, IEEE Transactions on Information Theory, Vol. 62, Number 10, Pages: 5603-5618, October 2016.

This dramatic increase from 1 DoF to K/2 DoF, especially without the burden of learning the precise channel coefficient values at the transmitters, without the need for asymptotically long precoding sequences, and without the need for asymptotically high SNRs, could potentially obliterate the interference barrier some day, making the ambitious dream of `everyone gets half the cake' a reality, provided that future technologies can find a way to achieve desired coherence patterns. Wouldn't that be exciting? Achieving interference-free transmission, at any SNR, for any number of interfering users, in just two channel uses! At the moment though, there is no known way to impose such a coherence pattern in practice.

Network Coherence: What if all channels have the same coherence time?

The examples that we have considered so far have all relied on the diversity of channel coherence times, i.e., different channels had different coherence times or different coherence patterns. Our next two examples show that the significant benefits of Blind Interference Alignment are still available even when all channels have the same coherence time and the same coherence pattern. We call this 'network coherence'. Through the next two toy examples, we will show that network coherence time matters, i.e., the capacity of the network increases with the network coherence time. This is surprising, because longer coherence time was conventionally thought to be useful primarily for the receivers to learn the channel through training and for the transmitters to learn the channel through feedback. So if we assume that the receivers already have perfect channel knowledge, and there is no feedback to the transmitter, then conventional wisdom dictates that network coherence time should not impact the capacity of the network. The examples will show that this conventional wisdom is not correct.

Toy Example 3: Consider the 2 user MIMO Broadcast Channel shown in the figure below. Over each channel-use, the transmitter has 6 inputs, and each receiver observes 3 outputs as specified in the figure. There are two independent messages, one for each receiver. For simplicity let us assume that all symbols and operations are over a large finite field \(\mathbb{F}_p\) whose elements we represent as integers modulo the large prime number \(p\). The channels can only take non-zero values and each receiver knows all of its channel coefficients. All channels have coherence time 1, i.e., all channels change to a different random value after each channel use. The transmitter knows this network coherence time. Besides the knowledge of the network coherence time, let us assume that the transmitter has perfect CSIT for User Z and no CSIT for User Y. Note that because the transmitter has perfect CSIT for User Z, without loss of generality all channels associated with User Z can be assumed to be equal to 1 (because these channel coefficients can be inverted by the transmitter). Click the 'Simplify' button in the figure to see this simplification.

Question 3. With a network coherence time of 1, what is the sum-rate capacity of this MIMO BC?

Remark: The achievable scheme in the solution presented above is quite simple. However, Question 3 is not so simple. That is because we also need a converse argument, i.e., an impossibility result, to show that no scheme can achieve a sum-rate higher than 4 symbols/channel-use. The converse is quite insightful but also highly non-trivial, so we will not try to summarize it here. Instead, let us point out that the converse relies on Aligned Images arguments, and follows from the results presented in this paper.

Arash G. Davoodi, Syed A. Jafar, Network Coherence Time Matters – Aligned Image Sets and the Degrees of Freedom of Interference Networks with Finite Precision CSIT and Perfect CSIR, IEEE Transactions on Information Theory, Vol. 64, No. 12, Pages: 7780-7791, December 2018.

Now, let us see what happens if we increase the network coherence time from 1 to 2 in the same network that we considered above for Toy Example 3. This takes us to our next toy example.

Toy Example 4: Consider the same 2 user MIMO Broadcast Channel from Toy Example 3, shown again in the figure below. The only difference is that now the network coherence time is 2, i.e., all channels stay constant for two consecutive channel uses (n = 2i+1, 2i+2) and then change to a different random non-zero value. Like before, the transmitter knows the network coherence model, and besides that has perfect CSIT for User Z, and no CSIT for User Y.

Question 4. With a network coherence time of 2, what is the sum-rate capacity of this MIMO BC?

Remark: The answer to Question 4 requires both an achievable scheme and a converse bound. Only the achievable scheme is shown in the solution presented in the figure above. The converse is quite straightforward and is summarized at a high level as follows. Two copies of User 1, who have collectively a total of 6 observations (with independent channel realizations), are jointly able to solve for all 6 channel inputs from those 6 observations. This allows them to recover not only their own message (individually, so twice) but also User 2's message (collectively, so once), yielding the bound \(2R_1+R_2\leq 6\). Combined with the trivial single user capacity bound \(R_2\leq 3\) we obtain the sum-capacity bound \(R_1+R_2\leq 4.5\). Indeed, while the converse is straightforward, it is the achievability that is the more interesting aspect of Toy Example 4. Note that this problem also has a non-trivial topological aspect, because not all inputs are connected to all outputs. As such, the achievable scheme makes use of the idea of Topological Interference Management (TIM) that was introduced in this paper.

Syed A. Jafar, Topological Interference Management through Index Coding, IEEE Transactions on Information Theory, Vol. 60, No. 1, Pages: 529-568, January 2014.

To summarize, Toy Examples 3 and 4 have shown us that network coherence time matters, i.e., even when all channels in a network have the same coherence times/patterns, and the CSI is already available perfectly to the receivers (so there is no benefit of training the receiver) and there is no feedback to the transmitters, the capacity of the network still increases with coherence time.

BIA beyond Wireless

BIA is related to a number of important problems in theoretical computer science − problems like Locally Decodable Codes (LDC) and Private Information Retrieval (PIR). The connection is quite strong. Every BIA scheme can be translated into a locally decodable code, and since every LDC can be translated into a PIR scheme, it follows that every BIA scheme also gives us a PIR scheme.

BIA and Smooth Locally Decodable Codes

Toy Example 5: Define X(n)=[X₁(n), X₂(n)], so that according to the solution for Toy Example 1, we have
X(1) = [a₁, a₂],
X(2) = [a₁ + b₁, a₂ + b₂],
X(3) = [b₁, b₂].
Suppose the 2 x 1 random channel vectors seen by each user are drawn from the support set S whose elements are pairwise-linearly-independent 2x1 vectors enumerated as U(1), U(2),..., U(M). Then the projections of X(1), X(2), X(3), along the channel vectors U(1), U(2),..., U(M) form a Smooth Locally Decodable Code of length 3M, and locality 3, that maps the messages (source symbols): W₁=(a₁, a₂), W₂=(b₁, b₂) to the code symbols c(n,m)=X(n)U(m). Note that the size of each code symbol is half of the size of each message symbol. For any distinct m₁, m₂ in [1:M], the source symbol W₁ can be decoded from the code symbols c(1,m₁), c(2,m₂), c(3,m₂), because those constitute three received symbols for User 1 in the BIA scheme of Toy Example 1. Similarly, the source symbol W₂ can be decoded from the code symbols c(1,m₁), c(2,m₁), c(3,m₂).

Question 5. For M=2, U(1)=[1; 2], U(2) = [1; 3], the smooth locally decodable code obtained from the BIA scheme of Toy Example 1 is shown explicitly below. The decoding sets for each source symbol are either the red or blue connected components.

Remark: An important open problem in theoretical computer science is to find optimal constructions of smooth locally decodable codes, i.e., constructions that achieve optimal tradeoffs between code lengths and locality for a given number of source symbols, typically for code symbols over the same alphabet as the source symbols. Much less important but perhaps still interesting is the question of finding the minimum code length possible for a smooth locally decodable code for a given coded symbol size given the locality and the number of source symbols. Codes that have the smallest possible code symbol size are of particular interest from the BIA perspective because they correspond to optimal BIA schemes. These codes are explored in this paper.

Hua Sun, Syed A. Jafar, On the Capacity of Locally Decodable Codes, December 2018, e-print, ArXiv:1812.05566.

BIA and Private Information Retrieval (PIR)

Since Blind Interference Alignment is closely related to locally decodable codes, and locally decodable codes are in turn closely related to Private Information Retrieval schemes, it follows naturally that BIA should have deep connections to Private Information Retrieval. This connection is highlighted by our next toy example.

Toy Example 6: Let us construct a 3 Server PIR scheme for 2 messages using the locally decodable code of Toy Example 5. This construction is shown in the figure below. Messages W₁=(a₁, a₂), W₂=(b₁, b₂) are stored in coded form at 3 servers as shown in the figure. A user wishes to retrieve one of the two messages without revealing to any individual server which message he wants. In order to do so the user can randomly download one of the two stored coded symbols from Server 1, and its blue neighbors (i.e., nodes connected by blue edges) from Server 2 and Server 3 if the desired message is W₁. Similarly, if the desired message is W₂ then the user downloads the red neighbors from Server 2 and Server 3. With this scheme, the user is equally likely to download either of the two stored symbols from each server, thus revealing no information to any individual server about his desired message. Since the same query can be repeated for each symbol of the desired message, for large messages, the communication cost of PIR is dominated by the download cost. The rate of a PIR setting is the number of bits of the desired symbol that can be retrieved per bit of total download from all the servers. The supremum of achievable rates for a PIR setting is called the capacity of that PIR setting.

Question 6. What is the rate of the PIR scheme shown in the figure? Choose the correct answer from the choices listed below.

1/3 2/3 1 4/3

Remark: Incidentally, 2/3 is the capacity of PIR with 2 messages and 3 servers if the upload from each server is restricted to 1 bit, i.e., there are only two possible answers from each server. In this sense, the PIR scheme shown above is optimal/capacity-achieving. Without upload constraints it is possible to do better, and the capacity turns out to be 3/4. The capacity of PIR is characterized for arbitrary number of servers and messages in this paper.

Hua Sun, Syed A. Jafar, The Capacity of Private Information Retrieval, IEEE Transactions on Information Theory, IEEE Transactions on Information Theory, Vol. 63, No. 7, Pages: 4075-4088, July 2017.