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
. 16
54
~
1
661
I
S
SN
: 208
8-8
7
0
8
,
D
O
I
:
10.115
91
/ij
ece.v6
i
4.1
046
9
1
654
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
New Decimation-in-Time Fast
Hartley Transform Algorithm
Mounir T. Hamood
Ele
c
tri
cal
Eng
i
n
eering
Depar
t
em
ent,
Un
iv
ersity
o
f
Tikrit, Iraq
Article Info
A
B
STRAC
T
Article histo
r
y:
Received
Mar 12, 2016
Rev
i
sed
Jun
15,
201
6
Accepted
Jun 28, 2016
This paper pr
esents a new alg
o
rithm
for fast calculation of the discrete
Hartley
tr
ansform (DHT) based on deci
mation-
in-time (DIT) approach. Th
e
proposed radix
fast Hartley
trans
f
orm (FHT
) DIT
algorithm has a
simple
butterf
ly
structur
e th
at off
e
rs flex
ibility
for v
a
riou
s powers-of-two transform
lengths, sign
ificantly
r
e
ducing
the comput
a
t
i
onal
c
o
mpl
e
xity
wi
th re
gul
a
r
bi
t
reversing orderf
or the output sequence.
The alg
o
rithm is derived through the
three-d
i
mensional ind
e
x mappin
g
approach and
b
y
incorpor
ating
two stages
of the signal
fl
ow graph into
an integ
r
at
ed b
u
tterf
l
y
. Th
e a
l
gorithm
is
im
plem
ented an
d its
arithm
e
t
i
c
com
p
lexit
y
h
a
s
been an
al
ys
ed a
nd com
p
are
d
with th
e
current
F
H
T algor
ithm
s
, rev
eal
i
ng th
at
it
is substant
ia
l
l
y
m
i
nim
i
z
e
the struc
t
ural
co
m
p
lexit
y
with b
e
tter ind
e
xing
arr
a
ngem
e
nt th
at is
suitable
for
effic
i
ent
im
plem
enta
tion
.
Keyword:
Decim
a
tio
n
-
in-ti
m
e
a
lg
o
r
ith
m
Fast transfo
r
m
alg
o
rith
m
s
d
i
screte h
a
rtley
tran
sfo
r
m
Rad
i
x
alg
o
rithm
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
:
M
o
u
n
i
r
Taha
Ham
ood,
Electrical Engi
neeri
n
g De
part
e
m
ent,
Co
lleg
e
o
f
Engin
eering
,
Un
iversity o
f
Tikrit,
Sal
a
h Al
-
D
een
G
ove
r
n
o
r
at
e, Ti
kri
t
,
Ira
q.
Em
a
il:
m.t.h
a
mo
od@tu
.edu
.iq
1.
INTRODUCTION
The discrete Hartley
trans
f
orm
(DH
T
) f
i
rst
in
trodu
ced
b
y
Bracewell [1
],[2
], has b
e
co
me
in
creasing
l
y
po
pu
lar as an
al
tern
ativ
e t
o
the d
i
screte
Fo
urier transfo
r
m
DFT fo
r app
licatio
n
s
i
n
vo
lv
i
n
g real
d
a
ta [3
]-[7
]
. Th
e DHT is main
ly attractiv
e fo
r t
h
e cas
e
of real
val
u
e
seque
nce, i
t
s
val
i
d
i
t
y
bei
ng m
a
d
e
p
o
s
sib
l
e b
y
the f
act th
at all th
e pr
op
er
ties
r
e
lated
to
th
e
D
F
T lik
e t
h
e
sh
if
ting
and
cir
c
u
l
ar
co
nvolu
tio
n
theorem
s
, are also applicable
t
o
t
h
e
D
H
T
[8
]
.
In
ge
neral
,
g
i
ven t
h
e
DHT
coefficients
of
a signal, it is easy t
o
com
put
e t
h
e co
rres
p
on
di
n
g
D
F
T coe
ffi
ci
ent
s
, an
d vi
ce
vers
a [9]
.
Ho
we
ver
,
t
h
e D
H
T
has
t
w
o a
dva
nt
age
s
ov
e
r
the DFT.
First, it is a real-to-real
tran
sform
,
so
n
o
co
m
p
lex
arith
m
e
t
i
c is
requi
red
.
Sec
o
nd
, t
h
e
D
H
T t
r
a
n
sfo
r
m
matrix
is symmetrical, an
d
th
er
ef
or
e t
h
e
f
o
r
w
ar
d and inver
s
e tr
an
sf
or
ms are i
d
en
tical. Th
e seco
nd
po
in
t is
q
u
ite sign
ifican
t b
ecau
s
e it mean
s th
at in
ap
p
lication
s
w
h
i
c
h
need
b
o
t
h
t
h
e fo
rw
ar
d a
nd i
nve
rse t
r
a
n
sfo
r
m
s
suc
h
as
fast c
o
nvolution al
gorithm
s
,
only
one routine for com
puting
t
h
e
DHT
is
necess
a
ry, since
it wi
ll also
per
f
o
r
m
t
h
e i
nverse
DH
T
.
Th
is feature is o
f
h
i
gh
im
p
o
r
tan
ce and
in
particu
l
ar fo
r t
h
e m
u
ltid
i
m
en
sio
n
a
l
appl
i
cat
i
o
ns w
h
ere
t
h
e
am
ou
nt
s of dat
a
a
r
e very
l
a
r
g
e [
10]
.
The am
ount
o
f
ari
t
h
m
e
t
i
cal
ope
rat
i
o
ns f
o
r
t
h
e com
put
at
i
o
n
o
f
t
h
e
D
H
T
i
s
seve
re a
n
d
needs
m
u
l
tip
licatio
n
s
an
d add
itio
ns, th
erefore th
e
fast Hartle
y tran
sfo
r
m
(FHT)
alg
o
rith
m
s
h
a
ve b
e
en
presen
ted
to
calculate the trans
f
orm
at high
spee
d
to
meet the requirem
ents of rea
l
tim
e
applications
. T
h
e first
FHT
algorithm
introduce
d
by Bracewell
[11] im
plem
ents the DHT in
c
o
m
p
lexity propo
rtionate to
u
s
i
ng
radi
x
d
ecim
a
ti
o
n
in
-tim
e (DIT) algorith
m
.
Fu
rt
h
e
r fast
al
go
ri
t
h
m
s
for
c
o
m
put
i
ng t
h
e
DHT
wi
t
h
p
o
w
ers
of
t
w
o t
r
a
n
s
f
o
r
m
l
e
ngt
h
s
are
d
e
vel
o
ped
by
M
eckeb
ur
g a
n
d Li
p
k
a
[1
2]
,
Kw
o
ng a
n
d S
h
i
u
[1
3]
an
d H
ou
[
14]
.
M
o
re
ove
r, S
o
r
e
ns
on
et al
[15] p
r
esen
ted
a co
m
p
lete set o
f
FHT algorith
ms u
s
ing
th
e index
i
ng
m
a
p
m
e
t
h
od
[16
]
, realizing
th
e alg
o
rith
m
s
d
ecim
a
tio
n
-
in-ti
m
e (DIT
) and decim
a
tion-in-fre
quency
(D
I
F
)
ap
pr
o
a
che
s
and
co
nfirm
e
d
th
at
all th
e well-kn
own
FFT algo
rith
m
s
can
al
so
b
e
u
s
ed
to th
e
calcu
lation
o
f
th
e FHT. Malv
ar
[1
7]
pr
o
pose
d
an FHT al
g
o
ri
t
h
m
based
on
di
scret
e
c
o
si
ne t
r
a
n
sf
r
o
m
(DC
T
) t
h
at
offe
r an i
m
pr
o
v
ed
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
New Decima
tio
n-in-Time Fast Hartley Tr
an
sfo
r
m
Al
go
rith
m (Mou
n
i
r T.
H
a
mo
od
)
1
655
com
put
at
i
onal
com
p
l
e
xi
t
y
.
C
h
an a
nd
Si
u
[1
8]
i
n
t
r
o
d
u
c
e
d a di
f
f
ere
n
t
app
r
oa
ch
by
m
eans of a
di
scret
e
sym
m
et
ri
c cosi
ne t
r
an
sf
orm
(DSC
T
)
.
D
uha
m
e
l
et al
[1
9
]
in
trodu
ced an alg
o
rith
m
th
at d
i
v
i
d
e
s a leng
th-
DHT calcu
lati
o
n
in
t
o
len
g
t
h
-
DHT an
d t
w
o
l
e
ngt
h-
D
F
Ts, w
h
ich
uses the lo
w
e
st k
nown
nu
m
b
er
o
f
ad
d
ition
s
witho
u
t
i
n
creasing
th
e
nu
m
b
er o
f
m
u
l
tip
licati
o
n
s
. All t
h
ese al
g
o
rith
m
s
can
b
e
classified
as th
e sp
lit-
rad
i
x
FHTs that ap
p
ear to
req
u
i
re th
e
m
i
n
i
m
u
m
arith
m
e
t
i
c co
m
p
lex
ity. Howev
e
r, like FFTs th
ey h
a
v
e
a
com
p
licated butterfly struct
ure, m
a
ki
ng t
h
e
m
di
ffi
cul
t
t
o
i
m
pl
em
ent
[2
0]
.
Recently, ne
w classes of
FFT
algorithm
s
known as
radi
x
al
go
ri
t
h
m
s
[21]
, a
n
d t
h
ei
r
vari
a
n
t
alg
o
rith
m
s
[2
2],[23
], h
a
v
e
b
e
en
in
trod
u
c
ed
as an
altern
ative to
sp
lit-rad
i
x
alg
o
rith
m
s
an
d
to
reso
lv
e th
e
len
g
t
h
l
i
m
i
t
a
t
i
on of t
h
e hi
ghe
r ra
di
x al
g
o
ri
t
h
m
s
for
har
d
w
a
re i
m
pl
em
ent
a
t
i
on of FF
Ts. T
h
e i
d
ea fo
r ra
d
i
x
alg
o
rith
m
s
is
to
realize b
o
t
h
th
e regu
lar
b
u
tterfly stru
ct
u
r
e
p
r
ov
id
ed
b
y
th
e rad
i
x
al
go
ri
t
h
m
and t
h
e
co
nd
en
sed
n
u
m
b
er o
f
t
w
idd
l
e factor m
u
ltip
licati
o
n
s
offered
b
y
th
e
h
i
gh
er rad
i
x
al
g
o
rithm
s
.
While the
DIF
approach for t
h
e ra
dix
FHT al
gorithm
has be
en recen
tly de
velope
d
[24]; howeve
r
,
for any tra
n
sform
to stand as
a good can
d
i
d
a
te fo
r
real ti
m
e
ap
p
licatio
ns, i
t
s en
tire fast alg
o
rith
m
s
n
eed
to
b
e
devel
ope
d, s
u
c
h
as t
h
e D
I
T a
p
p
r
oach
. The
r
e
f
o
r
e, i
t
i
s
t
h
e p
u
r
p
ose o
f
t
h
i
s
pape
r t
o
devel
op s
u
c
h
an al
g
o
ri
t
h
m
for fast
calcula
tion of
the DHT.
Th
e con
t
en
t
of th
e p
a
p
e
r is o
r
g
a
n
i
sed
a
s fo
llo
ws. Section
2
rev
i
ews th
e d
e
fin
ition
s
an
d
b
a
sic
p
r
op
erties of the DHT, and
then
th
e m
u
ltid
i
m
en
sio
n
a
l ind
e
x
m
a
p
p
i
n
g
tech
n
i
q
u
e
is briefl
y rev
i
ewed
in
sectio
n
2.
1. T
h
e c
o
m
p
l
e
t
e
de
vel
o
p
m
ent
s
of
t
h
e
pr
o
pose
d
al
go
ri
t
h
m
are pre
s
ent
e
d i
n
sect
i
on
3,
an
d t
h
en t
h
e
algorithm
’
s perform
a
nce is analysed
and c
o
m
p
ared with
existing FHT
al
g
o
rith
m
s
in
sectio
n
4. Finally, a
concl
u
si
o
n
i
n
g
i
ven i
n
sect
i
o
n
5.
2.
REVIEW
OF
DHT T
R
A
N
S
F
OR
M
The
DHT tra
n
s
f
orm
pair fo
r a
real val
u
e se
quence
of
leng
th
i
s
defi
ne
d a
s
[
1
]
:
0
0
-1
=
-1
=
1
()
(
)
()
(
)
()
c
a
s
()
c
a
s
=
=
N
n
N
k
N
n
θ
n
xn
θ
n
kx
k
Xk
k
X
(1
)
whe
r
e
,
and
is th
e tran
sform
l
e
n
g
t
h
.
The D
H
T i
s
cl
osel
y
rel
a
t
e
d t
o
t
h
e DFT an
d
t
h
e rel
a
t
i
onshi
p bet
w
ee
n t
h
e
m
can be obt
ai
ned
usi
n
g t
h
e
id
en
tity
, where
i
s
t
h
e
DFT
ke
rnel
de
fi
ne
d a
s
. There
f
o
r
e, t
h
e DHT can
be
obt
ai
ne
d by
subt
racting the
real part from
the im
aginary
part
of the
DFT of a
real
value seque
n
ce as:
(
)
()
()
DHT
R
e
DF
T
I
m
D
F
T
=
nn
n
xx
x
(2
)
On the ot
her
hand, the real
and im
aginary parts
of the
DFT of the real value sequence can be
o
b
t
ain
e
d
from th
e DHT u
s
ing
the id
en
tities
and
, as
fo
llows:
1
()
(
-
)
(
)
2
1
()
(
-
)
(
)
2
R
e
DF
T
D
H
T
DH
T
I
m
DF
T
D
H
T
DH
T
=
=
N
N
nn
n
nn
n
xx
x
xx
x
(3
)
Man
y
pr
op
er
ti
es of
th
e
DHT
are c
o
m
p
arable to the e
qui
valent
theo
rem
s
fo
r the
D
F
T.
One
o
f
the
m
o
st
conve
ni
e
n
t
p
r
ope
rt
i
e
s i
s
t
h
e
DH
T s
h
i
f
t
t
h
eo
rem
[2]
,
gi
ven
as:
00
0
(
)
()
(
)
()
()
c
o
s
s
i
n
DHT
=
N
k
θ
kk
θ
k
nn
X
n
X
n
x
(4
)
an
d th
e
DHT co
nvo
lu
tion
theo
rem
of t
w
o
re
al
-val
ue
d se
q
u
e
nces
and
i
s
g
i
ven
by
[1
5]
:
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
:
16
54
–
1
661
1
656
1
2
(
)
(
)
()
(
)
()
(
)
(
)
()
(
)
(
)
DHT
=
NN
N
N
k
k
kk
k
k
kk
n
n
XH
XH
X
H
X
H
xh
(5
)
whe
r
e
and
are
the
DHTs
of
and
resp
ectively.
2.
1.
Multidimensio
n
a
l
index
map
Th
e co
ncep
ts
o
f
t
h
e m
u
ltid
imen
sio
n
a
l lin
ear ind
e
x m
a
p
p
i
n
g
tech
n
i
q
u
e
will b
e
b
r
iefly
rev
i
ewed in
t
h
i
s
sect
i
o
n,
be
cause i
t
i
s
an
i
m
port
a
nt
pa
rt
cor
r
es
po
n
d
s t
o
t
h
e
pr
esent
e
d
al
go
ri
t
h
m
.
Thi
s
t
ech
ni
q
u
e
pr
ovi
de
s
an efficient approac
h
to the devel
opm
ent
of fast
al
go
ri
t
h
m
[16]
, and i
t
can be use
d
f
o
r t
h
e deri
vat
i
o
n of t
h
e
FFT as
well as
othe
r fa
st algorith
m
s
.
It
i
s
base
d
on
m
a
ppi
ng
o
f
a
o
n
e-
di
m
e
nsi
onal
ar
ray
of
l
e
ngt
h
in
to a t
w
o-d
i
m
e
n
s
io
nal
array of
size
. If the
r
e is a c
o
mmon factor
between
and
, a p
r
im
e facto
r
map
(PFM
)
will resu
lt,
whe
r
eas if the
r
e is a no com
m
on factor
between t
h
em
t
h
e com
m
on fact
or m
a
p (C
FM
) can be
obt
ai
ned
.
Si
nce
th
at th
e propo
sed
algo
rith
m
in
th
is p
a
p
e
r is
based
o
n
C
o
o
l
y-Tuk
e
y m
e
th
o
d
s wh
ich
requ
ire th
at th
e leng
th
is
a po
wer o
f
so
m
e
num
ber, i
.
e. (
) whe
r
e
r
is called
th
e rad
i
x
o
f
th
e algo
ri
t
h
m
,
therefore the CFM is of our
in
terest. Th
e two
d
i
m
e
n
s
io
nal CFM
m
a
p
fo
r th
e tim
e in
d
e
x
and f
r
e
que
ncy
i
nde
x
for th
e DFT m
a
trix
is
gi
ve
n by
:
12
21
2
2
1
11
2
1
2
21
=
+
0,
1,
...,
-
1
0,
1,
...,
-
1
=
+
0,
1
,
...,
-
1;
0,
1
,
...,
-
1
=;
=
==
NN
N
Nk
N
k
N
nn
nn
n
kk
k
(6
)
choosi
ng
and
will resu
lt t
h
e
DIT algo
rith
m
s
.
3.
ALGO
RIT
M
DERI
V
A
TIO
N
The de
ri
vat
i
o
n
of ra
di
x
FHT
DIT al
g
o
ri
t
h
m
begi
ns by
appl
y
i
n
g
t
h
e t
h
ree-
di
m
e
nsi
o
n
a
l
l
i
n
ear
i
nde
x m
a
p by
r
e
pl
aci
ng
t
h
e
i
n
di
ces
and
as:
12
3
1
2
3
32
1
1
2
3
4
42
4
0
1
0,
1,
.
.
.
,
-
1
0
1
0
,
1,
..
.,
-
1
+2
+4
,
=+
+
,
==
=
,=
;
,=
;
N
NN
N
nn
n
n
n
n
n
kk
k
k
k
k
k
(7
)
There
f
ore t
h
e
C
F
M
m
a
p of
(
1
)
bec
o
m
e
s:
12
3
=0
=0
=0
11
/
4
32
1
3
2
1
3
2
1
3
2
1
-1
42
42
(
+
+
)
(4
+
2
+
)
(4
+
2
+
)
(
+
+
)
=c
a
s
nn
n
N
NN
NN
Xk
k
k
x
θ
kk
k
nn
n
n
n
n
(8
)
Usin
g t
h
e
id
entity
:
=
++
-
c
a
s
(
)
c
o
s
(
)
cas
(
)
s
i
n
(
)cas
(
)
x
yx
y
x
y
(9
)
The
t
e
rm
i
n
(8
) ca
n
be e
xpa
n
d
ed
as:
32
1
3
2
1
2
1
3
2
1
3
3
42
42
21
3
2
1
3
3
42
(4
+
2
+
)
(
+
+
)
(2
+
)
(
+
+
)
4
(2
+
)
(
+
+
)
-
4
=c
o
s
c
a
s
sin
c
a
s
cas
NN
NN
NN
θ
θ
θ
kk
k
θ
kk
k
k
θ
kk
k
k
nn
n
n
n
n
nn
n
(1
0)
Sub
s
titu
tin
g (10
)
in
to (8
),
we
g
e
t:
12
32
1
32
1
11
32
1
3
2
1
3
2
1
42
42
=0
=0
32
1
3
2
1
44
2
4+
2
+
4+
2
+
(+
+
)
(
(
2
+
)
(
+
+
)
(-
(
2
+
)
(
+
+
)
=)
c
o
s
)s
i
n
NN
NN
nn
NN
N
nn
n
nn
n
Xk
k
k
X
k
θ
kk
k
Xk
θ
kk
k
nn
nn
(1
1)
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
New Decima
tio
n-in-Time Fast Hartley Tr
an
sfo
r
m
Al
go
rith
m (Mou
n
i
r T.
H
a
mo
od
)
1
657
whe
r
e
3
32
1
4+
2
+
()
nn
n
k
X
and
32
1
3
4
4+
2
+
(-
)
N
nn
n
Xk
in
(1
1) are two
DHTs
o
f
leng
th
, de
fi
ne
d as:
3
3
/4
1
33
=0
/4
1
33
=0
32
1
32
1
-
33
2
1
-
33
2
1
4
4+
2
+
4+
2
+
4
-4
((
4
+
2
+
)
(-
(
4
+
2
+
)
)
=
cas
)c
a
s
N
N
n
N
n
nn
n
nn
n
θ
θ
k
k
Xk
x
n
Xk
x
n
nn
n
nn
n
(1
2)
If (
1
1
)
i
s
t
o
be
com
put
ed, t
h
e
n
an o
r
di
nary
r
a
di
x
-
4
DIT F
H
T [9]
resul
t
s
w
i
t
h
t
h
e out
p
u
t
arra
nge
d i
n
di
gi
t
-re
ve
rse o
r
de
r. H
o
weve
r
as gi
ven i
n
[
2
5]
, i
f
we co
nsi
d
er t
h
e fi
r
s
t
t
w
o st
eges o
f
dec
o
m
posi
t
i
on t
o
g
e
t
h
er,
then t
h
e output
will be arranged in
bit- re
ve
rse orde
r ra
t
h
er
than i
n
di
git-re
verse
orde
r
by swappi
ng t
h
e places
o
f
th
e i
n
term
ed
iate twid
d
l
e-facto
r
s
and
, t
h
u
s
(
1
1
)
ca
n
be
m
odi
fi
ed t
o
:
21
21
11
1
=0
=0
11
1
11
1
==
0
31
2
31
2
31
2
11
32
1
3
2
2
2
2
1
3
42
2
4
2
32
2
2
2
1
3
24
2
1
32
2
2
1
3
4+
2
+
4+
2
+
4+
2
+
2
(+
+
)
(
(
+
+
+
(
2
+
)
)
(-
(
+
+
+
(
2
+
)
)
(+
+
)
+
(
2
+
)
=)
c
o
s
)s
in
=)
c
o
s
(
)
(
nn
nn
NN
N
N
N
NN
N
nn
n
nn
n
nn
n
Xk
k
k
X
k
θ
kk
k
k
Xk
θ
kk
k
k
Xk
k
k
θ
k
nn
n
n
n
nn
n
n
n
nn
n
n
n
0
11
1
31
2
1
32
2
2
1
3
4+
2
+
2
(-
+
+
)
+
(2
+
)
)s
in
(
)
(
nn
n
Xk
k
k
θ
k
nn
n
n
n
(1
3)
Eq
uat
i
o
n
(
1
3
)
can
be si
m
p
l
i
f
i
e
d
fu
rt
he
r
by
e
xpa
n
d
i
n
g t
h
e
fi
rst
sum
m
at
i
on wi
t
h
i
n
de
x
, w
e
get:
2
=0
1
1
32
32
32
32
1
32
1
3
2
2
2
3
3
2
2
2
3
42
32
2
2
3
32
2
2
3
4+
4+
4+
+
2
2
4+
+
2
2
(+
+
)
(
+
2
(
-
+
2
+
(
+
+
)
+
(
2
+
1
)
(-
+
+
)
+
(2
+
1
)
=)
c
o
s
)
s
i
n
)c
o
s
(
)s
i
n
(
n
NN
nn
nn
nn
nn
θθ
X
kk
k
X
k
k
k
X
k
k
k
Xk
k
k
θ
k
Xk
k
k
θ
k
nn
n
n
nn
nn
(1
4)
The sec
o
nd
s
u
m
m
a
t
i
on i
n
(
1
4)
, ca
n al
so
be
expa
n
d
ed
wi
t
h
i
nde
x
as:
11
22
11
33
3
33
33
32
1
3
3
2
3
3
2
3
42
33
3
3
32
3
3
2
3
44
+
2
4
+
2
22
4+
1
4
+
1
33
4+
3
4
+
3
22
(+
+
)
(
+
(
+
+
(
-
+
+
(+
2
(
-
+
2
(+
+
3
(
-
+
+
3
=)
)
c
o
s
)
s
i
n
)c
o
s
)
s
i
n
)c
o
s
)
s
i
n
NN
nn
n
nn
nn
Xk
k
k
X
k
X
k
k
k
θ
kX
k
k
k
θ
k
Xk
k
θ
kX
k
k
θ
k
Xk
k
k
θ
kX
k
k
k
θ
k
(1
5)
Eq
uat
i
on
(
1
5
)
i
s
t
h
e ge
neral
decom
posi
t
i
o
n
fo
rm
ul
a for t
h
e p
r
op
os
d ra
di
x
FHT
D
IT a
l
go
rithm
;
so
lv
i
n
g
it for
and
gi
ves t
h
e
desi
re
d
out
put
poi
nt
s. T
h
us, t
h
e fi
rst
p
o
i
n
t
o
f
t
h
e
dec
o
m
posi
t
i
ons
ca
n
be obt
ai
ne
d by
set
t
i
ng val
u
es
of
and
in (
1
5)
to ze
ro, yields
:
33
3
33
33
33
3
3
3
3
33
3
3
33
3
3
44
+
1
4
+
1
4
4+
2
4
+
2
4
4+
3
4
+
3
4
()
(
+
(
2
(
-
2
((
-
(3
(
-
3
=)
)
c
o
s
)
s
i
n
)c
o
s
)
s
i
n
)c
o
s
)
s
i
n
N
nn
n
N
nn
N
nn
Xk
X
k
X
k
θ
kX
k
θ
k
Xk
θ
kX
k
θ
k
Xk
θ
kX
k
θ
k
(1
6)
Using
t
h
e fo
llowing
tri
g
ono
metric id
en
tities:
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
:
16
54
–
1
661
1
658
33
3
3
33
3
3
33
3
3
33
3
3
33
3
3
33
3
22
2
22
2
22
2
+
+
+
+
+
cos
=
cos
c
os
s
i
n
s
i
n
=
s
i
n
s
i
n
s
i
n
cos
c
os
s
i
n
=
cos
cos
=
cos
c
os
s
i
n
s
i
n
=
c
os
s
i
n
s
i
n
c
o
s
c
o
s
si
n
=
si
n
co
s
=
cos
c
os
s
i
n
s
i
n
=
s
i
n
θ
k
θ
k
θ
k
θ
k
θ
k
θ
k
θ
k
θ
k
θ
k
θ
k
θ
k
θ
k
θ
k
θ
k
θ
k
θ
k
θ
k
θ
k
θ
k
θ
k
33
3
3
33
22
2
+
s
i
n
s
i
n
cos
c
o
s
s
i
n
=
cos
θ
k
θ
k
θ
k
θ
k
(1
7)
Ot
he
r
decom
posi
t
i
ons
can
be
com
put
ed a
s
:
4
44
+
1
4
+
1
4
4+
2
4
+
2
4
4+
3
4
+
3
4
(+
)
(
(
2
(
-
2
(-
(
(-
3
(
3
=)
)
c
o
s
)
s
i
n
)c
o
s
)
s
i
n
)c
o
s
)
s
i
n
N
N
nn
n
N
nn
N
nn
Xk
X
k
X
k
θ
kX
k
θ
k
Xk
θ
kX
k
θ
k
Xk
θ
kX
k
θ
k
(1
8)
2
44
+
1
4
+
1
4
4+
2
4
+
2
4
4+
3
4
+
3
4
(+
)
(
(
2
(
-
2
((
-
(3
(
-
3
=)
)
c
o
s
)
s
i
n
)c
o
s
)
s
i
n
)c
o
s
)c
o
s
N
N
nn
n
N
nn
N
nn
Xk
X
k
X
k
θ
kX
k
θ
k
Xk
θ
kX
k
θ
k
Xk
θ
kX
k
θ
k
(1
9)
3
4
44
+
1
4
+
1
4
4+
2
4
+
2
4
4+
3
4
+
3
4
(+
)
(
(
2
(
-
2
(-
(
(-
3
(
3
=)
)
c
o
s
)
s
i
n
)c
o
s
)
s
i
n
)c
o
s
)
s
i
n
N
N
nn
n
N
nn
N
nn
Xk
X
k
X
k
θ
kX
k
θ
k
Xk
θ
kX
k
θ
k
Xk
θ
kX
k
θ
k
(2
0)
The in-place butterfly for the
radix
FHT DIT alg
o
r
ith
m
can
b
e
ob
tain
ed
b
y
co
m
b
in
in
g
poi
nt
s
to
g
e
th
er as sh
own in
Fi
gure 1.
Figu
re
1.
A
b
u
t
t
erfly
o
f
the
ra
dix
FHT
DIT
algorithm
;
where
, do
tted
and
so
lid
lin
es stand
for su
b
t
ractio
n
an
d add
ition
s
resp
ectiv
ely
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
New Decima
tio
n-in-Time Fast Hartley Tr
an
sfo
r
m
Al
go
rith
m (Mou
n
i
r T.
H
a
mo
od
)
1
659
B
y
appl
y
i
ng t
h
e pr
oce
d
u
r
e ab
ove
re
peat
edl
y
t
o
t
h
e rem
a
i
n
i
ng
D
H
Ts
of l
e
ngt
h
N
/4, t
h
e
whole ra
dix-
2
2
DI
T FHT a
l
go
ri
t
h
m
i
s
achi
eve
d
. Fi
g
u
r
e
2 sh
ows a
16-point exam
ple for calcu
lating
th
e DHT u
s
i
n
g
the
pr
o
pose
d
ra
di
x
-
2
2
D
I
T
algor
ith
m
.
Fi
gu
re
2.
Si
g
n
a
l
fl
o
w
gra
p
h
f
o
r t
h
e
1
6
-
p
oi
nt
r
a
di
x
-
2
2
FHT DIT
algorithm
;
whe
r
e
and
, do
tted
and
so
l
i
d
lin
es stan
d fo
r sub
t
raction
an
d add
ition
s
resp
ectiv
ely
4.
ARIT
H
METI
C CO
MPLE
XITY
The pe
rf
orm
a
nce of t
h
e de
vel
ope
d al
g
o
ri
t
h
m
i
s
anal
y
s
ed i
n
t
h
i
s
sect
i
on, by
com
put
i
ng t
h
e
num
ber of
m
u
l
tiplications and additions. This calculation is base
d
on the in-place
butterfly of
the
prese
n
ted al
gorithm
sho
w
n i
n
Fi
g
u
r
e 1
.
I
n
gene
r
a
l
,
radi
x -
2
2
DIT algorithm
needs log
2
N
sta
g
es of butterfl
y
calculation. Every
stage uses
(11
N
/4
-
10)
a
d
di
t
i
ons a
n
d
(3
N
/2-12
)
m
u
ltip
lic
atio
n
s
. M
o
reover,
fou
r
N
/
4
l
e
ngt
h
DHT
s m
u
st
be
com
put
ed, t
h
us
t
h
e c
o
m
p
l
e
t
e
radi
x
-
2
2
FHT alg
o
rith
m
fu
lfills th
e
recurren
c
es,
3
42
11
44
=1
2
=1
0
()
()
4(
)
+
4(
)
+
N
N
N
N
N
N
MM
AA
(2
1)
So
lv
in
g
(2
1
)
b
y
rep
eated
su
b
s
titu
tio
n
s
o
f
th
e in
itial v
a
lu
es
g
i
v
e
s th
e clo
s
ed
fo
rm
co
m
p
lex
ities. Fo
r
th
is case, th
e in
itial
v
a
lu
es can
b
e
th
e n
u
m
b
e
r o
f
o
p
e
ratio
n
s
th
at are req
u
i
red
b
y
len
g
t
h
and
l
e
ngt
h
DHTs, wh
ich
are eq
u
a
l to
,
,
and
resp
ectiv
ely, we g
e
t:
2
2
5
2
19
10
12
3
3
4
11
8
lo
g
lo
g
()
4
()
N
N
N
N
MN
N
NN
A
(22)
An asses
s
m
e
nt has been m
a
de bet
w
een t
h
e
devel
ope
d al
g
o
ri
t
h
m
,
radi
x -
2
an
d radi
x -
4
al
gori
t
h
m
s
with
reg
a
rd
to th
e n
u
m
b
e
r
o
f
m
u
ltip
licati
o
n
s
and
add
itio
n
s
, as d
e
p
i
cted
in
Tab
l
e1
. Th
e resu
lts o
f
th
is
assessm
en
t sho
w
s th
at
th
e
presen
ted
al
g
o
ri
th
m
is b
e
tte
r t
h
an
ra
di
x
-
2
a
l
go
ri
t
h
m
and
ob
vi
o
u
sl
y
e
x
c
eedi
n
g
radi
x -
4
.
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
:
16
54
–
1
661
1
660
Tab
l
e
1
.
C
o
m
p
arison
in th
e
nu
m
b
er of m
u
lti
p
licatio
n
s
and
ad
d
ition
s
b
e
tween
rad
i
x
, radi
x
and ra
dix
DIT FHT al
g
o
rith
m
s
Tran
sf
o
r
m
L
e
ngth
Radix
FH
T
algor
ith
m
Radix
F
H
T
algor
ith
m
[4]
Radix
F
H
T
a
l
gor
ith
m
[9]
Mu
lts. Ad
d
s
.
Mu
lts.
Ad
d
s
.
Mu
lts.
Ad
d
s
.
8
2
22
4
26
-
-
16
12
66
20
74
14
70
32
44
166
68
194
-
-
64
132
430
196
482
142
450
128
356
1006
516
1154
-
-
256
900
2414
1284
2690
942
2498
512
2180
5422
3076
6146
-
-
1024
5124
1246
2
7172
1382
6
5294
1280
2
2048
1178
0
2731
0
1638
8
3072
2
-
-
4096
2662
8
6110
2
3686
8
6758
6
2731
0
6244
66
5.
CO
NCL
USI
O
N
Thi
s
pape
r has
bee
n
dev
o
t
e
d t
o
t
h
e de
ri
vat
i
o
n of
a new
fast
al
go
ri
t
h
m
cal
led radi
x-
2
2
F
H
T base
d
o
n
decim
a
tion-in-tim
e approach. The
de
ve
lopment of the
pres
ented al
gorithm
is
based on the
in-place butterfly
st
ruct
u
r
e
t
o
p
r
ovi
de
a wi
der
ran
g
e of radi
c
e
s
wi
t
h
be
tter
stru
ctural co
m
p
lex
ity and
wi
th
ou
t in
creasing
th
e
requ
ired
co
m
p
u
t
atio
n
a
l co
m
p
lex
ity. Th
e presen
ted
algor
ithm is o
f
su
bstan
tial i
m
p
o
r
tance for h
a
rdware and
soft
ware i
m
pl
em
ent
a
t
i
ons, be
cause t
h
i
s
al
go
ri
t
h
m
,
al
ong w
i
t
h
t
h
e fact
t
h
at
t
h
e DHT i
s
an
effi
ci
ent
al
t
e
rnat
i
v
e
to
the
DFT of real-value
d data,
m
a
kes
it likely that for
a single ha
rdware
or softwa
re m
odule to be
utilized for
th
e calcu
lationo
f th
e
DHT, as well as
for t
h
e calcu
latio
n of
th
e fo
rwar
d
rea
l
-val
ue
d
DFT
a
n
d
i
t
s
i
n
verse
.
REFERE
NC
ES
[1]
R. N. Bra
cewe
l
l
,
“
D
is
crete Har
t
l
e
y trans
f
orm
,
”
Journal of the Optical
Society of
America,
vol. 73
, pp. 1832-
1835,
1983.
[2]
R. N.
Brac
ewel
l,
Ed.
,
“
T
h
e
Har
t
l
e
y tr
ans
f
orm
,
” O
x
ford Univers
i
t
y
P
r
es
s
,
Inc
.
,
198
6.
[3]
J. Liu,
et al.
, “Super
‐
apertu
re
metrolog
y
:
over
c
oming a fundament
al limit in
imaging
smoot
h highly
curved
s
u
rfaces
,
”
Journ
a
l of microscopy,
2015
.
[4]
J. Liu,
et al.
, “S
y
n
thetic complex superresolvin
g pupil fi
lter
based on double-b
eam phase modulation
,
”
Applied
Optics,
vo
l. 47,
pp. 3803-3807
,
2008.
[5]
Z. Liu,
et
al
., “I
mage encr
y
p
tion
based on doub
le random amplit
ude cod
i
ng in
random Hartley
tr
ansform domain,”
Optik -
International Journal
for Light
and Electr
on
Optics,
vol. 1
21, pp
. 959-964
, 2010.
[6]
Z. Liu,
et al.
, “C
olor image en
cr
y
p
tion b
y
using
the rotation of
color vector in H
a
rtley
transform
domains,”
Optic
s
and Lasers in En
gineering
,
vol. 4
8
, pp
. 800-805
,
2010.
[7]
Z. Liu
,
et al.
, “Optical color image hiding scheme base
d on ch
aotic mapping and Hartley
trans
f
orm,”
Optics and
Lasers in Engineering,
vo
l. 51, p
p
. 967-972
, 201
3.
[8]
A. V. Oppenh
eim,
et al.
, “Discr
ete-
time sign
al p
r
ocessing, Pr
entice
h
a
ll Eng
l
ewo
od Cliffs, NJ, vo
l. 2
,
1989
.
[9]
K. Jones, “Design and p
a
ralle
l com
putation
of regular
ised
f
a
st Hartle
y transfor
m
,
”
in
Vision
, I
m
age and Signa
l
Pr
oces
s
i
ng, IEE
Pr
oceed
ings
-
, p
p
. 70-78
, 2006
.
[10]
D.
Narmadha,
et al.
,
“
A
n Optim
al HS
I Im
age Com
p
ression using DWT an
d CP,”
In
ternational Journal o
f
Electrica
l
and
C
o
mputer Engin
e
ering,
vo
l. 4, pp. 411-421, 2014.
[11]
R. N.
Brac
ewel
l,
“
T
he f
a
s
t
Har
tle
y
trans
f
orm
,
”
Pr
oceed
ings
of
the
IEEE
,
vo
l. 72, p
p
. 1010-1018
, 1
984.
[12]
H. J. Meckelbur
g and D. Lipka, “F
ast Hartley
transform
algorithm,”
Elec
tronic
s
Letters,
vol. 21, pp. 341-343,
1985.
[13]
C. Kwong and
K. Shiu, “Structured fa
st Hartley
tr
ansform algorithms,”
IEEE T
r
ansactions on
Acousti
cs, Spee
c
h
and Signal Processing,
,
vol. 34
,
pp. 1000-1002
,
1986.
[14]
H. S. Hou, “The
fast Ha
rt
le
y tran
sform
algorithm
,
”
IEEE Transactions on Computers,
vol. 100, pp.
147-156, 1987
.
[15]
H.
Sorensen,
et al.
, “On computing the discr
e
te
Hartley
transfor
m,”
IEEE T
r
ansactions on Acou
stics, Spe
ech an
d
Signal Processin
g
.,
vol. 33, pp. 1
231-1238, 1985
.
[16]
C. Burrus, “
I
nde
x m
a
ppings for m
u
ltidim
ensiona
l form
ulation of
the DFT and con
volution,
”
IEEE Transactions
on
Acoustics, Sp
eech and Signa
l
Processing.,
vol. 25
, pp. 239-242, 19
77.
[17]
H. Malvar
, “Fast computation of
discrete cosi
n
e
tr
ansform through fast Har
tley
tr
an
sform,”
Ele
c
tron
ics Lett
ers,
vol.
22, pp
. 352-353
, 1986.
[18]
Y
.
H
.
C
h
a
n
a
n
d
W
.
C
.
S
i
u
,
“
N
e
w
f
o
r
m
u
l
a
t
i
o
n
o
f
f
a
s
t
di
sc
re
te
Ha
rt
l
e
y
t
r
a
n
sform wi
t
h
t
h
e
mi
nimum nu
mbe
r
of
m
u
ltiplic
ations
,”
in
IEEE Pa
cific Rim Conferen
ce on Comm
unications, Computers and Signal Processing
, vol
. 1
,
pp. 323-326
, 19
91.
[19]
P. Duhamel an
d M. Vetterli,
“Improved Fou
r
ier and
Ha
rt
ley
tra
n
sform a
l
gori
t
h
ms:
Appl
i
c
a
t
i
on t
o
cy
c
lic
convolution of r
eal data,”
IEEE
Transactions on
Acoustics,
Sp
eech and Signal Processing,
vol. 3
5
, pp. 818-824,
1987.
[20]
R. Bra
cewe
ll,
“
A
lterna
tive
to
split-r
a
dix Har
t
l
e
y
transform
,
”
Electronic
s
Le
tte
rs,
v
o
l. 23
, pp
. 1148-
1149, 1987
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
New Decima
tio
n-in-Time Fast Hartley Tr
an
sfo
r
m
Al
go
rith
m (Mou
n
i
r T.
H
a
mo
od
)
1
661
[21]
S
.
He and
M
.
To
rkels
on, “
A
new
approach
to p
i
pe
line F
F
T
pro
ces
s
o
r,”
in
Parallel
Processing Sym
posium, The 10th
International
Pr
oceed
ings of
IP
PS'96,
pp
. 766-7
70, 1996
.
[22]
A.
Cortés,
et al.
,
“
R
adix FFTs: Matri
c
i
a
l r
e
present
a
tion
a
nd SDC/SDF
pipelin
e
im
ple
m
entation
,
”
IEE
E
Transactions
on Signal Processin
g
, ,
vol. 57
, pp
. 2
824-2839, 2009
.
[23]
I.
A.
Qureshi and F.
Qureshi,
“I
mp
act of FFT a
l
gorithm selection on switchi
ng
activi
t
y
and co
effic
i
ent m
e
m
o
r
y
s
i
ze,
”
TELKOMNIKA Indonesia
n
Journal
o
f
Electrical
Eng
i
neering,
vol. 12
, pp
. 6
224-6229, 2014
.
[24]
M. T. Hamood and S. Boussakta, “New
radix-bas
e
d FHT algor
ith
m for computi
ng the d
i
screte Har
tley
transform,”
in
IEEE Internati
onal Conference on
Acoust
i
cs, S
p
eech
and S
i
gna
l Proc
essing (
I
CASSP’11)
,
pp. 1
581-1584, 2011
.
[25]
C. S. Burrus, “Unscrambli
ng for fast DFT algorithms,”
IEE
E
Transactions on Acoustics
,
Speech and Sign
al
Processing.,
vol. 36, pp. 1086-10
87, 1988
.
BIOGRAP
HI
ES OF
AUTH
ORS
M
o
unir
Taha
Hamood
receiv
e
d the B.S
c
. deg
r
ee in e
l
ec
tri
cal
engine
ering fro
m
Univers
i
t
y
of
Techno
log
y
, Baghdad, Iraq in
1990 and the M.Sc
. degree in electronic and
communications
engineering fro
m Al-Nahrain University
, Baghd
ad
, Iraq
in 1995. He graduated fr
om Newcastle
University
, Newcastle upon
Ty
n
e
, U.K
in 2012
w
ith the PhD degree in
commu
nications an
d
signa
l proc
e
ssing.
His doc
tora
l re
se
a
r
c
h
wa
s in th
e developmen
t of efficient algo
rithms for fast
computation
of
discrete tr
ansfor
ms.
He is currently a Lecturer
in Signal Proce
ssing for Commu
nications at
th
e Department of
Ele
c
tri
cal
Eng
i
n
eering
,
Col
l
eg
e
of Eng
i
neer
ing
,
T
i
krit
Univers
i
t
y
,
Tikr
it,
Iraq
.
His
res
ear
ch
inter
e
st in
clude
discre
te
transf
orm
s
, fast al
gor
ithms for digital signal processing in on
e
and
m
u
ltidim
ensiona
l app
lic
ations
, an
d com
m
unicatio
n s
y
st
em
s.
Evaluation Warning : The document was created with Spire.PDF for Python.