# How to convert DFT to DCT

I've been trying to find a fast 16 point dct2 and dct3 implementation, however I could only find it in literature expressed as mathematical equations, which honestly I couldn't understand.

However I did find a code generator that outputs dft transforms. The main problem I have is the DFT and Inverse DFT don't have the same numbers going in and out.

// Before DFT              // After DFT and IDFT
inputArray[ 0] = 12;       outputArray[ 0] = 184;
inputArray[ 1] = 12;       outputArray[ 1] = 194;
inputArray[ 2] = 12;       outputArray[ 2] = 178;
inputArray[ 3] = 14;       outputArray[ 3] = 198;
inputArray[ 4] =  8;       outputArray[ 4] = 155;
inputArray[ 5] = 10;       outputArray[ 5] = 141;
inputArray[ 6] = 12;       outputArray[ 6] = 164;
inputArray[ 7] = 12;       outputArray[ 7] = 149;
inputArray[ 8] = 12;       outputArray[ 8] = 138;
inputArray[ 9] = 12;       outputArray[ 9] = 121;
inputArray = 12;       outputArray = 107;
inputArray = 12;       outputArray = 90;
inputArray = 12;       outputArray = 74;
inputArray = 12;       outputArray = 55;
inputArray = 12;       outputArray = 37;
inputArray = 12;       outputArray = 19;


I realized the first 5 or so indexes do equal the inputs when divided by 16, however this trend doesn't continue as you go down.

Is this the expected behavior? Or is there something else I need to do the get a proper conversion?

Also I did find an 8 point dct that works well and gives the proper results, is there anyway to expand that into a fast 16 point dct?

Edit:

The reason I want to find a fast 16x16 DCT is because I'm working on a javascript video codec that supports transparency.

So after inter frame prediction is finished I'm left with a lot of residue. Because it's in javascript, and it's processing 24 frames a second I need the fastest way possible to compress and decompress this residue.

• "IDFT(DFT(input))" doesn't need to be "input"; but it MUST be "input times constant". If that's not the case, your DFT or IDFT is broken. There's nothing to discuss, then, just use an not-broken implementation. – Marcus Müller Aug 2 '18 at 17:08
• also, computing a 16-DCT "naively" using the DCT matrix is ... pretty fast on modern computers. For what reasons / applications do you need a faster DCT? – Marcus Müller Aug 2 '18 at 17:09
• Thank you for your help! I edited my question to reflect why I need a fast 16x16 dct. I'm not sure what you mean by my must be input "input times constant". Can you explain a little more about that? – YAHsaves Aug 2 '18 at 17:20
• The IDFT, is, as the name suggests, the inverse operation to the DFT; but it depends on the specific definition whether IDFT(DFT(input)) == input or input·constant. – Marcus Müller Aug 2 '18 at 19:17
• Are you sure you want to write a video codec in an interpreted language that fully abstracts the memory model away from its data? JavaScript is especially notorious for not having a proper "vector" data type that has constant access time and contiguous memory – you can basically optimize your algorithm as much as you want, but chances are that the most naive implementation in C++ or C or FORTRAN or … would absolutely outperform what you've done, simply because "handling JavaScript to do some math" is so much more work for your computer than the math that you want to do... – Marcus Müller Aug 2 '18 at 19:19

• @Fat32 i think they find ways of doing it without explicitly copying and mirroring the data and doing the FFT of size $2N$. the people to ask are the FFTW people. they know everything. – robert bristow-johnson Aug 2 '18 at 17:48