2
$\begingroup$

I'm going through a Coursera course on signal processing, and we're just introduced to DFTs.

We are told that if you have a complex sinusoidal signal $x[n]$ where $n=0,1...\ N-1$, its DFT is given as

$$X[k]=\sum_{n=0}^{N-1} x[n] e^{-j2\pi kn/N}$$

And this makes sense to me. Because $x[n]$ has $N$ samples. You take each one, multiply it with the sample of a basis function, essentially taking the dot product of the signal with the basis function, and you get how much of that frequency is present in the input signal.

But we are told that if you have a real sinusoidal signal $y[n]$ where $n=0,1...\ N-1$, then the DFT is given as

$$X[k]=\sum_{n=-N/2}^{N/2-1} y[n] e^{-j2\pi kn/N}$$

My question: Why do we sum over the different values? What is the intuition and explanation behind this?

I'm not even sure what $y[-N/2]$ would mean.

Is the $-N/2^{th}$ sample the same as the $N/2^{th}$ sample because we assume the input signal is periodic? Even if so, why is taking the DFT summation over such a range beneficial? We could also do this for complex sinusoidal signals since they're periodic too right? What's the advantage?

$\endgroup$
2
$\begingroup$

The DFT (Discrete Fourier Transform) of an $N$-point sequence $\left\{x[n]\right\}$ is given as: $$X[k]=\sum_{n=0}^{N-1} x[n] e^{-j2\pi kn/N}, \quad k=0, 1, \ldots, N-1\tag{1}$$

If we assume the sequence $\left\{x[n]\right\}$ and its DFT are complex, they can be expressed as follows (with the subscript $r$ and $i$ for real and imaginary part respectively):

\begin{align} x[n] &= x_r[n]+jx_i[n], \quad 0\leq n\leq N-1\\ X[k] &= X_r[k]+jX_i[k], \quad 0\leq k\leq N-1 \end{align}

With a bit of algebra and using equation $(1)$, you get:

\begin{align} X_r[k] &= \sum_{n=0}^{N-1}\left[ x_r[n]\cos\left(\frac{2\pi kn}{N} \right)+x_i[n]\sin\left(\frac{2\pi kn}{N} \right)\right]\\ X_i[k] &= -\sum_{n=0}^{N-1}\left[ x_r[n]\sin\left(\frac{2\pi kn}{N} \right)-x_i[n]\cos\left(\frac{2\pi kn}{N} \right)\right] \end{align} If the sequence $\left\{x[n]\right\}$ is real-valued, this means $ x[n]=x_r[n]$ as $x_i[n]=0$. The DFT will then be expressed as:

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

And it can be shown from equation $(1)$ and $(2)$ that for these real-valued signals:

$$X(N-k)=X^*(k)=X(-k)\tag{3}$$

  • From the above results, it suffices to compute the DFT for half of the values of $k$ to get the full characteristic of the spectrum. From the $N$ values you compute less (roughly half) $k$ values. The boundaries of the summation are still the same, it still goes from $n=0$ to $N-1$ but your $k$'s shouldn't go up to $N-1$ as it will be a waste of resources. $$X[k]=\sum_{n=0}^{N-1}y[n] e^{-j2\pi kn/N}$$

    For $N$ even, $ 0\leq k \leq N/2$ suffices. With the results from equation $(3)$ you can get the remaining values from $N/2 + 1$ to $N-1$ or from $-N/2 + 1$ to $-1$.

  • You have $ 0\leq n \leq N$. So, $y[-N/2]$ does not exist and $y[N/2]$ is the value of your sequence $\left\{y[n]\right\}$ at $n=N/2$ (if $N$ is even).

  • However, for a real even sequence $\left\{y[n]\right\}$, the DFT $X[-N/2]$ equals $X[N/2]$ and this is the value at Nyquist.

  • Also note from equation $(3)$ that if $N$ is even, $X[0]$ and $X[N/2]$ must be real, and if $N$ is odd $X[0]$ is still real but you don't have a frequency bin at exactly $N/2$. Equation $(3)$ applies for real-valued sequences, what has been concluded from that equation doesn't apply for strictly complex-valued sequences. The advantage is that you've saved computations by computing only half of what you need to compute.

