>>>>> "BobW" == BobW <nimby_GIMME_SOME_SPAM@roadrunner.com> writes:BobW> "Jerry Avins" <jya@ieee.org> wrote in message >> 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 BobW> I certainly have found many real-to-real FFT routines, but the one that's BobW> available for my microcontroller merely stuffs zeros into the imaginary data BobW> input locations and then returns the magnitude of the outputs. BobW> This particular technique, described by Mr. Lyons, puts the real data input BobW> samples into the imaginary inputs (rather than just setting them all to BobW> zero). The advantage is that the input data buffer size can be cut in half BobW> (for a particular input data set). BobW> Is it your experience that the "Lyons" technique is commonly used? A wild guess. It's not so common today because we have lots more memory. Back when 1 MB (or even 64 KB) was a lot of memory, cutting down the size of an array by half was an important optimization. Same goes for embedded devices, which now have way more memory than they did 20 years ago. Ray
Performing a 1024 point real input FFT using a 512 point complex FFT routine
Started by ●June 28, 2009
Reply by ●July 1, 20092009-07-01
Reply by ●July 1, 20092009-07-01
On Jun 30, 1:37=A0pm, Jerry Avins <j...@ieee.org> wrote:> BobW wrote: >...> > I sense that this technique of packing real data samples into the imagi=nary> > 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.i think it's rarely needed is because the complex FFTs still do pretty good. if doing an equally optimized real FFT is only around 1/2 of the computation of the complex, it hardly often where that extra octave of computational bandwidth is worth the bother of rolling their own real FFT (out of 1/2 the size of a complex FFT). unless they do it for recreational purposes. the usual reason that, in a real-time frequency-domain process that i hadn't often bothered with a real FFT is that in the case of processing real audio signals, you can put two neighboring frames of this real date and, if you're convolving with a real h[n], you can ge guaranteed that the output frames of the iFFT you'ld get corresponding to the two input frames would appear in the real and imaginary parts. this is because of linearity and time-invariancy of the convolution operation (by definition) and the fact that Re{j}=3D0 and Im{1}=3D0. there might, because of roundoff error, be numerical sources to some crosstalk between the two frames, i dunno. you usually don't care about it (or even think about it) if your data is double float.> There are > real-to real FFT libraries available that do the scut work for the user, > as good libraries should.Jerry, i wonder if Steven G. Johnson would agree with you here. i dunno. r b-j
Reply by ●July 1, 20092009-07-01
On Jun 30, 1:43=A0pm, "BobW" <nimby_GIMME_SOME_S...@roadrunner.com> wrote:> "Jerry Avins" <j...@ieee.org> wrote in message > > news:b3s2m.2448$066.1548@newsfe08.iad... > > > > > BobW wrote: > >> "Jerry Avins" <j...@ieee.org> wrote in message > >>news:bfq2m.2441$066.810@newsfe08.iad... > >>> BobW wrote: > > >>> =A0 ... > > >>>> I found the answer. It was in the last place I looked. > >>> Almost inevitably. Having found it, why look further? > > >>> =A0 ... > > >>> 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 you=r> >> take, too? > > > No. The technique seems to be widely known, but rarely needed. There ar=e> > real-to real FFT libraries available that do the scut work for the user=,> > as good libraries should. > > > 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 d=ata> input locations and then returns the magnitude of the outputs.and, before the magnitude operation, you'll have a buffer of complex data of which has its second half a complex-conjugate reflection of the first (or "zeroth") half, with the exception of the DC and Nyquist bins (but both of those will have 0 in their imaginary part). So a unique set of N numbers gets inversibly mapped to another set of N numbers.> > This particular technique, described by Mr. Lyons, puts the real data inp=ut> 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 hal=f> (for a particular input data set). > > Is it your experience that the "Lyons" technique is commonly used?i dunno if Rick takes any original credit for this technique in his book but it likely is either one of two methods; one where the real parts of the N/2 FFT are comprized by the even-indexed samples from the length-N real data and the odd samples go into the imag parts. and then you detangle the output of the FFT (by investigation into how the DFT would behave with this). the other method puts the second half into the imaginary parts and the first (or "zeroth") half goes into the reals. and then detangle the output. r b-j
Reply by ●July 3, 20092009-07-03
robert bristow-johnson wrote:> On Jun 30, 1:37 pm, Jerry Avins <j...@ieee.org> wrote: >> BobW wrote: >> > ... >>> 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. > > i think it's rarely needed is because the complex FFTs still do pretty > good. if doing an equally optimized real FFT is only around 1/2 of > the computation of the complex, it hardly often where that extra > octave of computational bandwidth is worth the bother of rolling their > own real FFT (out of 1/2 the size of a complex FFT). unless they do > it for recreational purposes. > > the usual reason that, in a real-time frequency-domain process that i > hadn't often bothered with a real FFT is that in the case of > processing real audio signals, you can put two neighboring frames of > this real date and, if you're convolving with a real h[n], you can ge > guaranteed that the output frames of the iFFT you'ld get corresponding > to the two input frames would appear in the real and imaginary parts. > this is because of linearity and time-invariancy of the convolution > operation (by definition) and the fact that Re{j}=0 and Im{1}=0. > there might, because of roundoff error, be numerical sources to some > crosstalk between the two frames, i dunno. you usually don't care > about it (or even think about it) if your data is double float. > >> There are >> real-to real FFT libraries available that do the scut work for the user, >> as good libraries should. > > Jerry, i wonder if Steven G. Johnson would agree with you here. i > dunno.I've been hoping he would weigh in. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
