The Fourier Transformation

Observe that $\hat{x}(\frac{k}{N}) = \langle x, e_{\frac{k}{N}} \rangle$ with $e_{\frac{k}{N}}(n) = \frac{1}{\sqrt{N}} e^{i2\pi \frac{k}{N} n}$, for $n = 0, 1, 2, \ldots, N-1$.

Observe that $\hat{x}(f) = \langle x, e_f \rangle$ with $e_f(t) = \frac{1}{\sqrt{P}} e^{i2\pi f t}$, for $t \in [0, P]$ with $f \in \{\frac{k}{P}, k \in \mathbb{Z}\}$.

Thus, in the context of the relevant section, a Fourier series expansion is the representation of a square integrable signal in terms of a collection of a complete orthonormal harmonic signal sequence.

Intuition: The DDFT takes a finite-length discrete signal (N samples) and produces N frequency coefficients. Both the input and output are finite sequences, making this the version of the Fourier transform that computers actually compute. It decomposes a finite signal into N harmonic components equally spaced in frequency.

What each part of the does (DDFT forward):

$\hat{x}(f) = \sum_{n=0}^{N-1} \frac{1}{\sqrt{N}} x(n) \, e^{-i2\pi f n}, \quad f \in \left\{\frac{0}{N}, \frac{1}{N}, \ldots, \frac{N-1}{N}\right\}$

• $x(n)$ -- the original signal: a sequence of $N$ numbers (samples), indexed by $n = 0, 1, \ldots, N-1$
• $e^{-i2\pi f n}$ -- a complex sinusoid at frequency $f$, evaluated at discrete time $n$. By Euler's formula, $e^{-i2\pi f n} = \cos(2\pi f n) - i\sin(2\pi f n)$. This is the "detector" for frequency $f$
• $x(n) \cdot e^{-i2\pi f n}$ -- multiplying the signal by the detector at each sample. If the signal oscillates at frequency $f$, this product will tend to align (not cancel out)
• $\frac{1}{\sqrt{N}}$ -- a normalization factor that ensures the transform is unitary (energy-preserving). Some conventions put $1/N$ on the forward transform and $1$ on the inverse, but the symmetric $1/\sqrt{N}$ keeps the transform an isometry
• $\sum_{n=0}^{N-1}$ -- sum over all $N$ samples. This is the discrete analogue of integration. If frequency $f$ is present, the terms reinforce and the sum is large; if not, the terms cancel and the sum is small or zero
• $\hat{x}(f)$ -- the result: a complex number for each frequency $f$. Its magnitude $|\hat{x}(f)|$ is the amplitude of that frequency component, and its angle $\angle \hat{x}(f)$ is the phase shift

Intuition: The CDFT takes a continuous-time signal defined on a finite interval $[0,P]$ and produces a discrete (countable) set of Fourier coefficients at frequencies $k/P$. This is the classical Fourier series: a periodic continuous signal is decomposed into a countable set of harmonics. The spacing $1/P$ between frequencies is inversely proportional to the period -- longer signals yield finer frequency resolution.

What each part of the does (CDFT forward):

$\hat{x}(f) = \int_{\tau=0}^{P} \frac{1}{\sqrt{P}} x(\tau) \, e^{-i2\pi f \tau} \, d\tau, \quad f \in \left\{\frac{k}{P},\, k \in \mathbb{Z}\right\}$

• $x(\tau)$ -- the original continuous-time signal defined on the interval $[0, P]$
• $e^{-i2\pi f \tau}$ -- a complex sinusoid at frequency $f$, acting as the detector. By Euler's formula, $e^{-i2\pi f \tau} = \cos(2\pi f \tau) - i\sin(2\pi f \tau)$
• $x(\tau) \cdot e^{-i2\pi f \tau}$ -- the product of the signal with the detector. When the signal has energy at frequency $f$, this product has a non-zero average over the interval
• $\frac{1}{\sqrt{P}}$ -- normalization factor. Dividing by $\sqrt{P}$ makes the transform unitary, so energy is preserved between the time and frequency representations
• $\int_0^P d\tau$ -- integration over one full period. This is the continuous analogue of summation: it accumulates the correlation between the signal and the detector sinusoid. If frequency $f$ is present, the integral is large; if not, positive and negative contributions cancel out
• $\hat{x}(f)$ -- the Fourier coefficient at frequency $f = k/P$. Note that the output is discrete: you only get coefficients at the harmonic frequencies $0, \pm 1/P, \pm 2/P, \ldots$ The magnitude $|\hat{x}(f)|$ gives the amplitude of harmonic $k$, and the angle gives its phase

