> 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.
�����������������������������������������������������������������������
Reply by robert bristow-johnson●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 robert bristow-johnson●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
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
Reply by Jerry Avins●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.
�����������������������������������������������������������������������
Reply by Jerry Avins●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 BobW●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 BobW●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.
>
> 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 ==
Reply by Jerry Avins●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 BobW●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?
>
> ...
>
> 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 ==