2
$\begingroup$

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:

    enter image description here

    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?

$\endgroup$
  • 1
    $\begingroup$ You should split this up into separate questions, as right now the answers to all of them could fill a book chapter (as you have observed above) $\endgroup$ – jonsca Oct 13 '13 at 22:21
  • $\begingroup$ I think the general question or concern is to make sense of what these negative frequencies are and why we don't compute coefficient for harmonics above the Nyquist frequency. I realize these are big questions, but I have covered a lot of litterature and either the books are very high level in mathematics or low level and do not explain these points. I need pointers more than anything. $\endgroup$ – mast4as Oct 13 '13 at 22:33
  • 1
    $\begingroup$ I don't take issue with your questions at all, I think they are very good. Since Stack Exchange works on a "question/answer" format, they will likely get better and more thorough answers if they are split up. That's really the only issue that I can see with them. $\endgroup$ – jonsca Oct 13 '13 at 22:36
  • $\begingroup$ I totally agree and understand. Let me think about it and see how I can split them in several questions. I just don't want to overflow dsp.SE with too many questions at once. And now I am afraid the questions will be redundant with this post. $\endgroup$ – mast4as Oct 13 '13 at 22:39
  • $\begingroup$ Some of the questions raised here are answered in the responses to Why is the FFT Mirrored?. $\endgroup$ – Dilip Sarwate Dec 13 '13 at 0:29
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you this is of course helpful. I think I get the "real" signal part of the DFT, and I understand what you say, however I would like to understand better what these negative frequencies are. I know Fourier transform is not simple, but it's strange because there seems to be a line when it comes to theory above which it starts to get hard to get rational and logical explanations. I have been thrown out the identity of cosine and sine using exponential as a justification for neg. frequencies, however no one as yet been able to give full proof. Frustrating. $\endgroup$ – mast4as Oct 13 '13 at 22:17
  • $\begingroup$ Euler gave a proof about 250 years ago. Check en.m.wikipedia.org/wiki/Euler's_identity for many books and references on the topic. $\endgroup$ – hotpaw2 Oct 13 '13 at 23:21
  • $\begingroup$ I know about this proof. As I said I suspect it is involved in understanding negative frequencies. It's okay, I will find out thx. I was asking for an explanatin on neg. freq. not the Euler identity's proof. $\endgroup$ – mast4as Oct 14 '13 at 7:28
  • $\begingroup$ So after doing some research there is some explanations around as to why the negative frequencies exist 1) because indeed they are in the Euler's formulation 2) they cancel each other out in the imaginary plane leaving with only a real cosine or real sine. I read another reason which seems more complicated (complex numbers imply two degrees of freedom, I will try to find more info on this. As for WHY we use frequencies ABOVE the Nyquist frequency, there is almost nothing about that. Hopefully I start to put the pieces back together. It has something to do with aliasing and folding frequencies. $\endgroup$ – mast4as Oct 14 '13 at 23:09
  • $\begingroup$ The fact that there seems to be no good reference (not reference at all) about this is really strange to say the least. $\endgroup$ – mast4as Oct 14 '13 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.