International Journal of Electrical and Electronic Engineering & Telecommunications Vol. 8, No.

3, May 2019

Fast Performance Pipeline Re-Configurable FFT

Processor Based on Radix-22 for Variable Length N
Manish Bansal and Sangeeta Nakhate
MANIT EC Department, Bhopal, India
Email: {manishbansal2008; sanmanit}@gmail.com

Abstract—This paper proposes fast performance A reconfigurable computational scheme has attracted
reconfigurable pipeline variable points FFT processor many researchers [2]. Hardware acts as a general
design. This design is proposed for variable N points whose hardware solution for implementing a variety of different
values can be 8, 16, 32, 64, 128, 256 and 512 sample points.
computation within or across application domains which
Hence, the proposed reconfigurable design can be used for
different points OFDM applications rather using different require performing FFT of length N. Implementing each
designs. The proposed implementation design uses Radix-22 FFT on dedicated IP is an overhead in silicon area of the
Common Factor Algorithm (CFA) algorithm and SDF chip. The novel approach is used to design variable
architecture. Radix-22 CFA algorithm reduces the number length FFT processor to utilize the OFDM transmission.
of twiddle factors compared to Radix-4 and Radix-2 and Some of the approaches to design FFT are memory-based,
utilizes Radix-2 butterfly structure whose complexity is very pipeline-based and general-purpose DSP. Memory based
low. SDF architecture uses less memory and utilizes is most area efficient but it needs many computation
multipliers fully compared to others. The frequency of
proposed design is varied with the FFT points N. The
cycles. Pipeline based architecture possesses regularity,
proposed design is synthesized successfully using XST of modularity, local connection and high throughput rate
Xilinx ISE 14.1 and simulated using ModelSim & MATLAB with a lower clock frequency.
tool to verify results. Synthesized results of the proposed All implementations of FFT can be designed with
design for 512 points are 155.9 MHz max frequency, slice different pipelined architectures - SDF (single path delay
used 1795, slices Flip Flops used 1028 and LUTs used 3335 feedback), MDC (multipath delay commutator), and SDC
which are approximately 37% higher, 35%, 19%, 27% (single path delay commutator) architectures. The single
lesser in ratio than convention FFTs.  path delay feedback structure is more suitable than
Index Terms—FFT, Radix-22 CFA, complex multiplier, SDF, multipath delay and single path delay commutator
OFDM architecture as: -
1) The SDF architecture is very convenient to
implement the different length FFT.
I. INTRODUCTION 2) The number of the required registers in SDF
The Fast Fourier Transform (FFT) has been identified architecture is lesser than that in MDC and SDC
as a widely used algorithm in orthogonal frequency structures [3].
division multiplexing systems. Therefore, Fast Fourier The controller of proposed FFT design is easier than
transform is a fundamental building block used in DSP the other structures as overall architecture and all
systems, with applications ranging from OFDM based components are controlled by count clock signal only.
Digital Modems, to Ultrasound, CT Image and RADAR This proposed research presents the implementation of
algorithms as shown in Fig. 1. OFDM is a very flexible reconfigurable FFT for variable length N which can be
and efficient modulation technique to transmit data used for 8, 16, 32, 64, 128, 256 and 512 points instead
reliably on high transmission in the wireless and wire using the different processor for different point’s
systems such as ADSL, IEEE802.11a, WPAN, WLAN applications. The radix impacts FFT processor. A small
and DVB-T [1]. FFT Implementation technique is fast radix increases the count of twiddle factors and states
and efficient than other techniques. simple structure of butterfly. A higher radix reduces the
count of twiddle factors and states complex structure of
butterfly. In the proposed processor, Radix-22 uses lesser
twiddle factors compared to Radix-4, and butterfly
structure based on Radix-2 that is the simplest structure.
This paper is structured as follows. Section II describes
Fig. 1. Receiver OFDM transmission block diagram. the proposed reconfigurable algorithm for variable length
FFT. Section III describes the architecture of proposed
Manuscript received April 7, 2018; revised October 25, 2018; reconfigurable Radix-22 FFT processor for different
accepted October 25, 2018. points. Section IV describes the comparison and the
Corresponding author: Manish Bansal (manishbansal2008@
gmail.com). conclusion is given in the last section.

