Transform Pair

The Fourier transform links a signal with its representation in the frequency domain. There are several forms of the Fourier transform depending whether the input signal is continuous, finite or periodic. We define the following transforms accordingly:

Fourier Transform (FT):

$$X(\sigma) = \int_{-\infty}^{+\infty} x(t) e^{-2\pi i\sigma t} dt$$ (3.1)

$$x(t) = \frac{1}{2\pi} \int_{-\infty}^{+\infty} X(\sigma) e^{2\pi i\sigma t} d\sigma$$ (3.2)

Discrete-Time Fourier Transform (DTFT):

$$\hat{X}(\sigma) = \sum_{n=-\infty}^{\infty} x[n] e^{-2\pi i \sigma n}$$ (3.3)

$$x[n] = \frac{1}{2\pi} \int_{-\pi}^{+\pi} \hat{X}(\sigma) e^{2\pi i\sigma n} d\sigma$$ (3.4)

Discrete Fourier Transform (DFT):

$$\hat{X}_M[\mu] = \sum_{n=0}^{N-1} \hat{x}_N[n] e^{-in \frac{2\pi \mu}{M}}$$ (3.5)

$$\hat{x}_N[n] = \frac{1}{M} \sum_{\mu=0}^{M-1} \hat{X}_M[\mu] e^{i\mu \frac{2\pi n}{N}}$$ (3.6)

To get $\hat{x}_N[n]$ back exactly from $\hat{X}_M[\mu]$ we need $M \geq N$, but in most applications typically $M = N$. The computational effort for this transform is $\mathcal{O}(NM)$, or $\mathcal{O}(N^2)$ when $N = M$. There are more sophisticated algorithms named Fast Fourier Transform (introduced by Cooley and Tukey [5]); usually denoted as FFT that accomplishes the transform in $\mathcal{O}(N log N)$ time complexity. For the FFT, there are no restrictions on $N$, but the most well known version of the algorithm is the radix 2 transform, which assumes $N = 2^k$ [27].