Content area
Full Text
Proposed is a low-complexity twiddle factor multiplication structure for fast Fourier transform (FFT). In an FFT implementation, the twiddle factor multiplication requires a large ROM to store the twiddle factors. In the proposed structure, the ROM is partitioned into two small ROMs, whose sum of areas is much smaller than that of the original ROM. The proposed structure requires an additional multiplier, but the multiplier is shown to be small in the experimental results. The results show that the proposed structure reduces the area of the twiddle factor multiplication by around 30% with a marginal degradation in SQNR performance.
(ProQuest: ... denotes formulae omitted.)
Introduction: Fast Fourier transform (FFT) is one of the most widely used signal processing algorithms. FFT is a key function of orthogonal frequency division modulation, which is the basis of many modern communication standards. The mathematical operation of FFT consists of the butterfly operation and the twiddle factor multiplication. The butterfly operation consists of an adder and a subtractor, and the twiddle factor multiplication requires a complex multiplier and a ROM to store the twiddle factors. The area of the twiddle factor multiplication, therefore, is much bigger than that of the butterfly operation.
This Letter proposes a scheme to reduce the area of the ROM in the twiddle factor multiplication. In the proposed structure, the ROM is split into two small ROMs: a coarse ROM and a fine ROM. The coarse ROM has intermittently located twiddle factors while the fine ROM carries factors to complement the spacing of the coarse ROM twiddle factors. The original twiddle factor multiplication is performed by multiplying the two twiddle factors. The number of ROMs is increased from one to two, but a small amount of the fine ROM substitutes for a large amount of the coarse ROM, decreasing the total bit amount of ROMs. The number of multipliers also increases, but the multiplier for the fine ROM factors will be shown to be small compared to the saved ROM area. The experimental results show that the SQNR degradation is insignificant.
Twiddle factor multiplication: FFT for N points is a signal processing algorithm to convert N time domain signal samples to N frequency domain samples [1]. The FFT calculation consists of a butterfly operation...