4

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... N1, its DFT is given as

X[k]=N1n=0x[n]ej2π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... N1, then the DFT is given as

X[k]=N/21n=N/2y[n]ej2π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/2th sample the same as the N/2th 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?

2 Answers 2

3

The DFT (Discrete Fourier Transform) of an N-point sequence {x[n]} is given as: X[k]=N1n=0x[n]ej2πkn/N,k=0,1,,N1

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

x[n]=xr[n]+jxi[n],0nN1X[k]=Xr[k]+jXi[k],0kN1

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

Xr[k]=N1n=0[xr[n]cos(2πknN)+xi[n]sin(2πknN)]Xi[k]=N1n=0[xr[n]sin(2πknN)xi[n]cos(2πknN)] If the sequence {x[n]} is real-valued, this means x[n]=xr[n] as xi[n]=0. The DFT will then be expressed as:

X[k]=N1n=0x[n][cos(2πknN)jsin(2πknN)]

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

X(Nk)=X(k)=X(k)

  • 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 N1 but your k's shouldn't go up to N1 as it will be a waste of resources. X[k]=N1n=0y[n]ej2πkn/N

    For N even, 0kN/2 suffices. With the results from equation (3) you can get the remaining values from N/2+1 to N1 or from N/2+1 to 1.

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

  • However, for a real even sequence {y[n]}, 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.

9
  • 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?
    – GrowinMan
    Commented Apr 2, 2016 at 21:21
  • 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)?
    – GrowinMan
    Commented Apr 2, 2016 at 21:21
  • BTW sorry about the formatting. How do you add newlines to comments? Ending the line with two spaces doesn't seem to work.
    – GrowinMan
    Commented Apr 2, 2016 at 21:26
  • 1
    @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=mN/2 was done and also that y[n] is symmetric such that y[n]=y[Nn]. 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.
    – Gilles
    Commented Apr 2, 2016 at 22:16
  • 1
    Q2. Yes, not only that but also that |X(Nk)|=|X(k)| and X(Nk)=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.
    – Gilles
    Commented Apr 2, 2016 at 22:16
1

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]nZ

to another discrete and periodic sequence

X[k]=X[k+N]kZ

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]=n0+N1n=n0x[n] ej2πnk/N

x[n]=1Nk0+N1k=k0X[k] ej2πnk/N

n,n0,k,k0 can be any integers.

so the choice of k0=N2 comes from the convenience of pairing X[k] to X[k]. since, in general

X[k]={X[k]}+j{X[k]}

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

X[k]=X[k]={X[k]}j{X[k]}

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

x[n]=1NN21k=N2X[k] ej2πnk/N

if N is odd, then

x[n]=1NN12k=N12X[k] ej2πnk/N

and you can sorta plug in n=fst to reconstruct bandlimited x(t) outa x[n].

in the N even case, then you have an extra term at Nyquist, the k=N2 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(πfst) term at Nyquist.

x[n]=1NN21k=N2X[k] ej2πnk/N=1N(X[0]+X[N/2]cos(πn)+N21k=1X[k]ej2πnk/N + X[k]ej2πnk/N)=1N(X[0]+X[N/2]cos(πn))+1NN21k=1({X[k]}+j{X[k]})ej2πnk/N + ({X[k]}j{X[k]})ej2πnk/N=1N(X[0]+X[N/2]cos(πn))+1NN21k=12{X[k]}ej2πnk/N+ej2πnk/N2+j(2j){X[k]}ej2πnk/Nej2πnk/N2j=1N(X[0]+X[N/2]cos(πn))+2NN21k=1{X[k]}ej2πnk/N+ej2πnk/N2{X[k]}ej2πnk/Nej2πnk/N2j=1N(X[0]+X[N/2]cos(πn))+2NN21k=1{X[k]}cos(2πnk/N){X[k]}sin(2πnk/N)

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]=1NX[0]+2NN12k=1{X[k]}cos(2πnk/N){X[k]}sin(2π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]

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
9
  • \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
    Commented Mar 30, 2016 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 Commented Mar 31, 2016 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
    Commented Mar 31, 2016 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 Commented Mar 31, 2016 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 Commented Mar 31, 2016 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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