/sci/ - Science & Math

>>11199661

I'm trying to understand how Discrete Cosine Transforms algorithms work. I'm looking at a fixed size DCT (N=8), you can probably guess why I'm interested. Also note that I'm 100% self-taught in maths stuff through mostly wikipedia so I have many gaps.

My initial thought that was because of its similarity to a DFT it might be possible to do something similar to a recursive radix 2 DFT algorithm. But after I looked at some control flow graphs (such as pic related) none looked symmetrical despite there being the 'butterfly' operation in both DCT and DFT.

I found the paper 'Low-complexity 8-point DCT Approximations Based on Integer Functions' but it's very heavy on matrices so I'm struggling to understand a lot of it, but what I can gather it looks like you can construct a matrix, peform some reduction operation (like rounding) on it, extract constants and use it with the operations graph they show.

The constants from pic related are (though I'm not sure how these were derived):
m1 = cos(4pi/16)
m2 = cos(6pi/16)
m3 = cos(2pi/16) - cos(6pi/16)
m4 = cos(2pi/16) + cos(6pi/16)

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)?