# Radix-2α/4β Building Blocks for Efficient VLSI’s Higher Radices Butterflies Implementation

Authors: Marwan A. Jaber; Daniel Massicotte
Journal: VLSI Design
 (2014)

---

## Abstract

This paper describes an embedded FFT processor where the higher radices butterflies maintain one complex multiplier in its critical path. Based on the concept of a radix-r fast Fourier factorization and based on the FFT parallel processing, we introduce a new concept of a radix-r Fast Fourier Transform in which the concept of the radix-r butterfly computation
has been formulated as the combination of radix-2α/4β butterflies implemented in parallel. By doing so, the VLSI butterfly implementation for higher radices would be feasible since it maintains approximately the same complexity of the radix-2/4 butterfly which is obtained by block building of the radix-2/4 modules. The block building process is achieved by duplicating the block circuit diagram of the radix-2/4 module that is materialized by means of a feed-back network which will reuse the block circuit diagram of the radix-2/4 module.


---

## Body

## 1. Introduction

For the past decades, the main concern of the researchers was to develop a fast Fourier transform (FFT) algorithm in which the number of operations required is minimized. Since Cooley and Tukey presented their approach showing that the number of multiplications required to compute the discrete Fourier transform (DFT) of a sequence may be considerably reduced by using one of the fast Fourier transform (FFT) algorithms [1], interest has arisen both in finding applications for this powerful transform and for considering various FFT software and hardware implementations.The DFT computational complexity increases according to the square of the transform length and thus becomes expensive for largeN. Some algorithms used for efficient DFT computation, known as fast DFT computation algorithms, are based on the divide-and-conquer approach. The principle of this method is that a large problem is divided into smaller subproblems that are easier to solve. In the FFT case, dividing the work into subproblems means that the input data x
[
n
] can be divided into subsets from which the DFT is computed, and then the DFT of the initial data is reconstructed from these intermediate results. Some of these methods are known as the Cooley-Tukey algorithm [1], split-radix algorithm [2], Winograd Fourier transform algorithm (WFTA) [3], and others, such as the common factor algorithms [4].The problem with the computation of an FFT with an increasingN is associated with the straightforward computational structure, the coefficient multiplier memories’ accesses, and the number of multiplications that should be performed. The overall arithmetic operations deployed in the computation of an N-point FFT decreases with increasing r as a result; the butterfly complexity increases in terms of complex arithmetic computation, parallel inputs, connectivity, and number of phases in the butterfly’s critical path delay. The higher radix butterfly involves a nontrivial VLSI implementation problem (i.e., increasing butterfly critical path delay), which explains why the majority of FFT VLSI implementations are based on radix 2 or 4, due to their low butterfly complexity. The advantage of using a higher radix is that the number of multiplications and the number of stages to execute an FFT decrease [4–6].The most recent attempts to reduce the complexity of the higher radices butterfly’s critical path was achieved by the concept of a radix-r fast Fourier transform (FFT) [8, 9], in which the concept of the radix-r butterfly computation has been formulated as composed engines with identical structures and a systematic means of accessing the corresponding multiplier coefficients. This concept enables the design of butterfly processing element (BPE) with the lowest rate of complex multipliers and adders, which utilizes r or r
-
1 complex multipliers in parallel to implement each of the butterfly computations. Another strategy was based on targeting hardware oriented radix 2
α or 4
β which is an alternative way of representing higher radices by means of less complicated and simple butterflies in which they used the symmetry and periodicity of the root unity to further lower down the coefficient multiplier memories’ accesses [10–20].Based on the higher radices butterfly and the parallel FFT concepts [21, 22], we will introduce the structure of higher multiplexed 2
α or 4
β butterflies that will reduce the resources in terms of complex multiplier and adder by maintaining the same throughput and the same speed in comparison to the other proposed butterflies structures in [13–20].This paper is organized as follows. Section2 describes the higher radices butterfly computation and Section 3 details the FFT parallel processing. Section 4 elaborates the proposed higher radices butterflies; meanwhile Section 5 draws the performance evaluation of the proposed method and Section 6 is devoted to the conclusion.


