Design of pipelined parallel FFT architectures Using folding transformation

Design of pipelined parallel FFT architectures Using folding transformation

RAGAVI.V, K.RENUKA

1. (VLSI Design) Assistant Professor (ECE)

   Srinivasan Engineering College Srinivasan Engineering College

   ragavimevlsi@gmail.com1 renudev20@gmail.com2

   Abstract – In this paper, a novel approach to develop parallel pipelined architectures for the Fast Fourier transform (FFT) is presented. The folding transformation and register minimization techniques are proposed for designing FFT architectures. Novel parallel-pipelined 128-point radix-24 FFT architecture for the computation of complex and real valued fast Fourier transform are derived. For Complex valued Fast Fourier Transform (CFFT), the proposed architecture takes benefit of underutilized hardware in the serial architecture to derive L-parallel architectures not including the increment of hardware complexity by a factor of L. In addition to, the new parallel-pipelined architecture for the computation of Real-valued Fast Fourier Transform (RFFT) is presented. To reduce the hardware complexity, the proposed architecture exploits redundancy in the computation of FFT samples. A comparison is shown between the proposed design and the previous architectures.

   Index Terms Fast Fourier Transform (FFT), folding, radix-24, register minimization.

   1. INTRODUCTION

      DFT is one of the most important tools in the field of digital signal processing. Several Fast Fourier Transform (FFT) algorithms have been developed over the years due to its computational complexity. FFT plays a critical role in modern digital communications such as Digital Video Broadcasting (DVB) and Orthogonal Frequency Division Multiplexing (OFDM) systems. The design of pipelined architectures for computation of FFT of complex valued signals (CFFT) has been carried out. Different algorithms have been developed to reduce the computational complexity, of which Cooley-Tukey radix-2 FFT [1] is very popular.

      Algorithms such as radix-4 [2], split-radix [3] and radix-22 [4] have been developed based on the basic radix-2 FFT approach. The one of the most classical approaches for pipelined

      implementation of radix-2 FFT is Radix-2 multi-path delay commutator (R2MDC) [5]. A standard usage of the storage buffer in R2MDC leads to the Radix-2 Single-path delay feedback (R2SDF) [6] architecture with reduced memory.

      The architectures are developed for a specific-point FFT in [7] and [8], whereas hypercube theory is used to

      derive the architectures in [9].The method of developing these architectures from the algorithms is not well established.

      In additional, most of these hardware architectures are not fully utilized and require high hardware complexity. In the period of high speed digital communications, the high throughput and low power designs are essential to meet the speed and power requirements while keeping the hardware overhead to a minimum. In this paper, a new approach to design the architecture from the FFT flow graphs is presented. Folding transformation [10] and register minimization techniques [11], [12] are used to derive several known FFT architectures.

      If the input samples are real then the spectrum is symmetric and approximately half of the operations are redundant. The applications such as speech, audio, image, radar, and biomedical signal processing, a specialized hardware implementation is best suitable to meet the real- time constraints. The implantable or portable device saves power by using this type of implementation which is a key limitation. Few pipelined architectures for real valued signals have been proposed [13] based on the Brunn algorithm. However, these are not widely used. Different algorithms such as doubling algorithm, packing algorithm have been proposed for computation of RFFT. These approaches are based on removing the redundancies of the CFFT while the input is real. RFFT is calculated using the CFFT architecture in an efficient manner [14].

      In the folding transformation, many butterflies in the same column can be mapped to one butterfly unit. If the FFT size is N, a folding factor of N/2 leads to 2-parallel architecture and in another design, a folding factor of N/4 leads to design 4-parallel architectures in which four samples are processed in the same clock cycle. Various folding sets lead to a family of FFT architectures. Alternatively, known FFT architectures can also be described by the proposed methodology by selecting the appropriate folding set. To reduce latency and the number of storage elements, folding sets are designed. The prior FFT architectures were derived in an informal way, and their derivations were not explained in a systematic way. This is the effort to simplify the design of FFT architectures for arbitrary level of parallelism in an efficient manner by

      Ragavi.V, K.Renuka

      487

      means of the folding transformation. In this paper, the prior design architectures are explained by constructing the specific folding sets. Then new architecture is derived for radix and levels of parallelism and for either Decimation-In- Time (DIT) or Decimation-In-Frequency (DIF) flow graphs. The new architecture achieves full hardware utilization. It may be noted that all prior parallel FFT architectures did not achieve full hardware utilization. The new real FFT architecture is also presented based on higher radices.

      In [15], the parallel-pipelined architectures for the computation of RFFT based on radix-22 and radix-23 algorithms have been proposed. The real FFT architectures are not fully utilized. This drawback is removed by proposed methodology. The novel parallel-pipelined FFT architectures for the real-valued signals with full hardware utilization based on radix-24 algorithm is presented. It combines the advantages of radix-2n algorithms, which requires fewer complex multipliers when compared to radix-

      2 algorithm, with the reduction of operations using redundancy.

      This paper is organized as follows. The folding transformation and register minimization based FFT architectures design is presented in Section II. The proposed architecture for complex FFT is explained in Section III. The proposed architecture for real FFT is explained in Section IV. In Section V, the proposed architecture is compared with the previous approaches and some conclusions are drawn in Section VI.

   2. FFT ARCHITECTURES DESIGN TECHNIQUES

