A Rank-Metric Approach to Error Control in Random Network Coding

Abstract

<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> The problem of error control in random linear network coding is addressed from a matrix perspective that is closely related to the subspace perspective of KÖtter and Kschischang. A large class of constant-dimension subspace codes is investigated. It is shown that codes in this class can be easily constructed from rank-metric codes, while preserving their distance properties. Moreover, it is shown that minimum distance decoding of such subspace codes can be reformulated as a generalized decoding problem for rank-metric codes where partial information about the error is available. This partial information may be in the form of erasures (knowledge of an error location but not its value) and <emphasis emphasistype="boldital">deviations</emphasis> (knowledge of an error value but not its location). Taking erasures and deviations into account (when they occur) strictly increases the error correction capability of a code: if <emphasis><formula formulatype="inline"><tex>$\mu$</tex></formula></emphasis> erasures and <emphasis><formula formulatype="inline"><tex>$\delta$</tex></formula></emphasis> deviations occur, then errors of rank <emphasis><formula formulatype="inline"><tex>$t$</tex> </formula></emphasis> can always be corrected provided that <emphasis><formula formulatype="inline"><tex>$2t \leq d - 1 + \mu + \delta$</tex></formula></emphasis>, where <emphasis><formula formulatype="inline"><tex>$d$</tex></formula></emphasis> is the minimum rank distance of the code. For Gabidulin codes, an important family of maximum rank distance codes, an efficient decoding algorithm is proposed that can properly exploit erasures and deviations. In a network coding application, where <emphasis><formula formulatype="inline"><tex>$n$</tex></formula></emphasis> packets of length <emphasis><formula formulatype="inline"><tex>$M$</tex></formula></emphasis> over <emphasis><formula formulatype="inline"><tex>$\BBF _{q}$</tex></formula></emphasis> are transmitted, the complexity of the decoding algorithm is given by <emphasis><formula formulatype="inline"> <tex>$O(dM)$</tex></formula></emphasis> operations in an extension field <emphasis><formula formulatype="inline"><tex>$\BBF _{q^{n}}$</tex></formula></emphasis>. </para>