Digital Signal Processing relies heavily on "tricks". Effective use of DSP tricks can make a major difference in the amount of resources required to implement a given DSP function. A few well-placed tricks make the difference between an efficient system and an inefficient one. DSP textbooks cover some of the more important tricks, but experienced DSP'ers have absorbed a lot of tricks which simply don't appear in textbooks. After reviewing the basic tricks of DSP, we cover some of the lesser-known ones.
The Fast Fourier Transform (FFT) is the undisputed king of DSP tricks. The spectrum of a signal is of interest in many (if not most) DSP applications, and the Discrete Fourier Transform (DFT) is a discrete version of the famous Fourier Transform which allows us to calculate the spectrum of a sampled (discrete) signal. The DFT is straight-forward to calculate, but it has one problem: the calculations required are proportional to the square of the transform size, N. For DFT's of a small size, that doesn't matter much, but it quickly becomes opressive. Cooley and Tukey invented the FFT as a "fast" way of calculating the DFT. By "fast" we mean that the calculations required are proportional to N log N rather than N squared. That makes a big difference for large N. Although the FFT is difficult to understand, it is worth using in applications where you want to find the spectrum of more than just a few points. The FFT is discussed in virtually all DSP textbooks, so we won't dwell on it here. However, see dspGuru's FFT FAQ for some practical information on using the FFT.
The term "Multirate" simply means "multiple sampling rates". Why use multiple sampling rates? The most important reason is for efficiency of calculation and/or memory. In DSP, the calculations required to do some given amount of processing are proportional to the sampling rate; therefore, you would like to do calculations at the lowest sampling rate possible. But what is the lowest sampling rate possible? Well, the Nyquist theorem tells us that that sampling rate must be at least twice the bandwidth of the signal. Therefore, for maximum efficiency, you would like to do DSP processing at a rate which is a small multiple of the signal bandwidth.
Many signals start out as high-bandwidth, and turn into low-bandwidth as they get processed. In some systems, the converse is true: a signal starts out low-bandwidth and turns into high-bandwidth. By matching the sampling rate to the bandwidth of the signal at each stage of processing, you can do the processing with the maximum efficiency.
The term "decimation" means "reducing the sampling rate", and the term "interpolation" means "increasing the sampling rate". Compared to a straight-forward implementation, many DSP systems can be made more efficient by the use of decimation, interpolation, or both.
Mixing (heterodyning) is a process for changing the center frequency of a signal. Mixing goes hand-in-hand with multirate techniques to implement an efficient system. In order to reduce or increase the sampling rate, one often needs to change the center frequency of a signal so that it will be at the right frequency relative to a new sampling rate. For example, if we have a 100 Hz-wide signal centered at 1 kHz, sampled at a rate of 4 kHz, by mixing it to a center frequency of 50 Hz (so that is spans 0-100 Hz), we can decimate to reduce the sampling rate to 200 Hz, and the signal will not be aliased at the new sampling rate.
Mixing can be done two different ways: 1) in the straight-forward way, by multiplying the signal by a real or complex sine whose frequency is the mixing frequency, and 2) using aliasing.
In the first method, a real or complex sine is generated by function approximation, by iteration, or by some table-lookup method, and the sine is simply multiplied by the signal. This method is straight-forward, but can require a lot of calculation to generate the sine and to do the mixing multiplication. Often, mixing occurs in the high-rate portion of a DSP system, so very bit of calculation counts. Therefore, one common strategy is to use a small-size table-lookup for the mixing sine.
For more information on generating sines, see dspGuru's Sine Generation Tutorial. (TBD)
Aliasing is generally considered to be a "bad" thing in DSP, but under the right circumstances, it can provide a "free" mix, that is, a mix without having to do anything. However, it can only be used under very specific circumstances. (Often, part of the design of a DSP system is based on using aliasing as a free mix.). An alias mix occurs when a signal is decimated, and if it's center frequency is above the Nyquist frequency of the decimated sampling rate. For example, if a 100 Hz-wide signal is at a center frequency of 150 Hz (therefore spanning 100-200 Hz) and it is sampled at a 400 Hz rate, by decimating by a factor of 2, it now appears in the 0-100 Hz band at the resulting 200 Hz rate. (Note that there is also a "frequency reversal").
In the example above, we assumed that the band from 0-100 Hz had no signal in it prior to the decimation; if it had, then that signal would become combined with our band of interest, resulting in a corrupted signal. Therefore, the use of an alias mix requires not only that the center frequency of the signal of interest be compatible with the decimated sampling rate (to land within its Nyquist band), but also that the band that the signal will get aliased into is "clean" prior to the decimation. In most cases, such bands will have to be filtered prior to the decimation to assure that the signal off interest does not get corrupted.
This page is still Under Construction.
There's more to come.