Digital Signal Processing. The Scientist and Engineers Guide. Steven W. Smith

Subroutine called from Figure 33-7.

no

Chebyshev 4 filter?

8 9

The bilinear transform converts this into a s with the expression given in Eq. 33-10.

discrete system by replacing each This creates a z-domain transfer

Working through the long and placed in the standard form of identified as:

tedious algebra, this expression can be Eq. 33-3, and the recursion coefficients

T 2/D

2T 2/D T 2/D

( 8 & 2 M T 2 ) / D

(& 4 & 4 FT & M T 2 ) / D

EQUATION 33-12

Low-pass to low-pass transform. This is a method of changing the cutoff frequency of low-pass filters. The original filter has a cutoff frequency of unity, while the new filter has a cutoff frequency of W, in the range of 0 to B.

z & 1 6 z & 1 & k

1 & kz & 1

EQUATION 33-13

Low-pass to low-pass conversion. The recursion coefficients of the filter with unity cutoff are shown in italics. The coefficients of the low-pass filter with a cutoff frequency of W are in roman.

a0 ' ( a0 & a1k % a2k 2 ) / D

a1 ' (& 2a0k % a1 % a1k 2 & 2a2k ) / D a2 ' ( a0k 2 & a1k % a2 ) / D

b1 ' ( 2 k % b1 % b1k 2 & 2b2k ) / D b2 ' (& k 2 & b1k % b2 ) / D

EQUATION 33-14

Low-pass to high-pass transform. This substitution changes a low-pass filter into a high-pass filter. The cutoff frequency of the low-pass filter is one, while the cutoff frequency of the highpass filter is W.

z & 1 6 & z & 1 & k 1 % k z & 1

where:

k ' & cos( W/2 % 1/2 ) cos ( W/2 & 1/2 )

1/f noise: A type of random noise that increases in amplitude at lower frequencies. It is widely observable in physical systems, but not well understood. See white noise for comparison.

-3dB cutoff frequency: The division between a filter's passband and transition band. Defined as the frequency where the frequency response is reduced to -3dB (0.707 in amplitude).

"A" law: Companding standard used in Europe. Allows digital voice signals to be represented with only 8 bits instead of 12 bits by making the quantization levels unequal. See mu law for comparison.

AC: Alternating Current. Electrical term for the portion of a signal that fluctuates around the average (DC) value.

Accuracy: The error in a measurement (or a prediction) that is repeatable from trial to trial. Accuracy is limited by systematic (repeatable) errors. See precision for comparison.

Additivity: A mathematical property that is necessary for linear systems. If input a produces output p, and if input b produces output q, then an input of a+b produces an output of p+q.

Aliasing: The process where a sinusoid changes from one frequency to another as a result of sampling or other nonlinear action. Usually results in a loss of the signal's information.

Amplitude modulation: Method used in radio communication for combining an information carrying signal (such as audio) with a carrier wave. Usually carried out by multiplying the two signals.

Analysis: The forward Fourier transform; calculating the frequency domain from the time domain. See synthesis for comparison.

Antialias filter: Low-pass analog filter placed before an analog-to-digital converter. Removes

frequencies above one-half the sampling rate that would alias during conversion.

ASCII: A method of representing letters and numbers in binary form. Each character is assigned a number between 0 and 127. Very widely used in computers and communication.

Aspect ratio: The ratio of an image's width to its height. Standard television has an aspect ratio of 4:3, while motion pictures have an aspect ratio of 16:9.

Assembly: Low-level programming language that directly manipulates the registers and internal hardware of a microprocessor. See high-level language for comparison.

Associative property of convolution: Written as: ( a[n] tb[n] ) tc[n] ' a[n] t( b[n] tc[n]) . This is important in signal processing because it describes how cascaded stages behave.

Autocorrelation: A signal correlated with itself. Useful because the Fourier transform of the autocorrelation is the power spectrum of the original signal.

Backprojection: A technique used in computed tomography for reconstructing an image from its views. Results in poor image quality unless used with a more advanced method.

BASIC: A high-level programming language known for its simplicity, but also for its many weaknesses. Most of the programs in this book are in BASIC.

