I'm trying to understand (by implementing) the Cooley Tukey algorithm for an array $[x_0, \dotsc, x_{2^N-1}]$ of real valued data. Since the input data is real valued, the spectrum will have conjugate symmetry: $\hat{x}_{2^N-k} = \hat{x}_k^{\ast}$. Therefore it suffices to only store the first $2^{N-1}+1$ terms and moreover $\hat{x}_0$ and $\hat{x}_{2^{N-1}}$ are real numbers. The Cooley Tukey algorithm can be adapted in such a way that it does not need more space than that to compute a dft. The steps are:
- Reorder input data
- Combine data recursively
However, I don't see how the inverse dft can be done in a similar manner. That is, given the first half of a conjugate symmetric spectrum, is there a way to recover the original real data that does not need additional space?
I have the nagging feeling that I'm missing something quite obvious. However, I did also not find any reference for it. Any pointers appreciated!
Edit: The procedure indicated by Joriki works. However, the process of in-place reordering as the final step turns out to be a bit tedious to do fast. I now found an answer to my own question: It is possible to do an inverse transform by first reordering the data and then applying a recursion. Here's how.
Let $n = 2^N$ be the input size for the forward transform (on a sequence of $n$ real numbers) and $\zeta_n = e^{2\pi i/n}$. Let $S$ be the inverse DFT defined on half of a symmetric spectrum $ S(x_0, z_1, \dots, z_{n/2-1}, x_{n/2}; m) $ where $x$ indicates a real number and $z$ a complex number and $m$ the argument. Let $F$ be the usual inverse DFT on a full complex spectrum. Then the central identity for the recursion is:
$ S(x_0, z_1, \dots, z_{n/2-1}, x_{n/2};m) = S(x_0, z_2, \dotsc, z_{n/2-2}, x_{n/2}; m) + 2\mathrm{Re}\left(\zeta_n^m F(z_1, z_5, \dotsc, \overline{z_7}, \overline{z_3}; m)\right). $
The first summand uses all entries with an even index, the second term those with an odd index, rearranged and conjugated in a certain way. (First put $z_1$ in front, then $z_3$ conjugated at the back, $z_5$ at the front, $z_7$ conjugated at the back, and so on.) Now both summands can be computed in-place: $F$ with the usual Cooley-Tukey procedure and $S$ by recursion.