©2019 Int. J. Elec. & Elecn. Eng. & Telcomm. 163

doi: 10.18178/ijeetc.8.3.163-170
 International Journal of Electrical and Electronic Engineering & Telecommunications Vol. 8, No. 3, May 2019

II. PROPOSED RECONFIGURABLE ALGORITHM FOR The common factor algorithm (CFA) form [4]:
VARIABLE LENGTH FFT ( N 4) 1 1 1
N N 
The Radix-22 Common Factor Algorithm (CFA) and X  k1  2k2  4k3  =    x  n1  n2  n3 WNnk
n3  0 n2  0 n1  0  2 4 
butterfly structure are used to implement the variable
length FFT processor. Thus, the proposed processor is ( N / 4) 1 1 1
N N 
designed in such a way that it works for 8, 16, 32, 64, 128, =    x n1  n2  n3  
512 points FFT calculation. The Proposed processor is n3  0 n2  0 n1  0  2 4 
implemented in pipeline single path delay feedback N N 
 n1  n2  n3  k1  2 k2  4 k3 
structure that is more convenient structure and reduces WN 2 4 
(4)
the FFT processor's complexity. Each FFT stage consists
of butterfly structure. In this section, Radix-22 common The twiddle factor can be expressed as
factor algorithm, components, and the proposed FFT N N 
reconfigurable processor are described for variable length.  n1  n2  n3  k1  2 k2  4 k3 
WNnk =WN 2 4 
The definition of Discrete Fourier Transform (DFT) of (5)
= (1) ( j ) (1)n1k2 WNn3 ( k1  2 k2 )WNn3/k43
n1k1 n2 k1
size N is defined as [4]: -
BU PE BU PE
N 1
X  k    x  n WNnk 0  k  N (1) where n1, n2, and n3 are the index terms of the input sample
n 0 n and k1, k2, and k3 are the index terms of the output
where the twiddle WNnk is defined as
factor sample k. (1)n1k1 and (1)n1k2 are butterfly elements.
exp( j 2 nk / N ) and N represents the length of the
( j )n2 k1 and WNn3 ( k1  2 k2 ) are processing elements.
sequence to be transformed. n is time domain ordinal. k is
The detailed structure of the proposed pipeline Re-
frequency domain ordinal. The Radix-22 algorithm is
configurable FFT processor based on Radix-22 for
expressed using a common factor algorithm and 3-
variable length N is shown Fig. 2 that retains the Log2N
dimensional index mapping. The Radix-22 algorithm for
number of stages. Shift register (SR) stores values. For N
N points is presented as [5].
points, the 1st shift register stores N/2 values, the 2nd shift
Applying divide and conquer 3-D liner index mapping:
register stores N/4 values, the 3rd shift register stores N/8
N N values, so on and last shift register stores one value.
n n1  n2  n3 (2) Twiddle generator produces twiddle factors per
2 4
k  k1  2k2  4k3 (3) WNn3 ( k1  2 k2 ) based on n3, k1 and k2 values. Swapper
( j )n2 k1 swaps signed real value and imaginary value
where N = 8, 16, 32, 64, 128, 256 and 512.
then invert the sign of swapped imaginary value.
n1 , n2  0,1 and n3  0,1,  
, N 22  1 Butterfly structure adds, subtracts and bypasses two input
values. A complex multiplier multiplies twiddle factor
k1 , k2  0,1 and k3  0,1, ,  N 2  1
2
value with input complex value

Fig. 2. Structure of the proposed reconfigurable FFT for N points.

Fig. 3 shows a signal flow graph (SFG) of the calculations are based on n1, n2, n3, k1, k2, k3 which are
proposed reconfigurable Radix-22 FFT processor. It is to calculated as per N-points. Similarly, next two stage
be noted that inputs are in normal order and outputs are in calculations are based on n1, n2, n3, k1, k2, k3 which is
permuted (bit-reversed) order of inputs. First two stage calculated as per N/4-points and so on. First stage

