w_factor.h

快速傅里叶变换fft算法

//w_factor.h
//here, we choose to compute the fft by using w directly, 
//we can easily get w by search the w_factor.h,
//and the w factors have been converted into short form,
//the wn we may use are 1,2,4,8,16,32,64,128,256,512,and 1024

short w1[2] = {
32767,0};

short w2[4] = {
32767,0, 0,-32766};

short w4[8] = {
32767,0, 23169,-23169, 0,-32766, -23169,-23169
};

short w8[16] = {
32767,0, 30272,-12539, 23169,-23169, 12539,-30272,
0,-32766, -12539,-30272, -23169,-23169, -30272,-12539
};

short w16[32] = {
32767,0, 32137,-6392, 30272,-12539, 27244,-18204,
23169,-23169, 18204,-27244, 12539,-30272, 6392,-32137,
0,-32766, -6392,-32137, -12539,-30272, -18204,-27244,
-23169,-23169, -27244,-18204, -30272,-12539, -32137,-6392
};

short w32[64] = {
32767,0, 32609,-3211, 32137,-6392, 31356,-9511,
30272,-12539, 28897,-15446, 27244,-18204, 25329,-20787,
23169,-23169, 20787,-25329, 18204,-27244, 15446,-28897,
12539,-30272, 9511,-31356, 6392,-32137, 3211,-32609,
0,-32766, -3211,-32609, -6392,-32137, -9511,-31356,
-12539,-30272, -15446,-28897, -18204,-27244, -20787,-25329,
-23169,-23169, -25329,-20787, -27244,-18204, -28897,-15446,
-30272,-12539, -31356,-9511, -32137,-6392, -32609,-3211
};

short w64[128] = {
32767,0, 32727,-1607, 32609,-3211, 32412,-4807,
32137,-6392, 31785,-7961, 31356,-9511, 30851,-11038,
30272,-12539, 29621,-14009, 28897,-15446, 28105,-16845,
27244,-18204, 26318,-19519, 25329,-20787, 24278,-22004,
23169,-23169, 22004,-24278, 20787,-25329, 19519,-26318,
18204,-27244, 16845,-28105, 15446,-28897, 14009,-29621,
12539,-30272, 11038,-30851, 9511,-31356, 7961,-31785,
6392,-32137, 4807,-32412, 3211,-32609, 1607,-32727,
0,-32766, -1607,-32727, -3211,-32609, -4807,-32412,
-6392,-32137, -7961,-31785, -9511,-31356, -11038,-30851,
-12539,-30272, -14009,-29621, -15446,-28897, -16845,-28105,
-18204,-27244, -19519,-26318, -20787,-25329, -22004,-24278,
-23169,-23169, -24278,-22004, -25329,-20787, -26318,-19519,
-27244,-18204, -28105,-16845, -28897,-15446, -29621,-14009,
-30272,-12539, -30851,-11038, -31356,-9511, -31785,-7961,
-32137,-6392, -32412,-4807, -32609,-3211, -32727,-1607
};

