There is an old paper by L.R. Rabiner, "On the Use of Symmetry in FFT Computation" which describes (among other things) an optimized method to calculate the DFT of a real signal $x_n$, $n=0,\dots, N-1$ with the property that $x_{N/2+n} = -x_{n}, \ n=0,\dots, N/2-1$. The resulting transform $X=\mathrm{FFT}[x]$ only contains odd harmonics, that is $X_k=0$ when $k \,\mathrm{mod}\,2=0$, and $X_k=X_{N-k}^*$. The method requires an $N/4$ complex-valued FFT (or, equivalently, a $N/2$ real-to-complex FFT) with some pre- and post-processing.

What I wonder is if the corresponding inverse transform is described somewhere, that is obtaining the first half of $x_n$ given the first half of nonzero $X_k$. Unfortunately, Rabiner only provides an algorithm for the forward transform, and I cannot figure it out myself.


So, I've read the paper I cited more attentively, and it turned out that the author, while not having described the inverse algorithm explicitly, left enough clues in the derivation of the forward algorithm, after all. In case anyone needs it in the future, here it is.

Input: the nonzero (odd) harmonics $X_k$, $k=0,\dots,N/4-1$ (assuming here for simplicity that $N$ is divisible by 4).

  1. Build the array $Y_k$, $k=0,\dots,N/4$: $Y_0 = -2\mathrm{Im}X_0$, $Y_{N/4} = 2\mathrm{Im}X_{N/4-1}$, for the rest $Y_k = i(X_{k+1}-X_k)$.

  2. Calculate $y = \mathrm{IRFFT}(Y)$ (the standard inverse FFT to real signal, e.g. numpy.fft.irfft in Python or dft_c2r from FFTW). The resulting vector $y$ is real and has length $N/2$.

  3. $x_0 = \frac{2}{N}\sum_{k=0}^{N/4-1} \mathrm{Re}X_k$, $x_n = y_n / (4 \sin(2\pi n))$, $n=1,\dots,N/2-1$. This gives the first half of the full vector $x$.

Of course, this method is not ideal, since the division by a sine can introduce instabilities. There may exist a method to deal with that (there is one for the FFT of an (anti)symmetric signal, which requires a similar post-processing).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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