-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathfix_fft.cpp
231 lines (229 loc) · 15 KB
/
fix_fft.cpp
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
#include "fix_fft.h"
const short Fixed15FFT::Sinewave[Fixed15FFT::SAMPLE_SIZE] = {
0, 201, 402, 603, 804, 1005, 1206, 1406,
1607, 1808, 2009, 2209, 2410, 2610, 2811, 3011,
3211, 3411, 3611, 3811, 4011, 4210, 4409, 4608,
4807, 5006, 5205, 5403, 5601, 5799, 5997, 6195,
6392, 6589, 6786, 6982, 7179, 7375, 7571, 7766,
7961, 8156, 8351, 8545, 8739, 8932, 9126, 9319,
9511, 9703, 9895, 10087, 10278, 10469, 10659, 10849,
11038, 11227, 11416, 11604, 11792, 11980, 12166, 12353,
12539, 12724, 12909, 13094, 13278, 13462, 13645, 13827,
14009, 14191, 14372, 14552, 14732, 14911, 15090, 15268,
15446, 15623, 15799, 15975, 16150, 16325, 16499, 16672,
16845, 17017, 17189, 17360, 17530, 17699, 17868, 18036,
18204, 18371, 18537, 18702, 18867, 19031, 19194, 19357,
19519, 19680, 19840, 20000, 20159, 20317, 20474, 20631,
20787, 20942, 21096, 21249, 21402, 21554, 21705, 21855,
22004, 22153, 22301, 22448, 22594, 22739, 22883, 23027,
23169, 23311, 23452, 23592, 23731, 23869, 24006, 24143,
24278, 24413, 24546, 24679, 24811, 24942, 25072, 25201,
25329, 25456, 25582, 25707, 25831, 25954, 26077, 26198,
26318, 26437, 26556, 26673, 26789, 26905, 27019, 27132,
27244, 27355, 27466, 27575, 27683, 27790, 27896, 28001,
28105, 28208, 28309, 28410, 28510, 28608, 28706, 28802,
28897, 28992, 29085, 29177, 29268, 29358, 29446, 29534,
29621, 29706, 29790, 29873, 29955, 30036, 30116, 30195,
30272, 30349, 30424, 30498, 30571, 30643, 30713, 30783,
30851, 30918, 30984, 31049, 31113, 31175, 31236, 31297,
31356, 31413, 31470, 31525, 31580, 31633, 31684, 31735,
31785, 31833, 31880, 31926, 31970, 32014, 32056, 32097,
32137, 32176, 32213, 32249, 32284, 32318, 32350, 32382,
32412, 32441, 32468, 32495, 32520, 32544, 32567, 32588,
32609, 32628, 32646, 32662, 32678, 32692, 32705, 32717,
32727, 32736, 32744, 32751, 32757, 32761, 32764, 32766,
32767, 32766, 32764, 32761, 32757, 32751, 32744, 32736,
32727, 32717, 32705, 32692, 32678, 32662, 32646, 32628,
32609, 32588, 32567, 32544, 32520, 32495, 32468, 32441,
32412, 32382, 32350, 32318, 32284, 32249, 32213, 32176,
32137, 32097, 32056, 32014, 31970, 31926, 31880, 31833,
31785, 31735, 31684, 31633, 31580, 31525, 31470, 31413,
31356, 31297, 31236, 31175, 31113, 31049, 30984, 30918,
30851, 30783, 30713, 30643, 30571, 30498, 30424, 30349,
30272, 30195, 30116, 30036, 29955, 29873, 29790, 29706,
29621, 29534, 29446, 29358, 29268, 29177, 29085, 28992,
28897, 28802, 28706, 28608, 28510, 28410, 28309, 28208,
28105, 28001, 27896, 27790, 27683, 27575, 27466, 27355,
27244, 27132, 27019, 26905, 26789, 26673, 26556, 26437,
26318, 26198, 26077, 25954, 25831, 25707, 25582, 25456,
25329, 25201, 25072, 24942, 24811, 24679, 24546, 24413,
24278, 24143, 24006, 23869, 23731, 23592, 23452, 23311,
23169, 23027, 22883, 22739, 22594, 22448, 22301, 22153,
22004, 21855, 21705, 21554, 21402, 21249, 21096, 20942,
20787, 20631, 20474, 20317, 20159, 20000, 19840, 19680,
19519, 19357, 19194, 19031, 18867, 18702, 18537, 18371,
18204, 18036, 17868, 17699, 17530, 17360, 17189, 17017,
16845, 16672, 16499, 16325, 16150, 15975, 15799, 15623,
15446, 15268, 15090, 14911, 14732, 14552, 14372, 14191,
14009, 13827, 13645, 13462, 13278, 13094, 12909, 12724,
12539, 12353, 12166, 11980, 11792, 11604, 11416, 11227,
11038, 10849, 10659, 10469, 10278, 10087, 9895, 9703,
9511, 9319, 9126, 8932, 8739, 8545, 8351, 8156,
7961, 7766, 7571, 7375, 7179, 6982, 6786, 6589,
6392, 6195, 5997, 5799, 5601, 5403, 5205, 5006,
4807, 4608, 4409, 4210, 4011, 3811, 3611, 3411,
3211, 3011, 2811, 2610, 2410, 2209, 2009, 1808,
1607, 1406, 1206, 1005, 804, 603, 402, 201,
0, -201, -402, -603, -804, -1005, -1206, -1406,
-1607, -1808, -2009, -2209, -2410, -2610, -2811, -3011,
-3211, -3411, -3611, -3811, -4011, -4210, -4409, -4608,
-4807, -5006, -5205, -5403, -5601, -5799, -5997, -6195,
-6392, -6589, -6786, -6982, -7179, -7375, -7571, -7766,
-7961, -8156, -8351, -8545, -8739, -8932, -9126, -9319,
-9511, -9703, -9895, -10087, -10278, -10469, -10659, -10849,
-11038, -11227, -11416, -11604, -11792, -11980, -12166, -12353,
-12539, -12724, -12909, -13094, -13278, -13462, -13645, -13827,
-14009, -14191, -14372, -14552, -14732, -14911, -15090, -15268,
-15446, -15623, -15799, -15975, -16150, -16325, -16499, -16672,
-16845, -17017, -17189, -17360, -17530, -17699, -17868, -18036,
-18204, -18371, -18537, -18702, -18867, -19031, -19194, -19357,
-19519, -19680, -19840, -20000, -20159, -20317, -20474, -20631,
-20787, -20942, -21096, -21249, -21402, -21554, -21705, -21855,
-22004, -22153, -22301, -22448, -22594, -22739, -22883, -23027,
-23169, -23311, -23452, -23592, -23731, -23869, -24006, -24143,
-24278, -24413, -24546, -24679, -24811, -24942, -25072, -25201,
-25329, -25456, -25582, -25707, -25831, -25954, -26077, -26198,
-26318, -26437, -26556, -26673, -26789, -26905, -27019, -27132,
-27244, -27355, -27466, -27575, -27683, -27790, -27896, -28001,
-28105, -28208, -28309, -28410, -28510, -28608, -28706, -28802,
-28897, -28992, -29085, -29177, -29268, -29358, -29446, -29534,
-29621, -29706, -29790, -29873, -29955, -30036, -30116, -30195,
-30272, -30349, -30424, -30498, -30571, -30643, -30713, -30783,
-30851, -30918, -30984, -31049, -31113, -31175, -31236, -31297,
-31356, -31413, -31470, -31525, -31580, -31633, -31684, -31735,
-31785, -31833, -31880, -31926, -31970, -32014, -32056, -32097,
-32137, -32176, -32213, -32249, -32284, -32318, -32350, -32382,
-32412, -32441, -32468, -32495, -32520, -32544, -32567, -32588,
-32609, -32628, -32646, -32662, -32678, -32692, -32705, -32717,
-32727, -32736, -32744, -32751, -32757, -32761, -32764, -32766,
};
const short Fixed15FFT::Window[Fixed15FFT::N_WAVE] = {
2621, 2621, 2622, 2623, 2625, 2628, 2631, 2635,
2639, 2644, 2649, 2655, 2662, 2669, 2676, 2685,
2693, 2703, 2713, 2723, 2734, 2746, 2758, 2771,
2784, 2798, 2812, 2827, 2843, 2859, 2876, 2893,
2910, 2929, 2948, 2967, 2987, 3008, 3029, 3050,
3073, 3095, 3119, 3142, 3167, 3192, 3217, 3243,
3270, 3297, 3325, 3353, 3382, 3411, 3441, 3471,
3502, 3533, 3565, 3598, 3631, 3664, 3698, 3733,
3768, 3804, 3840, 3877, 3914, 3952, 3990, 4029,
4068, 4108, 4148, 4189, 4230, 4272, 4314, 4357,
4401, 4444, 4489, 4534, 4579, 4625, 4671, 4718,
4765, 4813, 4861, 4910, 4959, 5009, 5059, 5110,
5161, 5213, 5265, 5317, 5370, 5424, 5478, 5532,
5587, 5642, 5698, 5754, 5811, 5868, 5926, 5984,
6042, 6101, 6160, 6220, 6280, 6341, 6402, 6464,
6525, 6588, 6651, 6714, 6777, 6841, 6906, 6970,
7036, 7101, 7167, 7234, 7300, 7368, 7435, 7503,
7571, 7640, 7709, 7779, 7849, 7919, 7989, 8060,
8132, 8203, 8275, 8348, 8420, 8493, 8567, 8641,
8715, 8789, 8864, 8939, 9015, 9090, 9167, 9243,
9320, 9397, 9474, 9552, 9630, 9708, 9787, 9866,
9945, 10024, 10104, 10184, 10264, 10345, 10426, 10507,
10588, 10670, 10752, 10834, 10917, 11000, 11082, 11166,
11249, 11333, 11417, 11501, 11586, 11670, 11755, 11840,
11926, 12011, 12097, 12183, 12269, 12355, 12442, 12529,
12616, 12703, 12790, 12878, 12966, 13054, 13142, 13230,
13318, 13407, 13496, 13585, 13674, 13763, 13852, 13942,
14031, 14121, 14211, 14301, 14391, 14482, 14572, 14662,
14753, 14844, 14935, 15026, 15117, 15208, 15299, 15391,
15482, 15574, 15665, 15757, 15849, 15940, 16032, 16124,
16216, 16308, 16400, 16493, 16585, 16677, 16769, 16862,
16954, 17046, 17139, 17231, 17324, 17416, 17509, 17601,
17694, 17786, 17879, 17971, 18064, 18156, 18248, 18341,
18433, 18526, 18618, 18710, 18803, 18895, 18987, 19079,
19171, 19263, 19355, 19447, 19539, 19631, 19722, 19814,
19905, 19997, 20088, 20179, 20271, 20362, 20453, 20543,
20634, 20725, 20815, 20906, 20996, 21086, 21176, 21266,
21356, 21446, 21535, 21625, 21714, 21803, 21892, 21981,
22069, 22158, 22246, 22334, 22422, 22509, 22597, 22684,
22772, 22859, 22945, 23032, 23118, 23204, 23290, 23376,
23462, 23547, 23632, 23717, 23802, 23886, 23970, 24054,
24138, 24222, 24305, 24388, 24471, 24553, 24635, 24717,
24799, 24880, 24962, 25042, 25123, 25203, 25283, 25363,
25443, 25522, 25601, 25679, 25758, 25836, 25913, 25991,
26068, 26144, 26221, 26297, 26373, 26448, 26523, 26598,
26673, 26747, 26820, 26894, 26967, 27040, 27112, 27184,
27256, 27327, 27398, 27469, 27539, 27609, 27678, 27747,
27816, 27884, 27952, 28020, 28087, 28154, 28220, 28286,
28352, 28417, 28482, 28546, 28610, 28674, 28737, 28800,
28862, 28924, 28985, 29046, 29107, 29167, 29227, 29286,
29345, 29404, 29462, 29519, 29576, 29633, 29689, 29745,
29800, 29855, 29910, 29964, 30017, 30070, 30123, 30175,
30226, 30277, 30328, 30378, 30428, 30477, 30526, 30574,
30622, 30669, 30716, 30763, 30808, 30854, 30899, 30943,
30987, 31030, 31073, 31115, 31157, 31198, 31239, 31280,
31319, 31359, 31397, 31436, 31473, 31511, 31547, 31583,
31619, 31654, 31689, 31723, 31757, 31790, 31822, 31854,
31885, 31916, 31947, 31976, 32006, 32034, 32063, 32090,
32117, 32144, 32170, 32196, 32221, 32245, 32269, 32292,
32315, 32337, 32359, 32380, 32400, 32420, 32440, 32459,
32477, 32495, 32512, 32529, 32545, 32560, 32575, 32590,
32603, 32617, 32629, 32642, 32653, 32664, 32675, 32685,
32694, 32703, 32711, 32719, 32726, 32732, 32738, 32744,
32748, 32753, 32756, 32759, 32762, 32764, 32765, 32766,
32767, 32766, 32765, 32764, 32762, 32759, 32756, 32753,
32748, 32744, 32738, 32732, 32726, 32719, 32711, 32703,
32694, 32685, 32675, 32664, 32653, 32642, 32629, 32617,
32603, 32590, 32575, 32560, 32545, 32529, 32512, 32495,
32477, 32459, 32440, 32420, 32400, 32380, 32359, 32337,
32315, 32292, 32269, 32245, 32221, 32196, 32170, 32144,
32117, 32090, 32063, 32034, 32006, 31976, 31947, 31916,
31885, 31854, 31822, 31790, 31757, 31723, 31689, 31654,
31619, 31583, 31547, 31511, 31473, 31436, 31397, 31359,
31319, 31280, 31239, 31198, 31157, 31115, 31073, 31030,
30987, 30943, 30899, 30854, 30808, 30763, 30716, 30669,
30622, 30574, 30526, 30477, 30428, 30378, 30328, 30277,
30226, 30175, 30123, 30070, 30017, 29964, 29910, 29855,
29800, 29745, 29689, 29633, 29576, 29519, 29462, 29404,
29345, 29286, 29227, 29167, 29107, 29046, 28985, 28924,
28862, 28800, 28737, 28674, 28610, 28546, 28482, 28417,
28352, 28286, 28220, 28154, 28087, 28020, 27952, 27884,
27816, 27747, 27678, 27609, 27539, 27469, 27398, 27327,
27256, 27184, 27112, 27040, 26967, 26894, 26820, 26747,
26673, 26598, 26523, 26448, 26373, 26297, 26221, 26144,
26068, 25991, 25913, 25836, 25758, 25679, 25601, 25522,
25443, 25363, 25283, 25203, 25123, 25042, 24962, 24880,
24799, 24717, 24635, 24553, 24471, 24388, 24305, 24222,
24138, 24054, 23970, 23886, 23802, 23717, 23632, 23547,
23462, 23376, 23290, 23204, 23118, 23032, 22945, 22859,
22772, 22684, 22597, 22509, 22422, 22334, 22246, 22158,
22069, 21981, 21892, 21803, 21714, 21625, 21535, 21446,
21356, 21266, 21176, 21086, 20996, 20906, 20815, 20725,
20634, 20543, 20453, 20362, 20271, 20179, 20088, 19997,
19905, 19814, 19722, 19631, 19539, 19447, 19355, 19263,
19171, 19079, 18987, 18895, 18803, 18710, 18618, 18526,
18433, 18341, 18248, 18156, 18064, 17971, 17879, 17786,
17694, 17601, 17509, 17416, 17324, 17231, 17139, 17046,
16954, 16862, 16769, 16677, 16585, 16493, 16400, 16308,
16216, 16124, 16032, 15940, 15849, 15757, 15665, 15574,
15482, 15391, 15299, 15208, 15117, 15026, 14935, 14844,
14753, 14662, 14572, 14482, 14391, 14301, 14211, 14121,
14031, 13942, 13852, 13763, 13674, 13585, 13496, 13407,
13318, 13230, 13142, 13054, 12966, 12878, 12790, 12703,
12616, 12529, 12442, 12355, 12269, 12183, 12097, 12011,
11926, 11840, 11755, 11670, 11586, 11501, 11417, 11333,
11249, 11166, 11082, 11000, 10917, 10834, 10752, 10670,
10588, 10507, 10426, 10345, 10264, 10184, 10104, 10024,
9945, 9866, 9787, 9708, 9630, 9552, 9474, 9397,
9320, 9243, 9167, 9090, 9015, 8939, 8864, 8789,
8715, 8641, 8567, 8493, 8420, 8348, 8275, 8203,
8132, 8060, 7989, 7919, 7849, 7779, 7709, 7640,
7571, 7503, 7435, 7368, 7300, 7234, 7167, 7101,
7036, 6970, 6906, 6841, 6777, 6714, 6651, 6588,
6525, 6464, 6402, 6341, 6280, 6220, 6160, 6101,
6042, 5984, 5926, 5868, 5811, 5754, 5698, 5642,
5587, 5532, 5478, 5424, 5370, 5317, 5265, 5213,
5161, 5110, 5059, 5009, 4959, 4910, 4861, 4813,
4765, 4718, 4671, 4625, 4579, 4534, 4489, 4444,
4401, 4357, 4314, 4272, 4230, 4189, 4148, 4108,
4068, 4029, 3990, 3952, 3914, 3877, 3840, 3804,
3768, 3733, 3698, 3664, 3631, 3598, 3565, 3533,
3502, 3471, 3441, 3411, 3382, 3353, 3325, 3297,
3270, 3243, 3217, 3192, 3167, 3142, 3119, 3095,
3073, 3050, 3029, 3008, 2987, 2967, 2948, 2929,
2910, 2893, 2876, 2859, 2843, 2827, 2812, 2798,
2784, 2771, 2758, 2746, 2734, 2723, 2713, 2703,
2693, 2685, 2676, 2669, 2662, 2655, 2649, 2644,
2639, 2635, 2631, 2628, 2625, 2623, 2622, 2621,
};