# Real discrete Fourier transform

I am trying to understand the real DFT and the DFT and why the distinction exists.

From what I know so far the DFT uses $e^{i2\pi kn/N}$ for basis vectors and gives the representation $$x[n]=\sum_{k=0}^{N-1}X[k]e^{i2\pi kn/N}$$ The sum is written from $k=0$ to $N-1$ for historical reasons I think instead of writing it in a way analogous to the Fourier series with the sum going from $k=-N/2$ to $N/2-1$: $$x[n]=\sum_{k=-N/2}^{N/2-1}X[k]e^{i2\pi kn/N}$$ This relying on a peculiar anomoly of the DFT where high frequencies are the same as negative frequencies: $e^{i2\pi kn/N}=e^{i2\pi (k-N)n/N}$.

Continuing the analogy with Fourier Series the real DFT gives the representation $$x[n]=\sum_{k=0}^{N/2}\left(X_R[k]\cos\left(\frac{2\pi kn}{N}\right)-X_I[k]\sin\left(\frac{2\pi kn}{N}\right)\right)$$ This can be viewed as pairing $e^{i2\pi kn/N}$ with $e^{-i2\pi kn/N}$ in the DFT representation where the sum ranges from $k=-N/2$ to $N/2-1$. This is very much like the pairing $c_n e^{in\theta}+c_{-n}e^{-in\theta}=a_n \cos n\theta + b_n \sin n\theta$ which connects the two representations of a Fourier Series:$$\sum_{-\infty}^\infty c_n e^{in\theta}= \frac{a_0}{2} + \sum_1^{\infty}(a_n \cos n\theta + b_n \sin n\theta)$$

My question then is why is the DFT so much more prevalent than the real DFT? One would expect that since the real DFT is using real valued sines and cosines as the basis and is thus representing the geometric picture better that people would like it more. I can see why the DFT and the continuous Fourier Transform would be preferred in a theoretical sense as the algebra of exponentials is simpler. But ignoring the simpler algebra, from a practical computational applied viewpoint why would the DFT be more useful? Why would representing your signal with complex exponentials be more useful in various physics, speech, image, etc. applications than decomposing your signal into sines and cosines. Also if there is anything subtle I'm missing in my above exposition I would like to know: I'm puzzled that the DFT is seen as more connected to the continuous Fourier Transform than to the Fourier Series.

• The real discrete Fourier transform is important for the reason that applying the usual DFT to a real sequence results in some redundancy, in that for a length $N$ real sequence $x_0,x_1,\dots,x_{N-1}$ with corresponding transform $X_0,X_1,\dots,X_{N-1}$, the sequence $X_{N-1},X_{N-2},\cdots,X_{N/2+1}$ is precisely the complex conjugate of the sequence $X_1,X_2,\dots,X_{N/2-1}$. It stands to reason, then, that one only needs the entries corresponding to positive frequencies of the transform. One will also encounter the so-called Hartley transform in this context. Both approaches are used.
– user276
Feb 7 '12 at 10:20
• BTW: I highly recommend reading these two papers on both the real Fourier transform and the Hartley transform; they do a good job of explaining the interest in these methods apart from the DFT itself.
– user276
Feb 7 '12 at 23:00
• Is it true that the matrix of the RDFT and the matrix of the DFT are related by a change of basis? And that the change of basis is really a reflection parallelling how Fourier series can be represented in two ways with coefficients related by $c_n e^{in\theta}+c_{-n}e^{-in\theta}=a_n \cos n\theta + b_n \sin n\theta$. And the key point in the context of the DFT is that the upper frequencies should be thought of as the negative frequencies so that its possible to do the pairing $c_n e^{in\theta}+c_{-n}e^{-in\theta}$ to get sines and cosines like in the fourier series, giving the RDFT Feb 10 '12 at 1:32
• One of the chapters in Van Loan addresses your question in detail. That presumes some skill with the manipulation of Kronecker products.
– user276
Feb 10 '12 at 1:55
• At the very least you should have less questions than you now have.
– user276
Feb 10 '12 at 9:03

The advantage of the complex DFT or complex Fourier transform or complex Fourier series is that linear systems have the nice property that the response to $A\exp(j\omega t)$ is $H(\omega)A\exp(j\omega t)$. (Here $A$ can be a complex constant). So the output is just a scalar multiple of the input. More importantly, if we have a representation of the input as a weighted sum of complex exponentials, the output is just another weighted sum of the same exponentials. Different weights, but same set of exponentials. Furthermore, each new weight is obtained by multiplying the old weight by an appropriate number.
Of course, no physical system has complex-values signals going in and coming out; at least, not as of today though one can always hope for better things in the future. In the mean time, we take real parts of the complex signals, or get the response to $\cos(\omega t)$ or $\sin(\omega t)$ via linearity and superposition and liberal use of \begin{align*} \cos(\omega t) &= \frac{\exp(j\omega t) + \exp(-j\omega t)}{2}\\ \sin(\omega t) &= \frac{\exp(j\omega t) - \exp(-j\omega t)}{2j} \end{align*}
In contrast, the response to $\cos(\omega t)$ is of the form $B(\omega)\cos(\omega t) + C(\omega)\sin(\omega t)$. So, while linearity and superposition etc all work, the output might well need the use of different basis functions than the input does. Very closely related, of course, but still possibly different and maybe more basis functions might be needed. For example, input $\cos(\omega t)$ is represented by one basis function, output $B(\omega)\cos(\omega t) + C(\omega)\sin(\omega t)$ by two basis functions. It can be argued that complex functions require twice as much work as real functions and so any savings are purely imaginary (pun intended), but complex representations allow uniform treatment while sin/cos representations do not. Quick! Given the response to $\cos(\omega t)$ is $B(\omega)\cos(\omega t) + C(\omega)\sin(\omega t)$, what is the response to $\sin(\omega t)$? You have to work at it a bit, you may need to invoke formulas such as $$\cos (\alpha + \beta) = \cos(\alpha)\cos(\beta) - \sin(\alpha)\sin(\beta)$$ and so on. With complex exponentials, life is a lot easier.