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 X
with G
representing the FFT of a same sized real signal g
.
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.
EDIT
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.
X
in the Matlab script. (My N might indeed be 64, but it's now edited, thanks for pointing out...) $\endgroup$