Why is the FFT "mirrored"?

Question

If you do an FFT plot of a simple signal, like:

t = 0:0.01:1 ;
N = max(size(t));
x = 1 + sin( 2*pi*t ) ;
y = abs( fft( x ) ) ;
stem( N*t, y )

1Hz sinusoid + DC

FFT of above

I understand that the number in the first bin is "how much DC" there is in the signal.

y(1)  %DC
  > 101.0000

The number in the second bin should be "how much 1-cycle over the whole signal" there is:

y(2)  %1 cycle in the N samples
  > 50.6665

But it's not 101! It's about 50.5.

There's another entry at the end of the fft signal, equal in magnitude:

y(101)
  > 50.2971

So 50.5 again.

My question is, why is the FFT mirrored like this? Why isn't it just a 101 in y(2) (which would of course mean, all 101 bins of your signal have a 1 Hz sinusoid in it?)

Would it be accurate to do:

mid = round( N/2 ) ;

% Prepend y(1), then add y(2:middle) with the mirror FLIPPED vector
% from y(middle+1:end)
z = [ y(1), y( 2:mid ) + fliplr( y(mid+1:end) ) ];

stem( z )

Flip and add-in the second half of the FFT vector

I thought now, the mirrored part on the right hand side is added in correctly, giving me the desired "all 101 bins of the FFT contain a 1Hz sinusoid"

>> z(2)

ans =

  100.5943

Answer 1

Real signals are "mirrored" in the real and negative halves of the Fourier transform because of the nature of the Fourier transform. The Fourier transform is defined as the following-

$$H(f) = \int h(t)e^{-j2\pi ft}dt$$

Basically it correlates the signal with a bunch of complex sinusoids, each with its own frequency. So what do those complex sinusoids look like? The picture below illustrates one complex sinusoid.

The "corkscrew" is the rotating complex sinusoid in time, while the two sinusoids that follow it are the extracted real and imaginary components of the complex sinusoid. The astute reader will note that the real and imaginary components are the exact same, only they are out of phase with each other by 90 degrees ($\frac{\pi}{2}$). Because they are 90 degrees out of phase they are orthogonal and can "catch" any component of the signal at that frequency.

The relationship between the exponential and the cosine/sine is given by Euler's formula-

$$e^{jx} = \cos(x) + j\cdot\sin(x)$$

This allows us to modify the Fourier transform as follows- $$ H(f) = \int h(t)e^{-j2\pi ft}dt \\ = \int h(t)(\cos(2\pi ft) - j\cdot\sin(2\pi ft))dt $$

At the negative frequencies the Fourier transform becomes the following- $$ H(-f) = \int h(t)(\cos(2\pi (-f)t) - j\sin(2\pi (-f)t))dt \\ = \int h(t)(\cos(2\pi ft) + j\cdot\sin(2\pi ft))dt $$

Comparing the negative frequency version with the positive frequency version shows that the cosine is the same while the sine is inverted. They are still 90 degrees out of phase with each other, though, allowing them to catch any signal component at that (negative) frequency.

Because both the positive and negative frequency sinusoids are 90 degrees out of phase and have the same magnitude, they will both respond to real signals in the same way. Or rather, the magnitude of their response will be the same, but the correlation phase will be different.

EDIT: Specifically, the negative frequency correlation is the conjugate of the positive frequency correlation (due to the inverted imaginary sine component) for real signals. In mathematical terms, this is, as Dilip pointed out, the following

$H(-f) = [H(f)]^*$

Another way to think about it:

Imaginary components are just that..Imaginary! They are a tool, which allows the employ of an extra plane to view things on and makes much of digital (and analog) signal processing possible, if not much easier than using differential equations!

But we can't break the logical laws of nature, we can't do anything 'real' with the imaginary content$^\dagger$ and so it must effectively cancel itself out before returning to reality. How does this look in the Fourier Transform of a time based signal(complex frequency domain)? If we add/sum the positive and negative frequency components of the signal the imaginary parts cancel, this is what we mean by saying the positive and negative elements are conjugate to each-other. Notice that when an FT is taken of a time-signal there exists these conjugate signals, with the 'real' part of each sharing the magnitude, half in the positive domain, half in the negative, so in effect adding the conjugates together removes the imaginary content and provides the real content only.

$^\dagger$ Meaning we can't create a voltage that is $5i$ volts. Obviously, we can use imaginary numbers to represent real-world signals that are two-vector-valued, such as circularly polarized EM waves.

Answer 2

The FFT (or Fast Fourier Transform) is actually an algorithm for the computation of the Discrete Fourier Transform or DFT. The typical implementation achieves speed-up over the conventional computation of the DFT by exploiting the fact that $N$, the number of data points, is a composite integer which is not the case here since $101$ is a prime number. (While FFTs exist for the case when $N$ is a prime, they use a different formulation that might or might not be implemented in MATLAB). Indeed, many people deliberately choose $N$ to be of the form $2^k$ or $4^k$ so as to speed up the DFT computation via the FFT.

