A Comparative Analysis of CORDIC-Based versus LUT+Multiplier-Based Schemes for Parallel Computation of Radix-4 FFT Dragonfly

Introduction

The aim of this paper is to provide an analysis of the relative complexities, as expressed in terms of arithmetic and trigonometric memory requirements, of three different solutions for the parallel computation of those arithmetic tasks needing to be performed by the fixed-radix fast Fourier transform (FFT) algorithm’s computational unit, denoted CU_R for the radix-R version of the algorithm [1,2]. The FFT refers to a class of algorithms that provide a fast means of computing the discrete Fourier transform (DFT) algorithm, with CU_R being the computational engine used for carrying out the radix-R algorithm’s repetitive arithmetic operations resulting from its recursive structure [3]. The DFT, for the case of a length-N transform, may be expressed in normalized form via the equation

the primitive N^th complex root of unity [4]. The complex-valued exponential terms, W N^nk , as derived from the complex root of unity, each comprise two trigonometric components, one sinusoidal and the other cosinusoidal, with each pair being more commonly referred to as twiddle factors [1,2]. These terms, for the case of a radix-R transform of length N, whereby

                      N = R^E                                                   (3)

for some positive integer exponent E, are required to be fed, R at a time, to CU_R, although only R-1 of the twiddle factors are non-trivial as the first twiddle factor is trivial with a fixed value of one. Given the recursive nature of the fixed-radix FFT, it is clear that knowledge of the complexity of CU_R, as is sought here, leads directly to the complexity of the associated FFT algorithm, as the radix-R FFT can be shown to involve the execution of CU_R a total of (N/R)×log_RN times – that is, the algorithm comprises log_RN temporal stages where the processing for a given stage cannot commence until that of its predecessor has been completed and where each stage involves N/R instances of CU_R [5].

The complexity of CUR is to be measured in terms of: 1) the arithmetic component, as expressed in terms of the required numbers of adders and multipliers, and 2) the trigonometric memory component, which concerns the storage of a limited range of a sampled sine (or, equivalently, cosine) function, via the construction and maintenance of one or more suitably defined look-up tables (LUTs), from which the real and imaginary components of the twiddle factors – as required for the operation of CU_R – may be derived. The first two solutions are conventional, being based upon recently published results which involve the use of different combinations of LUTs, adders and multipliers [6,7]. The third solution takes a non-conventional approach, being based upon the use of multiple pipelined COordinate Rotation DIgital Computer (CORDIC) arithmetic units – with each unit involving the use of its own adders, together with bit-shifters and constant multipliers (that is, where each multiplier possesses one fixed multiplicand) – combined with additional adders [8-10]. This solution effectively eliminates the reliance on LUTs which, for those big data applications involving the use of very-long (of O(10⁶ ), say, as might be encountered with processing of wideband signals embedded in astronomical data) to ultra-long (of O(10⁹ ), say, as might be encountered with processing of ultra-wideband signals embedded in cosmic microwave data) transforms, might otherwise prove prohibitively costly in terms of fast on-chip memory.

The assessment of the three solutions is to be based upon a highly-parallel implementation of a single CU_R, where R is equal to four, denoted CU4 and chosen for ease of analysis and illustration, this including the associated trigonometric memory requirement. The chosen computing device is to be based upon silicon-based technology as typified by the field programmable gate array (FPGA) [11]. The dominant operator used by CU_R in the hardware implementation of most conventional FFT solutions is that of the complex multiplier (or, more commonly, multiplier-accumulator), which may be performed in one of two ways, using: 1) four real multipliers, with these being followed by two real adders, or 2) three real multipliers, with these being preceded by two real adders and followed by three real adders. Given the emphasis on minimizing the amount of silicon resources required for such an implementation, and that the orders of complexity for the multiplier and adder are given by O(L²) and O(L), respectively, where L is the word length, the second three-multiplier version is to be the solution of choice.

