Title :
Polymatroids with network coding
Author_Institution :
Waseda Univ., Tokyo, Japan
fDate :
Jan. 31 2010-Feb. 5 2010
Abstract :
The problem of network coding for multicasting a single source to multiple sinks has first been studied by Ahlswede, Cai, Li and Yeung in 2000, in which they have established the celebrated max-flow mini-cut theorem on non-physical information flow over a network of independent channels. On the other hand, in 1980, Han has studied the case with correlated multiple sources and a single sink from the viewpoint of polymatroidal functions in which a necessary and sufficient condition has been demonstrated for reliable transmission over the network. This paper presents an attempt to unify both cases, which leads to establish a necessary and sufficient condition for reliable transmission over a noisy network for multicasting all the correlated multiple sources to all the multiple sinks. Furthermore, we address also the problem of transmitting ¿independent¿ sources over a multiple-access-type of network as well as over a broadcast-type of network, which reveals that the (co-) polymatroidal structures are intrinsically involved in these types of network coding.
Keywords :
network coding; multicasting; network coding; noisy network; polymatroidal functions; polymatroidal structures; reliable transmission; Bit rate; Broadcasting; Channel capacity; Channel coding; Graph theory; Network coding; Source coding; Sufficient conditions; Sun; Tellurium;
Conference_Titel :
Information Theory and Applications Workshop (ITA), 2010
Conference_Location :
San Diego, CA
Print_ISBN :
978-1-4244-7012-9
Electronic_ISBN :
978-1-4244-7014-3
DOI :
10.1109/ITA.2010.5454126