Why calculate negative frequencies of DFT?

Question

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?

Answer 1

DFT does not decompose a signal into regular sinusoids, it decompose it up into complex exponentials.

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.

In case of FFT, it just produces all bins, unless the signal is real-valued where you can use Sorensen's method, but still the DFT conjugate applies there.

Answer 2

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.

Answer 3

The real world tends to be real-valued. There may be counter examples, but a signal captured by a camera, an antenna or a microphone most of the time seems to be best described as one or more waveforms of 1d/2d/3d real-valued voltages or equivalent that could be sampled to produce discrete streams.

As part of processing, it could make sense to describe them as complex. Such as an I/Q complex baseband description of a radio signal or a complex FFT-filterbank representation of an audio signal.

As physical input is often «real», the «imaginary part = 0») is often taken for granted and optimized FFTs that assume this property is used and the complex representation/storage/bandwidth is limited to the «non-trivial terms», assuming that they can be recreated if needed as a sort of contract.

Now, ask how many ways there are to pack the N/2+1 coefficients (of which the first and last have 0 imaginary part) of a length N real FFT into discrete numbers/arrays on a computer, often sparsely documented…