Basilar membrane: Small organ in the ear that acts as a spectrum analyzer. It allows different fibers in the cochlear nerve to be stimulated by different frequencies.

Basis functions: The set of waveforms that a decomposition uses. For instance, the basis functions for the Fourier decomposition are unity amplitude sine and cosine waves.

Bessel filter: Analog filter optimized for linear phase. It has almost no overshoot in the step response and similar rising and falling edges. Used to smooth time domain encoded signals.

Bidirectional filtering: Recursive method used to produce a zero phase filter. The signal is first filtered from left-to-right, then the intermediate signal is filtered from right-to-left.

Bilinear transform: Technique used to map the s-plane into the z-plane. Allows analog filters to be converted into equivalent digital filters.

Binning: Method of forming a histogram when the data (or signal) has numerous quantization levels, such as in floating point numbers.

Biquad: An analog or digital system with two poles and up to two zeros. Often cascaded to create a more sophisticated filter design.

Bit reversal sorting: Algorithm used in the FFT to achieve an interlaced decomposition of the signal. Carried out by counting in binary with the bits flipped left-for-right.

Blackman window: A smooth curve used in the design of filters and spectral analysis, calculated f r o m : 0.42 & 0.5 cos(2Bn /M ) % 0.08 cos(4Bn /M ) , where n runs from 0 to M.

Brightness: The overall lightness or darkness of an image. See contrast for comparison.

Butterfly: The basic computation used in the FFT. Changes two complex numbers into two other complex numbers.

Butterworth filter: Separates one band of frequencies from another; fastest roll-off while keeping the passband flat; can be analog or digital. Also called a maximally flat filter.

C: Common programming language used in science, engineering and DSP. Also comes in the more advanced C++.

C a r r i e r w a v e : T e r m u s e d i n a m p l i t u d e modulation of radio signals. Refers to the high frequency sine wave that is combined with a lower frequency information carrying signal.

Cascade: A combination of two or more stages where the output of one stage becomes the input for the next.

Causal signal: Any signal that has a value of zero for all negative numbered samples.

Causal system: A system that has a zero output until a nonzero value has appeared on its input (i.e., the input causes the output). The impulse response of a causal system is a causal signal.

Central Limit Theorem: Important theorem in statistics. In one form: a sum of many random numbers will have a Gaussian pdf, regardless of the pdf of the individual random numbers.

Cepstrum: A rearrangement of "spectrum." Used in homomorphic processing to describe the spectrum when the time and frequency domains are switched.

Charge coupled device (CCD): The light sensor in electronic cameras. Formed from a thin sheet of silicon containing a two-dimensional array of light sensitive regions called wells.

Chebyshev filter: Used for separating one band of frequencies from another. Achieves a faster roll-off than the Butterworth by allowing ripple in the passband. Can be analog or digital.

Chirp system: Used in radar and sonar. An impulse is converted into a longer duration signal before transmission, and compressed back into an impulse after reception.

Circular buffer: Method of data storage used in real time processing; each newly acquired sample replaces the oldest sample in memory.

Circular convolution: Aliasing that can occur in the time domain when frequency domain signals are multiplied. Each period in the time domain overflows into adjacent periods.

Circularity: The appearance that the end of a signal is connected to its beginning. This arises when considering only a single period of a periodic signal.

Classifiers: A parameter extracted from and representing a larger data set. For example: size of a region, amplitude of a peak, sharpness of an edge, etc. Used in pattern recognition.

Closing: A morphological operation defined as an erosion operation followed by a dilation operation.

Cochlea: Organ in the ear where sound in converted into a neural signal.

Cochlear nerve: Nerve that transmits audio information from the ear to the brain.

Coefficient-of-variation (CV): Common way of

stating the variation (noise) in data. Defined as: 100% × standard deviation / mean.

Commutative property of convolution: Written as: a[n] tb[n] ' b[n] ta[n] .

Companding: An "s" shaped nonlinearity allows voice signals to be digitized using only 8 bits instead of 12 bits. Europe uses "A" law, while the United States uses the mu law version.

Complex conjugation: Changing the sign of the imaginary part of a complex number. Often denoted by a star placed next to the variable. Example: if A ' 3 % 2 j , then A ( ' 3 & 2 j .

