Linear time encoding of cycle GF(2/sup P)/ codes through graph analysis

Abstract

In this letter, we present a linear-complexity encoding algorithm for any cycle GF(2/sup P/) code C/sub E/(G,H). We just need to investigate the case where G is a nontrivial connected graph. If G is a tree, the only codeword is the all-zero word. If G is not a tree, first, we show that through graph analysis H can be transformed into an equivalent block-diagonal upper-triangular form simply by permuting the rows and columns of H; then, we show that whether H is full row-rank or not, the code can be encoded in linear time.