Information flow decomposition for network coding

We propose a method to identify structural properties of multicast network configurations, by decomposing networks into regions through which the same information flows. This decomposition allows us to show that very different networks are equivalent from a coding point of view, and offers a means t...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2006-03, Vol.52 (3), p.829-848
Main Authors: Fragouli, C., Soljanin, E.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Arcs
Channel coding
Channels
Coding
Coding, codes
Communication networks
Computer programming
Convolutional codes
decentralized codes
Decomposition
Exact sciences and technology
Fluid flow
Galois fields
Graph theory
Information flow
Information technology
Information theory
Information, signal and communications theory
Joining processes
max-flow min-cut theorem
maximum distance separable (MDS) codes
Multicast communication
Network coding
network multicast
Network topologies
Network topology
Networks
Receivers
Signal and communications theory
Telecommunications and information theory
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:We propose a method to identify structural properties of multicast network configurations, by decomposing networks into regions through which the same information flows. This decomposition allows us to show that very different networks are equivalent from a coding point of view, and offers a means to identify such equivalence classes. It also allows us to divide the network coding problem into two almost independent tasks: one of graph theory and the other of classical channel coding theory. This approach to network coding enables us to derive the smallest code alphabet size sufficient to code any network configuration with two sources as a function of the number of receivers in the network. But perhaps the most significant strength of our approach concerns future network coding practice. Namely, we propose deterministic algorithms to specify the coding operations at network nodes without the knowledge of the overall network topology. Such decentralized designs facilitate the construction of codes that can easily accommodate future changes in the network, e.g., addition of receivers and loss of links
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2005.864435