This is mostly distilled from Stephen Martucci’s paper (pdf).

$\def\wsws{\small \text{WSWS}} \def\wawa{\small \text{WAWA}} \def\wswa{\small \text{WSWA}} \def\waws{\small \text{WAWS}} \def\hshs{\small \text{HSHS}} \def\haha{\small \text{HAHA}} \def\hsha{\small \text{HSHA}} \def\hahs{\small \text{HAHS}} \def\F{\mathcal{F}} \def\C{\mathcal{C}} \def\S{\mathcal{S}} \def\E{\mathcal{E}} \def\P{\mathcal{P}}$

The Discrete Fourier Transform and its inverse are linear operators that map periodic signals to periodic signals

$(\F x)[k] = \sum_{t = 0}^{m - 1} x[t] e^{-i 2 \pi k t / m} = (\F x)[k + m]$ $(\F^{-1} x)[k] = \sum_{t = 0}^{m - 1} x[t] e^{i 2 \pi k t / m} = (\F^{-1} x)[k + m] \enspace .$

Any signal with period $m$ can be defined in terms of a finite vector of length $m$ using the periodic extension operator $\P$ defined $(\P u)[t] = u[t \bmod m]$. Whereas $\F$ is the infinite transform, which maps periodic signals to periodic signals, let $F$ denote the finite transform (matrix), which maps vectors to vectors. These are related through the periodic extension operator

$\F \P = \P F \enspace .$

since $\F \P u = \P F u$ for all $u$.

## The DCT-1

Similarly to the DFT, the Discrete Trigonometric Transforms are linear operators that map real and symmetric periodic signals to real and symmetric periodic signals. If $x$ is a periodic signal $x[t] = x[t + m]$ that is real and symmetric $x[-t] = x[t]$ and has even period $m = 2 n$, then its Fourier transform

\begin{align} (\F x)[k] & = \sum_{t = 0}^{2 n - 1} x[t] e^{-i 2 \pi k t / 2 n} \\ & = x[0] + \sum_{t = 1}^{n - 1} x[t] e^{-i \pi k t / n} + x[n] (-1)^{k} + \sum_{t = 1}^{n - 1} x[2 n - t] e^{-i \pi k (2 n - t) / n} \\ & = x[0] + \sum_{t = 1}^{n - 1} x[t] \left( e^{-i \pi k t / n} + e^{i \pi k t / n} \right) + x[n] (-1)^{k} \\ & = x[0] + \sum_{t = 1}^{n - 1} 2 x[t] \cos(\pi k t / n) + (-1)^{k} x[n] \enspace . \end{align}

is also real and symmetric periodic $(\F x)[-t] = (\F x)[t]$. This is, in fact, the definition of the DCT-1. Whereas the DFT is defined for complex periodic signals, the DCT-1 is only defined for real and symmetric periodic signals.

Let $E_{\wsws}$ be a $2 n \times (n+1)$ matrix that maps an arbitrary vector to one period of a symmetric periodic signal

$E_{\wsws} = \begin{bmatrix} 1 \\ & 1 \\ & & \cdot \\ & & & 1 \\ & & & & 1 \\ & & & 1 \\ & & \cdot \\ & 1 \end{bmatrix}$

such that

$(E_{\wsws} u)[t] = \begin{cases} u[t] & \text{if } 0 \le t < n + 1 \\ u[2 n - t] & \text{if } n + 1 \le t < 2 n \end{cases}$

and let $\E_{\wsws} = \P E_{\wsws}$ be the linear operator that maps an arbitrary vector to a symmetric periodic signal. The reason for the “WSWS” subscript will become evident later on. Any symmetric periodic signal $x$ can be defined in terms of a finite vector $x = \E_{\wsws} u$. Since the DCT-1 is equal to the DFT for symmetric periodic signals, the two transforms are related

$\F \E_{\wsws} = \C_{1} \E_{\wsws} \enspace .$

### Finite Transform

If $x$ is real and symmetric periodic, then its transform $\C_{1} x$ is also real and symmetric periodic. Therefore there exist vectors $u$ and $\hat{u}$ such that $x = \E_{\wsws} u$ and $\C_{1} x = \E_{\wsws} \hat{u}$. The finite DCT-1 transform is defined as the $(n+1) \times (n+1)$ matrix $C_{1}$ that relates the unique elements of these two signals $\hat{u} = C_{1} u$. The infinite and finite DCT-1 operators are therefore related

