4_Rafayel_23--32_new.DVI


Mathematical Problems of Computer Science 48, 23{32, 2017.

About Complexity of FFT Algor ithms for Length of

q £ 2p

R a fa ye l V . B a r s e g h ya n

Institute for Informatics and Automation Problems of NAS RA

e-mail: rafayelbarseghyan@ipia.sci.am

Abstract

The paper presents logarithmic formula which allows to compute the exact number
of necessary operations for computing the discrete Fourier transform (DFT) of an
arbitrary q £ 2p - length, where q is an odd integer.

Keywords: Fast Fourier transform (FFT), Split-radix algorithm, Computational
complexity.

1 . In t r o d u c t io n

Th e d is c r e t e Fo u r ie r t r a n s fo r m ( D FT) h a s a wid e r a n g e o f a p p lic a t io n s in m a n y ¯ e ld s o f
s c ie n c e a n d e n g in e e r in g [1 ],[2 ]. Th e m a in r e a s o n fo r it s p o p u la r it y is t h e e xis t e n c e o f va r io u s
a lg o r it h m s wh ic h a llo ws t o s ig n i¯ c a n t ly r e d u c e t h e c o m p u t a t io n a l c o m p le xit y. Th e s e a lg o -
r it h m s a r e g e n e r a lly kn o wn a s fa s t Fo u r ie r t r a n s fo r m s ( FFT) . Fa s t a lg o r it h m fo r e ± c ie n t
c o m p u t a t io n o f D FT wa s ¯ r s t in t r o d u c e d b y Cu le y a n d Tu ke y b y t h e ir h is t o r ic a l p a p e r in
1 9 6 5 [3 ]. FFT a lg o r it h m s a llo w t o c o m p u t e D FT o f s iz e N wit h O ( N lg N ) o p e r a t io n s in
c o n t r a s t t o d ir e c t fo r m c o m p u t a t io n wh ic h r e qu ir e s O ( N 2 ) o p e r a t io n s . Th e r e a r e a n u m b e r
o f FFT a lg o r it h m s , b u t t h e m o s t p o p u la r m e t h o d s a r e b a s e d o n ¯ xe d -r a d ix a n d s p lit -r a d ix
a p p r o a c h e s . S p lit -r a d ix a lg o r it h m s h a ve b e e n c o n s id e r e d t o b e t h e m o s t c o m p u t a t io n a lly
e ± c ie n t a n d s t r u c t u r a lly r e g u la r .

S p lit -r a d ix a lg o r it h m wa s ¯ r s t in t r o d u c e d b y Y a vn e [4 ] in 1 9 6 9 a n d la t e r b y va r io u s
a u t h o r s [8 ]. S p lit -r a d ix a lg o r it h m a llo ws t o c o m p u t e D FT o f N = 2 p wit h 4 N lg N ¡ 6 N + 8
a r it h m e t ic o p e r a t io n s . In r e c e n t ye a r s b y va r io u s a u t h o r s [5 ], a n e w m o d i¯ c a t io n o f s p lit -
r a d ix a lg o r it h m wa s d e ve lo p e d wh ic h a llo ws t o p e r fo r m D FT o f N = 2 p wit h 34

9
N lg N ¡

124
27

N ¡ 2 lg N ¡ 2
9
( ¡ 1 ) lg N lg N + 16

27
( ¡1 ) lg N + 8 a r it h m e t ic o p e r a t io n s .

Fo r a p p lic a t io n s , wh ic h n e e d t o p e r fo r m D FT o f s iz e s N 6= 2 p, u s u a lly s p e c ia lis t s u s e t h e
z e r o p a d d in g t e c h n iqu e . It m e a n s t h a t t h e in p u t s e qu e n c e is ¯ lle d wit h z e r o e s u n t il it b e c o m e s
a p o we r o f t wo le n g t h fo r p e r fo r m in g a n y a va ila b le FFT a lg o r it h m . S u c h m e t h o d s ig n i¯ c a n t ly
d e c r e a s e s t h e r e qu ir e d n u m b e r o f a r it h m e t ic o p e r a t io n s . D FT fo r in p u t s e qu e n c e s wh ic h h a s
le n g t h n o n -p o we r -o f-2 is r e qu ir e d in m a n y p r a c t ic a l a p p lic a t io n s , it is a n im p o r t a n t p r o b le m .

A lg o r it h m fo r c o m p u t in g D FT fo r s iz e s q £ 2 p, wh e r e q is a n o d d in t e g e r , wa s in t r o d u c e d
b y B i a n d Ch e n in 1 9 9 8 [6 ]. A lg o r it h m h a s a 2 =4 s p lit -r a d ix s t r u c t u r e a n d in c a s e o f q = 1
h a s t h e s a m e c o m p le xit y a s t h e c o n ve n t io n a l s p lit -r a d ix FFT a lg o r it h m . A ft e r t h a t , in 2 0 0 4
b y B o u g u e z e l a n d e t . a l. [1 0 ] a n e w im p r o ve d a lg o r it h m fo r q£ 2 p le n g t h D FT wa s p r e s e n t e d .

2 3



2 4 About Complexity of FFT Algorithms for Length of q £ 2p

A lg o r it h m is b a s e d o n 2 = 8 s p lit -r a d ix FFT a lg o r it h m s c h e m e a n d im p r o ve s s u c h im p o r t a n t
fa c t o r s a s d a t a t r a n s fe r , a d d r e s s g e n e r a t io n , t wid d le fa c t o r c o m p u t a t io n a n d a c c e s s t o t h e
lo o ku p t a b le , b u t it d id n o t r e d u c e n u m b e r o f a r it h m e t ic o p e r a t io n s . In 2 0 1 0 B i a n d Ch e n [7 ]
p u b lis h e d a n e w p a p e r wh e r e t h e y p r e s e n t e d a u n i¯ e d m e t h o d fo r g e n e r a t io n o f 2 =2 a ( wh e r e
a is a n in t e g e r a n d a > 1 ) s p lit -r a d ix a lg o r it h m s fo r q £ 2 p le n g t h D FTs .

In t h is p a p e r a g e n e r a l lo g a r it h m ic fo r m u la is d e r ive d fo r c a lc u la t in g n u m b e r o f a r it h m e t ic
o p e r a t io n s fo r 2 = 4 a n d 2 =8 s p lit -r a d ix a lg o r it h m s fo r q £ 2 p le n g t h D FTs [1 4 ]. Fo r a ll q < 2 0
s p e c ia l c a s e s , fo r m u la s a r e d e ve lo p e d fo r c o u n t in g e xa c t n u m b e r o f a r it h m e t ic o p e r a t io n s
a n d s o m e c a s e s a r e s h o wn , wh e r e c o m p u t a t io n a l e ®e c t ive n e s s is in ve r s e ly p r o p o r t io n a l t o t h e
le n g t h o f t h e D FT-s iz e .

2 . Ge n e r a l A lg o r it h m

L e t x = fx0; x1; : : : ; xN¡1gT b e a c o m p le x va lu e d c o lu m n -ve c t o r o f le n g t h N, wh e r e N =
q £ 2 p a n d q is a n o d d in t e g e r . Th e D FT o f t h is ve c t o r a r e d e ¯ n e d a s

X[k] =
N ¡1X

k=0

x[n]W nkN ; ( 1 )

wh e r e
0 · k · N ¡ 1 ; W nN = e xp ( ¡j 2¼N n) = c o s (

2¼
N

n) ¡ j s in ( 2¼
N

n) ; j =
p
¡ 1 :

B e lo w t h e a lg o r it h m fr o m [7 ] is p r e s e n t e d . E ve n in d e xe s o f t h e t r a n s fo r m a r e c o m p u t e d b y

X[2 k] =
N=2¡1X

n=0

( x[n] + x[n + N=2 ]]) W nkN=2; ( 2 )

