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 $\displaystyle (\mathrm {CosFourier} ~F)(x)={\sqrt {\frac {2}{\pi }}}\int _{0}^{\infty }\cos(xy)~F(y)\mathrm {d} y$

The name DCTII is chosen in analogy with the Wikipedia article and notations by the Numerical recipes in C .

Explicit definition of DCTII

For a given natural number $N<math>,operator<math>\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}=dn$ 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 chosen values of coordinate $x_{0}={\frac {\pi }{16}},~x_{1}={\frac {3\pi }{16}},~x_{2}={\frac {5\pi }{16}},~x_{3}={\frac {7\pi }{16}},~x_{4}={\frac {9\pi }{16}},~x_{5}={\frac {11\pi }{16}},~x_{6}={\frac {13\pi }{16}},~x_{7}={\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}=nd~$.

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(xy_{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 (Which is another discrete approximation of the CosFourier operator) 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}$

References

The content of this article is adopted from http://tori.ils.uec.ac.jp/TORI/index.php/DCTII