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,