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*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*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*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)]^*$

Answer 2

Note that an FFT result is mirrored (as in conjugate symmetric) only if the input data is real. The two mirror images cancel out the imaginary part of the complex sinusoid, and sum to the real part, thus leaving your 100%, and strictly real, sine wave.

Answer 3

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.