fourier transform - DFT of discrete signals, why do we only analyze frequency bins equal to number of input samples?

If we have a signal $x[n]$ such that we have $N$ samples i.e. $n=0, \ldots, N-1$, then when we analyze the DFT $X[k]$ we only analyze for $k=0,\dots,N-1$ as well.

• Why is the range of $k$ tied to the range of $n$?


• Why don't we analyze more, or less number of frequencies?

Answer

From the definition of a $N$-point DFT of a sequence $\left\{x[n]\right\}$, you have:

$$X[k]=\sum_{n=0}^{N-1} x[n]\exp\left(-j\frac{2\pi kn}{N}\right),\quad k=0, 1, \dots, N-1\tag{1}$$

• 
  
  

  Let's say for a fixed $N$ we go against equation $(1)$ and compute more values to let's say $N_2$ such that $N_2\gg N$. Looking at the exponential term, let's say: $$e_k = \exp\left(-j\frac{2\pi kn}{N}\right),\quad k=0, 1, \dots, N-1, N, N+1, \ldots, N_2-1$$

  
  

  It can be verified that for $m\in \mathbb Z$: $$e_{k+m N} = \exp \left[-j\left(\frac{2\pi kn}{N}+ 2\pi mn\right)\right]=\exp\left(-j\frac{2\pi kn}{N}\right)\cdot 1=e_k\tag{2}$$

  
  

  In other words, all the values you'll compute for $k \gt N-1$ you already computed them. Equation $(1)$ requires $N$ harmonically related exponentials determined by the index $k$, and that is sufficient for a $N$-point DFT. No extra/new info beyond that, all the signal's spectral information can be extracted to at most $k=N-1$. And this is regardless of the nature of $x[n]$, whether $x[n]$ is periodic or not periodic the DFT by its definition in equation $(1)$ does not make such an assumption. (@Matt. L puts it nicely in his answer and comments here regarding the confusion on the periodicity assumption).

  
  


• 
  

  Yes, we can analyze more than the range of $n$. Let's say $N_2$. Note that we are doing a $N_2$-point DFT, (i.e. the denominator in the exponential term is $N_2$) and $0\leq k \leq N_2-1$. The choice of $N$(here $N_2$) determines two things: the frequency spacing of the DFT samples and the computation time taken to compute those DFT samples. The corresponding frequency spacing $\Delta f$ in $\textrm{ Hz}$ between two consecutive DFT samples is: $$\Delta f=\frac{F_s}{N}$$ $$N_2>N \Longrightarrow \frac{F_s}{N_2} < \frac{F_s}{N} $$ So, this will increase the computation time as you'll have more DFT samples since you have more $k$'s; but the frequency spacing gets smaller (i.e. reduces the spectral separation of consecutive DFT samples), and this gives a high resolution in the frequency domain.

  
  


• 
  

  Yes, we can even analyze less than the range of $n$. Application-dependent like the Goertzel algorithm already mentioned is one example. Or depending on nature of the signal, like real signals for instance where the resulting redundancies in the DFT can be used to compute up to half of the values to have a full spectral characteristic instead of going up to $N$.