There are two related questions with good answers; for calculating the forward FFT in N/2 values, and calculating inverse FFT from N real values, now I'm in search for the missing link of packing the N/2+1 element complex signal X back to the N/2 element complex signal that it was derived in the first place for memory and arithmetic efficient inverse FFT.
Having calculated N/2+1 valued complex FFT from N real values (code from the first link):
x = [ 1 2 3 4 5 6 7 8 ]; n = 8; n2 = 4; Z = fft(x(1:2:end) + i * x(2:2:end); Ze = .5*( Z + conj([Z(1),Z(n2:-1:2)])); Zo = -.5*j*( Z - conj([Z(1),Z(n2:-1:2)])); X = [Ze,Ze(1)] + exp(-j*2*pi/n*(0:n2)).*[Zo,Zo(1)];
I have actually packed the real valued element
X(n2+1) to imaginary part of
X(1), saving some memory. Then I've point wise multiplied
G representing the FFT of a same sized real signal
In order to finish the (circular) convolution of conv(x, g), I'd need to calculate the packed N/2 sized complex signal
Z from (X.*G) for IFFT.
The first coefficient can be reverted as
Z(1) = real(X(1)+X(n2+1))/2 + i*(imag(X(1)-X(n2+1)))/2;
As the other values
X(2:n2-1) are originally produced from a bufferfly operation of
x(k) +- exp(j*k/N) * x(n2-n), I would hope that all the elements would be recoverable. The question is how.
I need to recheck the formulas, but since for a pair A=Z(k+1), B=Z(n2+1-k):
[ 1-s 1+s c c ] [Real(A)] [Real(A') Imag(A') Real(B') Imag(B')] = [ 1+s 1-s -c -c ]*[Imag(A)] [ -c c 1-s -1-s] [Real(B)] [ -c c -1-s 1-s] [Imag(B)]
with invertible matrix, there really is a solution.