Dualities Between Entropy Functions and Network Codes

DOI10.1109/TIT.2008.928963MaRDI QIDQ3604866zbMATH OpenOpenAlexFDO

Authors Terence H. Chan, Alex Grant

Publication date 24 February 2009

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0708.4328

Mathematics Subject Classification ID

Information theory (general) (94A15) Coding theorems (Shannon theory) (94A24) Combinatorial aspects of matroids and geometric lattices (05B35) Applications of graph theory to circuits and networks (94C15)

Abstract: This paper provides a new duality between entropy functions and network codes. Given a function $ggeq0$ defined on all proper subsets of $N$ random variables, we provide a construction for a network multicast problem which is solvable if and only if $g$ is entropic. The underlying network topology is fixed and the multicast problem depends on $g$ only through edge capacities and source rates. Relaxing the requirement that the domain of $g$ be subsets of random variables, we obtain a similar duality between polymatroids and the linear programming bound. These duality results provide an alternative proof of the insufficiency of linear (and abelian) network codes, and demonstrate the utility of non-Shannon inequalities to tighten outer bounds on network coding capacity regions.

Recommendations

• Networks, Matroids, and Non-Shannon Information Inequalities
• On dualities in multiterminal coding problems
• Insufficiency of Linear Coding in Network Information Flow
• Linear network coding
• Network information flow

Cited in

(8)

• Upper concave envelopes and auxiliary random variables
• Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications
• Sensor networks: from dependence analysis via matroid bases to online synthesis
• On ideal and weakly-ideal access structures
• On abelian group representability of finite groups.
• Network encoding complexity: exact values, bounds, and inequalities
• Recent progresses in characterising information inequalities
• Non-linear information inequalities

This page was built for publication: Dualities Between Entropy Functions and Network Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604866)