0
$\begingroup$

This question already has an answer here:

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?
$\endgroup$

marked as duplicate by jojek, MBaz, Matt L., Peter K. May 5 '15 at 1:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ How is this different from your other question? $\endgroup$ – Peter K. Nov 5 '13 at 18:14
  • $\begingroup$ Not sure, but I think you're mixing up the FFT (a fast implementation) and the FT (the mathematical transform that is being implemented). $\endgroup$ – A. Donda Apr 29 '15 at 18:09
0
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Dilip Sarwate Nov 6 '13 at 14:08
  • $\begingroup$ 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. $\endgroup$ – Trey Nov 6 '13 at 14:53
  • $\begingroup$ It may be noteworthy that we're talking about a Kronecker-like delta, not a Dirac-delta. $\endgroup$ – A. Donda Apr 29 '15 at 18:07
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But why does $f_s$ need to be a multiple of $f_0$? $\endgroup$ – Seth Nov 5 '13 at 20:39
  • $\begingroup$ @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. $\endgroup$ – Dilip Sarwate Nov 5 '13 at 22:53
0
$\begingroup$

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.

$\endgroup$

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