In this section, the folding transformation method and register minimization to derive several known FFT architectures is illustrated in general. The process is described using an 8-point radix-2 DIF FFT as an example. It can be extended to other radices in a similar fashion. Fig. 1 shows the flow graph of a radix-2 8-point DIF FFT. The graph is divided into three stages and each of them consists of a set of butterflies and multipliers. The twiddle factor in between the stages indicates a multiplication by where WN denotes the Nth root of unity, among its exponent evaluated modulo N.

Fig.1 Flow graph of a radix-2 8-point DIF FFT.

This algorithm can be represented as a data flow graph (DFG) as shown in Fig. 2. The nodes in the DFG represent tasks or computations. In this case, all the nodes represent the butterfly computations of the radix-2 FFT

algorithm. Assume nodes A and B have the multiplier operation on the bottom edge of the butterfly. The folding transformation is used on the DFG in Fig. 2 to derive a pipelined architecture.

To transform the DFG, a folding set is required which is an ordered set of operations executed by the same functional unit. Each folding set cntains K entries some of which may be null operations is called the folding factor, i.e., the number of operations folded into a single functional unit. The operation in the jth position within the folding set (where j goes from 0 to K-1) is executed by the functional unit during the time partition. The term j is the folding order, i.e., the time instance to which the node is scheduled to be executed in hardware.

Fig. 2 DFG of a radix-2 8-point DIF FFT.

For example, consider the folding set A = {7, 7, 7, 7, A0, A1, A2, A3} for K=8. The operation belongs to the folding set A with the folding order 4. The functional unit executes the operations A0, A1, A2, A3 at the respective time instances and will be idle during the null operations. The systematic folding techniques are used to derive the 8- point FFT architecture. Consider an edge e connecting the nodes U and V with w (e) delays. The folding equation (1) for the edge e is

DF (U V) = K w(e)-PU + v – u (1)

where PU is the number of pipeline stages in the hardware unit which executes the node U [10]. By using folding sets, folding equations are derived with negative delays (w/o pipeline) and non negative delays (with pipeline or retiming). Consider folding of the DFG in Fig.2 with the folding sets

A = {7, 7, 7, 7, A0, A1, A2, A3}

B = {B2, B3, 7, 7, 7, 7, B0, B1}

C = {C1, C2, C3, 7, 7, 7, 7, C0}.

Assume that the butterfly operations do not have any pipeline stages, i.e, PA=0, PB=0, PC=0.Retiming and/or pipelining can be used to either satisfy DFUV) 0 or determine that the folding sets are not feasible [10]. The negative delays on some edges can be observed. The equations are

DF (A0 B0) = 2 DF (B0 C0) = 1

Ragavi.V, K.Renuka

488

DF (A0 B2) = – 4 DF (B0 C1) = – 6 DF (A1 B1) = 2 DF (B1 C0) = 0 DF (A1 B1) = – 4 DF (B1 C1) = – 7 DF (A2 B0) = 0 DF (B2 C2) = 1 DF (A2 B2) = – 6 DF (B2 C3) = 2 DF (A3 B1) = 0 DF (B3 C2) = 0

DF (A3 B3) = – 6 DF (B3 C3) =1 (2)

The DFG can be pipelined is shown to ensure that folded hardware has non-negative number of delays. The folded delays for the pipelined DFG are

