2
$\begingroup$

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.

  • 0
    @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.2012-09-18

1 Answers 1

2

In each part of step 2, you're applying a transformation of the form

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

The inverse transformation is

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

So you can just perform all the inverse operations in reverse order, and then undo the reordering. Of course you need to take into account the optimizations you made for real-valued data; but since mathematically all the operations are invertible, you can always apply the inverse operation to your optimized representation.

  • 0
    Yes, it was kinda obvious. :-) (By the way, the transformation is on four data points to nicely handle the restricted spectrum.) To do the reordering in the end is a minor drawback, but better than nothing. I'll just wait a little longer to see if a "forward" approach comes up. If not, I'll accept your answer.2012-09-19