Intuition: The inverse DDFT reconstructs the original time-domain samples from their frequency coefficients. The fact that this inverse exists and perfectly recovers the signal means no information is lost when transforming to the frequency domain -- the two representations are equivalent.

What each part of the does (Inverse DDFT -- Synthesis):

$x(n) = \sum_{k=0}^{N-1} \frac{1}{\sqrt{N}} \hat{x}\!\left(\frac{k}{N}\right) e^{i2\pi \frac{k}{N} n}, \quad n \in \{0, 1, \ldots, N-1\}$

• $\hat{x}(k/N)$ -- the Fourier coefficient at frequency $k/N$. This complex number encodes the amplitude and phase of the $k$-th harmonic component. It controls how much of that frequency to add back
• $e^{i2\pi \frac{k}{N} n}$ -- a complex sinusoid at frequency $k/N$, evaluated at time $n$. Note the positive sign in the exponent (compare with $e^{-i2\pi f n}$ in the forward transform). This generates the actual oscillation at frequency $k/N$
• $\hat{x}(k/N) \cdot e^{i2\pi \frac{k}{N} n}$ -- one frequency component, weighted by its coefficient. Each term in the sum adds one sinusoidal "ingredient" back into the signal
• $\frac{1}{\sqrt{N}}$ -- the same normalization as the forward transform, ensuring unitarity
• $\sum_{k=0}^{N-1}$ -- sum over all $N$ frequency components. By adding all the weighted oscillations together, you reconstruct the original signal sample $x(n)$ exactly. This is the synthesis step: the frequency recipe is turned back into a signal

Intuition: The inverse CDFT synthesizes a continuous-time signal from its countably many Fourier coefficients. Each coefficient $\hat{x}(k/P)$ weights a complex exponential at frequency $k/P$, and the sum of all these weighted harmonics reconstructs the original signal. This is the synthesis formula of the Fourier series.

What each part of the does (Inverse CDFT -- Synthesis):

$x(t) = \sum_{k \in \mathbb{Z}} \frac{1}{\sqrt{P}} \hat{x}\!\left(\frac{k}{P}\right) e^{i2\pi \frac{k}{P} t}, \quad t \in [0, P]$

• $\hat{x}(k/P)$ -- the Fourier coefficient at frequency $k/P$. This tells you the amplitude and phase of the $k$-th harmonic. It controls how much of that frequency to include in the reconstruction
• $e^{i2\pi \frac{k}{P} t}$ -- a complex sinusoid at frequency $k/P$, now as a continuous function of time $t$. The positive sign in the exponent (vs. negative in the forward CDFT) indicates this is synthesis, not analysis
• $\hat{x}(k/P) \cdot e^{i2\pi \frac{k}{P} t}$ -- one harmonic component, weighted by its Fourier coefficient. Each term in the sum contributes one "pure tone" to the reconstructed signal
• $\frac{1}{\sqrt{P}}$ -- normalization matching the forward transform
• $\sum_{k \in \mathbb{Z}}$ -- sum over all integer harmonics $k$, from $-\infty$ to $+\infty$. Unlike the finite DDFT inverse, this sum is infinite -- you need infinitely many harmonics to perfectly reconstruct a continuous-time signal from its Fourier series. In practice, the partial sums converge in the $L_2$ sense

Intuition: Parseval's equality says that energy is conserved when you transform between time and frequency domains. The total energy of a signal, computed by summing/integrating its squared amplitude over time, equals the total energy computed from its frequency coefficients. This is why the Fourier transform is called a "unitary" or "isometric" transformation -- it preserves distances and energies.

Time-shift, periodicity and differentiation will also be discussed. An important property is with regard to convolution. Suppose that in the following, we write $f(t) = f(t \mod P)$, in which case the convolution operation is also termed cyclical convolution.

Intuition: The convolution theorem is one of the most practically important results in signal processing. Computing a convolution directly requires integrating a product over all time shifts, but in the frequency domain it reduces to simple pointwise multiplication. This is why filtering is often done by transforming to the frequency domain, multiplying, and transforming back -- especially with the FFT, this is far more efficient.