short w128[256] = {
32767,0, 32757,-804, 32727,-1607, 32678,-2410,
32609,-3211, 32520,-4011, 32412,-4807, 32284,-5601,
32137,-6392, 31970,-7179, 31785,-7961, 31580,-8739,
31356,-9511, 31113,-10278, 30851,-11038, 30571,-11792,
30272,-12539, 29955,-13278, 29621,-14009, 29268,-14732,
28897,-15446, 28510,-16150, 28105,-16845, 27683,-17530,
27244,-18204, 26789,-18867, 26318,-19519, 25831,-20159,
25329,-20787, 24811,-21402, 24278,-22004, 23731,-22594,
23169,-23169, 22594,-23731, 22004,-24278, 21402,-24811,
20787,-25329, 20159,-25831, 19519,-26318, 18867,-26789,
18204,-27244, 17530,-27683, 16845,-28105, 16150,-28510,
15446,-28897, 14732,-29268, 14009,-29621, 13278,-29955,
12539,-30272, 11792,-30571, 11038,-30851, 10278,-31113,
9511,-31356, 8739,-31580, 7961,-31785, 7179,-31970,
6392,-32137, 5601,-32284, 4807,-32412, 4011,-32520,
3211,-32609, 2410,-32678, 1607,-32727, 804,-32757,
0,-32766, -804,-32757, -1607,-32727, -2410,-32678,
-3211,-32609, -4011,-32520, -4807,-32412, -5601,-32284,
-6392,-32137, -7179,-31970, -7961,-31785, -8739,-31580,
-9511,-31356, -10278,-31113, -11038,-30851, -11792,-30571,
-12539,-30272, -13278,-29955, -14009,-29621, -14732,-29268,
-15446,-28897, -16150,-28510, -16845,-28105, -17530,-27683,
-18204,-27244, -18867,-26789, -19519,-26318, -20159,-25831,
-20787,-25329, -21402,-24811, -22004,-24278, -22594,-23731,
-23169,-23169, -23731,-22594, -24278,-22004, -24811,-21402,
-25329,-20787, -25831,-20159, -26318,-19519, -26789,-18867,
-27244,-18204, -27683,-17530, -28105,-16845, -28510,-16150,
-28897,-15446, -29268,-14732, -29621,-14009, -29955,-13278,
-30272,-12539, -30571,-11792, -30851,-11038, -31113,-10278,
-31356,-9511, -31580,-8739, -31785,-7961, -31970,-7179,
-32137,-6392, -32284,-5601, -32412,-4807, -32520,-4011,
-32609,-3211, -32678,-2410, -32727,-1607, -32757,-804
};

short w256[512] = {
32767,0, 32764,-402, 32757,-804, 32744,-1206,
32727,-1607, 32705,-2009, 32678,-2410, 32646,-2811,
32609,-3211, 32567,-3611, 32520,-4011, 32468,-4409,
32412,-4807, 32350,-5205, 32284,-5601, 32213,-5997,
32137,-6392, 32056,-6786, 31970,-7179, 31880,-7571,
31785,-7961, 31684,-8351, 31580,-8739, 31470,-9126,
31356,-9511, 31236,-9895, 31113,-10278, 30984,-10659,
30851,-11038, 30713,-11416, 30571,-11792, 30424,-12166,
30272,-12539, 30116,-12909, 29955,-13278, 29790,-13645,
29621,-14009, 29446,-14372, 29268,-14732, 29085,-15090,
28897,-15446, 28706,-15799, 28510,-16150, 28309,-16499,
28105,-16845, 27896,-17189, 27683,-17530, 27466,-17868,
27244,-18204, 27019,-18537, 26789,-18867, 26556,-19194,
26318,-19519, 26077,-19840, 25831,-20159, 25582,-20474,
25329,-20787, 25072,-21096, 24811,-21402, 24546,-21705,
24278,-22004, 24006,-22301, 23731,-22594, 23452,-22883,
23169,-23169, 22883,-23452, 22594,-23731, 22301,-24006,
22004,-24278, 21705,-24546, 21402,-24811, 21096,-25072,
20787,-25329, 20474,-25582, 20159,-25831, 19840,-26077,
19519,-26318, 19194,-26556, 18867,-26789, 18537,-27019,
18204,-27244, 17868,-27466, 17530,-27683, 17189,-27896,
16845,-28105, 16499,-28309, 16150,-28510, 15799,-28706,
15446,-28897, 15090,-29085, 14732,-29268, 14372,-29446,
14009,-29621, 13645,-29790, 13278,-29955, 12909,-30116,
12539,-30272, 12166,-30424, 11792,-30571, 11416,-30713,
11038,-30851, 10659,-30984, 10278,-31113, 9895,-31236,
9511,-31356, 9126,-31470, 8739,-31580, 8351,-31684,
7961,-31785, 7571,-31880, 7179,-31970, 6786,-32056,
6392,-32137, 5997,-32213, 5601,-32284, 5205,-32350,
4807,-32412, 4409,-32468, 4011,-32520, 3611,-32567,
3211,-32609, 2811,-32646, 2410,-32678, 2009,-32705,
1607,-32727, 1206,-32744, 804,-32757, 402,-32764,
0,-32766, -402,-32764, -804,-32757, -1206,-32744,
-1607,-32727, -2009,-32705, -2410,-32678, -2811,-32646,
-3211,-32609, -3611,-32567, -4011,-32520, -4409,-32468,
-4807,-32412, -5205,-32350, -5601,-32284, -5997,-32213,
-6392,-32137, -6786,-32056, -7179,-31970, -7571,-31880,
-7961,-31785, -8351,-31684, -8739,-31580, -9126,-31470,
-9511,-31356, -9895,-31236, -10278,-31113, -10659,-30984,
-11038,-30851, -11416,-30713, -11792,-30571, -12166,-30424,
-12539,-30272, -12909,-30116, -13278,-29955, -13645,-29790,
-14009,-29621, -14372,-29446, -14732,-29268, -15090,-29085,
-15446,-28897, -15799,-28706, -16150,-28510, -16499,-28309,
-16845,-28105, -17189,-27896, -17530,-27683, -17868,-27466,
-18204,-27244, -18537,-27019, -18867,-26789, -19194,-26556,
-19519,-26318, -19840,-26077, -20159,-25831, -20474,-25582,
-20787,-25329, -21096,-25072, -21402,-24811, -21705,-24546,
-22004,-24278, -22301,-24006, -22594,-23731, -22883,-23452,
-23169,-23169, -23452,-22883, -23731,-22594, -24006,-22301,
-24278,-22004, -24546,-21705, -24811,-21402, -25072,-21096,
-25329,-20787, -25582,-20474, -25831,-20159, -26077,-19840,
-26318,-19519, -26556,-19194, -26789,-18867, -27019,-18537,
-27244,-18204, -27466,-17868, -27683,-17530, -27896,-17189,
-28105,-16845, -28309,-16499, -28510,-16150, -28706,-15799,
-28897,-15446, -29085,-15090, -29268,-14732, -29446,-14372,
-29621,-14009, -29790,-13645, -29955,-13278, -30116,-12909,
-30272,-12539, -30424,-12166, -30571,-11792, -30713,-11416,
-30851,-11038, -30984,-10659, -31113,-10278, -31236,-9895,
-31356,-9511, -31470,-9126, -31580,-8739, -31684,-8351,
-31785,-7961, -31880,-7571, -31970,-7179, -32056,-6786,
-32137,-6392, -32213,-5997, -32284,-5601, -32350,-5205,
-32412,-4807, -32468,-4409, -32520,-4011, -32567,-3611,
-32609,-3211, -32646,-2811, -32678,-2410, -32705,-2009,
-32727,-1607, -32744,-1206, -32757,-804, -32764,-402
};

