Source-linked AI summary
On the Capacity Region for Index Coding
Fatemeh Arbabjolfaei, Bernd Bandemer, Young-Han Kim, Eren Sasoglu, Lele Wang
TL;DR
The capacity region of a general index coding problem is unknown. The paper develops a composite-coding inner bound using random coding and optimal decoding; it is tight for all such problems with up to five messages.
Problem
The capacity region of a general index coding problem remains unknown.
Source: §I · pp. 1–2Method
Composite coding uses random coding and optimal decoding of relevant composite indices to establish a single-letter inner bound.
Source: §I · p. 2, §V · pp. 3–4Results
The composite-coding inner bound is tight for all index coding problems with up to five messages and many existing examples.
Source: §VI · p. 5Takeaways & Limitations
The resulting inner bound is simple and easy to compute, with tightness demonstrated for problems of up to five messages and many existing examples.
Source: §VI · p. 5
Abstract
from arXiv · showhide
A new inner bound on the capacity region of a general index coding problem is established. Unlike most existing bounds that are based on graph theoretic or algebraic tools, the bound is built on a random coding scheme and optimal decoding, and has a simple polymatroidal single-letter expression. The utility of the inner bound is demonstrated by examples that include the capacity region for all index coding problems with up to five messages (there are 9846 nonisomorphic ones).
I. INTRODUCTION
Index coding asks a sender to broadcast messages over a shared noiseless link to receivers with different side information, creating rate tradeoffs. The general capacity region remains unknown; this paper develops a random-coding approach and a single-letter inner bound.
I. INTRODUCTION
- Receivers recover their respective messages from a shared noiseless broadcast and different side information, creating tradeoffs among message rates.The capacity region is the closure of achievable rate tuples.Source: §I · p. 1
- Despite extensive combinatorial and algebraic work, the capacity region of a general index coding problem is not known.The problem is characterized by the receivers’ side-information sets.Source: §I · pp. 1–2
- The paper proposes composite coding based on random coding and establishes a corresponding single-letter inner bound on the capacity region.The approach contrasts with algebraic coding schemes and is developed from simpler schemes in later sections.Source: §I · p. 2
II. OUTER BOUNDS
The section gives entropy-based and graph-based outer bounds on achievable rates, then illustrates that the bounds can differ for a five-message problem.
II. OUTER BOUNDS
- Fano’s inequality and conditional entropy yield a polymatroidal outer bound with normalization, monotonicity, and submodularity constraints.The proof defines T_J as n^-1 H(X^n|M_J^c); the listed properties follow from entropy submodularity.Source: §II · p. 2
- The entropy-based outer bound is not tight in general.The paper notes that a relaxed version can still be useful.Source: §II · p. 2
- A graph-based outer bound applies to every message subset whose induced subgraph contains no directed cycle.It is presented as a corollary of the general outer bound.Source: §II · p. 2
- For the symmetric five-message example, the bounds include R1 + R3 ≤ 1, R2 + R4 ≤ 1, and R3 + R5 ≤ 1; the combined bounds characterize capacity later.The example illustrates that the two outer bounds need not coincide in general.Source: §II · p. 2
III. FLAT CODING
Flat coding uses a shared random codebook and simultaneous nonunique decoding to obtain an inner bound. It achieves capacity in many small problems but leaves three four-message exceptions to the stated coverage.
III. FLAT CODING
- The sender randomly generates one codeword for each message tuple, and each receiver uses simultaneous nonunique decoding with its side information.The receiver looks for its desired message and an interfering-message tuple consistent with the received sequence.Source: §III · p. 2
- Flat coding or its time sharing achieves capacity for every problem with one, two, or three messages, and for all but three of 218 four-message problems.The counts for one-, two-, and three-message problems are 1, 3, and 16, respectively.Source: §III · p. 3
- For the four-message setting, flat coding yields an inner bound consisting of rate quadruples satisfying R1 + R2 + R3 < 1, R1 + R4 < 1, and R3 + R4 < 1.Source: §III · p. 3
- The outer bound for that four-message example is tight.The paper points to the later composite-coding section for this conclusion.Source: §III · p. 3
IV. DUAL INDEX CODING
The section introduces a dual communication problem in which multiple senders convey message subtuples to one receiver, then characterizes its capacity region and shows it is achievable by flat coding.
IV. DUAL INDEX CODING
- The dual problem has multiple senders encode message subtuples into separate indices for delivery to a common receiver.The capacity-region question is posed as a function of the senders’ rates.Source: §IV · p. 3
- Proposition 2 characterizes the dual index coding capacity region through rate constraints for every subset J.Source: §IV · p. 3
- Flat coding achieves the characterized capacity region and is used later in the paper.Source: §IV · p. 3
- For the three-message example, the capacity region requires R1 + R2 + R3 ≤ 5, R2 ≤ 3, and R3 ≤ 4.Source: §IV · p. 3, Figure 5 · p. 3
- The example’s bounds are achieved by flat coding three specified message tuples and simultaneously decoding them at the receiver.The tuples are (M1, M2), (M1, M3), and (M1, M2, M3).Source: §IV · p. 3
V. COMPOSITE CODING
Composite coding layers random coding over message subsets with decoding over selected composite indices, yielding a polymatroidal inner bound by union over decoding sets. Examples demonstrate exact capacity regions in specific cases and agreement with an outer bound across computed five-message problems.
V. COMPOSITE CODING
- The scheme first forms composite indices by random coding, then uses flat coding to send them; receivers recover indices before their desired messages.The five-message example encodes pairs such as (M1, M2) into composite indices and uses those indices in decoding.Source: §V · pp. 3–4
- In a four-message example, two composite indices suffice for the construction, and eliminating their rates yields the capacity region.The indices are W1,4 and W1,2,3,4.Source: §V · p. 4
- The union over decoder choices gives the composite-coding inner bound, with each decoder's composite-message rates constrained by a polymatroidal region.The rate condition applies for all J ⊆ K_j \ A_j.Source: §V · p. 4
- Optimal decoding uses all composite indices relevant to a desired message, so composite coding is more than time sharing flat coding across subsets.The resulting rate region has a form similar to that for random-coded interference networks.Source: §V · p. 4
- For all 9,608 computed nonisomorphic five-message problems, the inner and outer bounds agree, establishing each capacity region.The bounds were computed using the polco tool for polyhedral computations.Source: §V · p. 4
- For the symmetric N-message problem, rate (U + 1)/(N − D + U) is achievable and is reported as optimal.The construction uses N − (D − U) composite indices that receivers need to recover from the transmitted codeword.Source: §V · p. 5
- For N = 6, U = 1, and D = 2, the optimal symmetric rate is 2/5, and the capacity region includes pairwise bounds and five-rate-sum bounds.The stated constraints include R_j + R_{j+2} ≤ 1, R_j + R_{j+3} ≤ 1, and sums of five consecutive rates ≤ 2.Source: §V · p. 5
VI. CONCLUDING REMARKS
The paper establishes a simple, computable composite-coding inner bound for general index coding, tight for all problems up to five messages and many examples. Further work is directed at evaluating more cases and studying the bounds' algebraic structure.
VI. CONCLUDING REMARKS
- The paper establishes a composite-coding inner bound for general index coding that is simple and easy to compute.The bound is based on a first principle in Shannon's random coding.Source: §VI · p. 5
- The inner bound is tight for all index coding problems with up to five messages and many existing examples.Source: §VI · p. 5
- Future work will evaluate more examples, including among 1,540,944 nonisomorphic six-message problems, and study the algebraic structures of the bounds.The bounds' polymatroidal and submodular properties suggest a connection rooted in matroid theory,.Source: §VI · p. 5