The FFT algorithm achieves a dramatic speedup: for $N = 1024$, the naive DFT requires about $10^6$ operations, while the FFT requires only about $10^4$. This makes real-time signal processing practical.

The DCFT maps a discrete-time signal to a continuous function of frequency. The output $\hat{x}(f)$ is periodic with period 1. This transform is the workhorse of discrete-time signal processing -- it takes a sequence of numbers and produces a continuous frequency spectrum.

What each part of the does (DCFT forward):

$\hat{x}(f) = \sum_{n \in \mathbb{Z}} x(n) \, e^{-i2\pi f n}, \quad f \in [0, 1)$

• $x(n)$ -- the original discrete-time signal: an infinite sequence of numbers indexed by all integers $n \in \mathbb{Z}$
• $e^{-i2\pi f n}$ -- a complex sinusoid at frequency $f$, evaluated at discrete time $n$. By Euler's formula, $e^{-i2\pi f n} = \cos(2\pi f n) - i\sin(2\pi f n)$. This is the frequency detector, just as in the other transforms
• $x(n) \cdot e^{-i2\pi f n}$ -- the product of the signal sample with the detector at that sample. If $x$ oscillates at frequency $f$, these products reinforce rather than cancel
• $\sum_{n \in \mathbb{Z}}$ -- sum over all integer time indices, from $-\infty$ to $+\infty$. This replaces integration (since the signal is discrete) and replaces the finite sum of the DDFT (since the signal is now infinite-length)
• $\hat{x}(f)$ -- the result is a continuous function of frequency $f \in [0,1)$, and it is periodic with period 1. The output lives on a continuous interval because the input is an infinite-length sequence -- more input data yields a denser (continuous) frequency representation. The magnitude $|\hat{x}(f)|$ gives the spectral amplitude at frequency $f$, and the angle gives the phase

Note that there is no explicit $1/\sqrt{P}$ normalization here because the convention uses $P = 1$ and the normalization is absorbed into the inverse transform's integration.

What each part of the does (DCFT inverse -- Synthesis):

$x(n) = \int_0^1 \hat{x}(f) \, e^{i2\pi f n} \, df, \quad n \in \mathbb{Z}$

• $\hat{x}(f)$ -- the continuous frequency spectrum. For each frequency $f$, this complex-valued function tells you the amplitude and phase of that component
• $e^{i2\pi f n}$ -- a complex sinusoid at frequency $f$, evaluated at discrete time $n$. The positive sign (vs. negative in the forward transform) signals that this is synthesis
• $\hat{x}(f) \cdot e^{i2\pi f n}$ -- one infinitesimal frequency component, weighted by the spectrum. Each value of $f$ contributes a tiny sinusoidal piece to the reconstructed signal
• $\int_0^1 df$ -- integration over all frequencies in one period $[0,1)$. Since the spectrum is continuous, reconstruction requires integrating (not summing) over all frequency components. This integral adds up a continuum of weighted oscillations to recover $x(n)$
• $x(n)$ -- the reconstructed signal sample at time $n$, perfectly recovered from the continuous spectrum

Intuition: The CCFT is the "fully continuous" Fourier transform: it maps a continuous-time signal defined on all of $\mathbb{R}$ to a continuous frequency spectrum on all of $\mathbb{R}$. Unlike the Fourier series (which produces discrete frequencies), the CCFT produces a continuous frequency density. This is the appropriate transform for non-periodic signals of finite energy, and it is the transform most commonly meant when engineers simply say "the Fourier transform."

What each part of the does (CCFT forward):

$\hat{x}(f) = \int_{\tau=-\infty}^{\infty} x(t) \, e^{-i2\pi f t} \, dt, \quad f \in \mathbb{R}$

• $x(t)$ -- the original signal in continuous time, defined for all $t \in \mathbb{R}$
• $e^{-i2\pi ft}$ -- a complex sinusoid at frequency $f$ (the "detector"). By Euler's formula, this equals $\cos(2\pi ft) - i\sin(2\pi ft)$. It probes the signal for content at frequency $f$
• $x(t) \cdot e^{-i2\pi ft}$ -- multiplying the signal by the detector. If the signal contains frequency $f$, this product will have a steady (non-cancelling) component
• $\int_{-\infty}^{\infty} dt$ -- integrating (summing up) over all time. If frequency $f$ is present, the integral is large; if not, positive and negative parts cancel and the integral is small or zero
• $\hat{x}(f)$ -- the result: a complex number for each frequency $f \in \mathbb{R}$, forming a continuous spectrum. The magnitude $|\hat{x}(f)|$ tells you the amplitude at frequency $f$, and the angle $\angle \hat{x}(f)$ tells you the phase shift of that component

