Editing Discrete cosine transform (section)

===== Arithmetic complexity =====
The whole 3-D DCT calculation needs <math>~ [\log_2 N] ~</math> stages, and each stage involves <math>~ \tfrac{1}{8}\ N^3 ~</math> butterflies. The whole 3-D DCT requires <math>~ \left[ \tfrac{1}{8}\ N^3 \log_2 N \right] ~</math> butterflies to be computed. Each butterfly requires seven real multiplications (including trivial multiplications) and 24&nbsp;real additions (including trivial additions). Therefore, the total number of real multiplications needed for this stage is <math>~ \left[ \tfrac{7}{8}\ N^3\ \log_2 N \right] ~,</math> and the total number of real additions i.e. including the post-additions (recursive additions) which can be calculated directly after the butterfly stage or after the bit-reverse stage are given by<ref name=":0" /> <math>~ \underbrace{\left[\frac{3}{2}N^3 \log_2N\right]}_\text{Real}+\underbrace{\left[\frac{3}{2}N^3 \log_2N-3N^3+3N^2\right]}_\text{Recursive} = \left[\frac{9}{2}N^3 \log_2N-3N^3+3N^2\right] ~.</math>

The conventional method to calculate MD-DCT-II is using a Row-Column-Frame (RCF) approach which is computationally complex and less productive on most advanced recent hardware platforms. The number of multiplications required to compute VR DIF Algorithm when compared to RCF algorithm are quite a few in number. The number of Multiplications and additions involved in RCF approach are given by <math>~\left[\frac{3}{2}N^3 \log_2 N \right]~</math> and <math>~ \left[\frac{9}{2}N^3 \log_2 N - 3N^3 + 3N^2 \right] ~,</math> respectively. From Table 1, it can be seen that the total number
{| class="wikitable sortable"
|+TABLE 1
Comparison of VR DIF & RCF Algorithms for computing 3D-DCT-II
!Transform Size
!3D VR Mults
!RCF Mults
!3D VR Adds
!RCF Adds
|-
|8 × 8 × 8
|2.625
|4.5
|10.875
|10.875
|-
|16 × 16 × 16
|3.5
|6
|15.188
|15.188
|-
|32 × 32 × 32
|4.375
|7.5
|19.594
|19.594
|-
|64 × 64 × 64
|5.25
|9
|24.047
|24.047
|}
of multiplications associated with the 3-D DCT VR algorithm is less than that associated with the RCF approach by more than 40%. In addition, the RCF approach involves matrix transpose and more indexing and data swapping than the new VR algorithm. This makes the 3-D DCT VR algorithm more efficient and better suited for 3-D applications that involve the 3-D DCT-II such as video compression and other 3-D image processing applications.

The main consideration in choosing a fast algorithm is to avoid computational and structural complexities. As the technology of computers and DSPs advances, the execution time of arithmetic operations (multiplications and additions) is becoming very fast, and regular computational structure becomes the most important factor.<ref>{{cite journal |doi=10.1109/78.827550 |title=On the computation of two-dimensional DCT |year=2000 |last1=Guoan Bi |last2=Gang Li |last3=Kai-Kuang Ma |last4=Tan |first4=T.C. |journal=IEEE Transactions on Signal Processing |volume=48 |issue=4 |pages=1171–1183 |bibcode=2000ITSP...48.1171B}}</ref> Therefore, although the above proposed 3-D VR algorithm does not achieve the theoretical lower bound on the number of multiplications,<ref>{{cite journal |doi=10.1109/18.144722 |title=On the multiplicative complexity of discrete cosine transforms |date=July 1992a |last1=Feig |first1=E. |last2=Winograd |first2=S. |journal=IEEE Transactions on Information Theory |volume=38 |issue=4 |pages=1387–1391}}</ref> it has a simpler computational structure as compared to other 3-D DCT algorithms. It can be implemented in place using a single butterfly and possesses the properties of the [[Cooley–Tukey FFT algorithm]] in 3-D. Hence, the 3-D VR presents a good choice for reducing arithmetic operations in the calculation of the 3-D DCT-II, while keeping the simple structure that characterize butterfly-style [[Cooley–Tukey FFT algorithm]]s.

[[File:DCT-8x8.png|thumb|250px|Two-dimensional DCT frequencies from the [[JPEG#Discrete cosine transform|JPEG DCT]]]]
The image to the right shows a combination of horizontal and vertical frequencies for an {{nobr| 8 × 8 }} <math>(~ N_1 = N_2 = 8 ~)</math> two-dimensional DCT. Each step from left to right and top to bottom is an increase in frequency by 1/2 cycle.
For example, moving right one from the top-left square yields a half-cycle increase in the horizontal frequency. Another move to the right yields two half-cycles. A move down yields two half-cycles horizontally and a half-cycle vertically. The source data {{nobr|( 8×8 )}} is transformed to a [[linear combination]] of these 64&nbsp;frequency squares.