The Nonuniform Discrete Fourier Transform

In many applications, when the representation of a discrete-time signal or a system in the frequency domain is of interest, the Discrete-Time Fourier Transform (DTFT) and the z-transform are often used. In the case of a discrete-time signal of finite length, the most widely used frequency-domain representation is the Discrete Fourier Transform (DFT), which is simply composed of samples of the DTFT of the sequence at equally spaced frequency points, or equivalently, samples of its z-transform at equally spaced points on the unit circle. A generalization of the DFT, introduced in this chapter, is the Nonuniform Discrete Fourier Transform (NDFT), which can be used to obtain frequency domain information of a finite-length signal at arbitrarily chosen frequency points. We provide an introduction to the NDFT and discuss its applications in the design of 1-D and 2-D FIR digital filters. We begin by introducing the problem of computing frequency samples of the z-transform of a finite-length sequence. We develop the basics of the NDFT, including its definition, properties and computational aspects. The NDFT is also extended to two dimensions. We propose NDFT-based nonuniform frequency sampling techniques for designing 1-D and 2-D FIR digital filters, and present design examples. The resulting filters are compared with those designed by other existing methods.