Source-linked AI summary
An Equivalence between Network Coding and Index Coding
Michelle Effros, Salim El Rouayheb, Michael Langberg
TL;DR
Network coding capacity is difficult to characterize in the general multi-source multi-terminal setting, and prior equivalence results with index coding were limited to linear codes. This paper gives an efficient reduction between network-coding and index-coding instances for general encoding functions, preserving feasibility and enabling solutions to be converted between the two problems.
Problem
General network coding has an unresolved capacity problem, while prior network-index coding equivalence results covered only linear encoding functions.
Method
The paper efficiently constructs an index-coding instance and broadcast rate from any network-coding instance, with corresponding codes constructible in both directions.
Results
For any rate tuple, block length, and error probability, network-coding feasibility is equivalent to feasibility of the constructed index-coding instance.
Takeaways & Limitations
Understanding the solvability of index-coding instances correspondingly informs the solvability of network-coding instances, including general nonlinear codes.
Abstract
from arXiv · showhide
We show that the network coding and index coding problems are equivalent. This equivalence holds in the general setting which includes linear and non-linear codes. Specifically, we present an efficient reduction that maps a network coding instance to an index coding one while preserving feasibility. Previous connections were restricted to the linear case.
I. INTRODUCTION
Index coding is a broadcast-with-side-information problem and a simple special case of network coding, but earlier equivalence results covered only linear codes. This work extends the equivalence to general encoding functions through an efficient reduction.
- I. INTRODUCTION: General multi-source multi-terminal network coding has an unresolved capacity problem.The paper identifies determining capacity in general network coding as a central open problem.
- I. INTRODUCTION: Index coding models one server communicating different requested information to clients with different side information.The server broadcasts messages while each terminal uses its wants and has sets to decode.
- I. INTRODUCTION: Index coding is a simple network-coding instance because only one internal node may have in-degree greater than one and perform encoding.The paper also describes index coding as representative under linear encoding.
- I. INTRODUCTION: Earlier equivalence results applied only to scalar and vector linear coding, while nonlinear codes can outperform linear solutions.This limitation matters because nonlinear codes may be necessary to achieve network-coding capacity.
- I. INTRODUCTION: The paper extends the equivalence to general, potentially nonlinear encoding functions and reduces a network-coding instance to an index-coding instance.A solution to the constructed index-coding instance can be converted back into a solution for the original network-coding instance.
II. MODEL
The paper introduces the formal models for network coding and index coding and distinguishes hatted index-coding variables from unhatted network-coding variables.
- II. MODEL: Hatted variables denote index-coding instances, whereas unhatted variables denote the corresponding network-coding instance.The notation is used throughout the model definitions.
- II. MODEL: The notation [k] denotes the set {1, . . . , k} for every integer k > 0.This convention supports later definitions of message and code alphabets.
A. Network coding
A network-coding instance is a directed acyclic network with sources, terminals, capacities, and source-to-terminal demands; local functions combine incoming information and terminals decode required sources.
- A. Network coding: A network-coding instance consists of a directed acyclic network, source nodes, terminal nodes, and a binary requirement matrix.The matrix indicates which source information each terminal requires.
- A. Network coding: Each edge carries a capacity-limited message, while source messages are independent random variables with specified rates.For block length n, edge and source alphabets are determined by their capacities and rates.
- A. Network coding: A network code assigns local encoding functions to edges and decoding functions to terminals.An edge function uses incoming-edge information, or source information when the edge leaves a source; terminal decoders output all required sources.
- A. Network coding: Global encoding functions express every edge value directly as a function of the source information.They are defined inductively according to the network's topological order from the local encoding functions.
- A. Network coding: Rate feasibility requires arbitrarily small error and rate backoff for some sufficiently large block length.An instance is R-feasible when this condition holds for every positive error and rate-backoff tolerance.
B. Index coding
Index coding is a single-server broadcast problem in which clients have different wants and has sets. An index code broadcasts one message that enables every client to recover its requested sources.
- B. Index coding: An index-coding instance contains server-held sources, terminals, wants sets, and has sets.The wants set identifies sources required by a terminal, while the has set identifies sources already available to it.
- B. Index coding: The server seeks to satisfy all terminal demands while minimizing broadcast-channel uses.The broadcast channel is error-free, and each terminal combines the broadcast with its available sources.
- B. Index coding: An index code consists of a broadcast encoding function and one decoding function for each terminal.The broadcast encoder maps all source variables to a broadcast message, and each decoder outputs the terminal's requested sources.
- B. Index coding: The butterfly-network construction represents each original source and network edge as a server source and creates clients for edges, terminals, and one additional terminal.For the butterfly example, the constructed instance has 9 server sources and 10 clients.
- B. Index coding: Index-code feasibility is defined by a source-rate tuple, broadcast rate, block length, and error tolerance.The capacity region contains rate tuples and broadcast capacities for which feasibility holds with arbitrarily small error and rate backoff.
III. EXAMPLE
The butterfly-network example illustrates both directions of the reduction between network coding and index coding, including how an index code induces network encoders and decoders. Correctness follows by fixing broadcast information and relating unique source-edge realizations to successful decoding.
- Reduction overview: The example presents the main equivalence through a reduction between network coding and index coding using the butterfly network.The construction is illustrated in both directions: network code to index code and index code to network code.
- Network code to index code: Each broadcast component combines an auxiliary edge source with the corresponding network encoding, as in ˆXB(ei) = ˆXei + ¯fei(ˆX1, ˆX2).The displayed construction gives the index-code broadcast components for all seven butterfly edges.
- Network code to index code: Clients recover wanted edge sources by subtracting broadcast terms associated with incoming edges and their known side information.For terminal ˆte5, the procedure computes the incoming encoded values before recovering ˆXe5 from its broadcast component.
- Index code to network code: Given an index code, the construction fixes a broadcast value σ and defines each network encoder from the corresponding client decoder.For edge e5, the local encoder uses incoming values Xe2 and Xe3 as inputs to the decoder ˆDˆte5(σ, Xe2, Xe3).
- Correctness: Correct decoding is established by showing that, for fixed source values, exactly one edge-source vector corresponds to zero broadcast information.This correspondence reduces correctness of the constructed network code to correct decoding in the original index code.
IV. MAIN RESULT
Theorem 1 establishes an efficient, feasibility-preserving equivalence between network coding instance I and constructed index coding instance Î. The reduction works in both directions, including general encoding functions, by introducing sources and terminals that reconstruct network-edge computations and terminal demands.
- Theorem 1: For any network coding instance I, the paper efficiently constructs an index coding instance Î and broadcast rate ĉB preserving (ε, R, n)-feasibility in both directions.The corresponding rate vector and network/index codes can also be efficiently computed or constructed from one another.
- Construction: The constructed index instance has |S| + |E| sources: one for each original source and one for each network edge.Original source rates are set to ˆRs = Rs, while edge-source rates are set to ˆRe = ce.
- Construction: The index instance has |E| + |T| + 1 terminals: edge terminals, terminals corresponding to original network terminals, and one all-edge terminal.The edge terminals recover edge sources, original-terminal clients recover demanded source messages, and the all-edge terminal recovers every edge source.
- Feasibility equivalence: The reverse implication is the major technical contribution, extending the earlier linear-only connection to general encoding functions.The proof explicitly identifies the reverse direction as the major technical contribution and constructs edge encoding functions by induction.
- Construction: Each broadcast chunk for edge e equals ˆXe + f̄e(ˆX1, ..., ˆX|S|), enabling decoders to cancel ˆXe and recover the network computation.The cancellation step uses bitwise xor and allows decoders to reconstruct incoming edge values before applying the original network encoding or decoding functions.
- Feasibility equivalence: Correct network decoding implies correct index decoding with the same error probability, while the reverse direction selects a value σ yielding a network code that succeeds with probability at least 1 − ε.The forward direction maps successful network realizations to successful index realizations; the reverse direction uses a sufficiently good σ and induction over the network’s topological order.
V. CAPACITY REGIONS
For collocated sources, the reduction constructs an index-coding instance whose capacity region corresponds exactly to that of the network-coding instance. The proof handles the reverse direction by covering source realizations and using a two-phase network code with vanishing overhead and error.
- Capacity-region equivalence: For collocated-source instances, a rate tuple R lies in the network-coding capacity region if and only if the constructed tuple (R̂, ĉB) lies in the index-coding capacity region.The construction and corresponding rate vector can be obtained efficiently.
- Network coding to index coding: The forward reduction maps a feasible network code to an index code with the same block length and broadcast rate ĉBn.The resulting index-code rates are scaled by (1−δ), with error probability ε.
- Index coding to network coding: The reverse reduction cannot directly reuse the theorem proof because the broadcast rate must equal the sum of edge-variable rates, but the available index code has a small slack.The construction instead introduces a claim that supports the collocated-source case.
- Index coding to network coding: A covered source realization admits an index-code edge assignment and a symbol σ that determines the network encoding and decoding functions.The source node checks whether such an assignment exists before selecting Case A or Case B.
- Index coding to network coding: In Case A, the network code first broadcasts σ using at most log |Σ| bits, then executes the network code induced by σ.The extra block-length factor is n(1+δ′), where δ′=log |Σ|/n tends to zero.
- Index coding to network coding: Case B is treated as an error, occurring with probability at most 2ε, so the resulting network code becomes feasible as ε and δ′ vanish.The achieved rate is R(1−δ)/(1+δ′) over block length n(1+δ′).
- Covering argument: A random subset Σ′ covers at least one quarter of the remaining source realizations, and iterating this construction covers all relevant realizations.The number of iterations is log |A|/log (4/3).
VI. CONCLUSIONS
The paper establishes an equivalence between network coding and index coding for general encoding functions, extending the earlier linear-only connection. However, the equivalence does not directly determine capacity regions for general network instances because the reduction lacks flexibility in the broadcast rate.
- Conclusions: The paper extends the network–index coding equivalence from linear codes to general, potentially nonlinear, encoding functions.It concludes that understanding index coding correspondingly informs understanding of network coding.
- Limitations: The connection does not directly provide a method for determining the capacity region of general network-coding instances.The limitation arises in the reduction of rate-membership questions to index-coding capacity questions.
- Limitations: A stronger connection allowing flexibility in the broadcast rate ĉB is identified as necessary and left for future study.The same issue prevents a naive transfer of certain index-coding results on open network-coding questions.
- Implications: Although index coding helps frame questions such as zero-versus-ε error and edge removal, the present equivalence does not by itself establish their full network-coding resolution.Applying the equivalence to those results again exposes the need for broadcast-rate flexibility.