# $Copyright: 
# ----------------------------------------------------------------
# This confidential and proprietary software may be used only as
# authorised by a licensing agreement from ARM Limited
#   (C) COPYRIGHT 2000,2002 ARM Limited
#       ALL RIGHTS RESERVED
# The entire notice above must be reproduced on all authorised
# copies and copies may only be made to the extent permitted
# by a licensing agreement from ARM Limited.
# ----------------------------------------------------------------
# File:     readme.txt,v
# Revision: 1.2
# ----------------------------------------------------------------
# $


Optimized FFT for ARM Architecture v4 & v5TE
============================================

This integer FFT code has the following features:
  - Radix 4 general stage for best performance on ARM architecture
  - 32-bit and 16-bit precision data support
  - Complex or real-only FFT

The assembler code can be built to target:
  - ARM v4 architecture (ARM7TDMI, ARM9TDMI, StrongARM)
  - ARM v5TE architecture (ARM9E, ARM10E, XScale) and later

The v5TE version takes advantage of the new multiply-accumulate instructions in the ARM v5TE architecture, which significantly reduces the number of cycles required.


File structure
==============

  fft_asm       Assembler source code for the FFT

  tables        Cos/sin coefficient tables required for the FFT

  test          Test data

  build.mk      Makefile
  build.bat     Batch file of above Makefile


Building
========

  nmake -f build.mk

(a batch file is also supplied)

This builds two versions of the FFT application:
  fft_v4.axf
  fft_v5TE.axf

The object files are the same for both versions, except for the FFT code itself:
  fft_main_v4.o
  fft_main_v5TE.o    (uses "armasm --cpu arm9e" option)

The asm code in fft_main.s is able to determine the target architecture using the armasm variable {ARCHITECTURE}, and generates the appropriate optimized version.


FFT size
========

The example supplied will calculate FFTs for a power of 2 from N=8 up to a size of N=4096.  The size is limited to N=4096 due to the supplied coefficient tables, but these can easily be regenerated to suit larger N.


Generating new coefficient tables
=================================

For a real application, appropriately sized cos/sin tables should be created using the "gentables.c" program supplied, in order to minimize the memory used.

There are two different types of coefficient table, and only one set is required, depending on the CPU architecture selected at assemble time:

  v5TE          Uses "R" variant (cos, sin) tables

  v4            Uses "S" variant (cos-sin, sin) tables

The linker will automatically eliminate the unwanted set of tables.


Using the FFT in your own application
=====================================

The FFT code is a generated by a macro called GENERATE_FFT in fft_main.h. This macro generates an FFT according to a flags bitmap parameter. See the end of
fft_mac.h for details of the bitmap options.

To use the FFT, your armasm source code should include the FFT macro, and then call it:

  INCLUDE fft_main.h

  GENERATE_FFT  <specify flags here>

An example of how to use the FFT is in the file arm_fft/fft_main.s


Choosing Radix

This code implements a Radix 4 general stage which is ideal for the ARM architecture.  The FFT_RADIX4 version is suitable for N=power of 4, e.g. 4,16,64,256, etc.  There is the option of a Radix 8 first stage (FFT_RADIX4_8F) which will permit the other N=8,32,128,512, etc.


Real FFT

The FFT_REAL option will perform a real-only FFT (using a complex FFT of half the number of points).  In this case N must specify the size of the complex FFT, for example for an 8192 point real FFT, use N=4096

This option adds post processing code which converts the complex output from the FFT into the correct real-only results.


Input Scaling

The PRESCALE input scaling option shifts the input values left by the amount specified in
register r3 before performing the FFT.


Output scaling

There is the choice of no scaling of the output (in which case there is the possibility of overflow), or "normalise" which avoids the possibility of overflow.  The NORMALISE output
scaling option divides the result by N where N is the number of points in the FFT. It does
this by shifting down by 2 bits in each radix 4 stage.



Tests
=====

Testing uses standard mathematical input functions such as sinewave, for which the correct FFT output can be mathematically calculated.  The FFT is executed and the output is compared with the mathematically generated answer.

The test data and correct output are generated using a program to generate the data as source files which are then incorporated into the fft.axf image.

Test data is supplied for different sized N.  Use the supplied "gentests.c" to generate test data for other N.
