T E L K O M N I K T elec o m m un ica t io n,  Co m pu t ing ,   E lect ro nics   a nd   Co ntr o l   Vo l.   18 ,   No .   6 Dec em b er   2 0 2 0 ,   p p .   3 0 6 7 ~3 0 7 2   I SS N:  1 6 9 3 - 6 9 3 0 ,   ac cr ed ited   First Gr ad b y   Kem en r is tek d i k ti,  Dec r ee   No : 2 1 /E/KPT /2 0 1 8   DOI : 1 0 . 1 2 9 2 8 /TE L KOM NI K A. v 1 8 i6 . 1 6 1 0 0     3067       Jo ur na l ho m ep a g e h ttp : //jo u r n a l.u a d . a c. id /in d ex . p h p /TELK OM N I K A   Direct  split - ra dix   a lg o rithm f o r f a st  com putatio n of  t y pe - II  discrete  H a r tley t ra nsfo rm       M o un ir  T a ha   H a m o o d   El e c tri c a En g i n e e rin g   De p a rtme n t,   C o ll e g e   o E n g i n e e rin g ,   Un i v e rsity   o f   Ti k rit ,   Ira q       Art icle  I nfo     AB S T RAC T   A r ticle  his to r y:   R ec eiv ed   Ma r   2 0 ,   2 0 2 0   R ev is ed   J u n   3 ,   2 0 2 0   Acc ep ted   J u n   2 5 ,   2 0 2 0       In   t h is  p a p e r,   a   n o v e l   sp li t - ra d ix   a lg o ri th m   f o fa st  c a lcu latio n   t h e   d isc re te  Ha rtl e y   tran sfo rm   o t y p e - II  ( DH T - II)  is  in t o d u c e d .   Th e   a l g o rit h m   is   e sta b li sh e d   th r o u g h   t h e   d e c ima ti o n   in   ti m e   (DIT)  a p p ro a c h ,   a n d   im p lem e n ted   b y   s p li tt i n g   a   len g th   o DH T - II   in t o   o n e   DH T - II  o len g th   N/2   fo e v e n - in d e x e d   sa m p les   a n d   tw o   DH Ts - II  o len g th   N/4   f o o d d - in d e x e d   sa m p les .   T h e   p r o p o s e d   a l g o r i t h m   p o s s e s s e s   t h e   d e s i re d   p r o p e r t i e s   s u c h   a s   r e g u l a r i t y ,   i n p l a c e   c a lc u l a t i o n   a n d   i t   i r e p re se n t e d   b y   s i m p l e   c l o se d   f o r m   d e c o m p o s i t i o n s   l e a d i n g   t o   c o n s i d e r a b l e   re d u c t i o n s   i n   t h e   a r i t h m e t ic   c o m p l e x i t y   c o m p a r e d   t o   t h e   e x i s t i n g   D H T - I I   a l g o r i t h m s .   A d d i t i o n a l l y ,   t h e   v a l id it y   o f   th e   p r o p o se d   a lg o rit h m   h a b e e n   c o n firme d   t h ro u g h   a n a ly sin g   th e   a rit h m e ti c   c o m p lex it y   b y   c a lcu lati n g   t h e   n u m b e o f   re a a d d i ti o n a n d   m u lt ip li c a ti o n s   a n d   a ss o c iatin g   it   with   th e   e x ist in g   D HT - II  a lg o ri th m s.   K ey w o r d s :   Dec im atio n - in - tim ap p r o ac h   Dis cr ete  Har tley   tr an s f o r m     Gen er alize d   DHT s     Sp lit r ad ix   alg o r ith m     Ty pe - I I   DHT   ( DHT - I I )   T h is i a n   o p e n   a c c e ss   a rticle   u n d e th e   CC B Y - SA   li c e n se .     C o r r e s p o nd ing   A uth o r :   Mo u n ir   T a h Ham o o d ,     E lectr ical  E n g in ee r in g   Dep ar t em en t,   C o lleg o f   E n g in ee r in g ,     Un iv er s ity   o f   T ik r it,   T ik r it,  P O  B OX  4 2 ,   I r aq .   E m ail:  m . t.h am o o d @ tu . ed u . iq       1.   I NT RO D UCT I O N     T h e   H a r t l e y   t r a n s f o r m   ( H T )   i s   a n   o r t h o g o n a l   t r a n s f o r m   t h a t   m a p s   a   r e a l   v al u e d   f u n c t io n   i n t o   i t s   f r e q u e n c y   r e a l   c o m p o n e n t s   [ 1 ] ,   u s e d   i n   d i v e r s e   f ie l d s u c h   a s   s i g n al / i m a g e   p r o c e s s i n g ,   d i g i ta l   c o m m u n i c at i o n s   a n d   m a n y   o t h e r   a p p l i c a t i o n s   [ 2 ] .   A l t h o u g h   H T   a n d   t h e   F o u r i er   t r a n s f o r m   ( F T )   [ 3 ] ,   s h a r es   e q u i v a l e n t   p r o p e r t i es ,   it   al l o ws   f u n c t i o n   t o   b e   s e p a r a t e d   i n t o   t w o   a u t o n o m o u s   s e ts   o f   s i n u s o i d a l   c o m p o n en t s ;   t h e s e   s e ts   a r c h a r a c t e r i z e d   i n   t e r m s   o f   n e g at i v e   a n d   p o s i t i v f r e q u e n c y   c o m p o n e n t s   r e s p ec t i v el y .   A n o t h e r   a d v a n t a g e   o f   t h e   H T   o v e r   t h F T   is   t h a t   t h e   c o m p u t a t i o n   o f   t h k e r n e o f   H T   i s   e x a c tl e y   s a m a s   t h a o f   it s   i n v e r s e ,   s o   t h a t h i n v e r s e   t r a n s f o r m   d i f f e r s   f r o m   f o r w a r d   o n l y   b y   t h e   s c a l e   f a c t o r ,   h e n c e   i d e n t i c a l   u t i l iz a t i o n   o f   t h e   H T   c a n   b e   u s e d   f o r   s i g n a l   s y n t h es i s   a n d   a n a l y s is .   As   we   k n o w   t h at   a   r ea l   g e n e r a l i z e d   d is c r e te   v e r s i o n   o f   H a r t l e y   t r a n s f o r m   ( G D H T )   [ 4 ]   c a n   b e   d e f i n e d   a n a l o g o u s   t o   t h e   c o m p l e x   g e n e r a l i z e d   d i s c r e t e   o f   f o u r i e r   t r a n s f o r m   ( G D F T )   [ 5 ] A l s o ,   it   i s   we l l   k n o w n   t h a t   t h e r e   i s   a   f a s t   w a y   o f   c o m p u t i n g   H a r t l e y   t r a n s f o r m   t h a t   i s   a n a l o g o u s   t o   t h e   f a s f o u r i e r   t r a n s f o r m   ( F F T )   a s   t h e r e   is   s i m p l e   s t e p   t o   g o   f r o m   D F T   t o   t h e   DH T   [ 6 ] .   C o n s e q u e n t l y   t h f as a l g o r i t h m   d e v e l o p e d   i n   t h i s   p ap e r   a l s o   c o n s t it u t e s   a   f as t   wa y   o f   a r r i v i n g   a t   GD F T .   I n   f a ct   t h e   a p p r o a c h   v i a   t h G D H T   p r o v e s   t o   b e   a d v a n t ag e o u s   m a i n l y   b e c a u s o f   t h s i m p li f i c at i o n s   t h a r e s u l t s   f r o m   t h e   f a c t h at   n o   c o m p l e x   a r i t h m e t ic   is   r e q u i r e d   w h e n   r e a l   d a t a   a r e   b ei n g   p r o c e s s e d .   I n   g en r al ,   th DHT   tr an s f o r m   k er n el  ca n   b e x ten d ed   to   allo s h if ts   in   eith er   tim i n d ex ,   f r eq u e n cy   in d ex   o r   b o th   i n d ex es.  T h e   r esu ltin g   in v er tb le  tr an s f o r m s   ar r ef f er e d   to   as  g en e r alize d   d is cr ete  Har tley   tr an s f o r m s   ( GDHT s )   an d   a r d ef in ed   as ;   Evaluation Warning : The document was created with Spire.PDF for Python.
                       I SS N :   1 6 9 3 - 6 9 3 0   T E L KOM NI KA   T elec o m m u n   C o m p u t E l Co n tr o l Vo l.  18 ,   No .   6 Dec em b e r   2 0 2 0 :    30 6 7   -   307 2   3068   X ( k ) = x ( n )  ( ( 2n + n ) ( 2k + k ) 4 ) N - 1 n = 0                               k = 0 , 1 , . . . , N - 1   ( 1 )     wh er  ( ) =    ( ) +    ( ) , = 2 /   is   th k er n el  o f   th tr an s f o r m ,   an d   th co n s tan t s     an d     ar th p ar am eter s   th at  id en tify   s h if ts   in   th f r eq u en c y   an d   ti m d o m ain s .   B y   ap p ly in g   d if f er en s et  o f   th ese  p ar am eter s ,   a   d if f e r en ty p e s   o f   GDHT   ca n   b o b tai n ed .   As  th in p u t   s eq u en ce   ( )   ca n   b ac c u r at ely   r etr iev ed   f r o m   th o u tp u s eq u en ce   ( ) ,   th er ef o r ( )   is   co m p lete ly   d e f in ed   b y   s et  o f   co ef f icie n ts   ( )   in   d i v er s e   d o m ain .   I n   m an y   r ea lted   ap p licatio n s ,   it  is   o r d in ar y   to   s p ec if y   p r o b lem   in   ap p r o p r iate   d o m ain   b ec au s n u m er o u s   ch ar ac ter is tics   o f   th s ig n als  ca n   b o n ly   r ev ea led   in   p ar ticu lar   d o m ai n .   T h is   p ap er   d ea ls   with   p ar ticu lar   ty p o f   GD H T   wh en   = 0   an d   = 1   th at  is   k n o wn   in   liter atu r as ty p e - I I   DHT   [ 7 ]   lo t   o f   al g o r ith m s   wer e   in tr o d u ce d   f o r   f ast  ca lcu latio n   o f   th e   GD HT s   [8 - 1 0 ] .   Am o n g   th e m ,     th s p lit - r ad ix   alg o r ith m   th at  was  f ir s p r o p o s ed   f o r   th ca l cu latio n s   o f   th FF T   [ 1 1 - 1 3 ]   an d   th en   d ev elo p e d   f o r   o t h er   tr a n s f o r m s   [ 1 4 - 17] ,   h as  p r o v e d   it  g i v es  th lo wes ar ith m etic  co m p lex ity   k n o w n   in   liter atu r e   [ 1 8 ,   19] ,   th at  em p l o y s   r a d ix - 4   d ec o m p o s itio n   to   th o d d - i n d ex ed   s am p les  an d   r ad i x - 2   d ec o m p o s itio n   to     th ev en - in d ex ed   s am p les  o f   th p o wer - of - two   s am p le s .   Ho wev er ,   th d ev el o p m en ts   o f   th s p lit   r ad ix   alg o r ith m s   in tr o d u ce d   f o r   th e   DHT - I I   ( SR - DHT - I I )   wer u s in d ir ec ap p r o ac h es   [ 2 0 ,   2 1 ] .   T h er ef o r e,   it  is   p u r p o s e   o f   th is   p ap er   to   in tr o d u ce   d ir ec s p lit  r ad ix   alg o r it hm  f o r   th ef f icien t   ca lcu lat io n s   o f   th DHT - I I   u s in g   d ec im atio n - in - tim e   ( DI T )   ap p r o ac h .   T h e   p a p er   is   p r ep ar ed   in   f o u r   s ec tio n s   as  f o llo ws:   s ec tio n   2   p u r p o s es  th d e v elo p m e n o f   t h n ew   s p lit - r ad ix   alg o r ith m   b ased   o n   DI T   a p p r o ac h   f o r   th e   DHT - I I .   I n   s ec tio n   3 ,   th ev al u tio n   o f   th p r o p o s ed   alg o r ith m   is   s tu d ied   b y   ca lcu latin g   t h eir   ar ith m et ic  co m p lex ity   a n d   ass o ciatin g   th em   w ith   th r ad i x - 2   alg o r ith m .   c o n clu s io n   is   th en   g iv e n   in   s ec tio n   4 .       2.   DE V E L O P M E N T   O F   SR - D H T - II   A L G O RIT H M   T h ty p e - I I   d is cr ete  Har tley   t r an s f o r m   ( DHT - I I )   o f   le n g th     f o r   th e   r ea l   v alu ed   s am p les   ( )   is   g iv en   as  [ 2 2 ] :     X ( k ) = x ( n )  (  ( 2k + 1 2 ) ) N - 1 n = 0                               k = 0 , 1 , . . . , N - 1   ( 2)     w h er e   th tr an s f o r m   le n g th     is   id en tifie d   to   b p o wer s   o f   two   = 2 .   T h e   in v er s DHT - II  t r an s f o r m   ( k n o wn   as th e   ty p e - I I I   DHT )   i s   d ef in ed   as ;     x ( n ) = 1 X ( k )  (  ( 2k + 1 2 ) ) N - 1 k = 0                               n = 0 , 1 , . . . , N - 1   ( 3)     T h d ec im atio n - in - tim alg o r ith m   ( DI T )   d er iv atio n   o f   th e   SR - DHT - I I   alg o r ith m   s tar ts   b y   d ec o m p o s in g     th tr an s f o r m ed   s eq u en ce   ( )   in to   its   o d d    ( )   an d   ev e n    ( )   in d e x ed   s eq u en ce s .   T h er ef o r ( 2 )   ca n   b d ec o m p o s ed   to ,     X ( k ) = X od ( k ) + X ev ( k )   ( 4)     wh er  ( )   an d    ( )   r ep r esen ts   th o d d -   an d   ev en - in d e x ed   s eq u e n ce s   o f   ( )   r esp ec tiv ely ,   b o t h   ar o f   len g th   ( / 2 ) .   Firstl y ,   r ad ix - 2   al g o r it h m   f o r   th  ( )   ca n   b wr itten   as ;     X ev ( k ) = x ( 2n ) N / 2 - 1 n = 0 c a s ( 2 n ( 2k + 1 2 ) ) = X 2n ( k )   ( 5)     Seco n d ly ,   r ad ix - 4   al g o r ith m   f o r   th e   DHT - I I   ca n   b e   d ev elo p ed   b y   d i v id in g   th e   in p u t   s am p les  ( )   in to   f o u r   ( / 4 )   DHT s - I I   as f o llo ws:     X ( k ) = X o ( k ) + X 1 ( k ) + X 2 ( k ) + X 3 ( k )   ( 6)     wh er e,     Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KOM NI KA   T elec o m m u n   C o m p u t E l Co n tr o l         Dir ec t sp lit - r a d ix  a lg o r ith fo r   fa s t c o mp u ta tio n   o f ty p e - I I   d is crete … ( Mo u n ir   T aha   Ha mo o d )   3069   X i ( k ) = x ( 4n + i ) / 4 - 1 n = 0 c a s ( ( 4n + i ) ( 2k + 1 2 ) )                           i = 0 , 1 , 2 , 3   ( 7)     T h er ef o r e,   b y   c o n s id er in g   t h o d d   in d e x ed   s am p les  o n ly   f o r   th ( )   in   ( 6 )   i.e . ,   [  ( ) = 1 ( ) + 3 ( ) ] we  g et:     ( ) ( ) ( ) ( ) 44 44 11 = 0 = 0 11 = 0 = 0 2 + 1 2 + 1 2 + 1 2 + 1 2 2 2 2 2 + 1 2 + 1 22 4 1 4 4 3 4 3 4 1 4 4 3 4 3 + + 1 + + + + + + ( ) ( ) ( ) ( ) ( ) ( ) ( ) = ( ) + ( ) =+ NN NN nn nn od k k k k kk n n n n n n n n k X x c a s x c a s x c a s x c a s  −− −−     ( 8 )     Ap p ly in g      p r o p er ty   g iv en   i n   [ 1 ]   as f o llo ws ;     c a s ( + ) = c os ( ) c a s ( ) + s in ( ) c a s ( - )   ( 9)      ( . )   ter m   in   ( 8 )   ca n   b s im p lifie d   t o :     ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) =0 44 4 4 = 0 = 0 =0 11 2 + 1 2 + 1 2 + 1 2 + 1 2 2 2 2 1 1 2 + 1 2 + 1 2 + 1 2 + 1 2 2 2 2 4 1 4 1 43 ++ 4 3 3 ( + ) - ( ) 4 ( ) 4 3 ( + ) 4 4 ( ) + - + = n NN N N nn n k k k k k k k k od nn xn nn x n n n k c o s x c a s s in x c a s s in c a s X c o s c a s −− +    ( 1 0 )     T h n eg ativ i n d ices o f      ter m s   in   ( 1 0 )   ca n   b s im p lifie d   to ;     ( ) ( ) ( ) ( ) 1 2 + 1 2 =0 -1 =0 -1 =0 -1 =0 - 1 2 1 2 2 ( - - 1 ) + 1 2 ( - - ) ( - - ) ( ) ( ) () () -= = = N k m N n N n N n Nk mk Nk m x m m x m m x m m x c a s c a s c a s c a s   ( 1 1 )     Fro m   ( 1 1 )   we  g et  th e   r elatio n ,     x ( 4n + i )  4 1 n = 0 c a s ( - 4 n 2k + 1 2 ) = x ( 4n + i )  4 1 n = 0 c a s ( 4  2 (  4 - k - 1 ) + 1 2 )     ( 12)     T h er ef o r    ( )   in   ( 1 0 )   b ec o m es ;     ( ) ( ) ( ) ( ) 4 2 + 1 2 + 1 2 4 2 2 + 1 2 + 1 4 + 1 4 + 1 22 4 + 3 4 + 3 1 1 -- 3 - - 3 () = ( ) + ( ) ( ) + ( ) + N k N k kk o d n n nn k k kk k X X c o s X s i n X c o s X s i n     ( 1 3 )     wh er 4 + 1 ( )   an d   4 + 3 ( )   ar two   DHT s - I I   o f   len g th   ( / 4 )   ,   d ef in ed   as:     X 4n + 1 ( k ) = x ( 4n + 1 ) 4 1 n = 0 c a s ( 4 n ( 2k + 1 2 ) )   ( 14)     X 4n + 3 ( k ) = x ( 4n + 3 ) 4 1 n = 0 c a s ( 4 n ( 2k + 1 2 ) )   ( 15)     Su b s titu tin g   ( 5 )   a n d   ( 1 3 )   i n to   ( 4 ) ,   ( ) ,   we  g et ,   Evaluation Warning : The document was created with Spire.PDF for Python.
                       I SS N :   1 6 9 3 - 6 9 3 0   T E L KOM NI KA   T elec o m m u n   C o m p u t E l Co n tr o l Vo l.  18 ,   No .   6 Dec em b e r   2 0 2 0 :    30 6 7   -   307 2   3070   ( ) ( ) ( ) ( ) 2 + 1 2 + 1 22 2 + 1 2 + 1 2 4 + 1 4 + 1 2 4 2 4 + 3 4 + 3 4 1 1 33 ( ) - - -- = ( ) ( )   + ( )   ( )   + ( )   + + kk k N k n n n N nn k k k k kk X X X c o s X s i n X c o s X s i n     ( 1 6 )     Usi n g   th f o llo win g   t r ig o n o m etr ic  id en titi es ,   ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 + + + + == c os = c os = = = c os c os c os sin sin sin sin sin c os sin c os c os c os sin sin sin sin sin c os c os sin c os −− =+ = +   ( 1 7 )     Oth er   d ec o m p o s itio n s   ( + / 4 ) , ( + / 2 )   an d   ( + 3 / 4 )   ca n   b ca lcu lated ,   as      ( ) ( ) ( ) ( ) 2 + 1 2 2 + 1 2 + 1 2 4 + 1 4 + 1 4 4 2 4 2 2 + 1 4 n + 3 4 n + 3 42 1 3 1 3 ( ) - - -- = ( ) ( )   ( )   ( )   ( )   + k N N k N k n n n Nk ++ k k k k kk X X X s in X c o s X s in X c o s    −−      ( 1 8 )     ( ) ( ) ( ) ( ) 2 + 1 2 + 1 22 2 + 1 2 + 1 2 4 + 1 4 + 1 2 2 4 2 4 + 3 4 + 3 4 1 1 33 ( ) - - -- = ( ) ( )   + ( )   ( )   + ( )   kk N k N k n n n N nn + k k k k kk X X X c o s X s in X c o s X s in         ( 1 9 )     ( ) ( ) ( ) ( ) 2 + 1 2 3 2 + 1 2 + 1 2 4 + 1 4 + 1 4 4 2 4 2 2 + 1 4 n + 3 4 n + 3 42 1 1 33 ( ) - - -- = ( ) ( )   ( )   ( )   ( )   k N N k N k n n n Nk ++ k k k k kk X X X s in X c o s X s in X c o s    +−      ( 2 0 )     Fo r   in - p lace   co m p u tatio n s ,   o th er   p o in ts   ( / 4 1 ) , ( / 2 1 ) , ( 3 / 4 1 )   an d     ( 1 )   n ee d   to   b c o m p u ted .   T h ese  p o in ts   ca n   b e   d er iv e d   u s in g   tr i g o n o m etr ic  id e n titi es  g iv en   b y   ( 1 7 an d   th p er io d icity   p r o p er ty   o f   DHT - I I ,   we  g et:     ( ) ( ) ( ) ( ) 2 + 1 2 + 1 22 2 + 1 2 + 1 2 4 + 1 4 + 1 4 4 2 4 2 4 + 3 4 + 3 4 1 1 1 1 33 ( - - ) - - - - -- = ( ) ( )   + ( )   ( )   + ( )   + kk N N k N k n n n N nn k k k k kk X X X c o s X s in X c o s X s in         ( 2 1 )     ( ) ( ) ( ) ( ) 2 + 1 2 2 + 1 2 + 1 2 4 + 1 4 + 1 2 2 2 4 2 2 + 1 4 n + 3 4 n + 3 42 1 1 1 1 33 ( - - ) - - - - -- = ( ) ( )   ( )   ( )   ( )   + k N N k N k n n n Nk k k k k kk X X X s in X c o s X s in X c o s    +−      ( 2 2 )     ( ) ( ) ( ) ( ) 2 + 1 2 + 1 22 3 2 + 1 2 + 1 2 4 + 1 4 + 1 4 4 2 4 2 4 + 3 4 + 3 4 1 1 1 1 33 ( - - ) - - - - -- = ( ) ( )   ( )   ( )   ( )   kk N N k N k n n n N nn k k k k kk X X X c o s X s in X c o s X s in    −+  −−     ( 2 3 )     ( ) ( ) ( ) ( ) 2 + 1 2 + 1 22 2 + 1 2 + 1 2 4 + 1 4 + 1 2 2 4 2 4 + 3 4 + 3 4 1 1 1 1 33 ( - - ) - - - - -- = ( ) ( )   ( )   ( )   ( )   kk N k N k n n n N nn N k k k k kk X X X s in X c o s X s in X c o s    −−      ( 2 4 )     Fro m   d ec o m p o s itio n s   ( 1 6 )   an d   ( 1 8 ) - ( 2 4 ) ,   it  is   clea r ly   th at  th is   alg o r ith m   p r o ce s s es  d ata   in   g r o u p s   o f   eig h t   p o in ts ,   s p ec if ically   ( ) , ( + / 4 ) , ( + / 2 ) , ( + 3 / 4 ) , ( / 4 1 ) , ( / 2 1 ) , ( 3 / 4 1 )   an d   ( 1 ) .   T h e   in d e x     i s   in   th r a n g 0 / 8 1 ,   with   th f ir s t     4 - p o in ts ,   f o u n d   f o r     = 0 ,   b ec o m es  ( 0 ) , ( / 4 ) , ( / 2 )   an d   ( 3 / 4 ) .   T h alg o r ith m   b u tter f ly     co n tain s   s p ec ial  in d e x in g   s ch em k n o wn   as  r etr o g r ad [ 2 3 ,   2 4 ] ,   i.e . ,   wh en   th n eg ativ e   in d ices  o f   s am p les  ( / 4 1 ) , ( / 2 1 ) , ( 3 / 4 1 )   an d   ( 1 )   ar d ec r em e n ted ,   t h p o s iti v in d ices  o f   s am p les  ( ) , ( + / 4 ) , ( + / 2 )   an d   ( + 3 / 4 )   ar in cr em en te d .   T h r esu ltan t     in - p lace   b u tter f ly   s tr u ctu r e   f o r   th is   alg o r ith m   is   s h o wn   in   Fig u r e   1.   Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KOM NI KA   T elec o m m u n   C o m p u t E l Co n tr o l         Dir ec t sp lit - r a d ix  a lg o r ith fo r   fa s t c o mp u ta tio n   o f ty p e - I I   d is crete … ( Mo u n ir   T aha   Ha mo o d )   3071       Fig u r 1 .   An   in - p lace   b u tter f ly   o f   th SR - DHT - I I   alg o r ith m wh er ( ) =  ( ( 2 + 1 ) / )     an d   ( ) =  ( ( ( 2 + 1 ) / ) ,   d o tted   an d   s o lid   lin es st an d   f o r   s u b tr ac tio n   an d   ad d itio n s   r esp ec tiv ely       3.   ARIT H M E T I C   CO M P L E X I T Y   In   (1 6 )   a n d   ( 1 8 - 24 )   r e p r e s e n t   t h e   d e c o m p o s i t i o n s   o f   t h e   d e v e l o p e d   D H T - II  s p l i t - r a d i x   a l g o r i t h m .   F o r   in - p l a c e   c o m p u t a t i o n ,   a   d o u b l e   b u t t e r f l y   i s   u s e d   a s   s h o w n   i n   F i g u r e   1 .   T h e r e f o r e ,   t h e   t r i v i a l   a r i t h m e t i c   o p e r a t i o n s   ( m u l t i p l y i n g   b y   - 1 ,   0 ,   1 )   w i l l   b e   r e m o v e d ;   t h e   r e s u l t a n t   b u t t e r f l y   c a l c u l a t e s   8   p o i n t s   a n d   r e q u i r e s   16   a d d i t i o n s   a n d   8   m u l t i p l i c a t i o n s .   T h e r e f o r e   f o r   t r a n s f o r m   l e n g t h   = 2 ,   t h e   s p l i t - r a d i x   D HT - I I   n e e d s    2     r o u n d s   o f   b u t t e r f l i e s   c o m p u t a t i o n   a n d   e a c h   r o u n d   u s e s   2   a d d i t i o n s   a n d     m u l t i p l i c a t i o n s .   A d d i t i o n a l l y ,   o n e   / 2   a n d   t w o   / 4   l e n g t h   D H T s - I I   m u s t   b e   c o m p u t e d ,   t h u s   t h e   w h o l e   s p l i t   r a d i x   D H T - II  f u l f i l ls   t h e   r e c u r r e n c e s :     24 24 ( ) ( ) 2 ( ) ( ) ( ) 2 ( ) 2 =+ =+ NN NN N NN M N + M M A + A A   ( 2 5 )     w h e r e   ( )   a n d   ( )   s t a n d   f o r   t h e   n u m b e r   o f   r e a l   a d d i t i o n s   a n d   m u l t i p l i c a t i o n s   r e s p e c t i v e l y .   S o l v i n g   t h e   c o m p l e x i t y   r e l a t i o n s   i n   (2 5 ) ,   b y   r e p e a t e d ly   s u b s t i t u t i o n   o f   t h e   i n i t i a l   v a l u e s   ( 4 ) = 2 ,   ( 4 ) = 6   a n d   ( 4 ) = 12 ,   ( 8 ) = 24 ,   w e   g e t   t h e   c l o s e d   f o r m   c o m p l e x i t y :     ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 2 2 2 1 1 18 19 18 8 39 44 39 () () l o g l o g =1 =1 m m N N N N N N N N M A   ( 2 6 )     C o m p a r i n g   t h e   c o m p u t a t i o n a l   c o m p l e x i t y   o f   t h e   r a d i x - 2   F H T   a l g o r i t h m   [ 2 5 ]   w i t h   t h i s   a l g o r i t h m   b a s e d   o t h e   s a m e   i m p l e m e n t a i o n ,   s h o w s   a n   i m p o r t a n t   s a v i n g   i n   t h e   a m o u n t   o f   a r i t h m e t i c   c o m p l e x i t y   c a n   b e   a c h i e v e d   a s   l i s t e d   i n   T a b l e   1 .   T h e   s a v i n g   i s   u p   t o   1 0 %   i n   t h e   n u m b e r   o f   a d d i t i o n s   a n d   a r o u n d   2 9 %   i n   t h e   n u m b e r   o f   m u l t i p l i c a t i o n s .       T ab le  1 .   C o u n ts   in   th ar i th m e tic  co m p lex ities   o f   s p lit - r ad ix   an d   r ad i x - 2   DHT - I I   alg o r ith m s     Tr a n sf o r m   L e n g t h   S p l it - r a i x   DHT - II   a l g o r i t h m (A )   R a d i x 2   DHT - I I   a l g o r i t h m (B)   S a v i n g   %   ( A / B )       Mu l t s.   Ad d s.   Mu l t s.   Ad d s.   Mu l t s.   Ad d s.   8   12   24   12   24   0   0   16   32   68   40   72   20   5 . 5 5   32   88   1 8 0   1 1 2   1 9 2   2 1 . 4 2     6 . 2 5   64   2 1 6   4 4 4   2 8 8   4 8 0   25   7 . 5 0   1 2 8   5 2 0   1 0 6 0   7 0 4   1 1 5 2   2 6 . 1 3   7 . 9 8   25 6   1 2 0 8   2 4 6 0   1 6 6 4   2 6 8 8   2 7 . 4 0   8 . 4 8   5 1 2   2 7 6 0   5 6 0 4   3 8 4 0   6 1 4 4   2 8 . 1 2   8 . 7 8   1 0 2 4   6 2 0 0   1 2 5 7 2   8 7 0 4   1 3 8 2 4   2 8 . 7 6   9 . 0 5       4.   CO NCLU SI O N   T h i s   p a p e r   p r e s e n t s   t h e   d e v e l o p m e n t   o f   a   n o v e l   d i r e c t   a l g o r i t h m   f o r   t h e   f a s t   c a l c u l a t i o n   o f   t h e   t y p e - I I   D H T   u s i n g   s p l i t - r a d i x   D I T   a p p r o a c h .   T h e   a l g o r i t h m   h a s   b e e n   i m p l e m e n t e d   a n d   i t s   a r i t h m e t i c al   c o m p l e x i t y   h a s   b e e n   a n a l y z e d .   C o m p a r i s o n s   b e t w e e n   t h e   d e v e l o p e d   a l g o r i t h m   a n d   t h e   b a s i c   r a d i x - 2   a l g o r i t h m ,   b a s e d   o n   t h e   a m o u n t   o f   t h e   a r i t h m e t i c al   o p e r a t i o n s   h a v e   b e e n   p e r f o r m e d .   T h i s   c o m p a r i s o n   h a s   r e v a e l   t h a t   t h e   d e v e l o p e d   s p l i t   r a d i x   a l g o r i t h m   i n v o l v e   m u c h   l e s s   a r i t h m e t i c al   c o m p l e x i t y   t h a n   r a d i x - 2   a l g o r i t h m   ( 1 0 %   s a v i n g   i n   t h e   n u m b e r   o f   a d d i t i o n s   a n d   a r o u n d   2 9 %   s a v i n g   i n   t h e   n u m b e r   o f   m u l t i p l i c a t i o n s   h a v e   b e e n   o b t a i n e d ) .   T h e   p r o p o s e d   a l g o r i t h m   Evaluation Warning : The document was created with Spire.PDF for Python.
                       I SS N :   1 6 9 3 - 6 9 3 0   T E L KOM NI KA   T elec o m m u n   C o m p u t E l Co n tr o l Vo l.  18 ,   No .   6 Dec em b e r   2 0 2 0 :    30 6 7   -   307 2   3072   h a s   r e g u l a r   a n d   s i m p l e   b u t t e r f l y   f r a m e w o r k ,   a n d   h a s   i n   p l a c e   c o m p u t a t i o n s .   T h e r e f o r e   i t   e n a b l e s   u s   t o   d e v e l o p   a n d   i m p r o v e   t h e   p e r f o r m a n c e   o f   t h e   m u l t i d i m e n s i o n a l   s p l i t - v e c t o r   r a d i x   ( S V R )   a l g o r i t h m s   f o r   t h e   m u l t i d i m e n s i o n al   ( M D )   G D H T   f o r   h i g h e r   d i m e n s i o n s   w i t h   r e g a r d   t o   a c c e s s e s   t o   t h e   l o o k u p   t a b l e   a n d   t o   t h e   n u m b e r   o f   t w i d d l e   f a c t o r   e s t i m a t i o n s   w i t h o u t   a n y   i n c r e a s e   i n   t h e   s t r u c t u r a l   o r   c o m p u t a t i o n a l   c o m p l e x i t i e s .       RE F E R E NC E S   [1 ]   R.   N.  Bra c e we ll ,   " Th e   Ha rtl e y   tra n sfo r m ,"   Ox f o rd   Un ive rs it y   Pre ss ,   In c . ,   1 9 8 6 .   [2 ]   G .   B i e t   a l . ,   " F a s t   g e n e r a l i z e d   D F T   a n d   D H T   a l g o r i t h m s , "   E l s e v i e r   S i g n a l   P r o c e s s i n g   J o u r n a l ,   v o l .   6 5 ,   n o .   3 ,   p p .   3 8 3 - 3 9 0 ,   1 9 9 8 .   [3 ]   H.  S o re n se n ,   D.  J o n e s,  C.   Bu rr u s,  a n d   M .   He id e m a n ,   " O n   c o m p u ti n g   t h e   d isc re te  Ha rtl e y   tr a n sfo rm , "   IE EE   T ra n sa c ti o n o n   Aco u stics ,   S p e e c h   a n d   S i g n a Pr o c e ss in g . ,   v o l.   3 3 ,   n o .   5 ,   p p .   1 2 3 1 - 1 2 3 8 ,   1 9 8 5 .   [4 ]   H.  Ne n g - C h u n g ,   I .   C .   H o n g ,   a n d   O.   K.  Erso y ,   " G e n e ra li z e d   d isc re te  Ha rtl e y   tra n sfo rm s,"   IEE E   T ra n sa c ti o n s   o n   S ig n a l   Pro c e ss in g ,   v o l.   4 0 ,   n o .   1 2 ,   p p .   2 9 3 1 - 2 9 4 0 ,   1 9 9 2 .   [5 ]   V.  Brit a n a k   a n d   K .   R.   Ra o ,   " Th e   fa st  g e n e ra li z e d   d isc re te  F o u rie tran sfo rm s:  u n if ied   a p p r o a c h   to   th e   d isc re te  sin u so i d a tran sf o rm s c o m p u tatio n , "   El se v ier   S ig n a Pro c e ss in g   J o u rn a l ,   v o l.   7 9 ,   n o .   2 ,   p p .   1 3 5 - 1 5 0 ,   1 9 9 9 .   [6 ]   M .   T.   Ha m o o d ,   " Ne De c ima ti o n - In - Ti m e   F a st  Ha rtl e y   Tran sfo r m   Alg o rit h m , "   In ter n a ti o n a J o u r n a o El e c trica l   a n d   Co m p u ter   E n g i n e e rin g ,   v o l.   6 ,   n o .   4 ,   p p .   1 6 5 4 - 1 6 6 1 ,   2 0 1 6 .   [7 ]   G .   B i   a n d   Y .   Z e n g ,   " T r a n s f o r m s   a n d   F a s t   A l g o r i t h m s   f o r   S i g n a l   A n a l y s i s   a n d   R e p r e s e n t a t i o n s ,"   B i r k h ä u s e r   B o s t o n 2012.   [8 ]   K.  Jo n e s,  " De sig n   a n d   p a ra ll e l   c o m p u tatio n   o f   re g u larise d   fa st  Ha r tl e y   tra n sfo rm , "   IEE   Pro c e e d i n g s - Vi sio n ,   Im a g e   a n d   S i g n a Pr o c e ss in g ,   p p .   7 0 - 78 ,   2 0 0 6 .   [9 ]   G .   A .   S h a h e t   a l . ,   " A   n e w   f a s t   r a d i x - 2   d e c i m a t i o n - in - f r e q u e n c y   a l g o r i t h m   f o r   c o m p u t i n g   t h e   d i s c r e t e   H a r t l e y   t r a n s f o r m , "   1 st   I n t e r n a t i o n a l   C o n f e r e n c e   o n   C o m p u t a t i o n a l   I n t e l l i g e n c e ,   C o m m u n i c a t i o n   S y s t e m s   a n d   N e t w o r k s ,   p p .   3 6 3 - 368 ,   2 0 0 9 .   [1 0 ]   M .   T.   Ha m o o d   a n d   S .   B o u ss a k ta,   " Ne ra d ix - b a se d   F HT  a l g o ri th m   fo c o m p u ti n g   t h e   d isc re te  Ha r tl e y   tran sf o rm , "   I EE In ter n a ti o n a C o n fer e n c e   o n   Aco u stics ,   S p e e c h   a n d   S i g n a P ro c e ss in g   (ICAS S P),   p p .   1 5 8 1 - 1 5 8 4 ,   2 0 1 1 .   [1 1 ]   P .   Du h a m e a n d   H.  H o ll m a n n ,   " S p li ra d ix '   F F a lg o rit h m , "   El e c tr o n ics   L e tt e r s,  v o l.   2 0 ,   n o .   1 ,   p p .   1 4 - 1 6 ,   1 9 8 4 .   [1 2 ]   S .   C .   C h a n e t   a l . ,   " S p l i t   v e c t o r - r a d i x   f a s t   F o u r i e r   t r a n s f o r m , "   I E E E   T .   S i g n a l .   P r o c e s . v o l .   4 0 ,   p p .   2 0 2 9 - 3 9 ,   1 9 9 2 .   [1 3 ]   W .   C .   Y e h e t   a l . ,   " H i g h - s p e e d   a n d   l o w   p o w e r   s p l i t - r a d i x   F F T , "   I E E E   T .   S i g n a l .   P r o c e s . v o l .   5 1 ,   n o .   3 ,   p p .   8 6 4 - 7 4 ,   2 0 0 3 .   [1 4 ]   N .   A n u p i n d i e t   a l . ,   " S p l i t - r a d i x   F H T   a l g o r i t h m   f o r   r e a l - s y m m e t r i c   d a t a , "   E l e c t r o n .   L e t t . v o l .   2 6 ,   n o .   2 3 ,   p p .   1 9 7 3 - 75,   1990.   [1 5 ]   S .   B o u g u e z e l,   M .   O.   Ah m a d ,   a n d   M .   N.  S .   S wa m y ,   " An   e ffici e n sp l it - ra d i x   F HT   a lg o rit h m , "   Pro c e e d in g s   o f     th e   2 0 0 4   In ter n a ti o n a S y mp o si u m o n   Circ u it s a n d   S y ste ms ,   2 0 0 4 .   [1 6 ]   M .   T .   H a m o o d ,   e t   a l . ,   " D e c i m a t i o n - in - f r e q u e n c y   s p l i t - r a d i x   a l g o r i t h m   f o r   c o m p u t i n g   n e w   M e r s e n n e   nu m b e r   t r a n s f o r m , "   I E E E   I n t e r n a t i o n a l   S y m p o s i u m   o n   S i g n a l   P r o c e s s i n g   a n d   I n f o r m a t i o n   T e c h n o l o g y   ( I S S P I T ) p p .   2 9 8 - 302 ,   2 0 1 0 .   [1 7 ]   D.  F .   Ch i p e r,   " S tru c t u re d   D u a S p li t - Ra d ix   Alg o rit h m   fo r   t h e   Disc re te  Ha rtl e y   Tra n sfo rm   o Le n g t h   2 N , "   S p rin g e Circ u it s,   S y s tem s,  a n d   S ig n a Pr o c e ss in g   J o u rn a l,   v o l .   3 7 ,   n o .   9 ,   p p .   2 9 0 - 3 0 4 ,   Ja n u a ry   0 1   2 0 1 8 .   [1 8 ]   P .   Du h a m e a n d   M .   Ve tt e rli ,   " F a st  F o u r ier  tran sfo rm s:  A   tu t o ria re v iew   a n d   a   sta te  o f   th e   a rt , "   El se v ier   S ig n a l   Pro c e ss in g   J o u rn a l,   v o l .   1 9 ,   n o .   4 ,   p p .   2 5 9 - 2 9 9 ,   1 9 9 0 .   [1 9 ]   H.  S o re n se n ,   M .   He id e m a n ,   a n d   C.   Bu rru s,  " O n   c o m p u t in g   th e   sp li t - ra d ix   F F T, "   IEE T ra n sa c ti o n o n   Aco u stics ,   S p e e c h   a n d   S i g n a Pr o c e ss in g ,   v o l.   3 4 ,   n o .   1 ,   p p .   1 5 2 - 1 5 6 ,   1 9 8 6 .   [2 0 ]   S .   B o u g u e z e l,   M .   O.   Ah m a d ,   a n d   M .   N.   S .   S wa m y ,   " A   n e s p li t - ra d ix   F HT   a l g o r it h m   fo r   len g th - q * 2 m   DH Ts, "   IEE T ra n sa c ti o n o n   Circ u it a n d   S y ste ms   I:  Reg u la Pa p e rs ,   v o l.   5 1 ,   n o .   1 0 ,   p p .   2 0 3 1 - 2 0 4 3 ,   2 0 0 4 .   [2 1 ]   K.  Jo n e s,  " Th e   Re g u lariz e d   F a st  Ha rtl e y   Tran sfo rm ,"   S p rin g e r S c i e n c e ,   2 0 0 9 .   [2 2 ]   Z.   Wan g ,   G .   A.  Ju ll ien e a l. ,   " T h e   g e n e ra li z e d   d isc re te  tran sf o rm   a n d   it a p p li c a ti o n   t o   in ter p o latio n , "   [ 1 9 9 2 ]   Co n fer e n c e   Rec o rd   o t h e   T we n ty - S ixth   Asi lo ma r C o n fer e n c e   o n   S i g n a ls,  S y ste ms   &   Co mp u ter s,   1 9 9 2 .   [2 3 ]   T.   Bo rtfel d   a n d   W.   Din ter,   " Ca l c u latio n   o m u lt i d ime n sio n a Ha rtl e y   tran sf o rm u sin g   o n e - d ime n sio n a l   F o u rier   tran sfo rm s,"   IEE T r a n sa c ti o n o n   S i g n a Pr o c e s sin g ,   v o l.   4 3 ,   n o .   5 ,   p p .   1 3 0 6 - 1 3 1 0 ,   1 9 9 5 .   [2 4 ]   O.  Nib o u c h e ,   S .   B o u ss a k ta,   M .   D a rn e ll ,   a n d   M .   Be n a issa ,   " Al g o ri t h m a n d   p ip e li n e   a rc h it e c tu re f o 2 - D   F F T   a n d   FFT - li k e   tran sfo rm s,"   El se v ier   Dig it a l   S i g n a Pr o c e ss in g   J o u rn a l,   v o l.   2 0 ,   n o .   4 ,   p p .   1 0 7 2 - 1 0 8 6 ,   2 0 1 0 .   [2 5 ]   M .   T.   Ha m o o d ,   " F a st  Alg o ri th m   fo Co m p u ti n g   t h e   Disc re te  Ha rtl e y   Tran sfo rm   o T y p e - II, "   In d o n e sia n   J o u rn a o f   El e c trica En g in e e rin g   a n d   In f o r ma ti c s (IJEEI),   v o l.   4 ,   n o .   2 ,   p p .   1 2 0 - 1 2 5 ,   2 0 1 6 .       B I O G RAP H I E S AU T H O R       M o u n i r   T a h a   H a m o o d   r e c e i v e d   t h e   B . S c .   d e g r e e   i n   e l e c t r i c a l   e n g i n e e r i n g   f r o m   U n i v e r s i t y   o f   T e c h n o l o g y ,   B a g h d a d ,   I r a q   i n   1 9 9 0   a n d   t h e   M . S c .   d e g r e e   i n   e l e c t r o n i c   a n d   c o m m u n i c a t i o n s   e n g i n e e r i n g   f r o m   A l - N a h r a i n   U n i v e r s i t y ,   B a g h d a d ,   I r a q   i n   1 9 9 5 .   H e   g r a d u a t e d   f r o m   N e w c a s t l e   U n i v e r s i t y ,   N e w c a s t l e   u p o n   T y n e ,   U . K   i n   2 0 1 2   w i t h   t h e   P h D   d e g r e e   i n   c o m m u n i c a t i o n s   a n d   s i g n a l   p r o c e s s i n g .   H i s   d o c t o r a l   r e s e a r c h   w a s   i n   t h e   d e v e l o p m e n t   o f   e f f i c i e n t   a l g o r i t h m s   f o r   f a s t   c o m p u t a t i o n   o f   d i s c r e t e   t r a n s f o r m s .   F r o m   2 0 1 2   t o   2 0 1 6   H e   w a s   a   l e c t u r e r   i n   s i g n a l   p r o c e s s i n g   f o r   c o m m u n i c a t i o n   a t   T i k r i t   U n i v e r s i t y .   H e   i s   c u r r e n t l y   a n   a s s o c i a t e   p r o f e s s o r   o f   s i g n a l   p r o c e s s i n g   a t     t h e   D e p a r t m e n t   o f   E l e c t r i c a l   E n g i n e e r i n g ,   C o l l e g e   o f   E n g i n e e r i n g ,   T i k r i t   U n i v e r s i t y ,   T i k r i t ,   I r a q .   H i s   r e s e a r c h   i n t e r e s t   i n c l u d e s   d i s c r e t e   t r a n s f o r m s ,   f a s t   a l g o r i t h m s   f o r   d i g i t a l   s i g n a l   p r o c e s s i n g   i n   o n e   a n d   m u l t i d i m e n s i o n a l   a p p l i c a t i o n s ,   a n d   c o m m u n i c a t i o n   s y s t e m s .     Evaluation Warning : The document was created with Spire.PDF for Python.