On Network Coding for Sum-Networks

A directed acyclic network is considered where all the terminals need to recover the sum of the symbols generated at all the sources. We call such a network a sum-network. It is shown that there exists a solvably (and linear solvably) equivalent sum-network for any multiple-unicast network, and thus...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2012-01, Vol.58 (1), p.50-63
Main Authors: Rai, Brijesh Kumar, Dey, Bikash Kumar
Format: Article
Language:English
Subjects:
Applied sciences
Coding
Coding theory
Coding, codes
Communication networks
Communications networks
Electrical engineering
Equivalence
Exact sciences and technology
Function computation
Information theory
Information, signal and communications theory
Linear code
linear network coding
Mathematical analysis
Network coding
Networks
polynomial equations
Polynomials
Scalars
Signal and communications theory
solvability
Switching and signalling
Systems, networks and services of telecommunications
Telecommunications
Telecommunications and information theory
Terminals
Transmission and modulation (techniques and equipments)
Vectors
Vectors (mathematics)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A directed acyclic network is considered where all the terminals need to recover the sum of the symbols generated at all the sources. We call such a network a sum-network. It is shown that there exists a solvably (and linear solvably) equivalent sum-network for any multiple-unicast network, and thus for any directed acyclic communication network. It is also shown that there exists a linear solvably equivalent multiple-unicast network for every sum-network. It is shown that for any set of polynomials having integer coefficients, there exists a sum-network which is scalar linear solvable over a finite field F if and only if the polynomials have a common root in F. For any finite or cofinite set of prime numbers, a network is constructed which has a vector linear solution of any length if and only if the characteristic of the alphabet field is in the given set. The insufficiency of linear net- work coding and unachievability of the network coding capacity are proved for sum-networks by using similar known results for communication networks. Under fractional vector linear network coding, a sum-network and its reverse network are shown to be equivalent. However, under nonlinear coding, it is shown that there exists a solvable sum-network whose reverse network is not solvable.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2011.2169532