>>11208361> I'm trying to understand how Discrete Cosine Transforms algorithms work.Like the DFT, the DCT for a specific size is just a linear transformation. y_i=sum[j=0..n-1](m_i,j * x_j). In both cases, the nature of the coefficients is such that you can express the matrix as an expression involving sums and products of "simple" matrices (those with many zeroes and/or ±1 entries and/or duplicate entries), reducing the time complexity from O(n^2) for a general matrix transform to O(n*log n) for practical DFT/DCT implementations.
> So my actual questions is: What are the butterfly operations doing in the DCT (as it doesn't appear to being used for combing smaller DCTs)?Note that a butterfly (size-2 DFT) is just [a,b]->[a+b,a-b], i.e. the matrix [[1,1], [1,-1]]. This arises in many such transforms. E.g. the Haar wavelet transform consists entirely of butterflies and radix-2 recursion; it's basically FFT with square waves instead of sinusoids.
More generally, any of the standard DCT types can be expressed as a restricted form of DFT. E.g. the type-II DCT of size N is equivalent to a DFT of 4N real values with even symmetry where the even-index values are zero. So you can take any DFT algorithm and use those constraints to eliminate some of the calculations.
There isn't any deep magic to practical DFT/DCT/etc algorithms. It's just rearranging a set of expressions so that you get a relatively small number of distinct sub-expressions repeated. Relevant trig identities are those for periodicity, even/odd symmetry, sum/difference identities, multiple angle identities.
