The Discrete Fourier Transform: Useful maths

A handful of mathematical tools are particularly useful in understanding the structure and use of the Discrete Fourier Transform (DFT), and signal processing in general. Several of them are gathered together here on a single page.

The other pages within the signals and signal processing section use this page as essential background.

Inner product

Inner product in real space

In regular 3D real space, the inner product $q$ (equivalent to the dot product), between two vectors $\underline{a}$ and $\underline{b}$ can be thought of as multiplying the lengths of the two vectors together with the cosine of the angle between them

(1) $\begin{align*} q = \langle \underline{a}, \underline{b} \rangle = \underline{a}\cdot\underline{b} = |{a}| |b| \cos{(\theta)} \end{align*}$

where $|{a}|$ means the Euclidian length of $\underline{a}$ .

The result, a scalar number $q$ , will be 0 if the vectors are orthogonal, and nonzero otherwise. In slightly woolly language, it tells us something about how much $\underline{a}$ `overlaps’ $\underline{b}$ , and vice versa (since $\langle \underline{a}, \underline{b} \rangle = \langle \underline{b}, \underline{a} \rangle$ ).

If we take the inner product of the vector $\underline{a}$ with itself, we obtain

(2) $\begin{align*} \langle \underline{a}, \underline{a} \rangle = \underline{a}\cdot\underline{a} = |{a}| |{a}| \cos{(0)} = |a|^2 \end{align*}$

from which it is easy to see that the strict `length’ of overlap of $\underline{a}$ with itself, i.e., its effective length regardess of direction, is given by

(3) $\begin{align*} \sqrt{\langle \underline{a}, \underline{a} \rangle} = |a| \end{align*}$

Inner product for discrete time signals (N-length, complex valued)

Consider a pair of $N$ -length complex valued discrete signals, say $u=u[n]$ and $v=v[n]$ , specified at integer sample time indices $n$ . Each signal comprises $N$ samples, and therefore runs from $n = 0, 1, 2, \cdots, N-1$ . The signals $u, v$ can be viewed as a pair of $N$ -dimensional vectors in $\mathbb{C}_N$ space.

The inner product between $u$ and $v$ , which we’ll call $q$ , is written as

(4) $\begin{align*} q = \langle u, v \rangle = \sum_{n=0}^{N-1} u[n] v^{\ast}[n] \end{align*}$

where $^{\ast}$ denotes the complex conjugate. As with the real space dot product, the extension to $u, v \in \mathbb{C}_N$ renders a (complex valued) scalar $q$ that tells us about the `amount of overlap’ between the signals.

If we take the inner product of the signal $u$ with itself, we obtain

(5) $\begin{align*} \langle u, u \rangle &= \sum_{n=0}^{N-1} u[n] u^{\ast}[n] = \sum_{n=0}^{N-1} |u[n]|^{2} \\ &= \|{u}\|^2 \end{align*}$

The quantity $\|{u}\|^2$ is referred to as the total energy of the signal. It’s also sometimes called the `squared L2-norm’. Notice the conceptual similarity with the real space example in equation 2 above.

Length and the L2-norm (Euclidian norm) for discrete signals

Analogous with the real space example of equation 3, an $N$ -length complex valued discrete signal, $u[n]$ , can be thought of as having an $N$ -dimensional `length’. This is usually defined in terms of the L2-norm (aka Euclidian norm), $\|{u}\|$ , as

(6) $\begin{align*} \|{u}\| &= \sqrt{\langle u, u \rangle} = \sqrt{\sum_{n=0}^{N-1} |u[n]|^{2}} \\ &= \sqrt{\|{u}\|^2} \end{align*}$

using the definition in equation 5. Sometimes $\|{u}\|$ is written as $\|{u}\|_{2}$ , to be explicit, but in general where $\|{u}\|$ is written we assume reference to the L2-norm.

Elsewhere (such as here, and here) we will see how useful it is to have strict definitions of `energy’ and `length’ when it comes to comparing real-world signals expressed in the discrete time vs. discrete frequency domains.