DCTII

DCTII is one of realizations of the DCT transform operator (Discrete Cosine transform); it is one of many discrete analogies of the integral operator CosFourier.

For a given natural number \(N\), operator \(\mathrm{DCTII}_N\) converts any array \(F\) of length \(N\) to the array with elements

\( \!\!\!\!\!\!\!\!\!\!\!\!\!\! (1) ~ ~ ~ ~ \displaystyle (\mathrm{DCTII}_N ~F) _k = \sum_{n=0}^{N-1} ~ F_n~ \cos \left(\frac{\pi}{N} \left(n\!+\!\frac{1}{2}\right) k \right) ~ ~ ~\), \(~ ~ ~ k = 0, \dots, N\!-\!1\)

As in the case of other discrete Fourier transforms, the numeration of elements begins with zero. For the simple and efficient implementation, \(N=2^q\) for some natural number \(q\). Note that the size of the arrays is for unity smaller than in the case of DCTI.

Numerical implementation and example

Numerilal implementation of the transform DCTII consists of 3 files: zfour1.cin, zrealft.cin, zcosft2.cin.

The example of the C++ call below calculates the expansion of function \(F(x)=\cos(x)+.1*\cos(3x)+.01*\cos(5x)\) represented at the array with \(x_n=d n\) for \(d=\pi/(2N)\) ; this corresponds to superopsition of three symmetric modes of a cavity of width \(\pi\) with boundary condition \(F(\pi/2)=0\). In the example, \(N=8\).

#include<math.h> 
#include<stdio.h>
#include <stdlib.h>
using namespace std;
#include <complex>
#define z_type double
#include"zfour1.cin"
#include"zrealft.cin"
#include"zcosft2.cin"
main(){ z_type *a, *b, *c; int j; unsigned long N=8;
a=(z_type *) malloc((size_t)((N)*sizeof(z_type)));
b=(z_type *) malloc((size_t)((N)*sizeof(z_type)));
c=(z_type *) malloc((size_t)((N)*sizeof(z_type)));
for(j=0;j<N;j++) a[j]=b[j]=cos( M_PI/N*.5*j);
zcosft2(a-1,N,-1);
for(j=0;j<N;j++) c[j]=a[j];
zcosft2(a-1,N,1);
for(j=0;j<N;j++) printf("%12.9f %12.9f %12.9f\n",b[j], c[j], a[j]);
free(a);
free(b);
free(c);
}

The example generates the following output:

 0.19634954  1.11000000  4.00000000  4.44000000
 0.58904862  1.06948794  0.40000000  4.27795178
 0.98174770  0.95832104  0.04000000  3.83328417
 1.37444679  0.80215273  0.00000000  3.20861091
 1.76714587  0.62932504  0.00000000  2.51730014
 2.15984495  0.45944261 -0.00000000  1.83777043
 2.55254403  0.29953427  0.00000000  1.19813710
 2.94524311  0.14784799  0.00000000  0.59139198

The 0th column repressents the initial values of coordinate \(x=\frac{\pi}{16}, \frac{3\pi}{16}, \frac{5\pi}{16} , \frac{7\pi}{16} , \frac{9\pi}{16} , \frac{11\pi}{16}, \frac{13\pi}{16}, \frac{15\pi}{16}\)

The 1st column shows values \(F_n=F(x_n)\)

The 2d column shows the \((\mathrm{DTCII}_8~ F)_n\)

The 3d (last) column shows array \((\mathrm{DTCIII}_8 ~ \mathrm{DTCII}_8~ F)\), which coincides with the initial array \(F\) multiplied with factor 4; it confirms that the transform DTCIII can be used to invert DTCII.

Approximation of CosFourier

Let \(F\) be smooth even function quickly decaying at infinity; let \(N\) be large natural number.

Let \(d=\sqrt{\pi/N}\);

Let \(y_n=\left(\frac{1}{2}+n\right)d~\) for integer values \(n\), and
Let \(x_n= n d~\).

Then, in the definition of the CosFourier transform, the integral can be replaced with sum, giving

\( \!\!\!\!\!\!\!\!\!\!\!\!\!\! (2) ~ ~ ~ ~ \displaystyle (\mathrm{CosFourier}~ F) (x) = \sqrt{\frac{2}{\pi}} \int_0^\infty ~ \cos(x_k y)~ F(y) ~\mathrm d y \approx \sqrt{\frac{2}{\pi}}~ \sum_{n=0}^{N-1} ~ \cos(x y_n)~ F(y_n) ~\sqrt{\pi/N}\) \(\displaystyle = \sqrt{\frac{2}{N}} ~ \sum_{n=0}^{N-1} \cos\left( \sqrt{\frac{\pi}{N}} x \left(\frac{1}{2}\!+\! n\right) \right) F_n\)

where \(F_n=F(y_n)\).

For \(x=x_k\), the CosFourier transform of \(F\) evaluated at \(x\) can be approximated as follows:

\( \!\!\!\!\!\!\!\!\!\!\!\!\!\! (3) ~ ~ ~ ~ \displaystyle (\mathrm{CosFourier}~ F) (x_k) \approx \sqrt{\frac{2}{N}}~ \sum_{n=0}^{N-1} ~ \cos\left( \frac{\pi}{N} k \left(\frac{1}{2}\!+\! n\right) \right) F_n = \sqrt{\frac{2}{N}}~ (\mathrm{DCTII}_N~F)_k \)

Note that DCTII\(_N\) approximation of CosFourier transform at points, displaced for half–step with respect to those at which the function \(F\) is evaluated. This may be considered as explanation why the second iteration of operation DCTII\(_N\) does not give a factor of the Identity transform.

Relation with other DCF

Inverse of DCTII can be easy expressed through DCTIII and vice versa:

\( \displaystyle (\mathrm {DCTII}_N ~ \mathrm {DCTIII}_N ~F)_n= (\mathrm {DCTIII}_N ~ \mathrm {DCTII}_N ~F)_n= \frac{N}{2} F_n\)

Keywords

CosFourier, Fourier, DCT, DCTI, DCTII, DCTIII,