# Positive and negative frequencies in DFT due to frequency folding, or due to negatively indexed frequencies?

When I look for the cause of the mirroring of frequencies in DFT output, I get two types of explanations:

• The first one which says the frequencies are mirrored because of the complex exponential which has a positive and negative counterpart. The poritive(real) parts add up and the negative (imaginary) parts cancel out, and that the amplitudes are spilt equally between the positive and negative frequencies.

• The second one which says this happens as a consequence of sampling above the Nyquist frequency, i.e., above $$\frac{N}2$$. But the mirroring would still be present if we take the range $$-\frac{N}2$$ to $$\frac{N}2$$.

My question is what is the actual cause for this mirroring, and what actually changes with taking the range as $$-\frac{N}2$$ to $$\frac{N}2$$ or $$0$$ to $$N-1$$?

Okay, to within a scaling factor where definitions may vary, this is the DFT and it's inverse:

$$X[k] = \sum\limits^{N-1}_{n=0} x[n] \ e^{-j2\pi n k/N}$$

$$x[n] = \frac{1}{N} \sum\limits^{N-1}_{k=0} X[k] \ e^{+j2\pi n k/N}$$

Both the discrete-time function $$x[n]$$ and discrete-frequency function $$X[k]$$ are periodic with period $$N$$. Even if your original data was not periodic, when you first apply a window of length $$N$$ and send it to the DFT, the DFT assumes it's one period of a given periodic function. The DFT and inverse DFT literally periodically extends the data input to it.

$$X[k+N] = X[k] \qquad \forall k \in \mathbb{Z}$$ $$x[n+N] = x[n] \qquad \forall n \in \mathbb{Z}$$

So there is a form of "mirroring" that doesn't flip like mirrors do, built into the DFT. What this periodic "mirroring" does is make the latter half ($$X[k]: \frac{N}2 < k < N$$) of the DFT (or iDFT) results be exactly the same as the negative half ($$X[k]: -\frac{N}2 < k < 0$$).

Now what flips it is what happens if $$x[n]$$ is real.

$$\Im\big\{ x[n] \big\} = 0 \quad \forall n \qquad \implies \qquad X[-k] = X[k]^* \quad \forall k$$

That'll make the latter half of the DFT look like a mirror image of the beginning half.

• Just out of curiosity, what if x[n] is not real...do we still get the mirroring? – Ranjan May 24 at 4:15
• you get the repeating: $$X[k] = X[k+N]$$, but not the flipped mirror image: $$X[-k] \ne X[k]^*$$ – robert bristow-johnson May 24 at 4:18

I think that considering the DFT from a linear algebraic point of view has some value, so I will attempt to introduce the foundations.

We will assume that our signal is a vector of $$N$$ complex entries.

$$\mathbb{C}^N$$ is the vector space of vectors with $$N$$ complex entries. Let $$\mathbf{u}_0,\mathbf{u}_1,\ldots,\mathbf{u}_{N-1}$$ be vectors in $$\mathbb{C}^{N}$$ defined by $$\begin{equation} \begin{split} \mathbf{u}_k &=~ \frac{1}{\sqrt{N}}\left(\begin{array}{c} \exp(2\pi \mathsf{j}\times 0\times(k/N))\\ \exp(2\pi \mathsf{j}\times 1\times(k/N))\\ \exp(2\pi \mathsf{j}\times 2\times(k/N))\\ \exp(2\pi \mathsf{j}\times 3\times(k/N))\\ \vdots\\ \exp(2\pi \mathsf{j}\times (N-1)\times(k/N)) \end{array}\right)\\ &=~ \frac{1}{\sqrt{N}}\left(\begin{array}{c} 1\\ e^{2\pi\mathsf{j}k/N}\\ (e^{2\pi\mathsf{j}k/N})^2\\ \vdots\\ (e^{2\pi\mathsf{j}k/N})^{N-1} \end{array}\right), \end{split} \end{equation}$$ for $$k = 0,1,2,\ldots,N-1$$, where $$\mathsf{j} = \sqrt{-1}$$.

• Every entry of $$\mathbf{u}_0$$ is $$1/\sqrt{N}$$, so $$\mathbf{u}_0$$ might be considered as a sampled DC signal.
• The entries of $$\mathbf{u}_1$$ are samples of a complex exponential with fequency $$\frac{1}{N}$$,
• The entries of $$\mathbf{u}_2$$ are samples of a complex exponential with fequency $$\frac{2}{N}$$,
• and so on, up through frequency $$\frac{N-1}{N}$$.

