Computing a DCT using an FFT, Signal analysis 
Computing a DCT using an FFT, Signal analysis 
Dec 9 2005, 06:40
Post
#1


Group: Members Posts: 35 Joined: 15April 04 From: Australia Member No.: 13509 
I am trying to make sense of the output of the FFT when used to calculate a type2 DCT (DCTII). I managed to scrape together enough documentation that infomed me that, if I wanted to perform a DCTII using an FFT algorithm, then the data should be arranged to be real even symmetric, with every even indexed data element set to zero.
No problem there. In addition, the outputs are correct, but half the expected value (I can see the output needs scaling by 2 to compensate for the fact that every second sample of the input is zero). However, I am tyring to figure out how the output comes to be what it is? In particular, where the zero comes from (term 4 & term 12) [counting from 0]. Input Real : 0 x0 0 x1 0 x2 0 x3 0 x3 0 x2 0 x1 0 x0 Imag : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Output Real : ya yb yc yd 0 yd yc yb ya yb yc yd 0 yd yc yb Imag : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [grumble: looks good in fixed width font, but spaces are not turning out here] In my real application, I am using a 16 point DCT, which equates to a 64 point FFT, but the above is representative. Any hints? PS: I know there are better ways of doing DCTs, but in my implementation, I only have access to an FFT routine. Cheers,Owen. 


Dec 9 2005, 12:57
Post
#2


Mad Scientist Group: Developer (Donating) Posts: 4901 Joined: 24September 01 Member No.: 13 
Use code or codebox to get it looking right.
Do you mean you cannot do a rotation or similar before the FFT? This method looks very wasteful, there are much better ways of doing it via an FFT but they need a some pre and postprocessing. 


Dec 9 2005, 21:32
Post
#3


Group: Members Posts: 35 Joined: 15April 04 From: Australia Member No.: 13509 
QUOTE (Garf @ Dec 9 2005, 03:57 AM) Use code or codebox to get it looking right. Thanks Garf, I am not so worried about appearances, more wanting to understand why it is so. I am not that familiar with the mathematics, only how to apply the end results. What I expected, and I should have put in my original post, is... I expected... Real : ya yb yc yd yd yc yb ya ya yb yc yd yd yc yb ya Imag : (all zero) That is, no zero terms in the real output. QUOTE (Garf @ Dec 9 2005, 03:57 AM) Do you mean you cannot do a rotation or similar before the FFT? This method looks very wasteful, there are much better ways of doing it via an FFT but they need a some pre and postprocessing. Yikes!! Not familiar with 'rotations' (but I have come across the term a lot). My application is targetted to hardware (so I can't use FP), and I am doing integer maths. I am trying to get away with 16 bits of precision (very convenient for the hardware). I agree, the method is very wasteful, and I intend to use the radix4 method of preprocessing to reduce the FFT size to n (rather than 4n). At the moment, I am trying out different things  but the output did give me a surprise. Nonmathematical documentation on doing a DCT using an FFT is sparse. I only found info on how the input is arranged [first post], but nothing on how the output is arranged. I did try a 16bit implementation of BinDCT, (internally, the precision extended to 22 bits) but the inaccuracies killed my application. I guess accuracy was the tradeoff for blistering speed! I suppose my essential question is : is the output correct, or have I stuffed up? As mentioned, documentation was sparse, so I could be loading the FFT indicies wrong? Thanks for the reply Garf. Owen. 


LoFi Version  Time is now: 29th November 2015  19:48 