<< Chapter < Page Chapter >> Page >

Basic radix-2 fft algorithm

Below is the Fortran code for a simple Decimation-in-Frequency, Radix-2, one butterfly Cooley-Tukey FFT followed by a bit-reversing unscrambler.

C C A COOLEY-TUKEY RADIX-2, DIF FFT PROGRAMC COMPLEX INPUT DATA IN ARRAYS X AND Y C C. S. BURRUS, RICE UNIVERSITY, SEPT 1983C--------------------------------------------------------- SUBROUTINE FFT (X,Y,N,M)REAL X(1), Y(1) C--------------MAIN FFT LOOPS-----------------------------C N2 = NDO 10 K = 1, M N1 = N2N2 = N2/2 E = 6.283185307179586/N1A = 0 DO 20 J = 1, N2C = COS (A) S = SIN (A)A = J*E DO 30 I = J, N, N1L = I + N2 XT = X(I) - X(L)X(I) = X(I) + X(L) YT = Y(I) - Y(L)Y(I) = Y(I) + Y(L) X(L) = C*XT + S*YTY(L) = C*YT - S*XT 30 CONTINUE20 CONTINUE 10 CONTINUEC C------------DIGIT REVERSE COUNTER-----------------100 J = 1 N1= N - 1 DO 104 I=1, N1IF (I.GE.J) GOXTO 101 XT = X(J)X(J) = X(I) X(I) = XTXT = Y(J) Y(J) = Y(I)Y(I) = XT 101 K = N/2102 IF (K.GE.J) GOTO 103 J = J - KK = K/2 GOTO 102103 J = J + K 104 CONTINUERETURN ENDFigure: Radix-2, DIF, One Butterfly Cooley-Tukey FFT

Basic dit radix-2 fft algorithm

Below is the Fortran code for a simple Decimation-in-Time, Radix-2, one butterfly Cooley-Tukey FFT preceeded by a bit-reversing scrambler.

C C A COOLEY-TUKEY RADIX-2, DIT FFT PROGRAMC COMPLEX INPUT DATA IN ARRAYS X AND Y C C. S. BURRUS, RICE UNIVERSITY, SEPT 1985C C---------------------------------------------------------SUBROUTINE FFT (X,Y,N,M) REAL X(1), Y(1)C------------DIGIT REVERSE COUNTER----------------- C100 J = 1 N1 = N - 1DO 104 I=1, N1 IF (I.GE.J) GOTO 101XT = X(J) X(J) = X(I)X(I) = XT XT = Y(J)Y(J) = Y(I) Y(I) = XT101 K = N/2 102 IF (K.GE.J) GOTO 103J = J - K K = K/2GOTO 102 103 J = J + K104 CONTINUE C--------------MAIN FFT LOOPS-----------------------------C N2 = 1DO 10 K = 1, M E = 6.283185307179586/(2*N2)A = 0 DO 20 J = 1, N2C = COS (A) S = SIN (A)A = J*E DO 30 I = J, N, 2*N2L = I + N2 XT = C*X(L) + S*Y(L)YT = C*Y(L) - S*X(L) X(L) = X(I) - XTX(I) = X(I) + XT Y(L) = Y(I) - YTY(I) = Y(I) + YT 30 CONTINUE20 CONTINUE N2 = N2+N210 CONTINUE CRETURN END

Dif radix-2 fft algorithm

Below is the Fortran code for a Decimation-in-Frequency, Radix-2, three butterfly Cooley-Tukey FFT followed by a bit-reversing unscrambler.

C A COOLEY-TUKEY RADIX 2, DIF FFT PROGRAM C THREE-BF, MULT BY 1 AND J ARE REMOVEDC COMPLEX INPUT DATA IN ARRAYS X AND Y C TABLE LOOK-UP OF W VALUESC C. S. BURRUS, RICE UNIVERSITY, SEPT 1983 C---------------------------------------------------------SUBROUTINE FFT (X,Y,N,M,WR,WI) REAL X(1), Y(1), WR(1), WI(1)C--------------MAIN FFT LOOPS----------------------------- CN2 = N DO 10 K = 1, MN1 = N2 N2 = N2/2JT = N2/2 + 1 DO 1 I = 1, N, N1L = I + N2 T = X(I) - X(L)X(I) = X(I) + X(L) X(L) = TT = Y(I) - Y(L) Y(I) = Y(I) + Y(L)Y(L) = T 1 CONTINUEIF (K.EQ.M) GOTO 10 IE = N/N1IA = 1 DO 20 J = 2, N2IA = IA + IE IF (J.EQ.JT) GOTO 50C = WR(IA) S = WI(IA)DO 30 I = J, N, N1 L = I + N2T = X(I) - X(L) X(I) = X(I) + X(L)TY = Y(I) - Y(L) Y(I) = Y(I) + Y(L)X(L) = C*T + S*TY Y(L) = C*TY - S*T30 CONTINUE GOTO 2550 DO 40 I = J, N, N1 L = I + N2T = X(I) - X(L) X(I) = X(I) + X(L)TY = Y(I) - Y(L) Y(I) = Y(I) + Y(L)X(L) = TY Y(L) =-T40 CONTINUE 25 A = J*E20 CONTINUE 10 CONTINUEC------------DIGIT REVERSE COUNTER Goes here---------- RETURNEND

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Fast fourier transforms. OpenStax CNX. Nov 18, 2012 Download for free at http://cnx.org/content/col10550/1.22
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Fast fourier transforms' conversation and receive update notifications?

Ask