read_me.txt

快速FFT,汇编原程序

File Name:     fft1drad2cmpx_121900.zip

File Contents: read_me.txt
               cr2fftnasm_outplace.asm
               fft.dxe
               fftrad2.bat
               mds_def.h
               stall_19dec.txt
               tcr2fftn.c
               tcr2fftn.h

Module Name:   one-dimensional radix-2 forward FFT for complex data (Out of place).

Label name:    __cfftN

Description:   This file contains the code for the implementation of FFT. The Algorithm 
               used is Decimation in Time. For the optimization point of view, the whole
               computation of butterfly signal flow has beeen divided in three parts. The
               first part, the middle part and the last part. In the first part, the 
               Stage 1 and Stage 2 of the butterfly structure are implemented. In the 2nd
               part the general butterfly computation is done, which corresponds to the 
               middle stages of butterfly. In the last part the last stage of the buttrfly
               structure is implemented, where mainly the loop overheads are saved.

               Input and output both the data are complex and 16 bit and represented in 1.15 
               format. The loop unroling is also done for optimization point of view. 
				
               The C callable prototype of the function is as follows:

                  void cfftN(complex_fract16  *in,  complex_fract16 *out, complex_fract16 *w, 
                             int wst, int n);
		  
                  *in  -> Pointer to Input array.  
                  *out -> Pointer to Output array.
                  *w   -> Pointer to Twiddle factor. 
                  wst  -> Twiddle factor Stride. It is equal to 512/(size of input).
                  n    -> length of Input data.

               The C equivalent code for the main loop of each butterfly is 
               as follows.

                  for(i=0; i<le; i++)
                  {   
                     xire = out[add].re >> 1;
                     xiim = out[add].im >> 1;
                     xipre = out[add+indx].re >> 1;
                     xipim = out[add+indx].im >> 1;

                     mult.re = ((xipre * wptr[indx_w].re - xipim * wptr[indx_w].im) >>15);
                     mult.im = ((xipre * wptr[indx_w].im + xipim * wptr[indx_w].re) >>15);
				
                     out[add].re = xire + mult.re; 
                     out[add].im = xiim + mult.im;
                     out[add+indx].re = xire - mult.re;
                     out[add+indx].im = xiim - mult.im;
                     add = add + 2*offset;
                  }

               The ouput is  provided in normal order.
 
Restrictions:  The length of input array should be more than 4.i.e, 8, 16, 32
               and it should be power of 2.

Registers Used: 
               R0 -> It is mainly used for counter for middle stages. Its value is equal to m-3.
                     if m are the total number of stages for a perticular n.
               R1 -> It is used for the storing the value of wst. wst = 512/n.
               R2 -> Used for storing Input/Output data.
               R3 -> used for storing the twiddle factor value.
               R4 -> Used for storing Input/Output data.
               R5 -> Used for storing Input/Output data.
               R6 -> Used for storing Input/Output data.
               R7 -> Used for calculating and storing the address offset for twiddle factor 
                     array.
               P0 -> It is used for storing the address offset of output buffer in middle part
                     of implementation.
               P1 -> It is used for storing the address offset of output buffer in middle part
                     of implementation.
               P2 -> It is used for storing the address offset of output buffer in middle part
                     of implementation.
               P3 -> It stores the number of lines for the butterflies at a perticular stage.
               P4 -> It stores the value of input array length.
               P5 -> It stores the number of butterflies at a perticular stage.
               A0 -> Used for storing the value of MAC temporarily.
               A1 -> Used for storing the value of MAC temporarily.
               B0 -> Start address of Input array.
               B2 -> start address of output array.
               B3 -> Start address of twiddle factor buffer.
               I0 -> Address for input array.
               I1 -> Address for output and temporary array while computing.
               I2 -> Address for output array while computing.
               I3 -> Address for twiddle factor array.
               M0 -> Address offset for input/output array.
               M1 -> Address offset for output array.
               M2 -> Address offset for output array.
               M3 -> Address offset for twiddle factor.
               LC0 -> Counter.
               LC1 -> Counter.

Cycle Count:
               N = 256.
               The cycle count for 256 point fft calculation is 3176 cycles.
               The Cycle count for Stage1 + Stage2 + Bitreverse computation  =  389
               The Cycle count for middle stage computation                  = 2291
               The Cycle count for last stage computation                    =  397
               The Cycle count for prologue, epilogue... etc                 =   99
               ----------------------------------------------------------------------
                                                               TOTAL         = 3176
	
Code Size:     484 Bytes.