ABSTRACT
In the next two chapters, we describe fast algorithms for computing one- and two-dimensional cyclic convolution of discrete sequences. The present chapter deals with one-dimensional algorithms and techniques for converting one-dimensional cyclic convolution to two- or higher-dimensional convolution. Chapter 10 is on fast algorithms for two- and higher-dimensional algorithms for cyclic convolution. In addition, we attempt to obtain closed form expressions for the polynomials in CRT-P reconstruction and various matrices that arise in the bilinear formulation of fast algorithms. The number systems included in this chapter are the fields of complex, real and rational numbers, finite fields, and finite integer rings. The analysis presented here is expected to be useful in understanding the structure of cyclic convolution algorithms in different number systems, organization of various steps in the computation, and overall realization of the algorithms.