wh e r e X[2 k] is a n N=2 D FT. Th e o d d in d e xe s a r e d e ¯ n e d b y

X[2 ak + l] =
N ¡1X

n=0

x[n]W
n(2ak+l)
N ; ( 3 )

wh e r e 0 · k · ( N=2 a ) ¡ 1 , a n d a is a n in t e g e r ( a > 1 ) a n d l h a s a s e le c t e d o d d va lu e s s o
t h a t 2 ak + l g e n e r a t e s N=2 o d d in t e g e r s t h a t c a n b e u n iqu e ly m a t c h e d t o a ll t h e o d d in d e x
va lu e s b e t we e n 0 a n d N. W it h s o m e m a n ip u la t io n s b a s e d o n t h e p e r io d ic a n d s ym m e t r ic
p r o p e r t ie s o f W

n(2ak+l)
N , ( 3 ) c a n b e r e p r e s e n t e d a s

X[2 ak + l] =
(N=2a)¡1X

n=0

x0[n]W nlN W
nk
N=2a +

(N=2a)¡1X

n=0

x0[n + N=2 a]W
(n+N=2a)l
N W

nk
N=2a + : : :

+
(N=2a)¡1X

n=0

x0[n +
( a ¡ 1 ) N

2 a
]W

(n+
( a¡1) N

2a
)l

N W
nk
N=2a;

( 4 )

wh e r e n = 0 ; 1 ; 2 : : : ; N= 2 ¡ 1 a n d

x0[n] = x[n] ¡ x[n + N=2 ]: ( 5 )

It c a n b e o b s e r ve d t h a t ( 4 ) is a le n g t h -N=2 a D FT t h e in p u t s e qu e n c e o f wh ic h is t h e r e s u lt
o f t h e c o m p u t a t io n in s id e t h e b r a c ke t s o f ( 4 ) fo r n = 0 ; 1 ; 2 : : : ; N= 2 ¡ 1 . In s u m m a r y, t h e
e ve n in d e xe d o u t p u t s o f ( 1 ) a r e o b t a in e d fr o m o n e le n g t h -N= 2 D FT d e ¯ n e d in ( 2 ) b a s e d o n



R. Barseghyan 2 5

t h e r a d ix-2 d e c o m p o s it io n , a n d t h e o d d in d e xe d o u t p u t s a r e o b t a in e d fr o m a le n g t h -N= 2 a
D FTs , b a s e d o n t h e r a d ix-2 a d e c o m p o s it io n . Th e c o m p le xit y o f a lg o r it h m c a n b e c o m p u t e d
b y t h e fo llo win g e xp r e s s io n s :

C£N = C
£
N=2 + aC

£
N=2a +

N
2a

C£ + 2 N ¡ C£t ;
C+N = C

+
N=2 + aC

+
N=2a +

N
2a

C+ + 3 N ¡ C+t ;
( 6 )

wh e r e b y C£ a n d C+ d e n o t e t h e n u m b e r o f r e a l m u lt ip lic a t io n s a n d a d d it io n s t h a t a r e u s e d
fo r e a c h o f t h e in n e r s u m s d e ¯ n e d in ( 4 ) , a n d C£t a n d C

