3 corrected typo in last equation
source | link

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(0.01n) \end{align*}$$$$\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.

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(0.01n) \end{align*}$$ which is precisely what you started from.

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.

2 expanded last section of answer
source | link

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$ d 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 N-1$$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. Note that theIndeed, what you are getting is $$x[n] = 1 + \sin(2\pi (0.01n)), ~ 0 \leq n \leq 100$$ where first$x[0] = x[100] = 1$. Thus, the first and the last of last$101$ samples are taken from has the same pointvalue. The DFT that you are computing is thus given by on$$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 sinusoidDFT: the values of $X[m]$ for $2 \leq m \leq 99$ are nonzero, albeit small. Adjust On the other hand, suppose you were to adjust the array t toin your MATLAB program to have $100$ samples taken at $t=0, 0.01, 0.02, \ldots, 0.99$ andso 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 resultsDFT will have equal amplitudes in MATLAB bins $2$ andbe $100$, and the intermediate bins willexactly have value exactly $0$$\mathbf X = (100, -50j, 0, 0, \ldots, 0, 50j)$ (or withinat least within round-off error) instead of, and the inverse DFT will give small clutter they have nowthat 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(0.01n) \end{align*}$$ which is precisely what you started from.

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$ d 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 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. Note that the first and last samples are taken from the same point on the sinusoid. Adjust t to have $100$ samples taken at $t=0, 0.01, 0.02, \ldots, 0.99$ and you will see that your results will have equal amplitudes in MATLAB bins $2$ and $100$, and the intermediate bins will have value exactly $0$ (or within round-off error) instead of the small clutter they have now.

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(0.01n) \end{align*}$$ which is precisely what you started from.

1
source | link

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$ d 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 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. Note that the first and last samples are taken from the same point on the sinusoid. Adjust t to have $100$ samples taken at $t=0, 0.01, 0.02, \ldots, 0.99$ and you will see that your results will have equal amplitudes in MATLAB bins $2$ and $100$, and the intermediate bins will have value exactly $0$ (or within round-off error) instead of the small clutter they have now.