Special Networks
From R. Ahlswede, N. Cai, S.-Y. R. Li
and R. W. Yeung, "Network information flow," IEEE Trans. on Information Theory, vol. 46, pp. 1024-1016, 2000.
This is the original example that kicked off the field of network
coding. In order to transmit both bits A,B to both receivers network
coding
is necessary at the middle link as indicated.
From M. Effros, M. Medard, T. Ho, D.
Karger, "On coding for non-multicast networks", 41st Annual Allerton Conference on
Communication Control
and Computing, Oct. 2003.
This is an example of a network showing that scalar linear network
coding is not sufficient to give the maximal throughput in a general
network
coding problem (case a ). Increasing the alphabet size to vectors of
length two
renders
the network problem feasible ( case b). The new solution is linear over
vectors
of length two. It is interesting to note that case (b) may be
considered as superposition of two solutions to depicted in cases (c)
and (d). In particular, the networks in cases (c) and (d) allow a flow
based solution and no "network coding" is neccessary. Switching
(time-sharing) between these two solutions effectively renders the
solution of case (b).
From S. Riis, "Linear versus
non-linear Boolean functions in Network Flow",
preprint, November, 2003
This network is the first example of a network that requires
truly non-linear coding in order to achieve capacity. While A,B,C,D can
be transmitted at one bit per time unit, additional log_2(5) bits can
be transmitted for M. For a proof see S. Riis, "Linear versus
non-linear Boolean functions in Network Flow",
preprint, November, 2003
If you have anything else you want to have posted let me know. A gif
file and a short paragraph about the network would be perfect ( koetter@uiuc.edu)
Last updated: 11/17/2003