Non-uniform discrete Fourier transform
In applied mathematics, the non-uniform discrete Fourier transform (NDFT) of a signal is a type of Fourier transform, related to a discrete Fourier transform or discrete-time Fourier transform, but in which the input signal is not sampled at equally spaced intervals. As a result of this, the computed Discrete Fourier Transform can also consist of unevenly sampled frequency values. It is however also possible to compute uniformly sampled frequency values from an unevenly sampled input signal.
As a generalized approach for nonuniform sampling, NDFT can help us to get the information of a finite length signal in frequency domain at any frequency. It can also be used to design the FIR filters as the role of DFT, no matter if it's 1-D or 2-D.
One of the reasons to adopt NDFT is that most signals have their energy distributed nonuniformly in the frequency domain. Therefore, a nonuniform sampling scheme could be more convenient and useful in lots of applications of Digital Signal Processing (DSP). For example, NDFT provides a variable spectral resolution controlled by the users.
Note that NDFT reduces to DFT when the sampling points are located on the unit circle at equally spaced angles.
1-D NDFT of a sequence x[n] of length N is
where is the z-transform of , and are arbitrarily distinct points in the z-plane.
Expressing the above as matrix, we get
As we can see, the NDFT is characterized by and hence the N points. If we further factorize , we can see that is nonsingular provided the N points are distinct. If is nonsingular, we can get a unique inverse NDFT as following:
Given , we can use Gaussian elimination to solve . However, the complexity of this method is . To solve this problem more efficiently, we first determine directly by polynomial interpolation
then x[n] is the coefficients of the above interpolating polynomial which can be solved more efficiently. This is illustrated in the next subsection.
Solving The Inverse NDFT
Expressing as the Lagrange polynomial of order N-1, we get
where are the fundamental polynomials:
Expressing by Newton interpolation method, we get
where is the divided difference of the jth order of with respect to :
The disadvantage of Lagrange representation is that any additional point included will increase the order of the interpolating polynomial, leading to the need of recomputing all the fundamental polynomials. However, any additional point included in Newton representation only require one more term.
We can use a lower triangular system to solve :
By the above equation, can be computed within operations. In this way Newton interpolation is more efficient than Lagrange Interpolation unless the latter is modified by
2-D NDFT of a sequence of size is
where is the 2-D z-transform of , and are arbitrarily distinct points in the 4-D space.
As in the 1-D case, we can express the above equation as
and the matrix is also depends only on the choice of those sampling points. However, even if those sampling points are distinct, could still be singular. No rules for determining whether the matrix is nonsingular or not have been found. Therefore, for all implementation of 2-D NDFT, we just check for a specific set of sampling points. In general, the complexity of 2-D NDFT .
The applications of NDFT are:
- Digital filter design
- Spectral analysis
- Antenna array design
- Antenna pattern synthesis with prescribed nulls
- Decoding of dual-tone multi-frequency(DTMF) signals
- Dual-tone multi-frequency tone detection
- Non-Uniform Fourier Transform: A Tutorial.
- Nonuniform fast Fourier transforms using min-max interpolation. CiteSeerX: 10.1.1.15.3781.
- Notation, the NDFT and the NFFT
- NFFT 3.0 – Tutorial
- Marvasti 2001, p. 326.
- Marvasti 2001, p. 334.
- F. Marvasti, Nonuniform sampling: Theory and Practice. Plenum Publishers Co., 2001, pp. 325–360.