Name: FFTR2D.ASM
         Type: Assembler Macro
      Version: 1.0
  Last Change:  8-Aug-86

  Description: Radix 2, In-place, Decimation-in-time Complex FFT Macro

 This macro performs a complete Fast Fourier Transform (FFT) on complex
 data.  The basic algorithm is the Decimation-in-time (DIT), Radix 2
 FFT algorithm using 24 bit fixed-point arithmetic.  The algorithm uses
 a full-cycle sinewave lookup table for the FFT coefficients (twiddle
 factors).  The macro can be called to perform any FFT from 2-32768
 points.  Simply call it with the arguments of number of FFT points,
 location of the data array, the location of the sinewave table and the
 number of points in the sinewave table.  Note that the size of the
 sinewave table does not have to match the size of the FFT transform.
 For example, a 256 point complex FFTR2D macro requires a sinewave
 table of 256, 512, 768, 1024,.. points; that is, a multiple of 256
 points.  For real FFT's, a 256 point real FFTR2D macro requires a
 sinewave table of 128, 256, 384, 512,.. points; that is, one-half the
 size required for a complex FFT.  This allows different size FFT's to
 use a fixed size sinewave table, such as the DSP56001 Y Data ROM.

 All register initialization is performed by this macro.  However, the
 macro assumes that registers which should not be altered by the FFT
 have already been saved by the main program.  This allows the user to
 fit the FFT macro into his application and thus control the context
 switching overhead.  No data scaling is performed and no overflow
 detection is done.  Modifications to this routine could allow it to
 be used with the scaling modes and thus allow dynamic scaling for
 each FFT pass.

 All data is complex, with the real part in X Data memory and the
 imaginary part in Y Data memory.  For an N point FFT, the data buffer
 requires N X Data and N Y Data memory locations.  The algorithm is
 performed "in-place", meaning that only one data buffer is required
 for both input and output data.  The input data is assumed to be in
 normal (time-sequential) order and the output is in bit-reversed
 order.  By using the reverse-carry address modifier and a separate
 output data buffer, the output data may be easily unscrambled.  Other
 methods also exist to unscramble the output data without a separate
 output data buffer.  The FFTR2D macro uses "twiddle factors" (sine
 table) stored in Y Data memory.  For maximum speed, the FFT macro
 performs a lookup table operation to get new sine values for each
 group of butterflies.  A SINEWAVE macro is available to generate
 these tables.  For an N point FFT, N Y Data locations are required.
 Sine values could be calculated in real-time to save data memory at
 the expense of execution time.

 The FFTR2D macro requires about 40 words of program memory for any
 size FFT from 2-32768 points.  The main advantage of this FFT routine
 is its use of a full-cycle sinewave table for coefficients.  This
 sinewave table can often be shared with other functions in the system
 and is available in the DSP56001 Y Data ROM.  Using a 20.5 MHz
 DSP56001, the FFTR2D macro can perform a 256 point complex FFT in
 approximately 0.86 milliseconds.  Additional algorithm details are
 included in the source file; however, more algorithm description
 would be required for complete understanding by typical users.  The
 test program FFTR2DT demonstrates the calling procedure for this
 macro.