# Converting fft to ifft

1. Jul 21, 2014

### btb4198

I have a working FFT, but my question is how do I convert it into an IFFT?
I was told that an IFFT should be just like the FFT that you are using.

this is the FFT I have:

Code (Text):

public Complex[] FFT(Complex[] x )
{
int N2 = x.Length;
Complex[] X = new Complex[N2];
if (N2 == 1)
{
return x;
}
Complex[] odd = new Complex[N2 / 2];
Complex[] even = new Complex[N2 / 2];
Complex[] Y_Odd = new Complex[N2 / 2];
Complex[] Y_Even = new Complex[N2 / 2];
for (int t = 0; t < N2 / 2; t++)
{
even[t] = x[t * 2];
odd[t] = x[(t * 2) + 1];
}
Y_Even = FFT(even);
Y_Odd = FFT(odd);
Complex temp4;

for (int k = 0; k < (N2 / 2); k++)
{
temp4 = Complex1(k, N2);
X[k] = Y_Even[k] + (Y_Odd[k] * temp4);
X[k + (N2 / 2)] = Y_Even[k] - (Y_Odd[k] * temp4);
}
return X;
}

public Complex Complex1(int K, int N3)
{
Complex W = Complex.Pow((Complex.Exp(-1 * Complex.ImaginaryOne * (2.0 * Math.PI / N3))), K);
return W;

}

so how do I make an ifft from this ?
I was told that it should only be a few changes made to get the ifft.

I tried to do it myself, but I am not getting the same values back that I put in...

so I made an array of values and put it in to the fft and then the ifft and I cannot get the same values I put in back.

so I do not think I changed it the right way.

Last edited: Jul 21, 2014
2. Jul 21, 2014

### Baluncore

It is usual to pass an integer to the FFT routine.
That integer takes a value of +1 or –1 depending on the direction of transformation required.

You will need to go back to the original source of your algorithm to find out how it can be reversed.

3. Jul 21, 2014

### olivermsun

Check out Expressing the inverse DFT in terms of the DFT. It'll be quicker than my explaining it.

4. Jul 21, 2014

### btb4198

Oliverman,
can you show me an example?

Baluncore,
the original source did not have a reversed.
what parts are normal different ?

I think that:
public Complex Complex1(int K, int N3)
{
Complex W = Complex.Pow((Complex.Exp(-1 * Complex.ImaginaryOne * (2.0 * Math.PI / N3))), K);
return W;

}

should be :
public Complex Complex1(int K, int N3)
{
Complex W = Complex.Pow((Complex.Exp(1 * Complex.ImaginaryOne * (2.0 * Math.PI / N3))), K);
return W;

}

5. Jul 22, 2014

### Baluncore

This is a FFT version originally written in FORTRAN by Brenner.
It is translated here to an easily understood hybrid form of BASIC.
Code (Text):

Dim As Integer Transform_Depth = 16     ' depth of transform = Log2(n)
Dim As Double Channel_Separation = 625. ' channel separation in hertz

' precompute secondary parameters
Dim As Integer n = 2 ^ Transform_Depth  ' number of samples
Dim As Floating real(n), imag(n)        ' In Phase and Quadrature Phase
Dim As Double Acquisition_Time = 1 / Channel_Separation
Dim As Double Sample_rate = n * Channel_Separation
Dim As Double Sample_Time = 1 / Sample_rate
Const As Double Pi = Atan2(0,-1)
Const As Double TwoPi = 2 * Pi

' analyser
FFT([B]-1[/B], n, Real(), Imag())

Sub FFT(_   ' Fast Fourier Transform, forward gain is sqr(lx)
[B]Byval sg As Integer,_   ' sg = -1 -> forward, sg = +1 -> reverse[/B]
Byval lx As Integer,_   ' number of elements in array
re() As Floating,_        '      In phase    = Real(1 ... lx)
im() As Floating)         ' Quadrature phase = Imag(1 ... lx)
Dim As Integer i, j, m, L, v, st
Dim As Floating sc, rt, it, ca, rw, iw
j = 1
sc = Sqr(1 / Lx)
For i = 1 To Lx
If i <= j Then
rt = re(j) * sc
it = im(j) * sc
re(j) = re(i) * sc
im(j) = im(i) * sc
re(i) = rt
im(i) = it
End If
m = Lx / 2
Do
If j <= m Then Exit Do
j = j - m
m = m / 2
Loop While m >= 1
j = j + m
Next i
L = 1
Do
st = 2 * L
For m = 1 To L
ca = Pi * (m - 1) * ([B]Sg[/B] / L)   ' note Sg selects direction
rw = Cos(ca)
iw = Sin(ca)
For i = m To Lx Step st
v = i + L
rt = rw * re(v) - iw * im(v)
it = rw * im(v) + iw * re(v)
re(v) = re(i) - rt
im(v) = im(i) - it
re(i) = re(i) + rt
im(i) = im(i) + it
Next i
Next m
L = st
Loop While L < Lx
End Sub

