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 allows one to obtain frequency domain information of a finite length signal 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 many signals have their energy distributed nonuniformly in the frequency domain. Therefore, a nonuniform sampling scheme could be more convenient and useful in many Digital Signal Processing (DSP) applications. For example, NDFT provides a variable spectral resolution controlled by the user.

Note that NDFT reduces to DFT when the sampling points are located on the unit circle at equally spaced angles.

1-D NDFT

Definition

1-D NDFT of a sequence x[n] of length N is^[1]

$X(z_{k})=X(z)|_{{z=z_{k}}}=\sum _{{n=0}}^{{N-1}}x[n]z_{k}^{{-n}},\quad k=0,1,...,N-1,$

where $X(z)$ is the Z-transform of $x[n]$, and $\{z_{i}\}_{{i=0,1,...,N-1}}$ are arbitrarily distinct points in the z-plane.

Expressing the above as matrix, we get

${\mathbf {X}}={\mathbf {D}}{\mathbf {x}}$

where

${\mathbf {X}}={\begin{bmatrix}X(z_{0})\\X(z_{1})\\\vdots \\X(z_{{N-1}})\end{bmatrix}},\quad {\mathbf {x}}={\begin{bmatrix}x[0]\\x[1]\\\vdots \\x[N-1]\end{bmatrix}},{\text{ and}}\quad {\mathbf {D}}={\begin{bmatrix}1&z_{0}^{{-1}}&z_{0}^{{-2}}&\cdots &z_{0}^{{-(N-1)}}\\1&z_{1}^{{-1}}&z_{1}^{{-2}}&\cdots &z_{1}^{{-(N-1)}}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&z_{{N-1}}^{{-1}}&z_{{N-1}}^{{-2}}&\cdots &z_{{N-1}}^{{-(N-1)}}\end{bmatrix}}.$

As we can see, the NDFT is characterized by $\mathbf{D}$ and hence the N ${z_k}$ points. If we further factorize $det({\mathbf {D}})$, we can see that $\mathbf{D}$ is nonsingular provided the N ${z_k}$ points are distinct. If $\mathbf{D}$ is nonsingular, we can get a unique inverse NDFT as following:

${\mathbf {x}}={\mathbf {D^{{-1}}}}{\mathbf {X}}$

Given ${\mathbf {X}}{\text{ and }}{\mathbf {D}}$, we can use Gaussian elimination to solve $\mathbf {x}$. However, the complexity of this method is $O(N^{3})$. To solve this problem more efficiently, we first determine $X(z)$ directly by polynomial interpolation

${\hat X}[k]=X(z_{k}),\quad k=0,1,...,N-1,$

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 $X(z)$ as the Lagrange polynomial of order N-1, we get

$X(z)=\sum _{{k=0}}^{{N-1}}{\frac {L_{k}(z)}{L_{k}(z_{k})}}{\hat X}[k],$

where $\{L_{i}(z)\}_{{i=0,1,...,N-1}}$ are the fundamental polynomials:

$L_{k}(z)=\prod _{{i\neq k}}(1-z_{i}z^{{-1}}),\quad k=0,1,...,N-1$

Expressing $X(z)$ by Newton interpolation method, we get

$X(z)=c_{0}+c_{1}(1-z_{0}z^{{-1}})+c_{2}(1-z_{0}z^{{-1}})(1-z_{1}z^{{-1}})+...+C_{{N-1}}\prod _{{k=0}}^{{N-2}}(1-z_{k}z^{{-1}}),$

where $c_{j}$ is the divided difference of the jth order of ${\hat X}[0],{\hat X}[1],...,{\hat X}[j]$ with respect to $z_{0},z_{1},...,z_{j}$:

$c_{0}={\hat X}[0],$

$c_{1}={\frac {{\hat X}[1]-c_{0}}{1-z_{0}z_{1}^{{-1}}}},$

$c_{2}={\frac {{\hat X}[2]-c_{0}-c_{1}(1-z_{0}z^{{-1}})}{(1-z_{0}z_{2}^{{-1}})(1-z_{1}z_{2}^{{-1}})}},$

$\vdots$

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 $\{c_{j}\}$:

${\mathbf {L}}{\mathbf {c}}={\mathbf {X}}$

where

${\mathbf {X}}={\begin{bmatrix}{\hat X}[0]\\{\hat X}[1]\\\vdots \\{\hat X}[N-1]\end{bmatrix}},\quad {\mathbf {c}}={\begin{bmatrix}c_{0}\\c_{1}\\\vdots \\c_{{N-1}}\end{bmatrix}},{\text{ and}}\quad {\mathbf {L}}={\begin{bmatrix}1&0&0&0&\cdots &0\\1&(1-z_{0}z_{1}^{{-1}})&0&0&\cdots &0\\1&(1-z_{0}z_{2}^{{-1}})&(1-z_{0}z_{2}^{{-1}})(1-z_{1}z_{2}^{{-1}})&0&\cdots &0\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots \\1&(1-z_{0}z_{{N-1}}^{{-1}})&(1-z_{0}z_{{N-1}}^{{-1}})(1-z_{1}z_{{N-1}}^{{-1}})&\cdots &\prod _{{k=0}}^{{N-2}}(1-z_{k}z_{{N-1}}^{{-1}})\end{bmatrix}}.$

By the above equation, $\{c_{j}\}$ can be computed within $O(N^{3})$ operations. In this way Newton interpolation is more efficient than Lagrange Interpolation unless the latter is modified by

$L_{{k+1}}(z)={\frac {(1-z_{{k+1}}z^{{-1}})}{(1-z_{k}z^{{-1}})}}L_{k}(z),\quad k=0,1,...,N-1$

2-D NDFT

2-D NDFT of a sequence $x[n_{1},n_{2}]$ of size $N_{1}\times N_{2}$ is^[2]

${\hat X}(z_{{1k}},z_{{2k}})=\sum _{{n_{1}=0}}^{{N_{1}-1}}\sum _{{n_{2}=0}}^{{N_{2}-1}}x[n_{1},n_{2}]z_{{1k}}^{{-n_{1}}}z_{{2k}}^{{-n_{2}}},\quad k=0,1,...,N_{1}N_{2}-1,$

where ${\hat X}(z_{{1k}},z_{{2k}})$ is the 2-D z-transform of $x[n_{1},n_{2}]$, and $(z_{{1k}},z_{{2k}})$ are arbitrarily distinct $N_{1}N_{2}$ points in the 4-D $(z_{1},z_{2})$ space.

As in the 1-D case, we can express the above equation as

${\mathbf {{\hat X}}}={\mathbf {D}}{\mathbf {X}},$

and the matrix $\mathbf{D}$ is also depends only on the choice of those sampling points. However, even if those sampling points are distinct, $\mathbf{D}$ 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 $det({\mathbf {D}})$ for a specific set of sampling points. In general, the complexity of 2-D NDFT $O(N_{1}^{3}N_{2}^{3})$.

Applications

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

See also

• Spectral estimation

Notes

1. Marvasti 2001, p. 326.
2. Marvasti 2001, p. 334.

References

• F. Marvasti, Nonuniform sampling: Theory and Practice. Plenum Publishers Co., 2001, pp. 325–360.

External links

• 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