Real DFT
N point real DFT with an N/2 point complex DFT
If the input to the FFT is all real, then it's possible to halve the calculation size, following this derivation:
\[X_k = \sum_{n=0}^{N-1} x_{n} e^{\frac{-i2 \pi nk}{N}}\] \[X_k = \sum_{n=0}^{N/2-1} x_{2n} e^{\frac{-i2 \pi nk}{N/2}} + e^{\frac{-i 2 \pi k}{N}} \sum_0^{N/2-1} x_{2n+1} e^{\frac{-i 2 \pi n k}{N/2}} \] \[X_k = \sum_{n=0}^{N/2-1} x_{2n} e^{\frac{-i2 \pi nk}{N/2}} - i e^{\frac{-i 2 \pi k}{N}} \sum_0^{N/2-1} i x_{2n+1} e^{\frac{-i 2 \pi n k}{N/2}} \] \[X_k = E_k - ie^{\frac{-i 2 \pi k}{N}} O_k \]Define a new series composed of the even input as real components and odd inputs as imaginary components, for a size N/2 complex DFT:
\[Y_k = \sum_{n=0}^{N/2-1} (x_{2n} + i x_{2n+1}) e^{\frac{-i2 \pi nk}{N/2}} \] \[Y_k = E_k + O_k \]We can use the symmetry properties of purely real and imaginary inputs to separate the outputs from the real and imaginary components
\[ E_k = E^*_{N/2-k} \] \[ O_k = -O^*_{N/2-k} \]Taking the sums and differences of corresponding complex DFT outputs gives the real and imaginary components of the odd and even series
\[ Y_k + Y_{N/2-k} = E_k + E_{N/2-k} + O_k + O_{N/2-k} \] \[ Y_k + Y_{N/2-k} = E_k + E^*_k + O_k - O^*_k \] \[ Y_k + Y_{N/2-k} = 2Re(E_k) + 2iIm(O_k) \] \[ Y_k - Y_{N/2-k} = E_k - E_{N/2-k} + O_k - O_{N/2-k} \] \[ Y_k - Y_{N/2-k} = E_k - E^*_k + O_k + O^*_k \] \[ Y_k - Y_{N/2-k} = 2iIm(E_k) + 2Re(O_k) \]The odd and even series can be calculated in terms of the complex DFT output
\[ E_k = \frac{1}{2} Re(Y_k + Y_{N/2-k}) + \frac{1}{2} i Im(Y_k - Y_{N/2-k}) \] \[ O_k = \frac{1}{2} Re(Y_k - Y_{N/2-k}) + \frac{1}{2} i Im(Y_k + Y_{N/2-k}) \]With the even and odd series calculated, the actual outputs can be calculated.
\[ X_k = E_k - i e^{-i2 \pi k/N} O_k \] \[ X_{N/2-k} = E^*_k - i e^{i2 \pi k/N} O^*_k \]So the algorithm for this involves just performing the complex DFT on the input assuming it was N/2 complex numbers, then using symmetry to calculate the first half of the coefficients for the real DFT.
References
- Uses javascript SyntaxHighlighter for syntax highlighting.
- Uses javascript MathJax for LateX rendering.
To the extent possible under law,
Craig Hughes
has waived all copyright and related or neighboring rights to
the text and source code in this example/tutorial.