Distributed Scaling Algorithm for FFT Computation Using Fixed-Point Arithmetic

Scaling is necessary to prevent output overflow in FFT computation using fixed-point arithmetic. In this paper, we present a novel distributed scaling algorithm to improve the computation accuracy. Unlike conventional fixed scaling algorithms, where scaling is performed at each stage or selected stages of FFT with one unified scaling factor, scaling in our method is done individually at each butterfly. In total, there are n/4 different scaling factors to be updated at each stage for an n-point Radix-4 FFT. Under this scheme, each butterfly has to accomplish following tasks in sequence: alignment/relaxation, scaling, and computation. Alignment is needed since the data inputs to one butterfly are associated with different scaling factors and relaxation is included into the alignment algorithm to prevent unnecessary over-scaling. In addition, a new decision rule deliberately tuned to input sample data is applied to compute scaling factors. FFTs using both conventional fixed and new distributed scaling algorithms are tested using TI's TMX320C6211 fixed-point DSP processor. The results show that under the new algorithm, the error rate can be considerably reduced, by 3-4 times for 256-point FFT and a jmagnitude order lower for 1024-point FFT, at a cost of increase in memory use and execution time.