Thus, following this introductory section, the paper continues in Section 2 with a brief discussion of the complexity of the computational building blocks required by those arithmetic tasks needing to be performed by CU₄. This is followed in Section 3 by an account of the two conventional solutions based upon the use of different combinations of LUTs, adders and multipliers – noting that the adoption of second-order recursion by one of the solutions also depends upon the use of just adders and multipliers. Section 4 then derives the basic CORDIC algorithm as required for the specific operating mode of phase rotation, as is of interest here, whilst Section 5 uses the CORDIC approach to derive an alternative non-conventional solution to the parallel computation of CU₄ based upon the use of three pipelined CORDIC arithmetic units. This is followed in Section 6 with a comparison of the relative complexities of all three solutions for various combinations of transform length and word length, with a summary and conclusions provided in Section 7.

Complexity of Computational Building Blocks -Arithmetic and Memory

The main problem to be addressed in this paper is concerned with the generation and application of the non-trivial twiddle factors by CU4. In assessing the associated complexity it is first proposed that L-bit fixed-point processing and a transform length of N should be adopted, where N >> L. Also, for ease of analysis and illustration, it is proposed that a somewhat simplistic measure of the required resources be adopted whereby the size of each arithmetic operator and storage location is expressed in terms of the required numbers of programmable logic slices – although the adoption of embedded functions, as provided by the device manufacturer, would be expected to provide more highly optimized results. This is achieved by making the following assumptions:- that 1) each real adder requires L/2 slices; 2) each real multiplier requires a (worst-case) figure of L2 slices; so that as a consequence, 3) each complex multiplier, expressed as the combination of three real multipliers and five real adders, requires a (worst case) figure of 3L2+5L/2 slices; 4) each constant real multiplier requires L slices; 5) each bit-shifter, assumed hard-wired when shift lengths may be predetermined (as is the case for the pipelined CORDIC arithmetic unit to be discussed in Sections 4 and 5), requires negligible resources when compared to that of a conventional barrel shifter; and 6) each word of trigonometric memory (assumed here to be of dual-port type for the simultaneous access of both sine and cosine components) requires L slices [11].

Note that the data memory, as required for the storage of the length-N complex-valued data sets, will be the same (aside from any double-buffering requirement for the simultaneous construction and processing of data sets) for all of the solutions considered whilst the control logic requirement will be assumed, for ease of analysis, to be of comparable complexity for all such solutions. Therefore, their contributions, as with the hard-wired bit-shifters, will not be included in the complexity results discussed in this paper – although the contribution of the data memory requirement will be crucial in assessing the complexity and viability of different solutions (and, in particular, of their computing architectures) to the associated FFT, particularly for big-data applications.

In assessing the relative complexities of the three solutions discussed here, for various combinations of transform length and word length, a parallel solution is to be assumed, whether that parallelism is achieved in the spatial domain, through the adoption of single-instruction multiple-data (SIMD) type processing [12], or the temporal domain, through the adoption of pipelined processing [12], or through a combination of the two. Each arithmetic operation is to be assigned its own hardware operator and each CU₄ (or set of CU₄’s) its own processing element (PE) containing the required hardware operators, with all the twiddle factors being produced and made available for input to CU₄ simultaneously, together with those samples of complex-valued data with which the twiddle factors are to be appropriately combined. Also, although the arithmetic operators and trigonometric memory are expressed in terms of real operators and real words, respectively, the arithmetic is assumed to be of fixed-point type so that the operators are actually assumed to be performing upon L-bit integers.

Summary of Recent Results Obtained for Fixed-Radix FFT Algorithm

For the most commonly adopted FFT radices, namely those with values of two or four, CU_R is more commonly known as a butterfly or dragonfly, respectively, this naming being due to the fact that the data within the resulting computational structures flow in a pattern that resembles that of the wings of the corresponding insect, respectively [1,2,5]. The structure of CU_R, in each case, is regular and relatively simple, so that the choice of the computationally-efficient radix-4 FFT dragonfly, CU₄, as the preferred algorithm seems a sensible one to make – see Figures 1 and 2 which depict the dragonfly’s signal flow graph for the decimation-in-time (DIT) and decimation-in-frequency (DIF) versions of the radix-4 algorithm, with digit-reversed (DR) input/output addresses being adopted, respectively [1,2]. Generalization of the complexity results follows in an obvious fashion to the case of CUR, for the radix-R FFT, where R is an arbitrary positive integer. The PE corresponds, therefore, to the hardware required for a highly parallel implementation of a single dragonfly, this including the trigonometric memory requirement needed for its operation – noting that with FPGA technology, the memory is typically available in the form of random access memory (RAM) which, for fast access, needs to be placed on the same device as is used for the processing where it is typically referred to as ‘fast RAM’ [11].

