Internati
o
nal
Journal of Ele
c
trical
and Computer
Engineering
(IJE
CE)
V
o
l.
6, N
o
. 4
,
A
ugu
st
2016
, pp
. 15
51
~
1
559
I
S
SN
: 208
8-8
7
0
8
,
D
O
I
:
10.115
91
/ij
ece.v6
i
4.9
218
1
551
Jo
urn
a
l
h
o
me
pa
ge
: h
ttp
://iaesjo
u
r
na
l.com/
o
n
lin
e/ind
e
x.ph
p
/
IJECE
Desi
gn of 8-p
o
int
DFT Based on Radem
a
ch
er Funct
i
ons
Z
u
lfika
r
, Hubbul Wa
lida
i
ny
Department o
f
Electrical Engin
e
eri
ng, S
y
iah Kuala University
, Ind
onesia
Article Info
A
B
STRAC
T
Article histo
r
y:
Received Oct 20, 2015
Rev
i
sed
Ap
r
26
, 20
16
Accepted
May 10, 2016
This paper
presents a new circuit de
sign for 8-point DFT algorith
m
based on
product of Rademacher fun
c
tions. Th
e d
e
signed cir
c
uit
is basically
c
onst
r
uc
te
d ba
se on 8-poi
nt
DFT
de
c
i
ma
ti
on i
n
time
t
h
a
t
ma
i
n
ly
const
r
uc
t
of
two 4-point
and
four 2-poin
t
D
F
Ts. However,
the op
eration of
the d
e
sign
circu
it is
differ
e
nt. It u
til
ized
the advan
t
age
s
of Radem
acher functio
n
s
simplicity
.
Th
er
efore, th
e propo
sed design
is co
nstructed
from o
u
r previous
design 4-point
DFT which is
based on
produ
ct of R
a
demach
er functions.
Some analy
s
is
upon number
ty
pes
,
in
tern
al connections and complex
conjuga
te of
the
res
u
lts
to a
c
hi
ev
e the m
o
re
effi
ci
ent c
i
rcui
t hav
e
been m
a
de
.
Therefor
e,
instead of four, th
e
proposed design
requires only
three 2-poin
t
DFTs. Again, two output results of th
e design DFT have been rem
oved since
the
y
ar
e equ
a
l i
n
term
s of m
a
gnitude
to
the o
t
her results, but two negativ
e
circu
it
are r
e
qu
ired as
a com
p
ens
a
tion
.
M
o
reo
v
er,
the pr
eviou
s
des
i
gned
circu
it of 4
-
poin
t
DF
T has
be
en
repl
aced
with
t
h
e new
circu
it d
e
s
i
gn.
This
circu
it
is special designed
for
non-sta
ndalon
e
used, th
e circuit must be
integr
ated
insid
e
the proposed 8-
point DFT.
Keyword:
4
-
po
in
t DFT
8
-
po
in
t DFT
FFT
Radem
acher functions
Twiddle Fact
or
Walsh transfo
r
m
s
Copyright ©
201
6 Institut
e
o
f
Ad
vanced
Engin
eer
ing and S
c
i
e
nce.
All rights re
se
rve
d
.
Co
rresp
ond
i
ng
Autho
r
:
Zu
lfik
ar,
Depa
rt
m
e
nt
of
El
ect
ri
cal
Engi
neeri
n
g
,
Syiah
Ku
ala
Un
iv
ersity,
Jl Syech
Ab
dur
Rauf
, D
a
r
u
ss
ala
m
,
Banda Aceh, Indonesia.
Em
a
il: zu
lfik
arsafri
n
a
@u
nsyiah
.ac.i
d
1.
INTRODUCTION
No
d
oub
t th
at Fou
r
ier tran
sform
s
is u
s
ed
ub
iq
u
itou
s
. Th
e Fo
urier algo
rithm
s
is av
ailab
l
e
in
ter
m
s o
f
bot
h co
nt
i
nue
and di
sc
ret
e
m
odel
s
. Di
sc
ret
e
m
odel
of
Fou
r
i
e
r w
h
i
c
h i
s
oft
e
n cal
l
e
d Di
scret
e
Fo
uri
e
r
Tran
sf
orm
s
(D
FT) i
s
m
o
re sui
t
a
bl
e for a
ppl
i
cat
i
on si
n
ce the d
e
v
e
lop
m
en
t o
f
co
m
p
u
ting
mach
in
es th
at li
mits
th
e ab
ility o
f
calcu
l
atio
n
.
Un
l
i
k
e
d
i
screte, t
h
e con
tin
u
e
m
o
d
e
l is
v
e
ry
d
i
ffi
cu
lt to
b
e
im
p
l
e
m
en
ted
.
The
de
vel
o
pm
ent
of
Fo
u
r
i
e
r t
r
ans
f
orm
s
has
been
do
ne si
nc
e ab
o
u
t
a ce
nt
u
r
y
ag
o.
H
o
wev
e
r,
beca
us
e
o
f
t
h
e
hu
g
e
num
b
e
r o
f
app
licatio
n
s
, it is still attracted
scien
tists to
d
e
v
e
l
o
p
a m
o
re and
m
o
re efficien
t
an
d fast
alg
o
rith
m
s
fo
r
i
m
p
l
e
m
en
tin
g
th
e tran
sform
s
in
th
e app
licatio
n
s
.
Du
h
a
m
e
l an
d Veterli summarized
, an
alyzed
and
pr
o
v
i
d
e
d
som
e
suggest
i
ons
o
f
t
h
o
s
e d
e
vel
o
pm
ent
i
n
19
9
0
[
1
]
.
Th
e
m
o
st
si
gni
fi
cant
im
pro
v
e
m
ent
of
Fo
uri
e
r
i
s
w
h
e
n
C
ool
ey
a
n
d
Tu
key
i
n
t
r
o
d
u
ced a
m
e
t
hod
fo
r
fact
o
r
i
zat
i
on
of
i
t
[
2
]
.
Af
t
e
r t
h
at
,
t
h
ous
an
d
s
num
ber
of
pa
p
e
r a
ppea
r
s
fo
r i
m
pl
em
ent
i
ng F
o
u
r
i
e
r i
n
a
ppl
i
c
at
i
ons.
Al
t
e
rnat
i
v
el
y
,
sci
e
nt
i
s
t
s
have
devel
ope
d t
h
e
al
gor
ith
m
s
o
f
Fou
r
ier tran
sform
s
th
at co
m
b
in
es
W
a
lsh
and
Fo
uri
e
r t
r
a
n
sf
orm
s
[3]
-
[
5
]
. The de
vel
o
p
m
ent
s
i
s
based
on t
h
e si
m
p
l
i
c
i
t
y
cal
cul
a
t
i
on of
Wal
s
h t
r
ans
f
o
r
m
s
th
at o
f
ten
ignor
ed
i
n
th
e
p
r
evio
u
s
r
e
search
es. Tho
s
e al
g
o
r
ith
m
s
su
ch
as
Walsh
tr
an
sfo
r
m
s
is ado
p
t
ed
thr
oug
h
facto
r
ization
of in
term
ed
iate tran
sform
s
T for calcu
la
tion
of
DFT
coe
fficients
[3].
Monir T et al
the
n
pr
o
pose
d
t
h
e e
ffi
ci
ent
com
b
i
n
at
i
on
of
DFT
and
Wal
s
h ca
l
c
ul
at
i
ons. T
h
i
s
t
echni
q
u
e i
s
use
d
t
o
pe
rf
or
m
Fast
Walsh
Had
a
mard
Tran
sfo
r
m
s
(FWHT)
b
y
u
tilizin
g
Radi
x
-
4
[4
]. Later th
en
, th
e efficien
t alg
o
rith
m
o
f
cal
cul
a
t
i
ng b
o
t
h
Wal
s
h
t
r
an
sf
orm
s
and
D
F
T t
r
ans
f
o
r
m
s
usi
n
g
t
h
e fam
ous R
a
di
x-
2 was
al
so pu
bl
i
s
he
d [
5
]
.
Th
ose p
r
evi
o
u
s
com
b
i
n
at
i
on a
l
go
ri
t
h
m
s
are desi
gne
d f
o
r
par
a
l
l
e
l
bot
h i
n
put
and
out
put
. T
h
i
s
l
eads t
o
hu
ge
num
ber o
f
m
e
m
o
ry
resources
whi
c
h i
s
not
s
u
i
t
a
bl
e fo
r
sm
al
l
ci
rcui
t
appl
i
cat
i
o
ns. A
m
e
t
hod f
o
r re
d
u
ci
n
g
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE
Vo
l. 6
,
N
o
. 4
,
Au
gu
st 2
016
:
15
51
–
1
559
1
552
ci
rcui
t
res
o
urc
e
s has
bee
n
pr
op
ose
d
i
n
[
6
]
.
The ci
rc
ui
t
i
s
desi
g
n
e
d
by
t
a
ki
n
g
i
n
p
u
t
seri
al
l
y
and t
h
e
o
u
t
put
i
s
gat
h
e
r
ed
i
n
pa
ral
l
e
l
.
The
p
r
o
pos
ed
m
e
t
hod
use
d
t
o
desi
gn
4
-
p
o
i
n
t
DFT
t
h
at
ad
o
p
t
s
beh
a
vi
o
r
of
h
o
w
Wal
s
h
t
r
ans
f
o
r
m
s
i
s
perf
orm
e
d.
Th
e pr
ev
iou
s
D
F
T
h
a
s b
e
en
d
e
sign
ed
on
ly f
o
r
4-
po
in
t,
wh
ich
is v
e
ry sim
p
le an
d
rarely u
s
ed
in
th
e
appl
i
cat
i
o
n. I
n
t
h
e real
a
ppl
i
cat
i
on, i
t
i
s
req
u
i
r
e
d
a
DF
T w
h
i
c
h a
b
l
e
t
o
pe
rf
orm
hi
ghe
r t
h
a
n
4
poi
n
t
t
r
ans
f
o
r
m
a
ti
on.
The
r
ef
ore
,
i
n
t
h
i
s
pape
r,
we
pr
o
pose
a
desi
gn
o
f
8-
p
o
i
n
t
DFT
t
h
at
i
s
c
o
nst
r
uct
e
d
by
us
i
ng t
h
e
pre
v
i
o
us 4
-
p
o
i
n
t
D
F
T desi
g
n
.
Tw
o 4-
p
o
i
n
t
DFT an
d fo
u
r
2-
p
o
i
n
t
DFT
a
r
e
re
qui
re
d
i
n
t
h
e
p
r
o
p
o
sed
de
s
i
gn.
Thi
s
pa
per i
s
o
r
ga
ni
zed as f
o
l
l
ows:
som
e
basi
c t
h
eori
es o
f
DFT are c
ove
r
e
d i
n
t
h
e ne
xt
sect
i
on. T
h
en
i
n
t
h
e sect
i
o
n 3
,
st
ep by
st
e
p
c
i
rcui
t
desi
g
n
fo
r area e
ffi
ci
enc
y
of 8
-
poi
nt
D
F
T i
s
desc
ri
be
d i
n
det
a
i
l
.
Sect
i
on
4
vi
ews t
h
e a
n
al
y
s
i
s
of res
u
l
t
s
and a fe
w
di
scussi
o
n
s
of t
h
e
pr
o
pose
d
de
si
g
n
. Fi
nal
l
y
, t
h
e
concl
u
si
o
n
s a
n
d som
e
su
gg
estion
s
fo
r fu
tu
re work
s are
p
r
esen
ted in
sectio
n
5
.
2.
THEORIES
2.
1.
2-P
o
i
n
t
and
4
-
Poi
n
t
Di
scre
te
Fo
uri
er T
r
an
sfor
ms
DFT
p
l
ays a
v
e
ry im
p
o
r
tan
t
ro
le i
n
alm
o
st all d
i
g
ital ap
p
licatio
n
s
.
For ex
am
p
l
e, in
th
e fields of
d
i
g
ital sign
al pro
cessing
(DSP),
sp
ectru
m
an
alysis and
filtering
pro
cess.
Man
y
scien
tists propo
sed th
e
th
eory
and im
ple
m
entation
of how
DFT
efficiently use
d
. T
h
e
basic calcu
lation
o
f
DFT is
usin
g equ
a
tion
(1) as
f
o
llow
[
7
]-[9
],
(1
)
whe
r
e, twiddle
factor
(W
N
) m
a
y
be e
v
al
uat
e
d acc
or
di
n
g
t
o
equat
i
o
n
(
2
) a
s
f
o
l
l
o
w:
(2
)
Sm
al
l
poi
nt
nu
m
b
er (N) o
f
D
F
T i
s
very
si
m
p
l
e
and m
a
y
be oft
e
n i
g
n
o
re
d i
n
di
sc
ussi
o
n
. H
o
weve
r
hi
g
h
er
N-
p
o
i
n
t
DFTs a
r
e c
onst
r
uct
e
d f
r
o
m
sm
all
e
r one
s. F
o
r i
n
st
anc
e
, t
h
e
8-
poi
nt
DFT
base
d
o
n
FF
T
al
go
ri
t
h
m
i
s
const
r
uct
e
d u
s
i
ng
2
-
p
o
i
n
t
a
n
d 4
-
poi
nt
DF
Ts. T
h
e 2
-
p
o
i
n
t
DF
T m
a
y
be cal
cul
a
t
e
d
easi
l
y
according to e
quations
(1) a
n
d (2). For instance,
give
n x(
n) = {2,
5}, let us first
com
pute
twiddle
factors for
th
e DFT.
W
2
0
= c
o
s
(0
)
–
j si
n (
0
) =
1
W
2
1
= c
o
s
(
π
) – j
si
n
(
π
) =
-
1
There
f
ore,
t
h
e
out
put
res
u
l
t
s
m
a
y
be n
o
w
o
b
t
ai
ned as
f
o
l
l
o
w:
X(
0)
=
x(
0)
W
2
0
+ x(
1)W
2
0
=
2(1) +
5(1) =
2 + 5 =
7
X(
1)
=
x(
0)
W
2
0
+ x(
1)W
2
1
= 2(
1)
+ (-
1)
(5
) =
2 – 5
=
-
3
The ci
rc
ui
t
f
o
r
im
pl
em
ent
i
n
g
t
h
e
2-
poi
nt
D
F
T i
s
very
eas
y
t
o
be
desi
g
n
e
d si
nce i
t
i
s
r
e
qui
red
o
n
l
y
t
h
e ad
di
t
i
on an
d su
bt
ract
i
o
n p
r
oces
s. Let
us
no
w m
ove t
o
t
h
e cal
cul
a
t
i
on
of
hi
g
h
er
poi
nt
(N)
DFT
(4
-p
oi
nt
)
.
For
e
x
am
pl
e, g
i
ven
x
(
n
)
= {
2
,
4
,
3
,
5
}, t
h
e t
w
i
ddl
e
fact
o
r
s ca
n
be e
v
al
uat
e
d
as f
o
l
l
o
w
s
:
W
4
0
= c
o
s
(0
)
–
j si
n (
0
) =
1
W
4
1
= c
o
s
(
π
/2) –
j
sin
(
π
/2) = -j
W
4
2
= c
o
s
(
π
) – j
si
n
(
π
) =
-
1
W
4
3
= c
o
s
(3
π
/2
) – j sin
(3
π
/2) =
j
There
f
ore,
the
trans
f
orm
a
tion resu
lts m
a
y b
e
calcu
lated
as
fo
llo
w:
X(
0)
=
x(
0)
W
4
0
+ x(
1)W
4
0
+
x(
2)
W
4
0
+
x(
3)W
4
0
=
2 +
4 +
3 +
5 =
1
4
X(
1)
=
x(
0)
W
4
0
+ x(
1)W
4
1
+
x(
2)
W
4
2
+
x(
3)W
4
3
= 2 - 4j
– 3
+ 5j
= -1
+ j
X(
2)
=
x(
0)
W
4
0
+ x(
1)W
4
2
+
x(
2)
W
4
0
+
x(
3)W
4
2
= 2 - 4
+ 3
- 5
=
-
4
X(
3)
=
x(
0)
W
4
0
+ x(
1)W
4
3
+
x(
2)
W
4
2
+
x(
3)W
4
1
= 2
+ 4
j
– 3 - 5j
=
-
1
- j
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Design
o
f
8
-
p
o
in
t DFT Ba
sed
o
n
Ra
d
e
ma
ch
er Fun
c
tion
s
(Zu
lfika
r
)
1
553
It
can
b
e
see
n
t
h
at
t
h
e
c
o
m
put
at
i
o
n
p
r
oce
s
s o
f
4-
p
o
i
n
t
D
F
T t
h
at
i
s
de
m
onst
r
at
ed
her
e
w
oul
d
n
o
t
requ
ire m
u
ltip
l
i
catio
n
.
Th
is calcu
l
atio
n
p
r
o
c
ess is sim
ilar t
o
the
2
-
p
o
i
n
t
DFT’s. However,
b
ecau
s
e it
d
o
es
cont
ai
n
s
i
m
aginary
pa
rt
,
we sho
u
l
d
sepa
rat
e
t
h
e res
u
l
t
s
and st
ore i
t
i
n
t
o
di
ffe
rent
bu
ff
ers. T
h
i
s
p
r
oce
ss ha
s
been
dem
onst
r
at
ed be
f
o
re i
n
20
1
5
[6]
.
2.
2.
Rademacher Functi
ons
Som
e
researchers
pre
f
er
re
d
per
f
o
r
m
i
ng Wal
s
h t
r
a
n
s
f
o
r
m
s
based u
p
on
pr
o
duct
of
R
a
dem
acher
fu
nct
i
o
ns. T
h
i
s
i
s
fou
nd t
o
b
e
m
o
re app
r
op
ri
at
e for ci
rc
ui
t
real
i
zat
i
on [9
]
-[1
3]
. The R
a
dem
acher fu
nc
t
i
ons
itself are
defi
ned as
stated i
n
equation
(3).
(3
)
whe
r
e
ϕ
(0
,x)=1
an
d th
e
sign
um
fu
n
c
tio
n Sgn
(
y) is
d
e
term
i
n
ed as
fo
llows,
(4
)
In practice, th
e Rad
e
m
ach
er fu
n
c
tion
s
can be easily g
e
n
e
rated
b
y
sim
p
ly
u
s
ing
a coun
ter circu
it.
3.
DESIGN OF 8
-
POINT
DIS
CRETE FOURIER TRANSFORMS
3.
1.
General Circuit
Desi
gn
Thi
s
pa
per p
r
o
pos
es t
h
e ci
rcu
i
t
desi
gn o
f
8-
poi
nt
DFT ba
s
e
d o
n
pr
o
duct
of R
a
dem
acher fu
nct
i
o
ns.
Th
e
d
e
sign
ed
circu
it is co
n
s
t
r
u
c
ted
fro
m
th
e prev
i
o
u
s
work of
4
-
po
in
t
DFT
[6
] co
m
b
in
ed
with
t
h
e
8
-
po
in
t
DFT
deci
m
a
ti
on i
n
t
i
m
e desi
gn. Fi
gu
re 1
sh
o
w
s t
h
e
8-
p
o
i
n
t
DFT
base
d o
n
deci
m
a
ti
on i
n
t
i
m
e
. The st
ruct
ure
co
nsists of several sm
aller p
o
in
t of
DFTs. Th
e stru
ctur
e al
so
requires
s
o
me arithm
e
tic
process
suc
h
a
s
real
m
u
l
tip
licatio
n
an
d im
ag
in
ary m
u
l
tip
licatio
n
.
Fi
gu
re 1.
Sc
he
m
e
of 8-
p
o
i
n
t
DFT [
1
]
Inpu
t d
a
ta
x
[
x
0
, x
1
, x
2
, x
3
, x
4
, x
5
, x
6
, x
7
]
will b
e
tran
sform
e
d
in
to
frequ
e
n
c
y
do
m
a
in
and
b
e
co
m
e
X[
X
0
, X
1
, X
2
, X
3
, X
4
, X
5
, X
6
, X
7
].
Ev
en
inpu
ts [x
0
, x
2
, x
4
, x
6
] are p
a
ssed
th
ro
ugh
th
e fi
rst (#1
)
4
-
po
in
t
DFT.
Mean
wh
ile, odd
inp
u
t
[x
1
, x
3
, x
5
, x
7
] are
pass
ed through t
h
e second
(#2)
4-poi
nt DFT. T
h
e calculation
proces
s
of b
o
t
h
4-
p
o
i
n
t
DFTs i
s
per
f
o
r
m
e
d based o
n
pro
d
u
ct
of R
a
dem
acher fu
nc
t
i
ons [
6
]
.
Let
’
s
assum
e
t
h
at
U
0
, U
1
,
U
2
, U
3
are results o
f
t
h
e
first
4-po
in
t
DFT and
L
0
, L
1
, L
2
, L
3
ar
e
r
e
su
lts of
t
h
e secon
d
4-
poin
t
D
F
T.
Fo
ur bl
oc
ks of
2-
p
o
i
n
t
DFT a
r
e used t
o
t
r
a
n
sf
orm
t
e
m
porary
resul
t
s
(U a
n
d
L) t
o
be t
h
e fi
nal
8-
p
o
i
n
t
DFT resu
lt X(k
)
. On
ly in
pu
ts o
f
th
e
first b
l
ock
of 2-po
int
DFT a
r
e conne
cted directly from
te
m
porary results
,
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE
Vo
l. 6
,
N
o
. 4
,
Au
gu
st 2
016
:
15
51
–
1
559
1
554
o
t
h
e
rs h
a
v
e
to
b
e
m
u
ltip
lied
with
twidd
l
e facto
r
s. Th
es
e mu
ltip
licatio
n
s
pro
cess will b
e
ev
alu
a
ted
later in
th
e
next
sect
i
o
n
s
.
The
pr
oces
s
ha
ve t
o
be c
o
n
s
i
d
ered
as a
d
di
t
i
onal
res
o
urce
t
h
at
i
s
use
d
besi
d
e
t
h
e m
a
i
n
bl
o
c
ks
of
4-
p
o
i
n
t
DFTs
a
n
d
2
-
poi
nt
D
F
Ts.
Int
e
r
n
al
ci
r
c
ui
t
o
f
4-
poi
nt
DFT i
s
sh
o
w
n
i
n
Fi
g
u
r
e
2.
Fi
gu
re 2.
I
n
t
e
r
n
al
ci
cui
t
of 4
-
poi
nt
D
F
T [6]
Inpu
t d
a
ta
x
is
co
nn
ected in parallel to
neg
a
t
i
v
e
circu
it, m
u
ltip
lex
e
rs and
d
a
ta buffers. Th
e
n
e
g
a
ti
v
e
circu
it is u
s
ed
to
p
r
ov
id
e
n
e
gativ
e v
a
lu
e
o
f
i
n
pu
t d
a
ta
x
b
a
sed
on
th
e selectio
n
of m
u
ltip
l
e
x
e
rs. Sin
ce t
h
e first
row
o
f
DFT matrix
co
n
t
ains
o
n
l
y
p
o
sitiv
e valu
e, th
e co
nn
ec
tio
n
o
f
d
a
ta i
n
p
u
t
x
t
o
th
e buffers is m
a
d
e
directly
in
ord
e
r t
o
av
oid
m
u
ltip
lex
e
rs. Th
e selected
v
a
lu
es w
ill
b
e
p
a
ssed
thro
ugh bu
ffers to
either real accu
m
u
lato
rs
o
r
im
ag
in
ary accu
m
u
lato
rs co
n
t
ro
lled b
y
t
h
e sign
al g
e
n
e
rated
fro
m
co
n
t
ro
l circu
it. Fin
a
lly, all sto
r
ed
v
a
lu
es
i
n
out
p
u
t
bu
ffe
rs are pa
ssed
o
u
t
an
d co
nsi
d
e
r
ed as t
h
e
DFT
resul
t
s
. Dat
a
bu
ffe
rs are c
o
n
t
rol
l
e
d by
t
h
e s
i
gna
l
whi
c
h i
s
gene
r
a
t
e
d by
c
o
nt
ro
l
ci
rcui
t
,
b
u
t
t
h
e
out
put
b
u
f
f
e
rs i
s
not
.
The
s
e b
u
f
f
ers
are
use
d
t
o
st
ore
val
u
es
t
e
m
porary
be
fo
re
t
h
ey
passe
d out
.
3.
2.
Type of
Num
b
er
The ci
rc
ui
t
sc
h
e
m
e
i
n
Fi
g
u
re
1 s
h
o
w
s
bl
oc
k
s
o
f
4
-
poi
nt
D
F
Ts,
2-
p
o
i
n
t
D
F
Ts a
nd t
w
i
d
d
l
e fact
or
s i
n
gene
ral
vi
ew
. I
n
o
r
de
r t
o
i
n
t
e
grat
e bl
ock
s
an
d com
p
o
n
ent
s
,
i
t
requi
res s
p
ec
i
f
i
c
han
d
l
i
ng t
h
at
m
a
y
i
nvol
v
e
real
and
i
m
agi
n
ary
num
bers.
T
h
e con
n
ect
i
o
ns be
t
w
een bl
oc
ks
o
r
com
ponents t
h
at involve
bo
th
real and
im
a
g
in
ary
num
bers
req
u
i
r
es m
o
re ci
rcu
i
t
.
Fi
gu
re 3 s
h
ows al
l
p
o
ssi
ble of real
(not
ed “R”) a
nd i
m
aginary (not
ed “I”
)
num
bers f
o
r p
r
ocessi
n
g
t
h
e 8-
poi
nt
D
F
T.
Figu
r
e
3. Type of
n
u
m
b
e
r
s
fo
r conn
ectio
n
s
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Design
o
f
8
-
p
o
in
t DFT Ba
sed
o
n
Ra
d
e
ma
ch
er Fun
c
tion
s
(Zu
lfika
r
)
1
555
It is assu
m
e
d
t
h
at in
pu
ts of 8-po
in
t DFT are all
real num
bers. T
h
en
base
d on the calcul
a
tion inside
4
-
po
in
t DFT, t
h
e tem
p
o
r
ary
resu
lts (U
and L) will b
e
i
n
real, im
ag
in
ary o
r
m
i
g
h
t
con
t
ain
s
b
o
t
h
real an
d
im
agi
n
ary
n
u
m
bers. Th
ose t
y
pe o
f
n
u
m
b
ers hav
e
bee
n
de
ri
ve
d f
r
om
t
h
e t
w
i
ddl
e
fact
or
of
bot
h 4
-
poi
nt
DF
T
bl
oc
ks. L
e
t
us
con
s
i
d
er
b
o
t
h
4-
p
o
i
n
t
D
F
T
bl
ock
s
, Ta
bl
e 1
s
h
o
w
s al
l
p
o
ssi
bl
e n
u
m
b
er t
y
p
e
s of
t
h
e
resul
t
fo
r al
l
in
pu
t real
nu
mb
er
s.
Tabl
e 1. Pos
s
i
b
l
e
t
y
pes
o
f
nu
m
b
ers
base
d o
n
t
w
i
ddl
e fact
o
r
of 4
-
p
o
i
n
t
DF
T
k
T
w
iddle Factor
Type of Input
Type of Outpu
t
0 W
4
0
Co
s (0
) –
j Sin
(0
)
1
x
0
: Real
U
0
: Real
1 W
4
1
Cos
(2
π
/4) – j Sin
(2
π
/4
) -
j
x
2
: Real
U
1
: Real
+ I
m
aginary
2 W
4
2
Cos
(4
π
/4) – j Sin
(4
π
/4
) -
1
x
4
: Real
U
2
: Real
3 W
4
3
Cos
(6
π
/4) – j Sin
(6
π
/4) j
x
6
: Real
U
3
: Real
+ I
m
aginary
So
m
e
resu
lts of th
e secon
d
4-po
in
t
DFT
(L
1
, L
2
, L
3
) are
m
u
l
tip
lied
with
twi
d
d
l
e
facto
r
s
(W
8
1
, W
8
2
and W
8
3
). Th
ese m
u
lt
ip
licatio
n
s
can
b
e
ex
amin
ed
as fo
llow,
(R
+ I) x W
8
1
=
(R +
I)
x
(C
os
(2
π
/
8
) – j Si
n (
2
π
/8)
)
=
(R +
I
)
x (R
+ I
)
=
R
+ I
(5)
(R) x W
8
2
= (R
) x
(C
os (4
π
/
8
)
– j Si
n (
4
π
/8
)) = (
R
)
x
( I)
=
I
(
6
)
(R
+ I) x W
8
3
=
(R +
I)
x
(C
os
(6
π
/
8
) – j Si
n (
6
π
/8)
)
=
(R +
I
)
x (R
+ I
)
=
R
+ I
(7
)
As th
e resu
lt, after
p
e
rform
i
n
g
all
of
2
-
po
in
t
D
F
T pro
cesses, th
e
ou
tpu
t
of 8
-
po
in
t
D
F
T co
n
t
ains r
eal
and im
aginary num
ber e
x
ce
pt for
X
0
a
nd
X
4
w
h
ich
co
n
t
ain
o
n
l
y r
eal
nu
m
b
er
s. Th
is is
b
e
cau
s
e
b
o
t
h
inputs o
f
t
h
e fi
rst
(
#
1)
2-
p
o
i
n
t
DF
T are co
nt
ai
n real
num
bers o
n
l
y
. These a
n
al
y
s
i
s
pl
ay
a very
im
port
a
nt
t
h
i
ng
i
n
det
e
rm
i
n
i
ng t
h
e am
ount
o
f
bu
ffe
rs
req
u
i
r
ed f
o
r i
m
pl
em
ent
i
ng t
h
e
c
i
rcui
t
,
si
nce
t
h
e real
a
n
d i
m
agi
n
ary
num
bers will be placed or stored in di
ffe
rent
buffers. Th
is
design will be furt
her analyze
d
for determ
ining the
am
ount
of
re
q
u
i
r
e
d
b
u
ffe
r. T
h
e c
o
n
n
ect
i
o
ns
t
h
at
i
n
v
o
l
v
e b
o
t
h
real
an
d i
m
agi
n
ary
re
q
u
i
res t
w
i
ce n
u
m
b
er
o
f
bu
ffe
r
fo
r st
ori
n
g
data tem
por
arily
.
3.
3.
Interc
onnec
t
Configur
ation
The de
si
g
n
ed
8-
p
o
i
n
t
DF
T m
a
i
n
l
y
req
u
i
r
es t
w
o
4-
p
o
i
n
t
D
F
Ts an
d f
o
u
r
2
-
poi
nt
DFT
s
. T
h
ese am
ount
of
DFTs will requi
res
huge
num
b
ers of circ
uit. Howeve
r,
in term
s of circuit persp
ective, there
is a space to
reduce t
h
e circuit.
A
dept
h
analysis is re
quire
d
for
det
e
r
m
i
n
i
ng w
h
i
c
h
pa
rt
of
t
h
e wh
ol
e
ci
rc
ui
t
can b
e
opt
i
m
i
zed. In
t
h
e p
r
evi
o
u
s
s
ect
i
on, t
h
e t
y
p
e
of
n
u
m
b
ers
use
d
f
o
r
co
n
n
ect
i
ng
bl
oc
ks
has
been
det
e
r
m
i
n
ed.
Here
, we pr
ovi
de deep
anal
y
s
i
s
of
t
h
ose n
u
m
b
ers
.
The res
u
lts of 8-point DFT s
h
ows
the unique phenom
ena, because so
m
e
of them
co
m
p
lex conjugat
e
t
o
t
h
e
ot
he
r
res
u
l
t
[
7
]
,
[
8
]
.
F
o
r
exam
pl
e gi
ve
n
x={1
,2
,3
,4
,5,6,
7
,
8
}, t
h
e
DFT
results a
r
e
X={
3
6, -
4
+
9
.
6
6i, -
4
+4i,
-4+
1
.
6
6i, -
4
,
-
4
-
1
.
6
6i, -
4
-4i,
-4
-9
.6
6i}.
Wh
ere,
X
1
is
co
m
p
lex
conj
ug
ate with X
7
, X
2
is com
p
lex c
onjugate
with
X
6
an
d X
3
is com
p
lex c
o
njugate wit
h
X
5
. In
gene
ral, t
h
is is accordi
n
g
to equation
(8).
(8
)
wh
ere N=4
,
8
,
1
6
, ….. Th
is b
e
h
a
v
i
or also
si
m
ilar
to
th
e 4
-
po
in
t DFT resu
lts, wh
ere
U
1
=U
3
* an
d L
1
=L
3
*.
Fi
gu
re
4 s
h
ows
t
h
e m
a
ppi
n
g
o
f
al
l
p
o
ssi
bl
e c
o
m
p
l
e
x co
n
j
u
g
a
t
e
resul
t
s
of
t
h
e desi
gne
d
8-
p
o
i
n
t
DFT
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE
Vo
l. 6
,
N
o
. 4
,
Au
gu
st 2
016
:
15
51
–
1
559
1
556
Fi
gu
re 4.
C
o
m
p
l
e
x
c
o
nj
u
g
at
e resul
t
s
By d
e
term
in
in
g
co
m
p
lex
conj
ug
ate
o
f
so
m
e
DFT
resu
lts, the circu
it can
b
e
op
ti
m
i
zed
.
4.
CIR
C
U
IT CO
MPLE
X
I
T
Y
I
n
th
e
pr
ev
i
o
us sectio
n, an
al
ysis o
f
nu
m
b
er
’
s
ty
pe a
n
d
c
o
m
p
l
e
x co
n
j
u
g
a
t
e
of
t
h
e
res
u
l
t
s
has
bee
n
m
a
de. T
h
ere
f
o
r
e, t
h
e
desi
g
n
e
d
ci
rc
ui
t
m
a
y
no
w
be
o
p
t
i
m
i
zed
by
re
d
u
ci
n
g
un
nee
d
ed
co
m
ponent
s
or
b
l
ock
s
.
Howev
e
r, th
ere is a co
st fo
r th
is im
p
r
o
v
e
m
e
n
t
.
From
the Figure 4, it can
be s
een that t
h
e re
s
u
lts of
2
nd
and
4
th
2
-
poi
nt
DF
Ts are c
o
m
p
l
e
x c
o
n
j
ugat
e
to each
other.
There
f
ore, one
of thes
e
bloc
ks can
be
rem
oved.
As a c
o
ns
eque
nce
of re
m
oving the
bl
ock, it is
req
u
i
r
e
d
a
ne
g
a
t
i
v
e ci
rcui
t
.
An
ot
he
r a
d
van
t
age
of
rem
o
v
i
ng t
h
e
DFT
b
l
ock,
ei
t
h
er
c
o
m
ponent
of
t
w
i
d
dl
e
factor W
8
1
or
W
8
3
i
s
not
re
q
u
i
r
e
d
any
m
ore.
Let
us rem
ove t
h
e l
a
st
bl
ock
of
2-
p
o
i
n
t
DF
T, as a res
u
l
t
,
t
w
i
d
dl
e
factor W
8
2
c
a
n
be al
s
o
rem
ove
d.
Thi
s
l
e
a
v
e c
o
n
n
ect
i
o
ns
fr
o
m
U
3
and L
3
di
sco
nnect
e
d
.
Th
e m
u
ltip
lica
tio
n
pro
c
ess in th
e
W
8
2
al
so can be r
e
m
oved beca
use t
h
e
m
a
gni
t
ude
of
W
8
2
is -1.
Based
on
prev
i
o
u
s
an
alysis o
f
twid
d
l
e factors
m
u
ltip
li
cat
io
n
in
d
i
cated
in
eq
u
a
tion
(6
). Th
e resu
lt 4
-
p
o
i
n
t
DFT
L
2
m
a
y n
o
w
b
e
con
n
ected
d
i
r
e
ctly to
th
e input o
f
th
e t
h
ird
2
-
p
o
i
n
t
DFT
b
l
ock
an
d assu
m
e
d
it as an
im
ag
in
ar
y
num
ber. T
w
o
negat
i
v
e ci
rc
ui
t
s
are req
u
i
r
e
d
for c
o
m
p
ensat
i
on o
f
rem
ovi
n
g
o
n
e bl
oc
k o
f
2-
poi
nt
DFT.
These
ci
rcui
t
s
are sh
ow
n i
n
t
h
e
pa
rt
of Fi
gu
re 5
.
The fi
rst
ci
rc
ui
t
i
s
used t
o
m
a
ke a negat
i
ve val
u
e o
f
X
I1
and
considere
d
a
s
X
I7
an
d t
h
e sec
o
n
d
o
n
e i
s
use
d
t
o
m
a
ke a ne
gat
i
v
e
val
u
e
o
f
X
I5
a
n
d consi
d
ered as
X
I3
.
An
ot
he
r ef
fi
ci
ency
can be a
ppl
i
e
d i
n
t
h
e bot
h bl
oc
ks
of
4-
poi
nt
DFT
due t
o
t
h
e
u
n
c
o
n
n
ect
ed
of
resu
lt U
3
an
d L
3
. Figu
r
e
5 sh
ow
s the eff
i
cient cir
c
u
it d
e
sign of
8
-
p
o
i
n
t
DFT.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Design
o
f
8
-
p
o
in
t DFT Ba
sed
o
n
Ra
d
e
ma
ch
er Fun
c
tion
s
(Zu
lfika
r
)
1
557
Fi
gu
re
5.
Pr
o
p
o
se e
ffi
ci
ent
8
-
poi
nt
D
F
T
Fi
gu
re 6 s
h
o
w
s
t
h
e ci
rcui
t
of 2
-
p
o
i
n
t
DF
T. T
h
e ci
rcui
t
has b
een de
vel
o
ped
base
d o
n
t
h
e si
m
p
li
ci
t
y
of
twiddle fact
ors
W
2
0
= 1 a
nd
W
2
1
= -1 a
n
alyzed in section two. The
r
ef
ore, fo
r
d
e
term
i
n
ing
th
e resu
lts o
f
2
-
p
o
i
n
t
D
F
T,
j
u
st si
m
p
ly ad
d
an
d
sub
t
r
act
bo
th
g
i
v
e
n
inputs. Th
e sub
t
r
a
ctio
n
is p
e
r
f
ormed
th
ro
ugh
seco
nd
co
m
p
le
m
e
n
t
meth
od
b
y
ju
st si
m
p
ly in
v
e
rt x
1
and t
h
e
n
ad
d t
o
x
0
. Fi
g
u
r
e
7
sh
ow
s th
e m
o
dif
i
ed
4-
po
in
t DFT of
t
h
e
p
r
e
v
i
o
us pr
op
ose
d
o
n
e
[
6
]
.
Fi
gu
re 6.
C
i
rcu
i
t
of 2-
p
o
i
n
t
D
F
T
Fi
gu
re
7.
Pr
o
p
o
se m
odi
fi
ed
4
-
p
o
i
n
t
DFT
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE
Vo
l. 6
,
N
o
. 4
,
Au
gu
st 2
016
:
15
51
–
1
559
1
558
The m
odifie
d
circuit of
4-point DFT is m
o
re effi
cie
n
t, it utilized less accum
u
lator and
buffer. It c
a
n
be see
n
that t
h
ere a
r
e
four accum
u
lators
and four
output buffers
.
T
h
e pre
v
ious design re
quire
d
eight
accum
u
lators and eight out
put buffe
rs [6]. Howeve
r
this circuit cannot use
d
as
a single standal
one
ap
p
lication
,
it
m
u
st b
e
in
tegrated
tog
e
th
er t
o
form
th
e p
r
op
o
s
ed 8-po
in
t
DFT.
5.
CO
NCL
USI
O
NS
The
desi
g
n
e
d
ci
rcui
t
o
f
8-
p
o
i
nt
DF
T
based
o
n
pr
o
duct
o
f
R
a
dem
acher
f
unct
i
o
ns
has
bee
n
do
n
e
successfuly.
Initiall
y, the circuit cons
ists of
sm
a
ller DFT
blocks which
ar
e
two 4-point DFTs
and four
2-point
DFTs
. T
h
e a
n
al
y
s
i
s
of t
y
pe n
u
m
b
er
u
s
ed, i
n
t
e
r
n
al
con
n
ect
i
o
ns a
nd c
o
m
p
l
e
x
con
j
ugat
e
has
bee
n
accom
p
lished.
Based on thes
e, the efficient
8-poi
nt DF
T
has bee
n
achie
ved. The e
fficient circuit involve
d
t
w
o m
odi
fi
ed
4-
p
o
i
n
t
D
F
Ts
and t
h
ree
2
-
p
o
i
nt
DFTs
. M
o
r
e
ove
r, t
h
e de
si
gn
o
f
t
h
e m
odi
fi
ed
4-
poi
nt
D
F
T a
n
d
t
h
e si
m
p
l
e
2-p
o
i
n
t
D
F
T al
so
has
been c
o
n
s
t
r
uct
e
d
.
Se
ver
a
l
out
p
u
t
res
u
l
t
s of t
h
e
desi
g
n
ed
DF
T ha
ve
been
rem
oved si
nce
t
h
ey
are e
q
ual
i
n
t
e
rm
s of
m
a
gni
t
ude
, t
w
o
ne
gat
i
v
e ci
rc
ui
t
a
r
e re
q
u
i
r
e
d
as a
com
p
ensat
i
o
n.
ACKNOWLE
DGE
M
ENTS
Th
e au
tho
r
s
g
r
atefu
lly ack
nowledg
e th
e
finan
c
ial sup
p
o
r
t
fro
m
Syiah
Kuala Un
iv
ersity, Min
i
stry o
f
Edu
catio
n
and
Cu
ltu
r
e
, I
ndon
esia u
n
d
e
r p
r
o
j
ect
H
i
b
a
h Ber
s
aing
,
No
. 03
5
/
SP2H
/PL/
Dit.Litab
m
as/I
I
/
2
015
,
Feb
5
,
201
5.
REFERE
NC
ES
[1]
P. Duham
e
l and
M. Vett
erli
, “
F
ast Fourier Tr
an
sfor
m
s
: a tutori
al, r
e
vi
ew and a
s
t
ate of
the
art
,
”
Trans. Signal
Proc
e
ssing
, vo
l/issue: 19(4), pp.
259-299, 1990
.
[2]
J. W. Cooley
an
d J. W. Tukey
,
“
A
n
Algorithm
for the Machine
Calcul
a
tion of
Complex Fourier Series,”
Math
.
Comp.
, vol. 19
,
pp. 297-301
, 19
65.
[3]
S. Boussakta
an
d A. G. J.
Holt, “Fast algorithm for calculation
of
both Walsh-Hadamard and
Fourier tr
ansforms
(FWFTs),”
Electron. Letter
, vo
l/issue: 25(20), pp. 1352-1354, 198
9.
[4]
M. T. Hamood and S. Boussakta, “Fast Wa
lsh–Hadamard–Fourier transform algo
rithm,”
Trans. S
i
gnal Processing
,
vol/issue:
59(11)
, pp
. 5627-5631
, 2011.
[5]
T
.
Su a
nd F.
Yu,
“A
Fa
mily
of Fa
st
Hadamard–Fourier Transform Algorithms,”
Signal Processing Letters
,
vol/issue: 19(9), pp.
583-586
,
20
12.
[6]
Zulfik
ar and H.
Walidain
y
, “A Novel 4-Point Discrete F
ourier Transforms Circuit ba
sed on Product of Rademacher
Functions,”
IE
E
E
Proceed
ing of
International Co
nferenc
e
of
El
ect
rical Engin
eerin
g and Informatics
(
I
CEEI)
, Bali
,
Indonesia, Augu
st 10-11, pp. 142
-147, 2015
.
[7]
J. G. Proakis
an
d D. G.
Mano
lakis, “Digital sig
n
al pro
cessing:
pr
incipl
es
, algor
ithm
s
,
a
nd applications,”
4
th
e
d
.,
Pearson Prentice Hall, New
Jersey
, 2007
.
[8]
S
.
S
a
liv
ahan
an,
et a
l
., “Digital Signal Processing,”
McGraw Hill,
New Delhi,
2000.
[9]
M. G. Karpovsky
,
et al.
, “Spectr
a
l Logic and Its Applications for
The Design of Digital Dev
i
ces
,” John Wiley
&
Sons Inc. Publication
,
New Jers
ey
, 2008
.
[10]
M. Y. Zulfik
ar,
et al.
, “
FPGA Based Anal
y
s
is a
nd Multipli
cat
io
n of Digital Sig
n
als,”
Proce
e
din
g
of IEEE S
econ
d
International Co
nference on Ad
vances
in Compu
ting, Con
t
rol, an
d Telecommunication Techno
log
i
es (
A
CT 2010)
,
Jakarta, Indon
esia, pp
. 32-36
, 201
0.
[11]
M. Y. Zulfikar
,
et al.
, “FPGA B
a
sed Processing of Digita
l Signals using W
a
lsh Anal
y
s
is,
”
Pr
oceed
ing of IEE
E
International Co
nference on
Electrical, Co
n
t
rol
and Computer Engineering (
I
NECCE 2011)
, 21-22 June, Pah
a
ng
,
Malay
s
ia, pp
. 44
0-444, 2011
.
[12]
Zulfik
ar,
et a
l
.
,
“
A
Novel Co
m
p
lete Se
t of
W
a
lsh and Inv
e
rse Walsh Tr
ansforms for Si
gnal Processing,”
Proceed
ing of I
EEE Int
e
rnatio
nal Conferenc
e
on Co
mmunication Systems and Network Technologi
es (
C
S
N
T
2011)
, Katra, Jammu, 3-5 June,
pp. 504-509
, 20
11.
[13]
Zulfik
ar,
et a
l
.
,
“
F
PGA Based
Com
p
lete Set o
f
Walsh and In
verse Walsh Transforms for
Signal Processing,”
Transaction of
Electronics and
E
l
ec
trical
Engin
e
ering
, vo
l/issue:
18(8), pp
. 3-8
,
2
012.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Design
o
f
8
-
p
o
in
t DFT Ba
sed
o
n
Ra
d
e
ma
ch
er Fun
c
tion
s
(Zu
lfika
r
)
1
559
BIOGRAP
HI
ES OF
AUTH
ORS
Z
u
lfikar.
He was born in Beureunuen, Aceh
, Ind
onesia,
in 1975
.
He received his
B.Sc. degr
ee in
Electrical Engin
eering
from North Sumatera Univ
ersity
, M
e
dan, I
ndonesia, the M. Sc. Degr
ee
in
Electrical Engin
eering from Kin
g
Saud Univer
sity
, Riy
a
dh, Sau
d
i Arabia, in 19
99 and 2011,
respect
ivel
y.
He
joined as tea
c
hi
ng staff in the Departm
e
nt of Ele
c
troni
cs at Politekn
ik Calt
ex
Riau, Pekanb
ar
u, Indonesia in
2003. He served
as head of Industrial Contr
o
l Laborator
y
,
Politeknik
Cal
t
ex Riau
from
2003 to 2006
. I
n
2006, h
e
joi
n
ed th
e E
l
ectri
cal
Engin
eer
ing
Department, S
y
iah Kuala Univer
si
ty
. He h
a
s been appointed
as head of
Digital
Laborator
y
for
two suc
c
e
ssive
y
e
a
r
s.
His
c
u
rrent re
sea
r
c
h
inte
r
e
sts includ
e VLSI design and S
y
stem on Ch
ips
(SoC).
Hubbul Walida
i
ny
.
He was born in Banda Aceh, Aceh, I
ndonesia, in 1973. He graduated from
Electrical Engin
eering
Dep
a
rtment
at Gadjah Mada University
,
Yog
y
ak
arta, Indo
nesia,
in 1998,
The M
a
s
t
er De
gree in
Ele
c
tri
c
al Engin
eer
ing
from
Gadjah M
a
da Univers
i
t
y
, Yog
y
a
k
art
a
,
Indonesia, in
2
003. He
join
ed
in th
e Dep
a
rtme
nt of Electrical Engin
eer
ing
,
S
y
iah
Kuala
Universit
y
,
Aceh,
Indonesi
a in 2000,
as a teachi
ng staff
.
His
current
position
is th
e h
ead o
f
Tel
ecom
m
unicat
ion Labor
ator
y.
His
current r
e
s
e
a
r
ch int
e
res
t
s
in
cl
ude al
l is
s
u
es
in
Digital S
i
gn
al
Processing (DSP).
Evaluation Warning : The document was created with Spire.PDF for Python.