Turning to the question as to why the mirroring occurs, hotpaw2 has essentially stated the reason, and so the following is just a filling in of the details. The DFT of a sequence $\mathbf x = \bigr(x[0], x[1], x[2], \ldots, x[N-1]\bigr)$ of $N$ data points is defined to be a sequence $\mathbf X =\bigr(X[0], X[1], X[2], \ldots, X[N-1]\bigr)$ where $$X[m] = \sum_{n=0}^{N-1} x[n]\left(\exp\left(-j2\pi \frac{m}{N}\right)\right)^n, m = 0, 1, \ldots, N-1$$ where $j = \sqrt{-1}$. It will be obvious that $\mathbf X$ is, in general a complex-valued sequence even when $\mathbf x$ is a real-valued sequence. But note that when $\mathbf x$ is a real-valued sequence, $\displaystyle X[0]=\sum_{n=0}^{N-1} x[n]$ is a real number. Furthermore, if $N$ is an even number, then, since $\exp(-j\pi) = -1$, we also have that $$X\left[\frac{N}{2}\right] = \sum_{n=0}^{N-1} x[n]\left(\exp\left(-j2\pi \frac{N/2}{N}\right)\right)^n = \sum_{n=0}^{N-1} x[n](-1)^n$$ is a real number. But, regardless of whether $N$ is odd or even, the DFT $\mathbf X$ of a real-valued sequence $\mathbf x$ has Hermitian symmetry property that you have mentioned in a comment. We have for any fixed $m$, $1 \leq m \leq N-1$, $$\begin{align*} X[m] &= \sum_{n=0}^{N-1} x[n]\left(\exp\left(-j2\pi \frac{m}{N}\right)\right)^n\\ X[N-m] &= \sum_{n=0}^{N-1} x[n]\left(\exp\left(-j2\pi \frac{N-m}{N}\right)\right)^n\\ &= \sum_{n=0}^{N-1} x[n]\left(\exp\left(-j2\pi + j2\pi\frac{m}{N}\right)\right)^n\\ &= \sum_{n=0}^{N-1} x[n]\left(\exp\left(j2\pi\frac{m}{N}\right)\right)^n\\ &= \left(X[m]\right)^* \end{align*}$$ Thus, for $1 \leq m \leq N-1$, $X[N-m] = \left(X[m]\right)^*$. As a special case of this, note that if we choose $m = N/2$ when $N$ is even, we get that $X[N/2] = \left(X[N/2]\right)^*$, thus confirming our earlier conclusion that $X[N/2]$ is a real number. Note that an effect of the Hermitian symmetry property is that

the $m$-th bin in the DFT of a real-valued sequence has the same magnitude as the $(N-m)$-th bin.

MATLABi people will need to translate this to account for the fact that MATLAB arrays are numbered from $1$ upwards.

---

Turning to your actual data, your $\mathbf x$ is a DC value of $1$ plus slightly more than one period of a sinusoid of frequency $1$ Hz. Indeed, what you are getting is $$x[n] = 1 + \sin(2\pi (0.01n)), ~ 0 \leq n \leq 100$$ where $x[0] = x[100] = 1$. Thus, the first and the last of $101$ samples has the same value. The DFT that you are computing is thus given by $$X[m] = \sum_{n=0}^{100} \left(1+\sin\left(2\pi \left(\frac{n}{100}\right)\right)\right)\left(\exp\left(-j2\pi \frac{m}{101}\right)\right)^n$$ The mismatch between $100$ and $101$ causes clutter in the DFT: the values of $X[m]$ for $2 \leq m \leq 99$ are nonzero, albeit small. On the other hand, suppose you were to adjust the array t in your MATLAB program to have $100$ samples taken at $t=0, 0.01, 0.02, \ldots, 0.99$ so that what you have is $$x[n] = 1 + \sin(2\pi (0.01n)), ~ 0 \leq n \leq 99.$$ Then the DFT is $$X[m] = \sum_{n=0}^{99} \left(1+\sin\left(2\pi \left(\frac{n}{100}\right)\right)\right)\left(\exp\left(-j2\pi \frac{m}{100}\right)\right)^n,$$ you will see that your DFT will be exactly $\mathbf X = (100, -50j, 0, 0, \ldots, 0, 50j)$ (or at least within round-off error), and the inverse DFT will give that for $0 \leq n \leq 99$, $$\begin{align*} x[n] &= \frac{1}{100}\sum_{m=0}^{99}X[m]\left(\exp\left(j2\pi \frac{n}{100}\right)\right)^m\\ &= \frac{1}{100}\left[100 - 50j\exp\left(j2\pi \frac{n}{100}\right)^1 + 50j \left(\exp\left(j2\pi \frac{n}{100}\right)\right)^{99}\right]\\ &= 1 + \frac{1}{2j}\left[\exp\left(j2\pi \frac{n}{100}\right) - \exp\left(j2\pi \frac{-n}{100}\right)\right]\\ &= 1 + \sin(2\pi (0.01n)) \end{align*}$$ which is precisely what you started from.

Answer 3

Note that an FFT result is mirrored (as in conjugate symmetric) only if the input data is real.

For strictly real input data, the two conjugate mirror images in the FFT result cancel out the imaginary parts of any complex sinusoids, and thus sum to a strictly real sinusoid (except for tiny numerical rounding noise), thus leaving you with a representation of strictly real sine waves.

If the FFT result wasn't conjugate mirrored, it would represent a waveform that had complex values (non-zero imaginary components), not something strictly real valued.