+
t is t h e n u m b e r o f r e a l m u lt ip lic a t io n s

a n d a d d it io n s s a ve d fr o m a ll t h e t r ivia l t wid d le fa c t o r s W nlN in ( 4 ) .

3 . 2 / 4 S p lit -R a d ix A lg o r it h m

Fo r a = 2 t h e a lg o r it h m b e c o m e s a m o d i¯ e d ve r s io n o f c o n ve n t io n a l 2 = 4 s p lit -r a d ix a lg o r it h m .
In s e r t in g a = 2 in t o ( 4 ) we g e t

X[4 k + l] =
N=4¡1X

n=0

W nlN (
1X

n=0

x0[n + i
N

4
]W ilN=4 ) W

nk
N=4 =

=
N=4¡1X

n=0

W nlN ( x
0[n] + ( ¡j ) lx0[n + N

4
]) W nkN=4;

( 7 )

Fr o m ( 7 ) we c a n s e e t h a t it b e c o m e s a c o n ve n t io n a l s p lit -r a d ix a lg o r it h m wh ic h is r e p o r t e d
in [4 ],[8 ],[9 ]. To c o ve r a ll o d d in d e xe s we s e t l = f¡ 1 ; 1 g. In t h is c a s e , we h a ve a n a r it h m e t ic
c o m p u t a t io n a l g a in o n ly in c a s e s o f n = 0 a n d n = N=8 ( W 0N a n d W

lN=8
N t wid d le fa c t o r s

b e c o m e t r ivia l) .
N o w it is e a s y t o s e e t h a t t h e n u m b e r o f a r it h m e t ic o p e r a t io n s a r e

C+N = C
+
N=2 + 2 C

+
N=4 + 4 N ¡ 4 q

C£N = C
£
N=2

+ 2 C£
N=4

+ 2 N ¡ 1 2 q:
( 8 )

U s in g t h e t h e o r y o f d i®e r e n c e e qu a t io n s a n d Ma xim a [1 2 ] c o m p u t e r a lg e b r a s ys t e m , we g e t
t h e n u m b e r o f a r it h m e t ic o p e r a t io n s r e qu ir e d fo r c o m p u t a t io n o f ( 7 ) in lo g a r it h m ic fo r m

C+N = ¡
2p(28q¡3C+2q¡3C

+
q )

9
+

(¡1)p(10q¡3C+2q+6C
+
q )

9
+ p2

p+3q
3

+ 2 q;

C£N = ¡
2p(44q¡3C£2q¡3C

£
q )

9
¡ (¡1)

p
(10q+3C

£
2q ¡6C

£
q )

9
+ p2

p+2q
3

+ 6 q;
( 9 )

wh e r e Cq a n d C2q d e n o t e t h e c o m p le xit ie s o f q a n d 2 q le n g t h D FTs , r e s p e c t ive ly. U s in g
m e t h o d s fr o m [6 ] fo r c o m p u t in g 2 q-le n g t h D FT we o b t a in

C+N = 2 C
+
q + 4 q;

C£N = 2 C
£
q ;

( 1 0 )

¯ n a lly s u b s t it u t in g ( 1 0 ) in t o ( 9 ) a n d 2 p = N
q

we g e t

C+N =
8
3
pq 2 p ¡ 2p

9
( 1 6 q ¡ 9 C+q ) ¡ 29 q ( ¡ 1 )

p + 2 q;

C£N =
4
3
pq 2 p ¡ 2p

9
( 4 4 q ¡ 9 C£q ) ¡ 109 q ( ¡1 )

p + 6 q;
( 1 1 )



2 6 About Complexity of FFT Algorithms for Length of q £ 2p

4 q-le n g t h D FT c a n b e c o m p u t e d b y

C+4q = 4 C
+
q + 1 6 q

C£4q = 4 C
£
q

U s in g it a n d ( 8 ) , ¯ n a lly we g e t t h e fo r m u la s wh ic h s h o w t h e n u m b e r o f r e a l a r it h m e t ic
o p e r a t io n s o f q £ 2 p

C+N =
8
3
pq 2 p ¡ 2p

9
( 1 6 q ¡ 9 C+q ) ¡ 29 q ( ¡1 )

p + 2 q =;

= 8
3
N lo g 2

³
N
q

´
¡ N

³
16
9
¡ 1

q
C+q

´
¡ 2

9
q ( ¡ 1 ) log2 (

N
q ) + 2 q;

C£N =
4
3
pq 2 p ¡ 2p

9
( 3 8 q ¡ 9 C£q ) + 29 q ( ¡1 )

p + 6 q =;

= 4
3
N lo g 2

³
N
q

´
¡ N

³
38
9
¡ 1

q
C+q

´
+ 2

9
q ( ¡ 1 ) log2 (

N
q ) + 6 q:

( 1 2 )

If q = 1 a n d , t h e r e fo r e C+1 = 0 a n d C
+
1 = 0 fr o m ( 1 2 ) we c a n g e t

C+N =
8
3
N lo g 2 N ¡ 169 N ¡

2
9
( ¡1 ) log2 N + 2 ;

C£N =
8
3
N lo g 2 N ¡ 389 N +

2
9
( ¡1 ) log2 N + 6 :

( 1 3 )

( 1 3 ) is t h e s a m e a s t h e n u m b e r o f r e a l a r it h m e t ic o p e r a t io n s c o u n t r e qu ir e d b y c o n ve n t io n a l
s p lit -r a d ix a lg o r it h m . D o in g s o m e o p t im iz a t io n fr o m [6 ], we g e t t h e fo llo win g r e c u r r e n t
e xp r e s s io n s fo r c o m p u t in g 8 q le n g t h D FTs .