## 2. Higher Radices’ Butterfly Computation

The basic operation of a radix-r PE is the so-called butterfly computation in which r inputs are combined to give the r outputs via the following operation:
(1)
X
=
B
r
x
in
,
x
in
=
[
x
(
0
)
,
x
(
1
)
,
…
,
x
(
r
-
1
)
]
T
,
X
=
[
X
(
0
)
,
X
(
1
)
,
…
,
X
(
r
-
1
)
]
T
,wherex
in and X are, respectively, the butterfly’s input and output vectors. B
r is the butterfly matrix (
dim
⁡
(
B
r
)
=
r
×
r
) which can be expressed as
(2)
B
r
=
W
N
T
r
,
for decimation in frequency (DIF) process, and
(3)
B
r
=
T
r
W
N
,
for decimation in time (DIT) process. In both cases the twiddle factor matrix, W
N, is a diagonal matrix which is defined by W
N
=
diag
⁡
(
1
,
w
N
p
,
w
N
2
p
,
…
,
w
N
(
r
-
1
)
p
) with p
=
0,1
,
…
,
N
/
r
s
-
1 and  s
=
0,1
,
…
,
lo
g
r
N
-
1 and T
r is theadder tree matrix within the butterfly structure expressed as [4]
(4)
T
r
=
[
w
N
0
w
N
0
w
N
0
⋯
⋯
w
N
0
w
N
0
w
N
N
/
r
w
N
2
N
/
r
⋯
⋯
w
N
(
r
-
1
)
N
/
r
w
N
0
w
N
2
N
/
r
w
N
4
N
/
r
⋮
⋮
w
N
2
(
r
-
1
)
N
/
r
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
w
N
0
w
N
(
r
-
1
)
N
/
r
w
N
2
(
r
-
1
)
N
/
r
⋯
⋯
w
N
(
r
-
1
)
2
N
/
r
]
.As seen from (2) and (3), the adder tree, T
r, is almost identical for the two algorithms, with the only difference being the order in which the twiddle factor and the adder tree multiplication are computed. A straightforward implementation of the adder tree is not effective for higher radices butterflies due to the added complex multipliers in the higher radices butterflies’ critical path that will complicate its implementation in VLSI.By defining the element of thelth line and the mth column in the matrix T
r as [
T
r
]
l
,
m,
(5)
[
T
r
]
l
,
m
=
w
N
⟦
(
l
m
N
/
r
)
⟧
N
,
where l
=
0,1
,
…
,
r
-
1, m
=
0,1
,
…
,
r
-
1, and ⟦
x
⟧
N represents the operation x modulo N. By defining W
N
(
m
,
v
,
s
) the set of the twiddle factor matrix as
(6)
[
W
N
]
l
,
m
(
v
,
s
)
=
diag
⁡
(
w
N
(
0
,
v
,
s
)
,
w
N
(
1
,
v
,
s
)
,
…
,
w
N
(
r
-
1
,
v
,
s
)
)
,
where the index r is the FFT’s radix, v
=
0,1
,
…
,
V
-
1 represents the number of words of size r
(
V
=
N
/
r
), and s
=
0,1
,
…, S is the number of stages (or iterations S
=
lo
g
r
N
-
1). Finally, the twiddle factor matrix in (2) and (3) can be expressed for the different stages of an FFT process as [7, 8]
(7)
[
W
N
]
l
,
m
(
v
,
s
)
=
{
w
N
⟦
⌊
v
/
r
s
⌋
l
r
s
⟧
N
for
l
=
m
0
elsewhere
,
for the DIF process and (3) would be expressed as
(8)
[
W
N
]
l
,
m
(
v
,
s
)
=
{
w
N
⟦
⌊
v
/
r
(
S
-
s
)
⌋
l
r
(
S
-
s
)
⟧
N
for
l
=
m
0
elsewhere
,
for the DIT process, where l
=
0,1
,
…
,
r
-
1 is the lth butterfly’s output, m
=
0,1
,
…
,
r
-
1 is the mth butterfly’s input, and ⌊
x
⌋ represents the integer part operator of x.As a result, thelth transform output during each stage can be illustrated as
(9)
X
(
v
,
s
)
[
l
]
=
∑
m
=
0
r
-
1
x
(
v
,
s
)
[
m
]
w
N
⟦
l
m
N
/
r
+
⌊
v
/
r
s
⌋
l
r
s
⟧
N
,
for the modified DIF process, and
(10)
X
(
v
,
s
)
[
l
]
=
∑
m
=
0
r
-
1
x
(
v
,
s
)
[
m
]
w
N
⟦
l
m
N
/
r
+
⌊
v
/
r
(
S
-
s
)
⌋
m
r
(
S
-
s
)
⟧
N
,
for the modified DIT process.The conceptual key to the modified radix-r FFT butterfly is the formulation of the radix-r as composed engines with identical structures and a systematic means of accessing the corresponding multiplier coefficients [8, 9]. This enables the design of an engine with the lowest rate of complex multipliers and adders, which utilizes r or r
-
1 complex multipliers in parallel to implement each of the butterfly computations. There is a simple mapping from the three indices m, v, and s (FFT stage, butterfly, and element) to the addresses of the multiplier coefficients needed by using the proposed FFT address generator in [24]. For a single processor environment, this type of butterfly with r parallel multipliers would result in decreasing the time delay for the complete FFT by a factor of O
(
r
). A second aspect of the modified radix-r FFT butterfly is that they are also useful in parallel multiprocessing environments. In essence, the precedence relations between the engines in the radix-r FFT are such that the execution of r engines in parallel is feasible during each FFT stage. If each engine is executed on the modified processing element (PE), it means that each of the r parallel processors would always be executing the same instruction simultaneously, which is very desirable for SIMD implementation on some of the latest DSP cards.Based on this concept, Kim and Sunwoo proposed a proper multiplexing scheme that reduces the usage of complex multiplier for the radix-8 butterfly from 11 to 5 [25].


## 3. Parallel FFT Processing

For the past decades, there were several attempts to parallelize the FFT algorithm which was mostly based on parallelizing each stage (iteration) of the FFT process [26–28]. The most successful FFT parallelization was accomplished by parallelizing the loops during each stage or iteration in the FFT process [29, 30] or by focusing on memory hierarchy utilization that is achieved by the combination of production and consumption of butterflies’ results, data reuse, and FFT parallelism [31].The definition of the DFT is represented by(11)
X
(
k
)
=
∑
n
=
0
N
-
1
x
(
k
)
w
N
n
k
,
k
∈
[
0
,
N
-
1
]
,
where x
(
n
) is the input sequence, X
(
k
) is the output sequence, N is the transform length, and w
N is the Nth root of unity: w
N
=
e
-
j
2
π
/
N. Both x
(
n
) and X
(
k
) are complex valued sequences.Letx
(
n
) be the input sequence of size N and let p
r denote the degree of parallelism which is multiple of N; therefore, we can rewrite (11) by considering k
1
=
0,1
,
…
,
V
-
1, p
=
0,1
,
…
,
p
r
-
1, q
=
0,1
,
…
,
p
r
-
1, V
=
N
/
p
r, and k
=
k
1
+
q
V as [9]
(12)
X
(
k
1
+
q
N
/
p
r
)
=
[
w
N
0
∑
n
=
0
N
/
p
r
-
1
x
(
p
r
n
)
w
N
/
p
r
n
(
k
1
+
q
r
N
/
p
r
)
k
+
w
N
(
k
1
+
q
N
/
p
r
)
∑
n
=
0
N
/
p
r
-
1
x
(
p
r
n
+
1
)
w
N
/
p
r
n
(
k
1
+
q
N
/
p
r
)
k
+
⋯
+
w
N
(
p
r
-
1
)
(
k
1
+
q
N
/
p
r
)
∑
n
=
0
N
/
p
r
-
1
x
(
p
r
n
+
(
p
r
-
1
)
)
w
N
/
p
r
n
(
k
1
+
q
N
/
p
r
)
]
.
If X
(
k
) is the Nth order Fourier transform ∑
n
=
0
N
-
1
x
(
n
)
w
N
n
k, then, X
(
0
)
(
k
1
), X
(
1
)
(
k
1
)
,
…, and X
(
p
r
-
1
)
(
k
1
) will be the N
th
/
p
r order Fourier transforms given, respectively, by the following expressions: ∑
n
=
0
V
-
1
x
(
p
r
n
)
w
V
n
v, ∑
n
=
0
V
-
1
x
(
p
r
n
+
1
)
w
V
n
v
,
…, and ∑
n
=
0
V
-
1
x
(
p
r
n
+
(
p
r
-
1
)
)
w
V
n
v.


## 4. The Proposed Higher Radices Butterflies

Most of the FFTs’ computation transforms are done within the butterfly loops. Any algorithm that reduces the number of additions and multiplications in these loops will reduce the overall computation speed. The reduction in computation is achieved by targeting trivial multiplications which have a limited speedup or by parallelizing the FFTs that have a significant speedup on the execution time of the FFT. In this section we will be limited in the elaboration of the proposed butterfly’s radix-2α/4β (the radix-2/4 families) for the DIT FFT process. By rewriting (3) as
(13)
X
=
W
N
∑
m
=
0
r
-
1
x
(
m
)
w
N
l
m
N
/
r
=
W
N
∑
m
=
0
r
-
1
x
(
m
)
w
r
l
m
and by applying the concept of the parallel FFT (introduced in Section 3) on the kernel B
r, therefore, (13) will be expressed as
(14)
X
=
W
N
∑
m
=
0
r
-
1
x
(
m
)
w
r
l
m
=
W
N
[
∑
m
=
0
r
/
α
-
1
x
(
α
m
)
w
r
l
m
α
+
⋯
k
k
k
k
+
∑
m
=
0
r
/
α
-
1
x
(
α
m
+
(
α
-
1
)
)
w
r
l
(
α
m
+
(
α
-
1
)
)
]
=
W
N
[
X
(
0
)
+
w
r
l
X
(
1
)
+
⋯
+
w
r
l
(
α
-
1
)
X
(
α
-
1
)
]
kkkkkkkkkkkkkkkkkkk
for
l
=
0
,
…
,
r
α
-
1
.It is to be noted that the notationw
x in all figures of this paper represents the set of twiddle factor associated with the butterfly input defined by [
w
0
,
…
,
w
(
r
-
2
)
]
=
diag
⁡
(
w
N
p
,
w
N
2
p
,
…
,
w
N
(
r
-
1
)
p
).For the radix-4 butterfly (r
=
2 and α
=
2), we can express (13) as
(15)
X
=
W
N
[
∑
m
=
0
1
x
(
2
m
)
w
2
l
m
+
w
4
l
∑
m
=
0
1
x
(
2
m
+
1
)
w
2
l
m
]
=
W
N
[
X
(
0
)
+
w
4
l
X
(
1
)
]
,
and the conventional radix-22 (MDC-R22) BPE in terms of radix-2 butterfly is illustrated in Figure 1.Figure 1
Conventional radix-22 (MDC-R22) BPE (butterfly processing element).The use of resources could also be reduced by a feedback network and a multiplexing network where the feedback network is for feeding theith output of the jth radix-2 adder network to the jth input of the ith butterfly and the multiplexers selectively pass the input data or the feedback, alternately, to the corresponding radix-2 adder network as illustrated in Figure 2(a) [23]. The circuit block diagram of the radix-2 adder network is illustrated in Figure 2(b) that consists of two complex adders only.(a) Proposed multiplexed radix-22 (MuxMDC-R22) BPE and (b) block circuit diagram of the radix-2 adder network [7].
(a)
(b)With the rising edge of the clock cycle the inputs data are fed to the butterfly’s input of the system presented in Figure1. In order to complete the butterfly’s operations within one clock cycle, the following conditions should be satisfied:
(16)
T
CLK
>
T
CM
+
2
T
CA
,
Throughput
=
4
T
CLK
,
where T
CM
/
T
CA is the time required to perform one complex multiplication/addition and the timing block diagram of Figure 1 is sketched in Figure 3.Figure 3
Timing block diagram of Figure1.With the rising edge of the clock cycle the inputs data are fed to the butterfly’s input of the system presented in Figure2(a) and with the falling edge of the clock cycle the feedback data are fed to the butterfly’s input. In order to complete the butterfly’s operations within one clock cycle, the following conditions should be satisfied:
(17)
t
1
>
T
CM
+
T
CA
,
t
2
>
T
CA
,
T
CLK
>
(
t
1
+
t
2
)
>
T
CM
+
2
T
CA
,
Throughput
=
4
T
CLK
,
and the timing block diagram of Figure 2(a) is illustrated in Figure 4.Figure 4
Timing block diagram of Figure2(a).Further block building of these modules could be achieved by duplicating the block circuit diagram of Figure2(a) and combining them in order to obtain the radix-8 MDC-R23 BPE; therefore, for this case (r
=
4 and α
=
2), (4) could be expressed as
(18)
X
(
l
)
=
W
N
[
∑
m
=
0
3
x
(
2
m
)
w
4
l
m
+
w
8
l
∑
m
=
0
3
x
(
2
m
+
1
)
w
4
l
m
]
=
W
N
[
X
(
0
)
+
w
8
l
X
(
1
)
]
,
and the signal flow graph (SFG) of the DIT conventional MDC-R23 BPE butterfly is illustrated in Figure 5. The resources in the conventional MDC-R23 BPE could also be reduced by means of the partial multiplexed radix 22 and a feedback network yielding to the proposed MuxMDC-R23 BPE structure in Figure 6.Figure 5
Conventional MDC-R23 BPE.Figure 6
Proposed MuxMDC-R23 BPE based on the partial MuxMDC-R22.The clock timing of Figure5 is computed as
(19)
T
CLK
>
T
CM
+
t
pm
+
3
T
CA
,
Throughput
=
8
T
CLK
,
where t
pm is the time required to execute one complex multiplication on a constant multiplier and the clock timing of the proposed MuxMDC-R23 is estimated as
(20)
t
1
>
T
CM
+
T
CA
,
t
2
>
T
CA
,
t
3
=
t
1
,
T
CLK
>
(
t
1
+
t
2
+
t
3
)
>
2
T
CM
+
3
T
CA
,
Throughput
=
8
T
CLK
.The overall timing block diagram of the proposed MuxMDC-R23 is sketched in Figure 7. In Figure 6, the inputs are multiplied by the twiddle factors w
i when S
2
=
1 and by the constant factors -
j, c, c
1 or 1 for S
2
=
0.Figure 7
Timing block diagram of Figure6.Further block building of these modules could be achieved by combining two radix-8 butterflies with eight radix-2 butterflies in order to obtain the conventional MDC-R24 BPE; therefore, for this case (r
=
8 and α
=
2), (4) could be expressed as
(21)
X
(
l
)
=
W
N
[
∑
m
=
0
7
x
(
2
m
)
w
8
l
m
+
w
8
l
∑
m
=
0
7
x
(
2
m
+
1
)
w
8
l
m
]
=
W
N
[
X
(
0
)
+
w
16
l
X
(
1
)
]
,
and the signal flow graph (SFG) of the proposed DIT radix-24 MuxMDC-R24 based on the partial MuxMDC-R23 (Figure 8) is illustrated in Figure 9.Figure 8
Proposed Partial MuxMDC-R23.Figure 9
Proposed MuxMDC-R24 BPE based on the Partial MuxMDC-R23.The clock timing of the conventional MDC-R24 BPE is computed as
(22)
T
CLK
>
T
CM
+
2
t
pm
+
4
T
CA
,
Throughput
=
16
T
CLK
,
and the clock timing of the proposed MuxMDC-R24 is estimated as
(23)
t
1
>
T
CM
+
T
CA
,
t
2
>
T
CA
,
t
3
=
t
pm
+
T
CA
,
t
4
=
t
1
,
T
CLK
>
(
t
1
+
t
2
+
t
3
+
t
4
)
>
2
T
C
M
+
t
pm
+
4
T
CA
,
Throughput
=
16
T
CLK
.
The overall timing block diagram of the proposed MuxMDC-R24 is sketched in Figure 10.Figure 10
Timing block diagram of Figure6.With the same reasoning as above, we will be limited in the elaboration of the proposed butterfly’s radix-4
α family to the DIT FFT process.For the radix-16 butterfly (r
=
4 and α
=
4), we can express (4) as
(24)
X
=
W
N
[
∑
m
=
0
3
x
(
4
m
)
w
4
l
m
+
w
16
l
∑
m
=
0
3
x
(
4
m
+
1
)
w
4
l
m
k
k
k
k
+
w
16
2
l
∑
m
=
0
3
x
(
4
m
+
2
)
w
4
l
m
+
w
16
3
l
∑
m
=
0
3
x
(
2
m
+
1
)
w
4
l
m
]
=
W
N
[
X
(
0
)
+
w
16
l
X
(
1
)
+
w
16
2
l
X
(
2
)
+
w
16
3
l
X
(
3
)
]
,
and the proposed MDC-R42 in terms of radix-4 network is illustrated in Figure 11 where the feedback network is for feeding the ith output of the jth radix-4 network to the jth input of the ith butterfly and the switches selectively pass the input data or the feedback, alternately, to the corresponding radix-4 butterfly. The circuit block diagram of the radix-4 network is illustrated in Figure 12.Figure 11
The proposed DIT MuxMDC-R42.Figure 12
Block circuit diagram of the radix-4 adder network.


## 5. Performance Evaluation

FFTs are the most powerful algorithms that are used in communication systems such as OFDM. Their implementation is very attractive in fixed point due to the reduction in cost compared to the floating point implementation. One of the most powerful FFT implementations is the pipelined FFT which is highly implemented in the communication systems; see Figure13.Figure 13
S stages radix-r pipelined FFT.Since the objective of this paper is mainly concentrated on the higher radices butterflies structures, in our performance study we will be limited to the impact of the butterfly structure. Once the pipeline is filled, the butterflies will producer output each clock cycle (throughput T in samples per cycle (Spc)). Therefore, Table 1 will draw the comparison between the different butterflies’ structures in terms of resources needed to compute an FFT of size N.Table 1
Resources needed to compute an FFT of sizeN.
Butterfly structure
Complex multiplier
Complex adder
Latency (cycles)
T (Spc)
4 parallel BPE architectures
R-24 [13], [14]
4(log
4
⁡
N
-
1)
16log
4
⁡
N
N
/
4
4
R-24 [15]
4(log
4
⁡
N
-
1)
16log
4
⁡
N
N
/
4
4
R-24 [16]
4(log
4
⁡
N
-
1)
16log
4
⁡
N
N
/
4
4
R-22 [17]
3(log
4
⁡
N
-
1)
16log
4
⁡
N
N
/
4
4
R-23 [17]
4(log
4
⁡
N
-
1)
8log
4
⁡
N
N
/
4
4
R-24 [17]
3.5(
log
4
⁡
N
-
4
)
8log
4
⁡
N
N
/
4
4
Proposed  MuxMDC-R22
3(log
4
⁡
N
-
1)
4log
4
⁡
N
N
/
4
4
8 parallel BPE architectures
R-2 [18]
8(log
4
⁡
N
-
1)
16log
4
⁡
N
N
/
8
8
R-2 [19]
8(log
4
⁡
N
-
1)
32log
4
⁡
N
N
/
8
8
R-24 [20]
8(log
4
⁡
N
-
1)
32log
4
⁡
N
N
/
8
8
R-22 [17]
6(log
4
⁡
N
-
1)
16log
4
⁡
N
N
/
8
8
R-23 [17]
6log
4
⁡
N
-
7
16log
4
⁡
N
N
/
8
8
R-24 [17]
7log
4
⁡
N
-
8
16log
4
⁡
N
N
/
8
8
Proposed MuxMDC-R23
7(log
8
⁡
N
-
1)
8log
8
⁡
N
N
/
8
8
16 parallel BPE architectures
Proposed MuxMDC-R24
17(log
16
⁡
N
-
1)
16log
16
⁡
N
N
/
16
16
Proposed MuxMDC-R42
15(log
16
⁡
N
-
1)
32log
16
⁡
N
N
/
16
16As shown in Figure14, we could clearly see that the proposed MuxMDC-R22 for the four parallel pipelined FFTs of size N will have the same amount of complex multiplier compared to the radix 24 cited in [30]. Furthermore, our proposed MuxMDC-R22 achieves a reduction in the usage of complex multiplier by a factor that ranges between 1.1 and 1.4 compared to the other cited butterflies.Figure 14
Comparison between the different butterflies’ structures in terms of complex multiplier needed to compute the 4 parallel BPE pipelined FFTs of sizeN.For the 4 parallel pipelined FFTs of sizeN, the reduction in the usage of complex adder for our proposed method MuxMDC-R22 ranges between 1.9 and 3.9 compared to the cited butterflies as shown in Figure 15.Figure 15
Comparison between the different butterflies’ structures in terms of complex adder needed to compute the 4 parallel BPE pipelined FFTs of sizeN.For the 8 parallel pipelined FFTs of sizeN, the reduction factor in the usage of complex multiplier for our proposed MuxMDC-R23 could range from 1.3 to 2.1 compared to the cited butterflies as illustrated in Figure 16.Figure 16
Comparison between the different butterflies’ structures in terms of complex multiplier needed to compute the 8 parallel BPE pipelined FFTs of sizeN.For the same structure, the reduction factor in the usage of complex adder for our proposed method MuxMDC-R23 could range from 3.0 to 5.4 compared to the cited butterflies (Figure 17).Figure 17
Comparison between the different butterflies’ structures in terms of complex adder needed to compute the 8 parallel BPE pipelined FFTs of sizeN.It seems that the proposed MuxMDC-R24 uses less complex adders than the proposed MuxMDC-R42 as shown in Figure 18 where the proposed MuxMDC-R24 achieves a reduction in the usage of complex adder by a factor of 2 but the proposed MuxMDC-R42 achieves a reduction in the usage of complex multiplier by a factor of 1.1 as shown in Figure 19.Figure 18
Comparison between the different butterflies’ structures in terms of complex adder needed to compute the 16 parallel BPE pipelined FFTs of sizeN.Figure 19
Comparison between the different butterflies’ structures in terms of complex multiplier needed to compute the 16 parallel BPE pipelined FFTs of sizeN.Since one complex multiplication is counted as 3 real multiplications and 5 real additions as shown in Figure20, Table 2 will illustrate the required resources in terms of full adder (FA) that will be computed as (a) n
2 for two n-digit real multiplier and (b) p for two p-digit real adder.Table 2
Resources needed in terms of FA to compute an FFT of sizeN.
Butterfly structure
FA
4 parallel BPE architectures
R-24 [13], [14]
12
n
2
(
log
4
⁡
N
-
1
)
+
20
(
p
log
4
⁡
N
-
1
)
+
32
p
log
4
⁡
N
R-24 [15]
12
n
2
(
log
4
⁡
N
-
1
)
+
20
p
(
log
4
⁡
N
-
1
)
+
32
p
log
4
⁡
N
R-24 [16]
12
n
2
log
4
⁡
(
N
-
1
)
+
20
p
log
4
⁡
(
N
-
1
)
+
32
p
log
4
⁡
N
R-22 [17]
9
n
2
(
log
4
⁡
N
-
1
)
+
15
p
(
log
4
⁡
N
-
1
)
+
32
p
log
4
⁡
N
R-23 [17]
12
n
2
(
log
4
⁡
N
-
1
)
+
20
p
(
log
4
⁡
N
-
1
)
+
16
p
log
4
⁡
N
R-24 [17]
10.5
n
2
(
log
4
⁡
N
-
1
)
+
17.5
p
(
log
4
⁡
N
-
1
)
+
16
p
log
4
⁡
N
Proposed  MuxMDC-R22
9
n
2
(
log
4
⁡
N
-
1
)
+
15
p
(
log
4
⁡
N
-
1
)
+
8
p
log
4
⁡
N
8 parallel BPE architectures
R-2 [18]
24
n
2
(
log
4
⁡
N
-
1
)
+
40
p
(
log
4
⁡
N
-
1
)
+
32
p
log
4
⁡
N
R-2 [19]
24
n
2
(
log
4
⁡
N
-
1
)
+
40
p
(
log
4
⁡
N
-
1
)
+
64
p
log
4
⁡
N
R-24 [20]
24
n
2
(
log
4
⁡
N
-
1
)
+
40
p
(
log
4
⁡
N
-
1
)
+
64
p
log
4
⁡
N
R-22 [17]
18
n
2
(
log
4
⁡
N
-
1
)
+
30
p
(
log
4
⁡
N
-
1
)
+
32
p
log
4
⁡
N
R-23 [17]
18
n
2
(
log
4
⁡
N
-
1
)
+
30
p
(
log
4
⁡
N
-
1
)
+
32
p
log
4
⁡
N
-
21
n
2
-
35
p
R-24 [17]
21
n
2
(
log
4
⁡
N
-
1
)
+
35
p
(
log
4
⁡
N
-
1
)
+
32
p
log
4
⁡
N
-
24
n
2
-
40
p
Proposed MuxMDC-R23
21
n
2
(
log
8
⁡
N
-
1
)
+
35
p
(
log
8
⁡
N
-
1
)
+
16
p
log
8
⁡
N
16 parallel BPE architectures
Proposed MuxMDC-R24
51
n
2
(
log
16
⁡
N
-
1
)
+
85
p
(
log
16
⁡
N
-
1
)
+
32
p
log
16
⁡
N
Proposed MuxMDC-R42
45
n
2
(
log
16
⁡
N
-
1
)
+
75
p
(
log
16
⁡
N
-
1
)
+
64
p
log
16
⁡
NFigure 20
Complex multiplier using three real multipliers and five real adders.For the four parallel pipelined FFTs of sizeN, it seems that the R-22 butterfly cited in [30] will have approximately the same amount of FA as the proposed MuxMDC-R22 according to Figure 21. Our proposed MuxMDC-R22 will achieve a reduction in the usage of FA by a factor that ranges between 1.17 and 1.34 (Figure 21).Figure 21
Comparison between the different butterflies’ structures in terms of full adder needed to compute the 4 parallel pipelined FFTs of sizeN (multiplier on 16 bits and adder on 32 bits).With regard to the eight parallel pipelined FFTs of sizeN, it seems that the proposed MuxMDC-R23 will achieve a reduction in the usage of FA by a factor that ranges between 1.4 and 1.9 in comparison to the other cited butterflies as shown in Figure 22.Figure 22
Comparison between the different butterflies’ structures in terms of full adder needed to compute the 8 parallel pipelined FFTs of sizeN (multiplier on 16 bits and adder on 32 bits).Since the implementation of higher radices by means of the radix-2α/4β butterfly is feasible, the optimal pipelined FFT is achieved by the two stage FFT as shown in Figure 23 where the use of complex memories between the different stages is completely eliminated and the delay required to fill up the pipeline is totally absent.Figure 23
Two stage pipelined FFT (or array structure) with a feedback network [23].


## 6. Conclusion

It has been shown that the higher radix FFT algorithms are advantageous for the hardware implementation, due to the reduced quantity of complex multiplications and memory access rate requirements. This paper has presented an efficient way of implementing the higher radices butterflies by means of the radix-2α/4β kernel where serial parallel models have been represented. The proposed optimized different structures with a scheduling scheme of complex multiplications are suitable for embedded FFT processors. Furthermore, it has been proven that the higher radices butterflies could be obtained by reusing the block circuit diagram of the radix-2α/4β butterfly. Based on this concept, the hardware resources needed could be reduced which is highly desirable for low power consumption FFT processors. The proposed method is suitable for large pipelined FFTs implementation where the performance gain will increase with an increasing FFTs’ radix size. This structure is also appropriate for SIMD implementation on some of the latest DSP cards.



---

*Source: 690594-2014-05-13.xml*