IFFT for complex N Signal - output: real Signal of length 2N

Question

In their book "Digital Signal Processing" Proakis & Manolakis describe a Method for computing the FFT of a real Signal of length 2N using a FFT of length N. This is basically done by splitting the signal in its odd and even parts. The even parts are the input for the real part of the FFT and the odd parts are the imaginary. Both signals are extracted of the FFTs output using a technique that is sometimes known as "Two for the price of one" http://www.engineeringproductivitytools.com/stuff/T0001/PT10.HTM

After that, the final stage of a decimation in time FFT is used to compute the signal in frequency domain. I've implemented and I think I also understood how this method works. However, I got stuck doing the IFFT in a similar way.

I have a frequency domain signal with the length of 2N. As it is the frequency domain representation of a real signal, its left and right side are symmetrical. I now want to use the first half of the signal, and use an IFFT with length N to compute the time domain representation of that signal. I spent all last night trying to figure out how this works and trying to implement it, however I never ended up with the numbers I should. The page I mentioned is the only source I found that gives a vague explanation how something similar should work, however that didn't help much to understand it.

What do I need to do in order to use a IFFT of length N in order to transform a complex and symmetric frequency domain signal of length 2N into its real time domain representation of length 2N in one pass?

Answer 1

The FFT of a real signal has complex-conjugate symmetry. If you have an frequency domain vector that is real symmetric with all zeros for the imaginary components, then what you might be looking for is a form of IDCT of length N, since the real signal will have only cosine composition with N degrees of freedom.

ADDED:

If you have a working forward real-data FFT of length 2N, you should be able to take the computational steps in reverse order, reverse each step, comparing the data after each step with the forward version, to find your bug. (e.g. if you used an FFT of length N on the forward process, then, when doing the process in reverse, the IFFT of length N should have the same inputs and outputs as the outputs and inputs to the original FFT (minus numerical rounding effects). If not, there's your bug.)

Answer 2

In case someone has the same question as me, here is my unoptimized source code in C. Hopefully I will sometimes find time to add some explanation. (code uses 2*n of the signal as real and 2*n+1 as imaginary part) Note that the array that keeps the complex spectrum needs to be of length realInputSignal + 2 in order to keep the DC offset. However it is possible to store the last real value in the place of the first complex value (as it is not used) and you don't have to add the 2 more samples to the array. However, your DFT has to also be aware of that.

N = lData/2;

double X1R = 0.5*(outData[0] + outData[N*2]);
double X1I = 0.0;
double X2Ra = 0.5*(outData[0] - outData[N*2]);
double X2Ib =0.0;//

double wr = cos((double)0 * M_PI / (double)N);
double wi = -sin((double)0 * M_PI / (double)N);
double X2R = (X2Ra*wr + X2Ib*wi)/(wr*wr + wi*wi);
double X2I = (X2Ib*wr - X2Ra*wi)/(wr*wr + wi*wi);
outData2[0*2] = X1R - X2I;
outData2[0*2+1] = X1I + X2R;


for (int i=1; i<N; i++){

    double X1R = 0.5*(outData[i*2] + outData[N*2-2*i]);
    double X1I = 0.5*(outData[i*2+1] - outData[N*2-2*i+1]);
    double X2Ra = 0.5*(outData[i*2] - outData[N*2-2*i]);
    double X2Ib = 0.5*(outData[i*2+1] + outData[N*2-2*i+1]);
    double wr = cos((double)i * M_PI / (double)N);
    double wi = -sin((double)i * M_PI / (double)N);
    double X2R = (X2Ra*wr + X2Ib*wi)/(wr*wr + wi*wi);
    double X2I = (X2Ib*wr - X2Ra*wi)/(wr*wr + wi*wi);
    outData2[i*2] = X1R - X2I;
    outData2[i*2+1] = X1I + X2R;

}

ifft(outData2);