©2019 Int. J. Elec. & Elecn. Eng. & Telcomm. 164

 International Journal of Electrical and Electronic Engineering & Telecommunications Vol. 8, No. 3, May 2019

performs the operation between the nth and the (n+N/2)th Fig. 5 Trivial (–j) multiplier performs swapping of real
points with butterfly structure, next stage performs the imaginary values and sign inversion of real value. The
operation between the (n+N/2)th and the (n+N/4)th points signal ‘S’ controls this swapping and the 2nd compliment
and so on. This process runs continuously up to last stage invert real value sign. Whenever (–j) multiplication is
log2N which performs the operation between the 1st and
required as per swapper ( j )n2 k1 value, multiplexers
the 2nd point, the 3rd and the 4th point and so on.
Mux1 and Mux2 switch to ‘1’ then real value sign is
inverted and imaginary signed value is swapped to real
and inverted real signed value is swapped to imaginary.
In this way, instead of doing (–j) multiplication,
swapping & sign inversion is done. This approach
enhances the frequency and reduces the logic and
hardware.

III. ARCHITECTURES OF PROPOSED RECONFIGURABLE

RADIX-22 FFT PROCESSOR FOR DIFFERENT POINTS
The proposed FFT processor is designed in such a way
that it automatically gets configured for variable points
FFT. As shown in Fig. 2, all components - BFs, Stages,
SRs, Twiddle generators, and Swappers are configured
automatically based on the value of N and all operations
are controlled by counter signal. Here the proposed
reconfigurable FFT processor is designed based on the
symmetry of different points FFTs that can be used for 8,
16, 32, 64, 128, 256, 512 points FFT instead of using
Fig. 3. SFG of the proposed reconfigurable FFT for N points. different length FFT processors for different applications.
Table I shows components used in the proposed
Fig. 4 states the structure of butterfly (BU) that reconfigurable FFT design for variable points. As the
performs the calculation between the nth and the (n+ value of N is provided, the number of stages, shift
N/2)th value. The data inputted and flows from the input registers, twiddle generators, twiddle factors and
side to the shift registers when multiplexer (Mux) 1, 2, 3, swappers are automatically generated, configured and
4 are at position ‘0’ in the 1st N/2 cycles. The multiplexers perform operations. In case of N points FFT, the proposed
turn to position ‘1’ in the next N/2 cycles then butterfly design generates log2 N Number of stages and the 1st, 2nd,
begins to subtract/add operation to compute 2 points DFT 3rd, 4th & other stages shift registers store N/2, N/4, N/8,
with the stored shift registers data and next N/2 inputted N/16, …, 1 values respectively, Floor[(log2N−1)/2]
data [6]. The subtracted outputs are stored in the same number of twiddle generators, the 1st twiddle generator
stage shift register, the 1st half numbers of added outputs after the 2nd stage generates [((N/4)×3)–3] twiddle factors,
are stored to the shift register of next stage and the 2nd the 2nd twiddle generator after the 4th stage generates
half number of added outputs are subtracted/added with [((N/4×4)×3)−3]×4 twiddle factors, the 3 rd twiddle
the 1st half number of added which is stored in the same generator after the 6th stage generates [((N/4×4)×3)−
stage. In this way, this flow persists from the present 3]×4×4 twiddle factors and similarly after others stages,
stage to next stage up to the final stage. Theses butterfly Floor[(log2N)/2] number of swappers.
components are joined in pipelined structure to compute As shown in Table I, 16 points FFT have 4 stages, 2
data in each clock. swappers and 1 twiddle generator which generates 9
twiddle factors. Similarly, 32 points FFT have 5 stages, 2
swappers, and 2 twiddle generators. the 1st and the 2nd
generator generates 21 and 12 twiddle factors respectively.
These swappers and twiddle generators are PEs.
The PEs ( j )n2 k1 and WNn3 ( k1  2 k2 ) after the 1st and the
Fig. 4. Butterfly structure for N-Point
2nd stages respectively are found out based on N for all
the Nth positions, after the 3rd and the 4th stages
respectively are found out based on N/4 for the (N/4)th
positions and repeats the same PEs for every next 4
positions up to the last position, after the 5 th and the 6th
stages respectively are found out based on N/16 for the
(N/16)th positions and repeats the same PEs for every next
Fig. 5. Trivial (-j) multiplier (Swapper) 16 positions up to the last position. The same way, PEs

