% FIGURE 5.3.1
      function F = DFFT(F,M)
%
%  FUNCTION DFFT PERFORMS A FAST FOURIER TRANSFORM ON THE COMPLEX
%     VECTOR F, OF LENGTH N=2^M.  THE FOURIER TRANSFORM IS DEFINED BY
%       Y(K) = SUM FROM J=1 TO N OF: EXP[I*2*PI*(K-1)*(J-1)/N]*F(J)
%     WHERE I = SQRT(-1).
%
%  ARGUMENTS
%
%             ON INPUT                          ON OUTPUT
%             --------                          ---------
%
%    F      - THE COMPLEX VECTOR OF LENGTH      THE TRANSFORMED VECTOR
%             2^M TO BE TRANSFORMED.            Y.
%
%    M      - THE LENGTH OF THE VECTOR F
%             IS ASSUMED TO BE 2^M.
%
%-----------------------------------------------------------------------
%                              FOURIER TRANSFORM OF A 1-VECTOR IS
%                              UNCHANGED
      if (M == 0)
         return
      end
      N = 2^M;
      H = cos(2*pi/N) + sin(2*pi/N)*i;
      N2 = N/2;
%                              COPY ODD COMPONENTS OF F TO FODD
%                              AND EVEN COMPONENTS TO FEVEN
      for K=1:N2
         FODD(K) = F(2*K-1);
         FEVEN(K)= F(2*K);
      end
%                              TRANSFORM N/2-VECTORS FODD AND FEVEN
      FODD  = DFFT(FODD ,M-1);
      FEVEN = DFFT(FEVEN,M-1);
      D = 1.0;
%                              Y = (FODD+D*FEVEN , FODD-D*FEVEN)
      for K=1:N2
         U = D*FEVEN(K);
         F(K)    = FODD(K) + U;
         F(N2+K) = FODD(K) - U;
         D = D*H;
      end
