

D:\sbornik\...\Rafayel.DVI


Mathematical Problems of Computer Science 33, 24{34, 2010.

N ew Appr oach to FFT Algor ithms

R a fa ye l B a r s e g h ya n a n d H a ko b S a r u kh a n ya n

Institute for Informatics and Automation Problems of NAS RA

Abstract

In this paper we present a new, e±cient modi¯cation of split-radix algorithm for
computing a power of two discrete Fourier transforms. The developed algorithm allows
to 40% real arithmetic operations reduction in comparison with previous best results
for 16-point discrete Fourier transform.

Refer ences

[1 ] R . B la h u t , Fa s t A lg o r it h m s fo r D ig it a l S ig n a l P r o c e s s in g . A d d is o n -W e s le y, 1 9 8 5 .
[2 ] P . D u h a m e l a n d M. V e t t e r li, Fa s t Fo u r ie r t r a n s fo r m s : a t u t o r ia l r e vie w a n d a s t a t e o f

t h e a r t , S ig n a l P r o c e s s in g - A p r ., vo l. 1 9 , p p . 2 5 9 2 9 9 , 1 9 9 0 .
[3 ] 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 " ,ÄIE E E Tr a n s . S ig n a l P r o c c e s s in g , vo l. 5 5 , p p . 1 1 1 -1 1 9 , 2 0 0 7 .
[4 ] H . S a r u kh a n ya n , S . A g a ia n , \ Co n ve n t io n a l, In t e g e r t o In t e g e r a n d Qu a n t iz e d Fa s t

Fo u r ie r Tr a n s fo r m s " , CS IT, p p . 2 0 4 -2 0 7 , 2 0 0 7 .
[5 ] I. G. P e t r o vs ki, L e c t u r e s o n t h e t h e o r y o f o r d in a r y d i®e r e n t ia l e qu a t io n s , ( in r u s s ia n ) ,

1 9 8 4 .
[6 ] M. V e t t e r li, H . J. N u s s b a u m e r , \ S im p le FFT a n d D CT a lg o r it h m s wit h r e d u c e d n u m b e r

o f o p e r a t io n s " , Signal P rocessing , vo l. 6 , N r . 4 , p p . 2 6 7 -2 7 8 , 1 9 8 4 .
[7 ] R .B a r s e g h ya n , \ FFT wit h lift in g t r a n s fo r m s " , 3-th annual conference, R AU , ( s u b m it -

t e d ) , 2 0 0 9 .
[8 ] R .B a r s e g h ya n , \ S p lit -r a d ix FFT a lg o r it h m wit h lift in g s t e p s " , Vestnik R AU, Series:

P hysics-mathematics and natural science, p p . 4 2 -5 0 , 2 0 0 9 .

Üáñ Ùáï»óáõÙ ü²Ò ³É·áñÇÃÙÝ»ñÇ

è. ´³ñë»ÕÛ³Ý ¨ Ð. ê³ñáõË³ÝÛ³Ý

²Ù÷á÷áõÙ

²ßË³ï³ÝùáõÙ Ùß³Ïí³Í ¿ Ïïñïí³Í ÑÇÙùáí üáõñÛ»Ç ³ñ³· Ó¨³÷áËáõÃÛ³Ý
Ýáñ, ³ñ¹ÛáõÝ³í»ï Ó¨³÷áËí³Í ³É·áñÇÃÙÁ: Ó¨³÷áËí³Í ³É·áñÇÃÙÇ ÑÇÙ³Ý íñ³
ûåïÇÙ³É³óí»É ¿ 16-ã³÷³ÝÇ í»ÏïáñÇ Ó¨³÷áËáõÃÛáõÝÁ, áñÇ Ñ»ï¨³Ýùáí å³Ñ³ÝçíáÕ
Çñ³Ï³Ý Ãí³µ³Ý³Ï³Ý ·áñÍáÕáõÃÛáõÝÝ»ñÇ ù³Ý³ÏÁ Ýí³½»É ¿ 40% -áí:

2 4