Multiplicative complexity of bilinear algorithms for cyclic convolution over finite fields (Q751615)

The author investigates the multiplicative complexity of bilinear algorithms for cyclic convolution over finite fields. It has been shown that mutually prime factor algorithms are inferior to directly designed algorithms for all lengths except those whose factors have relatively prime exponents. Several complexity results have been provided for factor lengths of specific form, and the manner in which cyclic convolution algorithms lead to linear algebraic error-correcting codes is discussed. The paper is of interest to researchers seeking efficient digital signal processing algorithms, and also to coding theorists.