Last edited: Jul 22, 2014
6. Jul 22, 2014

### btb4198

do you have one in C, C#, or C++ ?
sorry, I do not understand FORTRAN.
also, can this be used as an iFFT?

what part of an FFT do you change to get an IFFT?
and what do you change it to ?

I think this is the part that should be changer

Code (Text):

for (int k = 0; k < (N2 / 2); k++)
{
temp4 = Complex1(k, N2);
X[k] = Y_Even[k] + (Y_Odd[k] * temp4);
X[k + (N2 / 2)] = Y_Even[k] - (Y_Odd[k] * temp4);
}

I just do not know what to change it to...
does anyone know ?

oh this is the Complex1 function:
Code (Text):

public Complex Complex1(int K, int N3)
{
Complex W = Complex.Pow((Complex.Exp(-1 * Complex.ImaginaryOne * (2.0 * Math.PI / N3))), K);
return W;

}

7. Jul 22, 2014

### olivermsun

The first "trick" at the link I posted is to reverse the inputs. For example, suppose you have the sequence
$$\{ x_n \} = x_1, x_2, \ldots, x_{N},$$
which you transform using your fft() routine to get the Fourier coefficients
$$\mathcal{F}(\{ x_n \}) = \{ a_n \} = a_0, a_1, \ldots, a_{N-1}.$$

Now you want the inverse transform. You do this using the fact
$$\mathcal{F}^{-1} (\{ x_n \}) = \mathcal{F}(\{ x_{-n}\}) / N.$$
You divide by $N$ because fft() and ifft() are normalized differently by convention. You'll want to test this for your particular fft() code.

Because the Fourier transform is cyclic modulo $N$, $a_{-n} = a_{N-n}$, and
\begin{align} \mathcal{F}^{-1} ( [ a_0, a_1, \ldots, a_{N-1} ]) &= \mathcal{F}( [ a_0, a_{-1}, \ldots, a_{-(N-1)} ]) / N \\ &= \mathcal{F}( [ a_0, a_{N-1}, \ldots, a_{2}, a_{1} ]) / N . \end{align}
What you end up doing is reversing the input sequence except for the first element, $a_0$.

Hope this helps.

8. Jul 22, 2014

### btb4198

olivermsun,

so you are saying I just do a0/N?
where would I put that at in the FFT?

do I just have a for statement that goes in and dived all of them by N
would it be this ?
Code (Text):

for (int k = 0; k < (N2 / 2); k++)
{
temp4 = Complex1(k, N2);
X[k] =  X[K]/N;
X[k + (N2 / 2)]  =    X[k + (N2 / 2)] /N;
}

can you work an example?

Last edited: Jul 22, 2014
9. Jul 22, 2014

### olivermsun

Hmm, I'm not sure what more I can say, short of coding an example.

Take a closer look at my post to see the indices of the inputs. The key is to reverse the order of the input array that you're going pass to your FFT() function. You divide the outputs by $N$ after you're done.

10. Jul 22, 2014

### btb4198

olivermsun,

can you code an example ?
what do you mean by reverse the order of the input array?

11. Jul 22, 2014

### Baluncore

@ btb4198.

My example code does both the FFT and the Inverse FFT. Read the comment...
Byval sg As Integer,_ ' sg = -1 -> forward, sg = +1 -> reverse

There is one line that uses the control variable Sg ...
ca = Pi * (m - 1) * (Sg / L) ' note Sg selects direction

If you cannot read the BASIC program then you will probably never understand an FFT.
_ underscore extends the line, ' single quote is a comment.

C is way more difficult to understand than BASIC because the ; is used instead of the word End.

