D:\sbornik\...\tpel.DVI


Mathematical Problems of Computer Science 33, 48{53, 2010.

E ±cient Computation of Subset of Output

P oints of FFT

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

Institute for Informatics and Automation Problems of NAS RA

Abstract

This paper presents e±cient pruning algorithms for computing the length q £ 2p
DFT for a subset of output points based on transform decomposition method and in
new results in computation of FFT.

Refer ences

[1 ] 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 .

[2 ] 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 .

[3 ] 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 ," P roc.
AF IP S F all J oint Computer Conf., p p . 1 1 5 1 2 5 , 1 9 6 8 .

[4 ] M. Fr ig o a n d S . G. Jo h n s o n ,\ A m o d ī 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 Trans. Signal P roccessing, - vo l. 5 5 , p p . 1 1 1 -1 1 9 , 2 2 0 7 .

[5 ] H . S a r u kh a n ya n , R . B a r s e g h ya n , \ N e w E ± c ie n t FFT wit h Fe we r Op e r a t io n s " , CS IT,
p p . 3 5 1 -3 5 4 , 2 0 0 9 .

[6 ] G. Go e r t z e l,\ A n A lg o r it h m fo r t h e e va lu a t io n o f ¯ n it e t r ig o n o m e t r ic s e r ie s " , Amer.
M ath. M onthly, p p . 3 4 -3 5 , 1 9 5 8 .

[7 ] C. G. B o n c e le t , \ A r e a r r a n g e d D FT a lg o r it h m r e qu ir in g N 2=6 m u lt ip lic a t io n s ," IE E E
Trans. Acoust., Speech, Signal P rocessing , p p . 1 6 5 8 -1 6 5 9 , 1 9 8 6 .

[8 ] R . d e W ild , \ Me t h o d fo r p a r t ia l s p e c t r u m c o m p u t a t io n ," P roc. Inst. E lec. E ng., p p .
6 5 9 -6 6 6 , 1 9 8 7 .

[9 ] J.D . Ma r ke l, \ FFT p r u n in g ," IE E E Trans. Audio E lectroacoust, p p . 3 0 5 -3 1 1 , 1 9 7 1 .

[1 0 ] H . V . S o r e n s e n , C. S . B u r r u s , a n d D . L . Jo n e s , \ A n e w e ± c ie n t a lg o r it h m fo r c o m p u t in g
a fe w D FT p o in t s ," P roc. IE E E Int., p p . 1 9 1 5 -1 9 1 8 , 1 9 8 8 .

[1 1 ] 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 1 -5 1 , 2 0 0 9 .

[1 2 ] H . S a r u kh a n ya n , R . B a r s e g h ya n ,\ N e w A p p r o a c h t o FFT a lg o r it h m s " , M athematical
P roblems of Computer Sciencevo l. 3 3 , p p . 2 4 { 3 4 , 2 0 1 0 .

[1 3 ] G. B i a n d Y . Q. Ch e n , " Fa s t D FT a lg o r it h m s fo r le n g t h ," IE E E Trans. Circuits and
Syst.- II: Analog and D igital Signal P rocessing, p p . 6 8 5 -6 9 0 , 1 9 9 8 .

4 8



R. Barseghyan 4 9

ü²Ò »Éù³ÛÇÝ áñáß³ÏÇ ïÇñáõÛÃÇ Ñ³ßíÙ³Ý ³ñ¹Ûáõݳí»ï ³É·áñÇÃÙ

è. ´³ñë»ÕÛ³Ý

²Ù÷á÷áõÙ

Ò¨³÷áËáõÃÛ³Ý ¹»ÏáÙåá½ÇódzÛÇ ÑÇÙ³Ý íñ³ ³ß˳ï³ÝùáõÙ Ùß³Ïí³Í ¿ ëå»Ïïñ³É
ïÇñáõÛÃÇ áñáß³ÏÇ Ñ³ïí³ÍÇ Ñ³ßíÙ³Ý ³ñ¹Ûáõݳí»ï ³É·áñÇÃÙ: