Fast Fourier Transform
Precision
The base-4 matrix expression (1) uses a form of “strength reduction” that trades off multipliers for adders. Since all additions are done to full precision, the round-off errors occur primarily in the multiplication step, which are reduced considerably compared to the usual DFT matrix expression Z=CX. The actual measured precision for a 1024-point transform is shown in Table 1 based on a large set of random input data. Here, it can be seen that the 16-bit base-4 FFT has a factor of ~4 better precision than a 16-bit Altera streaming fixed size block floating point circuit and is within a factor of ~2 compared to a 20-bit Altera circuit.
|
Error |
Altera
16-bit |
Altera
20-bit |
Base-4
16-bit |
|
Mean |
-0.0003806 |
-0.00003909 |
0.0000967 |
|
Standard Deviation |
0.00118 |
0.000217 |
0.000412 |
|
Minimum Error |
-0.0292 |
-0.01008 |
-0.01556 |
|
Maximum Error |
0.0192 |
0.00426 |
0.0283 |
Table 1 Measured precision
for 1024-point transform.