ABSTRACT
In this chapter, we study the theoretical aspects of digital signal processing algorithms for the computation of discrete Fourier transform (DFT) and convolutions. The various polynomial algebra results are cast in the matrix-vector form and certain lower bounds are derived for the computational complexity of the convolution algorithms. It is shown that in certain special cases of interest, the representation of the algorithm can be suitably altered without effecting the final results. This alteration can lead to computational simplifications and a different organization of the 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/f.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/>. We begin our description by defining and analyzing the DFT.
