Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
"... 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
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
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. –  WimC Sep 19 '12 at 10:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.