C+N = C
+
4q + 4 C

+
q + 3 6 q = 8 C

+
q + 5 2 q;

C£N = C
£
4q + 2 C

£
q + 2 C

£
sq = 6 C

£
q + 2 C

£
sq;

( 1 4 )

wh e r e C£sq d e n o t e s t h e n u m b e r o f a r it h m e t ic o p e r a t io n s r e qu ir e d b y s c a le d D FT [6 ]. U s in g
( 1 4 ) , we g e t a n im p r o ve m e n t in t h e n u m b e r o f a r it h m e t ic o p e r a t io n s

C+N =
8
3
pq 2 p ¡ 2p

9
( 1 6 q ¡ 9 C+q ) ¡ 29 q ( ¡ 1 )

p + 2 q =;

= 8
3
N lo g 2

³
N
q

´
¡ N

³
16
9
¡ 1

q
C+q

´
¡ 2

9
q ( ¡ 1 ) log2 (

N
q ) + 2 q;

C£N =
4
3
pq 2 p ¡ 2p

18
( 8 2 q ¡ 3 ( 5 C£q + C£sq ) ) + 29 ( 7 q + 3 ( C

£
q ¡ C£sq ) ) ( ¡1 ) p + 6 q =;

= 4
3
N lo g 2

³
N
q

´
¡ N

18

³
8 2 ¡ 3

q
( 5 C£q + C

£
sq )

´
+ 2

9
( 7 q + 3 ( C£q ¡ C£sq ) ) ( ¡ 1 )

log2 ( Nq ) + 6 q:

( 1 5 )

3 .1 Co m p le xit y o f 2 =4 S p lit -R a d ix A lg o r it h m fo r q < 2 0
In [6 ] a m e t h o d fo r c o m p u t in g 3 -p o in t D FT wit h o p t im iz a t io n in c a s e o f 2 4 -p o in t is p r e s e n t e d . 
U s in g t h a t r e s u lt we c a n g e t a c o m p le t e e xp r e s s io n wh ic h d e s c r ib e s t h e n u m b e r o f a r it h m e t ic
o p e r a t io n s r e qu ir e d b y 3 £ 2 p-le n g t h D FT.

C+N ( 3 £ 2 p ) = 8 p2 p + 203 2
p ¡ 2

3
( ¡ 1 ) p + 6 =

= 8
3
Nlo g 2 (

N
3
) + 20

9
N ¡ 2

3
( ¡ 1 ) log2( N3 ) + 6 ;

C£N ( 3 £ 2 p ) = 4 p 2 p ¡ 1 1 2 p + 2 ( ¡1 )
p
+ 1 8 =

= 4
3
Nlo g 2 (

N
3
) ¡ 11

3
N + 2 ( ¡ 1 ) log2( N3 ) + 1 8 :

( 1 6 )



R. Barseghyan 2 7

Fo r q = 9

C+N ( 9 £ 2 p ) = 2 4 p 2 p + 6 8 2 p ¡ 2 ( ¡ 1 )
p
+ 1 8 =

= 8
3
Nlo g 2

³
N
9

´
¡ 68

81
N ¡ 2

3
( ¡ 1 ) log2 (

N
9 ) + 1 8 ;

C£N ( 9 £ 2 p ) = 1 2 p 2 p ¡ 2 4 2 p + 1 0 ( ¡ 1 )
p
+ 5 4 =

= 4
3
Nlo g 2

³
N
9

´
¡ 8

3
N + 1 0 ( ¡ 1 ) log2 (

N
9 ) + 5 4 :

( 1 7 )

Fo r q = 1 5

C+N ( 1 5 £ 2 p ) = 4 0 p 2 p + 4243 2
p ¡ 10

3
( ¡ 1 ) p + 3 0 =

= 8
3
Nlo g 2

³
N
15

´
¡ 424

45
N ¡ 10

3
( ¡ 1 ) log2 (

N
15 ) + 3 0 ;

C£N ( 1 5 £ 2 p ) = 2 0 p 2 p ¡ 1093 2
p + 46

3
( ¡ 1 ) p + 9 0 =

= 4
3
Nlo g 2

³
N
15

´
¡ 109

45
N ¡ 2

3
( ¡1 ) log2 (

N
15 ) + 9 0 :

( 1 8 )

Fo r c o m p u t in g q = 7 le n g t h D FT, we u s e t h e m e t h o d p r e s e n t e d in [1 3 ]. Th a t m e t h o d a llo ws
t o c o m p u t e D FT wit h C+7 = 7 2 ; C

£
7 = 1 6 . Fo r g e t t in g a fu ll lo g a r it h m ic e xp r e s s io n fo r

7 £ 2 p, we u s e ( 1 2 ) .

C+N ( 7 £ 2 p ) = 73 2
3+pp + 67

9
2 3+p ¡ 14

9
( ¡ 1 ) p + 1 4 =

= 8
3
N lo g 2

³
N
7

´
+ 536

63
N ¡ 14

9
( ¡ 1 ) log2 (

N
7 ) + 1 4 ;

C£N ( 7 £ 2 p ) = 73 2
2+pp ¡ 61

18
2 p + 14

9
( ¡ 1 ) p + 4 2 =

= 4
3
N lo g 2

³
N
7

´
¡ 61

126
N + 14

9
( ¡ 1 ) log2 (

N
7 ) + 4 2 :

