Linear network coding: Difference between revisions

Revision as of 11:46, 9 December 2005

Revision as of 00:52, 10 December 2005

Line 1:

{{wikify}}

The fundamental concept of '''network coding''' was introduced for satellite communication networks in a paper by R. W. Yeung and Z. Zhang, "Distributed Source Coding for Satellite Communications" (IEEE Transactions on Information Theory, IT-45, pp. 1111-1120. 1999). The concept was fully developed in a subsequent paper by R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, "Network Information Flow" (IEEE Transactions on Information Theory, IT-46, pp. 1204-1216, 2000), where the term `network coding' was coined. In this paper, the advantage of network coding over routing, the traditional way of operating a network, was pointed out for the first time by means of a very simple example known as the butterfly network.

The principle of '''network coding''' is easiest explained with an example (from Ahlswede et al.).

Like many fundamental concepts, network coding is based on a simple basic idea which was first stated in its beautiful simplicity in the the seminal paper by R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, "Network Information Flow" (IEEE Transactions on Information Theory, IT-46, pp. 1204-1216, 2000). The core notion of network coding is to allow and encourage mixing of data at intermediate network nodes. A receiver sees these data packets and deduces from them the messages that were originally intended for thethat data sink. In contrast to traditional ways to operate a networkrouting that trytries to avoid collisions of data streams as much as possible, this elegant principle implies a plethora of surprising results. One of the most exciting opportunities of the approach is the use of random mixing of data streams, thus freeing up the symmetrizing properties of random coding arguments in the analysis of networks. Not only is network coding a fresh and sharp tool that has the potential to open up stagnant fundamental areas of research, but also due to its cross-cutting nature, it naturally suggests a unified treatment of previously segmented areas. A striking example of the type of unification that network coding makes possible is the recently found elegant and complete characterization of the capacity of multicast networks, which was possible only through the joint treatment of coding and routing.

==Examples ==

==Example ==

In thisthe examplebutterfly network, two sources having access to bits A and B at a rate of one bit per unit time have to communicate these bits to two sinks so that both sinks receive both bits per unit time. All links have a capacity of one bit per unit time. The network problem can be satisfied with the transmissions outlined in the example but cannot be satisfied with only forwarding of bits at intermediate packet nodes.