A new structured design method for convolutions over finite fields, Part I
M. Wagh, S.D. Morgera · IEEE Transactions on Information Theory · 1983
The structure of bilinear cyclic convolution algorithms is explored over finite fields. The algorithms derived are valid for any length not divisible by the field characteristic and are based upon the small length polynomial multiplication algorithms. The multiplicative complexity of these algorithms is small and depends on the field of constants. The linear transformation matricesA, B(premultiplication), andC(postmultiplication) defining the algorithm have block structures which are related to one another. The rows ofAandBand the columns ofCare maximal length recurrent sequences. Because of the highly regular structure ofA, B, andC, the algorithms can be very easily designed even for large lengths. The application of these algorithms to the decoding of Reed-Solomon codes is also examined.