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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
