# The Fourier Transform

## Continuous Time Fourier Transform

{% hint style="info" %}

### Definition 24

The Continuous Time Fourier Transform converts an aperiodic signal into the frequency domain.

$$X(\omega) = \int\_{-\infty}^{\infty}{x(t)e^{-j\omega t}dt}$$
{% endhint %}

The intuition for this transform comes from the Fourier Series. Only periodic signals can be represented by the Fourier Series. If we start with a finite signal $$x(t)$$, then we can just make it periodic by copying the domain over which it is nonzero so it repeats over a period $$T$$. Call this signal $$\tilde{x}(t)$$. Since $$\tilde{x}$$ is periodic, we can find its fourier series coefficients.

$$a\_k = \frac{1}{T}\int\_{T}{\tilde{x}(t)e^{-jn\frac{2\pi}{T}t}} = \frac{1}{T}\int\_{T}{x(t)e^{-jn\frac{2\pi}{T}t}} = \frac{1}{T}\int\_{-\infty}^{\infty}{x(t)e^{-jn\frac{2\pi}{T}t}}$$

These steps are possible because $$\tilde{x}(t) = x(t)$$ over a single period, and $$x(t)$$ is zero outside that period.

$$Ta\_k = \int\_{-\infty}^{\infty}{x(t)e^{-jn\frac{2\pi}{T}t}}$$

Notice that if we let $$T$$ approach infinity, then $$\omega\_0 = \frac{2\pi}{T}$$ becomes very small, so the $$Ta\_k$$ can almost be thought of as samples of some continuous time function. What this means is for a general aperiodic signal, regardless of if it is finite or not, we can think of it as having "infinite period" and thus made up of a continuous set of frequencies. This is what motivates the CTFT.

{% hint style="info" %}

### Definition 25

The Inverse Continuous Time Fourier Transform takes us from the frequency domain reprsentation of a function $$X(\omega)$$ to its time domain representation $$x(t)$$

$$x(t) = \frac{1}{2\pi}\int\_{-\infty}^{\infty}{X(\omega)e^{j\omega t}d\omega}$$
{% endhint %}

We can arrive at this equation by starting from the Fourier series again. Our faux signal $$\tilde{x}(t)$$ which was the periodic function we constructed out of our aperiodic one is represented by its Fourier Series

$$\tilde{x}(t) = \sum\_{k-\infty}^{\infty}{a\_ke^{jk\omega\_0t}} = \sum\_{k=-\infty}^{\infty}{\left(\frac{1}{T}X(\omega)\right)e^{j\omega t}}|\_{w=k\omega\_0}.$$

Notice this is just rewriting $$a\_k$$ as the samples of the Fourier Transform $$X(\omega)$$. $$T = \frac{2\pi}{\omega\_0}$$ so

$$\tilde{x}(t) = \frac{1}{2\pi} \sum\_{k=-\infty}^{\infty}{\omega\_0X(\omega)e^{j\omega t}}|\_{w=k\omega\_0}$$

$$x(t) = \lim\_{T\to\infty}{\tilde{x}(t)} = \lim\_{\omega\_0\to0}{\tilde{x}(t)} = \frac{1}{2\pi}\int\_{-\infty}^{\infty}{X(\omega)e^{j\omega t}d\omega}.$$

### Properties of the CTFT

For all these properties, assume that $$x(t) \leftrightarrow X(\omega)$$ and $$y(t) \leftrightarrow Y(\omega)$$ **Linearity:**

$$ax(t) + by(t) \leftrightarrow aX(\omega) + bY(\omega)$$

**Time Shift:**

$$x(t-t\_0) \leftrightarrow e^{-j\omega t\_0}X(\omega)$$

**Time/Frequency Scaling:**

$$x(at) \leftrightarrow \frac{1}{|a|}X(\frac{\omega}{a})$$

**Conjugation:**

$$x^*(t) \leftrightarrow X^*(-\omega)$$

**Derivative:**

$$\frac{d}{dt}x(t) \leftrightarrow j\omega X(\omega), \frac{d}{d\omega}X(\omega) \leftrightarrow -jt x(t)$$

**Convolution/Multiplication:**

$$(x*y)(t) \leftrightarrow X(\omega)Y(\omega), x(t)y(t) \leftrightarrow \frac{1}{2\pi}(X*Y)(\omega)$$

