FFT core

[chatman]

I need an FFT/IFFT core of radix-3 for our project. I cannot use radix-2 or radix-4. Is it possible to implement such an FFT core on a programmable logic device? I need tips
Thanks in advance

 

[sreid]

Exactly what is meant by radix-2,3,4?

 

[nbucska]

base 3 : a0 +a1*3 +a2*9 +a3*27 ...+ an*3^n


<nbucska@pcperipherals DOT com> subj: eng-tips
read FAQ240-1032

 

[Skogsgurra]

Of course you can implement any algorithm in any radix. It just won't make much sense. And it will surely make your head ache a lot.

Is it necessary to do it? Can't you convert after you done it in base 2? That's the standard solution.

 

[nbucska]

Wouldn't it make more sense to collect the data in binary form? I am sure you can't find any base-3 sensor or ADC
on the market. The only thing you save are a few lines...

Or is this a school project?



<nbucska@pcperipherals DOT com> subj: eng-tips
read FAQ240-1032

 

[nbucska]

Sorry, if you want to implement it in FPGA you need
2 lines for each ternary digits ( I don't think you
can find FPGA with three level inputs).

What kind of speed do you need ? Where do you
get the ternary data from?


<nbucska@pcperipherals DOT com> subj: eng-tips
read FAQ240-1032

 

[johnwiss]

The radix-3 is related to the total length of the FFT (the length is a power of 3, e.g., 9,27,81) not the type of data you are transforming. The length of the data buffer will not be a power of two which means some wasted addressing and the possiblity that the inherent RAM sizes will not be fully utilized but who cares? Memory is cheap in FPGAs nowadays.

I think you can apply the standard Cooley-Tukey implementation which gives a good solution for size 2^n, 4^n, 8^n etc. which I have used for radix-2, radix-4, and radix-8 as well as mixed radix FFTs but never for 3^n- sized ones.

I googled and got some hits for "radix 3 FFT" so I know there are reasons to use it.

 

[BeerCandyman]

When you do a FFT it is for a certain lenght. If you can pick the lenght most pick 2^n and use CT. The can kind of math works for other number. If I want to do a 8 point FFT you do two 4 point DFT's and combine them (with a few extra multiplies) into a point 8 FFT. If I have 6 points I can "zero" pad the data to 8 (which will take longer) or I could do a 2 point DFT followed by a 3 point DFT.

The radix is the base number of points you are going to use. So really there is no 2 point FFT. Its a 2 point DFT (it can't be broken down any smaller) A 3 point DFT can't be broken any more either (it is prime). A 4 point transform can either be a radix 4 algorithm or it can be radix 2 (2 twos that are combined). If you use only 3 point DFT's to do a FFT it's a radix 3 based FFT. If you use different size DFT's to build up a FFT it is called a mixed radix algorithm..

You use these different radix algorithm so you don't have to zero pad you input vector. For example if I have 96 points I could use 5 levels of 2 (32) and one level of three. If I stay strictly with a radix algorithm I have zero pad my vector out to 128.

Steve