©2019 Int. J. Elec. & Elecn. Eng. & Telcomm. 165

 International Journal of Electrical and Electronic Engineering & Telecommunications Vol. 8, No. 3, May 2019

can be found at each position for next stages, later PEs at be discussed. Similarly, PEs at each position for others
each position and each stage are shown in Fig. 8 and Fig. point’s FFT can be found using parameters values in
9 for 16 points FFT and 32 Points FFT respectively will Table II.

TABLE I: COMPONENTS USED IN THE PROPOSED RECONFIGURABLE FFT BASED ON VARIABLE LENGTH N

Number of Number
Number Number of Number of values Number of Number of
N twiddle of
of Stages Shift Register Shift Registers store twiddle ROM twiddle factors
generators Swappers

8 3 3 4+2+1 1 1 3 1
16 4 4 8+4+2+1 1 1 9 2
32 5 5 16+8+4+2+1 1 2 21+12 2
64 6 6 32+16+8+4+2+1 1 2 45+36 3
128 7 7 64+32+16+8+4+2+1 1 3 93+84+48 3
256 8 8 128+64+32+16+8+4+2+1 1 3 191+180+144 4
512 9 9 256+128+64+32+16+8+4+2+1 1 4 381+372+336+192 4

TABLE II: PROCESSING ELEMENTS PARAMETERS VALUES FOR THE PROPOSED RECONFIGURABLE FFT
After 1st After 2nd After 4th After 5th After 6th After 8th
PEs After 3rd After 7th
Stage Stage Stage Stage Stage Stage
N
WNn3 ( k12k2 )
Stage ( j )n2k1 WNn3 ( k12k2 ) WNn3 ( k12k2 )
Stage ( j )n2k1 WNn3 ( k12k2 )
( j )n2k1 ( j )n2k1
n1, n2 = 0, 1
k1, k2 = 0, 1
8 No PE No PE No PE No PE No PE No PE
n3, k3 = 0, 1
N =8
n1, n2 = 0, 1 n1, n2 = 0, 1
16 k1, k2 = 0, 1 k1, k2 = 0, 1
No PE No PE No PE No PE No PE
n3, k3 = 0, 1, .., 3 n3, k3 = 0
N =16 N =4
n1, n2 = 0, 1, k1, k2 = 0, 1 n1, n2 = 0, 1, k1, k2 = 0, 1
32 n3, k3 = 0, 1, .., 7 n3, k3 = 0, 1 No PE No PE No PE No PE
N =32 N =8
n1, n2 = 0, 1, n1, n2 = 0, 1 n1, n2 = 0, 1
k1, k2 = 0, 1 k1, k2 = 0, 1 k1, k2 = 0, 1
64 No PE No PE No PE
n3, k3 = 0, 1, .., 15 n3, k3 = 0, 1, .., 3 n 3, k3 = 0
N =64 N =16 N=4
n1, n2 = 0, 1, k1, k2 = 0, 1 n1, n2 = 0, 1, k1, k2 = 0, 1 n1, n2 = 0, 1, k1, k2 = 0, 1
128 n3, k3 = 0, 1,.., 31 n3, k3 = 0, 1, .., 7 n 3, k3 = 0, 1 No PE No PE
N =128 N =32 N=8
n1, n2 = 0, 1, k1, k2 = 0, 1 n1, n2 = 0, 1, k1, k2 = 0, 1 n1, n2 = 0, 1, k1, k2 = 0, 1 n1, n2 = 0, 1, k1, k2 = 0, 1
256 n3, k3 = 0, 1, .., 63 n3, k3 = 0, 1, .., 15 n 3, k3 = 0, 1, .., 3 n 3, k3 = 0 No PE
N =256 N=64 N=16 N=4
n1, n2 = 0, 1 n1, n2 = 0, 1 n1, n2 = 0, 1 n1, n2 = 0, 1
k1, k2 = 0, 1 k1, k2 = 0, 1 k1, k2 = 0, 1 k1, k2 = 0, 1
512
n3, k3 = 0, 1,..,127 n3, k3 = 0, 1, .., 31 n 3, k3 = 0, 1, .., 7 n 3, k3 = 0, 1
N =512 N=128 N=32 N=8

