IFFT using FFT by taking conjugate of the FFT result

Question

I am doing fixed point FFT on 8bit pic microcontrller using C language, i am able to get the FFT result from the sample i have taken but i am getting wrong output when i do the IFFT for the FFT result.

The flow of program i am doing is as follows

1. Doing FFT for 8 samples say example: Real value are (1,0,0,0,0,0,0,0) and Imaginary values are (0,0,0,0,0,0,0,0)
2. The output of the FFT is (1,1,1,1,1,1,1,1) and imaginary values are (0,0,0,0,0,0,0,0)
3. Then taking the conjugate of FFT output
4. Doing FFT for the conjugated result
5. Again taking the conjugate of the second time FFT result
6. Finally dividing by 8 to get the original samples in time domain The output is Real value are (1,0,0,0,0,0,0,0) and Imaginary values are (0,-0,-0,-0,-0,-0,-0,-0);

But if i apply the same for Real values (1,2,3,4,5,6,7,8) and imaginary values (0,0,0,0,0,0,0,0) i am getting wrong result such as real value after IFFT are (1,2,4,7,4,5,4,5) and Imaginary values are(-0,-3,-1,-0,1,0,0,2)

please help me what i am doing wrong...

Answer 1

The FFT solves an interpolation problem, the IFFT the corresponding multi-point evaluation problem

The result of the FFT are coefficients of a polynomial p(z) where p(w^k)=x_k, w is the unit root associated with the dimension D of the FFT.

Denote with p_s,k(z) the polynomial formed from the subsequence of coefficients of p(z) starting in k and spaced with index distance s.

If D=2N is even, the general idea to get from the values to the coefficients is to use w^N=-1 and the decomposition

p(z) = p_2,0(z²) + z * p_2,1(z²)

in the relations

x_k = p(w^k)=p_2,0(w^2k) + w^k * p_2,1(w^k)

x_N+k = p(w^N+k) = p(-w^k)

= p_2,0(w^2k) - w^k * p_2,1(w^2k)

to reduce the big interpolation problem into two subproblems of half the size,

2*p_2,0(w^2k) = x_k + x_N+k

2*p_2,1(w^2k) = w^-k * (x_k - x_N+k)

In the next step,

• p_2,0 is reduced to p_4,0 and p_4,2, and
• p_2,1 is reduced to p_4,1 and p_4,3

etc.

---

For the sequence of 8 inputs, one gets in the first step w=(1+i)/sqrt(2) and w²=i

• x_1,0 = 2*p_2,0( 1) = x₀ + x₄
• x_1,2 = 2*p_2,0( i) = x₁ + x₅
• x_1,4 = 2*p_2,0(-1) = x₂ + x₆
• x_1,6 = 2*p_2,0(-i) = x₃ + x₇

..

• x_1,1 = 2*p_2,1( 1) = (x₀ - x₄)*1
• x_1,3 = 2*p_2,1( i) = (x₁ - x₅)*(1-i)/sqrt(2)
• x_1,5 = 2*p_2,1(-1) = (x₂ - x₆)*(-i)
• x_1,7 = 2*p_2,1(-i) = (x₃ - x₇)*(-1-i)/sqrt(2)

In the next step, one gets w=i and w²=-1

• x_2,0 = 4*p_4,0( 1) = x_1,0 + x_1,4
• x_2,4 = 4*p_4,0(-1) = x_1,2 + x_1,6

..

• x_2,2 = 4*p_4,2( 1)= (x_1,0 - x_1,4)*1
• x_2,6 = 4*p_4,2(-1)= (x_1,2 - x_1,6) * (-i)

--

• x_2,1 = 4*p_4,1( 1) = x_1,1 + x_1,5
• x_2,5 = 4*p_4,1(-1) = x_1,3 + x_1,7

..

• x_2,3 = 4*p_4,3( 1)= (x_1,1 - x_1,5)*1
• x_2,7 = 4*p_4,3(-1)= (x_1,3 - x_1,7) * (-i)

and finally the FFT coefficients X_k=x_3,k using w=-1 and w²=1

• X₀ = 8*p_8,0( 1) = x_2,0 + x_2,4
• X₄ = 8*p_8,4( 1) = (x_2,0 - x_2,4)*(-1)

--

• X₂ = 8*p_8,2( 1) = x_2,2 + x_2,6
• X₆ = 8*p_8,6( 1) = (x_2,2 - x_2,6)*(-1)

--

• X₁ = 8*p_8,1( 1) = x_2,1 + x_2,5
• X₅ = 8*p_8,5( 1) = (x_2,1 - x_2,5)*(-1)

--

• X₃ = 8*p_8,3( 1) = x_2,3 + x_2,7
• X₇ = 8*p_8,7( 1) = (x_2,3 - x_2,7)*(-1)

---

Please check that these steps are reflected in your code, especially, that the square root of 2 occurs at the necessary places. It is highly unlikely that the output of random integer inputs is again strictly integer.

Answer 2

In your description there, at no point do you take an inverse DFT.

Think about what is going on, lets say you have the the DFT result as X, taking X*X is going to give you the power spectrum, not an inverse DFT. Then preforming an DFT on this will not give you a time domain, it will give you nonsense.

you need to find the inverse DFT function in the library you are using.