Fourier Analysis

Fourier Analysis is rooted in the knowledge that almost all signals can be represented as a sum of cosines and it makes sense to break them down into their component cosines in order to analyze for things like noise, discontinuities etc. in the frequency domain.

Continuous Time Analysis

In continuous domain Fourier Transform analysis equation is given by \[ X(e^{j\omega})= \int_{-\infty}^{\infty} x(t) e^{-j\omega t}dt \] and the synthesis equation is

\[ x(t)=\frac{1}{2\pi}\int_{-\infty}^{\infty} X(e^{j\omega}) e^{j\omega t} d\omega \]

This continuous fourier transform exists only and only if signal \(x(t)\) is absolutely integrable.

\[ \int_{-\infty}^{\infty} x(t) dt \lt \infty \]

Before we move on to discrete domain it is helpful to point out that Fourier Transform requires knowledge of signal at all times which is really impractical in discrete domain. Continuous Time Fourier Series [CTFS] attempts to address this issue and is given by

\[ c_{n}=\frac{1}{T} \int_{0}^{T} x(t) e^{-jn \omega_{0}t} dt \]

where \(c_{n}\) is the \(nth\) harmonic and \(\omega_{0}\) is the fundamental frequency.

The synthesis equation is given by

\[ x(t)=\sum_{n=-\infty}^{\infty} c_{n}e^{jn \omega_{0}t} \]

CTFS seems better from a digital point of view than it actually is. The integral is finite but for synthesis equation we still need to calculate for all values of \(n\) which isn't any simpler for computers.

Discrete Time Analysis

Corresponding to continuous time fourier transform, we have Discrete Time Fourier Transform(DTFT). \[ X(e^{j \omega_{n}})= \sum_{k=-\infty}^{\infty} x(k) e^{-jk \omega_{n}} \] where \(\omega_{n} \in (-\pi,\pi)\) is the normalized frequency.It is normalized with respect to sampling frequency \(f_{s}\). DTFT exists only if \(x(k)\) is absolutely summable.

\[ \sum_{k=-\infty}^{\infty}x(k) \lt \infty \]

Inverse Discrete Time Fourier Transform is similarly given by

\[ x(k)=\frac{1}{2\pi}\int_{\omega_{n}=-\pi}^{\pi} X(e^{j \omega_{n}}) e^{jk \omega_{n}} d\omega_{n} \]

One problem that jumps out is that periodic signals, eg. sinusoids, are neither absolutely summable nor of finite energy which means that DTFT can not exist for these signals. Discrete Time Fourier Series is defined for periodic signal \(x_{p}(k)\). \[ x_{p}(k)=\sum_{n=0}^{N-1} c_{n} e^{\frac{j2\pi nk}{N}} \] where the complex exponential \(e^{\frac{j2\pi nk}{N}}\) is periodic in both \(k\) and \(n\) with period \(N\). \(c_{n}\) is known as the spectrum of the signal and , because of periodicity of \(n\) ,\(k\) and Nyquist sampling rate, it is given by

\[ c_{n}=\frac{1}{N}\sum_{k=0}^{N-1} x_{p}(k)e^{-\frac{j2\pi nk}{N}} \]

It should be noted that both analysis and synthesis equations of DTFS are finite summations which makes it suitable for digital implementation with only problem being it is only defined for periodic signals which makes its implementation tricky and leads us to Discrete Fourier Transform

Discrete Fourier Transform

Discrete Fourier Transform is a mapping of \(N\)-sample time domain signal to \(N\)-sample frequency domain signal. Signals in either or both domain can be complex so it is a \(C^{N}\leftrightarrow C^{N}\) mapping. The Discrete Fourier Transform of a signal \(x(k)\) is given by \[ X(n)=\sum_{k=0}^{N-1} x(k) e^\frac{-j2\pi kn}{N} \] for \( n \in [0,1,...,N-1]\)

The synthesis equation for DFT is known as Inverse Discrete Fourier Transform and is given by \[ x(k)=\frac{1}{N}\sum_{n=0}^{N-1} X(n) e^\frac{j2\pi kn}{N} \] for \( k \in [0,1,...,N-1]\) Unlike DTFS, DFT assumes periodicity and we don't have to prove periodicity of a given signal before computing its transform which makes things significantly easier. One of the most important property of DFT is that it is orthogonal. DFT's basis functions \(e^\frac{-j2\pi kn}{N}\) form a 2D orthogonal matrix. This property is utilized in numerous signal processing and digital communications applications.

Fast Fourier Transform

One issue with DFT is that it is computationally intensive for large values of \(N\). \[ X(n)=\sum_{k=0}^{N-1} x(k) e^\frac{-j2\pi kn}{N} \] If you look at the DFT equation, we need \(N^{2}\) complex multiplication and approximately \(N^{2}\) addition operations in order to compute \(X(n)\) and this may get unwieldy for large values of N. Fast Fourier Transform is an algorithm (there are many algorithms actually) that makes DFT computation faster. A simple introduction follows. Let us consider a N-point DFT where \(N=2^{n}\). We can partition \(x(k)\) into even and odd terms \(x_{e}(k)\) and \(x_{o}(k)\) of length \(N/2\) each. \(x_{e}(k)= x(2k)\) are even terms and \(x_{o}(k)= x(2k+1)\) are odd terms.

Taking DFT of \(x(k)\) \[ X(n)=\sum_{k=0}^{N-1} x(k) e^\frac{-j2\pi kn}{N} \] \[ X(n)=\sum_{k=0}^{N/2-1} x(2k) e^\frac{-j2\pi 2kn}{N} + \sum_{k=0}^{N/2-1} x(2k+1) e^\frac{-j2\pi (2k+1)n}{N} \] \(e^\frac{-j2\pi 2kn}{N}\) in equation above are basis functions of a \(N\)-point DFT but since each part of the signal is being computed for \(N/2\)-point DFT, the equations can be re-written as \[ X(n)=\sum_{k=0}^{N/2-1} x(2k) e^\frac{-j2\pi kn}{N/2} + \sum_{k=0}^{N/2-1} x(2k+1) e^\frac{-j\pi n}{N/2}e^\frac{-j2\pi kn}{N/2} \] It can be seen that above equation represents sum of two \(N/2\) DFTs with second one having a ``twiddle'' factor of \(e^\frac{-j\pi n}{N/2}\). The computation needed for this configuration. ,excluding twiddle factor multiplication, is, therefore \(2(N/2)^{2} = \frac{N^2}{2}\) which is roughly half of original \(N\)-point DFT. We can similarly keep halving the signal to the point where only \(N\log_{2}(N)\) computations are needed. As can be seen, for large values of N FFT algorithm is far superior to original DFT and is an essential part of any engineering and mathematical toolbox.