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