MATH_FFTReal

C Specification

#include <nitro/math/fft.h>

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

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 input real numbers.
sinTable Pointer to the table of sine values.
sinTable2 Pointer to the sine value table that omits every other value in sinTable.

Return Values

None.

Description

This takes a real number series as input and performs a discrete Fourier transform that outputs a complex number series using the fast Fourier transform algorithm.
This performs the same transform as the MATH_FFT function with the imaginary number parts filled with 0, but it uses only half the amount of memory and the calculation takes only around half as much time.

In the explanation below, the value 2nShift (2 to the nShift power) is represented as N. data is a type fx32 array of length N. These are the data in real numbers you want to transform.
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.
sinTable2 is the pointer to the array of length (N/2)*3/4, where fx16 type sine values are assigned that satisfy sinTable2[k] = sin( (2π/(N/2)) * k ) (k = 0, 1,..., (N/2)*3/4-1). This can be created by passing a value smaller by 1 to the nShift argument with the MATH_MakeFFTSinTable function.

The result of the discrete Fourier transform is a complex number series, but because a real number series is passed, only half the values are the independent numeric values. For this reason, this function extracts only the independent part, overwrites it as N/2+1 sets of complex number series (with the first and last imaginary components always 0) in data and then returns. The resulting size of the array that gets used is N, or the same as the input data. The return value is in a format that stores real and imaginary numbers alternately. However, the N/2th value (always a real number) gets stored in the imaginary part of the 0th value (always a real number) and returned. In other words, the transform result is N/2+1 sets of complex number sequence, expressed as {data[0], data[2]+i*data[3], ..., data[N-2]+i*data[N-1], data[1]}, where i is the unit for imaginary numbers. As for the latter half that was omitted because it was not independent, the values take the complex conjugate of the reverse order of the complex number series (from the first number to the N/2-1th number).

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).
Fm can be viewed as a coefficient of each frequency when the input signals are decomposed into a superposition of sine waves.
The fast Fourier transform is an algorithm that performs the discrete Fourier transform with the time complexity in the order of 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_FFT, MATH_IFFT, MATH_IFFTReal

Revision History

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