( 1 9 )

In c a s e o f q = 1 1 fr o m [1 3 ], we h a ve C+11 = 1 6 8 ; C
£
11 = 4 0

C+N ( 1 1 £ 2 p ) = 113 2
3+pp + 167

9
2 3+p ¡ 22

9
( ¡ 1 ) p + 2 2 =

= 8
3
Nlo g 2

³
N
11

´
+ 1336

99
N ¡ 22

9
( ¡ 1 ) log2 (

N
11 ) + 2 2 ;

C£N ( 1 1 £ 2 p ) = 113 2
2+pp ¡ 29

9
2 1+p + 22

9
( ¡ 1 ) p + 6 6 =

= 4
3
Nlo g 2

³
N
11

´
¡ 58

99
N + 22

9
( ¡ 1 ) log2 (

N
7 ) + 6 6 :

( 2 0 )

In c a s e o f q = 1 3 fr o m [1 3 ], we h a ve C+13 = 1 8 8 ; C
£
13 = 4 0

C+N ( 1 3 £ 2 p ) = 133 2
3+pp + 371

9
2 2+p ¡ 26

9
( ¡ 1 ) p + 2 6 =

= 8
3
Nlo g 2

³
N
13

´
+ 1484

117
N ¡ 26

9
( ¡ 1 ) log2 (

N
13 ) + 2 6 ;

C£N ( 1 3 £ 2 p ) = 133 2
2+pp ¡ 67

9
2 1+p + 26

9
( ¡ 1 ) p + 7 8 =

4
3
Nlo g 2

³
N
7

´
¡ 134

117
N + 26

9
( ¡1 ) log2 (

N
7 ) + 7 8 :

( 2 1 )



2 8 About Complexity of FFT Algorithms for Length of q £ 2p

In c a s e o f q = 1 7 fr o m [1 3 ], we h a ve C+17 = 2 7 4 ; C
£
13 = 8 2

C+N ( 1 7 £ 2 p ) = 173 2
3+pp + 1097

9
2 1+p ¡ 34

9
( ¡ 1 ) p + 3 4 =

= 8
3
Nlo g 2

³
N
17

´
+ 2194

153
N ¡ 34

9
( ¡ 1 ) log2 (

N
17 ) + 3 4 ;

C£N ( 1 7 £ 2 p ) = 173 2
2+pp + 23

9
2 2+p + 34

9
( ¡1 ) p + 1 0 2 =

= 4
3
Nlo g 2

³
N
17

´
¡ 92

153
N + 34

9
( ¡ 1 ) log2 (

N
17 ) + 1 0 2 :

( 2 2 )

In c a s e o f q = 1 9 fr o m [1 3 ], we h a ve C+19 = 4 0 4 ; C
£
19 = 7 6

C+N ( 1 9 £ 2 p ) = 193 2
3+pp + 833

9
2 2+p ¡ 38

9
( ¡1 ) p + 3 8 =

= 8
3
Nlo g 2

³
N
19

´
+ 3332

171
N ¡ 38

9
( ¡ 1 ) log2 (

N
19 ) + 3 8 ;

C£N ( 1 9 £ 2 p ) = 193 2
2+pp ¡ 19

9
2 1+p + 38

9
( ¡ 1 ) p + 1 1 4 =

= 4
3
Nlo g 2

³
N
19

´
¡ 38

171
N + 38

9
( ¡1 ) log2 (

N
19 ) + 1 1 4 :

( 2 3 )

4 . 2 / 8 S p lit -R a d ix A lg o r it h m

In c a s e o f a = 4 , t h e a lg o r it h m b e c o m e s 2 =8 s p lit -r a d ix a lg o r it h m .

X[8 k + l] =
N=4¡1X

n=0

W nlN (
3X

n=0

x0[n + i
N

8
]W il8 ) W

nk
N=8: ( 2 4 )

Th e t o t a l n u m b e r s o f r e a l m u lt ip lic a t io n s a n d r e a l a d d it io n s n e e d e d b y t h e a lg o r it h m a r e

C+N = C
+
N=2

+ 4 C+
N=8

+ 11
2
N ¡ C+t

C£N = C
£
N=2

+ 4 C£
N=8

+ 5
2
N ¡ C£t :

( 2 5 )

B e lo w t h e n u m b e r o f a r it h m e t ic o p e r a t io n s in lo g a r it h m ic fo r m a r e p r e s e n t e d

C+N =
11
4
pq 2 p ¡ 55

16
q 2 p ¡ 1

8
2 p

³
C+t ¡ ( 2 C+q + C+2qC+4q )

´
+ 1

4
C+t +

+( ¡ 1 ) p 2 p=2 [7 ( 1 2 C+q ¡ 2 ( C+2q + C+4q + C+t ) + 5 5 q ) c o s ( p a r c t a n (
p

7 ) )

+
p

7 ( 4 C+q ¡ 2 ( 1 1 C+2q ¡ 5 C+4q ¡ C+t ) ¡ 9 9 q ) s in ( p a r c t a n (
p

7 ) ) ]

C£N =
5
4
pq 2 p ¡ 25

16
q 2 p ¡ 1

8
2 p

³
C£t ¡ ( 2 C£q + C£2qC£4q )

´
+ 1

4
C£t +

+( ¡ 1 ) p 2 p=2 [7 ( 2 ( C£t ¡ 6 C£q + C£2q + C£4q ) ¡ 2 5 q ) c o s ( p a r c t a n (
p

7 ) )

+
p

7 ( C£t + 4 C
£
q ¡ 2 2 C£2q + 5 C£4q ¡ 4 5 q ) s in ( p a r c t a n (

p
7 ) ) ]:

