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_FFTReal</title> 9<LINK rel="stylesheet" href="../../css/nitro.css" type="text/css"> 10</head> 11 12<body> 13 14<h1 align="left">MATH_FFTReal <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 <nitro/math/fft.h> 20 21void MATH_FFTReal( fx32* data, u32 nShift, const fx16* sinTable, const fx16* sinTable2 ); 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">The value obtained by taking the base-2 logarithm of the number of input real 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 <TR> 40<TD width="176"><em><strong><font face="Courier New">sinTable2</font></strong></em></TD> 41<TD width="670">Pointer to a sine value table that omits every other value in <SPAN class="argument">sinTable</SPAN>.</TD> 42 </TR> 43 </table> 44<h2>Return Values</h2> 45<p>None.</p> 46<H2>Description</H2> 47<P> 48Takes a real number series as input and performs a discrete Fourier transform that outputs a complex number series using the fast Fourier transform algorithm.<BR>This performs the same transform as the <A href="MATH_FFT.html"><CODE>MATH_FFT</CODE></A> 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.<BR> 49</P> 50<P> 51In 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 type <CODE>fx32</CODE> array of length N. This is the data in real numbers you want to transform.<BR>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π/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 <SPAN class="argument">sinTable2</SPAN> argument is a pointer to an array of length <CODE>(N/2)*3/4</CODE>, filled with <CODE>fx16</CODE>-type sine values that satisfy <CODE>sinTable2[k] = <i>sin</i>( (2π/(N/2)) * k ) (k = 0, 1,..., (N/2)*3/4-1)</CODE>. This can be created by passing a value decremented by 1 to the <SPAN class="argument">nShift</SPAN> argument in the <A href="MATH_MakeFFTSinTable.html"><CODE>MATH_MakeFFTSinTable</CODE></A> function. 52</P> 53<P> 54The 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 parts, overwrites them as an <CODE>N/2+1</CODE>-order complex number series (with the first and last imaginary components always 0) in <SPAN class="argument">data</SPAN> 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 an <CODE>N/2+1</CODE>-order complex number series, expressed as <CODE>{data[0], data[2]+<i>i</i>*data[3], ..., data[N-2]+<i>i</i>*data[N-1], data[1]}</CODE>, where <i>i</i> represents an imaginary number. 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-1)th number).<BR> 55</P> 56<P> 57The 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> = Σ<sub>k = 0</sub><sup>N-1</sup> <i>F</i><sub>k</sub><i>e</i><sup>-<i>i</i>2π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>. 58</P> 59<P> 60The 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>. 61</P> 62<h2>See Also</h2> 63<P><A href="MATH_MakeFFTSinTable.html"><CODE>MATH_MakeFFTSinTable</CODE></A><BR> <A href="MATH_FFT.html"><CODE>MATH_FFT</CODE></A><BR> <A href="MATH_IFFT.html"><CODE>MATH_IFFT</CODE></A><BR> <A href="MATH_IFFTReal.html"><CODE>MATH_IFFTReal</CODE></A></P> 64<H2>Revision History</H2> 65<P> 662009/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. 67</P> 68<hr><p>CONFIDENTIAL</p></body> 69</html> 70
