arithmetic/src/linearalgebra/fourier/FourierTransform.ig

GENERIC INTERFACE FourierTransform(C);
Arithmetic for Modula-3, see doc for details

Abstract: Fast Fourier Transforms (FFT's)

Much more sophisticated routines can be found in the Modula-3 interface to the FFTW library.

3/18/96 Warren Smith Initial version 

*************************************
Reorders array a[0..n-1] so that element[i] is
swapped with element[reverse-bit-order[i]].
Two successive calls are identity.
The algorithm below runs in O(n) time and is based on implementing a
reverse-binary counter. The forward counter f increments 0..n/2-1 step 2
and if r, 0<=r<n/2 is the bit-reverse of f,
we swap(f+1,n/2+r) with no test needed and we do
swap(f,r) if r>f and also swap(n-1-f,n-1-r) if f,r both <n/2.
**************************************************


PROCEDURE ReOrder (VAR a: ARRAY OF C.T; );

**************************************
 direction = +1 for inverse FFT, -1 for forward.  (See FFT defn
in module.)


 a[] overwritten by transform.
NOTE: You must call ReOrder(a) before calling this routine,
because this routine assumes it has re-ordered a[]s as its input.
To do an FFT of some data, therefore, we would call
  ReOrder(data); FFTwithWrongOrderedInput(data);
I have separated the routines this way because I want to be able to
avoid the ReOrder when computing convolutions and correlations.
***************************************

PROCEDURE FFTwithWrongOrderedInput
  (VAR a: ARRAY OF C.T; direction: [-1 .. 1]; );

PROCEDURE Test ();

 perform assertions

END FourierTransform.