Figure 1: DIT version of radix-4 FFT dragonfly with DR-reordered inputs

Figure 2: DIF version of radix-4 FFT dragonfly with DR-reordered outputs

Scheme for Minimizing Dragonfly’s Arithmetic Complexity

The task of this first solution, referred to hereafter as Solution I, which is based upon recently published results for efficient twiddle factor generation, involves the combined task of the parallel generation and application of the trigonometric components of the three non-trivial twiddle factors, using the single quadrant scheme which covers an angular region of 0 to π/2 radians, combined with adders and multipliers [7]. This approach, for the case of a length-N transform, involves the assigning of a one-level LUT, of length N/4, to each non-trivial twiddle factor, enabling all three LUTs to be accessed in parallel in the spatial domain in SIMD type fashion, as illustrated in Figure 3, to facilitate the parallel operation of the PE at minimal cost in terms of arithmetic complexity. Thus, the generation component of the solution – which is ideally suited to most applications which require the use of short to long (that is, up to O(10³ ), say) transforms – involves an additive complexity of

Figure 3: SIMD architecture for generation of dragonfly twiddle factors using single-level LUTs

Scheme for Minimizing Dragonfly’s Trigonometric Memory Requirement

The task of this second solution, referred to hereafter as Solution II, which like the first solution is based upon recently published results [7] for efficient twiddle factor generation, involves the combined task of the parallel generation and application of the trigonometric components of the three non-trivial twiddle factors using a two-level LUT and second-order recursion combined with additional adders and multipliers (that is, apart from the recursion’s own adders and multipliers). This approach, for the case of a length-N transform, involves the use of a two-level LUT comprising three single-level LUTs, each of length– one defined over a coarse-resolution region and two (one for each of the sine and cosine components) defined over a fine-resolution region – for the generation of the first non trivial twiddle factor, and second-order recursion for the generation of the second and third non-trivial twiddle factors. The computation may be carried out in parallel fashion, in the temporal domain, via the use of a suitably defined computational pipeline, as illustrated in Figure 4, at minimal cost in terms of memory.

Figure 4: Pipeline architecture for generation of dragonfly twiddle factors using two-level LUT and second-order recursion

For the first non-trivial twiddle factor, the trigonometric formulae required for the addressing of the two-level LUT may be derived in a straightforward manner from the standard two-angle identities

Figure 5: Decomposition of single quadrant of cosine function into coarse-resolution & fine-resolution angular regions using two single-level length-4 LUTs

Discussion

The two conventional dragonfly solutions discussed in this section are based upon recently published results [6,7] which highlighted the relative merits of different schemes – using different combinations of single-level and multi-level LUTs, second-order recursion, adders and multipliers – for the efficient parallel generation, but not the application, of the non-trivial twiddle factors for the fixed-radix version of the FFT. These are just two possible solutions to the problem, however, as other combinations of LUTs, adders and multipliers could also be used at comparable cost to achieve similar results. Of the two solutions considered, Solution I sought to minimize the arithmetic complexity at the expense of an increased memory requirement, whilst Solution II sought to minimize the memory requirement at the expense of increased arithmetic complexity – noting that the recursion itself involved the use of just adders and multipliers. The attraction of the second solution, compared to the first, is evident when the transform length is sufficiently large and/or the on-chip storage capacity limited, this being due to the relative Oand O(LN) complexities (including word length L due its relevance in describing complexity of CORDIC solution in Section 5) of their trigonometric memory requirements.

An Alternative Approach to Solving Problem of Phase Rotation

