# FFT of a periodic function [duplicate]

Suppose you have N samples of a sine wave of frequency $f_0$ sampled at $f_s$.

$$x[n] = A\sin[2\pi(f_0 /f_s)n]$$

1. How do you get a delta function in the frequency domain (i.e. all of the energy is in the center one bin of the FFT)?
2. Does the number of samples (N) need to be a prime number of cycles of $f_0$? If so, why?
3. Does $f_s$ need to be an integer multiple of $f_0$? If so, why?
• How is this different from your other question? – Peter K. Nov 5 '13 at 18:14
• Not sure, but I think you're mixing up the FFT (a fast implementation) and the FT (the mathematical transform that is being implemented). – A. Donda Apr 29 '15 at 18:09

I think it's easier to look at exponentials. The reasoning is exactly the same, but if a sine or cosine were used, we would need two exponentials. So first let's say that $$x[n]=e^{j2\pi\frac{f_0}{fs}n}$$ Then the DFT is \begin{align} X_N[k]&=\sum_{n=0}^{N-1}e^{-j\frac{2\pi}{N}kn}e^{j2\pi\frac{f_0}{fs}n} \\ &=\sum_{n=0}^{N-1}e^{-j2\pi n\left ( \frac{k}{N}-\frac{f_0}{f_s} \right)} \\ &=\frac{1-e^{-j2\pi N\left(\frac{k}{N} -\frac{f_0}{f_s}\right)}}{1-e^{-j2\pi \left(\frac{k}{N} -\frac{f_0}{f_s}\right)}} \mbox{, where } k=0,\ldots,N-1 \end{align}

For this to be a delta, we need the following condition to be satisfied: $$N\left(\frac{k}{N}-\frac{f_0}{f_s}\right) \in \mathbb{Z} \Rightarrow k-N\frac{f_0}{f_s} \in \mathbb{Z}$$

With this condition, the numerator is always zero. The denominator will be zero if $$\frac{k}{N}-\left.\frac{f_0}{f_s}\right\vert_{k=k_0}=0 \mbox{, or } k_0=N\frac{f_0}{f_s}$$

At that particular $k_0$, you will need to use L'Hospital's Rule. This will give you the complete DFT as $$X_N[k]=\begin{cases} N &\mbox{ if } k=N\frac{f_0}{f_s} \\ 0 &\mbox { else} \end{cases} \mbox{, } k=0,\ldots,N-1$$

So what conditions did we impose to get this result? Just that $k-N\frac{f_0}{f_s} \in \mathbb{Z}$. Since $k$ is already an integer, we need only check $N\frac{f_0}{f_s}$. Define $f_s=af_0$. Therefore $a$ is the number of points in a cycle. Then we need $$\frac{N}{a} \in \mathbb{Z}$$ This can only be satisfied if $a$ is an integer, and $N$ is an integer multiple of $a$.

Putting all this together, if the sampling frequency is an integer multiple of the input's frequency, and $N$ is an integer number of points in a cycle of the sampled exponential, then the DFT of $x[n]$ will be a delta with height $N$.

• There is no need to use L'Hospital's rule. When $k_0 = N\frac{f_0}{f_s}$, we have that $$X[k_0] = \sum_{n=0}^{N-1}e^{-j2\pi n\left ( \frac{k_0}{N}-\frac{f_0}{f_s} \right)} = \sum_{n=0}^{N-1} e^0 = N,$$ no muss, no fuss, and no need to disturb the poor Marquis's ghost. – Dilip Sarwate Nov 6 '13 at 14:08
• Oh yeah, that's right. I generally do L'Hospital's, just because it's easy for the exponentials, but your way is very clear. – Trey Nov 6 '13 at 14:53
• It may be noteworthy that we're talking about a Kronecker-like delta, not a Dirac-delta. – A. Donda Apr 29 '15 at 18:07

In reverse order,

1. Yes the sampling frequency needs to be a multiple of $f_0$.

2. The number of cycles of the sinusoid in $N$ samples needs to be an integer, not necessarily a prime number.

3. If you do 3. and 2., all the energy will be concentrated in two bins (corresponding to $100$ Hz and $-100$ Hz.

Be careful, though. If you have a sinusoid $x(t)=\sin(2\pi (100) t)$ at 100 Hz and you sample it at 1000 Hz, you will have $10$ samples per cycle of the waveform. With $x[0] = 0$ and $x[9] \neq 0$, you can do an "FFT" of length $10$ if you like, and all the energy will be in $X[1]$ and $X[9]$. I put FFT in quotation marks because at such short lengths, a plain vanilla brute-force DFT calculation might be almost as fast. Note also that $x[10] = 0$ is not part of the DFT calculation. Alternatively, you can use $N = 10n$ samples and do an FFT of length $1000$ (say) on samples $x[0]$ through $x[999]$. In this case, the energy will all be in $X[10]$ and $X[1014]$. Regardless of what some other answers will likely tell you,

DO NOT zero-pad the length $1000$ FFT to length $1024$ to get an "efficient" implementation.

If you do follow the advice on zero-padding, your length-$1024$ FFT will NOT have the energy concentrated in two bins as you desire.

• But why does $f_s$ need to be a multiple of $f_0$? – Seth Nov 5 '13 at 20:39
• @Seth $f_s$ needs to be a multiple of $f_0$ because you need one full period of the sinusoid (from $0$ at $t = 0$ to $0$ at $t = 1/f_0$) to be an integer number of samples. Else, the energy of the sinusoid will be smeared over several bins. – Dilip Sarwate Nov 5 '13 at 22:53

For any length of FFT and sample rate Fs, you can calculate the entire set of (positive) frequencies for which a pure sinusoid will produce a delta function in the FFT result. They are:

k * Fs / FFTLength


for integer k = 0 to infinity. (Or to FFTLength/2 if you don't want aliases.)

Any other frequency sinusoid will not produce a delta, but instead a sampled periodic Sinc or Dirichlet function (conjugate mirrored for strictly real input). So you can answer your own 3 questions by process of elimination.