1
$\begingroup$

Assume a discrete time signal $(x_n)$ is given. Some texts define the DFT as $$ X[k] = \sum_{n=-N}^N x_n\exp\left(\frac{-2\pi j k n}{N}\right) $$ while others define it as $$X[k] = \sum_{n=0}^{N-1} x_n\exp\left(\frac{-2\pi j k n}{N}\right) $$ or $$X[k] = \sum_{n=1}^N x_n\exp\left(\frac{-2\pi j k n}{N}\right)$$ or many other seemingly random variants with different indices. So what is the true index limits for DFT? Or is there no unique consensus and any random author is allowed to introduce a new one?

$\endgroup$
2
  • 1
    $\begingroup$ There is no trace of the signal $x$ in your formulas. So they look like the Fourier transforms of unit-amplitude windows, with different index positions, and all are legit. $\endgroup$ – Laurent Duval Feb 20 at 9:50
  • 1
    $\begingroup$ Apologies. It was a typo. Gonna correct it. $\endgroup$ – User32563 Feb 20 at 10:08
1
$\begingroup$

The second expression is the most common to me, for a standard $N$-length signal. The third could be equivalent if the $x[n]$ sequence is periodic, as the Fourier kernel $\exp\left(\frac{-2\pi j k n}{N}\right)$ has the same value (namely, 1) for $n=0$ and $n=N$.

The first one with $2N+1$ length seems odd to me, in both meanings. Yet, if the signal is considered to be null outside the considered support (the limits of the summation), the magnitude or the energy of the output may provide a sound amplitude spectrum (as a potential phase term could be cancelled).

I suspect than the diversity of formulae you have found (the second and the third) is related to different indexings that one can find in computer software: zero-based numbering (in C, Python) or one-based indices (Fortran, Matlab).

I believe that numbering should start at zero (see "Why numbering should start at zero (EWD 831)", Dijkstra, Edsger Wybe).

$\endgroup$
1
$\begingroup$

If $N$ is the DFT length, the summation is always over $N$ points. So under this assumption, the first formula doesn't make any sense. Note that the term $e^{-j2\pi nk/N}$ is $N$-periodic in $k$ and $n$, so summing over one period always gives the same value, regardless of the starting index. With the additional assumption that $x[n]$ is periodically continued, i.e., $x[n]=x[n+N]$, you can compute the given sum over any interval of length $N$. A notation emphasizing this fact is

$$X[k]=\sum_{<N>}x[n]e^{-j2\pi nk/N}\tag{1}$$

$\endgroup$
1
$\begingroup$

I have never seen the first and the third definitions of DFT within the context of digital signal processing as part of electrical & electronics engineering curriculum.

Almost all the texts define a DFT of a sequence (of length $N$) as

$$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} n k } ~~~,~~~k = 0,1,...,N-1 \tag{1}$$

Some authors prefer putting a scale (weight) such as $\frac{1}{N}$ or $\frac{1}{\sqrt{N}}$ to the forward or backward transforms, but that's a matter of convenience.

The important thing is to remember not mixing different definitions into the same equation.

$\endgroup$

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.