FFT question

I am looking at "Understanding Digital Signal Processing" Second
Edition page 137- figure 4-5.  It is a full decimation in time
butterfly diagram for an 8 point FFT

(It seems like everyone here has this book as near as I can tell - ha
ha)


-------------------------------------------
Here are my thoughts:

I know that for a sequence of real numbers that the DFT coefficients:
X(7), X(6), and X(5) are always conjugates of X(1), X(2) and X(3).

There fore if you calculate X(1), X(2) and X(3), you have essentially
calculated X(7), X(6) and X(5)

Yet the butterfly diagram does not explicitly show this shortcut.

-------------------------------------------

Here are my questions:


1. I assume every single real world implementation of an FFT takes
advantage of this conjugate symmetry.  Does it give an additional
advantage over the butterfly diagram (It seems like it does give a
slight advantage)?

2.  Are there diagrams that show the butterfly for calculating X(0)-
X(4) using the butterfly lines, then show X(5)-X(7) as a fallout from
X(1)-X(3)?



Thanks,

Brent

On Mar 25, 5:14 pm, buleg...@columbus.rr.com wrote:
> 1. I assume every single real world implementation of an FFT takes
> advantage of this conjugate symmetry.  Does it give an additional
> advantage over the butterfly diagram (It seems like it does give a
> slight advantage)?

Note that the conjugate symmetry is only for real inputs; there are
real-world cases involving complex inputs where that advantage is not
applicable.

However, yes it is true that FFT implementations exploiting the
special case of real inputs are extremely common.  If you start with
real inputs and throw away the redundant operations involving the zero
imaginary parts or computing redundant outputs, then you can save
slightly over a factor of two in the number of operations (and the
memory usage, etc.).  Another common approach is a trick to write a
real-input FFT of size N in terms of a complex FFT of size N/2, for
even N, with a similar computational advantage.

> 2.  Are there diagrams that show the butterfly for calculating X(0)-
> X(4) using the butterfly lines, then show X(5)-X(7) as a fallout from
> X(1)-X(3)?

FFTs specialized for real data have been widely described in the
literature.

If you specifically want butterfly diagrams, I seem to remember that
there were butterfly diagrams in e.g. Sorensen's widely-cited 1987
paper:

H. V. Sorensen, D. L. Jones, M. T. Heideman, and C. S. Burrus, 1987,
Real-valued fast Fourier transform algorithms, IEEE Trans. Acoust.
Speech Sig. Processing ASSP-35: 849-863.

(I've never found butterfly diagrams particularly useful myself.  Just
show me the recursive step(s); everything else follows by induction.)

Regards,
Steven G. Johnson

On Mar 25, 11:57&#4294967295;pm, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
> On Mar 25, 5:14 pm, buleg...@columbus.rr.com wrote:
>
> > 1. I assume every single real world implementation of an FFT takes
> > advantage of this conjugate symmetry. &#4294967295;Does it give an additional
> > advantage over the butterfly diagram (It seems like it does give a
> > slight advantage)?
>
> Note that the conjugate symmetry is only for real inputs; there are
> real-world cases involving complex inputs where that advantage is not
> applicable.
>
> However, yes it is true that FFT implementations exploiting the
> special case of real inputs are extremely common. &#4294967295;If you start with
> real inputs and throw away the redundant operations involving the zero
> imaginary parts or computing redundant outputs, then you can save
> slightly over a factor of two in the number of operations (and the
> memory usage, etc.). &#4294967295;Another common approach is a trick to write a
> real-input FFT of size N in terms of a complex FFT of size N/2, for
> even N, with a similar computational advantage.
>
> > 2. &#4294967295;Are there diagrams that show the butterfly for calculating X(0)-
> > X(4) using the butterfly lines, then show X(5)-X(7) as a fallout from
> > X(1)-X(3)?
>
> FFTs specialized for real data have been widely described in the
> literature.
>
> If you specifically want butterfly diagrams, I seem to remember that
> there were butterfly diagrams in e.g. Sorensen's widely-cited 1987
> paper:
>
> H. V. Sorensen, D. L. Jones, M. T. Heideman, and C. S. Burrus, 1987,
> Real-valued fast Fourier transform algorithms, IEEE Trans. Acoust.
> Speech Sig. Processing ASSP-35: 849-863.
>
> (I've never found butterfly diagrams particularly useful myself. &#4294967295;Just
> show me the recursive step(s); everything else follows by induction.)
>
> Regards,
> Steven G. Johnson

Thanks for the reply.

Brent

On Wed, 26 Mar 2008 03:30:43 -0700 (PDT), bulegoge@columbus.rr.com
wrote:

>On Mar 25, 11:57&#4294967295;pm, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
>> On Mar 25, 5:14 pm, buleg...@columbus.rr.com wrote:
>>
>> > 1. I assume every single real world implementation of an FFT takes
>> > advantage of this conjugate symmetry. &#4294967295;Does it give an additional
>> > advantage over the butterfly diagram (It seems like it does give a
>> > slight advantage)?
>>
>> Note that the conjugate symmetry is only for real inputs; there are
>> real-world cases involving complex inputs where that advantage is not
>> applicable.
>>
>> However, yes it is true that FFT implementations exploiting the
>> special case of real inputs are extremely common. &#4294967295;If you start with
>> real inputs and throw away the redundant operations involving the zero
>> imaginary parts or computing redundant outputs, then you can save
>> slightly over a factor of two in the number of operations (and the
>> memory usage, etc.). &#4294967295;Another common approach is a trick to write a
>> real-input FFT of size N in terms of a complex FFT of size N/2, for
>> even N, with a similar computational advantage.
>>
>> > 2. &#4294967295;Are there diagrams that show the butterfly for calculating X(0)-
>> > X(4) using the butterfly lines, then show X(5)-X(7) as a fallout from
>> > X(1)-X(3)?
>>
>> FFTs specialized for real data have been widely described in the
>> literature.
>>
>> If you specifically want butterfly diagrams, I seem to remember that
>> there were butterfly diagrams in e.g. Sorensen's widely-cited 1987
>> paper:
>>
>> H. V. Sorensen, D. L. Jones, M. T. Heideman, and C. S. Burrus, 1987,
>> Real-valued fast Fourier transform algorithms, IEEE Trans. Acoust.
>> Speech Sig. Processing ASSP-35: 849-863.
>>
>> (I've never found butterfly diagrams particularly useful myself. &#4294967295;Just
>> show me the recursive step(s); everything else follows by induction.)
>>
>> Regards,
>> Steven G. Johnson
>
>Thanks for the reply.
>
>Brent

Hello Brent,
  So you're trying to avoid unecessary computations 
huh?  Ha ha.  This is good.

I don't recall seeing any butterfly that explicitly 
showed (indicated) unecessary computations. 

To add a tiny bit to what Steven wrote, I've seen papers 
that discuss the possibilty of reducing the number of 
computations in some of the standard radix-2 FFTs 
based on some unusual (uncommon) input sample conditions.  
You can search the web for "+FFT +pruning" to find more 
info on that if you wish.

Steven's good comments about "real-input FFTs" made me 
recall to ask you if you've had a look at Section 13.6 
of your "Understanding DSP" book?

Brent, if you send me a personal E-mail, I'll send you 
the errata for your particular "Printing" of the book.

Regards,
[-Rick-]


Those 
papers