[music-dsp] Fixed Point FFT question

[Darren Gibbs]

On Jan 2, 2005, at 8:42 PM, robert bristow-johnson wrote:
>> Could someone spare a few sentences to describe in high-level terms 
>> the
>> difference between a complex and real FFT and appropriate contexts for
>> using one over the other.  I've found piles of articles on DFT v.s.
>> FFT, and incredibly over-my-head detailed info on implementing various
>> algorithms, but I don't fully understand this distinction.
>
> the FFT is a "fast" way of performing the DFT.  it is sorta like 
> comparing
> some slick "Quick sort" algorithm to the bonehead "Bubble sort".  they 
> both
> do the same thing, but one might do it more efficiently.

Yes, the DFT v.s. FFT I get... but the real v.s. complex I'm less clear 
about.

> oh geez, if i knew the post you mention, i might have had some math in 
> it.

nope... just the possibility teaser I quoted...  :-)

> lessee, you have N samples of real input data:
>
>     u[n]                             0 <= n < N
>
> you conceptually split it into two N/2 sized blocks of real data:
>
>     u_e[n] = u[2*n]
>                                      0 <= n < N/2
>     u_o[n] = u[2*n+1]

[lots of cool looking equations that make me really really wish I'd 
taken more math in college clipped]

> clear as mud?

Well, conceptually I was able to follow you, but not deep enough to 
implement it in code...  I reckon I'm gonna to have to admit a certain 
level of defeat, for the time being treat the FFT as a slightly 
translucent black box, and find someone to implement the low-level 
magic for me.

> i would *not* recommend any of this for Fixed-point FFT unless you 
> gotta
> lotta bits (32 bit words with 64 bit accumulators).  the roundoff 
> noise of
> the FFT (as opposed to the straight forward slow DFT) is a bitch.

Hmmm.... If I've correctly understood certain bits of the articles I've 
been perusing, a real FFT requires 1/2 the space/time to perform.  In 
general, is it more clever to use the complex FFT in the way you've 
described, or to implement a real FFT as a separate algorithm?  The ARM 
CPU I'm targeting is 32-bit, but does FP in software emulation which is 
what got me on the trail of a fixed point solution. I haven't been able 
to find an explanation I could grok that describes the algorithmic 
difference between a real v.s. complex FFT.

Thanks!

darren