On Construction of Variable-Rate and Static Linear Network Codes

Abstract

On a (single-source) multicast network with possible edge failures, variable-rate and static linear network coding (LNC) is a special class of scalar LNC schemes under which the source can generate a message of an arbitrary rate so that every eligible receiver can recover the message. In this paper, we formulate the variable-rate and static properties in the context of vector LNC, which is a generalization of scalar LNC. The variable-rate property formulated herein is stronger than the original one in the sense that when the message rate changes, it requires preserving the coding operations not only at intermediate nodes but also at the source, and the decoding matrix at every eligible receivers need not be modified. Under the new formulation, we further propose a method to reduce the construction of a variable-rate and static linear solution for a multicast network to the construction of a static linear solution for an associated multicast network. It turns out that every algorithm to construct a linear solution can be adopted to construct a linear solution with the additional variable-rate property.

Keywords

• Network coding
• variable-rate
• static network codes
• vector network codes