# $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.6
# ----------------------------------------------------------------
# $


  FFT Coefficient tables format and generator
  ===========================================
  
  Overview
  ========
  
The FFT implementation requires tables of various formats. These tables store
twiddle (complex multiply) coefficients of the form:

  c(k) = cos(+2*k*pi*i/N)
  s(k) = sin(+2*k*pi*i/N)
  
where N is the size of the FFT.

The tables are generated by 'gentable.c' in this directory. This file should
usually be compiled natively (using for example cl.exe on PC or gcc on unix).
When executed it outputs a C table file to be included in the FFT project.


  Table naming and format for the twiddle table
  =============================================
  
The (symbolic) name of a coefficient twiddle table is of the form:

  t_<Format>_<R1>_<R2>_..._<Rk>
  
Where Format is one of:

  Q14R  - Q14 values stored in (cos, sin) form, 16-bits per real
  Q30R  - Q30 values stored in (cos, sin) form, 32-bits per real
  Q14S  - Q14 values stored in (cos-sin, sin) form, 16-bits per real
  Q30S  - Q30 values stored in (cos-sin, sin) form, 32-bits per real
  
And Rj is the radix used for the j'th FFT stage (only the early stages need
to be specified as will be clear from the following).

Also specified is an associate integer variable:

  s_<Format>_<R1>_<R2>_..._<Rk>
  
which reads as a size value S, which must be a multiple of R1*...*Rk.

The table then contains stages of radix R1, R2, R3, ..., Rk, R(k+1),...Rl
where R(k+1)...Rl are chosen automatically such that it is a decreasing
sequence of odd primes following by 4,4,4,4...,4 and optionally ,2 chosen so
that S=R1*...*Rk*...*Rl.

Only enough stages need to be specified so that the identfier is unique and
that the standard "automatic choice" algorithm can select the remaining
stages.

For example:

  if     *s_Q14S_4 = 1024
  then    t_Q14S_4 points to a table for stages of radix 4,4,4,4,4
  
  if     *s_Q14S_4 = 2048
  then    t_Q14S_4 points to a table for stages of radix 4,4,4,4,4,2
  
  if     *s_Q14S_8 = 2048
  then    t_Q14S_8 points to a table for stages of radix 8,4,4,4,4
  
  if     *s_Q14S_5 = 60
  then    t_Q14S_5 points to a table for stages of radix 5,3,4

  
The table then contains a list of complex (cos,sin) or (cos-sin, sin) values.
For a table supporting stages of radix R1,R2,...,Rk the table has format:

  For j=2...k
    t = exp(+2*pi*i/(R1*..*Rj))
    For l=0...(R1*R2*..*R(j-1))-1
      If Rj is prime
        Append (t, t^2, ..., t^(Rj-1)) to the table
      If Rj is composite use bit reversed order so for Rj=4:
        Append (t^2, t, t^3) to the table
    EndFor l
  EndFor j
  
On each l loop, (Rj-1) complex elements are added. So, on each j loop,
R1*R2*..*R(j-1)*(Rj-1) elements are added, which is:

  R1*R2*...*Rj - R1*R2*...*R(j-1)
  
Summing over j, the table has N-R1 complex elements (where N=R1*..*Rk).


  Table naming and format for complicated stages
  ==============================================
   
A radix R stage which is quite complicated (eg R=8,3,5) will require
coefficients for peforming the actual stages, in addition to the coefficients
for the pre-twiddle, as described in the table above.

These coefficients are stored in a table called:

  t_<Format>_rad<R>
  
If:

  w = exp(+2*pi*i/R)
  
then the contents of the table is:

  ( w, w^2, w^3, ... w^(R/2-1) )
  
Only these values are required since:

  w^0=1, w^(R/2)=-1, w^(R-j) = conjugate(w^j)


  File Names
  ==========
  
The twiddle tables with s_<Format>_<Stages> = N are stored in the file:

  t_<N>_<Stages>.c
   
The tables for storing the radix R coefficients are stored in the file:

  t_rad.c
