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 PROGRAM
C   COMPLEX INPUT DATA IN ARRAYS X AND Y
C      C. S. BURRUS, RICE UNIVERSITY, SEPT 1983
C---------------------------------------------------------
    SUBROUTINE FFT (X,Y,N,M)
    REAL X(1), Y(1)
C--------------MAIN FFT LOOPS-----------------------------
C
    N2 = N
    DO 10 K = 1, M
        N1 = N2
        N2 = N2/2
        E  = 6.283185307179586/N1
        A  = 0
        DO 20 J = 1, N2
        C = COS (A)
        S = SIN (A)
        A = J*E
        DO 30 I = J, N, N1
                    L = 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*YT
                    Y(L) = C*YT - S*XT
   30           CONTINUE
   20       CONTINUE
   10   CONTINUE
C
C------------DIGIT REVERSE COUNTER-----------------
  100   J = 1
    N1 = N - 1
    DO 104 I=1, N1
        IF (I.GE.J) GOXTO 101
        XT = X(J)
        X(J) = X(I)
        X(I) = XT
        XT   = Y(J)
        Y(J) = Y(I)
        Y(I) = XT
  101       K = N/2
  102       IF (K.GE.J) GOTO 103
        J = J - K
        K = K/2
        GOTO 102
  103       J = J + K
  104   CONTINUE
    RETURN
    END
 
Figure: Radix-2, DIF, One Butterfly Cooley-Tukey FFT