Fourier Transform

Idea

Towards Frequency Domain

The Fourier Transformation is a mathematical technique that transforms a signal from its original domain (often time or space) into a representation in the frequency domain. It allows us to break down complex signals into simpler components—specifically, the different frequencies that make up the signal. In essence, the Fourier Transformation provides a different perspective on the same information, highlighting the underlying frequency components and their amplitudes.

High Level Idea

Fourier transformation can be understood as a transformation of coordinates in a Hilbert space (A infinite dimensional vector space equipped with an inner product). The general idea is that, every function can be seen as a vector in a infinite dimensional space, and the transformation between functions could be the different representations of a function vector in different coordinates.

Hilbert Space

A Hilbert space is a complete vector space equipped with an inner product. It generalizes the notion of Euclidean space to infinite dimensions and provides the framework for discussing concepts like orthogonality, projection, and more in a rigorous manner. Functions can be elements of a Hilbert space, with operations like addition and scalar multiplication defined pointwise.

Function Space

In the context of Fourier transforms, we typically consider the Hilbert space $L^2(\mathbb{R})$, the space of square-integrable functions. This means functions $f$ such that:

$${\int }_{-\infty }^{\infty }|f(x){|}^{2}dx<\infty$$

Coordinate Transformation

The Fourier transform can be viewed as changing the "basis" in this function space from the time (or spatial) domain to the frequency domain.

In $L^2(\mathbb{R})$, functions are often represented in terms of the standard basis, which consists of functions like Dirac delta functions that are localized in space. To simplify this, you could view a function as

$$\mathbf{f}=\sum _{n=-\infty }^{\infty }f(n){\mathbf{e}}_n$$

where $f(n)$ is the value of $f$ at point $n$, and ${\mathbf{e}}_n$ is the corresponding standard basis.

Now, if we apply a coordinate transformation ${\mathbf{e}}_n\to {\mathbf{d}}_n$, to obtain the representation of $\mathbf{f}$ in this new space, we are supposed to calculate its projection

$$f(n)\cdot {\mathbf{d}}_n=⟨\mathbf{f},{\mathbf{d}}_n⟩{\hat{\mathbf{d}}}_n={\int }_{-\infty }^{\infty }f(t)d_n(t)\mathrm{d}t\cdot {\hat{\mathbf{d}}}_n$$

where $⟨\cdot ,\ast ⟩=\int \cdot \ast \mathrm{d}t$ is the inner product, and then we sum them up

$$\mathbf{f}=\sum _{n=-\infty }^{\infty }F(n){\hat{\mathbf{d}}}_n$$

where

$$F(n)=⟨\mathbf{f},{\mathbf{d}}_n⟩={\int }_{-\infty }^{\infty }f(t)d_n(t)\mathrm{d}t$$

In particular, the Fourier transform projects these functions onto an orthogonal basis of complex exponentials $e^{i\omega x}$. These exponentials are eigenfunctions of the Fourier transform operator and form a complete orthonormal set in $L^2(\mathbb{R})$.

Fourier Series as Special Case of Fourier Transform

We define the Forward Fourier Transform as

$$X(\omega )=\mathcal{F}\left\{x(t)\right\}={\int }_{-\infty }^{\infty }x(t)\exp (-j\omega t)\mathrm{d}t$$

and the Inverse Fourier Transform as

$$x(t)={\mathcal{F}}^{-1}\left\{X(\omega )\right\}=\frac{1}{2\pi }{\int }_{-\infty }^{\infty }X(\omega )\exp (j\omega t)\mathrm{d}\omega$$

For periodic $x(t)$, assuming $x(t+T)=x(t)$, we can break this integral into a sum of integrals over each period:

$$X(\omega )=\sum _{k=-\infty }^{\infty }{\int }_{kT}^{(k+1)T}x(t)\exp (-j\omega t)\mathrm{d}t$$

Because $x(t)$ is the same over each period, we can factor out the integral over a single period $[0,T]$ or any interval of length $T$:

$$\begin{array}{rl}X(\omega )& =\sum _{k=-\infty }^{\infty }\left(\exp (-j\omega kT){\int }_0^{T}x(t)\exp (-j\omega t)\mathrm{d}t\right)\\ & =\left({\int }_0^{T}x(t)\exp (-j\omega t)\mathrm{d}t\right)\sum _{k=-\infty }^{\infty }\exp (-j\omega kT)\end{array}$$

where the second term is a Dirac comb $\frac{2\pi }{T}\sum _{n=-\infty }^{\infty }\delta \left(\omega -n\frac{2\pi }{T}\right)$. Therefore

$$X(\omega )=\frac{2\pi }{T}\left({\int }_0^{T}x(t)\exp (-j\omega t)\mathrm{d}t\right)\sum _{n=-\infty }^{\infty }\delta \left(\omega -n\frac{2\pi }{T}\right)$$

Substitute it to the inverse transform

$$x(t)=\frac{1}{T}{\int }_{-\infty }^{\infty }\left({\int }_0^{T}x(\tau )e^{-j\omega \tau }d\tau \right)\sum _{n=-\infty }^{\infty }\delta \left(\omega -n\frac{2\pi }{T}\right)e^{j\omega t}d\omega$$

