StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I'm not an expert at DCTs but I have written a few <a href="https://stackoverflow.com/questions/8687148/why-fftw-on-windows-is-faster-than-linux/8687263#8687263">FFT implementations</a> in my time so I'm going to take a stab at answering this. Please take the following with a pinch of salt. </p> <pre><code>void njRowIDCT(int* blk) </code></pre> <p>You correctly say that the algorithm appears to be an 8-length Radix-2 DCT that uses fixed point arithmetic with 24:8 precision. I'm guessing the precision because the last stage right shifts by 8 to get the desired (that and the tell tale comment ;)</p> <p>Because its 8-length, its power is 3 (2^3 = 8) meaning there are 3 stages in the DCT. So far this is all very similar to FFTs. The "fourth stage" seems to be just a scaling to recover the original precision after fixed point arithmetic. </p> <p>As far as I can see the input stage is the <a href="https://stackoverflow.com/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c">bit-reversal</a> from input array blk to local variables x0-x7. x8 seems to be a temporary variable. Sorry I can't be more descriptive than that. </p> <p><strong>Bit reversal stage</strong></p> <p><img src="https://i.stack.imgur.com/ZizHD.png" alt="Bit Reversal of input"></p> <p><strong>Update</strong></p> <p>Take a look at <a href="http://www.dspguide.com/CH27.PDF" rel="nofollow noreferrer">DSP For Scientists and Engineers</a>. It gives a clear and precise explanation of signal processing topics. This chapter is on the DCT (please skip to p497). </p> <p>The Wn (twiddle factors) correspond to the Basis Functions in this chapter, although note this is describing an 8x8 (2D) DCT. </p> <p>With regard to 3 stages that I mentioned, compare to the description of an 8 point FFT:</p> <p><img src="https://i.stack.imgur.com/BctvB.png" alt="8ptFFTGraph"></p> <p>The FFT is performing butterflies on the bit-reversed input array (which are essentially complex multiply-adds), multiplying one path by the Wn or twiddle factor along the way. The FFT is performed in stages. I still haven't worked out what your DCT code is doing but decomposing it into a diagram like this may help. </p> <p>That or someone who knows what they're talking about step up ;-)</p> <p><em>I'll revisit this page and edit as I decipher more code</em></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload