Source-linked AI summary
Index Coding - An Interference Alignment Perspective
Hamed Maleki, Viveck R. Cadambe, Syed A. Jafar
TL;DR
The paper asks how interference-alignment principles can characterize and solve index-coding capacity problems, including the role of linear codes in multiple unicast settings. It develops equivalences and alignment-based conditions, then gives vector-linear solutions for symmetric problems. The results include linear-code insufficiency for multiple unicast index coding and capacity-optimal solutions for several wireless-inspired instances.
Problem
Index coding contains difficult network-coding and wireless problems, while whether linear codes suffice for multiple unicast index coding remained unresolved.
Source: §1 · p. 2Method
The paper applies interference-alignment constraints to index coding, establishes groupcast–unicast equivalences, and constructs vector linear codes for symmetric instances.
Source: §3 · p. 8, §5.3 · p. 28, §8.1 · p. 41Results
Linear coding is insufficient for multiple unicast index coding, while interference-alignment conditions and vector linear schemes yield the stated rate and capacity results.
Source: §4.1 · p. 16, §5.3 · p. 28, §10 · p. 44Takeaways & Limitations
The interference-alignment perspective provides transparent capacity-optimal constructions and extends index-coding insights to related wireless and network-coding settings.
Source: §10 · p. 44The necessity of auxiliary messages and destinations in the groupcast–unicast equivalence remains unproved.
Source: §10 · p. 44
Abstract
from arXiv · showhide
The index coding problem is studied from an interference alignment perspective, providing new results as well as new insights into, and generalizations of, previously known results. An equivalence is established between multiple unicast index coding where each message is desired by exactly one receiver, and multiple groupcast index coding where a message can be desired by multiple receivers, which settles the heretofore open question of insufficiency of linear codes for the multiple unicast index coding problem by equivalence with multiple groupcast settings where this question has previously been answered. Necessary and sufficient conditions for the achievability of rate half per message are shown to be a natural consequence of interference alignment constraints, and generalizations to feasibility of rate $\frac{1}{L+1}$ per message when each destination desires at least $L$ messages, are similarly obtained. Finally, capacity optimal solutions are presented to a series of symmetric index coding problems inspired by the local connectivity and local interference characteristics of wireless networks. The solutions are based on vector linear coding.
1 Introduction
The paper frames index coding as a single-bottleneck capacity problem whose interference-alignment structure connects wired network coding, wireless index coding, and cellular blind interference alignment. These connections motivate studying index coding as a tractable setting that nevertheless captures substantial network complexity.
1 Introduction
1.1 Single Bottleneck Wired Networks – Index Coding
- In the wired reduction, infinite-capacity links convey side information while the finite bottleneck carries the symbols needed for decoding desired messages.Source: §1.1 · p. 2, Figure 1 · p. 3
1.2 Single Bottleneck Wireless Networks – Wireless Index Coding
- In wireless index coding, one noisy receiver forms the bottleneck while noiseless receivers provide effectively infinite-capacity links; the bottleneck capacity maps to degrees of freedom in corresponding examples.Source: §1.2 · p. 3, Figure 2 · p. 4
- Vector linear index-coding solutions can translate to the complex field, and therefore provide solutions for corresponding wireless index-coding problems when the required cooperation is available.Source: §1.2 · p. 4
1.3 Cellular Blind Interference Alignment Problem
- Cellular blind interference alignment is represented by a complementary index-coding graph, where antidote links correspond to absent local wireless connections.Source: §1.3 · pp. 5–6
- The same corresponding index-coding instance can solve both cellular blind interference alignment and blind linear network-coding problems when transmitters know connectivity but not channel realizations.Source: §1.3 · p. 6
2 Index Coding – Problem Formulation
The index coding model sends jointly encoded messages over a shared bottleneck while destinations use side information to recover their demands. Its formulation includes groupcast and unicast cases, rate-region definitions, and linear schemes based on zero-forcing and invertible desired-signal mappings.
2 Index Coding – Problem Formulation
- An index coding instance consists of independent messages, destinations with desired-message sets and antidotes, and a shared transmitted sequence from which each destination decodes its demands.Source: §2 · pp. 6–7
- The capacity region contains rate tuples achievable with arbitrarily small error probability, and for index coding it equals the zero-error capacity region.Source: §2 · p. 7
- The multiple groupcast formulation allows each message to be desired by multiple destinations, including multiple unicast and multiple multicast as special cases.Source: §2 · p. 7
- A linear scheme splits each message into scalar streams and transmits them along precoding vectors over a field, with scalar linear coding as the one-stream special case.Source: §2 · p. 8
- Linear decoding first removes antidote contributions, zero-forces remaining interference, and uses an invertible desired-message mapping to recover the requested symbols.Source: §2 · p. 8
3 Index Coding as an Interference Alignment Problem
The paper formulates index coding as interference alignment: antidotes let aligned interference occupy fewer bottleneck dimensions while desired signals remain separable. Three examples show scalar one-to-one alignment, vector one-to-one alignment, and scalar subspace alignment in wireless-inspired settings.
3 Index Coding as an Interference Alignment Problem
- Interference alignment frees bottleneck dimensions by exploiting receiver-specific antidotes, allowing aligned signals to remain decodable at destinations with appropriate side information.A rate above routing's 1/M requires linear dependence among transmitted vectors, with interference constrained to fit outside the desired-signal dimensions.Source: §3 · pp. 8–9
3.1 Example 1: Scalar linear index coding with One-to-One Alignment
- Aligning V2 and V3 transmits 3 scalar messages in a 2-dimensional vector space, achieving rate 1/2 per message through scalar one-to-one alignment.The example uses V1 = [0,1]^T and V2 = V3 = [1,0]^T, so the aligned interference is decoded using the receivers' antidotes.Source: Figure 4 · p. 9, §3.1 · p. 10
3.2 Example 2: Vector linear index coding with One-to-One Alignment
- The five-message CBIA interference-channel example achieves the capacity-optimal symmetric rate of 2/5 per message using vector linear coding over 5 channel uses.Each destination's four interfering signal vectors align into at most three dimensions, while its desired space remains linearly independent from the interference space.Source: §3.2 · pp. 10–11, Figure 5 · p. 10
3.3 Example 3: Scalar linear index coding with Subspace Alignment
- The fifteen-message CBIA X-channel example achieves the capacity 1/6 per message with a scalar linear subspace-alignment scheme over 6 channel uses.Unlike one-to-one alignment, vectors such as V8 lie in the span of several basis vectors; desired and interfering spaces remain linearly independent at each destination.Source: §3.3 · pp. 12, 14, 15, Figure 6 · p. 12
4 Background and Results
This section develops foundational results for index coding, including limitations of linear coding, interference-alignment characterizations of symmetric-rate feasibility, and capacity results for symmetric network-inspired models. It presents scalar and vector linear coding schemes, with achievability and converse details addressed in later sections.
4.1 Insufficiency of Linear Codes for Multiple Unicast Index Coding
- Linear coding is insufficient to achieve the capacity region of multiple-unicast index coding, via an equivalence with multiple-groupcast problems.The construction preserves linear achievability in both directions and transfers every groupcast-achievable rate, including nonlinear schemes, to the equivalent multiple-unicast problem.Source: §4.1 · p. 16
4.2 Feasibility of Symmetric Rate
- For destinations decoding L messages each, symmetric rate 1/(L+1) is infeasible exactly when an aligned message pair lacks the antidote needed to separate them.The condition applies to all coding schemes, while rate-half feasibility is the L = 1 special case previously obtained by Blasiak et al..Source: §4.2 · p. 19
- Whenever rate half is feasible, linear coding achieves it using scalar coding over two channel uses with a sufficiently large field or vector coding over a fixed field with sufficiently many even channel uses.The construction assigns distinct nonintersecting half-dimensional subspaces to alignment subsets; identifying subsets is polynomial, but minimizing their number is NP-hard and fixed-field, fixed-length feasibility is NP-complete.Source: §4.2 · p. 20
4.3 Symmetric Instances of the Multiple Unicast Index Coding Problem
- The paper studies symmetric multiple-unicast instances in which each destination has the same relative desired and antidote pattern, presenting capacity results for classes inspired by cellular broadcast interference alignment.These instances can be represented by directed side-information graphs, extending prior capacity results for several symmetric graph families.Source: §4.3 · pp. 20–21
4.3.1 Neighboring antidotes
- For symmetric neighboring-antidote instances, each destination knows U preceding and D succeeding messages, with U + D = A < K, and the capacity is stated in Theorem 5.The theorem considers M = K with all message indices interpreted modulo K.Source: §4.3.1 · p. 21
- For neighboring antidotes, the capacity is (U + 1)/(K − A + 2U) per message, achieved by vector linear coding that aligns adjacent-message interference in U dimensions.Each message uses U + 1 scalar symbols over a U + 1 dimensional signal space, while the total signal space has K − A + 2U dimensions.Source: §4.3.1 · p. 21
4.3.2 Neighboring interference
- For neighboring interference with L = U + D missing antidotes, symmetric placement yields capacity 1/(⌈L/2⌉ + 1) per message, whereas one-sided placement yields 1/(L + 1).The one-sided case requires no interference alignment; generally, scalar linear coding aligns the U preceding messages with messages among the D succeeding messages over D + 1 channel uses.Source: §4.3.2 · pp. 22–23
4.3.3 X network setting with local connectivity
- The locally connected X-network setting is formulated as a symmetric index-coding problem in which each destination connects to L consecutive base stations and the antidote graph complements the connectivity graph.The proposed scalar linear scheme uses one-to-one alignments over L(L+1)/2 channel uses, making the L desired symbols resolvable.Source: §4.3.3 · pp. 23–24
5 Proof of Theorem 1: Insufficiency of Linear Codes for Multiple Unicast Index Coding
The proof establishes equivalence between groupcast and multiple unicast index coding, preserving both achievability and linear-code achievability, and transfers groupcast nonlinear separations to multiple unicast settings.
5.1 Proof of Theorem 2 - Property 1
- Property 1 shows that every achievable groupcast rate tuple remains achievable in the equivalent multiple unicast problem.The proof reuses the groupcast encoder, forms additional random codebooks, and superposes the resulting codewords.Source: §5.1 · p. 24
- The constructed multiple unicast decoder recovers expanded messages by exploiting antidotes and reproducing the corresponding groupcast decoding strategy.For the auxiliary messages, random coding achieves sufficiently small error probability at rates up to the relevant mutual information.Source: §5.1 · p. 25
5.2 Proof of Theorem 2 - Property 2
- Property 2 shows that a rate tuple is achievable by linear coding in the groupcast setting if and only if it is achievable by linear coding in the equivalent multiple unicast setting.The converse direction constructs groupcast encoding and decoding matrices from the multiple unicast vector spaces while preserving rates arbitrarily closely.Source: §5.2 · pp. 25–27
5.3 Proof of Theorem 1
- A groupcast rate achievable nonlinearly but not linearly therefore yields a multiple unicast instance with the same separation, proving that linear coding is insufficient.This follows by combining the previously established groupcast separation with both properties of the equivalence theorem.Source: §5.3 · p. 28
6 Proof of Theorem 3: Feasibility of rate 1 L+1 per message
The section characterizes rate 1/(L+1) feasibility through alignment constraints, using scalar alignment constructions for achievability and information-theoretic outer bounds for converse results.
6.1 Achievability
- Rate 1/(L+1) is achievable when aligned messages form feasible partitions and every L+1 resulting coding vectors are linearly independent.The construction uses n=L+1 channel uses and assigns one coding vector to each alignment subset.Source: §6.1 · p. 29
6.2 Outer Bounds
- Theorem 8 bounds the desired rates at a destination together with interfering messages unavailable as antidotes by a total of at most one.The proof gives a genie the remaining messages, allowing one destination to decode the messages counted in the bound.Source: §6.2 · p. 29
- The outer bounds apply to both linear and nonlinear coding schemes because they are information theoretic.A four-message example attains R1+R2+R3+R4≤1 by sending messages separately, showing tightness for that instance.Source: §6.2 · pp. 29–30
- Theorem 9 generalizes these constraints along arbitrary alignment chains, yielding rate inequalities whose right-hand side equals the chain length N.The result supplies outer bounds that are tight for the 1/(L+1) feasibility problem.Source: §6.2 · p. 30
- Corollary 2 states that symmetric rate 1/(L+1) fails exactly when two messages in one alignment subset create an undesired interference relation at a destination.The criterion links feasibility directly to the structure of alignment subsets and antidote availability.Source: §6.2 · p. 30
6.2.1 Proof of Theorem 9
- The proof handles alignment chains of lengths two, three, and arbitrary N using genie-aided entropy inequalities and repeated applications of a submodularity lemma.The lemma is used repeatedly to combine conditional-entropy bounds before taking the asymptotic limit.Source: §6.2.1 · pp. 31, 33, 34
Lemma 2
- The entropy submodularity lemma provides the repeated inequality used to complete the arbitrary-chain outer-bound proof.Its proof relies on submodularity of entropy and the fact that conditioning reduces entropy.Source: Lemma 2 · p. 34
7 Proof of Theorem 5
Theorem 5 is proved by a vector-linear construction whose adjacent-message overlaps align interference, together with dimension-counting and information-theoretic outer bounds matching the achievable rate.
7.1 Achievability
- Rate 1 is achievable when A = K −1, while rate 1 2 is outer-bounded when A = K −2.Source: §7.1 · p. 34, §7.2 · p. 35
- For A ≤K −3, each user sends U + 1 symbols in an n = K −A + 2U dimensional space using vectors for which any n are linearly independent.Source: §7.1 · p. 34
- Adjacent message signal spaces overlap in U dimensions, causing the undesired messages to occupy fewer dimensions while preserving linear independence of each desired message.Source: §7.1 · pp. 34–35
- The construction makes each destination resolve its desired U + 1 symbols because the desired vectors and aligned interference together fit within n independent dimensions.Source: §7.1 · p. 35
7.2.1 Dimension Counting Outerbound
- The outer-bound argument first develops linear intuition through subspace dimensions, then extends the same recursive structure using entropy submodularity and decoding constraints.Source: §7.2 · p. 35, §7.2.1 · p. 36, §7.2.2 · pp. 39, 41
7.2.2 Information Theoretic Outerbound
- Dimension counting and entropy-based recursions bound the total interference, yielding the information-theoretic capacity outer bound of U+1 K−A+2U per message.Source: §7.2.2 · pp. 39–40
8 Proof of Theorem 6: Neighboring interference
The neighboring-interference problem achieves rate 1 D+1 per message with a periodic scalar-linear assignment, and a genie-aided converse establishes the matching bound.
8.1 Achievability
- A D + 1 dimensional scalar-linear scheme assigns linearly independent vectors periodically so all interference aligns in a D-dimensional subspace independent of the desired vector.Source: §8.1 · p. 41
- The scheme resolves each desired message in D + 1 dimensions, and the vectors can be chosen from the identity matrix over F2 to obtain an XOR implementation.Source: §8.1 · p. 41
8.2 Outerbound
- A genie-aided converse reduces the setting to U = 0 and shows every D + 1 consecutive rates satisfy Ri + Ri+1 + ... + Ri+D ≤1.Source: §8.2 · p. 42
9 Proof of Theorem 7: X network setting with local connectivity
Theorem 7 constructs a periodic scalar-linear solution for the locally connected X network, aligning interference outside the desired vectors, and proves its matching symmetric outer bound.
9.1 Achievability
- At each destination, L desired messages use L independent vectors while the remaining interference is confined to the complementary dimensions of an L(L+1) 2-dimensional space.Source: §9.1 · pp. 42–43
- The periodic assignment makes every circular block of L desired vectors linearly independent from one another and from the interference vectors, proving resolvability at all destinations.Source: §9.1 · p. 43
- The vectors may be chosen as columns of an L(L+1) 2-dimensional identity matrix over F2, yielding an orthogonal scheme without requiring channel coherence in the corresponding CBIA problem.Source: §9.1 · p. 43
9.2 Outerbound
- The converse selects a set of L(L+1) 2 messages and uses genie-provided side information to show that one destination can successively decode all of them.Source: §9.2 · p. 43
- This decoding chain bounds the symmetric per-message rate by 2 L(L+1).Source: §9.2 · p. 43
10 Conclusion
The paper concludes that interference alignment is central to index coding, while identifying unresolved questions about auxiliary nodes and finite-user X-channel capacity.
10 Conclusion
- Interference alignment supplies both capacity-optimal solutions for complex symmetric index-coding problems and intuition that often converts dimension-counting bounds into tight information-theoretic bounds.Source: §10 · p. 44
- The perspective also establishes the insufficiency of linear codes for multiple unicast index coding and transfers vector-linear capacity results to cellular blind interference-alignment degrees of freedom.Source: §10 · p. 44
- Whether auxiliary messages and destinations are necessary for the multiple-unicast equivalence remains unproved, leaving open the possibility of higher min-rates through non-aligned solutions.Source: §10 · p. 44
- For X channels, rate 2 L(L+1) per message is known for infinitely many users and appears in finite-user examples, but universal finite-K achievability remains an open question.Source: §10 · p. 44
- Finite-user alignment can be substantially more complex than the simpler orthogonal solutions available in the infinite-user setting.Source: §10 · p. 44