$$\mathbf{u}_0,\mathbf{u}_1,\ldots,\mathbf{u}_{N-1}$$ form an orthonormal basis for $$\mathbb{C}^{N}$$, which means that each $$\mathbf{u}_k$$ has norm 1, they are all orthogonal to one another, and each vector in $$\mathbb{C}^{N}$$ can be represented unambiguously as a linear combination of them. An important result of this is that, if $$\mathbf{x}\in\mathbb{C}^{N}$$, then there is exactly one list of complex numbers $$c_0,c_1,\ldots,c_N$$ such that $$\begin{equation} \mathbb{x} = c_0\mathbf{u}_0 + c_1\mathbf{u}_1 + \cdots + c_{N-1}\mathbf{u}_{N-1}. \end{equation}$$

The coefficients mentioned above are the entries of the DFT of $$\mathbf{x}$$: $$\begin{equation} \mathbf{x} = X\mathbf{u}_0 + X\mathbf{u}_1 + \cdots + X[N-1]\mathbf{u}_{N-1}. \end{equation}$$ We might interpret $$X$$ as the strength of the DC component of $$\mathbf{x}$$, $$X$$ as the strength of the component of $$\mathbf{x}$$ with frequency $$\frac{1}{N}$$, and so on. Since $$\mathbf{X} = \mathsf{DFT}\mathbf{x}$$ has complex entries, there is some phase information attached to each "strength".

So far, we have considered only components of non-negative frequencies. What if we would rather view $$\mathbf{x}$$ as a combination of negative and positive frequency components? Consider a component of frequency $$-\frac{k}{N}$$ for $$0< k \leq \frac{N}{2}$$: $$\begin{equation} \mathbf{u}_{-k} ~=~ \frac{1}{\sqrt{N}}\left(\begin{array}{c} \exp(2\pi \mathsf{j}\times 0\times(-k/N))\\ \exp(2\pi \mathsf{j}\times 1\times(-k/N))\\ \exp(2\pi \mathsf{j}\times 2\times(-k/N))\\ \exp(2\pi \mathsf{j}\times 3\times(-k/N))\\ \vdots\\ \exp(2\pi \mathsf{j}\times (N-1)\times(-k/N)) \end{array}\right). \end{equation}$$ The $$\ell^{\textrm{th}}$$ entry of this vector is $$\begin{equation} \begin{split} u_{-k}[\ell] &=~ \frac{1}{\sqrt{N}}\exp\left(2\pi\mathsf{j}\times\ell\times\frac{-k}{N}\right)\\ &=~ \frac{1}{\sqrt{N}}\exp\left(2\pi\mathsf{j}\times\ell\times\frac{-k}{N}\right)\times\underbrace{\exp\left(2\pi\mathsf{j}\times\ell\times\frac{N}{N}\right)}_{1}\\ &=~ \frac{1}{\sqrt{N}}\exp\left(2\pi\mathsf{j}\times\ell\times\frac{N-k}{N}\right)\\ &=~ u_{N-k}[\ell]. \end{split} \end{equation}$$ In other words, the negative-frequency component $$\mathbf{u}_{-k}$$ is exactly the same as the positive-frequency component $$\mathbf{u}_{N-k}$$.

Suppose that $$N = 2M$$ for some positive integer $$M$$. Then $$\begin{equation} \begin{split} \mathbf{x} &=~ X\mathbf{u}_0 + \cdots + X[N/2-1]\mathbf{u}_{N/2-1} + X[N/2]\mathbf{u}_{N/2} + \cdots + X[N-1]\mathbf{u}_{N-1}\\ &=~ X\mathbf{u}_0 + \cdots + X[M-1]\mathbf{u}_{M-1} + X[M]\mathbf{u}_{M} + \cdots + X[N-1]\mathbf{u}_{N-1}\\ &=~ \underbrace{X\mathbf{u}_0 + \cdots + X[M-1]\mathbf{u}_{M-1}}_{\textrm{non-negative-frequency components}} + \underbrace{X[M]\mathbf{u}_{N-M} + \cdots + X[N-1]\mathbf{u}_{N-1}}_{\textrm{negative-frequency components}} \end{split} \end{equation}$$ For a full decomposition, one can choose the frequency-sets $$\begin{equation} -\frac{N/2}{N},-\frac{N/2-1}{N},\ldots,-\frac{1}{N},0,\frac{1}{N},\ldots,\frac{N/2-1}{N} \end{equation}$$ or $$\begin{equation} 0,\frac{1}{N},\ldots,\frac{N-1}{N}, \end{equation}$$ each of which consists of $$N$$ distinct frequencies. In truth, one can choose other frequency-sets of $$N$$ frequencies, too, but these are the ones to which we have attached some intuition over the decades.

