So, there are algorithms out there to perform an FFT on real data, that save (I think) roughly 2x the calculations of FFTs for complex data. I did a quick search, but didn't find any that are made specifically for FPGAs. Was my search too quick, or are there no IP sources to do this? It would seem like a slam-dunk for Xilinx and Intel/Altera to include these algorithms in their FFT libraries. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com I'm looking for work -- see my website!
All-real FFT for FPGA
Started by ●February 12, 2017
Reply by ●February 12, 20172017-02-12
On 2/12/2017 1:05 PM, Tim Wescott wrote:> So, there are algorithms out there to perform an FFT on real data, that > save (I think) roughly 2x the calculations of FFTs for complex data. > > I did a quick search, but didn't find any that are made specifically for > FPGAs. Was my search too quick, or are there no IP sources to do this? > > It would seem like a slam-dunk for Xilinx and Intel/Altera to include > these algorithms in their FFT libraries.I thought I replied to this, but my computer has been crashing a bit so maybe I lost that one. An FFT is inherently a complex function. Real data can be processed by taking advantage of some of the symmetries in the FFT. I don't recall the details as it has been over a decade since I worked with this, but you can fold half of the real data into the imaginary portion, run a size N/2 FFT and then unfold the results. I believe you have to run a final N sized complex pass on these results to get your final answer. I do recall it saved a *lot* when performing FFTs, nearly 50%. -- Rick C
Reply by ●February 13, 20172017-02-13
On Sun, 12 Feb 2017 20:32:59 -0500, rickman wrote:> On 2/12/2017 1:05 PM, Tim Wescott wrote: >> So, there are algorithms out there to perform an FFT on real data, that >> save (I think) roughly 2x the calculations of FFTs for complex data. >> >> I did a quick search, but didn't find any that are made specifically >> for FPGAs. Was my search too quick, or are there no IP sources to do >> this? >> >> It would seem like a slam-dunk for Xilinx and Intel/Altera to include >> these algorithms in their FFT libraries. > > I thought I replied to this, but my computer has been crashing a bit so > maybe I lost that one. > > An FFT is inherently a complex function. Real data can be processed by > taking advantage of some of the symmetries in the FFT. I don't recall > the details as it has been over a decade since I worked with this, but > you can fold half of the real data into the imaginary portion, run a > size N/2 FFT and then unfold the results. I believe you have to run a > final N sized complex pass on these results to get your final answer. I > do recall it saved a *lot* when performing FFTs, nearly 50%.My understanding is that there were some software packages that baked that into the algorithm, for what savings I don't know. I was wondering if it was done for FFTs as well. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com I'm looking for work -- see my website!
Reply by ●February 13, 20172017-02-13
On 2/12/2017 1:05 PM, Tim Wescott wrote:> So, there are algorithms out there to perform an FFT on real data, that > save (I think) roughly 2x the calculations of FFTs for complex data.> I did a quick search, but didn't find any that are made specifically for > FPGAs. Was my search too quick, or are there no IP sources to do this?> It would seem like a slam-dunk for Xilinx and Intel/Altera to include > these algorithms in their FFT libraries.Protip: the synthesizer should trim out the unneeded logic, so you don't need an optimized library macro. Steve, always helpful
Reply by ●February 13, 20172017-02-13
On 2/13/2017 12:03 AM, Tim Wescott wrote:> On Sun, 12 Feb 2017 20:32:59 -0500, rickman wrote: > >> On 2/12/2017 1:05 PM, Tim Wescott wrote: >>> So, there are algorithms out there to perform an FFT on real data, that >>> save (I think) roughly 2x the calculations of FFTs for complex data. >>> >>> I did a quick search, but didn't find any that are made specifically >>> for FPGAs. Was my search too quick, or are there no IP sources to do >>> this? >>> >>> It would seem like a slam-dunk for Xilinx and Intel/Altera to include >>> these algorithms in their FFT libraries. >> >> I thought I replied to this, but my computer has been crashing a bit so >> maybe I lost that one. >> >> An FFT is inherently a complex function. Real data can be processed by >> taking advantage of some of the symmetries in the FFT. I don't recall >> the details as it has been over a decade since I worked with this, but >> you can fold half of the real data into the imaginary portion, run a >> size N/2 FFT and then unfold the results. I believe you have to run a >> final N sized complex pass on these results to get your final answer. I >> do recall it saved a *lot* when performing FFTs, nearly 50%. > > My understanding is that there were some software packages that baked > that into the algorithm, for what savings I don't know. I was wondering > if it was done for FFTs as well.I'm not sure what you mean. When you say "baking" it into the algorithm, it would do pretty much what I described. That *is* the algorithm. I haven't heard of any other optimizations. The savings is in time/size. Essentially it does an N/2 size FFT with an extra pass, so instead of N*log(N) step it takes (N+1)*log(N/2) steps. -- Rick C
Reply by ●February 13, 20172017-02-13
On 2/13/2017 1:48 AM, rickman wrote:> On 2/13/2017 12:03 AM, Tim Wescott wrote: >> On Sun, 12 Feb 2017 20:32:59 -0500, rickman wrote: >> >>> On 2/12/2017 1:05 PM, Tim Wescott wrote: >>>> So, there are algorithms out there to perform an FFT on real data, that >>>> save (I think) roughly 2x the calculations of FFTs for complex data. >>>> >>>> I did a quick search, but didn't find any that are made specifically >>>> for FPGAs. Was my search too quick, or are there no IP sources to do >>>> this? >>>> >>>> It would seem like a slam-dunk for Xilinx and Intel/Altera to include >>>> these algorithms in their FFT libraries. >>> >>> I thought I replied to this, but my computer has been crashing a bit so >>> maybe I lost that one. >>> >>> An FFT is inherently a complex function. Real data can be processed by >>> taking advantage of some of the symmetries in the FFT. I don't recall >>> the details as it has been over a decade since I worked with this, but >>> you can fold half of the real data into the imaginary portion, run a >>> size N/2 FFT and then unfold the results. I believe you have to run a >>> final N sized complex pass on these results to get your final answer. I >>> do recall it saved a *lot* when performing FFTs, nearly 50%. >> >> My understanding is that there were some software packages that baked >> that into the algorithm, for what savings I don't know. I was wondering >> if it was done for FFTs as well. > > I'm not sure what you mean. When you say "baking" it into the > algorithm, it would do pretty much what I described. That *is* the > algorithm. I haven't heard of any other optimizations. The savings is > in time/size. Essentially it does an N/2 size FFT with an extra pass, > so instead of N*log(N) step it takes (N+1)*log(N/2) steps.Opps, I wrote that wrong. The optimized result would be order N/2 * (log(N)+1). Just to be clear (or less clear depending on how you read this), there are actually N/2 butterflies in each pass of the FFT. I didn't show that since the constant 1/2 applies to both the standard FFT and the optimized FFT. The point is the number of butterflies is cut in half on each pass of the FFT for the optimized approach. -- Rick C
Reply by ●February 13, 20172017-02-13
On 2/13/2017 12:24 AM, Steve Pope wrote:> On 2/12/2017 1:05 PM, Tim Wescott wrote: > >> So, there are algorithms out there to perform an FFT on real data, that >> save (I think) roughly 2x the calculations of FFTs for complex data. > >> I did a quick search, but didn't find any that are made specifically for >> FPGAs. Was my search too quick, or are there no IP sources to do this? > >> It would seem like a slam-dunk for Xilinx and Intel/Altera to include >> these algorithms in their FFT libraries. > > Protip: the synthesizer should trim out the unneeded logic, so > you don't need an optimized library macro.I don't think the synthesizer is capable of getting the same savings. The optimizations would see the zero imaginary inputs and optimize the first pass of the FFT. All passes would be N/2 butterflies while the optimized approach would use half that many at the expense of an extra pass. This is a big savings that the synthesis tools aren't likely to figure out unless they recognize you are performing an FFT. Someone refresh my memory. If you do an FFT with zeros in the imaginary part of the inputs, the output has a symmetry that can be used to process two real streams at once. I can't recall how it works exactly, but that symmetry is the basis for separating the results of the two halves of the original sequence before completing the last pass. One portion is pulled out because of the even symmetry and the other portion is pulled out because of the odd symmetry. I found this page that appears to explain it, but I haven't taken the time to dig into the math. I think I'd have to start all over again, it's just been too long. -- Rick C
Reply by ●February 13, 20172017-02-13
On Mon, 13 Feb 2017 01:48:49 -0500, rickman wrote:> On 2/13/2017 12:03 AM, Tim Wescott wrote: >> On Sun, 12 Feb 2017 20:32:59 -0500, rickman wrote: >> >>> On 2/12/2017 1:05 PM, Tim Wescott wrote: >>>> So, there are algorithms out there to perform an FFT on real data, >>>> that save (I think) roughly 2x the calculations of FFTs for complex >>>> data. >>>> >>>> I did a quick search, but didn't find any that are made specifically >>>> for FPGAs. Was my search too quick, or are there no IP sources to do >>>> this? >>>> >>>> It would seem like a slam-dunk for Xilinx and Intel/Altera to include >>>> these algorithms in their FFT libraries. >>> >>> I thought I replied to this, but my computer has been crashing a bit >>> so maybe I lost that one. >>> >>> An FFT is inherently a complex function. Real data can be processed >>> by taking advantage of some of the symmetries in the FFT. I don't >>> recall the details as it has been over a decade since I worked with >>> this, but you can fold half of the real data into the imaginary >>> portion, run a size N/2 FFT and then unfold the results. I believe >>> you have to run a final N sized complex pass on these results to get >>> your final answer. I do recall it saved a *lot* when performing FFTs, >>> nearly 50%. >> >> My understanding is that there were some software packages that baked >> that into the algorithm, for what savings I don't know. I was >> wondering if it was done for FFTs as well. > > I'm not sure what you mean. When you say "baking" it into the > algorithm, it would do pretty much what I described. That *is* the > algorithm. I haven't heard of any other optimizations. The savings is > in time/size. Essentially it does an N/2 size FFT with an extra pass, > so instead of N*log(N) step it takes (N+1)*log(N/2) steps.There's a distinct symmetry to the Fourier transform that you could use at each step of the way instead of doing the whole thing and fixing it up at the end. I don't know if it would save steps, but it would certainly be easier on someone who just wants to apply an algorithm. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com I'm looking for work -- see my website!
Reply by ●February 13, 20172017-02-13
On Sun, 12 Feb 2017 12:05:17 -0600, Tim Wescott <seemywebsite@myfooter.really> wrote:>So, there are algorithms out there to perform an FFT on real data, that >save (I think) roughly 2x the calculations of FFTs for complex data. > >I did a quick search, but didn't find any that are made specifically for >FPGAs. Was my search too quick, or are there no IP sources to do this? > >It would seem like a slam-dunk for Xilinx and Intel/Altera to include >these algorithms in their FFT libraries.As has been mentioned, there are a number of algorithms that exploit symmetries to prune the computations down near minimal, but I don't know of any canned FPGA libraries that do it. I don't know of any canned FPGA libraries that include a FHT (Fast Hartley Transofrm) either, which would also serve essentially the same purpose. As Steve suggested, you could just force the imaginary part to static zeroes and let the synthesizer optimizations clean it up, but it probably wouldn't be quite as good as using a well-designed RFFT if one was available. All that said, many of the existing FPGA FFT libraries are pretty efficient, so it may be worth just brute-forcing it and see whether it is good enough. --- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus
Reply by ●February 13, 20172017-02-13
On Monday, February 13, 2017 at 2:21:14 PM UTC-5, eric.j...@ieee.org wrote:> On Sun, 12 Feb 2017 12:05:17 -0600, Tim Wescott > <seemywebsite@myfooter.really> wrote: > > >So, there are algorithms out there to perform an FFT on real data, that > >save (I think) roughly 2x the calculations of FFTs for complex data. > > > >I did a quick search, but didn't find any that are made specifically for > >FPGAs. Was my search too quick, or are there no IP sources to do this? > > > >It would seem like a slam-dunk for Xilinx and Intel/Altera to include > >these algorithms in their FFT libraries. > > As has been mentioned, there are a number of algorithms that exploit > symmetries to prune the computations down near minimal, but I don't > know of any canned FPGA libraries that do it. I don't know of any > canned FPGA libraries that include a FHT (Fast Hartley Transofrm) > either, which would also serve essentially the same purpose. > > As Steve suggested, you could just force the imaginary part to static > zeroes and let the synthesizer optimizations clean it up, but it > probably wouldn't be quite as good as using a well-designed RFFT if > one was available. > > All that said, many of the existing FPGA FFT libraries are pretty > efficient, so it may be worth just brute-forcing it and see whether it > is good enough.Tim, i dunno diddley-shit about how algorithms get programmed into FPGAs. but assuming you do (or your client), i can send you the math necessary to use a regular-old complex FFT of N/2 points to perform a real FFT for N points. put the N/2 even-numbered reals into the real part and the N/2 odd-numbered reals into the imaginary part, do the size-N/2 complex FFT and sort it out on the output of the FFT. you must, of course, use the Hermitian symmetry of the FT of a real signal to detangle the results. and you will need the twiddle factors of the size-N FFT that are not needed in the size-N/2 FFT. lemme know, i'll send you something (unless you figure it out). L8r, r b-j
