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.
Answer
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.
But, as in real life, your mileage may vary, and if you feel that sin/cos representations are the way to go and complex exponentials should be eschewed, you are free to follow your heart. If you have difficulty communicating your ideas to colleagues, bosses, clients or consultants, that will be their loss, not yours.
No comments:
Post a Comment