The previous two solutions have possessed complexities that are based upon the use of one or more LUTs, together with second-order recursion for one of the solutions, plus additional adders and multipliers, which taken together – depending upon the size of the transform – might prove prohibitively expensive in terms of the resulting silicon area. The third solution, as will be described in some detail in Section 5, will illustrate how the reliance upon the use of potentially costly LUTs may be effectively eliminated. Unlike the other two solutions, it will no longer involve having to perform two separate tasks, namely: 1) the generation of the trigonometric component pairs of the non-trivial twiddle factors, followed by 2) their multiplicative application to the complex-valued data samples, but will instead use: 3) multiple pipelined CORDIC arithmetic units which apply the phase rotations corresponding to the complex twiddle factor multiplications, piece-by-piece and in an iterative fashion – which, for a pipelined implementation, needs to be fully unfolded – whilst those pieces, which each correspond to a small-angle rotation, are actually being computed. The generation and application stages are thus carried out simultaneously, with the memory requirement being reduced to that required for the storage of a small number of angles, consistent with the word length, as required for execution of the small-angle rotations.

The Basic CORDIC Algorithm

As already stated, the basic operation of the fixed-radix FFT is essentially that of phase rotation arising from multiplication of the data by the associated twiddle factors, making the choice of the CORDIC algorithm an obvious candidate for consideration as the chosen arithmetic unit. The original version of the algorithm, as introduced by Volder [10], may be expressed as

Suppressing the application of the multiplicative terms in this way must subsequently be corrected for, however, in order that the correct L-bit results should be obtained. To achieve this, it is required that after all L multiplication-free iterations have been completed, the multi-term product KL – which may be pre-computed and stored in binary form once the value of L has been decided upon and performed as a number of shift-and-add operations – needs to be applied to both the real and the imaginary components of each of the rotated outputs, so that when all of the dragonfly inputs have been processed there will be consistency between the output levels produced by the application of both the trivial and the non-trivial twiddle factors to the respective data samples. An alternative and lower-complexity approach to achieving this consistency in the output levels is possible, however, as will be discussed in the next section.

Discussion

Much work has been carried out on the development of the CORDIC algorithm since the original paper of Volder [10] and, in particular, in extending the number of: 1) algorithmic variations of the CORDIC algorithm so as to cater, for example, for higher radices that are able to handle more than just {-1,+1} or {-1,0,+1} as defining the range of possible values for the ‘sense’ parameter used by the non-redundant and redundant versions of the algorithm [8,14,15], respectively, which enables the number of iterations (and thus the latency of the solution) to be commensurately reduced but at the expense of a non-constant scale factor; as well as 2) possible applications, such as those involving signal and image processing, communication systems, robotics or 3D graphics [16], that are able to exploit and benefit from the computational attraction, in terms of flexibility, versatility and simplicity, of the CORDIC approach. These advances, combined with the provision of highly-optimized CORDIC arithmetic units (typically as IP cores) by most major FPGA manufacturers, make the CORDIC algorithm as relevant today as when it was chosen for use with the first generation of pocket calculators, as emerged from the introduction of the semiconductor industry in the early 1960s.

Scheme for Eliminating Dragonflys Trigonometric Memory Requirement

The previous section has shown how CORDIC arithmetic may be effectively applied to the problem of phase rotation, as is required when multiplying data samples by twiddle factors within CUR, reducing each problem from that of a single rotation to a number of small-angle rotations, each of which may be carried out in hardware using simple adders and hard-wired bit-shifters. For this third solution, referred to hereafter as Solution III, it is now seen how a non-conventional CORDIC-based implementation of the radix-4 FFT dragonfly, CU4, may be straightforwardly obtained at zero cost in terms of trigonometric memory. This is achieved with three pipelined CORDIC arithmetic units combined with additional adders (that is, apart from its own adders) for dealing with the dragonfly’s remaining two stages of pre/post (according to choice of decimation scheme) additions.

Application of CORDIC Arithmetic Unit to Radix-4 FFT Dragonfly

Precision and Accuracy Considerations

Assuming the adoption of L multiplication-free iterations, each carrying out a small-angle rotation for each of the three non-trivial twiddle factor rotation angles, the scheme achieves approximately L-bit accuracy, with each additional iteration – which involves the maintaining and updating of nine parameters – as already stated, producing approximately one extra bit of accuracy in the rotated result. With each operation being assigned its own hardware operator, a pipelined implementation requires a total of nine adders and six hard- wired bit-shifters, for each stage, together with the storage of the set of L small rotation angles, , as required for the updating of the cumulative estimates of the corresponding twiddle factor rotation angles. To deal with possible word growth incurred during the CORDIC operation, a number of guard bits are typically adopted, with L iterations requiring approximately
additional bits in order to prevent overflow and to maintain precision to the desired level.

