Negative frequencies in DFT output

[bkelly]

I am a software guy, not a math major. I strive to understand various articles about the Fourier transform, but the math is beyond me. Please try to explain in layman’s terms.
Reading about the DFT (Discrete Fourier Transform) and specifically the product from www.fftw.org, the descriptions indicate that the upper half of the output array contains the negative frequencies. This comes from the concept of graphing the amplitude for the real and imaginary part on an XY graph. Negative frequencies are example of routing the vector in the opposite direction.
Other than the phase difference, why might clockwise and counter-clockwise produce different values? When I plot these values for a spectrum display, what might be lost or gained by incorporating negative frequencies in the display? In the display I am creating, should it have an option to include or exclude the negative frequencies?
Thank you for your time and patience.

 

[Cubist]

When I plot these values for a spectrum display, what might be lost or gained by incorporating negative frequencies in the display? In the display I am creating, should it have an option to include or exclude the negative frequencies?

Are your inputs to the DFT real values (ie they are not complex numbers)? If so then the upper half of the DFT would always be the complex conjugate of the lower half, and therefore it wouldn't carry any useful information. Also, in this situation, you should consider using routines optimised for real inputs.

 

[bkelly]

Hello Cubist,
My appologies for not replying sooner. MS outlook is not getting my email from my site host service and I keep forgetting to go on line to get it.
The FFTW utilities do have the the ability to optimize the output for specific categories of inputs, to include a real only input. The call it a plan which must be created before running a DFT.

As I have progressed through this project and viewed multiple on line references, none of them take that time to explain exactly what is in the output. They all presume that the user has the mathematical chops to understand and figure it out. I cannot make this very short, but maybe, and if I am correct, this may help others like me, a programmer that must use the utility in a project but cannot spend a year learning the concepts of a DFT. Here is my understanding of the outputs.

From at least one of the many on line references visited is the concept that the positive frequency components are found in the output array from: out[ 0 ] to out[ N / 2 ].
The array index values range from 0 to N/ 2, not N / 2 - 1.
Here is a specific reference: http://www.dspguide.com/ch8/3.htm
And a quote from the first paragraph:
Notice that 128 points in the time domain corresponds to 65 points in each of the frequency domain signals, with the frequency indexes running from 0 to 64. That is, N points in the time domain corresponds to N/2 + 1 points in the frequency domain (not N/2 points). Forgetting about this extra point is a common bug in DFT programs.

With that in mind, I wanted a visual representation and created the below mirrored table. Rather than 128 points and 64 rows, only 8 are used to demonstrate the concept. The middle column is left blank to emphasize the split between the left and right half of the table.

After creating the table, I cannot get the cursor beneath it so this text belongs below the table.

Note that moving one item from the negative side to the positive side makes the negative side two elements smaller. If I understand this correctly, the negative frequencies components do not contain a magnitude for the infinite wave length component or for the wavelength of length 8/1.
The problem is that of all the references that present and discuss the Fourier transforms, and the resultant DFT (Discrete Fourier Transform), none of the spend any significant space/time describing what is in the output of a DFT. Or if they do, it is buried sufficiently deep within the discussion that I am unable to detect it.
The table is, hopefully, a succinct presentation of what is in the output.
Here is the question posed: Is this concept correct? Is the table accurate?

Positive Array Index	Positive wavelength	blank	Negative wavelength	Negative Array Index
0	8/0 infinite
1	8/1
2	8/2		8/2	7
3	8/3		8/3	6
4	8/4		8/4	5

 

[Cubist]

Here is the question posed: Is this concept correct? Is the table accurate?

I think you made a mistake, see an adjusted table below.

This table holds for even N:-

Positive Array Index	Positive wavelength	blank	Negative wavelength	Negative Array Index
0	8/0 infinite
1	8/1		8/1	7
2	8/2		8/2	6
3	8/3		8/3	5
4	8/4

The DC component of the input signal is given at index 0.

The highest frequency is at index 4 and it is always real for real input signals. This is because it can't have any phase information since it corresponds to a signal that looks like [1 -1 1 -1 1 -1 1 -1]. NOTE it can be 180° out which would look like [-1 1 -1 1 -1 1 -1 1] and would mean that the value obtained at index 4 would be -ve rather than +ve.

