5
$\begingroup$

This answer says that when calculating the DFT on a real valued signal, the (roughly) second half of the bins are the complex conjugates of the first half of the bins. Firstly I was curious if that is true?

If it is true, it seems like for frequency analysis purposes, you could forgo calculating the second half of the bins, which ought to be helpful for computation times and also for storage space if you want to store information in frequency domain since you could calculate the second half of the information on demand.

This also seems to be "more correct" to what people would expect when doing an FFT.

For instance, if using the equation:

$$X_k = \frac 1N \sum\limits_{n=0}^{N-1}x_ke^{-2i \pi kn/N}, \quad k\in[0,N), \quad k\in \mathbb Z$$

If you DFT a 4 sample cosine wave: $[1, 0, -1, 0]$, it gives the result: $[0, 0.5, 0, 0.5]$.

But, if you are only calculating the positive frequencies, it seems reasonable to modify the equation to be this:

$$X_k = \frac 2N \sum\limits_{n=0}^{N-1}x_ke^{-2i \pi kn/N}, \quad k\in[0,N/2), \quad k\in \mathbb Z$$

Which when applied to the 4 sample cosine wave gives us this result: $[0,1]$

It seems more correct (to me anyways!) that it shows that $0\textrm{ Hz}$ (DC) has an amplitude of 0, and that $1\textrm{ Hz}$ has an amplitude of 1. It's kind of confusing the other way, where the full amplitude of the $1\textrm{ Hz}$ wave is split between the positive and negative $1\textrm{ Hz}$ frequency.

Why is it then, that for real valued signals, we even bother calculating and reporting negative frequencies?

$\endgroup$
6
$\begingroup$

Nice question, first of all, DFT does not decompose a signal into regular sinusoids, it decompose it up into complex exponentials. Therefore, the Fourier transform of a real value signal must be conjugate symmetric (has both positive and negative frequencies), because when we are calculating inverse DFT, the real values of DFT would sum up and the imaginary parts cancel out to result a real valued signal. Your example $x=[1, 0, -1, 0] $ is a special case, since its DFT representation does not have any complex coefficients (however it is still conjugate symmetric),if you consider something like $x=[1,0,-1,1]$ you'll see its DFT would be

$$f =[ 1.0 + 0.0i,2.0 + 1.0i,-1.0 + 0.0i,2.0 - 1.0i]$$

now you need all coefficients to get the inverse DFT of the signal. And note the coefficients are not the same but are conjugate.

$\endgroup$
  • $\begingroup$ That makes a lot of sense, thank you very much! $\endgroup$ – Alan Wolfe Aug 7 '16 at 16:54
  • 2
    $\begingroup$ A DFT can be written to decompose into sinusoids (cosine + sine) instead of complex exponentials, The arithmetic is the same, it's just written differently on the chalkboard. $\endgroup$ – hotpaw2 Aug 7 '16 at 17:00
  • $\begingroup$ "Now you need all coefficients" - you don't need the last one because you know it's the complex conjugate of the second one. $\endgroup$ – immibis Aug 8 '16 at 3:07
  • 1
    $\begingroup$ @immibis: To be precise, the IDFT needs all coefficients. it cannot assume that the second half is the conjugate of the first. You only know that because your input was real. $\endgroup$ – MSalters Aug 8 '16 at 8:27
  • $\begingroup$ @immibis and @ hotpaw2, you are right (in real valued signal case), Now this could be regarded as another question, and it is like this, why we have to compute and store all DFT coefficients, when we know not all of them are necessary and if fact we can deduce one half of DFT from the other? I feel the answer is well explained by "Hilmar" in other answer of this page. And as far as I know, people do not store are FFT coefficients and just half of them is used. $\endgroup$ – MimSaad Aug 8 '16 at 12:16
10
$\begingroup$

Mainly because its easier. The FFT is a specific algorithm to calculate the DFT. However, it only works if you calculate ALL frequencies (regardless if you want them or not). It takes in N complex values and it spits out N complex values. So the FFT can be used to evaluate the your first equation but not your second.

In your example, that's a trivial difference; but for larger FFT sizes this makes a substantial difference. It's a lot faster to calculate the values at negative frequencies with FFT and simply throw them away then calculating only the values at positive frequencies with a different algorithm.

This being said, there are ways for making use of the redundancy:

  1. You can pack two real signals into a single complex, do a single complex FFT and split this into odd and even parts to get the DFTs of both input signals
  2. There is a way to do a N point real DFT using N/2 point complex FFT. It just needs one extra stage of "unwinding" the result.
$\endgroup$
  • $\begingroup$ Great answer and thanks for the bonus tips, very cool! $\endgroup$ – Alan Wolfe Aug 7 '16 at 16:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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