( 2 6 )

wh e r e b y Cq,C2q a n d C4q d e n o t e n u m b e r o f a r it h m e t ic o p e r a t io n s r e qu ir e d fo r c o m p u t a t io n s
o f q, 2 q a n d 4 q le n g t h D FTs , r e s p e c t ive ly. Fo r c o m p u t in g 2 q a n d 4 q le n g t h D FT, we c a n u s e



R. Barseghyan 2 9

m e t h o d s d e s c r ib e d in t h e p r e vio u s s e c t io n , wh ic h a llo ws t o r e wr it e ( 2 6 )

C+N =
11
4
pq 2 p ¡ 15

16
q 2 p ¡ 1

8
2 p

³
C+t ¡ 8 C+q

´
+ 1

4
C+t +

+( ¡ 1 ) p 2 p=2 [7 ( 1 5 q ¡ 2 C+t ) c o s ( p a r c t a n (
p

7 ) )

+
p

7 ( 2 C+t ¡ 2 7 q ) s in ( p a r c t a n (
p

7 ) ) ]

C£N =
5
4
pq 2 p ¡ 25

16
q 2 p ¡ 1

8
2 p

³
C£t ¡ 8 C£q

´
+ 1

4
C£t +

+( ¡ 1 ) p 2 p=2 [7 ( 2 5 q ¡ 2 C£t ) c o s ( p a r c t a n (
p

7 ) )

+
p

7 ( 2 C£t ¡ 4 5 q ) s in ( p a r c t a n (
p

7 ) ) ]:

( 2 7 )

4 .1 Co m p le xit y o f 2 =8 S p lit -R a d ix A lg o r it h m fo r q < 2 0
In c a s e o f q = 1 5 , we h a ve C+15 = 1 6 8 ; C

£
15 = 3 0 a n d fr o m [7 ] C

+
t = 1 8 0 ; C

£
t = 6 0 a n d

t h e r e fo r e
C+N =

11
4
pq 2 p ¡ 15

16
q 2 p ¡ 1

8
2 p

³
C+t ¡ 8 C+q

´
+ 1

4
C+t +

+( ¡ 1 ) p 2 p=2 [7 ( 1 5 q ¡ 2 C+t ) c o s ( p a r c t a n (
p

7 ) )

+
p

7 ( 2 C+t ¡ 2 7 q ) s in ( p a r c t a n (
p

7 ) ) ]

C£N ( 1 5 £ 2 p ) = 54 p 1 5 £ 2
p ¡ 17

16
1 5 £ 2 p ¡ 15

16
( ¡1 ) p 2 p=2 ( ) + 4 5

+( ¡ 1 ) p 2 p=2 [7 ( 2 5 q ¡ 2 C£t ) c o s ( p a r c t a n (
p

7 ) )

+
p

7 ( 2 C£t ¡ 4 5 q ) s in ( p a r c t a n (
p

7 ) ) ]:

( 2 8 )

5 . Co m p a r is o n

Th e n u m b e r o f a d d it io n s a n d m u lt ip lic a t io n s r e qu ir e d fo r c o m p u t in g D FT fo r va r io u s le n g t h s
a r e p r e s e n t e d in Ta b le 1 ( 2 =4 s p lit -r a d ix a lg o r it h m ) . A s a n e xa m p le a r a n g e fr o m 2 5 6 t o
2 0 4 8 is c h o s e n . U s in g o n ly c o n ve n t io n a l a lg o r it h m fo r 2 p we h a ve o n ly c o m p u t e D FT o f
2 5 6 ; 5 1 2 ; 1 0 2 4 ; 2 0 4 8 s iz e s . If s iz e is n o t e qu a l t o t h e s e va lu e s we n e e d t o p a d t h e in p u t d a t a
u p t o n e xt 2 p. U s in g q £ 2 p a lg o r it h m a llo ws t o c o ve r t h e r a n g e 2 5 6 ¡ 1 0 2 4 wit h 2 7 n e w
p o in t s . Th is a p p r o a c h a llo ws t o s ig n ī c a n t ly r e d u c e t h e n u m b e r o f a r it h m e t ic o p e r a t io n s .
To ¯ n d o u t t h e q fo r wh ic h t h e a lg o r it h m b e c o m e s t h e m o s t e ± c ie n t in t e r m s o f t h e n u m b e r
o f a r it h m e t ic o p e r a t io n s , ¯ r s t o f a ll we c u t t h e va lu e s o f q fo r wh ic h
CN1 > CN2, b u t N1 < N2, wh e r e CN = C

+
N +C

£
N . It is e a s y t o s e e t h a t o n ly fo r 1 ; 3 ; 5 ; 9 ; 1 3 ; 1 5

c o n d it io n p r e s e n t e d a b o ve is t r u e . Fo r g e t t in g m o r e a c c u r a t e r e s u lt s we c o m p a r e t h e va lu e
o f EN =

CN
N

. Fin a lly we g e t

EN ( 9 £ 2 p ) < EN ( 9 £ 3 p ) < EN ( 9 £ 1 5 p ) < EN ( 1 £ 2 p ) <

< EN ( 5 £ 2 p ) < EN ( 1 5 £ 2 p ) :



3 0 About Complexity of FFT Algorithms for Length of q £ 2p

Table 1: Number of arithmetic operations required by 2=4 split-radix algorithm for the DFT

length 256 ¡ 1024

N q p Add. Mul. Count

