Take the 2-minute tour ×
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It's 100% free, no registration required.

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

1Hz

FFT of above

fft

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

enter image description here

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
share|improve this question
    
A similar question has been answered here: dsp.stackexchange.com/questions/3466/… –  pichenettes Oct 28 '12 at 17:35
    
But this is specifically about the symmetry (I believe it's called Hermetian symmetry?) of the signal. –  bobobobo Oct 28 '12 at 17:44
    
For a pure real signals F(k)=conj(F(N-k)), this is why the Fourier transform of a pure real signal is symmetric. –  WebMonster Oct 28 '12 at 18:02
    
Ask yourself: what result would you expect if your signal was 1 + cos(2*pit)... And 1 + i cos(2*pit)... And 1 + i sin(2*pi*t)... –  pichenettes Oct 28 '12 at 18:21
    
Because a Fourier transform breaks up a signal into complex exponentials, and a sine wave is the sum of 2 complex exponentials. dsp.stackexchange.com/a/449/29 –  endolith Oct 28 '12 at 19:55

3 Answers 3

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.

enter image description here enter image description here enter image description here

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

share|improve this answer
    
Good answer - one slight nitpick though, I am not on-board with "Because they are the same, anything that one correlates with, the other will too with the exact same magnitude and a 90 degree phase shift.". I know what you are trying to say, however (as you know), a sine correlates with a sine (score 1), but wont correlate at all with a cosine at all, (score 0). They are the same signal, but with different phases afterall. –  Mohammad Oct 29 '12 at 12:54
    
You're right. There's another more serious problem too. I will fix it later. –  Jim Clay Oct 29 '12 at 13:23
    
It would be nice if you could edit your answer to be more responsive to the question which is about DFTs (though it says FFT in the title) rather than giving the general theory of Fourier transforms. –  Dilip Sarwate Oct 29 '12 at 22:35
    
@DilipSarwate My goal is to help the questioner understand, and I think my approach is best for that. I have upvoted your answer, though, for doing the discrete math. –  Jim Clay Oct 29 '12 at 23:01
    
@JimClay Your approach is greatly appreciated by the entire readership of dsp.SE, and I hope that you will find the time to make your answer a truly great answer by explicitly including in your answer what is currently left for the reader to deduce: viz. that the equations show that $H(-f) = [H(f)]^*$ (and hence $|H(-f)| = |H(f)|$) when $x(t)$ is a real-valued signal and that this is the "mirroring" that the OP was asking about. In other words, I request that you edit your answer to be more responsive to the question actually asked (as I requested in my previous comment). –  Dilip Sarwate Oct 30 '12 at 12:42

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.

share|improve this answer
    
+1 Exhaustive and eloquent as always! = ) –  Phonon Oct 30 '12 at 16:17

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.