readme_fft_flp32_c.txt

ADSP-TS101S and ADSP-TS201S Real and Complex radix-2 C-callable FFT

*******************************************************************************

	ADSP-TS101S and ADSP-TS201S Real and Complex radix-2 C-callable FFT

This is a Real and Complex radix-2 C-callable FFT on TigerSHARC family of DSPs.

Analog Devices, Inc.
DSP Division
Three Technology Way
P.O. Box 9106
Norwood, MA 02062

October, 2003 - Prelim rev. - BL
February, 2004 - Rev. 1.0 - added real inputs case - PM


This directory contains a Complex radix-2 C-callable FFT example for ADSP-TS101S and ADSP-TS201S.

#defines have been added allowing the same source code to be used on both an ADSP-TS101S
or an ADSP-TS201S EZ-Kit.


Files contained in this directory:

Inputs Folder		contains the input points files: inputN.dat, N=32, 128,...,65536
Outputs Folder		contains the fft output files output_N.dat obtained from the DSP and
    			the files output_N_matlab.dat obtained by performing the fft in Matlab
Tcl_TS101 Folder	Tcl scripts used to build, execute and save the fft results
Tcl_TS201 Folder	Tcl scripts used to build, execute and save the fft results
Twiddles Folder		Ccontains the twiddle factor specific for each number of points N: twidN.dat
ADSP-TS101_C.ldf	Linker Description File for TS101
ADSP-TS201_C.ldf	Linker Description File for TS201
init.c			Init routine for the Complex radix-2 C-callable FFT
main.c			Main program to call fft_flp32.asm file
fft_flp32.asm		Complex radix-2 C-callable FFT
variables.asm		Twiddle factor table
fft_flp32_TS101.dpj	VisualDSP project file
fft_flp32_TS201.dpj	VisualDSP project file
FFT_REAL.m		Matlab program that produces input files to FFT
FFT_COMPLEX.m		Matlab program that produces input files to FFT
save_fp.m		Matlab utilities
defts201.h		Defines for the ADSP-TS201
FFTDef.h		Defines for the FFT routines
ini_cache.h		Contains the program that preloads the cache with the twiddless
cache_macros.h		TS201S macro file which includes macros to enable the cache
EE218v11.pdf		EE-218 application note
Readme_fft_flp32_C.txt	This README file

 _________________________________________________________________

CONTENTS

I.	Description of Calling.
II.	Description of the FFT algorithm.
III.	Description of the REAL FFT algorithm.
IV.	EE-218 application note.

	I. Description of Calling.

		1. Inputs:
			j4 -> input (ping-pong buffer 1)
			j5 -> ping-pong buffer 1
      		j6 -> ping-pong buffer 2
			j7 -> output
			j27+0x18 -> N = Number of points
			j27+0x19 -> REAL or COMPLEX

		2. C-Calling Example:
			fft32(&(input), &(ping_pong_buffer1), &(ping_pong_buffer2), &(output), N, COMPLEX);

		3. Limitations:
			a. All buffers must be aligned on memory boundary which is a multiple of 4.
			b. N must be between 32 and MAX_FFT_SIZE.
			c. If memory space savings are required and input does not have to be
			   preserved, ping_pong_buffer1 can be the same buffer as input.
			d. If memory space savings are required, output can be the same buffer
			   as ping_pong_buffer2 if the number of FFT stages is even (i.e. 
			   Log2(N) is even) or the same as ping_pong_buffer1 if the number of
			   FFT stages is odd (i.e. Log2(N) is odd).

		4. MAX_FFT_SIZE can be selected via #define. Larger values allow for more choices
		   of N, but its twiddles will occupy more memory.
    		5. This C - callable function can process up to 64K blocks of data on TS201 
        	   (16K blocks on TS101) because C environment itself necessitates memory. 
        	   Therefore, if more input points are necessary, assembly language development 
        	   may become a must. On TS201, a block of memory is 128K words long, so 
        	   maximum N is 128K real points or 64K complex points. TS101 contains 
        	   only 2 blocks of data memory of 64K words and 4 buffers must be
        	   accommodated. Therefore, maximum N is 32K real words or 16K complex words.

	
	II. Description of the FFT algorithm.

		1. The input data is treated as complex interleaved N-point.
		2. Due to re-ordering, no stage can be done in-place.
		3. The bit reversal and the first two stages are combined into
		   a single loop. This loop takes data from input and stores it
		   in the ping-pong buffer1.
		4. Each subsequent stage ping-pongs the data between the two ping-pong
		   buffers. The last stage uses FFT output buffer for its output.
		5. Although the FFT is designed to be called with any point size
		   N <= MAX_FFT_SIZE by subsampling the twiddle factors, for ADSP-TS20x
		   processors, the best cycle optimization is achieved when MAX_FFT_SIZE=N.
		   For ADSP-TS101 all choices of MAX_FFT_SIZE are equally optimal.
		   

	III. Description of the REAL FFT algorithm.

		1. The input data is treated as complex interleaved N/2-point. The N/2 point complex
		   FFT will be computed first. Thus, N is halved, now number of points = N/2.

		2. Details and source code of the N/2 point complex FFT are in II above.

		3. Real re-combine:
			Here the complex N/2-point FFT computed in the previous steps is recombined to
			produce the N-point real FFT. If G is the complex FFT and F is the real FFT,
			the formula for F is given by:

			F(n) = 0.5*(G(n)+conj(G(N/2-n))-0.5*i*exp(-2*pi*i*n/N)*(G(n)-conj(G(N/2-n)). 
			
			From this the following can be derived:

			conj(F(N/2-n)) = 0.5*(G(n)+conj(G(N/2-n))+0.5*i*exp(-2*pi*i*n/N)*(G(n)-conj(G(N/2-n)).

			Thus, this can be computed in (n,N/2-n) pairs, as follows (dropping factor of 2):

			G(n) ------------------------------->------------------------>--------> F(n)
                                            \ +/                     \ +/
                                             \/                       \/
                                             /\                       /\
                      conj                  / -\  exp(-2*pi*i*n)*i   / -\   conj
			G(N/2-n) -----> conj(G(N/2-n))------>------------------------>--------> F(N/2-n)

			This is very efficient on the TigerSHARC architecture due to the add/subtract
			instruction.

	
	IV. For all additional details regarding this algorithm and code, see EE-218
	    application note, available from the ADI web site.


Project options for ADSP-TS101S EZ-Kit: 
=======================================
Please refer to the VisualDSP++ release notes and the 
ADSP-TS101S anomaly listings for full details of the following switch usage, 
operation and silicon revision requirements

Assembler/Compiler switches to be used in the assembler and 
compiler property pages' Additional Options fields

'-default-branch-np'	Required for TS101S Rev 0.1 silicon. 
						Use in BOTH compiler AND Assembler property 
						page 'Additional Options' field.

"-align-branch-lines'	Required for TS101S Rev 0.1 and 0.2 silicon". 
						Although a specific example may not contain a 
						"jump(P)", to keep generality the switch is 
						required for all silicon versions. Use only 
						in Assembler property page 'Additional Options'
						field.


If any example code projects are built/rebuilt for the above mentioned 
silicon revisions, these switches must be used. The same holds true for 
user created code sets.