home *** CD-ROM | disk | FTP | other *** search
/ CD Shareware Magazine 1996 December / CD_shareware_12-96.iso / DOS / Programa / NUMANA01.ZIP / DEF / FOURIER.DEF < prev    next >
Encoding:
Modula Definition  |  1996-07-31  |  3.2 KB  |  61 lines
  1. DEFINITION MODULE Fourier;
  2.  
  3.         (********************************************************)
  4.         (*                                                      *)
  5.         (*              Fast Fourier Transform                  *)
  6.         (*                                                      *)
  7.         (*  Programmer:         P. Moylan                       *)
  8.         (*  Last edited:        31 July 1996                    *)
  9.         (*  Status:             Working                         *)
  10.         (*                                                      *)
  11.         (********************************************************)
  12.  
  13. PROCEDURE FFT3 (Direct: BOOLEAN;  N: CARDINAL;
  14.                         VAR (*INOUT*) data: ARRAY OF LONGCOMPLEX);
  15.  
  16.     (* Fast Fourier transform of an array of N complex data points.     *)
  17.     (* The result is returned in the same array.  N must be a power of  *)
  18.     (* two.  This is essentially the Cooley-Tukey algorithm, modulo a   *)
  19.     (* few changes I've made for efficiency.                            *)
  20.     (* Specify Direct=FALSE for an inverse transform.                   *)
  21.  
  22. PROCEDURE FFT8 (Direct: BOOLEAN;  N: CARDINAL;
  23.                         VAR (*INOUT*) data: ARRAY OF LONGCOMPLEX);
  24.  
  25.     (* Alternative implementation, based on the Sande variant of        *)
  26.     (* the FFT.  From my tests it's not quite as accurate as the above. *)
  27.  
  28. PROCEDURE SlowFT (Direct: BOOLEAN;  N: CARDINAL;
  29.                                 VAR (*IN*) X: ARRAY OF LONGCOMPLEX;
  30.                                 VAR (*OUT*) A: ARRAY OF LONGCOMPLEX);
  31.  
  32.     (* For comparison: a Fourier transform by the slow method.  This is *)
  33.     (* both slower and less accurate than the FFT, so you wouldn't      *)
  34.     (* normally bother using it.  It's here simply because it provides  *)
  35.     (* a base against which I can compare my FFT implementations.       *)
  36.  
  37. PROCEDURE RealFFT (Direct: BOOLEAN;  N: CARDINAL;
  38.                                 VAR (*INOUT*) data: ARRAY OF LONGREAL);
  39.  
  40.     (* Fast Fourier transform of an array of N real data points.        *)
  41.     (* N must be a power of two.  The complex result is returned in the *)
  42.     (* same array, by storing each complex number in two successive     *)
  43.     (* elements of data (the real part first, then the imaginary part). *)
  44.     (* This means that we can return only (N DIV 2) answers, but this   *)
  45.     (* is usually acceptable: because of the symmetries for real input  *)
  46.     (* data, it suffices to confine our attention to the positive half  *)
  47.     (* of the frequency spectrum.                                       *)
  48.  
  49.     (* In fact we return (N DIV 2)+1 complex results, by storing the    *)
  50.     (* result for the highest frequency in data[1].  This works because *)
  51.     (* the values of the transform for zero frequency and this highest  *)
  52.     (* frequency are both real, i.e. we're overwriting an imaginary     *)
  53.     (* part which is known to be zero anyway.                           *)
  54.  
  55.     (* For the inverse transform (Direct=FALSE), the original complex   *)
  56.     (* data should be packed into the array as above, and the answer    *)
  57.     (* is a genuine real array.                                         *)
  58.  
  59. END Fourier.
  60.  
  61.