General question about DFT

Question

I am learning Fourier analysis and without any teacher, just trying to read books on my own. I think I have made some decent progress but they are a couple of points which are still very unclear to me and that I can't find explained in any of the books I have.

One of the sources that I found in this document, which is great because it teaches DFT without really using complex numbers. I shall say that I understand complex numbers and I am aware of Euler's Formula.

So what they say in this PDF/document is that in fact, in the simple case you can create a DFT by just using $N/2$ coefficients. I thought the choice of $N/2$ was related to the Nyquist frequency. If the signal contains $N$ samples then the Nyquist sampling theorem says that the signal can't contain a wave whose frequency is higher than half of the sampling frequency (hence the $N/2$ harmonics in the DFT).

So to me, explained that way everything made a lot of sense and in the simplest case you just needed to do something like this:

\begin{align} a[k] &= \sum_{x = 0}^{N-1} s[x] \cos\left(2 \pi k {1 \over N } x\right), \quad \text{ for } k = \left\{ 1, 2, ..., \frac N2\right\},\\ b[k] &= \sum_{x = 0}^{N-1} s[x] \sin\left(2 \pi k {1 \over N } x\right), \quad \text{ for } k = \left\{ 1, 2, ..., \frac N2\right\}. \end{align}

So this seemed simple. Now it says that when $k = 0$ and when $k = N/2$ then we need to divide $a$ and $b$ by $N$ or multiply them by $2/N$ otherwise. I understand why when $k = 0$, because it's the DC offset, but didn't really understand why you had to do the same thing when $k = N/2$ until I read this post

• QUESTION 1: It seems to indicate that when you use the exponential form of the DFT then when $k = N/2$ then you have $\exp(\pi)$ which is equal to 1. Then it seems that in that situation the coefficient $a[N/2]$ has a particular meaning by I don't know which one?

  Now this is where I am lost. In the "complete" equation for the DFT you don't compute $N/2$ coefficients by $N$ coefficients. That means that has soon as $k > N/2$ then the frequency of the harmonics is greater than the Nyquist frequency. I have illustrated this with the following image:

  

  We have $N=8$ samples, thus the fundamental frequency is $\frac 18$ and we have harmonics: $1\cdot \frac 18, \ 2\cdot \frac 18, \ 3\cdot \frac 18, \ 4\cdot \frac 18$. However as soon as go above that then the harmonics go beyond the Nyquist frequency.

• QUESTION 2: why do we test the signal with harmonics whose frequency go beyond the Nyquist frequency?

  Finally, and I think this is actually related to question 2, I keep reading about positive and negative frequencies, but I just can make sense of this at all? This is my question 3.

• QUESTION 3: could you please briefly explained if that's possible why we do speak and need positive and negative frequencies? Why do we need to care for negative frequencies?

Answer 1

The need for all these coefficients may not be obvious if you are looking at only real number input to the DFT.

But a complex vector input of length N will have twice the degrees of freedom compared to a strictly real input of that length. The DFT, as an invertible linear transform therefore must therefore retain that same number of degrees of freedom, which for complex input ends up in the relationship between the positive and "negative" frequencies, or upper half of the transform, to produce complex exponential frequency results, instead of just strictly real cosine and sine functions.

For strictly real valued input, you don't really need to "care" about the other half, as it is duplicated information in the form of a complex conjugate (where the imaginary components of positive and "negative" frequency bins all cancel out to zero). Thus the "mirroring" reduces the number of degrees of freedom to match that of the strictly real-valued input. But one might still use the other half for computational purposes, as it makes the matrix math more regular and symmetric, and thus optimizable in the form of some FFT algorithms.

Thus the negative frequency coefficients don't need to be computed because they are redundant (unless the input is complex and not strictly real valued). In that case, the frequency coefficients above N/2 don't need to be computed because they are identical to the negative coefficients that don't need to be computed