Alternatives to the discrete fourier transform

It is well-known that the discrete Fourier transform (DFT) of a finite length discrete-time signal samples the discrete-time Fourier transform (DTFT) of the same signal at equidistant points on the unit circle. Hence, as the signal length goes to infinity, the DFT approaches the DTFT. Associated with the DFT are circular convolution and a periodic signal extension. In this paper we identify a large class of alternatives to the DFT using the theory of polynomial algebras. Each of these transforms approaches the DTFT just as the DFT does, but has its own signal extension and own notion of convolution. Further, these transforms have Vandermonde structure, which enables their fast computation. We provide a few experimental examples that confirm our theoretical results.

1. INTRODUCTION

The discrete-time Fourier transform (DTFT) for a discrete-time signal with finite support is given by

$$y(\theta)=\sum_{0\leq\ell< n}s_{\ell}e^{-j\theta\ell}, \ \ \theta\in[0, \pi). \eqno{\hbox{(1)}}$$