On Matrix Representation of Extension Field GF(<i>p^L</i>) and Its Application in Vector Linear Network Coding

Abstract

For a finite field GF(pL) with prime p and L>1, one of the standard representations is L×L matrices over GF(p) so that the arithmetic of GF(pL) can be realized by the arithmetic among these matrices over GF(p). Based on the matrix representation of GF(pL), a conventional linear network coding scheme over GF(pL) can be transformed to an L-dimensional vector LNC scheme over GF(p). Recently, a few real implementations of coding schemes over GF(2L), such as the Reed–Solomon (RS) codes in the ISA-L library and the Cauchy-RS codes in the Longhair library, are built upon the classical result to achieve matrix representation, which focuses more on the structure of every individual matrix but does not shed light on the inherent correlation among matrices which corresponds to different elements. In this paper, we first generalize this classical result from over GF(2L) to over GF(pL) and paraphrase it from the perspective of matrices with different powers to make the inherent correlation among these matrices more transparent. Moreover, motivated by this correlation, we can devise a lookup table to pre-store the matrix representation with a smaller size than the one utilized in current implementations. In addition, this correlation also implies useful theoretical results which can be adopted to further demonstrate the advantages of binary matrix representation in vector LNC. In the following part of this paper, we focus on the study of vector LNC and investigate the applications of matrix representation related to the aspects of random and deterministic vector LNC.

Keywords

• vector linear network coding
• matrix representation
• finite field