1
$\begingroup$

In one of my projects I need to do a large number of real FFTs, so I'm looking for the most efficient algorithm. Is it possible to pre/process the N DCT in N operations to produce the real FFT - exactly opposite to the N FFT case in Fast Cosine Transform via FFT? If so, would this be, as I expect, several times as fast as the real FFT given the use of real numbers rather than complex?

$\endgroup$
1
$\begingroup$

If you have an efficient FFT routine (and there are many out there) the best and easiest approach to compute DFTs of real-valued data is to combine two real-valued signals into one complex valued signal and compute the DFT of the complex-valued signal:

$$x[n]=x_1[n]+jx_2[n]\tag{1}$$

From the DFT $X[k]$ of $(1)$ you can obtain the DFTs of the two individual signals $x_1[n]$ and $x_2[n]$ as follows:

$$X_1[k]=\frac12\left(X[k]+X^*[N-k]\right)\\ X_2[k]=\frac{1}{2j}\left(X[k]-X^*[N-k]\right)\tag{2}$$

In this way you've computed the length $N$ DFTs of two real-valued signals by one length $N$ DFT of a complex-valued signal.

In a similar manner, you can compute the length $N$ DFT of a real-valued signal by computing the length $N/2$ DFT of a complex-valued signal. This is explained in detail in this answer.

$\endgroup$

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.