%0 Journal Article
%T A Survey of Linear Network Coding and Network Error Correction Code Constructions and Algorithms
%A Michele Sanna
%A Ebroul Izquierdo
%J International Journal of Digital Multimedia Broadcasting
%D 2011
%I Hindawi Publishing Corporation
%R 10.1155/2011/857847
%X Network coding was introduced by Ahlswede et al. in a pioneering work in 2000. This paradigm encompasses coding and retransmission of messages at the intermediate nodes of the network. In contrast with traditional store-and-forward networking, network coding increases the throughput and the robustness of the transmission. Linear network coding is a practical implementation of this new paradigm covered by several research works that include rate characterization, error-protection coding, and construction of codes. Especially determining the coding characteristics has its importance in providing the premise for an efficient transmission. In this paper, we review the recent breakthroughs in linear network coding for acyclic networks with a survey of code constructions literature. Deterministic construction algorithms and randomized procedures are presented for traditional network coding and for network-control network coding. 1. Introduction The theoretical foundations of network coding were first provided by Ahlswede et al. [1]. The idea originated in the sphere of satellite communications, in the scenario in Figure 1. A satellite acts as relay node for the bidirectional communication between two ground stations in nonline-of-sight. The relay receives the data from the ground stations, and it broadcasts a function of the two messages (Figure 1(b)). Each station can decode the respective message from the transmitted and the received information, with a remarkable saving of bandwidth. Figure 1: Bidirectional communication through satellite. With the traditional method (a) the satellite (s) can receive and retransmit one message at a time. With network coding (b) a xor b is broadcasted to both ground nodes, which are able to decode the respective messages. Ahlswede et al. applied the idea of coding at intermediate nodes to general multinode networks, referring to it as the network information flow problem. Network coding allows network nodes to perform decoding and reencoding of the received information, resulting in the retransmission of messages that are a function of the incoming messages, as opposed to traditional routing (which can be regarded as a special case of network coding). The network equivalent of the satellite example is the butterfly network (Figure 2). The benefit of coding at the bottleneck edge is the increased rate with respect to the case of traditional networking, in which the intermediate node can only forward one packet at a time. The major achievement of network coding is, thus, the possibility of reaching the full theoretical
%U http://www.hindawi.com/journals/ijdmb/2011/857847/