Low complexity optimal algebraic multicast codes

We present a low complexity algorithm for designing algebraic codes that achieve the information theoretic capacity for the multicast problem on directed acyclic networks. These codes operate over field sizes which are significantly smaller than those previously known, leading to significantly lower design and implementation complexity, and network link usage. These codes can be extended for networks with cycles and delays, and for robustness properties.

A network is represented by a directed graph g = (V, E) with a vertex set V and edge set E. Multiple edges are allowed between vertices, and g is acyclic. A source node 8 €- V generating information at rate R, and a set of N receiver nodes R = {Tl,r2, . , rN} C V, are specified. Nodes are allowed to transmit on outgoing edges any causal function of information on incoming edges. The multicast capacity is defined as the maximum rate at which identical information can be decoded by each node in R. The multicast network coding problem is the 4-tuple (g, s, R, R), and it is said to have a solution if there exist causal functions for each node in V such that the multicast capacity equals R. The solution comprises these functions at each node in V and the decoders at nodes in ‘R. Let C S mini {Ci}, where Ci is the min-cut max-flow capacity of the network between s and ‘ft. For any e > O, the multicast network coding problem (G, s, R, C — e) was shown by a random coding argument in [1] to have a solution. Further, [2] defined an IF2tn -linear network as follows. Source bits are concatenated in blocks of length m to form symbols in the finite field . Nodes in V perform linear combinations (over IF2m) of the symbols on incoming edges to obtain symbols on outgoing edges. They show that for 2^m > NC there exist IF2tn -linear networks which solve the network coding problem.