256 1 8 5380 1284 6664

272 17 4 6832 1720 8552
288 9 5 6036 1196 7232
304 19 4 9200 1672 10872
320 5 6 6736 1880 8616
352 11 5 9468 2204 11672
360 45 3 7812 1140 8952
384 3 7 8028 2192 10220
416 13 5 10852 2372 13224
448 7 6 10992 2760 13752
480 15 5 10956 2112 13068

512 1 9 12292 3076 15368

544 17 5 15092 4052 19144
576 9 6 13584 3136 16720
608 19 5 19996 4028 24024
640 5 7 15172 4580 19752
704 11 6 20784 5288 26072
720 45 4 17424 3000 20424
768 3 8 18096 5396 23492
832 13 6 23888 5784 29672
896 7 7 24364 6668 31032
960 15 6 24432 5460 29892

1024 1 10 27652 7172 34824

1088 17 6 33040 9464 42504
1152 9 7 30228 7724 37952
1216 19 6 43184 9576 52760
1280 5 8 33744 10840 44584
1408 11 7 45308 12380 57688
1440 45 5 38628 7620 46248
1536 3 9 40284 12816 53100
1664 13 7 52196 13700 65896
1792 7 8 53488 15688 69176
1920 15 7 53964 13344 67308

2048 1 11 61444 16388 77832

In Ta b le 2 a r e p r e s e n t e d t h e c o m p a r is o n r e s u lt s fo r t h e va r io u s le n g t h D FTs ( 2 =8 s p lit -r a d ix
a lg o r it h m ) .



R. Barseghyan 3 1

Table 2: Number of arithmetic operations required by 2=4 split-radix algorithm for the DFT

length 256 ¡ 2048

N q p Add. Mul. Count

256 1 8 5380 1284 6664

360 45 3 8048 1360 9408
480 15 5 11256 2520 13776

512 1 9 12292 3076 15368

720 45 4 18076 3620 21696
960 15 6 25212 6180 31392

1024 1 10 27652 7172 34824

1440 45 5 39696 8640 48336
1920 15 7 55824 14880 70704

2048 1 11 61444 16388 77832

6 . Co n c lu s io n

In c a s e o f lo o kin g fo r c o m p u t a t io n a lly e ± c ie n t a lg o r it h m in t e r m s o f n u m b e r o f m u lt ip lic a -
t io n s in g e n e r a l c a s e we n e e d t o c h o o s e 2 =8 s p lit -r a d ix FFT a lg o r it h m , b e c a u s e c o e ± c ie n t o f
N lo g 2 is s m a lle r . E ± c ie n c y o f a lg o r it h m s in t e r m s o f t o t a l n u m b e r o f a r it h m e t ic o p e r a t io n s
is d is c u s s e d b e lo w.
Th e t o t a l n u m b e r o f a r it h m e t ic o p e r a t io n s r e qu ir e d b y 2 = 4 s p lit -r a d ix a lg o r it h m c a n b e
c o m p u t e d u s in g ( 1 2 ) a n d is p r e s e n t e d b e lo w

CN ( 2 =4 ) = 4 pq 2
p ¡ 2 p ( 6 q ¡ C+q ) + 8 q: ( 2 9 )

Th e t o t a l n u m b e r o f a r it h m e t ic o p e r a t io n s r e qu ir e d fo r c o m p u t a t io n 2 =8 s p lit -r a d ix a lg o r it h m
c a n b e r e t r ie ve d fr o m ( 2 8 )

CN ( 2 =8 ) = 4 pq 2
p ¡ 2 p ( 5

2
q ¡ ( 1

8
Ct ¡ Cq ) ) + 8 q+

+2 ( ¡ 1 ) p 2 p=2 £ [7 ( 2 0 q ¡ Ct ) c o s ( ® ) +
+
p

7 ( Ct ¡ 3 6 q ) s in ( ® ) :]
( 3 0 )

Fo r g e t t in g a c o m p u t a t io n a lly e ± c ie n t a lg o r it h m , we n e e d t o c a lc u la t e CN ( 2 =4 ) ¡ CN ( 2 = 8 )
u s in g ( 2 9 ) a n d ( 3 0 ) . Fo r s im p lic it y, o n ly t h e c o e ± c ie n t s fo r 2 p a n d q £ 2 p a r e in c lu d e d

CN ( 2 =4 ) ¡ CN ( 2 =8 ) = ( 72 q ¡
1
8
Ct ) 2

p < 0
Ct > 2 8 q:

In o t h e r wo r d s we c a n s a y t h a t if Ct is g r e a t e r t h a n 2 8 q, 2 =4 s p lit -r a d ix a lg o r it h m is m o r e
e ± c ie n t c o m p a r e d t o CN ( 2 =8 ) .

Refer ences

[1 ] E . O. B r ig h a m , The F ast F ourier Applications, E n g le wo o d Cli®s , N J, P r e n t ic e -H a ll,
1 9 8 8 .

[2 ] J. K . E r s o y, F ourier-R elated Transforms. F ast Algorithms and Applications, E n g le wo o d
Cli®s , N J, P r e n t ic e -H a ll,1 9 9 7 .



3 2 About Complexity of FFT Algorithms for Length of q £ 2p

[3 ] J. W . Co o le y a n d J. W . Tu ke y, \ A n a lg o r it h m fo r t h e m a c h in e c o m p u t a t io n o f t h e
c o m p le x Fo u r ie r s e r ie s ," M ath. Computation, p p . 2 9 7 { 3 0 1 , 1 9 6 5 .