short w512[1024] = {
32767,0, 32766,-201, 32764,-402, 32761,-603,
32757,-804, 32751,-1005, 32744,-1206, 32736,-1406,
32727,-1607, 32717,-1808, 32705,-2009, 32692,-2209,
32678,-2410, 32662,-2610, 32646,-2811, 32628,-3011,
32609,-3211, 32588,-3411, 32567,-3611, 32544,-3811,
32520,-4011, 32495,-4210, 32468,-4409, 32441,-4608,
32412,-4807, 32382,-5006, 32350,-5205, 32318,-5403,
32284,-5601, 32249,-5799, 32213,-5997, 32176,-6195,
32137,-6392, 32097,-6589, 32056,-6786, 32014,-6982,
31970,-7179, 31926,-7375, 31880,-7571, 31833,-7766,
31785,-7961, 31735,-8156, 31684,-8351, 31633,-8545,
31580,-8739, 31525,-8932, 31470,-9126, 31413,-9319,
31356,-9511, 31297,-9703, 31236,-9895, 31175,-10087,
31113,-10278, 31049,-10469, 30984,-10659, 30918,-10849,
30851,-11038, 30783,-11227, 30713,-11416, 30643,-11604,
30571,-11792, 30498,-11980, 30424,-12166, 30349,-12353,
30272,-12539, 30195,-12724, 30116,-12909, 30036,-13094,
29955,-13278, 29873,-13462, 29790,-13645, 29706,-13827,
29621,-14009, 29534,-14191, 29446,-14372, 29358,-14552,
29268,-14732, 29177,-14911, 29085,-15090, 28992,-15268,
28897,-15446, 28802,-15623, 28706,-15799, 28608,-15975,
28510,-16150, 28410,-16325, 28309,-16499, 28208,-16672,
28105,-16845, 28001,-17017, 27896,-17189, 27790,-17360,
27683,-17530, 27575,-17699, 27466,-17868, 27355,-18036,
27244,-18204, 27132,-18371, 27019,-18537, 26905,-18702,
26789,-18867, 26673,-19031, 26556,-19194, 26437,-19357,
26318,-19519, 26198,-19680, 26077,-19840, 25954,-20000,
25831,-20159, 25707,-20317, 25582,-20474, 25456,-20631,
25329,-20787, 25201,-20942, 25072,-21096, 24942,-21249,
24811,-21402, 24679,-21554, 24546,-21705, 24413,-21855,
24278,-22004, 24143,-22153, 24006,-22301, 23869,-22448,
23731,-22594, 23592,-22739, 23452,-22883, 23311,-23027,
23169,-23169, 23027,-23311, 22883,-23452, 22739,-23592,
22594,-23731, 22448,-23869, 22301,-24006, 22153,-24143,
22004,-24278, 21855,-24413, 21705,-24546, 21554,-24679,
21402,-24811, 21249,-24942, 21096,-25072, 20942,-25201,
20787,-25329, 20631,-25456, 20474,-25582, 20317,-25707,
20159,-25831, 20000,-25954, 19840,-26077, 19680,-26198,
19519,-26318, 19357,-26437, 19194,-26556, 19031,-26673,
18867,-26789, 18702,-26905, 18537,-27019, 18371,-27132,
18204,-27244, 18036,-27355, 17868,-27466, 17699,-27575,
17530,-27683, 17360,-27790, 17189,-27896, 17017,-28001,
16845,-28105, 16672,-28208, 16499,-28309, 16325,-28410,
16150,-28510, 15975,-28608, 15799,-28706, 15623,-28802,
15446,-28897, 15268,-28992, 15090,-29085, 14911,-29177,
14732,-29268, 14552,-29358, 14372,-29446, 14191,-29534,
14009,-29621, 13827,-29706, 13645,-29790, 13462,-29873,
13278,-29955, 13094,-30036, 12909,-30116, 12724,-30195,
12539,-30272, 12353,-30349, 12166,-30424, 11980,-30498,
11792,-30571, 11604,-30643, 11416,-30713, 11227,-30783,
11038,-30851, 10849,-30918, 10659,-30984, 10469,-31049,
10278,-31113, 10087,-31175, 9895,-31236, 9703,-31297,
9511,-31356, 9319,-31413, 9126,-31470, 8932,-31525,
8739,-31580, 8545,-31633, 8351,-31684, 8156,-31735,
7961,-31785, 7766,-31833, 7571,-31880, 7375,-31926,
7179,-31970, 6982,-32014, 6786,-32056, 6589,-32097,
6392,-32137, 6195,-32176, 5997,-32213, 5799,-32249,
5601,-32284, 5403,-32318, 5205,-32350, 5006,-32382,
4807,-32412, 4608,-32441, 4409,-32468, 4210,-32495,
4011,-32520, 3811,-32544, 3611,-32567, 3411,-32588,
3211,-32609, 3011,-32628, 2811,-32646, 2610,-32662,
2410,-32678, 2209,-32692, 2009,-32705, 1808,-32717,
1607,-32727, 1406,-32736, 1206,-32744, 1005,-32751,
804,-32757, 603,-32761, 402,-32764, 201,-32766,
0,-32766, -201,-32766, -402,-32764, -603,-32761,
-804,-32757, -1005,-32751, -1206,-32744, -1406,-32736,
-1607,-32727, -1808,-32717, -2009,-32705, -2209,-32692,
-2410,-32678, -2610,-32662, -2811,-32646, -3011,-32628,
-3211,-32609, -3411,-32588, -3611,-32567, -3811,-32544,
-4011,-32520, -4210,-32495, -4409,-32468, -4608,-32441,
-4807,-32412, -5006,-32382, -5205,-32350, -5403,-32318,
-5601,-32284, -5799,-32249, -5997,-32213, -6195,-32176,
-6392,-32137, -6589,-32097, -6786,-32056, -6982,-32014,
-7179,-31970, -7375,-31926, -7571,-31880, -7766,-31833,
-7961,-31785, -8156,-31735, -8351,-31684, -8545,-31633,
-8739,-31580, -8932,-31525, -9126,-31470, -9319,-31413,
-9511,-31356, -9703,-31297, -9895,-31236, -10087,-31175,
-10278,-31113, -10469,-31049, -10659,-30984, -10849,-30918,
-11038,-30851, -11227,-30783, -11416,-30713, -11604,-30643,
-11792,-30571, -11980,-30498, -12166,-30424, -12353,-30349,
-12539,-30272, -12724,-30195, -12909,-30116, -13094,-30036,
-13278,-29955, -13462,-29873, -13645,-29790, -13827,-29706,
-14009,-29621, -14191,-29534, -14372,-29446, -14552,-29358,
-14732,-29268, -14911,-29177, -15090,-29085, -15268,-28992,
-15446,-28897, -15623,-28802, -15799,-28706, -15975,-28608,
-16150,-28510, -16325,-28410, -16499,-28309, -16672,-28208,
-16845,-28105, -17017,-28001, -17189,-27896, -17360,-27790,
-17530,-27683, -17699,-27575, -17868,-27466, -18036,-27355,
-18204,-27244, -18371,-27132, -18537,-27019, -18702,-26905,
-18867,-26789, -19031,-26673, -19194,-26556, -19357,-26437,
-19519,-26318, -19680,-26198, -19840,-26077, -20000,-25954,
-20159,-25831, -20317,-25707, -20474,-25582, -20631,-25456,
-20787,-25329, -20942,-25201, -21096,-25072, -21249,-24942,
-21402,-24811, -21554,-24679, -21705,-24546, -21855,-24413,
-22004,-24278, -22153,-24143, -22301,-24006, -22448,-23869,
-22594,-23731, -22739,-23592, -22883,-23452, -23027,-23311,
-23169,-23169, -23311,-23027, -23452,-22883, -23592,-22739,
-23731,-22594, -23869,-22448, -24006,-22301, -24143,-22153,
-24278,-22004, -24413,-21855, -24546,-21705, -24679,-21554,
-24811,-21402, -24942,-21249, -25072,-21096, -25201,-20942,
-25329,-20787, -25456,-20631, -25582,-20474, -25707,-20317,
-25831,-20159, -25954,-20000, -26077,-19840, -26198,-19680,
-26318,-19519, -26437,-19357, -26556,-19194, -26673,-19031,
-26789,-18867, -26905,-18702, -27019,-18537, -27132,-18371,
-27244,-18204, -27355,-18036, -27466,-17868, -27575,-17699,
-27683,-17530, -27790,-17360, -27896,-17189, -28001,-17017,
-28105,-16845, -28208,-16672, -28309,-16499, -28410,-16325,
-28510,-16150, -28608,-15975, -28706,-15799, -28802,-15623,
-28897,-15446, -28992,-15268, -29085,-15090, -29177,-14911,
-29268,-14732, -29358,-14552, -29446,-14372, -29534,-14191,
-29621,-14009, -29706,-13827, -29790,-13645, -29873,-13462,
-29955,-13278, -30036,-13094, -30116,-12909, -30195,-12724,
-30272,-12539, -30349,-12353, -30424,-12166, -30498,-11980,
-30571,-11792, -30643,-11604, -30713,-11416, -30783,-11227,
-30851,-11038, -30918,-10849, -30984,-10659, -31049,-10469,
-31113,-10278, -31175,-10087, -31236,-9895, -31297,-9703,
-31356,-9511, -31413,-9319, -31470,-9126, -31525,-8933,
-31580,-8739, -31633,-8545, -31684,-8351, -31735,-8156,
-31785,-7961, -31833,-7766, -31880,-7571, -31926,-7375,
-31970,-7179, -32014,-6983, -32056,-6786, -32097,-6589,
-32137,-6392, -32176,-6195, -32213,-5997, -32249,-5799,
-32284,-5601, -32318,-5403, -32350,-5205, -32382,-5006,
-32412,-4807, -32441,-4608, -32468,-4409, -32495,-4210,
-32520,-4011, -32544,-3811, -32567,-3611, -32588,-3411,
-32609,-3211, -32628,-3011, -32646,-2811, -32662,-2610,
-32678,-2410, -32692,-2209, -32705,-2009, -32717,-1808,
-32727,-1607, -32736,-1406, -32744,-1206, -32751,-1005,
-32757,-804, -32761,-603, -32764,-402, -32766,-201
};