$\C_{1} \E_{\wsws} = \E_{\wsws} C_{1} \enspace .$

The finite DCT-1 is related to the finite DFT

$F E_{\wsws} = E_{\wsws} C_{1}$

since $\F \E_{\wsws} = \F \P E_{\wsws} = \P F E_{\wsws}$ and $\C_{1} \E_{\wsws} = \E_{\wsws} C_{1} = \P E_{\wsws} C_{1}$.

To obtain an explicit expression for $C_{1}$ in terms of $F$, let $E_{\wsws}^{-1}$ denote a matrix that is the left inverse of $E_{\wsws}$ such that

$E_{\wsws}^{-1} E_{\wsws} = I \enspace .$

This is an $(n+1) \times 2 n$ matrix that extracts the unique elements from one period of a symmetric periodic signal. Using the left inverse yields

$C_{1} = E_{\wsws}^{-1} F E_{\wsws} \enspace .$

### Convolution

The relationship with the Fourier transform can be used to obtain a convolution theorem for symmetric signals. The convolution of two symmetric periodic signals is a symmetric periodic signal

$\E_{\wsws} u * \E_{\wsws} v = \E_{\wsws} w$

whose unique elements are related by the finite transform

$C_{1} w = C_{1} u \odot C_{1} v \enspace .$

#### Proof

Let $z = \E_{\wsws} u * \E_{\wsws} v$. Its Fourier transform is

$\F z = (\F \E_{\wsws} u) \odot (\F \E_{\wsws} v) = (\E_{\wsws} C_{1} u) \odot (\E_{\wsws} C_{1} v)$

using the Fourier convolution theorem and the properties of the DCT-1. Since the product of two symmetric signals is symmetric, this can be expressed

$\F z = \E_{\wsws} (C_{1} u \odot C_{1} v) \enspace .$

Since the Fourier transform of $z$ is real and symmetric, $z$ itself must be real and symmetric $z = E_{\wsws} w$, and the elements of $w$ must satisfy

\begin{align} \E_{\wsws} u * \E_{\wsws} v & = \E_{\wsws} w \\ \E_{\wsws} (C_{1} u \odot C_{1} v) & = \E_{\wsws} C_{1} w \enspace . \end{align}

q.e.d.

### Orthogonality

The finite DFT is orthogonal $F^{H} F = F F^{H} = m I$, which gives Parseval’s theorem $\|F x\|^{2} = m \|x\|^{2}$. The finite DCT-1 is not orthogonal, although it does satisfy

$\| E_{\wsws} C u \|^{2} = \| F E_{\wsws} u \|^{2} = m \| E_{\wsws} u \|^{2}$

due to the orthogonality of the Fourier transform. Substitute $D = E_{\wsws}^{T} E_{\wsws}$ with $D = (D^{\frac{1}{2}})^{2}$ diagonal and invertible to give

$\| D^{\frac{1}{2}} C D^{-\frac{1}{2}} u \|^{2} = \| E_{\wsws} C D^{-\frac{1}{2}} u \|^{2} = m \| E_{\wsws} D^{-\frac{1}{2}} u \|^{2} = m \| u \|^{2} \enspace .$

Therefore, while $C_{1}$ is not orthogonal, $\tilde{C}_{1} = D^{\frac{1}{2}} C_{1} D^{-\frac{1}{2}}$ is. This is known as the orthogonal form of the DCT-1. The diagonal matrix $D$ counts the number of times each unique element appears in the symmetric periodic extension

$D = E^{T}_{\wsws} E_{\wsws} = \begin{bmatrix} 1 \\ & 2 \\ && 2 \\ &&& \cdot \\ &&&& 2 \\ &&&&& 1 \end{bmatrix} \enspace .$

## More general symmetry

This section will introduce the DST-1, DCT-2 and DST-2 and generalise the above results.

## Even more general symmetry

There are a total of sixteen DTTs, of which only four have been discussed so far. To compute the convolution of signals that are anti-periodic, i.e. that have one symmetric and one anti-symmetric reflection, it is necessary to introduce the DCT- and DST-3 and -4. To handle signals that have mixed whole and half symmetry, and therefore odd period, it is necessary to introduce the -odd variant of every transform. For the gritty details, refer to Stephen Martucci’s paper and PhD thesis.