<< Chapter < Page | Chapter >> Page > |
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
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
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
Notification Switch
Would you like to follow the 'Fast fourier transforms' conversation and receive update notifications?