Free Books    Mathematics of the DFT  

Appendix: Frequencies Representable
by a Geometric Sequence

Consider $ z_0\in{\bf C}$, with $ \vert z_0\vert=1$. Then we can write $ z_0$ in polar form as

$\displaystyle z_0\isdef e^{j\theta_0 } \isdef e^{j\omega_0 T}, $

where $ \theta_0 $, $ \omega_0$, and $ T$ are real numbers.

Forming a geometric sequence based on $ z_0$ yields the sequence

$\displaystyle x(t_n) \isdef z_0^n = e^{j\theta_0 n} = e^{j\omega_0 t_n} $

where $ t_n \isdef nT$. Thus, successive integer powers of $ z_0$ produce a sampled complex sinusoid with unit amplitude, and zero phase. Defining the sampling interval as $ T$ in seconds provides that $ \omega_0$ is the radian frequency in radians per second.

A natural question to investigate is what frequencies $ \omega_0$ are possible. The angular step of the point $ z_0^n$ along the unit circle in the complex plane is $ \theta_0 =\omega_0 T$. Since $ e^{j(\theta_0 n + 2\pi)} = e^{j\theta_0 n}$, an angular step $ \theta_0 >2\pi$ is indistinguishable from the angular step $ \theta_0 -2\pi$. Therefore, we must restrict the angular step $ \theta_0 $ to a length $ 2\pi $ range in order to avoid ambiguity.

Recall from §4.3.3 that we need support for both positive and negative frequencies since equal magnitudes of each must be summed to produce real sinusoids, as indicated by the identities

\begin{eqnarray*} \cos(\omega_0 t_n) &=& \frac{1}{2}e^{j\omega_0 t_n} + \frac{1}... ...& -\frac{j}{2}e^{j\omega_0 t_n} + \frac{j}{2}e^{-j\omega_0 t_n}. \end{eqnarray*}

The length $ 2\pi $ range which is symmetric about zero is

$\displaystyle \theta_0 \in [-\pi,\pi], $

which, since $ \theta_0 =\omega_0 T= 2\pi f_0T$, corresponds to the frequency range

\begin{eqnarray*} \omega_0 &\in& \left[-\frac{\pi}{T},\frac{\pi}{T}\right]\\ f_0&\in& \left[-\frac{f_s}{2},\frac{f_s}{2}\right]. \end{eqnarray*}

However, there is a problem with the point at $ f_0=\pm f_s/2$: Both $ +f_s/2$ and $ -f_s/2$ correspond to the same point $ z_0=-1$ in the $ z$-plane. Technically, this can be viewed as aliasing of the frequency $ -f_s/2$ on top of $ f_s/2$, or vice versa. The practical impact is that it is not possible in general to reconstruct a sinusoid from its samples at this frequency. For an obvious example, consider the sinusoid at half the sampling-rate sampled on its zero-crossings: $ \sin(\omega_0 t_n) = \sin(\pi n) \equiv 0$. We cannot be expected to reconstruct a nonzero signal from a sequence of zeros! For the signal $ \cos(\omega_0 t_n) = \cos(\pi n) = (-1)^n$, on the other hand, we sample the positive and negative peaks, and everything looks fine. In general, we either do not know the amplitude, or we do not know phase of a sinusoid sampled at exactly twice its frequency, and if we hit the zero crossings, we lose it altogether.

In view of the foregoing, we may define the valid range of ``digital frequencies'' to be

\begin{eqnarray*} \theta_0 &\in& [-\pi,\pi) \\ \omega_0 &\in& [-\pi/T,\pi/T) \\ f_0&\in& [-f_s/2,f_s/2). \end{eqnarray*}

While one might have expected the open interval $ (-\pi,\pi)$, we are free to give the point $ z_0=-1$ either the largest positive or largest negative representable frequency. Here, we chose the largest negative frequency since it corresponds to the assignment of numbers in two's complement arithmetic, which is often used to implement phase registers in sinusoidal oscillators. Since there is no corresponding positive-frequency component, samples at $ f_s/2$ must be interpreted as samples of clockwise circular motion around the unit circle at two points per revolution. Such signals appear as an alternating sequence of the form $ c(-1)^n$, where $ c$ can be complex. The amplitude at $ -f_s/2$ is then defined as $ \vert c\vert$, and the phase is $ \angle c$.

We have seen that uniformly spaced samples can represent frequencies $ f_0$ only in the range $ [-f_s/2,f_s/2)$, where $ f_s$ denotes the sampling rate. Frequencies outside this range yield sampled sinusoids indistinguishable from frequencies inside the range.

Suppose we henceforth agree to sample at higher than twice the highest frequency in our continuous-time signal. This is normally ensured in practice by lowpass-filtering the input signal to remove all signal energy at $ f_s/2$ and above. Such a filter is called an anti-aliasing filter, and it is a standard first stage in an Analog-to-Digital (A/D) Converter (ADC). Nowadays, ADCs are normally implemented within a single integrated circuit chip, such as a CODEC (for ``coder/decoder'') or ``multimedia chip''.

Next Section:
Informal Derivation of Taylor Series
Previous Section:
Sampling Theorem