# MATH_FFT

## C Specification

      #include <nitro/math/fft.h>

      void MATH_FFT( fx32* data, u32 nShift, const fx16* sinTable );

## Arguments

data | Pointer to the data to transform. Data after the transform is overwritten.
nShift | The value obtained by taking the base-2 logarithm of the number of the input complex numbers.
sinTable | Pointer to the table of sine values.

## Return Values

None.

## Description

This takes a complex number series as input and performs discrete Fourier transform that outputs complex number series using the fast Fourier transform algorithm.

In the explanation below, the value 2nShift (2 to the nShift power) is represented as N. data is a type fx32 array of length 2*N. N number of complex numbers is passed to data in a format that stores real numbers and imaginary numbers alternately. Thus, if i is the unit for imaginary numbers, then the input data is the complex number sequence of N length `{data[0]+i*data[1], data[2]+i*data[3], ..., data[N*2-2]+i*data[N*2-1]}`. sinTable is the pointer to the array of N*3/4 length that has fx16 type sine values assigned that satisfy `sinTable[k] = sin( (2π/N) * k ) (k = 0, 1,..., N*3/4-1)`. This can be created using the `MATH_MakeFFTSinTable` function. The result of the discrete Fourier transform also becomes a complex number series, and is overwritten in data in the same format as the input and returned.

The discrete Fourier transform is a calculation for obtaining `Fm (m = 0, 1, ... N-1)` to satisfy the expression:
`fn = Σk = 0N-1 Fkei2πkn/N`,
where the sampling value in complex numbers taken along the time axis expressed as `fn (n = 0, 1, ... N-1)`. When the input signals are decomposed into a superposition of sine waves,`Fm` can be viewed as a coefficient of each frequency. The fast Fourier transform is an algorithm that performs the discrete Fourier transform with the order of time complexity `N*log(N)`.

The calculations are performed using fixed-decimal numbers, so if a large value is given as the input, there is a risk of overflow. When the input value is viewed as type s32, the absolute value should not be greater than or equal to `0x80000000/N`. Also note that the maximum error when performing both the forward transform and inverse transform is around several times `FX32_ONE`.

## See Also

`MATH_MakeFFTSinTable, MATH_IFFT, MATH_FFTReal, MATH_IFFTReal`

## Revision History

07/21/2005 Corrected the explanation for sinTable.
07/11/2005 Corrected the explanation.
05/13/2005 Initial version.