MATLAB's fft gives the DFT with all non-negative frequencies. To convert the output of fft to the vector of coefficients for negative, zero, and positive frequencies, one applies the fftshift function.
All of this and much more is explained from a linear algebraic point of view in Linear Algebra, Signal Processing, and Wavelets - A Unified Approach (PDF) by Øyvind Ryan of the University of Oslo.

• Thanks for this linear algebra point of view, especially the derivation that you've shown. That answers my question. – Ranjan May 24 at 14:15

Both. And more.

From just looking at the FFT results, you can't tell if the input samples were samples of a low frequency sinewave (below half the sample rate) reversed in time, or of a high frequency (above half the sample rate and below the sample rate), or any of an infinite multiple of image folding frequencies thereof (both high (under sampled) and/or reversed).

So you either know or make assumptions about the input data; information that is outside that of just the FFT results. Or pick an assumption that makes your subsequent math (or visualization, etc.) easier.

• Thanks very much, this is what I was looking for. Also, can you please expound a bit, or point towards some resources, I want to read a little more on this.... This is very interesting to me... – Ranjan May 24 at 15:51

what is the actual cause for this mirroring

Nothing is "mirrored" per se. Sampling in the time domain makes it periodic in the frequency domain (and vice versa). The period is the sample rate. The DFT is discrete in both domains that means it's also periodic in both domains (with $$N$$). Hence you have $$X(-N/2) = X(+N/2), X(-N/2+1) = X(N/2+1), ...$$

and what actually changes with taking the range as $$-\frac{N}2$$ to $$\frac{N}2$$ or $$0$$ to $$N-1$$

not much. The DFT assumes that the signal is periodic and so the choice of a "starting point" is somewhat arbitrary. Neither is "wrong" or "right". It's just more convenient to pick one convention and stick with it.

• Can you please elaborate a bit on this: The period is the sample rate. – Ranjan May 23 at 18:52
• If you sample a time domain signal with a sampling rate of 1kHz the spectrum of that time domain signal will be periodic with a period of 1 kHz. – Hilmar May 23 at 18:58
• I get it. So the frequency folding is just because the whole series of amplitudes are getting repeated after 1 period (1khz)? I'm sorry is this is too basic, I am new to Fourier transforms... – Ranjan May 23 at 19:05
• Yes. That's a fundamental property of sampling: discrete in one domain equals periodic in the other – Hilmar May 23 at 21:49

Both.

For a visual, check this out: This is a representation of a sixteen point DFT which is part of an animation. Looking at the bottom graph. Can you see that the signal is clearly 14 cycles per frame? Yet, it you connect the dots with your eyes, you see 2 cycles per frame from the same sample points.

Now look at "the clock". The big hand is pointing at the 14. Notice, if you look up, the 14 aligns with 2. 2 is the same as -14, and 14 is the same as -2 on the clock (bin) scale.

The rest of the diagram is left unexplained.

Here is one from earlier in the sequence: • Wow! Thanks for this explanation. Could you also please share the source of this diagram, I really want to read more on this... – Ranjan May 24 at 3:58
• @Ranjan Private stock. It is produced by a program that I wrote for an upcoming blog article. My blog concentrates on understanding the DFT. This other article would be the most similar (except "the clocks" are in the time domain there): dsprelated.com/showarticle/768.php You can find the rest by clicking on the red author name. The periodicity of the DFT (as RBJ emphasizes) is in both the input and output domains, usually time and frequency. Thus, both are well represented in circular arrangements. – Cedron Dawg May 24 at 4:07
• I see. Is there some common name to these sort of diagrams, or have you come up with these for the first time? – Ranjan May 24 at 4:12
• @Ranjan They are just polar graphs, bar charts, and graphs of a DFT of a pure tone. I didn't copy anybody. With the second pic there you should be able to tell what the other square is. The outer circles around the clock are also representations of the bin values. The line shows the phase angle and the size of the inner circle shows the magnitude (the area gives you "energy"). Computer geeks will note that the Nyquist bin is labeled -8, (1000b). The animation is cool, but it is huuuuuge. (gif) – Cedron Dawg May 24 at 4:22