# MATH_FFT

## Syntax

      #include <nitro/math/fft.h>

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

## Arguments

data | Pointer to the data to transform. Overwritten by the transformed data.
nShift | 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

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. The data argument is a `fx32`-type array of length `2*N`. An N-order complex number series is passed to data in a format that stores real numbers and imaginary numbers alternately. In other words, the input data is a complex number series of length N, expressed as `{data[0]+i*data[1], data[2]+i*data[3], ..., data[N*2-2]+i*data[N*2-1]}`, where i represents an imaginary number. The sinTable argument is a pointer to the array of length `N*3/4`, filled with `fx16`-type sine values satisfying `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 is also a complex number series, which is written to data in the same format as the input and returned.

The discrete Fourier transform is a calculation for getting `Fm (m = 0, 1, ... N-1)` to satisfy the expression
`fn = Σk = 0N-1 Fke-i2πkn/N`
where the sampling value in complex numbers taken along the time axis is 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 a time complexity of order `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

2009/03/23 Corrected mistakes in formula.
2005/07/21 Corrected explanation of sinTable.
2005/07/11 Corrected Description.
2005/05/13 Initial version.

CONFIDENTIAL