The scale factor applied here to both forward and inverse transforms is the square root of the length, Lx.

12. Jul 22, 2014

### olivermsun

You pass an array Complex x to your function FFT(x), right?

So say you have
x = {0.0 1.0 2.0 3.0 4.0 5.0}
then to do an ifft instead of an fft, you need to reverse the array
x_ifft = {0.0 5.0 4.0 3.0 2.0 1.0}
and then call FFT(x_ifft) and divide the output by N.
That will give you the ifft of x.

13. Jul 23, 2014

### btb4198

Baluncore,
I do understand C. I learned C in school. It would be a lot better for me in C.

olivermsun,
Why would you x to the ifft ?
ok so

you have an x with is a Complex array. and this you send it to the FFT and you get X which is amplitude over frequency/bin. you use the bins to get the frequency, So now I have all my frequencies from x are in X. I am going to add a fifter and zero out the frequencies I do not need/want.
and then you would send X to the IFFT and you should get x back ?

if I use the filter and zero out the bins of the frequencies I do not need, and then send it to the IFFT I will get x back without the frequencies I did not want.

that is how it works right ?

so why would I send x backward ? I do not understand ?
wait do you mean X
x is the input array with the signal
X is after the fft with the amplitude over frequency / bins

should I reverse X and then send it to the ifft?

14. Jul 23, 2014

### olivermsun

?

Okay, sure. I assume you understand that you have to zero out positive and negative frequency members in pairs.

No, you reverse the entries in X and send it to the same FFT() function you already have. That will return the inverse FFT of X (the original, unreversed version).

15. Jul 23, 2014

### btb4198

Baluncore
this function does not call itself
how can it be going the fft?

