[IEEE Trans. on Information Theory - IEEE/ACM Trans. on Networking, June 2006, pp. 2365-2372]
Unachievability of Network Coding Capacity
Randall Dougherty, Chris Freiling, and Kenneth Zeger
Abstract
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.