Content deleted Content added
m review: rm unnec quotes |
Link |
||
Line 506:
Specialized DCT algorithms, on the other hand, see widespread use for transforms of small, fixed sizes such as the {{nobr| 8 × 8 }} DCT-II used in [[JPEG]] compression, or the small DCTs (or MDCTs) typically used in audio compression. (Reduced code size may also be a reason to use a specialized DCT for embedded-device applications.)
In fact, even the DCT algorithms using an ordinary FFT are sometimes equivalent to pruning the redundant operations from a larger FFT of real-symmetric data, and they can even be optimal from the perspective of arithmetic counts. For example, a type-II DCT is equivalent to a DFT of size <math>~ 4N ~</math> with real-even symmetry whose even-indexed elements are zero. One of the most common methods for computing this via an FFT (e.g. the method used in [[FFTPACK]] and [[Fastest Fourier Transform in the West|FFTW]]) was described by {{harvtxt|Narasimha|Peterson|1978}} and {{harvtxt|Makhoul|1980}}, and this method in hindsight can be seen as one step of a radix-4 decimation-in-time Cooley–Tukey algorithm applied to the "logical" real-even DFT corresponding to the DCT-II.{{efn|
The radix-4 step reduces the size <math>~ 4N ~</math> DFT to four size <math>~ N ~</math> DFTs of real data, two of which are zero, and two of which are equal to one another by the even symmetry. Hence giving a single size <math>~ N ~</math> FFT of real data plus <math>~ \mathcal{O}(N) ~</math> [[butterfly (FFT algorithm)|butterflies]], once the trivial and / or duplicate parts are eliminated and / or merged.
}}
| |||