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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N<math>, operator <math>\mathrm{DCTII}_N} converts any array Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} of length Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} to the array with elements

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\!\!\!\!\!\!\!\!\!\!\!\!\! (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) ~ ~ ~} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ~ ~ ~ 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, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N=2^q} for some natural number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(x)=\cos(x)+.1*\cos(3x)+.01*\cos(5x)} represented at the array with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_n=d n} for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d=\pi/(2N)}  ; this corresponds to superopsition of three symmetric modes of a cavity of width Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi} with boundary condition Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(\pi/2)=0} . In the example, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_n=F(x_n)}

The 2d column shows the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathrm{DTCII}_8~ F)_n}

The 3d (last) column shows array Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathrm{DTCIII}_8 ~ \mathrm{DTCII}_8~ F)} , which coincides with the initial array Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} multiplied with factor 4; it confirms that the transform DTCIII can be used to invert DTCII.

Approximation of CosFourier

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} be smooth even function quickly decaying at infinity; let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} be large natural number.

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d=\sqrt{\pi/N}} ;

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_n=\left(\frac{1}{2}+n\right)d~} for integer values Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , and
Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_n= n d~} .

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\!\!\!\!\!\!\!\!\!\!\!\!\! (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}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_n=F(y_n)} .

For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=x_k} , the CosFourier transform of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} evaluated at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} can be approximated as follows:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\!\!\!\!\!\!\!\!\!\!\!\!\! (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 DCTIIFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle _N} approximation of CosFourier transform at points, displaced for half–step with respect to those at which the function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is evaluated. This may be considered as explanation why the second iteration of operation DCTIIFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle _N} does not give a factor of the Identity transform.

Note, that mode points for the initial function and those for the transform do not coincide, as it takes place in the case of DCTI.

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:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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