0
After 2nd stage
W512 [((N/4) *3)-3] number
of Twiddles WN values
1
W512 After 4th stage
Twiddle ROM

[((N/16) *3)-3]*4number
of Twiddles WN/4 values
… After 6th stage
W…511 [((N/64) *3)-3]*16number
512
… … of Twiddles WN/16 values
… …
.. ..
… After mth stage
[((N/4^(m/2)) *3)-3]*4^(m/2-1) number
…
of Twiddles WN/4^(m/2-1) values
..
Fig. 6. Twiddle values fetched from twiddle ROM.

The twiddle ROM has 512 twiddle factors values from 6 and Table III. These values are fetched from ROM
0
W 512 to W 511
512 in the proposed processor. Even stages based on symmetric W kN N / 2  W kN and periodicity
have the number of twiddle factors which are generated W kN N / 2  W kN properties. Some of the values are shown
by twiddle generators and the value of these twiddle in Table III. This method is reducing area as even stages
factors are fetched from twiddle ROM as shown in a Fig. use the same values of twiddle ROM for different FFT

©2019 Int. J. Elec. & Elecn. Eng. & Telcomm. 166

 International Journal of Electrical and Electronic Engineering & Telecommunications Vol. 8, No. 3, May 2019

points. The twiddle factor W 0N value wherever is reduce hardware and increase the performance of the
required is bypassed rather than multiplying in the proposed design.
proposed processor as W 0N =1. These all techniques
TABLE III: TECHNIQUE TO FIND TWIDDLE FACTORS FROM TWIDDLE ROM
PEs After 2nd Stage After 4th Stage After 6th Stage After 8th Stage
N W n3(k12k 2) W n3(k12k 2) W n3(k12k 2) W nN3(k12k 2)
N N N

W 512  W 8
128 2

W 512  W 8
64 1
8 No PEs as there are only 3 stages in 8 points FFT
W 512  W 8
192 3

64

W 512 W 16
2
16 W 512  W 16
32 1
No PEs as there are only 4 stages in 16 points FFT
96

W 512 W 16
3

W 512  W 32 W 512  W 8
32 2 128 2

W 512  W 32 W 512  W 8
224 14 64 1
32 No PEs as there are only 5 stages in 32 points FFT
W 512  W 32 W 512  W 8
112 7 192 3

W 512  W 64 W 512  W 16
240 30 64 2

W 512  W 64 W 512  W 16
120 15 32 1
64 No PEs as there are only 6 stages in 64 points FFT
 W 512  W 16
360 45 96 3
W 512 W 64
W 512  W 128 W 512  W 32 W 512  W 8
240 60 32 2 128 2

W 512  W 128 W 512  W 32 W 512  W 8 No PEs as there are only 7

96 24 224 14 64 1
128
stages in 128 points FFT
W 512  W 128 W 512  W 32 W 512  W 8
372 93 112 7 192 3

W 512  W 256 W 512  W 64 W 512  W 16

240 120 240 30 64 2

W 512  W 256 W 512  W 64 W 512  W 16 No PEs as there are only 8

126 63 120 15 32 1
256
stages in 256 points FFT
W 512  W 256 W 512  W 64 W 512  W 16
378 189 360 45 96 3

W 512  W 512 W 512  W 128 W 512  W 32 W 512  W 8

378 378 240 60 32 2 128 2

W 512  W 512 W 512  W 128 W 512  W 32 W 512  W 8

211 211 96 24 224 14 64 1
512
W 512  W 512  W 512  W 32 W 512  W 8
433 433 372 93 112 7 192 3
W 512 W 128

and the swapper ( j )n2 k1 after the 3rd stage generates

