1
$\begingroup$

For the definition of the DFT we have

  • $X[k] = \sum\limits_{n=0}^{N-1}x[n]\exp(- \frac{2 \pi i \cdot n}{N} k)$

Let's say for simplification that $N$ is even.

Then

  • $k_{N/2-1} = \frac{N}{2}$ is considered as being the nyquist frequency
  • and $X[k_{N/2-1}] = 0$

What is the inuitve and mathematical reason for the two statements above?

I can see that for every value of $k$ the complex sinewaves are getting faster and at some point they are too fast and we get an aliasing effect. The sampling rate of the complex sine waves could be interpreted as $\frac{1}{N}$ and $N$ is mostly equal to the fundamental period of $x[n]$

$\endgroup$
1
  • 1
    $\begingroup$ For $N$ odd, then $\left\lfloor \frac{N}{2} \right\rfloor$ is not the index of the Nyquist frequency component, but just below it. $X[\frac{N-1}{2}]$ is just below Nyquist. $\endgroup$ Jan 26 at 8:12

4 Answers 4

3
$\begingroup$

The Nyquist bin $X[N/2]$ (for even $N$) is real-valued for real-valued sequences $x[n]$, but it is generally not equal to zero. It is given by

$$X[N/2]=\sum_{n=0}^{N-1}x[n]e^{-j\pi n}=\sum_{n=0}^{N-1}x[n](-1)^n$$

So you just change the sign of every other time domain sample and then you compute the sum. That value can be zero but it doesn't need to be zero.

The frequency index $N/2$ corresponds to Nyquist (for even $N$) because the related complex exponential has maximum frequency, i.e., it is an alternating sequence of constant amplitude:

$$e^{-\frac{j2\pi n}{N}\cdot\frac{N}{2}}=e^{-j\pi n}=(-1)^n$$

$\endgroup$
4
  • $\begingroup$ Okay makes sense thanks a lot! so it depends on the signal, what is the reason for the nyquist being at $N/2$? This part was not included in your answer $\endgroup$ Jan 25 at 9:21
  • 1
    $\begingroup$ @OuttaSpaceTime: $k=N/2$ corresponds to the maximum frequency possible for a discrete-time signal, namely a sequence with alternating sign: $e^{j2\pi n/N\cdot N/2}=(-1)^n$. $\endgroup$
    – Matt L.
    Jan 25 at 11:47
  • $\begingroup$ Also see my updated answer. $\endgroup$
    – Matt L.
    Jan 25 at 11:50
  • $\begingroup$ @OuttaSpaceTime: Not sure what this is about ... your second equation is correct, but I don't understand what it has to do with the question. $\endgroup$
    – Matt L.
    Jan 25 at 16:18
2
$\begingroup$

@OuttaSpaceTime To answer the question in your comment: For an even-N point DFT, the frequency associated with the k = N/2 DFT bin is Fs/2 where Fs is the data sample rate measured in hertz.

$\endgroup$
4
  • $\begingroup$ do you know the reason for this, it seems a little bit strange that the frequencies are mapped perfectly to each other though the k frequency value is going from 1 to N $\endgroup$ Jan 25 at 10:48
  • $\begingroup$ @OuttaSpaceTime, For an N-point DFT, the frequency associated with the kth DFT bin is k*Fs/N where Fs is the data sample rate measured in hertz. (And dimensionless integer k is in the range 0≤k≤N-1.) $\endgroup$ Jan 26 at 8:01
  • $\begingroup$ its adds value in the sense of pointing out that it is the case but not in getting a better understanding why it is the case $\endgroup$ Jan 26 at 8:20
  • $\begingroup$ @OuttaSpaceTime, please read my second “Answer” below. $\endgroup$ Jan 26 at 17:56
1
$\begingroup$

@OuttaSpaceTime, When we perform an N-point DFT we're simultaneously computing N correlations of the input signal with N different complex exponential sequences. So, ask yourself: What are the frequencies of those complex exponentials? That is, how many times do N samples of the kth complex exponential rotate around a circle (how many times do N samples of the kth complex exponential rotate through an angle of two pi radians)?