**Frequency Shift:**

$$e^{j\omega\_0 t}x(t) \leftrightarrow X(\omega - \omega\_0)$$

**Parsevals Theorem:**

$$\int\_{-\infty}^{\infty}{|x(t)|^2dt} = \frac{1}{2\pi}\int\_{-\infty}^{\infty}{|X(\omega)|^2d\omega}$$

### Convergence of the CTFT

A big question that arises when thinking about the Fourier Transform is whether or not the integral $$\int{x(t)e^{-j\omega t}}$$ actually converges.

{% hint style="info" %}

### Theorem 5

If $$\int\_{-\infty}^{\infty}{|x(t)|dt}$$ converges, then $$X(\omega)$$ exists and is continuous. In addition, $$X(\omega)$$ approaches 0 as $$|\omega|$$ approaches $$\infty$$.
{% endhint %}

Conceptually, this theorem makes sense because

$$|x(t)e{-j\omega t}| = |x(t)| |e^{-j\omega t}| = |x(t)|.$$

So if one converges, the other must converge. However, this means that $$x(t)=1$$, $$x(t)=\sin(\omega t)$$, $$x(t)=\cos(\omega t)$$ don’t have a "strict" Fourier Series because the integral doesn’t converge for these periodic signals. In order to get around this, we can define a "generalized" Fourier Transform which operates on periodic signals.

Starting with $$x(t)=1$$, we know that in the frequency domain, the only consituent frequency is $$\omega=0$$. This means that $$X(\omega) = k\delta(\omega)$$ where $$k$$ is some scalar. Using the Inverse Fourier Transform,

$$x(t) = \frac{1}{2\pi}\int{k\delta(\omega)e^{j\omega t}d\omega} = \frac{k}{2\pi}.$$

That means $$k = 2\pi$$, so

$$x(t) = 1 \leftrightarrow X(\omega) = 2\pi \delta(\omega).$$

Now if we apply the frequency shift property, we see that

$$x(t) = e^{j\omega\_0 t} = 2\pi \delta(\omega - \omega\_0).$$

With this, we can define our generalized Fourier Transform for periodic signals.

{% hint style="info" %}

### Definition 26

The generalized Fourier Transform for a periodic signal $$x(t)$$ is

$$X(\omega) = \sum\_{-\infty}^{\infty}{a\_k\cdot 2\pi \delta(\omega - \omega\_0)}$$

where $$a\_k$$ are the coefficients of the Fourier Series of $$x(t)$$.
{% endhint %}

This definition works because any periodic signal can be represented by its Fourier Series. The rational behind using the Dirac Delta in this generalized Fourier Transform is exlained by the Theory of Distributions which can be found in Appendix.

## Discrete Time Fourier Transform

{% hint style="info" %}

### Definition 27

The Discrete Time Fourier Transform converts aperiodic discrete signals into the frequency domain.

$$X(\omega) = \sum\_{-\infty}^{\infty}{x\[n]e^{-j\omega n}}$$
{% endhint %}

The intution for the Discrete Time Fourier Transform is more or less the same as that of the Continuous Time Fourier Transform.

{% hint style="info" %}

### Definition 28

The Inverse Discrete Time Fourier Transform converts the frequency domain representation of a signal back into its time domain representation.

$$x\[n] = \frac{1}{2\pi}\int\_{<2\pi>}{X(\omega)e^{j\omega n}d\omega}$$
{% endhint %}

### Properties of the DTFT

For all these properties, assume that $$x\[n] \leftrightarrow X(\omega)$$ and $$y\[n]\leftrightarrow (\omega)$$ **Time Shift:**

$$x\[n-n\_0] \leftrightarrow e^{-j\omega n\_0}X(\omega)$$

**Frequency Shift:**

$$X(\omega - \omega\_0) \leftrightarrow e^{j\omega\_0 n}x\[n]$$

**Time Reversal:**

$$x\[-n] \leftrightarrow X(-\omega)$$

**Conjugation:**

$$x^*\[n] = X^*(-\omega)$$

**Time Expansion:** In discrete time, compression of a signal doesn’t make sense because we can’t have partial steps (i.e n must be an integer). However, we can stretch a signal.