(−j)0, (−j)0, (−j)0, (−j)0, (−j)0, (−j)0, (−j)0,( −j)0,(−j)0,
(−j)0, (−j)0, (−j)0, (−j)1, (−j)1, (−j)1, (−j)1.
Fig. 8 states the SFG of the 16 points proposed design
reconfigurable processor. For the 16 points FFT results,
the first 8 points are feed in the Stage 1 shift register by
butterfly unit in every cycle. It takes 8 cycles and at the
9th cycle as x(8) point is inserted into the Stage 1,
butterfly unit starts to add and subtract between x(0) &
x(8) points and this added output is feed in the Stage 2
shift register and subtracted output is feed in the Stage 1
shift register. At 10th cycle, x(9) point entered into the
Fig. 7. Block diagram of the proposed reconfigurable FFT for 16 points Stage 1, the butterfly unit again begins to add and
Fig. 7 shows a block diagram of 16 points FFT, the subtract between x(1) & x(9) points and the added output
proposed design generates 4 shift registers, 4 stages, and is feed in the Stage 2 register and subtracted is feed in the
1 twiddle generator. The 1st stage registers stores 8 value, Stage 1 register. This flow continues up to the 12th cycle.
the 2nd stage register stores 4 value, the 3rd stage register At the 13th cycle as x(12) point entered into the Stage 1,
stores 2 value and the 4th stage register stores 1 value as the butterfly again starts addition and subtraction between
x(4) & x(12) point then this subtracted output is feet in
mentioned in Table I. The first stage, swapper ( j )n2 k1 ,
the Stage 1 register and added value and the Stage 2
the second stage and the twiddle factors W16n3 ( k1  2 k2 ) register values perform addition & subtraction then Stage
operations are computed based on the 16 points. The third 2 subtracted output is feedback in the Stage 2 register and
stage, the swapper ( j )n2 k1 and the fourth stage the Stage 2 added output is feed in the Stage 3 register.
This flow continues up to the 13th cycle. At the 15th cycle,
operations are computed based on 4 points samples as
as x(14) point entered into the Stage 1, the Stage 3
presented in Table II. Thus, the swapper ( j )n2k1 after the butterfly unit also begins to add and subtract then this
1st stage generates (−j)0, (−j)0, (−j)0, (−j)1, (−j)0, (−j)0, subtracted output is stored in the Stage 3 register and
(−j)0,( −j)1,(−j)0, (−j)0, (−j)0, (−j)1, (−j)0, (−j)0, (−j)0, added output is stored in the Stage 4 register. At the 16th
(−j)1 and the twiddle generator W16n3 ( k1  2 k2 ) after the 2nd cycle, as x(15) point entered into the Stage 1, the Stage 4
stage generates twiddle factors W160 , W160 , W160 , W160 , W160， buttery unit also begins to add and subtract then this
subtracted output is feed in the Stage 4 register and added
W162，W164 W166 , W160，W161 ，W162，W163，W106，W163，W166，W169 output is the 1st output result y(0) of FFT output. This

©2019 Int. J. Elec. & Elecn. Eng. & Telcomm. 167

 International Journal of Electrical and Electronic Engineering & Telecommunications Vol. 8, No. 3, May 2019

flow continuous up to the 31st cycle. Stage 4 additions also performed at the clocks wherever it’s required based
outputs from 16th to 31st cycles are FFT results. on addresses as shown in Fig. 8 and Fig. 9. These
Swapping and twiddle multiplication operations are operations are controlled by counter signal.

Fig. 8. SFG of proposed reconfigurable FFT for 16 points

Fig. 9. SFG of proposed reconfigurable FFT for 32 points

twiddle factors, fewer multiplication operations, and less

IV. COMPARISON
hardware. Table V shows implementation results of the
The proposed pipeline re-configurable FFT processor proposed and conventional FFT processors [5, 4 and 7]
based on Radix-22 for variable length N is designed in between slices used, flip-flops used, LUT used and no. of
VHDL. It is simulated in MATLAB & ModelSim to GCLKs used. Fig. 10 shows the comparison between
validate the proposed design results and synthesized with synthesized max frequencies of the proposed design for
xc7vx330t-3ffg1157 FPGA hardware. different points and conventional designs. The proposed
Table IV shows the comparison of the proposed design Max frequency for variable length is higher than
Reconfigurable Radix-22 and conventional FFT conventional in ratio and max frequency of proposed
processors [8]-[11]. This table shows that the proposed design for variable length decreases as increasing number
design uses only one twiddle ROM which results in lesser of points because of increased logic and complexity.

