Downsampling

From Wikipedia, the free encyclopedia
  (Redirected from Downsample)
Jump to: navigation, search

In signal processing, downsampling is the process of reducing the sampling rate of a signal. This is usually done to reduce the data rate or the size of the data. The downsampling factor is usually an integer or a rational fraction greater than one. This factor multiplies the sampling time or, equivalently, divides the sampling rate. For example, if 16-bit compact disc audio (sampled at 44,100 Hz) is downsampled to 22,050 Hz, the audio is said to be downsampled by a factor of 2. The bit rate is also reduced in half, from 1,411,200 bit/s to 705,600 bit/s, assuming that each sample retains its bit depth of 16 bits.

Downsampling by an integer factor[edit]

Downsampling by an integer factor, M, can be explained as a 2-step process, with an equivalent implementation that is more efficient:

  1. Reduce high-frequency components with a digital lowpass filter.
  2. Decimate the output sequence, keeping only every Mth output sample.

Decimation causes high-frequency signal components to be misinterpreted by subsequent users of the data, which is a form of distortion called aliasing. The first step, if necessary, is to suppress such components to an acceptable level of distortion. In this application, the filter is called an anti-aliasing filter, and its design is discussed below. Also see undersampling for information about downsampling bandpass functions and signals.

When the anti-aliasing filter is an IIR design, it relies on feedback from output to input, prior to the decimation step. With FIR filtering, it is an easy matter to compute only every Mth output. The calculation performed by a decimating FIR filter for the nth output sample is a dot product:

y[n] = \sum_{k=0}^{K-1} x[nM-k]\cdot h[k],

where the h[•] sequence is the impulse response, and K is its length.  x[•] represents the input sequence being downsampled. In a general purpose processor, after computing y[n], the easiest way to compute y[n+1] is to advance the starting index in the x[•] array by M, and recompute the dot product. In the case M=2, h[•] can be designed as a half-band filter, where almost half of the coefficients are zero and need not be included in the dot products.

Impulse response coefficients taken at intervals of M form a subsequence, and there are M such subsequences (phases) multiplexed together. The dot product is the sum of the dot products of each subsequence with the corresponding samples of the x[•] sequence. Furthermore, because of decimation by M, the stream of x[•] samples involved in any one of the M dot products is never involved in the other dot products. Thus M low-order FIR filters are each filtering one of M multiplexed phases of the input stream, and the M outputs are being summed. This viewpoint offers a different implementation that might be advantageous in a multi-processor architecture. In other words, the input stream is demultiplexed and sent through a bank of M filters whose outputs are summed. When implemented that way, it is called a polyphase filter.

For completeness, we now mention that a possible, but unlikely, implementation of each phase is to replace the coefficients of the other phases with zeros in a copy of the h[•] array, process the original x[•] sequence at the input rate, and decimate the output by a factor of M. The equivalence of this inefficient method and the implementation described above is known as the first Noble identity.[1]

Fig.1: Spectral effects of decimation compared on 3 popular frequency scale conventions

Anti-aliasing filter[edit]

The requirements of the anti-aliasing filter can be deduced from any of the 3 pairs of graphs in Fig. 1. Note that all 3 pairs are identical, except for the units of the abscissa variables. The upper graph of each pair is an example of the periodic frequency distribution of a sampled function, x(t), with Fourier transform, X(f). The lower graph is the new distribution that results when x(t) is sampled 3 times slower, or (equivalently) when the original sample sequence is decimated by a factor of M=3. In all 3 cases, the condition that ensures the copies of X(f) don't overlap each other is the same: B < \tfrac{1}{M}\cdot\tfrac{1}{2T},  where T is the interval between samples, 1/T is the sample-rate, and 1/2T is the Nyquist frequency. The anti-aliasing filter that can ensure the condition is met has a cutoff frequency less than \tfrac{1}{M} times the Nyquist frequency.[note 1]

The abscissa of the top pair of graphs represents the discrete-time Fourier transform (DTFT), which is a Fourier series representation of a periodic summation of X(f):

