Calculation number and meaning of DFT

Question

I'm posting this question to both check my own understand of DFTs (I'm relatively new to the subject), and to ask a few questions at the bottom regarding the DFT and its output. If anything isn't allowed then just let me know.

If we have a continuous signal in the time domain, $x(t) = cos(2\pi f t)$, we need to convert it to a discrete time signal.

If we sample this signal at a rate $f_s$, which is the no. of samples taken per second, our equation becomes: $$x[n] = cos(2\pi f n T_s)$$ $$\Rightarrow x[n] = cos(\frac{2\pi f n}{f_s})$$ where n is the sample number.

If we wanted to find the spectrum of this sampled signal, we could use the DTFT which would give us a continuous and periodic output. But because we're working with computers, the output must be finite, so instead we use the DTF which will give us a sampled version of the DTFT output. The DFT is given by: $$X_k = \sum_{n=0}^{N-1} x_n . exp^{-j \frac{2\pi kn}{N}}$$ where N is the total number of samples, n is the sample of the input signal x[n], and k is the number of the frequency bin.

The frequency bin resolution is $\Delta f = \frac{f_s}{N}$, where N is the total no. of samples of x[n].

If we were to sample an input signal $x(t)$ with maximum frequency $f_{max}$, then by the Nyquist Sampling Theorem we want the sampling frequency $f_s = 2f_{max}$ to sample up to $f_{max}$ without aliasing.

I was wondering if my understanding of the DFT above is correct, and does this mean that, for each DFT bin, the DFT performs N summations and N multiplications to give the amplitude of the frequency at that DFT bin? And lastly, if I were to plot the amplitude vs frequency of the output of the DFT, would I only consider half of the spectrum (up to $\frac{f_s}{2}$) and then just double the amplitudes of the frequency bins below that?

Answer 1

I was wondering if my understanding of the DFT above is correct,

Yes. This all seems correct although I recommend looking closely at the case of a sine wave that does not line up exactly with a frequency bin. There is a lot of insights and learning in that one

and does this mean that, for each DFT bin, the DFT performs N summations and N multiplications to give the amplitude of the frequency at that DFT bin?

Don't confuse definition with implementation. You can certainly do it with N summations and N multiplications per bin, however there are algorithms that can do the same thing much more efficiently. Notably the FFT.

And lastly, if I were to plot the amplitude vs frequency of the output of the DFT, would I only consider half of the spectrum (up to fs2)

That's typically done for real valued input signals since the spectrum is conjugate symmetric. Most people omit the negative frequencies since it's redundant information.

and then just double the amplitudes of the frequency bins below that?

This depends a bit on your application and what you want to do with the graph. This would be misleading when plotting a transfer function but good for plotting a power spectrum.

Answer 2

Plain DFT performs N summations and N multiplications to give the amplitude of the frequency at that DFT bin but usually, we use FTT which is an algorithm for reduction of the number of multiplications. Since you project your signal on the complex exponent, your output is complex too. There are different ways to represent the output. You can decompose the spectrum to amplitude and phase (Bode plot) or just ignore the phase and plot only the amplitude.

For a real input signal, the spectrum should be symmetric around zero and you can present the right plane only but for a complex input signal, you have to represent both sides of the spectrum. Regarding doubling the amplitude, I am not sure that it is mandatory but it is a common practice.

Answer 3

For any finite length DFT, to prevent aliasing, the sampling rate needs to be above (not equal to) twice the highest frequency in the signal.