The other rows can be complex numbers, giving phase information, and occur in conjugate pairs for real inputs.

 

[Cubist]

Some extra notes:

Always refer to the documentation of the actual DFT routines that you plan to use since their API might be slightly different to the usual output format. (Or just test it with different inputs.)

I personally view the "negative frequency" outputs as a simple consequence of how the Fourier transform is defined and performed, and I don't try to attach any kind of mystical meaning to them! There's no such thing as a negative frequency in real life. (But it could be the case that I'm simply not clever enough to fully understand!)

I still recommend the routines optimised for real inputs, because their API does not expose these "negative frequencies" perhaps making them simpler to use? (as well as having a slightly faster runtime I believe).

It looks like the fftw library gives advice for the choice of N with dramatic speedup available for some numbers. Other libraries provide separate FFT routines which only accept certain N values but are much faster/ more accurate.

Be aware of aliasing, and the use of window functions to help reduce the effect.

 

[Phil Karn]

When I teach the absolute basics of the FFT to, say, a bunch of radio hams I start by saying that we're used to thinking of signals as oscillations. And they are. But they're really rotations; an sinusoidal oscillation is just what you get when you look at a circular rotation from one side. I'll demonstrate this by holding up a bicycle wheel with a screwdriver attached to the periphery. You can tell how fast the wheel is turning but you can't tell which way. But if you look at the wheel from two separate directions (except exactly 180 degrees apart), now you can tell. That's analogous to how sampling a complex signal lets you tell whether its frequency is negative or positive. At this point I invoke the lame old joke about two blind men arguing about the shape of an elephant. If they're standing 90 degrees apart around the elephant as it spins on a turntable, they'll disagree on when the elephant gets wide, then narrow, then wide again when in fact the elephant is just standing still on a rotating platfom. Same with the real and imaginary samples of a complex sinusoid of constant power.

A real signal can be decomposed into two complex signals of the same amplitude and frequency rotating in opposite directions (i.e., one positive, one negative) so that their imaginary parts cancel at all times. This is why the negative spectrum of a real-only signal is the complex conjugate of the positive spectrum. Any other spectrum must have a non-zero imaginary component in the time domain.

When the FFT is used to analyze a piece of the radio spectrum, it is often shifted down in frequency (by multiplication by a complex exponential) so that zero frequency in the FFT output corresponds to some specified radio frequency at the input, fc. Input radio frequencies below fc come out as negative and those above fc come out positive. Working with complex signals in this way actually simplifies the math enormously.

 

[Cubist]

I was taught the FFT at uni 30+ years ago without any mention of negative frequency.

The interpretation/ visualisation of wheels spinning in different directions does seem very interesting to me (see this Wikipedia page). I'm quite a visual thinker and I can therefore appreciate that it might help some people while they learn the Fourier transform etc. But I have a concern that this way of teaching might lead some people to think that spinning wheels actually exist (in some ethereal, other dimension, sense) whenever a sin wave is present, and that negative frequencies might exist in the real world (like someday a radio could be built that can tune to -100MHz ). So I feel that this kind of material should be taught alongside a strong emphasis that it's just a visualisation to help with some of the mathematics (and complex numbers are just a part of the mathematical toolbox, and don't directly point to any "extra" physical phenomena in this particular use)

 

[Phil Karn]

I was taught the FFT at uni 30+ years ago without any mention of negative frequency.

Really? How you can talk about the complex FFT without talking about negative frequency? Real input yes, but not complex (and real is just a special case of complex). It's been 43 years (!!) since Cornell but I remember this pretty well. Lab-sized minicomputers that could run the FFT in real time were just becoming practical.

But I have a concern that this way of teaching might lead some people to think that spinning wheels actually exist (in some ethereal, other dimension, sense) whenever a sin wave is present, and that negative frequencies might exist in the real world (like someday a radio could be built that can tune to -100MHz ). So I feel that this kind of material should be taught alongside a strong emphasis that it's just a visualisation to help with some of the mathematics (and complex numbers are just a part of the mathematical toolbox, and don't directly point to any "extra" physical phenomena in this particular use)

Point taken, but that's exactly what I do when I generate a signal in my SDR. I start with a complex oscillator, which is definitely rotating in the mathematical sense. After I modulate and upconvert it to RF I no longer need the complex representation because my signal spectrum no longer spans DC as it did at baseband. So without losing information I can throw away one of the complex components and send the other to the antenna.

You can certainly build a radio that takes a negative frequency input; it just needs two RF inputs. Hmm. What if you have vertically and horizontally polarized antennas and use them for the real and imaginary components? Then you have a complex signal whose electric field is literally rotating in space. This is how circular polarization works. You can think of a circularly polarized antenna as only accepting, e.g. positive frequencies and rejecting negative ones.

I stress the complex representation of signals in my teaching because, contrary to the word, it vastly simplifies things. Everything becomes so much easier to visualize and understand. Expressions like "spinning a signal down" (downconverting frequency by complex mixing) become very intuitive.

 

[Cubist]

Really? How you can talk about the complex FFT without talking about negative frequency? Real input yes, but not complex

Yes, I've checked my notes and I covered the topic with complex inputs and there's no mention of negative freq. But my notes were handwritten from a blackboard (or overhead projector) so I guess it's possible that I fell asleep in those lectures at some point and missed it. I did drink a lot of beer back then ?. But this Wikipedia page also talks about the complex FFT without mentioning negative frequency. Also this page for the slower DFT.

Point taken, but that's exactly what I do when...

...if I read your post correctly you seem to have switched from talking about a single signal to two signals. If two signals x and y are x=cos(wt), y=sin(wt) then indeed this can be thought of as a point in the xy plane that rotates as t increases. However I was just trying to make the point that if you have a SINGLE signal, say x=sin(wt), then I think it's questionable to consider anything to be rotating since it's purely an oscillation.

I'm not an immediate fan of describing the frequency as negative if we have two signals x₂=cos(-wt), y₂=sin(-wt). To me, this locus has a positive frequency which is the number of times the locus returns to the same point per unit time. The direction of rotation is simply different. I guess if enough people are taught and accept this nomenclature then it will (and maybe already has!) become widely accepted.

 

[Phil Karn]

Yes, I've checked my notes and I covered the topic with complex inputs and there's no mention of negative freq. But my notes were handwritten from a blackboard (or overhead projector) so I guess it's possible that I fell asleep in those lectures at some point and missed it. I did drink a lot of beer back then ?. But this Wikipedia page also talks about the complex FFT without mentioning negative frequency. Also this page for the slower DFT.

I thought it so obvious that it didn't really need to be stated. Consider the shifting property of the fourier transform. A shift in the frequency domain is equivalent to multiplication by a complex exponential in the time domain, and a shift in the time domain is equivalent to multiplication by a complex exponential in the frequency domain. (I use this property for coarse downconversion in a SDR based on fast convolution. I follow it with multiplication back in the time domain by a low frequency complex exponential for fine tuning. The frequency of that exponential can be either negative or positive depending on which way I want to shift it).

In the usual representation, frequency bin 0 of a DFT is the DC (zero frequency) component. Put a 1 there, set all the other bins to zero and do an inverse transform; you'll get a real constant in the time domain. Rotate those bins one to the right so the '1' is now in bin 1 and you'll get a complex exponential that rotates counterclockwise one full rotation across the time domain span. Keep rotating those frequency bins to the right and the time domain exponential will spin successively faster counterclockwise, i.e, its frequency will get more positive.

Now start with the '1' bin in the DC frequency position and rotate the bins one to the left. The '1' bin will be in the rightmost bin and the complex exponential will now rotate one rotation clockwise across the time domain span. The time domain signal frequency is now negative. Keep shifting to the left and the time domain signal will spin faster clockwise; its frequency getting more and more negative. The middle bin corresponds to both the most positive and the most negative frequency (the Nyuist frequency, Fs/2) because, being a discrete time operation, the DFT exhibits aliasing. So from the shifting property of the fourier transform the inescapable conclusion is that the left half of the DFT frequency domain bins correspond to positive frequencies, which rotate counterclockwise in the complex time domain, and the right half of the frequency bins correspond to negative frequencies, which rotate clockwise in the complex time domain. A complex sinusoid is exp(jωt), where j = sqrt(-1), ω (omega) is angular frequency and t is time. The sign of ω most definitely matters; a complex exponential has a signed frequency. I've always seen the complex FFT described this way from the very first time it was explained to me.

The DFT of a purely real signal has a negative frequency spectrum that is the complex conjugate of the positive spectrum. Real-only signals are a common enough special case that there are specialized FFTs to handle them, but a complex FFT will work just fine too if you set the imaginary components to zero. The complex DFT is the general case, the real DFT is the special case.

...if I read your post correctly you seem to have switched from talking about a single signal to two signals. If two signals x and y are x=cos(wt), y=sin(wt) then indeed this can be thought of as a point in the xy plane that rotates as t increases. However I was just trying to make the point that if you have a SINGLE signal, say x=sin(wt), then I think it's questionable to consider anything to be rotating since it's purely an oscillation.

No, it's still one single signal that happens to have a real and imaginary components; it's complex. Obviously a real-only signal cannot exhibit a direction of rotation, though strictly speaking it consists of equal amounts of positive and negative power at the same frequency such that their imaginary components cancel.

Signal theory is not the only place in electrical engineering where signals exhibit a direction of rotation. So does 3-phase power. Flip any two wires to a 3-phase AC motor and it will reverse direction. The 3-phase power supply sets up a rotating magnetic field across the rotor that drags it in the same direction. A single-phase AC motor, however, sets up a rotating magnetic field that is the superposition of one turning clockwise and another turning counterclockwise at the same frequency. Without something to tell the rotor which way to start, it'll just sit there until the motor burns up. So single phase motors require start or run windings with some sort of phase shift (usually a capacitor) to define a direction of rotation.

 

[Cubist]

This thread seems to be blowing out of proportion. There seem to be two main differences of opinion between us:-

(1) The use of the words, "negative frequency".
(2) Whether or not using complex numbers to represent AC signals (and AC impedance) actually means there is another, un-measurable, dimension somehow orthogonal to reality.

--

Regarding point (1), I've found some internet resources that use these words, and some that don't. I think we just basically have different opinions on whether or not we like these words. Either way, regardless of the words, the mathematics of the DFT/FFT remains EXACTLY the same for both of us.

I have now been educated about what people are referring to when they say, "negative frequency" in this context, and for this I'm both grateful and interested! I have learned something new, thanks.

--

Regarding point (2), it seems like a belief/ faith situation. I can't, and neither can anyone else, disprove the existence of a physical manifestation of an imaginary component of current in some other dimension (for example).

I have quite a scientific brain and tend to only believe statements backed by physical evidence/ experiment. None of the systems, or thought experiments, that you have described prove its existence to me (see * below). I view the use of complex number REPRESENTATION in the mathematics of AC analysis as just a very clever, back compatible, convenient, way to represent a system where two real world quantities are represented in one complex variable (like amplitude and phase for example).


* - Your example of a negative frequency radio in post#8 requires two real-world signals that are both sent with the same POSITIVE PHYSICAL frequency - and the two signals are simply just out of phase with each other. For me, there's no physical manifestation of complex signals nor real world negative frequency reception.

Obviously a real-only signal cannot exhibit a direction of rotation, though strictly speaking it consists of equal amounts of positive and negative power at the same frequency such that their imaginary components cancel.

...I'm not sure what you're saying here. Are you saying that adding together the corresponding positive frequency and negative frequency bins in the output generated by the FFT results in the actual, real, signal level? My understanding is that the imaginary and real components of a single output bin supply information about the overall amplitude and phase at that frequency (as far as I'm aware). To remove the imaginary part, by adding two conjugate bins, seems to remove information and give an incorrect amplitude at that frequency. For example:-
fft([0 1 0 -1 0 1 0 -1]) = 0 0 0-4i 0 0 0 0+4i 0
You're probably not saying that this real signal has zero amplitude after adding (0-4i) + (0+4i) = 0?

 

[jonah2.0]

Beer soaked non relevant comedy relief comment follows.

.... I did drink a lot of beer back then ?. ...

Mmmm, Beer.