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