[music-dsp] Fixed Point FFT question
tsquank at yahoo.com
Mon Jan 3 15:22:49 EST 2005
On Jan 2, 2005, at 8:42 PM, robert bristow-johnson wrote:
>> Could someone spare a few sentences to describe in high-level terms
>> 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
> some slick "Quick sort" algorithm to the bonehead "Bubble sort". they
> 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
> oh geez, if i knew the post you mention, i might have had some math in
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
> 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.
More information about the music-dsp