©2019 Int. J. Elec. & Elecn. Eng. & Telcomm. 168

 International Journal of Electrical and Electronic Engineering & Telecommunications Vol. 8, No. 3, May 2019

TABLE IV: COMPARISON OF DIFFERENT PROCESSORS

Processor Number of Points Method Radix Number of stages Number of twiddle ROM Memory
R22SDF [8] 256 Pipeline Radix -22 8 8 256
R24SDF [9,10] 128 2 Parallel, Pipeline Radix -24 7 7 128
R25SDF [11] 512 8 Parallel, Pipeline Radix -25 9 9 512
16 4 16
32 5 32
Proposed
64 6 64
reconfigurable Pipeline Radix -22 1
128 7 128
Radix-22
256 8 256
512 9 512
TABLE V: IMPLEMENTATION RESULTS
Parameters FPGA [5] FFT [4] Vedic [7] Proposed Reconfigurable Radix-22 FFT
No. of Point (N) 1024 256 64 16 32 64 128 256 512
No. of slices used 3155 - 624 340 562 725 1042 1323 1795
No. of slices Flip Flops used 1514 - - 284 410 538 697 851 1028
No. of 4 input LUTs used 5916 - - 629 1031 1345 1937 2497 3335
Max Frequency (in MHz) 92.36 35.76 149.92 173.27 161.29 158.96 158.69 158.37 155.9
SQNR (in dB) - - - 38.72 35.19 37.02 33.49 33.27 32.98

[5] K. Harikrishna, T. R. Rao, and V. A. Labay, “FPGA

implementation of FFT algorithm for IEEE 802.16e (Mobile
Max Frequency in MHz

WiMAX),” Int. Journal of Computer Theory and Engineering, vol.