$$x\_M\[n] \leftrightarrow X(M\omega), x\_M\[n] = \begin{cases} x\left\[\frac{n}{M}\right] & \text{when } n \mod M = 0\ 0 & \text{else.} \end{cases}$$

**Derivative Property:**

$$nx\[n] \leftrightarrow j \frac{d}{d\omega}X(\omega)$$

**Multiplication Property:**

$$x\[n]y\[n] \leftrightarrow \frac{1}{2\pi}\int\_{2\pi}{X(\theta)Y(\omega-\theta)d\theta}$$

**Convolution Property:**

$$(x\*y)\[n] = X(\omega)Y(\omega)$$

### Convergence of the DTFT

Just like in continuous time, it was unclear whether or not the integral would converge, in discrete time, it is unclear if the infinite sum will converge. The convergence theorem for both are essentially the same.

{% hint style="info" %}

### Theorem 6

If $$\sum\_{-\infty}^{\infty}{|x\[n]|}$$ converges, then $$X(\omega)$$exists and is continuous.
{% endhint %}

Just like in continuous time, periodic signals like $$x\[n] = 1, x\[n] = sin(\omega\_0t), x\[n]=cos(\omega\_0t)...$$ are problematic because they don’t converge under the "strict" transform, so they require a generalized transform. In the frequency domain, a constant signal like $$x\[n] = 1$$ will be the sum of all frequencies. This will look like a sum of Dirac Deltas

$$X(\omega) = k \sum\_{l=-\infty}^{\infty}{\delta(\omega - 2\pi l)}.$$

Applying the synthesis equation to this, we get

$$x(t) = \frac{1}{2\pi}\int\_{2\pi}{k \sum\_{l=-\infty}^{\infty}{\delta(\omega - 2\pi l)}} = \frac{k}{2\pi}\sum\_{l=-\infty}^{\infty}{\int\_{2\pi}{\delta(\omega - 2\pi l)}} = \frac{k}{2\pi}\int\_{2\pi}{\delta(\omega - 2\pi \cdot 0)} = \frac{k}{2\pi}.$$

Therefore $$k = 2\pi$$, so

$$x\[n] = 1 \leftrightarrow X(\omega) = 2\pi\sum\_{l=-\infty}^{\infty}{\delta(\omega - 2\pi l)}$$

and we can apply the frequency shift property to get

$$x\[n] = e^{j\omega\_0n} \leftrightarrow X(\omega) = 2\pi\sum\_{l=-\infty}^{\infty}{\delta(\omega - \omega\_0 - 2\pi l)}.$$

Once again using the Fourier Series representation of $$x\[n]$$, we can define the generalized Discrete Time Fourier Transform.

{% hint style="info" %}

### Definition 29

For a perioidic signal $$x\[n]$$, the generalized Discrete Time Fourier Transform is

$$x\[n] \leftrightarrow 2\pi\sum\_{-\infty}^{\infty}{a\_k\delta\left(\omega-\frac{2\pi}{N}k\right)}$$

where $$a\_k$$ are the Fourier Series coefficients of $$x\[n]$$
{% endhint %}

## Discrete Fourier Transform

Whereas the CTFT takes a continuous signal and outputs a continuous frequency spectrum and the DTFT takes a discrete signal and outputs a continuous, periodic frequecy spectrum, the Discrete Fourier Transform takes a discrete periodic signal and outputs a discrete frequency spectrum.

{% hint style="info" %}

### Definition 30

For a length $$N$$ finite sequence $${x\[n]}^{n-1}*{0}$$, the Discrete Fourier Transform of the signal is a length N finite sequence $${X\[k]}^{n-1}*{0}$$ where

$$X\[k] = \sum\_{n=0}^{N-1}{x\[n]e^{-j\frac{2\pi}{N}kn}}.$$
{% endhint %}

One way to interpret the DFT is in terms of the Fourier series for a disrete periodic signal $$\tilde{x}\[n]=x\[n\text{ mod N}]$$. Recall that the coefficient of the kth term of the Fourier Series is

$$a\_k = \frac{1}{N}\sum\_{n=0}^{N-1}{x\[n]e^{-j\frac{2\pi}{N}kn}}.$$

