In radix-2 FFT, why is the bit growth equal to $1+\sqrt{2}$ per stage?
I want to know the logic as to how that value has been obtained. Is it just empirical or has it been derived?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
FFT error analysis is a well-studied field with a significant literature. For a radix-2 Decimation-in-Time (DIT) butterfly, bit growth per stage can be 2.4142..., and for a Decimation-in-Frequency (DIF) stage it can be 2.8284... . Other factors are related to: matter of rounding (eg: round up, round down, round to nearest, truncate, etc.), hardware considerations (number of guard bits, overflow/underflow detection/correction, etc.), algorithm type, number representation, etc., etc.
Although the maximum numbers from a butterfly can be determined by inspection, significant analytical work has also been done in expressing average errors, error variance, etc., subject to the conditions mentioned above.
There's other info available, such as: https://groups.google.com/forum/#!msg/comp.dsp/c5c9DKYE1Qw/8SNY4gRqqBcJ