Upon completion of all L multiplication-free iterations, the required L-bit accuracy may be achieved by having the multi-term product KL applied to each of the three complex-valued outputs (involving six real-valued components), this involving the use of six constant multipliers. Alternatively, rather than applying the multi-term product to the rotated outputs obtained from the application of the non-trivial twiddle factors, the complex-valued output obtained from using the trivial twiddle factor (involving two real-valued components) could instead be modified by means of the inverse version of the multi-term product of Eqtn. 33, namely:

                             Gn=1/Kn                                                       (44)                                                                                                                                                                                                                      

(which, as ‘n’ is increased, tends to a value of 1.64676026 to eight decimal places), with ‘n’ set to a value of L, which would involve the use of just two constant multipliers, rather than six. In this way, each of the four complex-valued outputs on completion of the rotation operation would be in error by a multiplicative factor equal to that of the multi-term product, GL, the effects of which may subsequently be corrected for, together with any naturally occurring word growth, after each of the log4N temporal stages of FFT dragonflies. This correction could be achieved by means of a suitably defined scaling strategy, such as that of the block floating point scheme, for example, as would typically be required by any fixed-point implementation of the fixed-radix FFT algorithm (regardless of the choice of arithmetic unit) for dealing with word growth and thus for maintaining accuracy [17].

Complexity of CORDIC-Based Solution

components this contribution, as with that of the hard-wired bit-shifters, is taken to be negligible.

Discussion

With the CORDIC-based solution described here there is no longer a requirement to construct and maintain potentially large LUTs for the storage of the twiddle factors and that for the operation of phase rotation the CORDIC approach may be considered as being close to optimal in achieving high precision and fast convergence for minimum cost in terms of hardware resources. Such an approach possesses the attraction of great versatility, as the arithmetic unit can be designed to range from being: 1) very small, in terms of silicon area, through the adoption of a slow, iterative, purely sequential solution, to 2) very fast, in terms of throughput, via the adoption of a fully pipelined version of the unfolded solution. With regard to its efficient implementation, the use of conventional barrel shifters for carrying out the bit-shifting would involve both high complexity and high latency, whereas that of hard-wired bit-shifters, as has been proposed here, results in negligible cost, lower latency and higher throughput. As a result, the complexity of the radix-4 FFT dragonfly, CU4, is dominated by the adder requirement of Eqtn. 45, with the constant multipliers, in comparison, making a negligible contribution.

Note that the version of the CORDIC algorithm discussed here is referred to in the literature as being non-redundant due to the fact that by setting the value of each dn to either +1 or –1, each small rotation angle is always applied according to the associated sense, even if it is not absolutely necessary to do so – that is, if it produces a less accurate estimate than the previous iteration. An alternative version of the algorithm, referred to as being redundant, allows the value of dn to be set to 0, as well as +1 or -1, so that specific small rotation angles may, if necessary, be ignored. As a result of this distinction, the latency of a pipelined implementation of the redundant version of the CORDIC algorithm may vary according to the value of the original rotation angle whereas the non-redundant version possesses the attractive property that the latency is fixed, being independent of the original rotation angle. Clearly, when multiple pipelined CORDIC arithmetic units are required to operate in parallel, it is essential that they should possess the same latency in order to ensure synchronization, otherwise angle dependent delays might be needed to ensure that their outputs are simultaneously available for subsequent processing.

Complexity Comparison of All Three Solutions

Adopting the silicon-based complexities of the computational building blocks, as introduced in Section 2, the overall sizing of Solution I for the case of a single highly-parallel FFT dragonfly, CU₄, based upon the use of single-level LUTs combined with adders and multipliers, may be expressed as

