Fast Fourier Transform: One Dimensional Data Sequences

In this chapter, we study fast algorithms for computing the discrete Fourier transfonn (OFT). Collectively, they are known as Fast Fourier Transform: One-Dimensional Data Sequences In this chapter, we study fast algorithms for computing the discrete Fourier transform (DFT). Collectively, they are known as fast Fourier transform (FFT) algorithms. This chapter deals with one-dimensional data sequences and the next chapter is focused on two- and higher-dimensional sequences. The nature of FFT algorithms depends on the number-theoretic properties of the data sequences and their indices. This fact will influence not only our presentation of the FFT but also the overall structure of the algorithms. We can partition the FFT into three categories: (a) FFT for complex-valued data sequences; (b) FFT for real-valued data sequences; and (c) FFT for data sequences defined in finite number systems (rings or fields). For the FFT belonging to category (a), one may exploit the number-theoretic properties of the indices only. For the FFT belonging to category (b), one may desire to exploit the real-valued nature of the data sequence and/or restrict the intermediate quantities to be real-valued to the extent possible. For the FFT belonging to category (c), there may be additional mathematical properties that could play a role in the derivation of an algorithm. All the quantities in this chapter are defined over a field https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315141312/eb9507de-5963-43d1-b207-f60a521e202b/content/eqn12_13.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/>. We begin our description by defining and analyzing the mathematical properties of DFT.