# frequency folding due to aliasing in FFT

I am having problem understanding why negative frequencies are showing up to the right of positive frequencies in discrete complex FFT.

I am not sure how to apply aliasing concept to explain such phenomenon even after reading about modulo-2pi angular frequency concept at MIT OCW signal processing course.

Anyone ?

• Kevin you are not sure how to apply aliasing to explain it since because it's not about aliasing... – Fat32 May 25 '17 at 23:01

The Fourier transform $X(e^{j\Omega})$ of a sequence $x[n]$ is by definition periodic of period $2\pi$ in $\Omega$. The $N$-point discrete Fourier transform (DFT) of $x[n]$ is simply defined as a sampled version of the Fourier transform $X(e^{j\Omega})$, that is $$X[k] = X(e^{j\frac{2k\pi}{N}}).$$ The periodicity of $2\pi$ in $\Omega$ for the Fourier transform becomes a periodicity of $N$ in $k$ for the DFT $$X[k+N] = X[k].$$ The negative frequencies showing up to the right of the positive frequencies is simply a consequence of this periodicity. Or if you prefer, you get $X[k]$ for $k \in [0, N-1]$ instead of $k \in [-\frac{N-1}{2}, \frac{N-1}{2}]$. If you want the vector to contain first negative frequencies, then the DC and finally the positive frequencies instead, you can for example use MATLAB fftshift.

Those negative frequencies are not shown for the "real" DFT because if $x[n]$ is real, then $X[k] = X^*[-k]$ (conjugate symmetry). Hence, you only need $X[k]$ for $k \in [0, N/2]$.

• I understand the periodicity of 2pi which results in X[k+N] = X[k] , but how does the periodicity concept places negative frequencies to the right of negative frequencies ? Besides, I do not get why is it that the Nyuist frequency component at X[N/2] separates the positive and negative frequencies. – kevin May 24 '17 at 11:20
• By periodicity, $X[N/2 + i] = X[-N/2 + i]$. Hence, the frequencies "above" the Nyquist frequency $N/2$ are the same as the frequencies "above" $-N/2$. – anpar May 24 '17 at 11:31
• Thanks. According to en.wikipedia.org/wiki/Aliasing#Folding , the symmetrical folding happens at Nyquist frequency N/2 instead of DC 0 implied by X[N/2+i]=X[−N/2+i]. Am I missing something ? – kevin May 24 '17 at 13:49

I will try to give a more intuitive answer here. Have you ever seen this effect? It is related to your question.

For simplicity, I will take easy numbers. The camera rate (fs) is, lets say, 1 frames per second: every second it takes a snapshot of the wheel. Now, assume that the wheel is spinning also at 1 turn per second (fw). Result? you see a static wheel, the car is going fast (the landscape is passing by...), but the wheels just seem not to spin at all, but you know they are moving. In this case, $fw = fs$, and you see how $2 \cdot \pi$ [rads] maps to $0 \cdot \pi$ [rads], you lose information in the sampling process.

Now, if $fw$ is 0.9 ([Hz]), the wheels seem to spin counterclockwise very slowly. But the question is, did it turn counterclockwise slowly or clockwise but much faster?. We have two options:

1. Assume they are always spinning clockwise (or counterclockwise), i.e. it spun at 0.9 Hz clockwise. So possible frequencies span [0, N) samples or [0, 1) Hz.
2. Assume that wheels reached that state through the shortest pat, i.e. it spun counterclockwise at 0.1 Hz. So possible frequencies span [-N/2,N/2) samples or [-0.5, 0.5) Hz.

In the signal domain, a wheel spinning clockwise would be sine and a counterclockwise spinning wheel would be a negative sine ($sin(- \omega \cdot t) = -sin(\omega \cdot t)$), and so on for cosine. Since negative sine is common we better go with the second approach.

In short, negative frequencies equal higher positive frequencies, in the digital domain you can not tell the difference.