Schemes for Resource-Efficient Generation of Twiddle Factors for Fixed-Radix FFT Algorithms
Abstract
Keith Jones
The paper describes schemes for the resource-efficient generation of twiddle factors for the fixed-radix version of the ubiquitous fast Fourier transform (FFT) algorithm. The schemes, which are targeted at a parallel implementation of the FFT, provide one with the facility for trading off arithmetic complexity, as expressed in terms of the required numbers of multiplications and additions (or subtractions), against the memory requirement, as expressed in terms of the amount of random access memory (RAM) required for constructing the look-up tables (LUTs) needed for the storage of the two twiddle factor components – one component being derived from the sine function and the other from the cosine function. Examples are provided which illustrate the advantages and disadvantages of each scheme – which are very much dependent upon the length of the FFT to be computed – for both the single-level and multi-level LUTs, highlighting those situations where their adoption might be most appropriate. More specifically, it is seen that the adoption of a multi level LUT scheme may be used to facilitate significant reductions in memory – namely, from O(N) to an O(β√N) requirement, for the case of an N-point FFT, where β ≥ 2 corresponds to the number of distinct angular resolutions used – at a relatively small cost in terms of increased FFT latency and arithmetic complexity.