\underbrace{
\sum_{n=-\infty}^{\infty} \overbrace{x(nT)}^{x[n]}\ e^{-i 2\pi f nT}
}_{\text{DTFT}} = \frac{1}{T}\sum_{k=-\infty}^{\infty} X(f-k/T).

 

 

 

 

(Eq.1)

When T has units of seconds, \scriptstyle f has units of hertz. Replacing T with MT in the formulas above gives the DTFT of the decimated sequence, x[nM]:

\sum_{n=-\infty}^{\infty} x(n\cdot MT)\ e^{-i 2\pi f n(MT)} = \frac{1}{MT}\sum_{k=-\infty}^{\infty} X\left(f-\tfrac{k}{(MT)}\right).

The periodic summation has been reduced in amplitude and periodicity by a factor of M, as depicted in the second graph of Fig. 1.  Aliasing occurs when adjacent copies of X(f) overlap. The purpose of the anti-aliasing filter is to ensure that the reduced periodicity does not create overlap.

In the middle pair of graphs, the frequency variable, \scriptstyle f, has been replaced by normalized frequency, which creates a periodicity of 1 and a Nyquist frequency of ½. A common practice in filter design programs is to assume those values and request only the corresponding cutoff frequency in the same units. In other words, the cutoff frequency B_{max} = \tfrac{1}{M}\cdot\tfrac{1}{2T}, is normalized to TB_{max} = \tfrac{1}{M}\cdot\tfrac{1}{2} = \tfrac{0.5}{M}.   The units of this quantity are (seconds/sample)×(cycles/second) = cycles/sample.

The bottom pair of graphs represent the Z-transforms of the original sequence and the decimated sequence, constrained to values of complex-variable, z, of the form z=e^{i\omega}.  Then the transform of the x[n] sequence has the form of a Fourier series. By comparison with Eq.1, we deduce:


\sum_{n=-\infty}^{\infty} x[n]\ z^{-n} = \sum_{n=-\infty}^{\infty} x(nT)\ e^{-i\omega n} = \frac{1}{T}\sum_{k=-\infty}^{\infty} \underbrace{X\left(\tfrac{\omega}{2\pi T} - \tfrac{k}{T}\right)}_{X\left(\frac{\omega - 2\pi k}{2\pi T}\right)},

which is depicted by the fifth graph in Fig. 1.  Similarly, the sixth graph depicts:


\sum_{n=-\infty}^{\infty} x[nM]\ z^{-n} = \sum_{n=-\infty}^{\infty} x(nMT)\ e^{-i\omega n} = \frac{1}{MT}\sum_{k=-\infty}^{\infty} \underbrace{X\left(\tfrac{\omega}{2\pi MT} - \tfrac{k}{MT}\right)}_{X\left(\frac{\omega - 2\pi k}{2\pi MT}\right)}.

Downsampling by a rational fraction[edit]

Let M/L denote the downsampling factor, where M > L.

  1. Upsample by a factor of L
  2. Downsample by a factor of M

Upsampling requires a lowpass filter after increasing the data rate, and downsampling requires a lowpass filter before decimation. Therefore, both operations can be accomplished by a single filter with the lower of the two cutoff frequencies. For the M > L case, the anti-aliasing filter cutoff,  \tfrac{0.5}{M} cycles per intermediate sample, is the lower frequency.

See also[edit]

Notes[edit]

  1. ^ Realizable low-pass filters have a "skirt", where the response diminishes from near one to near zero. So in practice the cutoff frequency is placed far enough below the theoretical cutoff that the filter's skirt is contained below the theoretical cutoff.

Citations[edit]

  1. ^ Strang, Gilbert; Nguyen, Truong (1996-10-01). Wavelets and Filter Banks (2 ed.). Wellesley,MA: Wellesley-Cambridge Press. pp. 100–101. ISBN 0961408871. 

References[edit]

  • Oppenheim, Alan V.; Schafer, Ronald W.; Buck, John R. (1999). Discrete-Time Signal Processing (2nd ed.). Prentice Hall. ISBN 0-13-754920-2. 
  • Proakis, John G. (2000). Digital Signal Processing: Principles, Algorithms and Applications (3rd ed.). India: Prentice-Hall. ISBN 8120311299.