-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathfast-fourier-transform.html
More file actions
243 lines (209 loc) · 54.3 KB
/
fast-fourier-transform.html
File metadata and controls
243 lines (209 loc) · 54.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
<!DOCTYPE html>
<html lang="en-US">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<title>Algorithm - Fast Fourier Transform</title>
<meta name="generator" content="VuePress 1.8.2">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/site.webmanifest">
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">
<meta name="description" content="Radix 2 FFT, Radix 2 Inverse FFT">
<meta property="og:site_name" content="DevTut">
<meta property="og:title" content="Algorithm - Fast Fourier Transform">
<meta property="og:description" content="Radix 2 FFT, Radix 2 Inverse FFT">
<meta property="og:type" content="article">
<meta property="og:url" content="/algorithm/fast-fourier-transform.html">
<meta property="og:image" content="/logo.png">
<meta name="twitter:title" content="Algorithm - Fast Fourier Transform">
<meta name="twitter:description" content="Radix 2 FFT, Radix 2 Inverse FFT">
<meta name="twitter:url" content="/algorithm/fast-fourier-transform.html">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="/logo.png">
<meta name="theme-color" content="#ffffff">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="msapplication-TileImage" content="/mstile-150x150.png">
<meta name="msapplication-TileColor" content="#da532c">
<meta name="google-site-verification" content="76_rKXgwMVIjd-axJC_1zPV9OS4mEjvtgjYOWVkAdnQ">
<link rel="preload" href="/assets/css/0.styles.60619e34.css" as="style"><link rel="preload" href="/assets/js/app.1779e102.js" as="script"><link rel="preload" href="/assets/js/3.2cfa8016.js" as="script"><link rel="preload" href="/assets/js/36.64813417.js" as="script">
<link rel="stylesheet" href="/assets/css/0.styles.60619e34.css">
</head>
<body>
<div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">DevTut</span></a> <div class="links"><form id="search-form" role="search" class="algolia-search-wrapper search-box"><input id="algolia-search-input" class="search-query"></form> <nav class="nav-links can-hide"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav> <ul class="sidebar-links"><li><section class="sidebar-group depth-0"><p class="sidebar-heading open"><span>Algorithm</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/algorithm/" aria-current="page" class="sidebar-link">Disclaimer</a></li><li><a href="/algorithm/getting-started-with-algorithm.html" class="sidebar-link">Getting started with algorithm</a></li><li><a href="/algorithm/algorithm-complexity.html" class="sidebar-link">Algorithm Complexity</a></li><li><a href="/algorithm/big-o-notation.html" class="sidebar-link">Big-O Notation</a></li><li><a href="/algorithm/trees.html" class="sidebar-link">Trees</a></li><li><a href="/algorithm/binary-search-trees.html" class="sidebar-link">Binary Search Trees</a></li><li><a href="/algorithm/check-if-a-tree-is-bst-or-not.html" class="sidebar-link">Check if a tree is BST or not</a></li><li><a href="/algorithm/binary-tree-traversals.html" class="sidebar-link">Binary Tree traversals</a></li><li><a href="/algorithm/lowest-common-ancestor-of-a-binary-tree.html" class="sidebar-link">Lowest common ancestor of a Binary Tree</a></li><li><a href="/algorithm/graph.html" class="sidebar-link">Graph</a></li><li><a href="/algorithm/graph-traversals.html" class="sidebar-link">Graph Traversals</a></li><li><a href="/algorithm/dijkstras-algorithm.html" class="sidebar-link">Dijkstra’s Algorithm</a></li><li><a href="/algorithm/a-pathfinding.html" class="sidebar-link">A* Pathfinding</a></li><li><a href="/algorithm/a-pathfinding-algorithm.html" class="sidebar-link">A* Pathfinding Algorithm</a></li><li><a href="/algorithm/dynamic-programming.html" class="sidebar-link">Dynamic Programming</a></li><li><a href="/algorithm/applications-of-dynamic-programming.html" class="sidebar-link">Applications of Dynamic Programming</a></li><li><a href="/algorithm/kruskal-s-algorithm.html" class="sidebar-link">Kruskal's Algorithm</a></li><li><a href="/algorithm/greedy-algorithms.html" class="sidebar-link">Greedy Algorithms</a></li><li><a href="/algorithm/applications-of-greedy-technique.html" class="sidebar-link">Applications of Greedy technique</a></li><li><a href="/algorithm/prim-s-algorithm.html" class="sidebar-link">Prim's Algorithm</a></li><li><a href="/algorithm/bellman-ford-algorithm.html" class="sidebar-link">Bellman–Ford Algorithm</a></li><li><a href="/algorithm/line-algorithm.html" class="sidebar-link">Line Algorithm</a></li><li><a href="/algorithm/floyd-warshall-algorithm.html" class="sidebar-link">Floyd-Warshall Algorithm</a></li><li><a href="/algorithm/catalan-number-algorithm.html" class="sidebar-link">Catalan Number Algorithm</a></li><li><a href="/algorithm/multithreaded-algorithms.html" class="sidebar-link">Multithreaded Algorithms</a></li><li><a href="/algorithm/knuth-morris-pratt-kmp-algorithm.html" class="sidebar-link">Knuth Morris Pratt (KMP) Algorithm</a></li><li><a href="/algorithm/edit-distance-dynamic-algorithm.html" class="sidebar-link">Edit Distance Dynamic Algorithm</a></li><li><a href="/algorithm/online-algorithms.html" class="sidebar-link">Online algorithms</a></li><li><a href="/algorithm/integer-partition-algorithm.html" class="sidebar-link">Integer Partition Algorithm</a></li><li><a href="/algorithm/maximum-path-sum-algorithm.html" class="sidebar-link">Maximum Path Sum Algorithm</a></li><li><a href="/algorithm/maximum-subarray-algorithm.html" class="sidebar-link">Maximum Subarray Algorithm</a></li><li><a href="/algorithm/sliding-window-algorithm.html" class="sidebar-link">Sliding Window Algorithm</a></li><li><a href="/algorithm/sorting.html" class="sidebar-link">Sorting</a></li><li><a href="/algorithm/bubble-sort.html" class="sidebar-link">Bubble Sort</a></li><li><a href="/algorithm/merge-sort.html" class="sidebar-link">Merge Sort</a></li><li><a href="/algorithm/insertion-sort.html" class="sidebar-link">Insertion Sort</a></li><li><a href="/algorithm/bucket-sort.html" class="sidebar-link">Bucket Sort</a></li><li><a href="/algorithm/quicksort.html" class="sidebar-link">Quicksort</a></li><li><a href="/algorithm/counting-sort.html" class="sidebar-link">Counting Sort</a></li><li><a href="/algorithm/heap-sort.html" class="sidebar-link">Heap Sort</a></li><li><a href="/algorithm/cycle-sort.html" class="sidebar-link">Cycle Sort</a></li><li><a href="/algorithm/odd-even-sort.html" class="sidebar-link">Odd-Even Sort</a></li><li><a href="/algorithm/selection-sort.html" class="sidebar-link">Selection Sort</a></li><li><a href="/algorithm/pigeonhole-sort.html" class="sidebar-link">Pigeonhole Sort</a></li><li><a href="/algorithm/radix-sort.html" class="sidebar-link">Radix Sort</a></li><li><a href="/algorithm/shell-sort.html" class="sidebar-link">Shell Sort</a></li><li><a href="/algorithm/pancake-sort.html" class="sidebar-link">Pancake Sort</a></li><li><a href="/algorithm/searching.html" class="sidebar-link">Searching</a></li><li><a href="/algorithm/substring-search.html" class="sidebar-link">Substring Search</a></li><li><a href="/algorithm/breadth-first-search.html" class="sidebar-link">Breadth-First Search</a></li><li><a href="/algorithm/depth-first-search.html" class="sidebar-link">Depth First Search</a></li><li><a href="/algorithm/hash-functions.html" class="sidebar-link">Hash Functions</a></li><li><a href="/algorithm/travelling-salesman.html" class="sidebar-link">Travelling Salesman</a></li><li><a href="/algorithm/shortest-common-supersequence-problem.html" class="sidebar-link">Shortest Common Supersequence Problem</a></li><li><a href="/algorithm/knapsack-problem.html" class="sidebar-link">Knapsack Problem</a></li><li><a href="/algorithm/equation-solving.html" class="sidebar-link">Equation Solving</a></li><li><a href="/algorithm/longest-common-subsequence.html" class="sidebar-link">Longest Common Subsequence</a></li><li><a href="/algorithm/longest-increasing-subsequence.html" class="sidebar-link">Longest Increasing Subsequence</a></li><li><a href="/algorithm/check-two-strings-are-anagrams.html" class="sidebar-link">Check two strings are anagrams</a></li><li><a href="/algorithm/pascal-s-triangle.html" class="sidebar-link">Pascal's Triangle</a></li><li><a href="/algorithm/algo-print-a-m-n-matrix-in-square-wise.html" class="sidebar-link">Algo:- Print a m*n matrix in square wise</a></li><li><a href="/algorithm/matrix-exponentiation.html" class="sidebar-link">Matrix Exponentiation</a></li><li><a href="/algorithm/polynomial-time-bounded-algorithm-for-minimum-vertex-cover.html" class="sidebar-link">polynomial-time bounded algorithm for Minimum Vertex Cover</a></li><li><a href="/algorithm/dynamic-time-warping.html" class="sidebar-link">Dynamic Time Warping</a></li><li><a href="/algorithm/fast-fourier-transform.html" aria-current="page" class="active sidebar-link">Fast Fourier Transform</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/algorithm/fast-fourier-transform.html#radix-2-fft" class="sidebar-link">Radix 2 FFT</a></li><li class="sidebar-sub-header"><a href="/algorithm/fast-fourier-transform.html#radix-2-inverse-fft" class="sidebar-link">Radix 2 Inverse FFT</a></li></ul></li><li><a href="/algorithm/pseudocode.html" class="sidebar-link">Pseudocode</a></li><li><a href="/algorithm/contributors.html" class="sidebar-link">The Contributors</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="fast-fourier-transform"><a href="#fast-fourier-transform" class="header-anchor">#</a> Fast Fourier Transform</h1> <p>The Real and Complex form of DFT (<strong>D</strong>iscrete <strong>F</strong>ourier <strong>T</strong>ransforms) can be used to perform frequency analysis or synthesis for any discrete and periodic signals. The FFT (<strong>F</strong>ast <strong>F</strong>ourier <strong>T</strong>ransform) is an implementation of the DFT which may be performed quickly on modern CPUs.</p> <h2 id="radix-2-fft"><a href="#radix-2-fft" class="header-anchor">#</a> Radix 2 FFT</h2> <p>The simplest and perhaps best-known method for computing the FFT is the Radix-2 Decimation in Time algorithm. The Radix-2 FFT works by decomposing an N point time domain signal into N time domain signals each composed of a single point<a href="https://i.stack.imgur.com/KNiJM.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/KNiJM.png" alt="Signal Decomposition in the FFT prior to spectral reconstruction [Steven. W. Smith, 1997]"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>.</p> <p>Signal decomposition, or ‘decimation in time’ is achieved by bit reversing the indices for the array of time domain data. Thus, for a sixteen-point signal, sample 1 (Binary 0001) is swapped with sample 8 (1000), sample 2 (0010) is swapped with 4 (0100) and so on. Sample swapping using the bit reverse technique can be achieved simply in software, but limits the use of the Radix 2 FFT to signals of length N = 2^M.</p> <p>The value of a 1-point signal in the time domain is equal to its value in the frequency domain, thus this array of decomposed single time-domain points requires no transformation to become an array of frequency domain points. The N single points; however, need to be reconstructed into one N-point frequency spectra. Optimal reconstruction of the complete frequency spectrum is performed using butterfly calculations. Each reconstruction stage in the Radix-2 FFT performs a number of two point butterflies, using a similar set of exponential weighting functions, Wn^R.</p> <p><a href="https://i.stack.imgur.com/OKYjB.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/OKYjB.png" alt="Radix 2 Butterfly used in the FFT"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>The FFT removes redundant calculations in the Discrete Fourier Transform by exploiting the periodicity of Wn^R. Spectral reconstruction is completed in log2(N) stages of butterfly calculations giving X[K]; the real and imaginary frequency domain data in rectangular form. To convert to magnitude and phase (polar coordinates) requires finding the absolute value, √(Re2 + Im2), and argument, tan-1(Im/Re).</p> <p><a href="https://i.stack.imgur.com/RsWAe.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/RsWAe.png" alt="enter image description here"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>The complete butterfly flow diagram for an eight point Radix 2 FFT is shown below. Note the input signals have previously been reordered according to the decimation in time procedure outlined previously.</p> <p><a href="https://i.stack.imgur.com/4plRM.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/4plRM.png" alt="Three Stage Radix 2 FFT on Signal size 16"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>The FFT typically operates on complex inputs and produces a complex output. For real signals, the imaginary part may be set to zero and real part set to the input signal, x[n], however many optimisations are possible involving the transformation of real-only data. Values of Wn^R used throughout the reconstruction can be determined using the exponential weighting equation.</p> <p>The value of R (the exponential weighting power) is determined the current stage in the spectral reconstruction and the current calculation within a particular butterfly.</p> <p><strong>Code Example (C/C++)</strong></p> <p>A C/C++ code sample for computing the Radix 2 FFT can be found below. This is a simple implementation which works for any size N where N is a power of 2. It is approx 3x slower than the fastest FFTw implementation, but still a very good basis for future optimisation or for learning about how this algorithm works.</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string"><math.h></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">PI</span> <span class="token expression"><span class="token number">3.1415926535897932384626433832795</span> </span><span class="token comment">// PI for sine/cos calculations</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">TWOPI</span> <span class="token expression"><span class="token number">6.283185307179586476925286766559</span> </span><span class="token comment">// 2*PI for sine/cos calculations</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">Deg2Rad</span> <span class="token expression"><span class="token number">0.017453292519943295769236907684886</span> </span><span class="token comment">// Degrees to Radians factor</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">Rad2Deg</span> <span class="token expression"><span class="token number">57.295779513082320876798154814105</span> </span><span class="token comment">// Radians to Degrees factor</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">log10_2</span> <span class="token expression"><span class="token number">0.30102999566398119521373889472449</span> </span><span class="token comment">// Log10 of 2 </span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">log10_2_INV</span> <span class="token expression"><span class="token number">3.3219280948873623478703194294948</span> </span><span class="token comment">// 1/Log10(2)</span></span>
<span class="token comment">// complex variable structure (double precision)</span>
<span class="token keyword">struct</span> <span class="token class-name">complex</span>
<span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
<span class="token keyword">double</span> Re<span class="token punctuation">,</span> Im<span class="token punctuation">;</span> <span class="token comment">// Not so complicated after all</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token comment">// Returns true if N is a power of 2</span>
<span class="token keyword">bool</span> <span class="token function">isPwrTwo</span><span class="token punctuation">(</span><span class="token keyword">int</span> N<span class="token punctuation">,</span> <span class="token keyword">int</span> <span class="token operator">*</span>M<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token operator">*</span>M <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token function">ceil</span><span class="token punctuation">(</span><span class="token function">log10</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token keyword">double</span><span class="token punctuation">)</span>N<span class="token punctuation">)</span> <span class="token operator">*</span> log10_2_INV<span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">// M is number of stages to perform. 2^M = N</span>
<span class="token keyword">int</span> NN <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token function">pow</span><span class="token punctuation">(</span><span class="token number">2.0</span><span class="token punctuation">,</span> <span class="token operator">*</span>M<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>NN <span class="token operator">!=</span> N<span class="token punctuation">)</span> <span class="token operator">||</span> <span class="token punctuation">(</span>NN <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token comment">// Check N is a power of 2. </span>
<span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
<span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">void</span> <span class="token function">rad2FFT</span><span class="token punctuation">(</span><span class="token keyword">int</span> N<span class="token punctuation">,</span> complex <span class="token operator">*</span>x<span class="token punctuation">,</span> complex <span class="token operator">*</span>DFT<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> M <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token comment">// Check if power of two. If not, exit </span>
<span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span><span class="token function">isPwrTwo</span><span class="token punctuation">(</span>N<span class="token punctuation">,</span> <span class="token operator">&</span>M<span class="token punctuation">)</span><span class="token punctuation">)</span>
<span class="token keyword">throw</span> <span class="token string">"Rad2FFT(): N must be a power of 2 for Radix FFT"</span><span class="token punctuation">;</span>
<span class="token comment">// Integer Variables</span>
<span class="token keyword">int</span> BSep<span class="token punctuation">;</span> <span class="token comment">// BSep is memory spacing between butterflies</span>
<span class="token keyword">int</span> BWidth<span class="token punctuation">;</span> <span class="token comment">// BWidth is memory spacing of opposite ends of the butterfly</span>
<span class="token keyword">int</span> P<span class="token punctuation">;</span> <span class="token comment">// P is number of similar Wn's to be used in that stage</span>
<span class="token keyword">int</span> j<span class="token punctuation">;</span> <span class="token comment">// j is used in a loop to perform all calculations in each stage</span>
<span class="token keyword">int</span> stage <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// stage is the stage number of the FFT. There are M stages in total (1 to M).</span>
<span class="token keyword">int</span> HiIndex<span class="token punctuation">;</span> <span class="token comment">// HiIndex is the index of the DFT array for the top value of each butterfly calc </span>
<span class="token keyword">unsigned</span> <span class="token keyword">int</span> iaddr<span class="token punctuation">;</span> <span class="token comment">// bitmask for bit reversal </span>
<span class="token keyword">int</span> ii<span class="token punctuation">;</span> <span class="token comment">// Integer bitfield for bit reversal (Decimation in Time)</span>
<span class="token keyword">int</span> MM1 <span class="token operator">=</span> M <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token keyword">unsigned</span> <span class="token keyword">int</span> i<span class="token punctuation">;</span>
<span class="token keyword">int</span> l<span class="token punctuation">;</span>
<span class="token keyword">unsigned</span> <span class="token keyword">int</span> nMax <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">unsigned</span> <span class="token keyword">int</span><span class="token punctuation">)</span>N<span class="token punctuation">;</span>
<span class="token comment">// Double Precision Variables</span>
<span class="token keyword">double</span> TwoPi_N <span class="token operator">=</span> TWOPI <span class="token operator">/</span> <span class="token punctuation">(</span><span class="token keyword">double</span><span class="token punctuation">)</span>N<span class="token punctuation">;</span> <span class="token comment">// constant to save computational time. = 2*PI / N</span>
<span class="token keyword">double</span> TwoPi_NP<span class="token punctuation">;</span>
<span class="token comment">// complex Variables (See 'struct complex')</span>
complex WN<span class="token punctuation">;</span> <span class="token comment">// Wn is the exponential weighting function in the form a + jb</span>
complex TEMP<span class="token punctuation">;</span> <span class="token comment">// TEMP is used to save computation in the butterfly calc</span>
complex <span class="token operator">*</span>pDFT <span class="token operator">=</span> DFT<span class="token punctuation">;</span> <span class="token comment">// Pointer to first elements in DFT array</span>
complex <span class="token operator">*</span>pLo<span class="token punctuation">;</span> <span class="token comment">// Pointer for lo / hi value of butterfly calcs</span>
complex <span class="token operator">*</span>pHi<span class="token punctuation">;</span>
complex <span class="token operator">*</span>pX<span class="token punctuation">;</span> <span class="token comment">// Pointer to x[n]</span>
<span class="token comment">// Decimation In Time - x[n] sample sorting</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> nMax<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">,</span> DFT<span class="token operator">++</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
pX <span class="token operator">=</span> x <span class="token operator">+</span> i<span class="token punctuation">;</span> <span class="token comment">// Calculate current x[n] from base address *x and index i.</span>
ii <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// Reset new address for DFT[n]</span>
iaddr <span class="token operator">=</span> i<span class="token punctuation">;</span> <span class="token comment">// Copy i for manipulations</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>l <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> l <span class="token operator"><</span> M<span class="token punctuation">;</span> l<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token comment">// Bit reverse i and store in ii...</span>
<span class="token punctuation">{</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>iaddr <span class="token operator">&</span> <span class="token number">0x01</span><span class="token punctuation">)</span> <span class="token comment">// Detemine least significant bit</span>
ii <span class="token operator">+=</span> <span class="token punctuation">(</span><span class="token number">1</span> <span class="token operator"><<</span> <span class="token punctuation">(</span>MM1 <span class="token operator">-</span> l<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// Increment ii by 2^(M-1-l) if lsb was 1</span>
iaddr <span class="token operator">>>=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// right shift iaddr to test next bit. Use logical operations for speed increase</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>iaddr<span class="token punctuation">)</span>
<span class="token keyword">break</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
DFT <span class="token operator">=</span> pDFT <span class="token operator">+</span> ii<span class="token punctuation">;</span> <span class="token comment">// Calculate current DFT[n] from base address *pDFT and bit reversed index ii </span>
DFT<span class="token operator">-></span>Re <span class="token operator">=</span> pX<span class="token operator">-></span>Re<span class="token punctuation">;</span> <span class="token comment">// Update the complex array with address sorted time domain signal x[n]</span>
DFT<span class="token operator">-></span>Im <span class="token operator">=</span> pX<span class="token operator">-></span>Im<span class="token punctuation">;</span> <span class="token comment">// NB: Imaginary is always zero</span>
<span class="token punctuation">}</span>
<span class="token comment">// FFT Computation by butterfly calculation</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>stage <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> stage <span class="token operator"><=</span> M<span class="token punctuation">;</span> stage<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token comment">// Loop for M stages, where 2^M = N</span>
<span class="token punctuation">{</span>
BSep <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token punctuation">(</span><span class="token function">pow</span><span class="token punctuation">(</span><span class="token number">2</span><span class="token punctuation">,</span> stage<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// Separation between butterflies = 2^stage</span>
P <span class="token operator">=</span> N <span class="token operator">/</span> BSep<span class="token punctuation">;</span> <span class="token comment">// Similar Wn's in this stage = N/Bsep</span>
BWidth <span class="token operator">=</span> BSep <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">;</span> <span class="token comment">// Butterfly width (spacing between opposite points) = Separation / 2.</span>
TwoPi_NP <span class="token operator">=</span> TwoPi_N<span class="token operator">*</span>P<span class="token punctuation">;</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator"><</span> BWidth<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token comment">// Loop for j calculations per butterfly</span>
<span class="token punctuation">{</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">!=</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token comment">// Save on calculation if R = 0, as WN^0 = (1 + j0)</span>
<span class="token punctuation">{</span>
<span class="token comment">//WN.Re = cos(TwoPi_NP*j)</span>
WN<span class="token punctuation">.</span>Re <span class="token operator">=</span> <span class="token function">cos</span><span class="token punctuation">(</span>TwoPi_N<span class="token operator">*</span>P<span class="token operator">*</span>j<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// Calculate Wn (Real and Imaginary)</span>
WN<span class="token punctuation">.</span>Im <span class="token operator">=</span> <span class="token operator">-</span><span class="token function">sin</span><span class="token punctuation">(</span>TwoPi_N<span class="token operator">*</span>P<span class="token operator">*</span>j<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>HiIndex <span class="token operator">=</span> j<span class="token punctuation">;</span> HiIndex <span class="token operator"><</span> N<span class="token punctuation">;</span> HiIndex <span class="token operator">+=</span> BSep<span class="token punctuation">)</span> <span class="token comment">// Loop for HiIndex Step BSep butterflies per stage</span>
<span class="token punctuation">{</span>
pHi <span class="token operator">=</span> pDFT <span class="token operator">+</span> HiIndex<span class="token punctuation">;</span> <span class="token comment">// Point to higher value</span>
pLo <span class="token operator">=</span> pHi <span class="token operator">+</span> BWidth<span class="token punctuation">;</span> <span class="token comment">// Point to lower value (Note VC++ adjusts for spacing between elements)</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">!=</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token comment">// If exponential power is not zero...</span>
<span class="token punctuation">{</span>
<span class="token comment">//CMult(pLo, &WN, &TEMP); // Perform complex multiplication of Lovalue with Wn</span>
TEMP<span class="token punctuation">.</span>Re <span class="token operator">=</span> <span class="token punctuation">(</span>pLo<span class="token operator">-></span>Re <span class="token operator">*</span> WN<span class="token punctuation">.</span>Re<span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token punctuation">(</span>pLo<span class="token operator">-></span>Im <span class="token operator">*</span> WN<span class="token punctuation">.</span>Im<span class="token punctuation">)</span><span class="token punctuation">;</span>
TEMP<span class="token punctuation">.</span>Im <span class="token operator">=</span> <span class="token punctuation">(</span>pLo<span class="token operator">-></span>Re <span class="token operator">*</span> WN<span class="token punctuation">.</span>Im<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token punctuation">(</span>pLo<span class="token operator">-></span>Im <span class="token operator">*</span> WN<span class="token punctuation">.</span>Re<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">//CSub (pHi, &TEMP, pLo);</span>
pLo<span class="token operator">-></span>Re <span class="token operator">=</span> pHi<span class="token operator">-></span>Re <span class="token operator">-</span> TEMP<span class="token punctuation">.</span>Re<span class="token punctuation">;</span> <span class="token comment">// Find new Lovalue (complex subtraction)</span>
pLo<span class="token operator">-></span>Im <span class="token operator">=</span> pHi<span class="token operator">-></span>Im <span class="token operator">-</span> TEMP<span class="token punctuation">.</span>Im<span class="token punctuation">;</span>
<span class="token comment">//CAdd (pHi, &TEMP, pHi); // Find new Hivalue (complex addition)</span>
pHi<span class="token operator">-></span>Re <span class="token operator">=</span> <span class="token punctuation">(</span>pHi<span class="token operator">-></span>Re <span class="token operator">+</span> TEMP<span class="token punctuation">.</span>Re<span class="token punctuation">)</span><span class="token punctuation">;</span>
pHi<span class="token operator">-></span>Im <span class="token operator">=</span> <span class="token punctuation">(</span>pHi<span class="token operator">-></span>Im <span class="token operator">+</span> TEMP<span class="token punctuation">.</span>Im<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">else</span>
<span class="token punctuation">{</span>
TEMP<span class="token punctuation">.</span>Re <span class="token operator">=</span> pLo<span class="token operator">-></span>Re<span class="token punctuation">;</span>
TEMP<span class="token punctuation">.</span>Im <span class="token operator">=</span> pLo<span class="token operator">-></span>Im<span class="token punctuation">;</span>
<span class="token comment">//CSub (pHi, &TEMP, pLo);</span>
pLo<span class="token operator">-></span>Re <span class="token operator">=</span> pHi<span class="token operator">-></span>Re <span class="token operator">-</span> TEMP<span class="token punctuation">.</span>Re<span class="token punctuation">;</span> <span class="token comment">// Find new Lovalue (complex subtraction)</span>
pLo<span class="token operator">-></span>Im <span class="token operator">=</span> pHi<span class="token operator">-></span>Im <span class="token operator">-</span> TEMP<span class="token punctuation">.</span>Im<span class="token punctuation">;</span>
<span class="token comment">//CAdd (pHi, &TEMP, pHi); // Find new Hivalue (complex addition)</span>
pHi<span class="token operator">-></span>Re <span class="token operator">=</span> <span class="token punctuation">(</span>pHi<span class="token operator">-></span>Re <span class="token operator">+</span> TEMP<span class="token punctuation">.</span>Re<span class="token punctuation">)</span><span class="token punctuation">;</span>
pHi<span class="token operator">-></span>Im <span class="token operator">=</span> <span class="token punctuation">(</span>pHi<span class="token operator">-></span>Im <span class="token operator">+</span> TEMP<span class="token punctuation">.</span>Im<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
pLo <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// Null all pointers</span>
pHi <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
pDFT <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
DFT <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
pX <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="radix-2-inverse-fft"><a href="#radix-2-inverse-fft" class="header-anchor">#</a> Radix 2 Inverse FFT</h2> <p>Due to the strong duality of the Fourier Transform, adjusting the output of a forward transform can produce the inverse FFT. Data in the frequency domain can be converted to the time domain by the following method:</p> <ol><li>Find the complex conjugate of the frequency domain data by inverting the imaginary component for all instances of K.</li> <li>Perform the forward FFT on the conjugated frequency domain data.</li> <li>Divide each output of the result of this FFT by N to give the true time domain value.</li> <li>Find the complex conjugate of the output by inverting the imaginary component of the time domain data for all instances of n.</li></ol> <p><strong><strong>Note</strong>: both frequency and time domain data are complex variables. Typically the imaginary component of the time domain signal following an inverse FFT is either zero, or ignored as rounding error. Increasing the precision of variables from 32-bit float to 64-bit double, or 128-bit long double significantly reduces rounding errors produced by several consecutive FFT operations.</strong></p> <p><strong>Code Example (C/C++)</strong></p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string"><math.h></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">PI</span> <span class="token expression"><span class="token number">3.1415926535897932384626433832795</span> </span><span class="token comment">// PI for sine/cos calculations</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">TWOPI</span> <span class="token expression"><span class="token number">6.283185307179586476925286766559</span> </span><span class="token comment">// 2*PI for sine/cos calculations</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">Deg2Rad</span> <span class="token expression"><span class="token number">0.017453292519943295769236907684886</span> </span><span class="token comment">// Degrees to Radians factor</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">Rad2Deg</span> <span class="token expression"><span class="token number">57.295779513082320876798154814105</span> </span><span class="token comment">// Radians to Degrees factor</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">log10_2</span> <span class="token expression"><span class="token number">0.30102999566398119521373889472449</span> </span><span class="token comment">// Log10 of 2 </span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">log10_2_INV</span> <span class="token expression"><span class="token number">3.3219280948873623478703194294948</span> </span><span class="token comment">// 1/Log10(2)</span></span>
<span class="token comment">// complex variable structure (double precision)</span>
<span class="token keyword">struct</span> <span class="token class-name">complex</span>
<span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
<span class="token keyword">double</span> Re<span class="token punctuation">,</span> Im<span class="token punctuation">;</span> <span class="token comment">// Not so complicated after all</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">rad2InverseFFT</span><span class="token punctuation">(</span><span class="token keyword">int</span> N<span class="token punctuation">,</span> complex <span class="token operator">*</span>x<span class="token punctuation">,</span> complex <span class="token operator">*</span>DFT<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token comment">// M is number of stages to perform. 2^M = N</span>
<span class="token keyword">double</span> Mx <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token function">log10</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token keyword">double</span><span class="token punctuation">)</span>N<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token function">log10</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token keyword">double</span><span class="token punctuation">)</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> a <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token punctuation">(</span><span class="token function">ceil</span><span class="token punctuation">(</span><span class="token function">pow</span><span class="token punctuation">(</span><span class="token number">2.0</span><span class="token punctuation">,</span> Mx<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> status <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>a <span class="token operator">!=</span> N<span class="token punctuation">)</span> <span class="token comment">// Check N is a power of 2</span>
<span class="token punctuation">{</span>
x <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
DFT <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">throw</span> <span class="token string">"rad2InverseFFT(): N must be a power of 2 for Radix 2 Inverse FFT"</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
complex <span class="token operator">*</span>pDFT <span class="token operator">=</span> DFT<span class="token punctuation">;</span> <span class="token comment">// Reset vector for DFT pointers</span>
complex <span class="token operator">*</span>pX <span class="token operator">=</span> x<span class="token punctuation">;</span> <span class="token comment">// Reset vector for x[n] pointer</span>
<span class="token keyword">double</span> NN <span class="token operator">=</span> <span class="token number">1</span> <span class="token operator">/</span> <span class="token punctuation">(</span><span class="token keyword">double</span><span class="token punctuation">)</span>N<span class="token punctuation">;</span> <span class="token comment">// Scaling factor for the inverse FFT </span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> N<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">,</span> DFT<span class="token operator">++</span><span class="token punctuation">)</span>
DFT<span class="token operator">-></span>Im <span class="token operator">*=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// Find the complex conjugate of the Frequency Spectrum</span>
DFT <span class="token operator">=</span> pDFT<span class="token punctuation">;</span> <span class="token comment">// Reset Freq Domain Pointer</span>
<span class="token function">rad2FFT</span><span class="token punctuation">(</span>N<span class="token punctuation">,</span> DFT<span class="token punctuation">,</span> x<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// Calculate the forward FFT with variables switched (time & freq)</span>
<span class="token keyword">int</span> i<span class="token punctuation">;</span>
complex<span class="token operator">*</span> x<span class="token punctuation">;</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> x <span class="token operator">=</span> pX<span class="token punctuation">;</span> i <span class="token operator"><</span> N<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">,</span> x<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
x<span class="token operator">-></span>Re <span class="token operator">*=</span> NN<span class="token punctuation">;</span> <span class="token comment">// Divide time domain by N for correct amplitude scaling</span>
x<span class="token operator">-></span>Im <span class="token operator">*=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// Change the sign of ImX</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div></div> <footer class="page-edit"><div class="edit-link"><a href="https://github.com/devtut/generate/edit/master/docs/algorithm/fast-fourier-transform.md" target="_blank" rel="noopener noreferrer">Edit this page on GitHub</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
←
<a href="/algorithm/dynamic-time-warping.html" class="prev">
Dynamic Time Warping
</a></span> <span class="next"><a href="/algorithm/pseudocode.html">
Pseudocode
</a>
→
</span></p></div> </main></div><div class="global-ui"><!----></div></div>
<script src="/assets/js/app.1779e102.js" defer></script><script src="/assets/js/3.2cfa8016.js" defer></script><script src="/assets/js/36.64813417.js" defer></script>
</body>
</html>