what is "_ "? it is here Sub FFT(_ ' F
why it is there ?

what is this going ?
ca = Pi * (m - 1) * (Sg / L) ' note Sg selects direction

where is your
Complex W = Complex.Pow((Complex.Exp(-1 * Complex.ImaginaryOne * (2.0 * Math.PI / N3))), K); ?

you need that
I do not see anything like that

16. Jul 23, 2014

### btb4198

ok
olivermsun,
I did what you said and this it what I got :

Code (Text):

FFT  before IFF
5.38330078125
10.7666015625
16.14990234375
21.533203125
26.91650390625
32.2998046875
37.68310546875
43.06640625
48.44970703125
53.8330078125
59.21630859375
64.599609375
69.98291015625
75.3662109375
80.74951171875
86.1328125
91.51611328125
96.8994140625
102.28271484375
107.666015625
113.04931640625
118.4326171875
123.81591796875
129.19921875
134.58251953125
139.9658203125
145.34912109375
150.732421875
156.11572265625
161.4990234375
166.88232421875
172.265625
177.64892578125
183.0322265625
188.41552734375
193.798828125
199.18212890625
204.5654296875
209.94873046875
215.33203125
220.71533203125
226.0986328125
231.48193359375
236.865234375
242.24853515625
247.6318359375
253.01513671875
258.3984375
263.78173828125
269.1650390625
274.54833984375
279.931640625
285.31494140625
290.6982421875
296.08154296875
301.46484375
306.84814453125
312.2314453125
317.61474609375
322.998046875
328.38134765625
333.7646484375
339.14794921875
344.53125
349.91455078125
355.2978515625
360.68115234375
366.064453125
371.44775390625
376.8310546875
382.21435546875
387.59765625
392.98095703125
398.3642578125
403.74755859375
409.130859375
414.51416015625
419.8974609375
425.28076171875
430.6640625
436.04736328125
441.4306640625
446.81396484375
452.197265625
457.58056640625
462.9638671875
468.34716796875
473.73046875
479.11376953125
484.4970703125
489.88037109375
495.263671875
500.64697265625
506.0302734375
511.41357421875
516.796875
522.18017578125
527.5634765625
532.94677734375
538.330078125
543.71337890625
549.0966796875
554.47998046875
559.86328125
565.24658203125
570.6298828125
576.01318359375
581.396484375
586.77978515625
592.1630859375
597.54638671875
602.9296875
608.31298828125
613.6962890625
619.07958984375
624.462890625
629.84619140625
635.2294921875
640.61279296875
645.99609375
651.37939453125
656.7626953125
662.14599609375
667.529296875
672.91259765625
678.2958984375
683.67919921875
689.0625
694.44580078125
699.8291015625
705.21240234375
710.595703125
715.97900390625
721.3623046875
726.74560546875
732.12890625
737.51220703125
742.8955078125
748.27880859375
753.662109375
759.04541015625
764.4287109375
769.81201171875
775.1953125
780.57861328125
785.9619140625
791.34521484375
796.728515625
802.11181640625
807.4951171875
812.87841796875
818.26171875
823.64501953125
829.0283203125
834.41162109375
839.794921875
845.17822265625
850.5615234375
855.94482421875
861.328125
866.71142578125
872.0947265625
877.47802734375
882.861328125
888.24462890625
893.6279296875
899.01123046875
904.39453125
909.77783203125
915.1611328125
920.54443359375
925.927734375
931.31103515625
936.6943359375
942.07763671875
947.4609375
952.84423828125
958.2275390625
963.61083984375
968.994140625
974.37744140625
979.7607421875
985.14404296875
990.52734375
995.91064453125
1001.2939453125
1006.67724609375
1012.060546875
1017.44384765625
1022.8271484375
1028.21044921875
1033.59375
1038.97705078125
1044.3603515625
1049.74365234375
1055.126953125
1060.51025390625
1065.8935546875
1071.27685546875
1076.66015625
1082.04345703125
1087.4267578125
1092.81005859375
1098.193359375
1103.57666015625
1108.9599609375
1114.34326171875
1119.7265625
1125.10986328125
1130.4931640625
1135.87646484375
1141.259765625
1146.64306640625
1152.0263671875
1157.40966796875
1162.79296875
1168.17626953125
1173.5595703125
1178.94287109375
1184.326171875
1189.70947265625
1195.0927734375
1200.47607421875
1205.859375
1211.24267578125
1216.6259765625
1222.00927734375
1227.392578125
1232.77587890625
1238.1591796875
1243.54248046875
1248.92578125
1254.30908203125
1259.6923828125
1265.07568359375
1270.458984375
1275.84228515625
1281.2255859375
1286.60888671875
1291.9921875
1297.37548828125
1302.7587890625
1308.14208984375
1313.525390625
1318.90869140625
1324.2919921875
1329.67529296875
1335.05859375
1340.44189453125
1345.8251953125
1351.20849609375
1356.591796875
1361.97509765625
1367.3583984375
1372.74169921875
1378.125
1383.50830078125
1388.8916015625
1394.27490234375
1399.658203125
1405.04150390625
1410.4248046875
1415.80810546875
1421.19140625
1426.57470703125
1431.9580078125
1437.34130859375
1442.724609375
1448.10791015625
1453.4912109375
1458.87451171875
1464.2578125
1469.64111328125
1475.0244140625
1480.40771484375
1485.791015625
1491.17431640625
1496.5576171875
1501.94091796875
1507.32421875
1512.70751953125
1518.0908203125
1523.47412109375
1528.857421875
1534.24072265625
1539.6240234375
1545.00732421875
1550.390625
1555.77392578125
1561.1572265625
1566.54052734375
1571.923828125
1577.30712890625
1582.6904296875
1588.07373046875
1593.45703125
1598.84033203125
1604.2236328125
1609.60693359375
1614.990234375
1620.37353515625
1625.7568359375
1631.14013671875
1636.5234375
1641.90673828125
1647.2900390625
1652.67333984375
1658.056640625
1663.43994140625
1668.8232421875
1674.20654296875
1679.58984375
1684.97314453125
1690.3564453125
1695.73974609375
1701.123046875
1706.50634765625
1711.8896484375
1717.27294921875
1722.65625
1728.03955078125
1733.4228515625
1738.80615234375
1744.189453125
1749.57275390625
1754.9560546875
1760.33935546875
1765.72265625
1771.10595703125
1776.4892578125
1781.87255859375
1787.255859375
1792.63916015625
1798.0224609375
1803.40576171875
1808.7890625
1814.17236328125
1819.5556640625
1824.93896484375
1830.322265625
1835.70556640625
1841.0888671875
1846.47216796875
1851.85546875
1857.23876953125
1862.6220703125
1868.00537109375
1873.388671875
1878.77197265625
1884.1552734375
1889.53857421875
1894.921875
1900.30517578125
1905.6884765625
1911.07177734375
1916.455078125
1921.83837890625
1927.2216796875
1932.60498046875
1937.98828125
1943.37158203125
1948.7548828125
1954.13818359375
1959.521484375
1964.90478515625
1970.2880859375
1975.67138671875
1981.0546875
1986.43798828125
1991.8212890625
1997.20458984375
2002.587890625
2007.97119140625
2013.3544921875
2018.73779296875
2024.12109375
2029.50439453125
2034.8876953125
2040.27099609375
2045.654296875
2051.03759765625
2056.4208984375
2061.80419921875
2067.1875
2072.57080078125
2077.9541015625
2083.33740234375
2088.720703125
2094.10400390625
2099.4873046875
2104.87060546875
2110.25390625
2115.63720703125
2121.0205078125
2126.40380859375
2131.787109375
2137.17041015625
2142.5537109375
2147.93701171875
2153.3203125
2158.70361328125
2164.0869140625
2169.47021484375
2174.853515625
2180.23681640625
2185.6201171875
2191.00341796875
2196.38671875
2201.77001953125
2207.1533203125
2212.53662109375
2217.919921875
2223.30322265625
2228.6865234375
2234.06982421875
2239.453125
2244.83642578125
2250.2197265625
2255.60302734375
2260.986328125
2266.36962890625
2271.7529296875
2277.13623046875
2282.51953125
2287.90283203125
2293.2861328125
2298.66943359375
2304.052734375
2309.43603515625
2314.8193359375
2320.20263671875
2325.5859375
2330.96923828125
2336.3525390625
2341.73583984375
2347.119140625
2352.50244140625
2357.8857421875
2363.26904296875
2368.65234375
2374.03564453125
2379.4189453125
2384.80224609375
2390.185546875
2395.56884765625
2400.9521484375
2406.33544921875
2411.71875
2417.10205078125
2422.4853515625
2427.86865234375
2433.251953125
2438.63525390625
2444.0185546875
2449.40185546875
2454.78515625
2460.16845703125
2465.5517578125
2470.93505859375
2476.318359375
2481.70166015625
2487.0849609375
2492.46826171875
2497.8515625
2503.23486328125
2508.6181640625
2514.00146484375
2519.384765625
2524.76806640625
2530.1513671875
2535.53466796875
2540.91796875
2546.30126953125
2551.6845703125
2557.06787109375
2562.451171875
2567.83447265625
2573.2177734375
2578.60107421875
2583.984375
2589.36767578125
2594.7509765625
2600.13427734375
2605.517578125
2610.90087890625
2616.2841796875
2621.66748046875
2627.05078125
2632.43408203125
2637.8173828125
2643.20068359375
2648.583984375
2653.96728515625
2659.3505859375
2664.73388671875
2670.1171875
2675.50048828125
2680.8837890625
2686.26708984375
2691.650390625
2697.03369140625
2702.4169921875
2707.80029296875
2713.18359375
2718.56689453125
2723.9501953125
2729.33349609375
2734.716796875
2740.10009765625
2745.4833984375
2750.86669921875
2756.25
2761.63330078125
2767.0166015625
2772.39990234375
2777.783203125
2783.16650390625
2788.5498046875
2793.93310546875
2799.31640625
2804.69970703125
2810.0830078125
2815.46630859375
2820.849609375
2826.23291015625
2831.6162109375
2836.99951171875
2842.3828125
2847.76611328125
2853.1494140625
2858.53271484375
2863.916015625
2869.29931640625
2874.6826171875
2880.06591796875
2885.44921875
2890.83251953125
2896.2158203125
2901.59912109375
2906.982421875
2912.36572265625
2917.7490234375
2923.13232421875
2928.515625
2933.89892578125
2939.2822265625
2944.66552734375
2950.048828125
2955.43212890625
2960.8154296875
2966.19873046875
2971.58203125
2976.96533203125
2982.3486328125
2987.73193359375
2993.115234375
2998.49853515625
3003.8818359375
3009.26513671875
3014.6484375
3020.03173828125
3025.4150390625
3030.79833984375
3036.181640625
3041.56494140625
3046.9482421875
3052.33154296875
3057.71484375
3063.09814453125
3068.4814453125
3073.86474609375
3079.248046875
3084.63134765625
3090.0146484375
3095.39794921875
3100.78125
3106.16455078125
3111.5478515625
3116.93115234375
3122.314453125
3127.69775390625
3133.0810546875
3138.46435546875
3143.84765625
3149.23095703125
3154.6142578125
3159.99755859375
3165.380859375
3170.76416015625
3176.1474609375
3181.53076171875
3186.9140625
3192.29736328125
3197.6806640625
3203.06396484375
3208.447265625
3213.83056640625
3219.2138671875
3224.59716796875
3229.98046875
3235.36376953125
3240.7470703125
3246.13037109375
3251.513671875
3256.89697265625
3262.2802734375
3267.66357421875
3273.046875
3278.43017578125
3283.8134765625
3289.19677734375
3294.580078125
3299.96337890625
3305.3466796875
3310.72998046875
3316.11328125
3321.49658203125
3326.8798828125
3332.26318359375
3337.646484375
3343.02978515625
3348.4130859375
3353.79638671875
3359.1796875
3364.56298828125
3369.9462890625
3375.32958984375
3380.712890625
3386.09619140625
3391.4794921875
3396.86279296875
3402.24609375
3407.62939453125
3413.0126953125
3418.39599609375
3423.779296875
3429.16259765625
3434.5458984375
3439.92919921875
3445.3125
3450.69580078125
3456.0791015625
3461.46240234375
3466.845703125
3472.22900390625
3477.6123046875
3482.99560546875
3488.37890625
3493.76220703125
3499.1455078125
3504.52880859375
3509.912109375
3515.29541015625
3520.6787109375
3526.06201171875
3531.4453125
3536.82861328125
3542.2119140625
3547.59521484375
3552.978515625
3558.36181640625
3563.7451171875
3569.12841796875
3574.51171875
3579.89501953125
3585.2783203125
3590.66162109375
3596.044921875
3601.42822265625
3606.8115234375
3612.19482421875
3617.578125
3622.96142578125
3628.3447265625
3633.72802734375
3639.111328125
3644.49462890625
3649.8779296875
3655.26123046875
3660.64453125
3666.02783203125
3671.4111328125
3676.79443359375
3682.177734375
3687.56103515625
3692.9443359375
3698.32763671875
3703.7109375
3709.09423828125
3714.4775390625
3719.86083984375
3725.244140625
3730.62744140625
3736.0107421875
3741.39404296875
3746.77734375
3752.16064453125
3757.5439453125
3762.92724609375
3768.310546875
3773.69384765625
3779.0771484375
3784.46044921875
3789.84375
3795.22705078125
3800.6103515625
3805.99365234375
3811.376953125
3816.76025390625
3822.1435546875
3827.52685546875
3832.91015625
3838.29345703125
3843.6767578125
3849.06005859375

Code (Text):

After the IFFT
5.38330078125
10.7666015625
16.14990234375
21.533203125
26.91650390625
32.2998046875
37.68310546875
43.06640625
48.44970703125
53.8330078125
59.21630859375
64.599609375
69.98291015625
75.3662109375
80.74951171875
86.1328125
91.51611328125
96.8994140625
102.28271484375
107.666015625
113.04931640625
118.4326171875
123.81591796875
129.19921875
134.58251953125
139.9658203125
145.34912109375
150.732421875
156.11572265625
161.4990234375
166.88232421875
172.265625
177.64892578125
183.0322265625
188.41552734375
193.798828125
199.18212890625
204.5654296875
209.94873046875
215.33203125
220.71533203125
226.0986328125
231.48193359375
236.865234375
242.24853515625
247.6318359375
253.01513671875
258.3984375
263.78173828125
269.1650390625
274.54833984375
279.931640625
285.31494140625
290.6982421875
296.08154296875
301.46484375
306.84814453125
312.2314453125
317.61474609375
322.998046875
328.38134765625
333.7646484375
339.14794921875
344.53125
349.91455078125
355.2978515625
360.68115234375
366.064453125
371.44775390625
376.8310546875
382.21435546875
387.59765625
392.98095703125
398.3642578125
403.74755859375
409.130859375
414.51416015625
419.8974609375
425.28076171875
430.6640625
436.04736328125
441.4306640625
446.81396484375
452.197265625
457.58056640625
462.9638671875
947.4609375
952.84423828125
958.2275390625
963.61083984375
968.994140625
974.37744140625
979.7607421875
985.14404296875
990.52734375
995.91064453125
1001.2939453125
1006.67724609375
1012.060546875
1017.44384765625
1022.8271484375
1028.21044921875
1033.59375
1038.97705078125
1044.3603515625
1049.74365234375
1055.126953125
1060.51025390625
1065.8935546875
1071.27685546875
1076.66015625
1082.04345703125
1087.4267578125
1092.81005859375
1098.193359375
1103.57666015625
1108.9599609375
1114.34326171875
1119.7265625
1125.10986328125
1130.4931640625
1135.87646484375
1141.259765625
1146.64306640625
1152.0263671875
1157.40966796875
1162.79296875
1168.17626953125
1173.5595703125
1178.94287109375
1184.326171875
1189.70947265625
1195.0927734375
1200.47607421875
1205.859375
1211.24267578125
1216.6259765625
1222.00927734375
1227.392578125
1232.77587890625
1238.1591796875
1243.54248046875
1248.92578125
1254.30908203125
1259.6923828125
1265.07568359375
1270.458984375
1275.84228515625
1281.2255859375
1286.60888671875
1291.9921875
1297.37548828125
1302.7587890625
1308.14208984375
1313.525390625
1318.90869140625
1324.2919921875
1329.67529296875
1335.05859375
1340.44189453125
1345.8251953125
1351.20849609375
1356.591796875
1361.97509765625
1367.3583984375
1372.74169921875
1378.125
1383.50830078125
1388.8916015625
1394.27490234375
1399.658203125
1405.04150390625
1410.4248046875
1415.80810546875
1421.19140625
1426.57470703125
1431.9580078125
1437.34130859375
1442.724609375
1448.10791015625
1453.4912109375
1458.87451171875
1464.2578125
1469.64111328125
1475.0244140625
1480.40771484375
1485.791015625
1491.17431640625
1496.5576171875
1501.94091796875
1507.32421875
1512.70751953125
1518.0908203125
1523.47412109375
1528.857421875
1534.24072265625
1539.6240234375
1545.00732421875
1550.390625
1555.77392578125
1561.1572265625
1566.54052734375
1571.923828125
1577.30712890625
1582.6904296875
1588.07373046875
1593.45703125
1598.84033203125
1604.2236328125
1609.60693359375
1614.990234375
1620.37353515625
1625.7568359375
1631.14013671875
1636.5234375
1641.90673828125
1647.2900390625
1652.67333984375
1658.056640625
1663.43994140625
1668.8232421875
1674.20654296875
2347.119140625
2352.50244140625
2357.8857421875
2363.26904296875
2368.65234375
2374.03564453125
2379.4189453125
2384.80224609375
2390.185546875
2395.56884765625
2400.9521484375
2406.33544921875
2411.71875
2417.10205078125
2422.4853515625
2427.86865234375
2433.251953125
2438.63525390625
2444.0185546875
2449.40185546875
2454.78515625
2460.16845703125
2465.5517578125
2470.93505859375
2476.318359375
2481.70166015625
2487.0849609375
2492.46826171875
2497.8515625
2503.23486328125
2508.6181640625
2514.00146484375
2519.384765625
2524.76806640625
2530.1513671875
2535.53466796875
2540.91796875
2546.30126953125
2551.6845703125
2557.06787109375
2562.451171875
2567.83447265625
2573.2177734375
2578.60107421875
2583.984375
2589.36767578125
2594.7509765625
2600.13427734375
2605.517578125
2610.90087890625
2616.2841796875
2621.66748046875
2627.05078125
2632.43408203125
2637.8173828125
2643.20068359375
2648.583984375
2653.96728515625
2659.3505859375
2664.73388671875
2670.1171875
2675.50048828125
2680.8837890625
2686.26708984375
2691.650390625
2697.03369140625
2702.4169921875
2707.80029296875
2713.18359375
2718.56689453125
2723.9501953125
2729.33349609375
2734.716796875
2740.10009765625
2745.4833984375
2750.86669921875
2756.25
2761.63330078125
2767.0166015625
2772.39990234375
2777.783203125
2783.16650390625
2788.5498046875
2793.93310546875
2799.31640625
2804.69970703125
2810.0830078125
2815.46630859375
2820.849609375
2826.23291015625
2831.6162109375
2836.99951171875
2842.3828125
2847.76611328125
2853.1494140625
2858.53271484375
2863.916015625
2869.29931640625
2874.6826171875
2880.06591796875
2885.44921875
2890.83251953125
2896.2158203125
2901.59912109375
2906.982421875
2912.36572265625
3762.92724609375
3768.310546875
3773.69384765625
3779.0771484375
3784.46044921875
3789.84375
3795.22705078125
3800.6103515625
3805.99365234375
3811.376953125
3816.76025390625
3822.1435546875
3827.52685546875
3832.91015625
3838.29345703125
3843.6767578125
3849.06005859375
3854.443359375
3859.82666015625
3865.2099609375
3870.59326171875
3875.9765625
3881.35986328125
3886.7431640625
3892.12646484375
3897.509765625
3902.89306640625
3908.2763671875
3913.65966796875
3919.04296875
3924.42626953125
3929.8095703125
3935.19287109375
3940.576171875
3945.95947265625
3951.3427734375
3956.72607421875
3962.109375
3967.49267578125
3972.8759765625
3978.25927734375
3983.642578125
3989.02587890625
3994.4091796875
3999.79248046875
4005.17578125
4010.55908203125
4015.9423828125
4021.32568359375
4026.708984375
4032.09228515625
4037.4755859375
4042.85888671875
4048.2421875
4053.62548828125
4059.0087890625
4064.39208984375
4069.775390625
4075.15869140625
4080.5419921875
4085.92529296875
4091.30859375
4096.69189453125
4102.0751953125
4107.45849609375
4112.841796875
4118.22509765625
4123.6083984375
4128.99169921875
4134.375
4139.75830078125
4145.1416015625

the Magnitude are not right ...
it does not get high over 177 or 183

it does before the ifft

so you know I am doing
this
sample array -> fft -> reverse X -> fft -> divided by N

17. Jul 23, 2014

### olivermsun

Did you reverse X except for the first element as I said in the posts above?

Also why don't you try a sample array with something like 8 elements? That ought to be a lot easier for the rest of us to look at. Plot the sample array, the fft, your reversed input, and the out put from a second fft.

18. Jul 23, 2014

### btb4198

ok this is what I have now:

input is this
0.0128224757617273
0.0256428432180955
0.0384589944103984
0.0512688220731793
0.0640702199807129
0.0768610832933166
0.0896393089034335

in to the FFT
then I get this:

{(0.358763747640863, 0)}
{(-0.0513165020896524, 0.123645814974265)}
{(-0.0512351044382327, 0.0512056075713916)}
{(-0.0512211420567062, 0.0212093348238226)}
{(-0.0512182504716808, 0)}
{(-0.0512211420567062, -0.0212093348238226)}
{(-0.0512351044382327, -0.0512056075713916)}
{(-0.0513165020896524, -0.123645814974265)}

F is 11025

then I do the reverse X

{(0.358763747640863, 0)}
{(-0.0513165020896524, -0.123645814974265)}
{(-0.0512351044382327, -0.0512056075713916)}
{(-0.0512211420567062, -0.0212093348238226)}
{(-0.0512182504716808, 0)}
{(-0.0512211420567062, 0.0212093348238226)}
{(-0.0512351044382327, 0.0512056075713916)}
{(-0.0513165020896524, 0.123645814974265)}

and then I send it to the fft
and Divided by N
and I get :
0.0448454684551079
0.0167339806547222
0.00905456564180467
0.00692982827761433
0.0064022813089601
0.00692982827761433
0.00905456564180467
0.0167339806547222

and f is this 11025

so I am not getting back the input

19. Jul 23, 2014

### Baluncore

Why does it have to call itself? There are many ways of writing elegant symbolic recursive code for an I/FFT.
Arithmetically, they did not run as quickly as this non-recursive algorithm.

The Sg parameter effectively reverses the direction of the trig functions.
Why move all the data if you can just negate an angle, or index a trig table backwards.
The value of Sg simply selects between Forward FFT and Inverse FFT.

So what do you think a complex exponential really is?

The code was written this way to eliminate the complex data type for testing prior to assembly language coding. You can translate it easily to complex type, Complex = Re() + j Im().

20. Jul 23, 2014

### olivermsun

How come your input only has 7 elements and your FFT has 8?

Edit: Never mind, I see why.

Last edited: Jul 23, 2014