Radix-4 Fast Cosine Transform

EDAboard.com Forum Index -> Digital Signal Processing -> Radix-4 Fast Cosine Transform

Author

Message

mendozaulises

Joined: 08 Mar 2006
Posts: 58
Helped: 7

17 Mar 2006 19:55 radix-4

I am trying to implement a 1024-point DCT on an FPGA. So Far I have only found Radix-2 Decimation in Frequency algorithms, but I'm interested in Radix-4 algorithms. I don't want to use the FFT approach. I am looking for algorithms developed directly for DCT-II.
Can someone help me?

Best Regards,

mimomod

Joined: 25 Jan 2006
Posts: 109
Helped: 15

17 Mar 2006 21:45 radix4+dct

Hi mendozaulises,

as far as I know, FFT is an algorithm to compute transforms (DFT, discrete sine transform, discrete cosine transform, hartley transform, etc) faster than if we use the original formula of the aforementioned transform.

Indeed in many textbooks, for example "Inside the FFT black box - serial and parallel fast Fourier transform algorithms 2000 - Chu, Eleanor Chin-hwa - CRC Press" which I downloaded from EDA (?) for other links in the Internet, refer fast discrete cosine transform by using FFT.

To summarize, the task of computing a DCT of N−1 real-valued data items can be
accomplished by computing a “real” DFT of length 2N, which can be implemented by
the FFT algorithm speciﬁcally tailored to real-valued data.

In case of radix-2 and radix-4 (or other radix, for example radix-3), it is just the atomic unit in the specified FFT algorithm. This means that for radix-2 FFT algorithm, the problem (in your case 1024 samples) at hand is decomposed until at a certain stage the algorithm only take into acount 2 specific points (samples) to process them together. This is the heart of FFT algorithm, i.e. you divide an attack the problem into smaller unit to reduce the computation burden.

In radix-4 FFT algorithm, we problem is decomposed into atomic unit of 4 samples, etc. As far as I know, the most efficient FFT algorithm is the one with radix-2. But in some applications people do need other radix to attack the problem. For example if the number of samples to be processed is the power of 3, then people do need the radix-3 FFT algorithm. Yet, until now I'm not really sure why people still use radix-4 FFT because actually it is less efficient than radix-2 FFT, and furthermore radix-4 FFT may be simplified into 2 radix-2 FFT.

I am not really sure what is your goal in your design. But if it is for speed, then radix-2 FFT algorithm is the one you need for doing DCT.

best

mendozaulises

Joined: 08 Mar 2006
Posts: 58
Helped: 7

20 Mar 2006 18:34 radix+4+dct

Thanks mimomod,
I am looking for Radix-4 algorithms, because for N being a power of four, Radix-4 algorithms are faster than radix-2 algorithms. It's just that more resourceses are needed in order to implement them. I am looking for an algorithm developed directly because using FFT to compute the DCT uses more resources than using a direct fast algorithm.
Currently I am working on a Radix-2 algorithm, it uses only 2 multipliers and 3 adders to compute the 1024-point transform. However, this algorithm requires 10 butterfly stages and 9 recombining stages.
If a use a Radix-4 FFT that has been already developed, I would only need 5 butterfly stages and 1 scaling stage, this would increase the speed at leat twice, but it also uses 3 times as much resources as the algorithm I am currently using. This because of the imaginary terms that need to be managed.

I am looking for a non-FFT Fast algorithm that uses less resources than an FFT approach, but that it is faster than the current algorithm I am using.

Thanks for your help.

Added after 7 minutes:

I forgot, the Radix-2 algorithm I am currently working on is described in the attached paper.
I just want to know is someone knows about a developed radix-4 algorithm for computing the DCT. This to compare the advantages and drawbacks of each algorithm, like resources they use, time to compute a single 1024-point transform, etc.

Google
AdSense
Google Adsense

20 Mar 2006 18:34 Ads

Sorry, but you need login in to view this attachment

mimomod

Joined: 25 Jan 2006
Posts: 109
Helped: 15

21 Mar 2006 14:33 radix-4 fft algorithm

Hi mendozaulises,

yes, you were right and i was wrong. After digging my textbook, indeed radix-4 algorithm is more efficient than radix-2 algorithm, given that the FFT is the power of 4.

Here is a paragraph from one of my texbook:

The number of multiplications in the IFFT can be reduced even further by using a radix-4 algorithm. This technique makes use of the fact that in a four-point IFFT, there are only multiplications by { 1,-1 j,-j), which actually do not need to be implemented by a full multiplier, but rather by a simple add or subtract and a switch of real and imaginary parts in the case of multiplications by j or -j. In the radix-4 algorithm, the transform is split into a number of these trivial four-point transforms, and non-trivial multiplications only have to be performed between stages of these fourpoint transforms. In this way, an N-point FFT using the radix-4 algorithm requires only (3/ Cool

N(log_2(N-2)) complex multiplications or phase rotations and Nlog_2(N) complex additions. For a 64-point FFT, for example, this means 96 rotations and 384 additions, or 1.5 and 6 rotations and additions per sample, respectively.

best