A Transform Approach to Linear Network Coding for Acyclic Networks with Delay

2011/03/20 by Teja Damodaram Bavirisetti, G. Abhinav, Bavirisetti, Teja Damodaram +5 · 3 citations
Computer Science · Engineering · Mathematics · #Advanced MIMO Systems Optimization #Advanced Wireless Network Optimization #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Full-Duplex Wireless Communications #Information Theory (cs.IT) #cs.IT #math.IT

paper · pdf · doi:10.48550/arxiv.1103.3882

Edits to Section II A, Theorem 4, Theorem 5. Lemma 4 newly added

openalex publication_date 2011/03/20 · arxiv created 2012/05/10 · arxiv updated 2015/03/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The algebraic formulation for linear network coding in acyclic networks with the links having integer delay is well known. Based on this formulation, for a given set of connections over an arbitrary acyclic network with integer delay assumed for the links, the output symbols at the sink nodes, at any given time instant, is a \mathbbF_q-linear combination of the input symbols across different generations, where \mathbbF_q denotes the field over which the network operates. We use finite-field discrete fourier transform (DFT) to convert the output symbols at the sink nodes, at any given time instant, into a \mathbbF_q-linear combination of the input symbols generated during the same generation. We call this as transforming the acyclic network with delay into \em n-instantaneous networks (n is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (non-transform) approach if and only if there exists a network code satisfying sink demands in the transform approach. Furthermore, we show that the transform method (along with the use of alignment strategies) can be employed to achieve half the rate corresponding to the individual source-destination min-cut (which are assumed to be equal to 1) for some classes of three-source three-destination unicast network with delays, when the zero-interference conditions are not satisfied.

Citations

• On network coding for acyclic networks with delays

Cited by

• On the Capacity of the Finite Field Counterparts of Wireless Interference Networks
• On the Feasibility of Network Alignment for Three-Source Three-Destination Multiple Unicast Networks with Delays
• Precoding Based Network Alignment using Transform Approach for Acyclic Networks with Delay

Related

• Precoding Based Network Alignment using Transform Approach for Acyclic Networks with Delay
• On network coding for acyclic networks with delays
• On the Feasibility of Network Alignment for Three-Source Three-Destination Multiple Unicast Networks with Delays
• Network Coding for Multiple Unicasts: An Interference Alignment Approach
• A Simple Necessary and Sufficient Condition for the Double Unicast Problem