Welcome Guest ( Log In | Register )

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

Group: Members
Posts: 35
Joined: 15-April 04
From: Australia
Member No.: 13509

I am trying to make sense of the output of the FFT when used to calculate a type-2 DCT (DCT-II). I managed to scrape together enough documentation that infomed me that, if I wanted to perform a DCT-II 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].


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


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.

Go to the top of the page
+Quote Post
Start new topic
post Dec 12 2005, 01:13
Post #2

Group: Developer
Posts: 1245
Joined: 16-December 02
From: Australia
Member No.: 4097

I agree that there is often not enough documentation on how to do a simple DCT using an FFT. Though it is not the best, computational-wise, it is however interesting to see the relationship between the two, esp. why the DCT is used more often than the FFT in compression (the even-symmetry creates smoothness that results in less high frequency energy).

Anyway, I was interested in this problem a while ago as well and found this link to be the best I've found.

Not sure if this is any help or not, but here is some MATLAB code I wrote during that time, which calculates the DCT using FFT.

clear all;
close all;

x=[1 2 3 4];
d = dct(x);

x2=[4 3 2 1 1 2 3 4];

n = 0:2*N-1;


f2 = real(f./shift);

d2 = f2(1:N)/sqrt(2*N);



Notice how I don't do any zero-setting (no idea why you need to anyway). I just take my original signal, mirror it and then take the fft. Now the thing to note is that the Fourier transform of an even symmetry signal is real but we can't make true even symmetry signals on a computer, so we have to compensate for the phase shift caused by the time-shift of 3.5 samples, hence the division by the FFT of the variable 'shift'. Then I scale the coefficients appropriately (to make them orthonormal), and voila.

Hope that helps in a little way cool.gif

EDIT: fixed a spelling mistake

This post has been edited by QuantumKnot: Dec 12 2005, 04:55
Go to the top of the page
+Quote Post
post Dec 13 2005, 23:25
Post #3

Group: Members
Posts: 35
Joined: 15-April 04
From: Australia
Member No.: 13509

Hi QuantumKnot,

Thanks for your reply. Indeed I had read the same page on using an FFT to do a DCT, and understood the reasoning behind having to mirror the co-efficents before placing them into a FFT.

I did a bit of experimenting, and created a "brute force" DCT using floating point maths on a PC. I had some code for a DCT-II, and re-wrote it to perform a DCT-I. The results were quite different.

I also examined the documentation on FFTW, in particular about the different types of DCT. They refer to them as 00, 01, 10, and 11. The 0 stands for no shift, the 1 stands for a half-sample shift. The first figure refers to the input, the last to the output. The FFTW routines REDFT00 = DCT-I, REDFT10 = DCT-II, REDFT01 = DCT-III, REDFT11 = DCT-IV.

Apparently, filling an FFT without padding but with mirroring (as you have done) is equivilant to a DCT-I.

Filling with padding and mirroring (as described in my first post) is supposed to be equivilant to a DCT-II (which is what I need). However, this takes the FFT to 4n. Further documentation (wikipedia in fact) hints at this "For example, a type-II DCT is equivalent to a DFT of size 4n with real-even symmetry whose even-indexed elements are zero. One of the most common methods for computing this via an FFT (e.g. the method used in FFTPACK and FFTW)..."
It goes on a bit further to say computations can be shorthened to O(nlogn) + O(n) if a pre-processing step of radix-4 is used (O(n) steps) and the FFT is then reduced to size n. A decent saving.

As I said before, my application is power impoverished hardware, where all I have is a 16-bit integer FFT routine (which works surprisingly well I must say). Additionally BinDCT may be very fast, but it is also considerably less accurate.

Again, thanks for your reply. A cursory look at your sample code has been enlightening, and I am about to print it and examine it in detail.

Cheers and thanks,
Go to the top of the page
+Quote Post

Posts in this topic

Reply to this topicStart new topic
1 User(s) are reading this topic (1 Guests and 0 Anonymous Users)
0 Members:


RSS Lo-Fi Version Time is now: 26th November 2015 - 13:10