4
$\begingroup$

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?
$\endgroup$
  • 1
    $\begingroup$ If you are taking a sequence of length N and taking it's DFT, You are saying original sequence is periodic with period N ( In DFT, You have to consider only one period of seq).This results in another periodic signal of same length. Even if you increase the range of 'k', you are not gaining anything $\endgroup$ – spectre Mar 30 '16 at 7:27
  • $\begingroup$ the short answer is that either the result of the DFT or of the iDFT fully defines your signal to the same degree. that's what it means for a mapping to be one-to-one or invertible or "bijective". so in either domain you have exactly $N$ degrees of freedom. (or $2N$ degrees of freedom, if you mean real-valued degrees of freedom.) $\endgroup$ – robert bristow-johnson Apr 5 '16 at 3:37
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ @GrowinMan You're welcome, I am glad it helped. Also check the edit I made. $\endgroup$ – Gilles Apr 7 '16 at 7:12
  • $\begingroup$ Hi @Gilles I was going through this answer again and I realized that I understand the math you provided - it makes it obvious that if you tried to analyze the DFT for $k$ more than $N$ you're end up repeating values. But can we intuitively understand why this happens? i.e. Intuitively understand why, for a given $N$ samples of a discrete signal, taking their dot product with exactly $N$ basis functions of the DFT is sufficient? $\endgroup$ – GrowinMan Sep 30 '16 at 8:32
  • $\begingroup$ And also, how do you obtain $$\Delta f = \frac{F_s}{N}$$ $\endgroup$ – GrowinMan Sep 30 '16 at 8:33
  • 1
    $\begingroup$ @GrowinMan it's not for any basis, it's an intrinsic property of the periodicity of the exponential in equation (2). The frequency in $\textrm{Hz}$ of a DFT bin at index $k$ is $f_k=k\frac{F_s}{N}$. For two consecutive bins $\Delta k = 1$, you can deduce $\Delta f$. $\endgroup$ – Gilles Oct 4 '16 at 17:52
  • $\begingroup$ oh alright. Thanks. And what about the question before that (intuition behind why N basis functions are sufficient) $\endgroup$ – GrowinMan Oct 5 '16 at 16:27
2
$\begingroup$

A DFT is an invertable (square matrix) transform, thus the complex result vector is the same size as the complex input vector. But you can analyze as many (additional) frequencies as you want by interpolating the results after the DFT (which requires additional computation that doesn't really increase separation resolution, but can produce a smoother looking plot).

You can analyze less if you want by using the Goertzel algorithm, which can be used to compute any single frequency result bin of a DFT. (But calculating less than N orthogonal bins won't be invertable or "complete". And any more than log(N) bins will likely be a lot slower than just doing a full FFT and throwing away what you don't need.)

$\endgroup$
2
$\begingroup$

One easy way to understand DFT is direct substitution of $k$ in $X[k]$.

If you calculate $X[N:2N-1]$, you will get the same result with $X[0:N-1]$.

And then If you calculate $X[2N:3N-1]$, you will get the same result with $X[0:N-1]$.

You will always find the same result with $N$ period substitution.

This means $X[k]$ is periodic function having $N$ period and all information is in $X[0:N-1]$.

$\endgroup$
  • $\begingroup$ "And then If you calculate X[2N:2N-1], you will get the same result with X[0:N-1]." ?? $\endgroup$ – Arpit Jain Mar 30 '16 at 11:42
  • $\begingroup$ It's my mistake. $\endgroup$ – KKS Mar 30 '16 at 12:33
  • $\begingroup$ I guess then my follow-up question would be that if when a discrete input signal x[n] is periodic with a period of N samples, then why is the DFT also periodic with N frequencies? $\endgroup$ – GrowinMan Apr 2 '16 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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