This book will give the readers the basic knowledge of discrete Fourier transform (DFT) and its fast algorithms. The text consists of four chapters: The first chapter contains introductory remarks concerning methods of computer algebra and its applications. The second chapter describes the principle of the DFT and its development for general use. In detail, the conventional method of the DFT is first remarked. The concept of the generalized DFT is then given. Further, its property is analyzed. The third chapter derives fast algorithms of the DFT and the generalized DFT from the ordinary ones. Speeding up of the DFT implementation can be realized by reducing algebraic operations in numbers. Through the above two chapters, topics of the so-called multiplicative complexity are discussed. The last chapter is devoted to a description of the methods and applications of special implementation of the DFT and FFT.
In our review, the contents and their arrangement are almost available for the purpose of providing the basic knowledge of the DFT and its fast algorithms. If there were anything to be added, the thing is to refer to the methods for DFT and FFT convolution of an infinite and a finite duration waveform. It is so because that the digital convolution must be computed as a counter measure for the so-called window effect due to recording within a finite interval of time. If possible, the text could touch on the method of pipeline.