Hi, I am looking for an FFT algorithm that can give me a 4096 pt. FFT using two 64 pt. FFTs. Is it the mixed radix FFT? Thank you.
64 x 64 FFT algorithm for 4096 pt. FFT
Started by ●June 29, 2010
Reply by ●June 29, 20102010-06-29
On 6/29/2010 6:22 PM, onkars wrote:> Hi, > > I am looking for an FFT algorithm that can give me a 4096 pt. FFT using two > 64 pt. FFTs. Is it the mixed radix FFT? > > Thank you.I'd like to have a bank account That gives me a $4096 balance for two $64 deposits. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●June 29, 20102010-06-29
>On 6/29/2010 6:22 PM, onkars wrote: >> Hi, >> >> I am looking for an FFT algorithm that can give me a 4096 pt. FFT usingtwo>> 64 pt. FFTs. Is it the mixed radix FFT? >> >> Thank you. > >I'd like to have a bank account That gives me a $4096 balance for two >$64 deposits. > >Jerry >-- >Engineering is the art of making what you want from things you can get. >����������������������������������������������������������������������� >What i mean "using two 64 pt FFTs" is that there is some reordering and twiddle multiplications between the 2 64 pt FFTs. And of course the whole 4096 pt. FFT will take many cycles. I guess this can be achieved using the mixed-radix -- i.e. 4096 = 64 x 64. Hence the 1st 64 point FFT will perform 64 number of 64 pt FFTs followed by some reordering and twiddle factor mults (which I intend to learn about) and then finally again 64 number of 64 pt FFTs using the 2nd 64 pt. FFT. Is this the mixed-radix? also where can I read the theory about this mixed radix ffts -- which will enable me to implement any N (N=P*Q) pt. FFt using P pt and Q pt FFT engines. Thank you.
Reply by ●June 29, 20102010-06-29
On 6/29/2010 7:28 PM, onkars wrote:>> On 6/29/2010 6:22 PM, onkars wrote: >>> Hi, >>> >>> I am looking for an FFT algorithm that can give me a 4096 pt. FFT using > two >>> 64 pt. FFTs. Is it the mixed radix FFT? >>> >>> Thank you. >> >> I'd like to have a bank account That gives me a $4096 balance for two >> $64 deposits. >> >> Jerry >> -- >> Engineering is the art of making what you want from things you can get. >> > > What i mean "using two 64 pt FFTs" is that there is some reordering and > twiddle multiplications between the 2 64 pt FFTs. And of course the whole > 4096 pt. FFT will take many cycles. > I guess this can be achieved using the mixed-radix -- i.e. 4096 = 64 x 64. > Hence the 1st 64 point FFT will perform 64 number of 64 pt FFTs followed by > some reordering and twiddle factor mults (which I intend to learn about) > and then finally again 64 number of 64 pt FFTs using the 2nd 64 pt. FFT. > > Is this the mixed-radix? also where can I read the theory about this mixed > radix ffts -- which will enable me to implement any N (N=P*Q) pt. FFt using > P pt and Q pt FFT engines.Perhaps there is enlightenment here: www.vassilios-chouliaras.com/pubs/c39.pdf Jerry -- Engineering is the art of making what you want from things you can get.
Reply by ●June 29, 20102010-06-29
On Jun 29, 6:28�pm, "onkars" <onkar.sarode@n_o_s_p_a_m.gmail.com> wrote:> >On 6/29/2010 6:22 PM, onkars wrote: > >> Hi, > > >> I am looking for an FFT algorithm that can give me a 4096 pt. FFT using > two > >> 64 pt. FFTs. Is it the mixed radix FFT? > > >> Thank you. > > >I'd like to have a bank account That gives me a $4096 balance for two > >$64 deposits. > > >Jerry > >-- > >Engineering is the art of making what you want from things you can get. > > > > What i mean "using two 64 pt FFTs" is that there is some reordering and > twiddle multiplications between the 2 64 pt FFTs. And of course the whole > 4096 pt. FFT will take many cycles.The theory says that a 4096 FFT can be done using 4096x12 multiplications. Some savings can be achieved by careful coding, but N log_2 N is a useful rule of thumb.> I guess this can be achieved using the mixed-radix -- i.e. 4096 = 64 x 64. > Hence the 1st 64 point FFT will perform 64 number of 64 pt FFTs followed by > some reordering and twiddle factor mults (which I intend to learn about) > and then finally again 64 number of 64 pt FFTs using the 2nd 64 pt. FFT.If you do 64 64-point FFTs, that is 64x64x6 = 4096x6 muiltiplications.The next set of 64 64-point FFTs also takes 4096x6 multiplications. So, we are up to 4096x12 muiltipications already. Taking into account the re- ordering and the twiddle factors that you refer to, your proposed approach may not provide a significant gain. Plus, the programming is that much more complicated, but YMMV. --Dilip Sarwate
Reply by ●June 30, 20102010-06-30
On 6/29/2010 6:22 PM, onkars wrote:> I am looking for an FFT algorithm that can give me a 4096 pt. FFT using two > 64 pt. FFTs. Is it the mixed radix FFT?... plus second post of 7:28 PM 4096=64x64 is not mixed radix. It's 2 stages of radix 64 butterflies, so it's radix 64. Mixed radix would be 4096 = 128x32, or 32x128, or 256x16, or 16x256, or ... (it's a long list). Based on some of your previous posts, I presume that you're looking to do this in hardware. In that case, a 64x64 isn't a bad choice (there are better ones), because you can break the 64x64 down into a 4 stage pipeline of 8x8x8x8. Radix 8 is quite efficient in that you only have a couple of 'difficult' internal twiddles of the +/-.707.... type, and they can be done efficiently with a special purpose multiplier. So you'd have 4 radix 8 butterfly stages (each with a special purpose +/-. 707... multiplier), plus 3 full scale multipliers for the inter-stage twiddles. There are a lot of additional concepts that could be applied, but I'm not really sure exactly what you're trying to do, so I won't get into them. To get an idea of the basic concepts, you may want to look at: L. R. Rabiner, B. Gold, Theory and Application of Digital Signal Processing. Englewood Cliffs, NJ, Prentice-Hall, 1975. Chapters 6 and 10 in the above deal with FFT and some basic pipeline architectures. Although the book is out of print, you may be able to find it at a local university library, or on EBAY. As for the twiddles between the stages, they're fairly simple to figure out. I could tell you what they are for a 64x64 graph, or an 8x8x8x8, but then I'd be doing all the work, and you wouldn't really learn anything (here's a hint: note the pattern of the input/output order and twiddle sequence of each butterfly for the 8x8 graph in Fig. 10.15 on p. 587 in Rabiner and Gold's book. Now imagine what the graph would look like if you had 2 stages of 64x64 butterflies). If you get through all of the above and feel a little ambitious, you might want to take a look at: K. J. McGee, �Comments on �A 64-Point Fourier Transform Chip for Video Motion Compensation Using Phase Correlation,� IEEE J. Solid-State Circuits, vol. 33, no. 6, June 1998, pp. 928-932. In particular, pay attention to Section III in the above: Equivalence of Higher and Lower Radix Graphs. It has important implications for shuffle exchange algorithms and pipeline architectures (and, as noted, I originally developed the concept in 1981). Kevin McGee
Reply by ●June 30, 20102010-06-30
On Jun 29, 6:22�pm, "onkars" <onkar.sarode@n_o_s_p_a_m.gmail.com> wrote:> Hi, > > I am looking for an FFT algorithm that can give me a 4096 pt. FFT using two > 64 pt. FFTs. Is it the mixed radix FFT? > > Thank you.You need to do some reading. The following book has a good section on this: http://www.amazon.com/Digital-Signal-Processing-John-Proakis/dp/0131873741 It's in the older editions too. John
Reply by ●June 30, 20102010-06-30
"Jerry Avins" <jya@ieee.org> wrote in message news:hAuWn.8398$YX3.6555@newsfe18.iad...> On 6/29/2010 6:22 PM, onkars wrote: >> Hi, >> >> I am looking for an FFT algorithm that can give me a 4096 pt. FFT using >> two >> 64 pt. FFTs. Is it the mixed radix FFT? >> >> Thank you. > > I'd like to have a bank account That gives me a $4096 balance for two $64 > deposits.Just wait a while ;-)> > Jerry > -- > Engineering is the art of making what you want from things you can get. > �����������������������������������������������������������������������
Reply by ●July 1, 20102010-07-01
On Jun 30, 10:01�pm, "Phil Martel" <pomar...@comcast.net> wrote:> "Jerry Avins" <j...@ieee.org> wrote in message > > news:hAuWn.8398$YX3.6555@newsfe18.iad...> On 6/29/2010 6:22 PM, onkars wrote: > >> Hi, > > >> I am looking for an FFT algorithm that can give me a 4096 pt. FFT using > >> two > >> 64 pt. FFTs. Is it the mixed radix FFT? > > >> Thank you. > > > I'd like to have a bank account That gives me a $4096 balance for two $64 > > deposits. > > Just wait a while ;-)It may be a long time. However, it's still preferrable to the stock market where having a $64 balance after two $4096 deposits hasn't been uncommon. Greg
Reply by ●July 1, 20102010-07-01
On Jun 30, 11:36�pm, Greg Heath <he...@alumni.brown.edu> wrote:> > > I'd like to have a bank account That gives me a $4096 balance for two $64 > > > deposits. > > > Just wait a while ;-) > > It may be a long time. > > However, it's still preferrable to the > stock market where having a $64 balance > after two $4096 deposits hasn't been > uncommon.About nine years ago, the following appeared on a different newsgroup. (and no, I did not write it.....) ==================================================== While I typically do not attempt to give out investment advice, this is something I can really get behind. If you bought $1000 worth of Nortel stock one year ago, it would now be worth $49.00. If you bought $1000 worth of Budweiser (the beer, not the stock) one year ago, drank all the beer, and traded in the cans for the nickel deposit, you would have $79.00. My advice to you is to start drinking heavily. ===================================================
