# In-place inverse of DFT?

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:

1. Reorder input data
2. 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.

-
"... and $\hat{x}_0$ and $\hat{x}_{2N−1}$ are real numbers." How come? You store half the numbers, but the numbers are complex, so you have not attained any form of compression. – Rod Carvalho Sep 18 '12 at 15:34
@RodCarvalho: no indeed, the size is the same. Only for the full complex valued spectrum it would be twice as much. Anyway, the real point is an in-place procedure. – WimC Sep 18 '12 at 16:45

$$\pmatrix{x_k\\x_{k+d}}\to\pmatrix{1&\omega\\1&-\omega}\pmatrix{x_k\\x_{k+d}}\;.$$
$$\pmatrix{x_k\\x_{k+d}}\to\frac12\pmatrix{1&1\\\overline\omega&-\overline\omega}\pmatrix{x_k\\x_{k+d}}\;.$$