Discrete cosine transform

We consider a shifted discrete Fourier transform of \(2 N\) real numbers:

\[ \begin{align}\begin{aligned}X_k & = \sum_{n = 0}^{2 N - 1} x_n \twiddle{- 2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N}\\& = \sum_{n = 0}^{N - 1} x_n \twiddle{- 2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N} + \sum_{n = N}^{2 N - 1} x_n \twiddle{- 2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N}\end{aligned}\end{align} \]

for \(\seq{k}{0}{1}{2 N - 1}\), and the corresponding inverse transform:

\[ \begin{align}\begin{aligned}x_n & = \frac{1}{2 N} \sum_{k = 0}^{2 N - 1} X_k \twiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N}\\& = \frac{1}{2 N} \sum_{k = 0}^{N - 1} X_k \twiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N} + \frac{1}{2 N} \sum_{k = N}^{2 N - 1} X_k \twiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N}\end{aligned}\end{align} \]

for \(\seq{n}{0}{1}{2 N - 1}\). Although \(x_n\) can be arbitrary, here we request the signal to satisfy

\[x_{2 N - 1 - n} = x_n\]

for \(\seq{n}{0}{1}{2 N - 1}\). Due to

\[\sum_{n = N}^{2 N - 1} x_n \twiddle{- 2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N} = \sum_{n = 0}^{N - 1} x_n \twiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N},\]

Derivation

With \(m = 2 N - 1 - n\), we have

\[ \begin{align}\begin{aligned}\sum_{m = N - 1}^{0} x_{2 N - 1 - m} \twiddle{- 2 \pi}{\left( 2 N - 1 - m + \frac{1}{2} \right) k}{2 N} & = \sum_{n = 0}^{N - 1} x_n \exp \left( - 2 \pi k I \right) \twiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N}\\& = \sum_{n = 0}^{N - 1} x_n \twiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N}.\end{aligned}\end{align} \]

we obtain

\[ \begin{align}\begin{aligned}X_k & = \sum_{n = 0}^{N - 1} x_n \twiddle{- 2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N} + \sum_{n = 0}^{N - 1} x_n \twiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N}\\& = 2 \sum_{n = 0}^{N - 1} x_n \ctwiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N}.\end{aligned}\end{align} \]

It is readily apparent that \(X_k \in \mathbb{R}\). Note that

\[X_{2 N - k} = - X_k,\]

Derivation

\[ \begin{align}\begin{aligned}X_{2 N - k} & = 2 \sum_{n = 0}^{N - 1} x_n \ctwiddle{2 \pi}{\left( n + \frac{1}{2} \right) \left( 2 N - k \right)}{2 N}\\& = 2 \sum_{n = 0}^{N - 1} x_n \cos \left( \pi \left( 2 n + 1 \right) - 2 \pi \frac{\left( n + \frac{1}{2} \right) k}{2 N} \right)\\& = - 2 \sum_{n = 0}^{N - 1} x_n \ctwiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N}\\& = - X_k.\end{aligned}\end{align} \]

and thus it is sufficient to consider \(\seq{k}{0}{1}{N - 1}\). Also by utilizing this relation, we find

\[\sum_{k = N}^{2 N - 1} X_k \twiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N} = \sum_{k = 1}^{N - 1} X_k \twiddle{- 2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N},\]

Derivation

Assigning \(k \leftarrow 2 N - k\) to the relation of the discrete cosine transform (type II) yields

\[ \begin{align}\begin{aligned}\sum_{k = N}^{2 N - 1} X_k \twiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N} & = - \sum_{k = N}^{2 N - 1} X_{2 N - k} \twiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N}\\& = - \sum_{l = N}^{1} X_l \twiddle{2 \pi}{\left( n + \frac{1}{2} \right) \left( 2 N - l \right)}{2 N} \,\, \left( l \equiv 2 N - k \right)\\& = - \sum_{k = 1}^{N} X_k \exp \left\{ \pi \left( 2 n + 1 \right) I \right\} \twiddle{- 2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N}\\& = \sum_{k = 1}^{N} X_k \twiddle{- 2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N} \,\, \left( \because \exp \left\{ \pi \left( 2 n + 1 \right) I \right\} = -1 \right)\\& = \sum_{k = 1}^{N - 1} X_k \twiddle{- 2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N} \,\, \left( \because X_N = 0 \right).\end{aligned}\end{align} \]

from which the inverse transform leads to

\[ \begin{align}\begin{aligned}x_n & = \frac{1}{2 N} \sum_{k = 0}^{N - 1} X_k \twiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N} + \frac{1}{2 N} \sum_{k = 1}^{N - 1} X_k \twiddle{- 2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N}\\& = \frac{1}{N} \left\{ \frac{X_0}{2} + \sum_{k = 1}^{N - 1} X_k \ctwiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N} \right\}.\end{aligned}\end{align} \]

To summarize, the discrete cosine transform of type II and type III are defined as

\[X_k \equiv 2 \sum_{n = 0}^{N - 1} x_n \ctwiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N}\]

for \(\seq{k}{0}{1}{N - 1}\), and

\[x_n \equiv \frac{1}{N} \left\{ \frac{X_0}{2} + \sum_{k = 1}^{N - 1} X_k \ctwiddle{2 \pi}{\left( n + \frac{1}{2} \right) k}{2 N} \right\}\]

for \(\seq{n}{0}{1}{N - 1}\), respectively. Note that both transforms are \(\mathbb{R}^N \rightarrow \mathbb{R}^N\).