TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol. 12, No. 8, August 201
4, pp. 6224 ~ 6229
DOI: 10.115
9
1
/telkomni
ka.
v
12i8.522
4
6224
Re
cei
v
ed
No
vem
ber 2
8
, 2013; Re
vi
sed
Febr
uary 19,
2014; Accept
ed March 6, 2
014
Impact of FFT Algorithm Selection on Switching
Activity and Coefficient Memory Size
Imran Ali Qureshi*
1
, Faha
d Qureshi
2
1
School of Infor
m
ation a
nd El
e
c
tronics, Beij
in
g
Institute of
T
e
chn
o
lo
g
y
, Beij
ing, P.R Chi
n
a
2
Mehran U
n
ive
r
sit
y
of Eng
i
ne
erin
g and T
e
ch
nol
og
y, Jamsh
o
ro Pakista
n
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: i.ali1
225
@
y
a
hoo.com
A
b
st
r
a
ct
T
he bi
nary tree
deco
m
positi
o
n
allow
s
for o
b
ta
inin
g
a
larg
e n
u
mber
of alg
o
ri
thms th
at can
be us
e
d
to calcu
l
ate t
h
e fast F
ouri
e
r
transform. T
h
i
s
pap
er
a
n
a
l
y
z
e
s
the
differe
nces a
m
on
g t
hese
al
gorith
m
s in
terms of sw
itchin
g activity, w
h
ich is relate
d to t
he pow
er consu
m
pti
o
n
of the circuit, and si
z
e
of the
coefficie
n
t
me
mor
i
es, w
h
ic
h i
s
relat
ed
to
the
are
a
of th
e c
i
r
c
uit.Experi
m
en
tal res
u
lts show the most efficient
alg
o
rith
ms
in
term of
are
a
a
nd
pow
er c
ons
umptio
n.
F
u
rth
e
rmore, th
e
pa
per s
how
s the
i
m
p
o
rtance
of
a
prop
er al
gorith
m
se
lectio
n, si
nce
effici
ent al
gorith
m
s c
an l
ead to s
a
vi
n
g
s
of upto 4
5
%
in ter
m
s of th
e
coefficie
n
t me
mory a
nd ev
e
n
greater th
an
50% in ter
m
s
of sw
itching a
c
tivity w
i
th respect to other l
e
ss
efficient on
es.
Ke
y
w
ords
: switching activity, twiddle fa
ctor, bin
a
ry tree, pip
e
lin
ed arc
h
itect
u
re, coefficie
n
t me
mory
Copy
right
©
201
4 In
stitu
t
e
o
f
Ad
van
ced
En
g
i
n
eerin
g an
d
Scien
ce. All righ
ts reser
ved
.
1. Introduc
tion
The
di
screte Fouri
e
r
t
r
an
sf
orm (DFT)
is one of
the m
o
st imp
o
rta
n
t
algorith
m
s in
the field
of digital
sign
al processin
g
.
It transfo
rm
s a
sig
nal
in
the time
doma
i
n into the
fre
quen
cy do
ma
in.
The DFT is u
s
ed in
multipl
e
appli
c
ation
s
, inclu
d
ing
spectrum an
al
ysis an
d ort
h
ogon
al freq
u
ency
division
multi
p
lexer
(OF
D
M). The
r
e
are vario
u
s
efficient m
e
thod
s for computi
ng DFT h
o
we
ver
the Fast Fo
urier Tran
sform
(FFT)
ba
sed
on the Co
ol
e
y
-Tukey algo
rithm [1] is mostly used
as i
t
redu
ce
s the numbe
r of operatio
ns fro
m
O(N
2
) fo
r the DFT to O(N log N) f
o
r the FFT. To
efficiently implement the FFT algo
rith
ms, vari
ou
s h
a
rd
wa
re arch
itecture
s hav
e been propo
sed,
su
ch a
s
i
n
-pl
a
ce
archite
c
t
u
re
s [2], pip
e
lined
archit
ectures [3-7].
Among th
ese, the pip
e
lin
ed
architectu
re
are p
r
efe
rre
d
,
as this a
r
ch
itectu
re
provides
high p
e
rf
orma
nce with
an acce
ptab
le
hard
w
a
r
e
co
st. In additi
on, pipelin
ed
hard
w
a
r
e a
r
chite
c
tu
re
s
are hi
ghly regula
r
, there
b
y
automatically gene
rating F
FTs of vario
u
s
length
s
.
A pipeline
d
FFT a
r
chitect
u
re
co
nsi
s
ts
of a serie
s
of stage
s i
n
whi
c
h a
dditio
n
s a
n
d
twiddle facto
r
multiplication
s
are calculat
ed [8, 9
]. However, the di
stributio
n of the twiddle fa
ctors
among
the
di
fferent sta
g
e
s
of the FF
T d
epen
ds
on
th
e algo
rithm t
hat is
ch
osen
[9, 10]. In [1
0],
all the possi
ble radix-2 F
FT algorith
m
s ba
s
ed on
binary tree
were pre
s
e
n
ted. These F
F
T
algorith
m
s in
clud
e all the different dist
ri
bution
s
of
twiddle facto
r
be
tween the
sta
ges of the FF
T.
A twiddle fa
ctor multipli
cat
i
on is
actu
all
y
a rotation,
i.e, a multipli
cation
by a
complex
numbe
r with a
mag
n
itude
equal
to
on
e, so only
the
p
hase of the
in
put data i
s
affected.
Differe
nt
method
s hav
e been
sug
g
e
sted in the l
i
terature for
twiddl
e factor multipliers. For in
stan
ce
the
coeffici
ents
{
±
1,±j} fo
r a
W4 multiplie
r can be
ea
sily solved
by interchan
ging
real an
d imagi
nary
parts or chan
ging the
sig
n
of the inp
u
ts. In
[11, 12]
twiddle fa
cto
r
multiplie
r fo
r {
W
8
,W
16
, and
W
32
} u
s
ing
consta
nt multi
p
licatio
ns
we
re p
r
op
osed,
whe
r
e
a
s i
n
[
13] a meth
od
to increa
se
the
accuracy
of
t
he rotation
s based on scaling
th
e
coe
fficients
ha
s
been
p
r
e
s
ent
ed. Th
e u
s
e
of
gene
ral com
p
lex multiplie
r is still the
most com
m
on way to
calculate the twiddle fa
ctor
multiplicatio
n whi
c
h preco
m
putes a
nd st
ores th
e twid
dle factors in
memory.
In this work
we analy
z
e the impa
ct of
the FFT algorithm selecti
on on the switchi
n
g
activity (SA)
and on the size of the co
effi
cient mem
o
ry. The swit
chin
g activity [14],
α
, is
th
e
numbe
r of 0
→
1 tran
sitio
n
s bet
wee
n
su
ccessive coeffi
cient that
are re
ad fro
m
the coefficient
memory. The
SA is related to the power co
nsum
pti
on of the circuit, being abl
e to approxi
m
ate
the dynamic
power [15] by
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Im
pact of FFT Algorithm
Selectio
n on Switchi
n
g
Ac
tiv
i
ty
and Coeffic
i
ent
… (Im
r
an Ali Qureshi)
6225
2
dyn
a
mi
c
c
l
k
L
d
d
Pf
C
V
(1)
Whe
r
e f
clk
i
s
t
he
clo
ck f
r
eq
uen
cy , V
dd
is the
supply v
o
ltage, a
nd
C
L
is the
load
cap
a
cita
nce.
On
the othe
r ha
n
d
, the mem
o
ry size is an i
ndicator
of th
e area of th
e
circuit. Th
us,
ea
ch al
gorith
m
pre
s
ent
s
a tradeoff b
e
twe
en a
r
ea
a
nd
power co
nsu
m
ption,
which allo
ws fo
r
selectin
g the
most
efficient algo
rithm.
The pa
per i
s
orga
nized a
s
follows. In the next se
ctio
n we b
r
iefly review the rad
i
x-2 FFT
algorith
m
s b
a
se
d the on
binary tre
e
d
e
com
p
o
s
ition
and the FF
T architectu
re that is use
d
for
cal
c
ulatin
g t
he al
gorith
m
s. Se
ction II
I discu
s
se
s
the switchin
g a
c
tivity of the
coeffici
ent
memori
es. S
e
ction IV p
r
e
s
ent
s expe
ri
mental re
sults on th
e swi
t
ching
activity and the to
tal
coef
f
i
ci
ent
memory
si
ze.
I
n
se
ct
ion V concl
u
si
on
s are given.
2. The Binar
y
Tree Repre
sentation o
f
FFT Algorith
m
s
2.1. Algorith
m
s
A binary tre
e
ca
n be u
s
ed to
rep
r
e
s
ent the
Co
oley-Tu
k
ey
FFT algo
rith
m. This
rep
r
e
s
entatio
n is ba
sed o
n
the decom
positio
n of
an N-point FF
T into two smaller FF
Ts.
As a
result we
ca
n
brea
k the
N-point FFT int
o
N1
-poi
nt a
nd N2-p
oint
FFTs th
at are name
d
a
s
i
nner
and oute
r
FF
Ts, re
spe
c
tively. In a binary tree, each node h
a
s lea
v
es whi
c
h
co
rre
sp
ond
s to the
inner
and o
u
ter FFT
s, wh
e
r
ein the left l
eaf co
rre
sp
o
nds to the
N1 FFTs
of N2-poi
nts a
nd
the
right leaf to the N2 FFT
s of N1- p
o
ints. T
he root
no
de i
s
assig
ned th
e power
of two weig
ht of the
total FFT l
e
n
g
th an
d the
subno
de
s a
r
e
assign
ed th
e
power
of two
weig
ht for th
e
inne
r a
nd
ou
ter
FFTs,
re
spe
c
tively. As a consequ
en
ce,
the wei
ght
of
a no
de i
s
th
e sum of the
weig
hts
of its
sub
nod
es. When the tree
is com
p
lete, all leaves correspon
d to butterfly and node
s rep
r
e
s
e
n
t
the twid
dle f
a
ctor multipli
cation. Fi
gu
re 1
sh
ows t
he p
o
ssible
decompo
sitio
n
of a
no
de
with
weig
ht 6, i.e., a 2
6
= 64-p
o
i
n
t FFT.
Figure 1. De
compo
s
ed Alg
o
rithm
s
for 64
Point FFTs
With this
rep
r
ese
n
tation, a
numbe
r of p
o
ssible
radix-2 FFT alg
o
rit
h
ms
we
re ge
nerate
d
in [10]. The
gene
rated
al
gorithm
s h
a
ve a different
twiddle fa
ctor multiplier fo
r each sta
ge
but
have the
sa
me n
u
mbe
r
o
f
butterfly op
eration
s
. T
h
e
num
ber of
radix-2
2
n
-p
oi
nt FFT
algo
rit
h
ms
gene
rated u
s
i
ng bina
ry tree
s wa
s sho
w
n
in [10] to be.
2.2. Architec
ture
Single del
ay feedba
ck (S
DF)
pipelin
e
d
FFT a
r
chitecture sho
w
n in Figu
re
2. In this
architectu
re
sample
s ente
r
in natural order a
nd
o
u
tp
uts are delive
r
ed in
bit-reversed o
r
d
e
r [
16].
The num
be
r of stage
s is
calcul
ated a
s
n = log
2
(N).
Each stage consi
s
ts
of a
radix-2 b
u
tterfly, a
compl
e
x multiplier, buffers
for stori
ng da
ta and me
mo
ries fo
r the twiddle facto
r
coefficient
s. Any
FFT al
gorith
m
gen
erated
by the
bin
a
ry tre
e
d
e
compo
s
ition
can b
e
ma
pp
ed o
n
the
S
D
F
architectu
re.
(2
(
1
)
)
!
!1
!
n
nn
(2)
V
6
5
1
2
4
66
3
3
III
I
6
4
2
IV
II
6
5
1
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 8, August 2014: 622
4 –
6229
6226
These alg
o
rit
h
ms o
n
ly differ in the
cont
ents
of the t
w
iddl
e facto
r
coeffici
ent m
e
mori
es,
i.e. M1, M2, . . . , Mn
−
1. A
s
the th
rou
g
h
put of SDF
a
r
chite
c
tu
re i
s
one
sampl
e
per
clo
c
k cy
cl
e
,
whi
c
h mea
n
s
that a coeffici
ent is fetch
e
d
from the me
mory every cl
ock cycl
e.
Figure 2. Single Del
a
y Feedba
ck Pipeli
ned FFT
Hardwa
re Archite
c
ture
The ge
ne
rati
on of the
coe
fficients that
are u
s
e
d
for t
he rotatio
n
s i
s
detail
ed in
Figure 3.
Firs
t,
φ
is ge
nerate
d
fro
m
the index, b
e
ing
φ
a
nu
mber i
n
the
range [0,
N
−
1] that define
s
a
rotation by:
2
j
N
e
(3)
Figure 3. Twi
d
le Factor Multiplication
The g
ene
rati
on of
φ
fro
m
the index i
s
e
x
plained i
n
d
e
tail in [10].
Once
φ
is obt
ained, its
value is
use
d
to rea
d
th
e add
re
ss
of a twi
ddl
e fa
ctor m
e
mo
ry in whi
c
h th
e co
rrespon
d
i
ng
coef
f
i
ci
ent
s,
i
.
e.
,
cos
2
()
N
an
d
sin
2
()
N
, are
sto
r
ed. The
s
e
coefficient
s a
r
e inp
u
t to th
e
compl
e
x multi
p
lier in
ord
e
r to calculate
ro
tation of i
nput
sa
mple
In o
r
der to
red
u
ce
the
si
ze
of th
e
coeffici
ent m
e
mory, it is
a common
practi
ce to
utilize
the quart
er symme
try
property of
the
coeffici
ents [17]. Thi
s
me
ans that o
n
ly twiddl
e
fa
cto
r
s correspon
ding to
an
gle
s
in
the
ran
g
e of
0/
2
need to be consi
dered. Multiplication fo
r ot
her value
s
can be obtai
ned by app
ro
priat
e
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Im
pact of FFT Algorithm
Selectio
n on Switchi
n
g
Ac
tiv
i
ty
and Coeffic
i
ent
… (Im
r
an Ali Qureshi)
6227
swappi
ng of real and ima
g
i
nary output
s and an a
ppr
o
p
riate si
gn o
r
by rotating any outstandi
n
g
/2,
, or 3
/2 rad in the following stag
e, si
milar to wh
at is don
e in rad
i
x-2
2
FFTs.
3. S
w
i
t
c
h
ing Activ
i
t
y
The s
w
it
c
h
ing
ac
tivity,
α
, in (1
) i
s
the
a
v
erage
num
b
e
r of
0
→
1 and 1
→
0
transitio
ns
per
clo
ck
cycle. In a twid
dle facto
r
m
u
ltiplicat
ion, t
he Switching
Activity betwee
n
su
cce
s
sive
coeffici
ents is defined
in te
rms of
Hamm
ing di
stan
ce f
o
r e
a
ch
coeffi
cient tran
sitio
n
. In pipeli
n
e
d
SDF a
r
chite
c
ture
the t
w
iddl
e facto
r
are p
r
ecomp
u
ted
a
nd
stored i
n
l
ook-up
table
s
and
a
r
e
fed t
o
the com
p
lex
multiplier in
each
cycl
e. The sequ
en
ce of the
co
efficient fed
to the com
p
l
e
x
multiplier affe
cts th
e SA.T
he al
gorith
m
s gen
erate
d
b
y
the bin
a
ry t
r
ee
have
eith
er
sam
e
twi
d
dle
factor comple
xity with different po
sition
o
f
twiddl
e
fa
ctor
or differe
nt twi
ddle fac
t
or
c
o
mplexity. In
both ca
se
s th
e twiddle fa
ctor memo
ry a
nd swit
chi
ng
activity differ betwe
en the
s
e algorith
m
s.
4. Experimental Re
sults
We
con
s
id
er
all the co
efficient se
quen
ces of the
co
mplex multipli
ers
re
sulting
from the
FFT algo
rith
ms ba
se
d on
binary tre
e
s.
These are
initially represented with
1
6
-bit word l
e
ngth
(re
al and ima
g
inary
)
. The acce
ss
seq
u
e
n
ce i
s
t
hen computed to o
b
tain the re
su
lting activity.
The switchi
n
g
activity is then norm
a
lized
as:
2.
SA
NS
A
bN
(4)
Whe
r
e SA i
s
the
swit
chin
g a
c
tivity, N is th
e FFT
length
and
b
is th
e word
length
of th
e
coeffici
ents.
The no
rmali
z
ed SA for the
algorithm
s
with varying F
FT length
s
is sho
w
n in Fi
g
u
re
4, illustrating
the be
st an
d
the worst case. On the
oth
e
r h
and, th
e
norm
a
lized S
A
as
a fun
c
ti
on
of the
wo
rdl
ength i
s
sho
w
n i
n
Fi
gure
5. As
ca
n
b
e
note
d
i
n
Fi
gure
4
(
a
)
, fo
r a
fixed
N t
he
norm
a
lized S
A
is almo
st con
s
tant with
the numbe
r of bits, b. This
sho
w
s th
at the swit
chi
n
g
activity is p
r
oportio
nal to
the si
ze
of
the FFT.
Li
kewi
se, for a
fixed b the
n
o
rmali
z
e
d
S
A
is
con
s
tant
with
the FFT
size, as
sho
w
n
in Figu
re 5
(
a
)
. The
r
efore, the switchi
n
g
activity is al
so
prop
ortio
nal to the wordlen
g
th.
Furthe
rmo
r
e,
Figure 4(b
)
and
5
(
b) sho
w
t
he ratio
s
betwe
en the
algorithm
s
with the
maximum
an
d minim
u
m
switchi
ng
activ
i
ties. It can
b
e
note
d
th
at the
ratio
between th
e m
a
ximum
and th
e mi
ni
mum
swit
chin
g a
c
tivity increases with
th
e len
g
th
of th
e FFT.
Fu
rthe
rmore, the
ratios
are
bigg
er th
an 2
in
mo
st ca
se
s,
whi
c
h lea
d
s to
savings of m
o
re th
an
50%
in the
swit
ching
ac
tivity.
The
algo
rithm
s
with th
e lo
west
swit
chin
g
activity are
summari
ze
d in
Tabl
e 1
for d
i
fferent
FFT len
g
ths.
The al
go
rith
ms
sho
w
n
in
the tabl
e turn out to
be t
he radix-2
3
decimatio
n in
time
(DIT
) algo
rith
m in all the case
s. As me
n
t
ioned ab
ove, we calculate
the SA from the W1
6, due
to
this
fac
t
radix- 2
3
DIT h
a
v
e minimum
SA. Similarly, one
c
an
exp
e
ct that if th
e
twiddl
e fa
cto
r
s
from W
2
k
and
highe
r resolu
tion multiplie
rs was con
s
id
ered, th
e be
st algorithm
would b
e
a
rad
i
x-
2
k
−
1
DIT algori
t
hm.
(a)
Normali
z
e
d
swit
chin
g a
c
tivity
(b)
Ratio bet
wee
n
the ma
ximum and m
i
nimum
SA
Figure 4. Normalize
d
Switching Activity
of Coe
fficie
n
t Memori
es of t
he Differe
nt Algorithm
s of
the FFT Size,
N, for 16 bit Coeffici
ents
16
32
64
128
256
512
102
4
0
0.5
1
1.5
2
Number of point,
N
Normalized SA
Max.
Min.
16
32
64
128
256
512
102
4
1
2
3
4
Number of point,
N
Ratio (max./min.)
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 8, August 2014: 622
4 –
6229
6228
(a) Norm
alized switchi
ng
activity
(b)
Ratio bet
wee
n
the ma
ximum and
minimum SA
Figure 5. Normalize
d
Switching Activity
of the
Coeffici
ent Memori
es of the Differe
nt Algorithms
as a Fu
nction
of the Word
Length of t
he
Coeffici
ents,
b, for a 256 Point FFT
Table 1. Twi
d
le Facto
r
Di
stribution of the
FFT Algorith
m
s with the
Minimum SA
Number of P
o
ints, N
Stage Numbe
r
1 2 3 4
5
6
7
8
9
16 W
16
W
8
W
4
32 W
4
W
32
W
8
W
4
64 W
8
W
4
W
64
W
8
W
4
128 W
16
W
8
W
4
W
128
W
8
W
4
256 W
4
W
32
W
8
W
4
W
256
W
8
W
4
512 W
8
W
4
W
64
W
8
W
4
W
512
W
8
W
4
1024
W
16
W
8
W
4
W
128
W
8
W
4
W
1024
W
8
W
4
(a) T
o
tal coef
ficient memo
ry
(b)
Ration b
e
twee
n the ma
ximum and th
e
minimum total coefficient memory
Figure 6. Total Coeffici
ent Memory of th
e Differ
ent Al
gorithm
s a
s
a
Function of t
he FFT Size,
N,
for 16 bit Coe
fficients
With respe
c
t to the si
ze
of the coefficie
n
t memo
ry, Figure
6
sho
w
s the m
a
xim
u
m an
d
minimum
tota
l co
efficient
memory
si
ze
that the
diffe
rent
algo
rith
ms
req
u
ire.
As h
app
ened
with
the swit
chin
g
activity, it can be note
d
that t
here is a big difference betwee
n
the memo
ries
requi
re
d by different algorit
hms. The sa
vings va
ry fro
m
a 14% for a 16-p
o
int FF
T to 45% for
a
1024
-poi
nt FFT.
Finally, Figure 7 sho
w
s th
e trade
off betwee
n
co
effici
ent memo
ry and switchin
g activity
for all the
alg
o
rithm
s
ba
se
d on bi
nary trees th
at
ca
n
be u
s
ed to
ca
lculate
a 25
6-point FFT. It ca
n
be note
d
tha
t
there a
r
e
b
i
g differe
nce
s
am
ong th
e
algo
rithms b
o
th in
swit
chi
ng a
c
tivity and
memory
si
ze.
Furthe
rmo
r
e,
the alg
o
rithm
s
with
both l
o
w switching
a
c
tivity and m
e
mory
size
can
be d
e
termi
n
e
d
from
Figu
re 7. Th
ese
are
also
sam
e
alg
o
rithm
s
having th
e lo
we
st switchin
g
ac
tivity.
4
6
8
12
16
2
4
0
0.5
1
1.5
2
Wordlength,
b
Normalized SA
Max.
Min.
4
8
12
16
24
3
2
1
2
3
4
Wordlength,
b
Ratio (max./min.)
16
32
64
128
256
512
102
4
0
200
400
600
Number of point,
N
Total coeff. memory
Max.
Min.
16
32
64
128
256
512
102
4
1
1.2
1.4
1.6
1.8
2
Number of point,
N
Ratio (max./min.)
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Im
pact of FFT Algorithm
Selectio
n on Switchi
n
g
Ac
tiv
i
ty
and Coeffic
i
ent
… (Im
r
an Ali Qureshi)
6229
5. Conclusio
n
This p
ape
r shows that bo
th
the power con
s
um
ption
due to switching a
c
tivity
and th
e
total size of the coefficient
memori
es i
n
FFT ha
rd
wa
re a
r
chitectu
res a
r
e di
re
ctly related to t
he
FFT algo
rith
m that is use
d
. It has bee
n sho
w
n that
the swit
chin
g
activity is proportio
nal to both
the FFT
size
and th
e n
u
m
ber of bit
s
of
the coeffi
cie
n
t
s. Finally, by
co
mpa
r
ing
the
re
sults of
all
the po
ssible
algorith
m
s th
at ca
n b
e
g
e
nerate
d
u
s
in
g the
bina
ry t
r
ee
de
com
p
o
s
ition
s
it
can
be
noted that sel
e
cting an effi
cient algo
rith
m can lea
d
to significa
nt re
ductio
n
s in te
rms of switchi
ng
activity and memory si
ze.
Referen
ces
[1]
J Coo
l
e
y
, J T
u
ke
y
.
A
n
a
l
gor
ithm for the m
a
chin
e calc
ul
ati
on of c
o
mpl
e
x
F
ourier s
e
ries.
Math. Com
p
.
,
196
5; 19: 297
–
301.
[2]
SC Moon, IC Park. Area-
efficient memory
-based
archit
ect
u
re for fft processing.
Proc. IEEE Int. Symp.
Circuits and Sy
stem
s
. 20
03; 5
:
V–101– V
–10
4.
[3]
S He, M T
o
rkelson. D
e
sig
n
a
nd im
plem
enta
t
ion of
a 10
24-
poi
nt pi
pel
ine
F
F
T
processor
.
Proc. IEEE
Custo
m
Integr
ated Circ
u
its C
onf.
, 1998: 13
1
–13
4.
[4]
H Groginsky
,
G Works. A pi
p
e
lin
e fast F
ouri
e
r transform.
IEEE Trans. on Com
p
uters
. 1
970; C-
19(1
1
):
101
5-10
19.
[5]
W
Han, AT
Erdog
an, T
Arsl
an, M Hasa
n. High-
perform
a
n
ce lo
w
-
po
w
e
r
F
F
T
cores.
ET
RI Journal
.
200
8; 30(3): 45
1–4
60.
[6]
M Garrido, KK Parhi, J Gr
a
j
al. A p
i
pe
lin
ed
F
F
T
architecture for r
eal-v
a
l
ue
d si
gna
ls.
IEEE Trans.
Circuits Syst. I
. 2009; 5
6
(12):
263
4–
264
3.
[7]
MAS´anch
e
z,
M Garrido, M
L
L´op
ez, J Graj
al. Im
plem
enti
ng F
F
T
-based
digit
a
l c
han
ne
li
zed rec
e
iv
ers
on FPGA platforms.
IEEETra
ns. Aerosp. Electron. Syst.,
20
08; 44(4): 1
567
–15
85.
[8] L
W
anhamm
a
r
,
DSP Integrated Circ
u
its
. Academ
ic Press. 199
9.
[9]
M Garrido. Effi
cient
hard
w
a
r
e
architect
u
res f
o
r t
he c
o
mp
utation
of the
F
F
T
and other
re
lated
sig
n
a
l
process
i
ng a
l
g
o
rithms in re
al
time. Ph.D. dissert
ation, Un
iv
ersid
ad Pol
i
t´e
c
nica d
e
Madri
d
. 2009
[10]
F
Qureshi, O
Gustafsson. Gener
ation
of al
l radi
x-
2 fast F
ourie
r transfo
rm algorit
hms usin
g bin
a
r
y
trees.
Proc. Europe
an Co
nf. Circuit T
heory D
e
sig
n
. 201
1.
[11]
S Le
e, Y Ju
n
g
, J Kim. L
o
w
compl
e
xit
y
pipeline FFT
processor f
o
r MIMO-OFDM sy
stems.
IEICE
Electron
ics Express
. 200
7; 4(
23): 750
–7
54.
[12]
F Qureshi, O
Gustafsson. Lo
w
-
complexit
y
const
ant m
u
lti
p
licati
o
n
bas
e
d
on
trigo
nom
etric id
entiti
e
s
w
i
t
h
ap
plic
atio
ns to F
F
T
s
.
IEICET
rans. F
und
amenta
l
s
. 201
1; E94-A,(11).
[13]
M Garrido, O Gustafsson, J Grajal. Accur
a
te rotations based on
coefficient scaling.
IEEE Trans.
Circuits Syst. II
, 2011.
[14]
JM W
u
, YC Fan. Co
efficient
orderi
ng b
a
se
d pip
e
li
ne
d F
F
T
/IFFT
w
i
th m
i
nimum s
w
itc
h
i
ng activit
y
for
lo
w
po
w
e
r
w
i
max
c
o
mmunication s
y
stem.
Proc. IEEE Tenth Intern. S
y
m
p
. Cons
umer Electronics.
200
6: 1–4.
[15]
F
Najm. A
sur
v
e
y
of
po
w
e
r
estimatio
n
tec
hni
ques
i
n
V
L
SI circuits.
IE
EE T
r
ans. V
e
r
y
Lar
ge
Scal
e
Integratio
n (VL
S
I) Systems,
. 1994; 2(4): 4
46–
455.
[16]
M Garrido, J Grajal, O Gustafsson.
Optimum circuits
for bit reversal.
IEEE Trans. Circuits Syst. II
.
201
1.
[17]
HY Le
e, IC Park. Bala
nced
bin
a
r
y
-tre
e d
e
co
mp
ositio
n for are
aefficie
n
t
pipe
lin
ed F
F
T
processing
.
IEEE Trans. Circuits and Syst
. I
. 2007; 54(
4): 889–
90
0.
Evaluation Warning : The document was created with Spire.PDF for Python.