This is the "fully continuous" version: continuous time in, continuous frequency out. Both the signal and its transform live on $\mathbb{R}$, and neither is assumed periodic.

What each part of the does (CCFT inverse -- Synthesis):

$x(t) = \int_{f=-\infty}^{\infty} \hat{x}(f) \, e^{i2\pi f t} \, df, \quad t \in \mathbb{R}$

• $\hat{x}(f)$ -- the continuous frequency spectrum (the "frequency recipe"). For each frequency $f$, this complex number encodes the amplitude and phase of that component
• $e^{i2\pi ft}$ -- a complex sinusoid at frequency $f$. Note the positive sign in the exponent (vs. $e^{-i2\pi ft}$ in the forward transform). This generates the actual oscillation at frequency $f$
• $\hat{x}(f) \cdot e^{i2\pi ft}$ -- one infinitesimal frequency component, weighted by the spectrum. The coefficient $\hat{x}(f)$ controls how much of frequency $f$ to add back
• $\int_{-\infty}^{\infty} df$ -- integrating over all frequencies. Since the spectrum is continuous, we sum a continuum of weighted oscillations. Each infinitesimal frequency band $[f, f+df]$ contributes $\hat{x}(f) e^{i2\pi ft} df$ to the total signal
• $x(t)$ -- the reconstructed signal at time $t$, perfectly recovered by summing all frequency contributions

The synthesis integral assembles the original signal from its frequency ingredients, just as the forward transform decomposed it. The two operations are perfect inverses of each other.

Theorem is one of the most powerful properties of the Fourier transform. Part (a) says that differentiation in time corresponds to multiplication by $i2\pi f$ in frequency. Part (b) says that multiplication by $t$ in time corresponds to differentiation in frequency (up to a constant). These properties are what make the Fourier transform so useful for solving differential equations.

Intuition: Schwartz functions are "maximally well-behaved" signals -- they are infinitely smooth and decay faster than any polynomial. This theorem says the Fourier transform preserves this niceness: transforming a Schwartz function gives another Schwartz function. This makes the Schwartz space a natural starting point for Fourier analysis, from which results can then be extended to larger spaces like $L_2$.

Intuition: The Riemann-Lebesgue lemma says that the Fourier transform of any integrable signal decays to zero at extreme frequencies. Physically, this means an $L_1$ signal cannot have unbounded high-frequency content -- eventually, the frequency components must die out. This is a fundamental regularity property of the Fourier transform.

Intuition: This lemma shows that the "sinc-like" function $\frac{\sin(nx)}{\pi x}$ behaves like a Dirac delta as $n$ grows large -- it concentrates all its mass at the origin and "picks out" the value $\phi(0)$. This is the key technical fact that makes the Fourier inversion formula work: the integral of the inverse transform converges to the original signal value.

When $h = g$, Plancherel's identity reduces to Parseval's theorem: $\|\hat{h}\|^2 = \|h\|^2$. This says that the Fourier transform preserves energy -- the total energy of a signal computed in the time domain equals the total energy computed in the frequency domain. In engineering terms, the Fourier transform is an isometry (distance-preserving map).

Intuition: This density result is what allows us to extend the Fourier transform from Schwartz functions (where everything converges nicely) to all of $L_2(\mathbb{R})$. Since every $L_2$ signal can be approximated by Schwartz functions, we can define its Fourier transform as the limit of the transforms of the approximating Schwartz functions.

Intuition: This theorem is the general machine for extending operators from a dense subspace to the entire space. If a linear map is bounded (continuous) on a dense subset of a normed space, it can be uniquely extended to the whole space without increasing its norm. This is precisely how the CCFT is extended from the Schwartz space to all of $L_2$ -- the Fourier transform is bounded on $\mathcal{S}$ (by Parseval), so it extends uniquely and continuously to $L_2$.