# DCTII

Jump to: navigation, search

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$$