FOLDING SETS

FOLDING EQUATIONS

RETIMING FOLDING EQUATIONS

FOLDED ARCHITECTURE

REGISTER ALLOCATION

LIFETIME ANALYSIS

Fig. 3 Block diagram of FFT design techniques

The technique for minimizing register is lifetime analysis

T input = u + PU (4)

T output = u + PU + maxv {DF (UV)} (5)

where u is the folding order of U and PU is the number of pipelining stages in the functional unit that executes u. From

Tinput Toutput

NODE

(3) the 24 registers are required to implement the folded architecture. Lifetime analysis technique is used to design the folded architecture with minimum possible registers. For example, in the current 8-point FFT design, consider the variables y0, y1,. . . y7, i.e., the outputs at the nodes A0,A1,A2,A3 respectively. It takes 16 registers to synthesize these edges in the folded architecture. The linear lifetime table and lifetime chart for these variables is shown in Fig. 4 and Fig. 5. From the lifetime chart, it can be seen that the folded architecture requires 4 registers as opposed to 16 registers in a straightforward implementation. The next step is to perform forward-backward register allocation.

Fig.4 Linear lifetime table

Fig.5 Linear lifetime chart

Fig. 6 Register allocation table.

From the allocation table in Fig.6 and the folding equations, the final architecture in Fig. 7 can be synthesized and can be derived by minimizing the registers on all variables at once. The hardware utilization is only 50% in the derived architecture. This can also be observed from the folding sets where half of the time null operations are being executed, i.e., hardware is idle. The pipelined parallel FFT architectures are presented by using this methodology.

Ragavi.V, K.Renuka

489

Fig. 7 Folded architecture.

1. PROPOSED ARCHITECTURES WITH COMPLEX INPUTS (CFFT)

   The proposed approach can be described using folding methodology [10].The 4-parallel 128-point FFT architecture can be derived using the following folding sets.

   A = {A0, A1, A2, A3} A = {A0, A1, A2, A3}

   B = {B3, B0, B1, B2} B = {B3, B0, B1, B2}

   C = {C1, C2, C3, C0} C = {C1, C2, C3, C0}

   D = {D1, D2, D3, D0} D = {D1, D2, D3, D1}

   The folded architecture can be derived by writing the folding equation [10] for the edges in the flow graph. The register minimization techniques and the forward and backward register allocation scheme [12] are applied to derive the architecture and then the final architecture can be derived. The 128-point FFT flow graph is based on radix-24 algorithm which is decimated in time. To achieve the high throughput requirement with low hardware cost, both the proposed pipelining method and radix-2n algorithms are exploited in this design.

   The proposed 4-parallel 128-point FFT architecture is shown in fig.8. It consists of two parallel data paths processing two input samples. Each data path consists of seven butterfly units, four constant and two full complex multipliers, delay elements and multiplexers. The function of delay elements and switches is to store and reorder the input data until the other available data is received for the butterfly operation. The four output data values generated after the first stage are multiplied by constant twiddle factors (W18 = eij2/8, W38 = eij23/8). These twiddle factors can be implemented efficiently using Canonic Signed Digit (CSD) approach. The outputs after the third stage are multiplied by the nontrivial twiddle factor.

   128 point CFFT architecture based on radix-24 algorithm

   Another constant multiplier stage is required before the sixth butterfly stage. The CSD complex constant multiplier processes the multiplication of twiddle factors W8, W16, W24, W48. These twiddle factors correspond to cos (/8), sin (/8), and cos(/4).

2. PROPOSED ARCHITECTURE WITH REAL INPUTS (RFFT)

The proposed radix-24 4-parallel architecture is explained using N = 128 point FFT is shown in fig.9. Further, the folding sets can be modified to derive L-parallel architectures of any N-point RFFT.

Fig.8 Proposed

The radix-24 algorithm is described in detail in [8]. We can modify the flow graph similar to the other radices. The advantage of radix-24 algorithm is that it needs only one full multiplier every four stages. To derive the 4-parallel architecture divides the nodes into two groups. The nodes in the same group are processed by the same computation unit. Consider the following folding sets.

A = {A0, A2, A4, A6} A = {A1, A3, A5, A7}

B = {B1, B3, B0, B2} B = {B5, B7, B4, B6}