The k=1 complex exponential cycles around a circle one time over N samples. It’s ‘cyclic’ frequency is 1*Fs/N = Fs/N Hz where Fs is the data sample rate measured in hertz.

The k=2 complex exponential cycles around a circle two times over N samples. It’s ‘cyclic’ frequency is 2*Fs/N Hz

The final k=N-1 complex exponential cycles around a circle N-1 times over N samples. It’s ‘cyclic’ frequency is (N-1)*Fs/N Hz

So we can say, the frequency of the complex exponential for the kth DFT bin is k*Fs/N Hz.

To substantiate what I’m claiming here, the DFT can be viewed as a bank of complex-valued bandpass filters. That is, if you have a long sequence of x(n) input samples you can perform an N-point DFT of the x(0)-thru-x(N-1) input samples and retain the X(k) sample and assign it to be the first sample of an ‘R’ sequence. Next, perform an N-point DFT of the x(1)-thru-x(N) samples and retain the X(k) sample and assign it to be the second sample of the ‘R’ sequence. Then perform an N-point DFT of the x(2)-thru-x(N+1) samples and retain the X(k) sample and assign it to be the third sample of the ‘R’ sequence. And so on.

The ‘R’ sequence that you’ve computed is the output of a complex-valued bandpass filter whose center frequency is k*Fs/N Hz. (The frequency magnitude response of that bandpass filter is essentially sin(x)/x.)

$\endgroup$
3
  • $\begingroup$ Thanks! Isn't this not also connected to the normalization factor $1/N$ in the DFT because one period would have to be mapped to (0,1) so it can be compared to the correlated sine waves. $\endgroup$ Jan 26 at 20:55
  • $\begingroup$ How does the sampling rate Fs fall into place here? It is not a part of the complex sine waves argument $\endgroup$ Jan 26 at 20:58
  • $\begingroup$ @OuttaSpaceTime, please read my third “Answer” below. $\endgroup$ Jan 27 at 10:09
1
$\begingroup$

No, the 1/N factor in the definition of an inverse DFT is totally unrelated to an notion of "frequency" with regard to the DFT.

In signal processing the notion of "frequency" is the ratio $\text{angular change}\over\text{a time interval}$. In DSP, frequency is often measured in $\text{radians}\over\text{sample time}$, or just $\text{radians}\over\text{sample}$ where "sample" is the time duration between signal samples. In the DFT we specify a complex exponential as $e^{-j2{\pi}kn/N}$ measured in radians/sample. So..., what are the 'angular change' and the 'time interval' values (what is the "frequency") of our $e^{-j2{\pi}kn/N}$ complex exponential?

In our $e^{-j2{\pi}kn/N}$ complex exponential the angle changes by $2{\pi}k/N$ radians for each sample and the time duration between samples is $1/F_s$ seconds. So our complex exponential has a frequency of $\text{angular change}\over\text{a time interval}$=${2{\pi}k/N\over {1/F_s}}=2{\pi}kF_s/N$ radians per second. That frequency of our DFT's complex exponential measured in cycles per second is ${2{\pi}kF_s/N\over 2{\pi}}=kF_s/N$ Hz.

$\endgroup$
3
  • $\begingroup$ Ok this makes sense so far, I am wondering now that the frequency comes into play with the dft even though the definition of the DFT does not contain anything about time interverals, it is just $N$ time points around the complex unity circle, I mean when I plot their related cosine und sine waves their period will always take value within (0,1) while my signal can have periods way bigger an (0.1), when I see the DFT as the dot (inner) product I would expect both to have the same periods. This confuses me a little bit. $\endgroup$ Jan 27 at 11:04
  • $\begingroup$ It's clear now I was confusing the mapping a little bit, thanks the answer added great value! $\endgroup$ Jan 27 at 13:52
  • 1
    $\begingroup$ @OuttaSpaceTime, the DFT certainly is an interesting and useful mathematical process. Studying the DFT more and more is never a waste of time. $\endgroup$ Jan 28 at 10:31

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.