Unachievability of network coding capacity

The coding capacity of a network is the supremum of ratios k/n, for which there exists a fractional (k,n) coding solution, where k is the source message dimension and n is the maximum edge dimension. The coding capacity is referred to as routing capacity in the case when only routing is allowed. A n...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2006-06, Vol.52 (6), p.2365-2372
Main Authors: Dougherty, R., Freiling, C., Zeger, K.
Format: Article
Language:English
Subjects:
Alphabets
Capacity
Coding
Communications networks
Computer networks
Construction
Data transmission
Decoding
flow
Information theory
Linear code
Linearity
Mathematics
Messages
Network coding
Networks
Routing
Routing (telecommunications)
Studies
switching
Wireless communication
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:The coding capacity of a network is the supremum of ratios k/n, for which there exists a fractional (k,n) coding solution, where k is the source message dimension and n is the maximum edge dimension. The coding capacity is referred to as routing capacity in the case when only routing is allowed. A network is said to achieve its capacity if there is some fractional (k,n) solution for which k/n equals the capacity. The routing capacity is known to be achievable for arbitrary networks. We give an example of a network whose coding capacity (which is 1) cannot be achieved by a network code. We do this by constructing two networks, one of which is solvable if and only if the alphabet size is odd, and the other of which is solvable if and only if the alphabet size is a power of 2. No linearity assumptions are made.
ISSN:0018-9448
1063-6692
1557-9654
1558-2566
DOI:10.1109/TIT.2006.874405