The complete set of complexity results are as listed in Tables 1 and 2, for various combinations of transform length and word length, these being based upon a highly parallel implementation of a single PE performing the radix-4 FFT dragonfly, CU₄, using programmable logic slices – although it is anticipated that the relative advantages/disadvantages of each solution would apply equally when implemented using the highly optimized embedded functions made available by the device manufacturer. Of the two conventional solutions discussed, Solution I sought to minimize the arithmetic complexity at the expense of an increased memory requirement, whilst Solution II sought to minimize the memory requirement at the expense of increased arithmetic complexity. The complexity of Solution III, unlike that of the other two solutions, is dependent upon the word length but independent of the transform length so that the solution, as well as looking attractive for the short-to-long transforms, looks increasingly attractive as the transform length is increased. Thus, for those big-data applications where resources, such as fast RAM for the trigonometric memory, may be limited, the trivial memory requirement of the CORDIC-based approach makes it look particularly attractive in terms of reduced silicon area. With Solutions I and II, when the memory requirement is sufficiently large, it is possible that slower off chip memory might well be needed to supplement the on chip RAM which could, as a result, lead to potential timing issues.

Table 2: Complexity for length-N radix-4 FFT dragonfly with L-bit fixed-point processing (control logic & hard-wired bit-shifters not taken into account)

Note, finally, that the complexity of the associated radix-4 FFT would clearly be dependent upon the chosen computing architecture, whether to be based, for example, upon the adoption of 1) a scalable memory-based architecture, involving the repeated execution of a single highly parallel PE exploiting fine-grain parallelism via the use of spatial-domain and/or temporal domain techniques; or 2) a pipelined architecture, exploiting coarse-grain parallelism via the simultaneous execution of multiple PEs – for the radix-R case, this would entail the use of logRN such PEs, one per stage, with each stage catering for N/R dragonflies. Double buffering of some kind would probably be needed in each case in order to prevent the occurrence of unnecessary delays in the processing, With these and other hybrid approaches, each would have its own merits according to the values of the various parameters involved, such as that of transform length and word length, as well as to the constraints of the particular application, such as update period, clock frequency, power budget, memory capacity (in the form of fast RAM), etc. With regard to the actual PE, it should be noted that with an arbitrary radix, R, a total of R-1 non trivial twiddle factors would need to be generated and applied to the corresponding data set. This suggests, not surprisingly, that the larger the radix, the greater the amount of parallelism that might be exploited by the individual PE given a suitably chosen FFT computing architecture combined with a suitable PE design.

Summary and Conclusions

This paper has analyzed the relative complexities, as expressed in terms of arithmetic and trigonometric memory requirements, of three different solutions to the parallel computation of those arithmetic tasks needing to be performed by the radix-4 FFT dragonfly, CU₄, for different combinations of transform length and word length. The two conventional solutions were based upon the combined use of LUTs, adders and multipliers: Solution I, employing three single-level LUTs combined with adders and multipliers, sought to minimize the arithmetic complexity at the expense of an increased memory requirement, whilst Solution II, employing a two-level LUT and second-order recursion combined with additional adders and multipliers, sought to minimize the memory requirement at the expense of increased arithmetic complexity. Solution III took a non-conventional approach, being based upon the use of three pipelined CORDIC arithmetic units combined with additional adders and had a complexity, unlike that of the other two solutions, that was dependent upon the word length but independent of the transform length, effectively eliminating the trigonometric memory requirement at the expense of an increased number of adders. These properties follow directly from the derived complexity results which stated that Solution I possesses O(LN) complexity,Solution II  complexity and Solution III O(L² ) complexity, where N >> L, with the results generalizing in an obvious fashion to the case of CU_R, for the radix R FFT, where R is an arbitrary positive integer. Thus, the results of the study have shown, in particular, that the CORDIC-based approach of Solution III looks increasingly attractive as the transform length is increased, especially for those big-data applications where resources, such as fast RAM, may be limited. The solution relies upon the use of a potentially large number of adders, however, so that the key to an efficient implementation of Solution III being realized – assuming the CORDIC unit is designed from ‘scratch’ as opposed to being a highly-optimized IP core, as made available by the device manufacturer – is that a hardware efficient adder design should be identified that’s able to effectively exploit the properties of silicon based technology as typified by the FPGA [18,19].

Conflicts of Interest: The author, having been retired for some years, has no access to funding of any kind and states that there are no conflicts of interest associated with the production of this paper.

References