$\endgroup$
  • $\begingroup$ Hi Giles Thanks for taking the time out for your elaborate answer. I have a few follow up questions: Q1. From your second point, you say that $y[-N/2]$ doesn't exist. And I agree with that. But then the course slides use the second equation that I posted in the question. How does one interpret $y[n]$ when $n=-N/2$ in that equation? Q2. The sole purpose of deriving $(3)$ in your answer is just to realize that the computations can be halved and leverage that fact right? $\endgroup$ – GrowinMan Apr 2 '16 at 21:21
  • $\begingroup$ Q3. Is there any particular benefit of considering a negative frequency like X(-k) as opposed to just looking at it traditionally as X(N-k)? $\endgroup$ – GrowinMan Apr 2 '16 at 21:21
  • $\begingroup$ BTW sorry about the formatting. How do you add newlines to comments? Ending the line with two spaces doesn't seem to work. $\endgroup$ – GrowinMan Apr 2 '16 at 21:26
  • 1
    $\begingroup$ @GrowinMan . Q1. We're still doing a $N$-point DFT of $y[n]$. One could write $y[-N/2]$ as you did and do half the summation but only if a change of variable to let's $n=m-N/2$ was done and also that $y[n]$ is symmetric such that $y[n]=y[N-n]$. If there was a change of variables that would apply to the $n$ exponent on the exponential. But strictly going from the definition $y[-N/2]$ is undefined. $\endgroup$ – Gilles Apr 2 '16 at 22:16
  • 1
    $\begingroup$ Q2. Yes, not only that but also that $\left|X(N-k)\right| = \left|X(k)\right|$ and $\angle X(N-k) = -\angle X(k)$, and also see that for certain $k$ values $X(k)$ are real (not complex) values. Q3. There is no benefit in doing so, as the spectrum characteristics can be deducted from half of the values. Most of spectra you'll encounter in textbooks are single-side because of the symmetry. And there is no actual physical meaning to negative frequencies, see this post and comments. $\endgroup$ – Gilles Apr 2 '16 at 22:16
1
$\begingroup$

The DFT is one and the same as the DFS. The DFT maps a discrete and periodic sequence of values with period $N$, that is

$$x[n] = x[n+N] \quad \quad \forall n \in \mathbb{Z}$$

to another discrete and periodic sequence

$$X[k] = X[k+N] \quad \quad \forall k \in \mathbb{Z}$$

and the iDFT maps it back. the discreteness in one domain causes the periodicity in the other domain, and since the mapping is 1-to-1, you can say that periodicity in one domain causes discreteness in the other. both periodic sequences are fully defined by $N$ complex numbers and a practical iDFT and DFT maps those two finite-length sets of numbers back and forth to each other.

Although not commonly done, it's perfectly okay to generalize the DFT and iDFT to be

$$ X[k] = \sum\limits_{n=n_0}^{n_0+N-1} x[n] \ e^{-j 2 \pi nk/N} $$

$$ x[n] = \frac1N \sum\limits_{k=k_0}^{k_0+N-1} X[k] \ e^{j 2 \pi nk/N} $$

$n, n_0, k, k_0$ can be any integers.

so the choice of $k_0 = -\frac{N}{2}$ comes from the convenience of pairing $X[-k]$ to $X[k]$. since, in general

$$ X[k] = \Re\{X[k]\} + j \Im\{X[k]\} $$

and if $\Im\{x[n]\}=0$ for all $n$, then

$$ X[-k] = X^*[k] = \Re\{X[k]\} - j \Im\{X[k]\} $$

then you can say, about reconstructing $x[n]$, that if $N$ is even

$$ x[n] = \frac1N \sum\limits_{k=-\frac{N}{2}}^{\frac{N}{2}-1} X[k] \ e^{j 2 \pi nk/N} $$

if $N$ is odd, then

$$ x[n] = \frac1N \sum\limits_{k=-\frac{N-1}{2}}^{\frac{N-1}{2}} X[k] \ e^{j 2 \pi nk/N} $$

and you can sorta plug in $n = f_\text{s} t$ to reconstruct bandlimited $x(t)$ outa $x[n]$.

in the $N$ even case, then you have an extra term at Nyquist, the $k=-\frac{N}{2}$ term, for that you cannot know both the amplitude and phase of that sinusoid. you must assume one or the other. often people only keep the $\cos(\pi f_\text{s} t)$ term at Nyquist.

