Difference between revisions of "DiscreteCos"
Jump to navigation
Jump to search
m (Text replacement - "\$([^\$]+)\$" to "\\(\1\\)") |
|||
| Line 1: | Line 1: | ||
[[DiscreteCos]] is [[linear operator]] that provides the orthogonal transformation of an array of finite length in a way, that have some analogies with the integral [[CosFourier]] transform |
[[DiscreteCos]] is [[linear operator]] that provides the orthogonal transformation of an array of finite length in a way, that have some analogies with the integral [[CosFourier]] transform |
||
| − | : |
+ | :\( \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!(1) ~ ~ ~ \displaystyle \mathrm{CosFourier}(F)(x) ~=~ \sqrt{\frac{2}{\pi}}~ \int_0^\infty \! \cos(xy) ~F(y)~ \mathrm d y\) |
There are many kinds of the DiscreteCos transform, and many corresponding algorithms are implemented. Usually, they are poorly documented, and from the description of a DiscreteCos, it is difficult to guess, where to load the code, which formula is implemented and how is it related with other kinds of DiscreteCos. In order to make from the Discrete Cos the useful Tool of Research and Investigation, the formulas, their descriptions and the C++ implementations are collected here. |
There are many kinds of the DiscreteCos transform, and many corresponding algorithms are implemented. Usually, they are poorly documented, and from the description of a DiscreteCos, it is difficult to guess, where to load the code, which formula is implemented and how is it related with other kinds of DiscreteCos. In order to make from the Discrete Cos the useful Tool of Research and Investigation, the formulas, their descriptions and the C++ implementations are collected here. |
||
| Line 12: | Line 12: | ||
W.H.Press, B.P.Flannery, S.A.Teukolsky, W.T.Vetterling. Numerical Recipes in C. Fast Sine and Cosine transform. </ref>. |
W.H.Press, B.P.Flannery, S.A.Teukolsky, W.T.Vetterling. Numerical Recipes in C. Fast Sine and Cosine transform. </ref>. |
||
| − | DCTI, or Discrete Cos Transform of kind I, is orthogonal transform, that repalces an array |
+ | DCTI, or Discrete Cos Transform of kind I, is orthogonal transform, that repalces an array \(F\) of length \(N+1\) with elements \(F_n\), \(n-0 .. N\) to the array \(G\) with elements |
| − | : |
+ | : \( \!\!\!\!\!\!\!\!\!\!(2) ~ ~ ~ \displaystyle G_k = (\mathrm{DCTI}_N F)_k = \frac{1}{2} F_0 + \frac{(-1)^k}{2} F_{N} + \sum_{n=1}^{N-1} F_n \cos\! \left(\frac{\pi}{N} n k \right)~\) for \(~k=0, .. N\) |
| − | The orthonormaized transform can be defined with operator |
+ | The orthonormaized transform can be defined with operator \(ふ_{\mathrm C1,N}\), that acts on array \(F\) in the following way: |
| − | : |
+ | : \( \!\!\!\!\!\!\!\!\!\!(3) ~ ~ ~ ~ \displaystyle |
(ふ_{\mathrm C1,N}~ F)_k= |
(ふ_{\mathrm C1,N}~ F)_k= |
||
\sqrt{\frac{2}{N}} ~(\mathrm{DCT1}_N~ F)_k= |
\sqrt{\frac{2}{N}} ~(\mathrm{DCT1}_N~ F)_k= |
||
\sqrt{\frac{2}{N}} \left( \frac{1}{2} F_0 + \frac{(-1)^k}{2} F_{N} |
\sqrt{\frac{2}{N}} \left( \frac{1}{2} F_0 + \frac{(-1)^k}{2} F_{N} |
||
| − | + \sum_{n=1}^{N-1} F_n \cos \left(\frac{\pi}{N} n k \right)\right) |
+ | + \sum_{n=1}^{N-1} F_n \cos \left(\frac{\pi}{N} n k \right)\right)\) |
See the special article [[DCTI]] for the numerical implementation and the applications. |
See the special article [[DCTI]] for the numerical implementation and the applications. |
||
==DCTII== |
==DCTII== |
||
| − | : |
+ | :\( \!\!\!\!\!\!\!\!\!\!\!\!\!\! (4) ~ ~ ~ ~ \displaystyle |
(\mathrm{DCTII}_N ~F) |
(\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 = \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\) |
| − | For the simple and efficient implementation, |
+ | 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. For the properties and the numerical implementation and the example, see the special article [[DCTII]]. |
==DCTIII== |
==DCTIII== |
||
| − | : |
+ | :\( \!\!\!\!\!\!\!\!\!\!\!\!\!\! (5) ~ ~ ~ ~ \displaystyle |
(\mathrm{DCTIII}_N ~F) |
(\mathrm{DCTIII}_N ~F) |
||
| − | _k = \sum_{n=0}^{N-1} ~ F_n~ \cos \left(\frac{\pi}{N} n \left(k\!+\!\frac{1}{2}\right) \right) ~ ~ ~ |
+ | _k = \sum_{n=0}^{N-1} ~ F_n~ \cos \left(\frac{\pi}{N} n \left(k\!+\!\frac{1}{2}\right) \right) ~ ~ ~\), \(~ ~ ~ k = 0, \dots, N\!-\!1\) |
| − | For the simple and efficient implementation, |
+ | For the simple and efficient implementation, \(N=2^q\) for some natural number \(q\). For the properties and the numerical implementation and the example, see the special article [[DCTII|DCTII]]. |
==Relation between DCTII and DCTIII== |
==Relation between DCTII and DCTIII== |
||
Latest revision as of 18:26, 30 July 2019
DiscreteCos is linear operator that provides the orthogonal transformation of an array of finite length in a way, that have some analogies with the integral CosFourier transform
- \( \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!(1) ~ ~ ~ \displaystyle \mathrm{CosFourier}(F)(x) ~=~ \sqrt{\frac{2}{\pi}}~ \int_0^\infty \! \cos(xy) ~F(y)~ \mathrm d y\)
There are many kinds of the DiscreteCos transform, and many corresponding algorithms are implemented. Usually, they are poorly documented, and from the description of a DiscreteCos, it is difficult to guess, where to load the code, which formula is implemented and how is it related with other kinds of DiscreteCos. In order to make from the Discrete Cos the useful Tool of Research and Investigation, the formulas, their descriptions and the C++ implementations are collected here.
DCTI
DCTI is one of realizations of the DiscreteCos operator. The name is chosen in analogy with DCT by Wikipedia [1] and notations by the Numerical recipes in C [2].
DCTI, or Discrete Cos Transform of kind I, is orthogonal transform, that repalces an array \(F\) of length \(N+1\) with elements \(F_n\), \(n-0 .. N\) to the array \(G\) with elements
- \( \!\!\!\!\!\!\!\!\!\!(2) ~ ~ ~ \displaystyle G_k = (\mathrm{DCTI}_N F)_k = \frac{1}{2} F_0 + \frac{(-1)^k}{2} F_{N} + \sum_{n=1}^{N-1} F_n \cos\! \left(\frac{\pi}{N} n k \right)~\) for \(~k=0, .. N\)
The orthonormaized transform can be defined with operator \(ふ_{\mathrm C1,N}\), that acts on array \(F\) in the following way:
- \( \!\!\!\!\!\!\!\!\!\!(3) ~ ~ ~ ~ \displaystyle (ふ_{\mathrm C1,N}~ F)_k= \sqrt{\frac{2}{N}} ~(\mathrm{DCT1}_N~ F)_k= \sqrt{\frac{2}{N}} \left( \frac{1}{2} F_0 + \frac{(-1)^k}{2} F_{N} + \sum_{n=1}^{N-1} F_n \cos \left(\frac{\pi}{N} n k \right)\right)\)
See the special article DCTI for the numerical implementation and the applications.
DCTII
- \( \!\!\!\!\!\!\!\!\!\!\!\!\!\! (4) ~ ~ ~ ~ \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\)
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. For the properties and the numerical implementation and the example, see the special article DCTII.
DCTIII
- \( \!\!\!\!\!\!\!\!\!\!\!\!\!\! (5) ~ ~ ~ ~ \displaystyle (\mathrm{DCTIII}_N ~F) _k = \sum_{n=0}^{N-1} ~ F_n~ \cos \left(\frac{\pi}{N} n \left(k\!+\!\frac{1}{2}\right) \right) ~ ~ ~\), \(~ ~ ~ k = 0, \dots, N\!-\!1\)
For the simple and efficient implementation, \(N=2^q\) for some natural number \(q\). For the properties and the numerical implementation and the example, see the special article DCTII.
Relation between DCTII and DCTIII
References
- ↑ http://en.wikipedia.org/wiki/Discrete_cosine_transform
- ↑ http://88.167.97.19/albums/files/TMTisFree/Documents/Physics/11%20-%20Fourier%20Transform%20Spectral%20Methods.pdf W.H.Press, B.P.Flannery, S.A.Teukolsky, W.T.Vetterling. Numerical Recipes in C. Fast Sine and Cosine transform.