blob: 755d463867d3b8ab64c4c9d0a197dd34bbc68c7c [file] [log] [blame]
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<title>Real FFT Functions</title>
<title>CMSIS-DSP: Real FFT Functions</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="cmsis.css" rel="stylesheet" type="text/css" />
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<script type="text/javascript" src="printComponentTabs.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
$(document).ready(initResizable);
</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
$(document).ready(function() { searchBox.OnSelectItem(0); });
</script>
<link href="stylsheetf" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 46px;">
<td id="projectlogo"><img alt="Logo" src="CMSIS_Logo_Final.png"/></td>
<td style="padding-left: 0.5em;">
<div id="projectname">CMSIS-DSP
&#160;<span id="projectnumber">Version 1.4.7</span>
</div>
<div id="projectbrief">CMSIS DSP Software Library</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<div id="CMSISnav" class="tabs1">
<ul class="tablist">
<script type="text/javascript">
<!--
writeComponentTabs.call(this);
//-->
</script>
</ul>
</div>
<!-- Generated by Doxygen 1.8.2 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main&#160;Page</span></a></li>
<li><a href="pages.html"><span>Usage&#160;and&#160;Description</span></a></li>
<li><a href="modules.html"><span>Reference</span></a></li>
<li>
<div id="MSearchBox" class="MSearchBoxInactive">
<span class="left">
<img id="MSearchSelect" src="search/mag_sel.png"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
alt=""/>
<input type="text" id="MSearchField" value="Search" accesskey="S"
onfocus="searchBox.OnSearchFieldFocus(true)"
onblur="searchBox.OnSearchFieldFocus(false)"
onkeyup="searchBox.OnSearchFieldChange(event)"/>
</span><span class="right">
<a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
</span>
</div>
</li>
</ul>
</div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
<div id="nav-tree">
<div id="nav-tree-contents">
<div id="nav-sync" class="sync"></div>
</div>
</div>
<div id="splitbar" style="-moz-user-select:none;"
class="ui-resizable-handle">
</div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('group___fast.html','');});
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Data Structures</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&#160;</span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark">&#160;</span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark">&#160;</span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(8)"><span class="SelectionMark">&#160;</span>Macros</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(9)"><span class="SelectionMark">&#160;</span>Groups</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(10)"><span class="SelectionMark">&#160;</span>Pages</a></div>
<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0"
name="MSearchResults" id="MSearchResults">
</iframe>
</div>
<div class="header">
<div class="headertitle">
<div class="title">Real FFT Functions</div> </div>
<div class="ingroups"><a class="el" href="group__group_transforms.html">Transform Functions</a></div></div><!--header-->
<div class="contents">
<dl class="section user"><dt></dt><dd>The CMSIS DSP library includes specialized algorithms for computing the FFT of real data sequences. The FFT is defined over complex data but in many applications the input is real. Real FFT algorithms take advantage of the symmetry properties of the FFT and have a speed advantage over complex algorithms of the same length. </dd></dl>
<dl class="section user"><dt></dt><dd>The Fast RFFT algorith relays on the mixed radix CFFT that save processor usage. </dd></dl>
<dl class="section user"><dt></dt><dd>The real length N forward FFT of a sequence is computed using the steps shown below. </dd></dl>
<dl class="section user"><dt></dt><dd><div class="image">
<img src="RFFT.gif" alt="RFFT.gif"/>
<div class="caption">
Real Fast Fourier Transform</div></div>
</dd></dl>
<dl class="section user"><dt></dt><dd>The real sequence is initially treated as if it were complex to perform a CFFT. Later, a processing stage reshapes the data to obtain half of the frequency spectrum in complex format. Except the first complex number that contains the two real numbers X[0] and X[N/2] all the data is complex. In other words, the first complex sample contains two real values packed. </dd></dl>
<dl class="section user"><dt></dt><dd>The input for the inverse RFFT should keep the same format as the output of the forward RFFT. A first processing stage pre-process the data to later perform an inverse CFFT. </dd></dl>
<dl class="section user"><dt></dt><dd><div class="image">
<img src="RIFFT.gif" alt="RIFFT.gif"/>
<div class="caption">
Real Inverse Fast Fourier Transform</div></div>
</dd></dl>
<dl class="section user"><dt></dt><dd>The algorithms for floating-point, Q15, and Q31 data are slightly different and we describe each algorithm in turn. </dd></dl>
<dl class="section user"><dt>Floating-point</dt><dd>The main functions are <code><a class="el" href="group___real_f_f_t.html#ga180d8b764d59cbb85d37a2d5f7cd9799" title="Processing function for the floating-point real FFT.">arm_rfft_fast_f32()</a></code> and <code><a class="el" href="group___real_f_f_t.html#gac5fceb172551e7c11eb4d0e17ef15aa3" title="Initialization function for the floating-point real FFT.">arm_rfft_fast_init_f32()</a></code>. The older functions <code><a class="el" href="group___real_f_f_t.html#ga3df1766d230532bc068fc4ed69d0fcdc" title="Processing function for the floating-point RFFT/RIFFT.">arm_rfft_f32()</a></code> and <code><a class="el" href="group___real_f_f_t.html#ga10717ee326bf50832ef1c25b85a23068" title="Initialization function for the floating-point RFFT/RIFFT.">arm_rfft_init_f32()</a></code> have been deprecated but are still documented. </dd></dl>
<dl class="section user"><dt></dt><dd>The FFT of a real N-point sequence has even symmetry in the frequency domain. The second half of the data equals the conjugate of the first half flipped in frequency: <pre>
*X[0] - real data
*X[1] - complex data
*X[2] - complex data
...
*X[fftLen/2-1] - complex data
*X[fftLen/2] - real data
*X[fftLen/2+1] - conjugate of X[fftLen/2-1]
*X[fftLen/2+2] - conjugate of X[fftLen/2-2]
...
*X[fftLen-1] - conjugate of X[1]
</pre> Looking at the data, we see that we can uniquely represent the FFT using only <pre>
*N/2+1 samples:
*X[0] - real data
*X[1] - complex data
*X[2] - complex data
...
*X[fftLen/2-1] - complex data
*X[fftLen/2] - real data
</pre> Looking more closely we see that the first and last samples are real valued. They can be packed together and we can thus represent the FFT of an N-point real sequence by N/2 complex values: <pre>
*X[0],X[N/2] - packed real data: X[0] + jX[N/2]
*X[1] - complex data
*X[2] - complex data
...
*X[fftLen/2-1] - complex data
</pre> The real FFT functions pack the frequency domain data in this fashion. The forward transform outputs the data in this form and the inverse transform expects input data in this form. The function always performs the needed bitreversal so that the input and output data is always in normal order. The functions support lengths of [32, 64, 128, ..., 4096] samples. </dd></dl>
<dl class="section user"><dt></dt><dd>The forward and inverse real FFT functions apply the standard FFT scaling; no scaling on the forward transform and 1/fftLen scaling on the inverse transform. </dd></dl>
<dl class="section user"><dt>Q15 and Q31</dt><dd>The real algorithms are defined in a similar manner and utilize N/2 complex transforms behind the scenes. </dd></dl>
<dl class="section user"><dt></dt><dd>The complex transforms used internally include scaling to prevent fixed-point overflows. The overall scaling equals 1/(fftLen/2). </dd></dl>
<dl class="section user"><dt></dt><dd>A separate instance structure must be defined for each transform used but twiddle factor and bit reversal tables can be reused. </dd></dl>
<dl class="section user"><dt></dt><dd>There is also an associated initialization function for each data type. The initialization function performs the following operations:<ul>
<li>Sets the values of the internal structure fields.</li>
<li>Initializes twiddle factor table and bit reversal table pointers.</li>
<li>Initializes the internal complex FFT data structure. </li>
</ul>
</dd></dl>
<dl class="section user"><dt></dt><dd>Use of the initialization function is optional. However, if the initialization function is used, then the instance structure cannot be placed into a const data section. To place an instance structure into a const data section, the instance structure should be manually initialized as follows: <pre>
*arm_rfft_instance_q31 S = {fftLenReal, fftLenBy2, ifftFlagR, bitReverseFlagR, twidCoefRModifier, pTwiddleAReal, pTwiddleBReal, pCfft};
*arm_rfft_instance_q15 S = {fftLenReal, fftLenBy2, ifftFlagR, bitReverseFlagR, twidCoefRModifier, pTwiddleAReal, pTwiddleBReal, pCfft};
</pre> where <code>fftLenReal</code> is the length of the real transform; <code>fftLenBy2</code> length of the internal complex transform. <code>ifftFlagR</code> Selects forward (=0) or inverse (=1) transform. <code>bitReverseFlagR</code> Selects bit reversed output (=0) or normal order output (=1). <code>twidCoefRModifier</code> stride modifier for the twiddle factor table. The value is based on the FFT length; <code>pTwiddleAReal</code>points to the A array of twiddle coefficients; <code>pTwiddleBReal</code>points to the B array of twiddle coefficients; <code>pCfft</code> points to the CFFT Instance structure. The CFFT structure must also be initialized. Refer to <a class="el" href="group___complex_f_f_t.html#ga521f670cd9c571bc61aff9bec89f4c26" title="Processing function for the floating-point Radix-4 CFFT/CIFFT.">arm_cfft_radix4_f32()</a> for details regarding static initialization of the complex FFT instance structure. </dd></dl>
</div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<li class="footer">Generated on Tue Oct 27 2015 14:35:33 for CMSIS-DSP by ARM Ltd. All rights reserved.
<!--
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.2
-->
</li>
</ul>
</div>
</body>
</html>