3, no. 2, pp. 197-203, April 2011.
[6] W. H. Chang and T. Nguyen, “An OFDM-specified lossless FFT
architecture,” IEEE Trans. on Circuits and Systems I, vo. 53, no. 6,
pp. 1235-1243, Jun. 2006.
[7] N. John and G. K. Sadanandan, “FPGA implementation of a novel
efficient vedic FFT/IFFT processor for OFDM,” Int. Journal of
Advanced Research in Electrical, Electronics and Instrumentation
Engi., vol. 3, no. 3, pp. 7964-7972, Sep. 2014.
[8] U. Akshata and D. K. Gopika, “Hardware implementation of
Fig. 10. Comparison of synthesis results of different architecture
decimation in time FFT,” MIT Int. Journal of Electronics and
Communication Engineering, vol. 3, no. 1, pp. 39-42, Jan. 2013.
V. CONCLUSIONS [9] J. Lee and H. Lee, “A high-speed parallel radix-24 FFT/IFFT
processor for MB OFDM UWB system,” IEICE Trans.
The purpose of this research is to implement Fundamentals, vol. E91–A, no. 4, April 2008.
reconfigurable Radix-22 FFT processor that can be used [10] M. Shin and H. Lee, “A high-speed four-parallel radix-24
for 8, 16, 32, 64, 128, 256, 512 points FFT instead of FFT/IFFT processor for UWB applications,” in Proc. IEEE Int.
using different length FFT processor for different OFDM Symp. on Circuits and Systems, May 2008, pp. 960-963.
communication system FFT’s application. The Radix-22 [11] T. Cho and H. Lee, “A high-speed low-complexity modified FFT
algorithm is used to reduce the number of twiddle factors, Radix - 25 processor for high rate WPAN applications,” IEEE
Trans. on VLSI Systems, vol. 21, no. 1, pp. 187-191, Jan. 2013.
which causes the reduction in the area. The Radix-2
[12] V. Sarada and T. Vigneswaran, “Reconfigurable FFT processor -
butterfly structure is used to reduce the complexity. This A broader perspective survey,” Int. Journal of Engineering &
overall result increases speed as decrease number of Technology, vol. 5, no. 2, pp. 949-956, May 2013.
multiplications, reusing twiddle factors value for others [13] T. Cho, H. Lee, J. Park, and C. Park, “A high-speed low-
point FFT and passing input signal instead of multiplying complexity modified radix - 25 FFT processor for gigabit WPAN
applications,” in Proc. IEEE Int. Symp. of Circuits and Systems,
the twiddle factor WN0 as WN0 value is 1. This approach May 2011, pp. 1259–1262.
increases the maximum frequency of the proposed [14] W. H. Chang and T. Nguyen, “Design and simulation of 64 point
reconfigurable FFT processor than conventional FFT FFT using Radix - 4 algorithm for FPGA implementation,” Int.
processors. Journal of Engineering Trends and Technology, vol. 4, no. 1-2, pp
109-113, Feb. 2013.
[15] M. Garrido, J. Grajal, M. A. Sanchez, and O. Gustafsson,
REFERENCES “Pipelined radix-2k feedforward FFT architectures,” IEEE Trans.
[1] A. Saeed, M. Elbably, G. Abdelfadeel, and M. I. Eladawy, “FPGA on Very Large Scale Integration Systems, vol. 21, no. 1, pp. 23-32,
implementation of Radix-22 Pipelined FFT Processor,” in Proc. 3rd Jan. 2013.
WSEAS Int. Symp. on Wavelets Theory and Applications in [16] S. J. Huang and S. G. Chen, “A green FFT processor with 2.5-
Applied Mathematics, Signal Processing & Modern Science, 2009, GS/s for IEEE 802.15.3c (WPANs),” in Proc. Int. Conf. on Green
pp. 109-114. Circuits and Systems, June 2010, pp. 9–13.
[2] Z. Wang, X. Liu, B. He, and F. Yu, “A combined SDC-SDF [17] W. Li, Y. Ma and L. Wanhammar, “Design and power
architecture for normal I/O pipelined radix-2 FFT,” IEEE Trans. measurement of different points FFT using Radix-2 algorithm for
VLSI Systems, vol. 23, no. 5, pp. 973-977, 2015. FPGA implementation,” in Proc. Int. Conf. of Electronics,
[3] J. Wang and L. A. Ronningen, “An implementation of pipelined Communication and Aerospace Technology, April 2017, vol. 2, pp.
radix-4 FFT architecture on FPGAs,” Journal of Clean Energy 190-195.
Technologies, vol. 2, no. 1, pp. 101-103, Jan. 2014. [18] X. Cui and D. Yu, “Digital OFDM transmitter architecture and
[4] C. P. Fan, M. S. Lee, and G. A. Su, “Efficient low multiplier cost FPGA design,” in Proc. IEEE 8th Int. Conf. on ASIC, Oct. 2009,
256-point FFT design with Radix-24 SDF architecture,” Journal of pp. 477-480.
Engineering, vol. 19, no. 2, pp. 61-74, 2008. [19] M. Bansal and S. Nakhate, “High speed pipelined 64-point FFT
processor based on Radix-22 for wireless LAN,” in Proc. IEEE 4th

©2019 Int. J. Elec. & Elecn. Eng. & Telcomm. 169

 International Journal of Electrical and Electronic Engineering & Telecommunications Vol. 8, No. 3, May 2019

Int. Conf. on Signal Processing and Integrated Networks, Feb. Manish Bansal received the B.E. degree in Electronics &
2017, pp. 607-612. Telecommunication and M.Tech. degree. His research interests include
[20] S. He and M. Torkelson, “A new approach to pipeline processor,” fast Fourier transform, signal processing, parallel computing, and VLSI.
in Proc. International Conference on Parallel Processing, April Dr. Sangeeta Nakhate received the Ph.D. Her research interests
1996, pp. 766-770. include fast Fourier transform, signal processing, VLSI and microwave
fields.

©2019 Int. J. Elec. & Elecn. Eng. & Telcomm. 170