;********************************************************************************
; FILE NAME:  	readme.txt
; AUTHORS:    	Simon Lau and Nathan Baltz
; DESCRIPTION:	This is a readme file for rFFT.asm.  This document contains 
;               three sections: the first section describes in detail how the 
;               code runs; the second section gives an overview of the program 
;               and data usage; and the last section lists some benchmarks.
; DATE:       	Summer 1996
;********************************************************************************

DESCRIPTION:
============
	This code implements a 2N-point real FFT on the TMS320C54x processor.  It
uses a radix 2, in-place DIT algorithm.  Real input sequences ranging from 16 to
1024 points can be used by simply modifying N and LOGN appropriately.  Note that
the input data must be in Q0.15 format.  This code consists of four phases:

        In Phase One, the inputs are rearranged in a bit-reversed order.  That way
the final outputs will be in the correct, natural order.  Specifically, the
original 2N-point real sequence is temporarly stored into a contiguous section of
memory labeled INPUT and is interpreted as an N-point complex input d[n] (where
the even-indexed real inputs form the real part of d[n], and the odd-indexed real
inputs form the imaginary part).  We call this process "packing."  Next we simply
bit-reverse the order of this complex sequence and store it into another section
of memory labeled DATA.

	In Phase Two, an N-point complex FFT is performed.  Computation is done in 
place.  The twiddle factors (sine and cosine) used are in Q0.15 format and are 
stored in two separate tables, TWIDDLE1 and TWIDDLE2.  There are 512 values in 
each table representing angles ranging from 0 to (almost) 180 degrees.  By 
indexing through the twiddle tables in the proper fashion, the same twiddle 
tables are used for real FFTs of different sizes.  

	Phase Three separates the FFT output in order to compute four independent 
real sequences RP,RM,IP,IM, which are the even real part, odd real part, even 
imaginary part, and the odd imaginary part, respectively.  Since the DFT and 
hence the FFT is a linear transform, this separation can be done correctly.

	The fourth and final phase performs one more set of butterflies in order to
create the complex output which corresponds to the 2N-point complex FFT of the 
original 2N-point real input sequence.  

MEMORY USAGE:
=============
	The code takes 196 words of program space and (2*512+2N+3+16) = 2N+1043
words of data space.

EXECUTION TIME: 
===============
	# of real points = 2N  :	16	32	64	128	256	512	1024
	Cycles		     :	377	769	1603	3393	7239	15485	33107