Complex DFT: The discrete Fourier transform using complex numbers. A more complicated and powerful technique than the real DFT.

Complex exponential: A complex number of the form: e a % bj . They are useful in engineering and science because Euler's relation allows them to represent sinusoids.

Complex Fourier transform: Any of the four members of the Fourier transform family written using complex numbers . See real Fourier transform for comparison.

Complex numbers: The real numbers (used in everyday math) plus the imaginary numbers (numbers containing the term j, where j ' & 1 ). Example: 3 % 2 j .

Complex plane: A graphical interpretation of complex numbers, with the real part on the x-axis and the imaginary part on the y-axis. This is analogous to the number line used with ordinary numbers.

Composite video: An analog television signal that contains synchronization pulses to separate the fields or frames.

Computed tomography (CT): A method used to reconstruct an image of the interior of an object from its x-ray projections. Widely used in medicine; one of the earliest applications of DSP. Old name: CAT scanner.

Continuous signal: A signal formed from continuous (as opposed to discrete) variables. Example: a voltage that varies with time. Often used interchangeably with analog signal.

Contrast: The difference between the bright-ness of an object and the brightness of the background. See brightness for comparison.

Converge: Term used in iterative methods to indicate that progress is being made toward a solution ("The algorithm is converging") or that a solution has been reached ("The algorithm has converged").

Convolution integral: Mathematical equation that defines convolution in continuous systems; analogous to the convolution sum for discrete systems.

Convolution kernel: The impulse response of a filter implemented by convolution. Also known as the filter kernel and the kernel.

Convolution sum: Mathematical equation defining convolution for discrete systems.

Cooley and Tukey: J.W. Cooley and J.W. Tukey, given credit for bringing the FFT to the world in a paper they published in 1965.

Correlation: Mathematical operation carried out the same as convolution, except a left-for-right flip of one signal. This is an optimal way to detect a known waveform in a signal.

Cross-correlation: The signal formed when one signal is correlated with another signal. Peaks in this signal indicate a similarity between the original signals. See also autocorrelation.

Cutoff frequency: In analog and digital filters, the frequency separating the passband from the transition band. Often measured where the amplitude is reduced to 0.707 (-3dB).

CVSD: Continuously Variable Slope Delta modulation, a technique used to convert a voice signal into a continuous binary stream.

DC: Direct Current. Electrical term for the portion of the signal that does not change with time; the average value or mean. See AC for comparison.

Decibel SPL: Sound Pressure Level. Log scale used to express the intensity of a sound wave: 0 dB SPL is barely detectable; 60 dB SPL is normal speech, and 140 dB SPL causes ear damage.

Decimation: Reducing the sampling rate of a digitized signal. Generally involves low-pass filtering followed by discarding samples. See interpolation for comparison.

Decomposition: The process of breaking a signal into two or more additive components. Often refers specifically to the forward Fourier transform,

breaking a signal into sinusoids.

Deconvolution: The inverse operation of convolution: if x[n] th[n] ' y[n] , find x[n] given only h[n] and y[n] . Deconvolution is usually carried out by dividing the frequency spectra.

Delta encoding: A broad term referring to techniques that store data as the difference between adjacent samples. Used in ADC, data compression and many other applications.

Delta function: A normalized impulse. The discrete delta function is a signal composed of all zeros, except the sample at zero that has a value of one. The continuous delta function is similar, but more abstract.

Delta-sigma: Analog-to-digital conversion method popular in voice and music processing. Uses a very high sampling rate with only a single bit per sample, followed by decimation.

Dependent variable: In a signal, the dependent variable depends on the value of the indepen-dent variable. Example: when a voltage changes over time, time is the independent variable and voltage is the dependent variable.

Difference equation: Equation relating the past and present samples of the output signal with past and present samples of the input signal. Also called a recursion equation.

Dilation: A morphological operation. When applied to binary images, dilation makes the objects larger and can combine disconnected objects into a single object.

Discrete cosine transform (DCT): A relative of the Fourier transform. Decomposes a signal into cosine waves. Used in data compression.

Discrete derivative: An operation for discrete signals that is analogous to the derivative for continuous signals. A better name is the first difference.

Discrete Fourier transform (DFT): Member of the Fourier transform family dealing with time domain signals that are discrete and periodic.

Discrete integral: Operation on discrete signals that is analogous to the integral for continuous signals. A better name is the running sum.

Discrete signal: A signal that uses quantized variables, such as a digitized signal residing in a computer.

Discrete time Fourier transform (DTFT):

Member of the Fourier transform family dealing with time domain signals that are discrete and aperiodic

Dithering: Adding noise to an analog signal before analog-to-digital conversion to prevent the digitized signal from becoming "stuck" on one value.

Domain: The independent variable of a signal. For example, a voltage that varies with time is in the time domain. Other common domains are the s p a t i a l d o m a i n ( s u c h a s i m a g e s ) a n d t h e frequency domain (the output of the Fourier transform).

Double precision: A standard for floating point notation that used 64 bits to represent each number. See single precision for comparison.

DSP microprocessor: A type of microprocessor designed for rapid math calculations. Often has a pipeline and/or Harvard architecture. Also called a RISC.

Dynamic range: The largest amplitude a system can deal with divided by the inherent noise of the system. Also used to indicate the number of bits u s e d i n a n A D C . C a n a l s o b e u s e d w i t h parameters other than amplitude; see frequency dynamic range.

Edge enhancement: Any image processing algorithm that makes the edges more obvious. Also called a sharpening operation.

Edge response: In image processing, the output of a system when the input is an edge. The sharpness of the edge response is often used as a measure of the resolution of the system.

Elliptic filter: Used to separate one band of frequencies from another. Achieves a fast roll-off by allowing ripple in the passband and the stopband. Can be used in both analog and digital designs.

End effects: The poorly behaved ends of a filtered signal resulting from the filter kernel not being completely immersed in the input signal.

Erosion: A morphological operation. When applied to binary images, erosion makes the objects smaller and can break objects into two or more pieces.

Euler's relation: The most important equation in complex math, relating sine and cosine waves with

complex exponentials.

Even/odd decomposition: A way of breaking a signal into two other signals, one having even symmetry, and the other having odd symmetry.

Even order filter: An analog or digital filter having an even number of poles.

False-negative: One of four possible outcomes of a target detection trial. The target is present, but incorrectly indicated to be not present.

False-positive: One of four possible outcomes of a target detection trial. The target is not present, but incorrectly indicated to be present.

Fast Fourier transform (FFT): An efficient algorithm for calculating the discrete Fourier transform (DFT). Reduces the execution time by hundreds in some cases.

FFT convolution: A method of convolving signals by multiplying their frequency spectra. So named because the FFT is used to efficiently move between the time and frequency domains.

Field: Interlaced television displays the even lines of each frame (image) followed by the odd lines. The even lines are called the even field, and the odd lines the odd field.

Filter kernel: The impulse response of a filter implemented by convolution. Also known as the convolution kernel and the kernel.

Filtered backprojection: A technique used in computed tomography for reconstructing an image from its views. The views are filtered and then backprojected.

Finite impulse response (FIR): An impulse response that has a finite number of nonzero values. Often used to indicate that a filter is carried out by using convolution, rather than recursion.

First difference: An operation for discrete signals that mimics the first derivative for continuous signals; also called the discrete derivative.

Fixed point: One of two common ways that computers store numbers; usually used to store integers. See floating point for comparison.

Flat-top window: A window used in spectral analysis; provides an accurate measurement of the amplitudes of the spectral components. The windowed-sinc filter kernel can be used.

Floating point: One of the two common ways that computers store numbers. Floating point uses a form of scientific notation, where a mantissa is raised to an exponent. See fixed point for comparison.

Forward transform: The analysis equation of the Fourier transform, calculating the frequency domain from the time domain. See inverse transform for comparison.

Fourier reconstruction: One of the methods used in computed tomography to calculate an image from its views.

Fourier series: The member of the Fourier transform family that deals with time domain signals that are continuous and periodic.

Fourier transform: A family of mathematical techniques based on decomposing signals into sinusoids. In the complex version, signals are decomposed into complex exponentials.

Fourier transform pair: Waveforms in the time and frequency domains that correspond to each other. For example, the rectangular pulse and the sinc function.

Fovea: A small region in the retina of the eye that is optimized for high-resolution vision.

Frame: An individual image in a television signal. The NTSC television standard uses 30 frames per second.

Frame grabber: A analog-to-digital converter used to digitize and store a frame (image) from a television signal.

Frequency domain: A signal having frequency as the independent variable. The output of the Fourier transform.

Frequency domain aliasing: Aliasing that occurs occurring in the frequency domain in response to an action taken in the time domain. Aliasing during sampling is an example.

Frequency domain convolution: Convolution carried out by multiplying the frequency spectra of the signals.

Frequency domain encoding: One of two main ways that information can be encoded in a signal. The information is contained in the amplitude, frequency, and phase of the signal's component sinusoids. Audio signals are the best example. See time domain encoding for comparison.

Frequency domain multiplexing: A method of combining signals for simultaneous transmis-sion by shifting them to different parts of the frequency spectrum.

Frequency dynamic range: The ratio of the largest to the lowest frequency a system can deal with. Analog systems usually have a much larger frequency dynamic range than digital systems.

Frequency resolution: The ability to distinguish or separate closely spaced frequencies.

Frequency response: The magnitude and phase changes that sinusoids experience when passing through a linear system. Usually expressed as a function of frequency. Often found by taking the Fourier transform of the impulse response.

Fricative: Human speech sound that originates as random noise from air turbulence, such as: s, f, sh, z, v and th. See voiced for comparison.

Full-width-at-half-maximum (FWHM): A common way of measuring the width of a peak in a signal. The width of the peak is measured at one-half of the peak's maximum amplitude.

Fundamental frequency: The frequency that a periodic waveform repeats itself. See harmonic for comparison.

Gamma curve: The mathematical function or look-up table relating a stored pixel value and the brightness it appears in a displayed image. Also called a grayscale transform.

Gaussian: A bell shaped curve of the general form: e x 2 . The Gaussian has many unique properties. Also called the normal distribution.

Gibbs effect: When a signal is truncated in one domain, ringing and overshoot appear at edges and corners in the other domain.

GIF: A common image file format using LZW (lossless) compression. Widely used on the world wide web for graphics. See TIFF and JPEG for comparison.

Grayscale: image A digital image where each pixel is displayed in shades of gray between black and white; also called a black and white image.

Grayscale stretch: Greatly increasing the contrast of a digital image to allow the detailed examination of a small range of quantization levels. Quantization levels outside of this range are displayed as saturated black or white.

Grayscale transform: The conversion function between a stored pixel value and the brightness that appears in a displayed image. Also called a gamma curve.

Halftone: A common method of printing images on paper. Shades of gray are created by various patterns of small black dots. Color halftones use dots of red, green and blue.

Hamming window: A smooth curve used in the design of filters and spectral analysis, calculated from: 0.54 & 0.46 cos(2Bn /M ) , where n runs from 0 to M.

Harmonics: The frequency components of a periodic signal, always consisting of integer multiples of the fundamental frequency. The fundamental is the first harmonic, twice this frequency is the second harmonic, etc.

Harvard Architecture: Internal computer layout where the program and data reside in separate memories accessed through separate busses; common in microprocessors used for DSP. See

Von Neumann Architecture for comparison.

High fidelity: High quality music reproduction, such as provided by CD players.

High-level language: Programming languages such as C, BASIC and FORTRAN.

High-speed convolution: Another name for FFT convolution.

Hilbert transformer: A system having the frequency response: Mag = 1, Phase = 90E, for all frequencies. Used in communications systems for modulation. Can be analog or digital.

Histogram equalization: Processing an image by using the integrated histogram of the image as the grayscale transform. Works by giving large areas of the image higher contrast than the small areas.

Histogram: Displays the distribution of values in a signal. The x-axis show the possible values the samples can take on; the y-axis indicates the number of samples having each value.

Homogeneity: A mathematical property of all linear systems. If an input x[n] produces an output of y[n] , then an input k x[n] produces an output of ky[n] , for any constant k.

Homomorphic: DSP technique for separating signals combined in a nonlinear way, such as by multiplication or convolution. The nonlinear