Analysis frequency of the DFT?

Question

So I'm reading Richard G. Lyons' book "Understanding Digital Signal Processing" and I've just started to make my way through the DFT chapter. While most of his examples and explanations make sense, I am a bit confused about one particular term he defined. This term is the "analysis frequency" defined as

$$f_\text{a} = \frac{mf_\text{s}} N$$

where $f_\text{s}$ is the sampling frequency, $m$ is the index of the current DFT term we're calculating, and $N$ is the length of the discrete, input signal $x[n]$.

So in the book it's stated that $f_\text{a}$ tells us, for each value of $m$, which specific frequency we're currently searching $x[n]$ for. And for each value of $m$ we've got a specific complex sinusoid that we're matching up with $x[n]$ point by point to calculate a single value for $X[m]$. The frequency of that complex sinusoid is said to be $f_\text{a}$ but when the sinusoid is written out explicitly, it does not seem to have the frequency one would expect.

Here are the specifics of the example in the book.

$$x_\text{c}(t) = \sin(2\pi \cdot 1000 \cdot t) + 0.5\sin(2\pi \cdot t + \frac{3\pi}4)$$ $$x[n] = x_\text{c}(n \, T_\text{s}) = \sin(2\pi \cdot 1000 \cdot n \, T_\text{s}) + 0.5\sin(2\pi n \, T_\text{s} + \frac{3\pi}4)$$ $$f_\text{s} \triangleq \frac{1}{T_\text{s}} = 8000 \text{ Hz}$$ $$N=8$$ $$f_\text{a} = \frac{1 \cdot 8000}8 = 1 \text{ kHz}$$ $$X[1]= \sum_{n=0}^7{x[n] \cos(2\pi \cdot n/8) - jx[n] \sin(2\pi \cdot n/8)}$$

So based on my understanding of the text, the $X[1]$ term is searching $x[n]$ to find frequency content at a frequency of $f_\text{a} = 1\text{ kHz}$. This is done by summing a point for point product of $x[n]$ with a complex sinusiod that has a frequency of $f_\text{a} = 1\text{ kHz}$. However, the sinusoid I wrote above doesn't appear to have that frequency.

So I guess my question is two fold. One, how do we come up with the idea of $f_\text{a}$ and how does it relate to the DFT? Second, why doesn't the complex sinusoid have the expected frequency? Is it because we're dealing with a discrete complex sinusoid?

If I have made any mistakes in understanding the problem or the concepts please let me know. I appreciate any help you guys can provide and if this post is too incoherent or "busy" then let me know and I'll try and fix it. Thanks in advance!

Answer 1

I will provide two interpretations of the DFT samples $X[k]$;

The first interpretation relies on the concept of an inner product, $\langle x(t), \phi_k(t) \rangle $, between the signal $x(t)$ and a base function $\phi_k(t)$ which measures and quantifies the amount of the base function $\phi_k(t)$ in the signal $x(t)$. This operation is essentially performing an analysis of $x(t)$.

When this interpretation is applied to the DFT, those discrete functions $\phi_k[n] = e^{j\frac{2 \pi}{N} k n}$ become the base functions (as complex exponentials of a specific frequency) of an orthonormal basis and those values $X[k]$ become the inner products between $x[n]$ and the complex exponentials; computing the amount of that particular base function in the signal $x[n]$. Note that the analysis is performed in the discrete-time sampled frequency $\omega_k$ and its equivalent continuous-time frequency $\Omega_k$ can be found from the sampling operation and frequency normalization, which provides the second interpretation below.

Consider a continuous-time bandlimited signal $x_\text{c}(t)$ which is sampled by $f_\text{s}$ samples per second, or equivalently by a sampling period of $T_\text{s} \triangleq \tfrac{1}{f_\text{s}}$ seconds per sample, without aliasing, to produce the discrete-time samples $x[n]$ of length $N$;

$$x[n] = x_\text{c}(n T_\text{s})$$

An $N$-point DFT of this sequence be defined as:

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

These DFT values, $X[k]$, can also be considered as the samples of the DTFT $X(e^{j \omega})$ associated with $x[n]$ as;

$$X[k] = X(e^{j \omega}) \bigg|_{\omega_k = \frac{2 \pi}{N}k}$$

The DTFT itself is a frequency scaled and repeated version of the original continuous time signal's continuous Fourier transform $X_\text{c}(j\Omega)$ as

$$X(e^{j \omega}) = \frac{1}{T_\text{s}} X_\text{c}\left(j \tfrac{\omega}{T_\text{s}} \right)$$

in the base period $-\pi \le \omega < \pi$

Therefore the corresponding continuous-time frequency (in Hz.) that a given DFT sample $X[k]$ resides can be found by the relation

$$f_k = \frac{f_\text{s}}{N} k$$

for $ -\tfrac{N}{2} \le k < \tfrac{N}{2}$. Note the use of negative $k$ values.

So your equation provides this frequency $f_k$ (saying $f_\text{a}$ to indicate its analysis nature) as an equivalent continuous-time frequency that's being analysed by the complex exponential base function $\phi_k[n]=e^{j\frac{2\pi}{N}k n}$ with a discrete-time frequency $\omega_k = \frac{2 \pi}{N} k$.

Note that the value of $f_\text{a}$ is obtained by considering the sampling operation applied on the continuous time-signal $x_\text{c}(t)$ that's used to obtain the samples $x[n]$

Answer 2

In discrete time, sins and cosines of all possible frequencies are NOT periodic for a given choice of sampling frequency $f_s$ and the number of samples under observation $N$.

For example at $Fs = 8000Hz$, $f_a = 1000$ (a multiple of $f_s/N$) is periodic:

On the other hand,$Fs = 8000Hz$, $f_a = 1500$ (not a multiple of $f_s/N$) is not periodic:

By definition DFT only considers periodic signals, in $N$ samples only $N$ possible periodic signals exist and they are multiple of $f_s/N$, i.e., $k f_s/N$. Note that as $k$ exceeds $N-1$, frequencies start to repeat.

This concept can be generalized to complex exponential by separately considering sine and cosines and trying out values of $f_a$.

Answer 3

Fourier's basic theorem is that any (non-pathological) waveform can be decomposed into the sum of sinusoids, even waveforms that look nothing like a sinusoid. In the finite-sized discrete case (DFT), there are a finite number of sinusoidal basis vectors, and any signal can be decomposed into them, including non-sinusoidal waveforms, as well as segments of sinusoidal waveforms of different frequencies from those of the basis vectors.

So your basic confusion might be in expecting the DFT to be a "search" for a single basis solution, instead of a decomposition into a bunch of sinusoids that individually might or might not resemble the input closely, or at all.

However, if there are some reasonably close matches among the basis sinusoids, searching x[i] of a DFT magnitude result might find the one with the closest match or fit, which, itself, again, need not be an exact match. So need not be your "expected" one.