Since the Dirac delta functions select specific frequencies, we can interchange the sum and the integral

$$\begin{array}{rl}x(t)& =\frac{1}{T}\sum _{n=-\infty }^{\infty }{\int }_0^{T}x(\tau )e^{-jn\frac{2\pi }{T}\tau }{e}^{jn\frac{2\pi }{T}t}d\tau \\ & =\frac{1}{T}\sum _{n=-\infty }^{\infty }{e}^{jn\frac{2\pi }{T}t}{\int }_0^{T}x(\tau )e^{-jn\frac{2\pi }{T}\tau }d\tau \end{array}$$

Let's define the coefficients $a_n$ as:

$$a_n=\frac{1}{T}{\int }_0^{T}x(\tau )e^{-jn{\omega }_0\tau }d\tau \text{where}{\omega }_0=\frac{2\pi }{T}$$

Then we get the Fourier Series as a special case of Fourier Transform (we replace $n$ by $k$ here)

$$x(t)=\sum _{k=-\infty }^{\infty }{a}_k\exp \left(jk{\omega }_{0}t\right),\text{where}{a}_k=\frac{1}{T}{\int }_0^{T}x(t)\exp (-jk{\omega }_{0}t)\mathrm{d}t$$

From Continuous to Discrete

Non-periodic Discrete Function

Assuming we sampling the function $x(t)$ with a time interval of $\Delta t$, let $t=n\Delta t$. Then the $\mathrm{d}t$ in continuous Fourier transform becomes $\Delta t$, and the new formula will be

$$X(\omega )=\sum _{n=-\infty }^{\infty }x(n\Delta t)\exp \left(-j\omega n\Delta t\right)\Delta t$$

This is called discrete-time Fourier transform (DTFT).

If we set $\Delta t$ to be $1$, we have

$$X(\omega )=\sum _{n=-\infty }^{\infty }x(n)\exp (-j\omega n)$$

where we can notice that $X(\omega )$ is a periodic since $X(\omega )=X(\omega +2\pi )$.

Note that $\exp (-j\omega n\Delta t)$ is the Fourier transform of $\delta (t-n\Delta t)$, so we can also define DTFT as

$$X(\omega )=\mathcal{F}\left\{\sum _{n=-\infty }^{\infty }x(n\Delta t)\delta (t-n\Delta t)\right\}$$

When $\Delta t=1$, this is

$$X(\omega )=\mathcal{F}\left\{\sum _{n=-\infty }^{\infty }x(n)\delta (t-n)\right\}$$

From this we can get the formula for inverse DTFT when $\Delta t=1$. Performing the inverse Fourier transform at both sides gives

$$\sum _{n=-\infty }^{\infty }x(n)\delta (t-n)={\mathcal{F}}^{-1}\left\{X(\omega )\right\}=\frac{1}{2\pi }{\int }_{-\infty }^{\infty }X(\omega )\exp (j\omega t)\mathrm{d}\omega$$

Sampling from $t=n$, we could have (Nothing that DTFT converts a non-periodic discrete function in time domain to a periodic continuous function in frequency domain, which happens to be the inverse of Fourier series, therefore the inverse of DTFT can be seen as the calculation of Fourier Series)

$$x[n]=\frac{1}{2\pi }{\int }_0^{2\pi }X(\omega )\exp (j\omega n)\mathrm{d}\omega$$

Periodic Discrete Function

Discrete Fourier Series (DFS)

If we have $x(t)=x(t+T)$, we can sample $x(t)$ from $[0,T)$ with $N$ points, that is, $T=N\cdot \Delta t$. If we set $\Delta t=1$, then it gives $T=N$ and $t=n\Delta t=n$. In this way, $t\in [0,T)⟹n\in \left\{0,1,\dots ,N-1\right\}$. Now we can rewrite the formula of continuous Fourier series (since Fourier series is a special case of Fourier transform for periodic functions) as

$$a_k=\frac{1}{N}\sum _{n=0}^{N-1}x(n)\exp \left(-jk{\omega }_{0}n\right)$$

where ${\omega }_0=\frac{2\pi }{T}=\frac{2\pi }{N}$. Similarly, $a_k$ is also periodic since $a_{k+N}=a_k$. This is know as discrete Fourier series (DFS)

$$x[n]=\sum _{k=0}^{N-1}{a}_k\exp (jk{\omega }_{0}n)$$

Discrete Fourier Transform (DFT)

$$X(\omega )=\sum _{n=0}^{N-1}x(n)\exp (-j\omega n)$$

where $\omega =k{\omega }_0,k=0,1,\dots ,N-1$

$$x[n]=\frac{1}{N}\sum _{k=0}^{N-1}X(k{\omega }_0)\exp (jk{\omega }_{0}n)$$

See Also

Fourier Series

Derive Fourier Transform from Fourier Series Fourier Series

Fourier Transforms

Continuous-Time Fourier Transform Discrete-Time Fourier Transform

Optical Application

Applications of Fourier Transform in Optics Fourier Optics