$$ \begin{align} x[n] & = \frac1N \sum\limits_{k=-\frac{N}{2}}^{\frac{N}{2}-1} X[k] \ e^{j 2 \pi nk/N} \\ & = \frac1N \left( X[0] + X[N/2] \cos(\pi n) + \sum\limits_{k=1}^{\frac{N}{2}-1} X[k] e^{j 2 \pi nk/N} \ + \ X[-k] e^{-j 2 \pi nk/N} \right) \\ & = \frac1N \left( X[0] + X[N/2] \cos(\pi n) \right) \\ & \quad + \frac1N \sum\limits_{k=1}^{\frac{N}{2}-1} (\Re\{X[k]\} + j \Im\{X[k]\}) e^{j 2 \pi nk/N} \ + \ (\Re\{X[k]\} - j \Im\{X[k]\}) e^{-j 2 \pi nk/N} \\ & = \frac1N \left( X[0] + X[N/2] \cos(\pi n) \right) \\ & \quad + \frac1N \sum\limits_{k=1}^{\frac{N}{2}-1} 2\Re\{X[k]\} \frac{e^{j 2 \pi nk/N} + e^{-j 2 \pi nk/N}}{2} + j (2j) \Im\{X[k]\} \frac{e^{j 2 \pi nk/N} - e^{-j 2 \pi nk/N}}{2j} \\ & = \frac1N \left( X[0] + X[N/2] \cos(\pi n) \right) \\ & \quad + \frac2N \sum\limits_{k=1}^{\frac{N}{2}-1} \Re\{X[k]\} \frac{e^{j 2 \pi nk/N} + e^{-j 2 \pi nk/N}}{2} - \Im\{X[k]\} \frac{e^{j 2 \pi nk/N} - e^{-j 2 \pi nk/N}}{2j} \\ & = \frac1N \left( X[0] + X[N/2] \cos(\pi n) \right) \\ & \quad + \frac2N \sum\limits_{k=1}^{\frac{N}{2}-1} \Re\{X[k]\} \cos(2 \pi nk/N) - \Im\{X[k]\} \sin(2 \pi nk/N) \\ \end{align} $$

for $N$ odd, you can go through the same song and dance, but there is no Nyquist term and it comes out as

$$ x[n] = \frac1N X[0] + \frac2N \sum\limits_{k=1}^{\frac{N-1}{2}} \Re\{X[k]\} \cos(2 \pi nk/N) - \Im\{X[k]\} \sin(2 \pi nk/N) $$


for odd $N$, all of these discrete-time sinusoids can be understood as a properly-sampled bandlimited periodic, continuous-time, real signal, $x(t)$:

$$ x[n] \triangleq x(nT) = x(n/f_\text{s}) $$

or setting $ n \leftarrow f_\text{s} t $

$$ x(t) = \frac1N X[0] + \frac2N \sum\limits_{k=1}^{\frac{N-1}{2}} \Re\{X[k]\} \cos(2 \pi (k/N) f_\text{s} t) - \Im\{X[k]\} \sin(2 \pi (k/N) f_\text{s} t) $$

but when $N$ is even, the Nyquist term is a little more ambiguous:

$$ \begin{align} x(t) & = \frac1N \left( X[0] + X[N/2] \cos(2 \pi (f_\text{s}/2) t) \right) \\ & \quad + \frac2N \sum\limits_{k=1}^{\frac{N}{2}-1} \Re\{X[k]\} \cos(2 \pi k f_\text{s} t) - \Im\{X[k]\} \sin(2 \pi k f_\text{s} t) \\ & = \frac1N \left( X[0] + X[N/2] \cos(2 \pi (f_\text{s}/2) t) \right) \\ & \quad + \frac2N \sum\limits_{k=1}^{\frac{N}{2}-1} \Re\{X[k]\} \cos(2 \pi (k/N) f_\text{s} t) - \Im\{X[k]\} \sin(2 \pi (k/N) f_\text{s} t) \\ & = \frac1N \left( X[0] + X[N/2] \cos(2 \pi (f_\text{s}/2) t) + A_x \sin(2 \pi (f_\text{s}/2) t) \right) \\ & \quad + \frac2N \sum\limits_{k=1}^{\frac{N}{2}-1} \Re\{X[k]\} \cos(2 \pi (k/N) f_\text{s} t) - \Im\{X[k]\} \sin(2 \pi (k/N) f_\text{s} t) \\ \end{align} $$

