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. Overwritten by the transformed data.</TD>
30    </TR>
31    <TR>
32<TD width="176"><em><strong><font face="Courier New">nShift</font></strong></em></TD>
33<TD width="670">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>
44Takes 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 <SPAN class="argument">nShift</SPAN> power) is represented as N. The <SPAN class="argument">data</SPAN> argument is a <CODE>fx32</CODE>-type array of length <CODE>2*N</CODE>. An N-order complex number series is passed to <SPAN class="argument">data</SPAN> 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 <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>, where <i>i</i> represents an imaginary number. The <SPAN class="argument">sinTable</SPAN> argument is a pointer to the array of length <CODE>N*3/4</CODE>, filled with <CODE>fx16</CODE>-type sine values satisfying <CODE>sinTable[k] = <i>sin</i>( (2&#x3C0;/N) * k )  (k = 0, 1,..., N*3/4-1)</CODE>. This can be created using the <A href="MATH_MakeFFTSinTable.html"><CODE>MATH_MakeFFTSinTable</CODE></A> function.<BR><BR>The result of the discrete Fourier transform is also a complex number series, which is written to <SPAN class="argument">data</SPAN> in the same format as the input and returned.
48</P>
49<P>
50The discrete Fourier transform is a calculation for getting <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> = &#931;<sub>k = 0</sub><sup>N-1</sup> <i>F</i><sub>k</sub><i>e</i><sup>-<i>i</i>2&#960;kn/N</sup></CODE><BR> where the sampling value in complex numbers taken along the time axis is expressed as <CODE><i>f</i><sub>n</sub> (n = 0, 1, ... N-1)</CODE>.<BR>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 a time complexity of order <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><A href="MATH_MakeFFTSinTable.html"><CODE>MATH_MakeFFTSinTable</CODE></A><BR> <A href="MATH_IFFT.html"><CODE>MATH_IFFT</CODE></A><BR> <A href="MATH_FFTReal.html"><CODE>MATH_FFTReal</CODE></A><BR> <A href="MATH_IFFTReal.html"><CODE>MATH_IFFTReal</CODE></A></P>
57<H2>Revision History</H2>
58<P>
592009/03/23 Corrected mistakes in formula.<BR> 2005/07/21 Corrected explanation of <SPAN class="argument">sinTable</SPAN>.<BR> 2005/07/11 Corrected <B>Description</B>.<BR> 2005/05/13 Initial version.
60</P>
61<hr><p>CONFIDENTIAL</p></body>
62</html>
63