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 a whole bunch of Digital Signal Processing (DSP) applications. 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

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\ne k}(1-z_iz^{-1}),\quad k=0, 1, ..., N-1$

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

$X(z)=c_0 + c_1(1-z_0z^{-1}) + c_2(1-z_0z^{-1})(1-z_1z^{-1}) + ... + C_{N-1}\prod_{k=0}^{N-2}(1-z_kz^{-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_0z_1^{-1}},$

$c_2 = \frac{\hat X [2]-c_0-c_1(1-z_0z^{-1})}{(1-z_0z_2^{-1})(1-z_1z_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_0z_1^{-1}) & 0 & 0 & \cdots & 0\\ 1 & (1-z_0z_2^{-1}) & (1-z_0z_2^{-1})(1-z_1z_2^{-1}) & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & (1-z_0z_{N-1}^{-1}) & (1-z_0z_{N-1}^{-1})(1-z_1z_{N-1}^{-1}) & \cdots & \prod_{k=0}^{N-2}(1-z_kz_{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_kz^{-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_1N_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_1N_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^3N_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