Notice that the $$a\_k$$ of the Fourier Series are the DFT values except scaled by a factor of $$N$$. This gives an intuitive inverse DFT.

{% hint style="info" %}

### Definition 31

For a length N finite sequence $${X\[k]}^{N-1}*{0}$$ representing the DFT of a finite perioidc signal $${x\[n]}^{N-1}*{0}$$, the inverse DFT is given by

$$x\[n] = \frac{1}{N}\sum\_{k=0}^{N-1}{X\[k]e^{j\frac{2\pi}{N}kn}}.$$
{% endhint %}

One important property of the DFT is its complex conjugacy. When $$x\[n]$$ is a real valued signal, then $$X\[n-k]=X\[k]^\*$$. This can easily be shown by substituting $$N-k$$ into the DFT formula. Further intuition for the DFT comes from relating it to the DTFT. Suppose we have a finite signal $$x\[n]$$ which is $$0$$ for $$n < 0$$ and $$n > N-1$$. The DTFT of this signal is

$$X(\omega) = \sum\_{n=-\infty}^{\infty}{x\[n]e^{-j\omega n}} = \sum\_{n=0}^{N-1}{x\[n]e^{-j\omega n}}.$$

Suppose we sample the DTFT at intervals of $$\frac{2\pi}{N}k$$, then

$$X\[k] = X\left(\frac{2\pi}{N}k\right) = \sum\_{n=0}^{N-1}{x\[n]e^{-j\frac{2\pi}{N}k n}}.$$

Thus we can think of the DFT as a $$N$$ point sample of the DTFT.

## 2D Fourier Transforms

So far, our Fourier Transforms have been limited to signals of a single dimension. However, in the real world, signals might be multidimensional (think images). Thankfully, each of the Fourier Transforms generalizes easily into higher dimensions.\\

$$\textbf{2D CTFT: }X(\omega\_1, \omega\_2) = \int\_{-\infty}^{\infty}\int\_{-\infty}^{\infty}{x(t\_1, t\_2)e^{-j\omega\_0t}e^{-j\omega\_1t}dt\_1dt\_2}$$

$$\textbf{Inverse 2D CTFT: }x(t\_1, t\_2) = \frac{1}{(2\pi)^2}\int\_{-\infty}^{\infty}\int\_{-\infty}^{\infty}{X(\omega\_1, \omega\_2)e^{j\omega\_1t\_1}e^{j\omega\_2t\_2}d\omega\_1d\omega\_2}$$

$$\textbf{2D DTFT: }X(\omega\_1, \omega\_2) = \sum\_{n\_2=-\infty}^{\infty}\sum\_{n\_1=-\infty}^{\infty}{x\[n\_1,n\_2]e^{-j\omega\_1n\_1}e^{-j\omega\_2n\_2}}$$

$$\textbf{Inverse 2D DTFT: }x\[n\_1, n\_2] = \sum\_{\omega\_2=-\infty}^{\infty}\sum\_{\omega\_1=-\infty}^{\infty}{X(\omega\_1,\omega\_2)e^{j\omega\_1n\_1}e^{j\omega\_2n\_2}}$$

$$\textbf{2D DFT: }X\[k\_1, k\_2] = \sum\_{n\_2=0}^{N\_2-1}\sum\_{n\_1=0}^{N\_1-1}{x\[n\_1, n\_2]e^{-j\frac{2\pi}{N\_1}k\_1 n\_1}e^{-j\frac{2\pi}{N\_2}k\_2 n\_2}}$$

$$\textbf{2D DFT: }x\[n\_1, n\_2] = \sum\_{k\_2=0}^{N\_2-1}\sum\_{k\_1=0}^{N\_1-1}{X\[k\_1, k\_2]e^{j\frac{2\pi}{N\_1}k\_1 n\_1}e^{j\frac{2\pi}{N\_2}k\_2 n\_2}}$$

Just like in 1 dimension, absolute summability/integrability guarantee the convergence of these transforms. It turns out that when a 2D signal is simply a multiplication of two 1D signals, the Fourier Transforms are very easy to compute.

{% hint style="info" %}

### Theorem 7

If $$x(t\_1, t\_2) = x(t\_1)x(t\_2)$$, then $$X(\omega\_1, \omega\_2) = X(\omega\_1)X(\omega\_2)$$
{% endhint %}