where $A_x$ can be any number, because that term will be zero at the sampling instances, when $t = nT = n/f_\text{s}$.

looking at it from a magnitude/phase POV, for $N$ odd

$$ x(t) = \frac{X[0]}{N} + \frac2N \sum\limits_{k=1}^{\frac{N-1}{2}} |X[k]| \cos(2 \pi (k/N) f_\text{s} t + \arg\{X[k]\}) $$

and for $N$ even

$$ \begin{align} x(t) & = \frac{X[0]}{N} + \frac{X[N/2]}{N \cos(\theta)} \cos(2 \pi (f_\text{s}/2) t + \theta) \\ & \quad + \frac2N \sum\limits_{k=1}^{\frac{N}{2}-1} |X[k]| \cos(2 \pi (k/N) f_\text{s} t + \arg\{X[k]\}) \end{align}$$

where $$ \Re\{X[k]\} = |X[k]| \cos(\arg\{X[k]\}) $$ $$ \Im\{X[k]\} = |X[k]| \sin(\arg\{X[k]\}) $$

or $$ |X[k]| = \sqrt{\Re\{X[k]\}^2 + \Im\{X[k]\}^2} $$ $$ \arg\{X[k]\} = \operatorname{atan2}(\Im\{X[k]\}, \Re\{X[k]\}) $$

and $\theta$ is the phase of the Nyquist component and can be any real value except $\pm \frac{\pi}{2}$ or $\frac{\pi}{2}+ m \pi$ for integer $m$ (because you cannot divide by zero). the samples $x[n] \triangleq x(n/f_\text{s})$ will come out the same regardless of the phase of the Nyquist component as long as the amplitude of the component is adjusted accordingly by dividing by $\cos(\theta)$.

$\endgroup$
  • $\begingroup$ For real-valued sequences with $N$ even, you know both $\left|X[N/2]\right|$ and $\angle X[N/2]$. And $\angle X[N/2]=0$. $\endgroup$ – Gilles Mar 30 '16 at 21:18
  • $\begingroup$ $X[N/2]$ could be negative. then the angle is not zero. but the sinusoidal component at Nyquist could have virtually any phase, as long as the amplitude is adjusted so that it hits the same alternating points. a pure $\sin()$ term is not possible at Nyquist if $X[N/2] \ne 0$. $\endgroup$ – robert bristow-johnson Mar 31 '16 at 6:19
  • $\begingroup$ I don't agree with your statement that at $k=-N/2$ "you cannot know both the amplitude and phase" for real-valued sequences with $N$ even. Not only $\angle X[-N/2]=0$, but also $\angle X[0]$, $\angle X[N/2]$, and $\angle X[\pm N]$. And you also know their amplitudes. $\endgroup$ – Gilles Mar 31 '16 at 8:23
  • $\begingroup$ sorry, you're wrong on all counts. if $x[n]$ is real, then we know that $X[N/2]$ and $X[0]$ are real as well. but they can be positive or negative. how does that affect their angles? also try $$ \begin{align} x(t) & = \frac{X[0]}{N} + \frac{X[N/2]}{N \cos(\theta)} \cos(2 \pi (f_\text{s}/2) t + \theta) \\ & \quad + \frac2N \sum\limits_{k=1}^{\frac{N}{2}-1} |X[k]| \cos(2 \pi (k/N) f_\text{s} t + \arg\{X[k]\}) \end{align}$$ where $t = n/f_\text{s}$. do the samples come out differently as $\theta$ varies? this is why there is aliasing unless the sample rate exceeds twice the bandwidth. $\endgroup$ – robert bristow-johnson Mar 31 '16 at 17:54
  • 1
    $\begingroup$ what i am saying is that you do not know and you cannot know both the amplitude and the phase of a frequency component with frequency precisely at Nyquist. you can assume one and calculate the other based on that assumption. for all $|k| < N/2$, you know everything you need for each real sinusoid from the magnitude and angle of $X[k]$. but not at $|k| = N/2$. there, you don't know enough about the sinusoid to describe it completely. you know something about it, but not everything, and the reason is because of aliasing. $\endgroup$ – robert bristow-johnson Mar 31 '16 at 18:46

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.