FPGA Central

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 ==

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 cutin
> 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.engineeringproductivityto...T0001/PT10.HTM

Eric

"BobW" <[email protected]> wrote in message
news:[email protected]..
>
> 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

If 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 ==

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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

"Jerry Avins" <[email protected]> wrote in message
news:bfq2m.2441$[email protected]..
> 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.

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 ==

BobW wrote:
> "Jerry Avins" <[email protected]> wrote in message
> news:bfq2m.2441$[email protected]..
>> 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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

"Jerry Avins" <[email protected]> wrote in message
news:b3s2m.2448$[email protected]..
> BobW wrote:
>> "Jerry Avins" <[email protected]> wrote in message
>> news:bfq2m.2441$[email protected]..
>>> 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.

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 ==

[snip]

>
> Is it your experience that the "Lyons" technique is commonly used?
>

Oops. I meant to say, commonly available?

Bob

BobW wrote:
> "Jerry Avins" <[email protected]> wrote in message
> news:b3s2m.2448$[email protected]..
>> BobW wrote:
>>> "Jerry Avins" <[email protected]> wrote in message
>>> news:bfq2m.2441$[email protected]..
>>>> 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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

>>>>> "BobW" == BobW <[email protected]> writes:

BobW> "Jerry Avins" <[email protected]> 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

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.

r b-j

On Jun 30, 1:43*pm, "BobW" <nimby_GIMME_SOME_S...@roadrunner.com>
wrote:
> "Jerry Avins" <j...@ieee.org> wrote in message
>
> news:b3s2m.2448$[email protected]..
>
>
>
> > BobW wrote:
> >> "Jerry Avins" <j...@ieee.org> wrote in message
> >>news:bfq2m.2441$[email protected]..
> >>> 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.
>
>
> 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.

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 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?

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

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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