[4 ] R . Y a vn e , \ A n e c o n o m ic a l m e t h o d fo r c a lc u la t in g t h e d is c r e t e Fo u r ie r t r a n s fo r m ," in
P roc. AF IP S, vo l. 3 3 , p p . 1 1 5 { 1 2 5 , 1 9 6 8 .

[5 ] M. Fr ig o a n d S . G. Jo h n s o n , \ A m o d i¯ e d s p lit -r a d ix FFT wit h fe we r a r it h m e t ic o p e r a -
t io n s " , Ieee Trans. Signal P rocessing, vo l. 5 5 , p p . 1 1 1 -1 1 9 , 2 2 0 7 .

[6 ] G. B i a n d Y . Q. Ch e n , \ Fa s t D FT a lg o r it h m fo r le n g t h N = q £ 2 p," IE E E Trans.
Circuits and Systems II, vo l. 4 5 , n o . 6 , p p . 6 8 5 - 6 9 0 , 1 9 9 8 .

[7 ] G. B i, G. L i a n d X . L i, \ A u n i¯ e d e xp r e s s io n fo r s p lit -r a d ix D FT a lg o r it h m s ," p p . 3 2 3
- 3 2 6 , 2 0 1 0 .

[8 ] P . D u h a m e l, \ Im p le m e n t a t io n o f s p lit -r a d ix FFT a lg o r it h m s fo r c o m p le x, r e a l, a n d r e a l-
s ym m e t r ic d a t a " , IE E E Trans. Acoust., Speech, Signal P rocess., vo l. 3 4 , p p . 2 8 5 - 2 9 5 ,
A p r il, 1 9 8 6 .

[9 ] H . V . S o r e n s e n , M. T. H e id e m a n a n d C. S . B u r r u s , " On c o m p u t in g t h e s p lit -r a d ix
FFT," IE E E Tr a n s . A c o u s t ., S p e e c h , S ig n a l P r o c e s s ., vo l. 3 4 ,p p . 1 5 2 - 1 5 6 , Fe b . 1 9 8 6 .

[1 0 ] S . B o u g u e z e l, M. Om a ir a n d M. N . S . S wa m y, \ A n e w r a d ix-2 / 8 FFT a lg o r it h m fo r
le n g t h -q £ 2 m D FTs ," IE E E Trans. Circuits and Systems I, vo l. 5 1 , n o . 1 , p p . 1 7 2 3 -
1 7 3 2 , 2 0 0 4 .

[1 1 ] S . B o u g u e z e l, M. Om a ir a n d M. N . S . S wa m y, \ A g e n e r a l c la s s o f s p lit -r a d ix FFT a lg o -
r it h m s fo r t h e c o m p u t a t io n o f t h e D FT o f le n g t h -2 m," IE E E Trans. Signal P rocessing,
vo l. 5 5 , n o . 8 , p p . 4 1 2 7 - 4 1 3 8 , 2 0 0 7 .

[1 2 ] On lin e : [A va ila b le ] h t t p :/ / m a xim a .s o u r c e fo r g e .n e t
[1 3 ] I. S e le s n ic k a n d S . B u r r u s , \ P r o g r a m s fo r P r im e L e n g t h FFTs ,"

h t t p :/ / c n x.o r g / c o n t e n t / m 1 8 1 3 7 / 1 .5 / .
[1 4 ] R . B a r s e g h ya n , \ Co m p le xit y o f t h e c o m p o s it e le n g t h FFT a lg o r it h m s " , P roceedings of

International Conference CSIT 2015, Y e r e va n , A r m e n ia , 2 0 1 5 .

Submitted 22.08.2017, accepted 06.12.2017.

q £ 2 p - »ñϳñáõÃÛ³Ý ü²¼-µ³ñ¹áõÃÛ³Ý Ù³ëÇÝ
è. ´³ñë»ÕÛ³Ý

²Ù÷á÷áõÙ

²ß˳ï³ÝùáõÙ ëï³óí³Í ¿ Éá·³ñÇÃÙ³Ï³Ý µ³Ý³Ó¨Á, áñÁ Ï³Ù³Û³Ï³Ý q £
2 p-»ñϳñáõÃÛ³Ý í»ÏïáñÝ»ñÇ Ñ³Ù³ñ ÃáõÛÉ ¿ ï³ÉÇë ѳßí³ñÏ»É üáõñÛ»Ç ¹ÇëÏñ»ï
Ó¨³÷áËáõÃÛ³Ý (ü²Ò) ѳٳñ ³ÝÑñ³Å»ßï ·áñÍáÕáõÃÛáõÝÝ»ñÇ ×ß·ñÇï ù³Ý³ÏÁ, áñï»Õ
q-Ý Ï»Ýï ÃÇí ¿:

Î ñëîæíîñòè àëãîðèòìîâ ÁÏÔ äëÿ äëèíû q £ 2 p

Ð. Áàðñåãÿí

Àííîòàöèÿ

 ýòîé ñòàòüå âûâåäåíà ëîãàðèôìè÷åñêàÿ ôîðìóëà, êîòîðàÿ ïîçâîëÿåò
âû÷èñëèòü òî÷íîå êîëè÷åñòâî íåîáõîäèìûõ îïåðàöèé äëÿ âû÷èñëåíèÿ äèñêðåòíîãî
ïðåîáðàçîâàíèÿ Ôóðüå (DFT) äëÿ âåêòîðîâ äëèíû q £ 2 p, ãäå q - íå÷åòíîå öåëîå
÷èñëî.