1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
2<html>
3
4<head>
5<META http-equiv="Content-Type" content="text/html; charset=windows-1252">
6<META name="GENERATOR" content="IBM WebSphere Studio Homepage Builder Version 8.0.0.0 for Windows">
7<META http-equiv="Content-Style-Type" content="text/css">
8<title>MATH_FFT</title>
9<LINK rel="stylesheet" href="../../css/nitro.css" type="text/css">
10</head>
11
12<body>
13
14<h1 align="left">MATH_FFT <img src="../../image/NTR.gif"align="middle"><img src="../../image/TWL.gif" align="middle"></H1>
15<H2>Syntax</H2>
16
17<dl>
18  <dd>
19  <PRE><CODE>#include &lt;nitro/math/fft.h&gt;
20
21void MATH_FFT( fx32* data, u32 nShift, const fx16* sinTable );
22</CODE></PRE>
23  </dd>
24</dl><h2>Arguments</h2>
25
26<table border="1" width="100%">
27    <TR>
28      <TD width="176"><em><strong><font face="Courier New">data</font></strong></em></TD>
29      <TD width="670">Pointer to the data to transform. Data after the transform is overwritten.</TD>
30    </TR>
31    <TR>
32      <TD width="176"><em><strong><font face="Courier New">nShift</font></strong></em></TD>
33      <TD width="670">The value obtained by taking the base-2 logarithm of the number of the input complex numbers.</TD>
34    </TR>
35    <TR>
36      <TD width="176"><em><strong><font face="Courier New">sinTable</font></strong></em></TD>
37      <TD width="670">Pointer to the table of sine values.</TD>
38    </TR>
39  </table>
40<h2>Return Values</h2>
41<p>None.</p>
42<H2>Description</H2>
43<P>
44This takes a complex number series as input and performs discrete Fourier transform that outputs complex number series using the fast Fourier transform algorithm.
45</P>
46<P>
47In the explanation below, the value 2<sup>nShift</sup> (2 to the nShift power) is represented as N. <I>data</I> 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>i</i> is the unit for imaginary numbers, then the input data is the complex number sequence of N length <CODE>{data[0]+<i>i</i>*data[1], data[2]+<i>i</i>*data[3], ..., data[N*2-2]+<i>i</i>*data[N*2-1]}</CODE>. <I>sinTable</I> is the pointer to the array of N*3/4 length that has fx16 type sine values assigned that satisfy <CODE>sinTable[k] = <i>sin</i>( (2&#x3C0;/N) * k )  (k = 0, 1,..., N*3/4-1)</CODE>. This can be created using the <CODE><A href="MATH_MakeFFTSinTable.html">MATH_MakeFFTSinTable</A></CODE> function. The result of the discrete Fourier transform also becomes a complex number series, and is overwritten in <I>data</I> in the same format as the input and returned.
48</P>
49<P>
50The discrete Fourier transform is a calculation for obtaining <CODE><i>F</i><sub>m</sub> (m = 0, 1, ... N-1)</CODE> to satisfy the expression: <BR><CODE><i>f</i><sub>n</sub> = &#x3A3;<sub>k = 0</sub><sup>N-1</sup> <i>F</i><sub>k</sub><i>e</i><sup><i>i</i>2&#x3C0;kn/N</sup></CODE>, <BR>where the sampling value in complex numbers taken along the time axis expressed as <CODE><i>f</i><sub>n</sub> (n = 0, 1, ... N-1)</CODE>. When the input signals are decomposed into a superposition of sine waves,<CODE><i>F</i><sub>m</sub></CODE> 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 <CODE>N*log(N)</CODE>.
51</P>
52<P>
53The 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 <CODE>0x80000000/N</CODE>. Also note that the maximum error when performing both the forward transform and inverse transform is around several times <CODE>FX32_ONE</CODE>.
54</P>
55<h2>See Also</h2>
56<P><CODE><A href="MATH_MakeFFTSinTable.html">MATH_MakeFFTSinTable</A>, <A href="MATH_IFFT.html">MATH_IFFT</A>, <A href="MATH_FFTReal.html">MATH_FFTReal</A>, <A href="MATH_IFFTReal.html">MATH_IFFTReal</A></CODE></P>
57<H2>Revision History</H2>
58<P>
592005/07/21 Corrected the explanation for <CODE>sinTable</CODE>.<BR>2005/07/11 Corrected the explanation.<BR> 2005/05/13 Initial version.
60</P>
61<hr><p>CONFIDENTIAL</p></body>
62</html>
63