I'm using a microcontroller (dsPIC30F3013) to do an FFT on some "real" data (from a microphone) and I don't have enough internal RAM to get the frequency resolution I need. I found a forum entry by Rick Lyons as follows: -quote- Does the dsPIC33 allow you to perform 512-point FFT on complex-valued input samples? If so, there's a way to perform a 1024-point *real-input* FFT using a 512-point complex FFT routine. [-Rick-] -end quote- The FFT routine I have available does take a complex input (two sixteen bit words), and the existing code merely stuffs zeroes into the imaginary part of each complex input. So, can anyone tell me what the trick is for allowing this complex-input FFT to be more efficient with real input data such that I can effectively cut in half the input record length I need to use. Thanks in advance. Bob -- == All google group posts are automatically deleted due to spam ==
Performing a 1024 point real input FFT using a 512 point complex FFT routine
Started by ●June 28, 2009
Reply by ●June 28, 20092009-06-28
On Jun 28, 5:18�pm, "BobW" <nimby_GIMME_SOME_S...@roadrunner.com> wrote:> I'm using a microcontroller (dsPIC30F3013) to do an FFT on some "real" data > (from a microphone) and I don't have enough internal RAM to get the > frequency resolution I need. > > I found a forum entry by Rick Lyons as follows: > > -quote- > Does the dsPIC33 allow you to perform > 512-point FFT on complex-valued input > samples? �If so, there's a way to perform > a 1024-point *real-input* FFT using > a 512-point complex FFT routine. > [-Rick-] > -end quote- > > The FFT routine I have available does take a complex input (two sixteen bit > words), and the existing code merely stuffs zeroes into the imaginary part > of each complex input. > > So, can anyone tell me what the trick is for allowing this complex-input FFT > to be more efficient with real input data such that I can effectively cut in > half the input record length I need to use. > > Thanks in advance. > > Bob > -- > == All google group posts are automatically deleted due to spam ==Google is your friend. Try searching on 'real FFT' - the 3rd entry for me is this which seems useful: http://www.engineeringproductivitytools.com/stuff/T0001/PT10.HTM Eric
Reply by ●June 29, 20092009-06-29
"BobW" <nimby_GIMME_SOME_SPAM@roadrunner.com> wrote in message news:Rsidnd6P067YldXXnZ2dnUVZ_u-dnZ2d@giganews.com...> > I'm using a microcontroller (dsPIC30F3013) to do an FFT on some "real" > data (from a microphone) and I don't have enough internal RAM to get the > frequency resolution I need. > > I found a forum entry by Rick Lyons as follows: > > -quote- > Does the dsPIC33 allow you to perform > 512-point FFT on complex-valued input > samples? If so, there's a way to perform > a 1024-point *real-input* FFT using > a 512-point complex FFT routine. > [-Rick-] > -end quote- > > The FFT routine I have available does take a complex input (two sixteen > bit words), and the existing code merely stuffs zeroes into the imaginary > part of each complex input. > > So, can anyone tell me what the trick is for allowing this complex-input > FFT to be more efficient with real input data such that I can effectively > cut in half the input record length I need to use. > > Thanks in advance. > > BobIf anybody is interested, I found the answer. It was in the last place I looked. Rick Lyon's book "Understanding Digital Signal Processing" has an excellent and (relatively) simple description of the technique. It involves a decent amount of processing beyond the complex FFT, but it's doable. So, with Rick's help, I think that I can do what I need to do with the limited RAM that I have available. Bob -- == All google group posts are automatically deleted due to spam ==
Reply by ●June 30, 20092009-06-30
BobW wrote: ...> I found the answer. It was in the last place I looked.Almost inevitably. Having found it, why look further? ... Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●June 30, 20092009-06-30
"Jerry Avins" <jya@ieee.org> wrote in message news:bfq2m.2441$066.810@newsfe08.iad...> BobW wrote: > > ... > >> I found the answer. It was in the last place I looked. > > Almost inevitably. Having found it, why look further? > > ... > > JerryYes. I was merely trying to add a little bit of humor to this otherwise-dry newsgroup. I sense that this technique of packing real data samples into the imaginary part of the input to the FFT is rather uncommon. Is that your take, too? Bob -- == All google group posts are automatically deleted due to spam ==
Reply by ●June 30, 20092009-06-30
BobW wrote:> "Jerry Avins" <jya@ieee.org> wrote in message > news:bfq2m.2441$066.810@newsfe08.iad... >> BobW wrote: >> >> ... >> >>> I found the answer. It was in the last place I looked. >> Almost inevitably. Having found it, why look further? >> >> ... >> >> Jerry > > Yes. I was merely trying to add a little bit of humor to this otherwise-dry > newsgroup.It alternates. Sometimes the humor gets laid on thick. (When I attempt it, it often falls flat.)> I sense that this technique of packing real data samples into the imaginary > part of the input to the FFT is rather uncommon. Is that your take, too?No. The technique seems to be widely known, but rarely needed. There are real-to real FFT libraries available that do the scut work for the user, as good libraries should. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●June 30, 20092009-06-30
"Jerry Avins" <jya@ieee.org> wrote in message news:b3s2m.2448$066.1548@newsfe08.iad...> BobW wrote: >> "Jerry Avins" <jya@ieee.org> wrote in message >> news:bfq2m.2441$066.810@newsfe08.iad... >>> BobW wrote: >>> >>> ... >>> >>>> I found the answer. It was in the last place I looked. >>> Almost inevitably. Having found it, why look further? >>> >>> ... >>> >>> Jerry >> >> Yes. I was merely trying to add a little bit of humor to this >> otherwise-dry newsgroup. > > It alternates. Sometimes the humor gets laid on thick. (When I attempt it, > it often falls flat.) > >> I sense that this technique of packing real data samples into the >> imaginary part of the input to the FFT is rather uncommon. Is that your >> take, too? > > No. The technique seems to be widely known, but rarely needed. There are > real-to real FFT libraries available that do the scut work for the user, > as good libraries should. > > JerryI certainly have found many real-to-real FFT routines, but the one that's available for my microcontroller merely stuffs zeros into the imaginary data input locations and then returns the magnitude of the outputs. This particular technique, described by Mr. Lyons, puts the real data input samples into the imaginary inputs (rather than just setting them all to zero). The advantage is that the input data buffer size can be cut in half (for a particular input data set). Is it your experience that the "Lyons" technique is commonly used? Bob -- == All google group posts are automatically deleted due to spam ==
Reply by ●June 30, 20092009-06-30
[snip]> > Is it your experience that the "Lyons" technique is commonly used? >Oops. I meant to say, commonly available? Bob
Reply by ●June 30, 20092009-06-30
BobW wrote:> "Jerry Avins" <jya@ieee.org> wrote in message > news:b3s2m.2448$066.1548@newsfe08.iad... >> BobW wrote: >>> "Jerry Avins" <jya@ieee.org> wrote in message >>> news:bfq2m.2441$066.810@newsfe08.iad... >>>> BobW wrote: >>>> >>>> ... >>>> >>>>> I found the answer. It was in the last place I looked. >>>> Almost inevitably. Having found it, why look further? >>>> >>>> ... >>>> >>>> Jerry >>> Yes. I was merely trying to add a little bit of humor to this >>> otherwise-dry newsgroup. >> It alternates. Sometimes the humor gets laid on thick. (When I attempt it, >> it often falls flat.) >> >>> I sense that this technique of packing real data samples into the >>> imaginary part of the input to the FFT is rather uncommon. Is that your >>> take, too? >> No. The technique seems to be widely known, but rarely needed. There are >> real-to real FFT libraries available that do the scut work for the user, >> as good libraries should. >> >> Jerry > > I certainly have found many real-to-real FFT routines, but the one that's > available for my microcontroller merely stuffs zeros into the imaginary data > input locations and then returns the magnitude of the outputs.So you wrote a better one. The pressure to meet a deadline sometimes leads to inferior work.> This particular technique, described by Mr. Lyons, puts the real data input > samples into the imaginary inputs (rather than just setting them all to > zero). The advantage is that the input data buffer size can be cut in half > (for a particular input data set). > > Is it your experience that the "Lyons" technique is commonly used?Just an assumption. I think that I remember FFTW's library function doing that. I've used an assembly-language version for the TMS320C34 that one of their application programmers sent me. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●June 30, 20092009-06-30
BobW wrote:> [snip] > >> Is it your experience that the "Lyons" technique is commonly used? >> > > Oops. I meant to say, commonly available?About that, I can't say. (I'm just a dilettante.) Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
