1. Mathematical and Computational Foundations of DSP

Introduction and Context

Advanced digital signal processing (DSP) rests on a small number of mathematical ideas that recur throughout filtering, spectral analysis, estimation, communications, control, and machine learning. Discrete-time signals must be represented, manipulated, transformed, and implemented with finite computational resources. A strong foundation therefore requires more than memorizing transform pairs: it requires understanding how sampling creates a discrete representation, how linear time-invariant (LTI) systems operate, how convolution and transforms are related, and how numerical and computational constraints influence engineering decisions.

This chapter develops that foundation. It begins with discrete-time signals and systems, then examines sampling, convolution, LTI descriptions, the z-transform and DTFT, and the DFT and FFT. Matrix formulations provide an alternative viewpoint useful in estimation and numerical computation. The final sections address numerical stability, computational complexity, practical implementation, and an illustrative engineering case.

Learning Objectives

After completing this chapter, the reader should be able to:

1. Classify discrete-time signals and systems and express their basic properties mathematically.

2. Explain sampling, aliasing, reconstruction, and the role of anti-aliasing filters.

3. Derive and interpret linear convolution and the impulse response of an LTI system.

4. Relate the z-transform, DTFT, DFT, and FFT and identify their appropriate uses.

5. Formulate convolution and filtering using matrices.

6. Analyze computational complexity, finite precision, quantization, and numerical stability.

7. Select suitable DSP methods for practical engineering applications.

Discrete-Time Signals: Representation and Structure

A discrete-time signal is a sequence indexed by an integer, written as x[n], where n is usually a sample index. The notation does not imply that amplitude is quantized; a discrete-time signal may have continuous-valued samples. Quantization occurs when amplitudes are represented using a finite number of bits.

Common elementary sequences include the unit impulse δ[n], defined by δ[0]=1 and δ[n]=0 for n≠0; the unit step u[n], equal to one for n≥0 and zero otherwise; the exponential a^n; and the sinusoid A cos(ωn+φ). Every sequence can be represented through shifted impulses:

x[n] = Σ from k=-∞ to ∞ x[k]δ[n-k].

This representation is fundamental because an LTI system responds to each shifted impulse in a predictable way.

Signals may be finite- or infinite-duration, deterministic or random, periodic or aperiodic, and energy or power signals. A sequence is periodic if there exists a positive integer N such that x[n+N]=x[n] for every n. For a discrete-time sinusoid cos(ω0n), periodicity requires ω0/(2π) to be rational. If ω0/(2π)=p/q in lowest terms, the fundamental period is q. This differs from continuous-time intuition: not every frequency produces a periodic discrete-time sinusoid.

The energy and average power of a sequence are respectively

E = Σ |x[n]|²,

P = lim as N→∞ (1/(2N+1)) Σ from n=-N to N |x[n]|².

An energy signal has finite nonzero energy and zero average power; a power signal has finite nonzero average power and generally infinite energy. These classifications are useful in communications and spectral analysis.

Time shifting, time reversal, amplitude scaling, and modulation are basic operations. A shift x[n-n0] delays a sequence when n0 is positive, whereas x[n+n0] advances it. Multiplication by e^(jω0n) shifts a spectrum in frequency, a property central to modulation and multirate processing.

Systems and the LTI Viewpoint

A discrete-time system maps an input sequence x[n] into an output y[n]. Four properties are particularly important. A system is linear if the response to ax1[n]+bx2[n] is ay1[n]+by2[n]. It is time invariant if delaying the input delays the output by the same amount. It is causal if y[n] depends only on present and past input samples. It is BIBO stable if every bounded input produces a bounded output.

For an LTI system, the response to δ[n] is called the impulse response h[n]. Using impulse decomposition and linearity and time invariance,

y[n] = Σ from k=-∞ to ∞ x[k]h[n-k] = x[n]*h[n].

This is linear convolution. Equivalently, y[n]=Σ x[n-k]h[k]. The two forms are identical after a change of index, but the first often emphasizes the system response to each input sample.

For finite sequences, convolution can be computed by reversing one sequence, shifting it, multiplying pointwise, and summing. In implementation, direct convolution requires approximately MN multiplications for sequences of lengths M and N. For long sequences, transform-domain methods may be more efficient.

An LTI system is causal if h[n]=0 for n<0. It is BIBO stable if Σ|h[n]| is finite. Thus causality and stability are properties of the impulse response, not merely of an input-output example. For a finite-dimensional rational system, poles inside the unit circle generally indicate stability when the system is causal.

Difference equations provide another system description:

a0y[n]+a1y[n-1]+...+aNy[n-N] = b0x[n]+b1x[n-1]+...+bMx[n-M].

If a0 is nonzero, the equation can be solved recursively for y[n]. Systems containing feedback are recursive or IIR systems; systems without feedback are commonly FIR systems. FIR filters can be designed with exact finite-duration impulse responses and are inherently stable when implemented with finite coefficients, while IIR filters often achieve sharper responses with fewer coefficients but require greater care concerning poles and numerical effects.

Sampling, Reconstruction, and Aliasing

Sampling converts a continuous-time signal x_a(t) into x[n]=x_a(nT), where T is the sampling interval and fs=1/T is the sampling frequency. If the analog signal is bandlimited to frequencies below B hertz, ideal uniform sampling permits perfect reconstruction when fs>2B. This is the Nyquist sampling condition.

Sampling replicates the continuous-time spectrum at integer multiples of fs. If these replicas overlap, components from different frequencies become indistinguishable in the sampled data. This phenomenon is aliasing. Once aliasing has occurred, it cannot generally be removed by digital processing because the original frequency information has been irreversibly combined.

Before an analog-to-digital converter, an anti-aliasing low-pass filter limits the input bandwidth. In practice, the filter has a transition band, so the sampling frequency must exceed twice the nominal signal bandwidth by a margin. The converter also introduces amplitude quantization. For an ideal uniform quantizer with step size Δ, the quantization error is often modeled as a bounded error between -Δ/2 and Δ/2, although this model becomes unreliable for very small or highly structured signals.

Reconstruction uses a digital-to-analog converter followed by a reconstruction filter. The theoretical interpolation kernel for ideal bandlimited reconstruction is the sinc function. Practical systems approximate it using analog filters or digital interpolation stages.

A useful engineering distinction is that oversampling does not eliminate the need for filtering; it relaxes the analog filter transition-band requirement. In multirate DSP, decimation by an integer factor M requires low-pass filtering before downsampling, while interpolation by L requires insertion of zeros followed by low-pass filtering. Omitting the appropriate filter produces aliasing or imaging, respectively.

Frequency-Domain Descriptions

The z-transform of x[n] is

X(z)=Σ x[n]z^(-n),

for those values of z for which the sum converges. The set of convergence is the region of convergence (ROC). The ROC is essential: the same algebraic expression can represent different sequences depending on the ROC. For example, 1/(1-az^-1) represents a right-sided sequence when |z|>|a| and a left-sided sequence when |z|<|a|.

The z-transform converts convolution into multiplication:

Y(z)=X(z)H(z).

For rational systems, zeros are values of z that make the transform zero, and poles are values that make it unbounded. For a causal rational LTI system, the ROC lies outside the outermost pole. Stability requires that the unit circle be included in the ROC. Consequently, a causal rational system is stable when all poles lie strictly inside the unit circle.

The discrete-time Fourier transform (DTFT) is obtained by evaluating the z-transform on the unit circle:

X(e^jω)=Σ x[n]e^(-jωn).

It is periodic in ω with period 2π. The DTFT is a continuous function of frequency even though the signal is discrete in time. Time-domain convolution corresponds to multiplication of DTFTs, while multiplication in time corresponds to periodic convolution in frequency.

The DTFT is ideal for theoretical spectral analysis, but direct evaluation over many frequencies may be computationally expensive. The DFT samples the DTFT at N equally spaced frequencies:

X[k]=Σ from n=0 to N-1 x[n]e^(-j2πkn/N), k=0,...,N-1.

The inverse DFT is

x[n]=(1/N)Σ from k=0 to N-1 X[k]e^(j2πkn/N).

The DFT treats the finite data block as one period of a periodic sequence. This periodic-extension viewpoint explains circular convolution and spectral leakage. If a signal segment does not contain an integer number of sinusoidal cycles, its endpoints do not join smoothly under periodic extension, spreading energy across neighboring DFT bins. Window functions reduce sidelobes at the cost of wider main lobes and altered amplitude characteristics.

For two sequences, circular convolution is multiplication in the DFT domain. Linear convolution can be computed with DFTs by zero-padding sufficiently: for sequences of lengths M and N, an FFT length of at least M+N-1 prevents time-domain aliasing. Block methods such as overlap-add and overlap-save extend this idea to long streams.

The FFT and Computational Complexity

The DFT requires O(N²) arithmetic operations when computed directly. The fast Fourier transform (FFT) is not a different transform; it is a family of algorithms that computes the same DFT more efficiently. Radix-2 Cooley–Tukey decomposition factors an N-point transform into smaller transforms when N is a power of two, reducing complexity to O(N log2 N).

The gain is substantial for large N, but FFT selection involves more than asymptotic complexity. Memory access, cache behavior, real versus complex data, vectorization, parallel hardware, latency, numerical precision, and transform length all matter. A slightly longer transform may be faster on a particular processor if its factorization is more favorable.

Spectral interpretation also requires care. Frequency-bin spacing is fs/N, but this is not the same as guaranteed ability to resolve two nearby sinusoids. Resolution depends on observation duration, windowing, signal-to-noise ratio, and estimator choice. Zero-padding increases the density of plotted frequency samples; it does not increase the information contained in the original record.

Matrix Formulations of DSP Operations

Many DSP operations can be expressed using matrices. For a finite input vector x and FIR coefficient vector h, convolution can be written y=Hx, where H is a Toeplitz matrix. For example, with h=[h0,h1,h2] and an appropriately padded input,

H = [h0 0 0; h1 h0 0; h2 h1 h0; 0 h2 h1; 0 0 h2].

This formulation makes linearity explicit and is useful in least-squares filtering, system identification, inverse problems, and automatic differentiation.

Circular convolution corresponds to a circulant matrix. Circulant matrices are diagonalized by the DFT matrix F:

C = F^-1ΛF,

where Λ contains the DFT of the first column of C. This identity explains why FFT-based convolution is efficient: transformation diagonalizes the convolution operator, pointwise multiplication applies the diagonal operator, and the inverse transform returns to the time domain.

Least-squares problems often take the form min ||Ax-b||². The normal equations AᴴAx=Aᴴb are mathematically valid, but forming AᴴA can worsen the condition number approximately by squaring it. QR factorization or singular-value decomposition is usually more numerically reliable, especially for ill-conditioned problems. This principle is important when DSP is combined with adaptive filtering, parameter estimation, or compressed sensing.

Numerical Stability and Finite-Precision Effects

Digital computation uses finite word length. Quantization affects input samples, coefficients, states, and output values. In FIR filters, coefficient and round-off errors usually do not produce unbounded internal growth, but they can alter the frequency response. In IIR filters, round-off noise may circulate through feedback, and pole locations may shift enough to cause significant response changes or instability.

Direct-form implementations of high-order IIR filters can be poorly conditioned. Cascading second-order sections, with suitable scaling, is generally more robust. State-variable scaling prevents overflow, while saturation arithmetic can avoid wraparound but introduces nonlinear distortion. Floating-point arithmetic offers a wide dynamic range, whereas fixed-point arithmetic can provide predictable hardware cost and power consumption but requires explicit range and quantization analysis.

Numerical stability also concerns cancellation and ill-conditioned matrices. Subtracting nearly equal numbers can destroy significant digits. A stable algorithm controls error growth rather than merely producing a formally correct expression. Validation should include impulse, step, frequency-response, extreme-amplitude, and long-duration tests, preferably with a high-precision reference.

Practical and Professional Applications

These foundations support numerous systems. Audio equalizers use convolution or recursive filters; wireless receivers use sampling, digital downconversion, FFT-based channelization, and synchronization; radar and sonar use matched filtering and spectral processing; biomedical instruments use anti-aliasing, denoising, and feature extraction; image systems apply two-dimensional convolution and transforms; and embedded controllers use fixed-point filtering under strict latency and power constraints.

Engineering decisions involve trade-offs. A direct FIR implementation may be preferable when filter lengths are short and latency must be deterministic. FFT-based processing is attractive for long filters or large blocks but introduces block latency. IIR filters provide efficiency in computation and memory but require stability analysis. Higher sampling rates simplify analog filtering but increase data movement and power. These are system-level choices rather than purely mathematical ones.

Professional practice also requires traceability. Sampling rates, filter specifications, coefficient-generation methods, scaling assumptions, numerical formats, and test conditions should be documented. In safety-critical or regulated products, reproducibility, verification, and change control are as important as nominal signal quality.

Illustrative Case Study: Digital Vibration Monitoring

Background

Consider an illustrative industrial monitoring system for a motor whose vibration contains useful components up to 2 kHz. The system must detect emerging mechanical faults while operating on an embedded processor.

Situation and Problem

An accelerometer is connected to an ADC. The initial design samples at 3 kHz and applies a digital filter after conversion. Unexpected high-frequency components appear as low-frequency peaks, leading to false alarms.

Analysis

The sampling rate of 3 kHz gives a Nyquist frequency of 1.5 kHz, below the required 2 kHz bandwidth. Components above 1.5 kHz alias into the measured band. Digital filtering cannot recover the lost information because aliasing occurred before the samples were processed. In addition, the planned 4096-point spectrum has a bin spacing of approximately 0.73 Hz, but this does not by itself guarantee fault-resolution performance.

Approach and Solution

The design is changed to a 10 kHz sampling rate, preceded by an analog anti-aliasing filter whose passband extends to 2 kHz and whose stopband begins before 5 kHz. A digital band-limiting FIR filter is then applied. For computational efficiency, long records are processed using overlap-save FFT convolution. The processor uses fixed-point arithmetic, so coefficients and intermediate states are scaled and tested for overflow. A window is applied before spectral estimation, and calibration measurements are retained to distinguish sensor effects from mechanical changes.

Outcome

The revised system prevents the principal aliasing mechanism, reduces false spectral peaks, and permits repeatable comparison of vibration spectra over time. The FFT implementation meets the processor deadline, while fixed-point tests show acceptable noise and no overflow under specified operating conditions.

Learning Points

The case demonstrates that sampling, analog filtering, transform selection, windowing, complexity, and numerical representation must be considered together. A correct FFT cannot compensate for an inadequate sampling architecture, and a mathematically stable algorithm may still fail if implementation scaling is neglected.

Challenges, Limitations, and Common Mistakes

Several errors recur in DSP work. Treating the Nyquist rate as a complete sampling design ignores transition bands and analog imperfections. Confusing DTFT frequency continuity with DFT bin resolution leads to unjustified spectral claims. Interpreting zero-padding as added resolution overstates what the data contain. Using circular convolution when linear convolution is required creates wraparound artifacts. Applying an FFT without specifying normalization, window, record length, and sampling rate makes results difficult to reproduce.

Other mistakes include assuming every discrete sinusoid is periodic, ignoring the ROC in z-transform reasoning, using normal equations for badly conditioned estimation, implementing high-order IIR filters in a single direct form, and testing only nominal inputs. Numerical range, latency, memory, and hardware behavior should be included from the beginning of design.

Emerging Directions and Best Practices

Modern DSP increasingly combines classical transforms with heterogeneous computing, automatic code generation, GPU and FPGA acceleration, and machine-learning models. Differentiable signal-processing blocks allow filters and spectral operations to be optimized jointly with data-driven components. However, learned systems still depend on sound sampling, conditioning, and validation. An inaccurate front end can limit any downstream model.

Recommended practice is to define signal bandwidth and performance requirements first; select sampling and anti-aliasing provisions next; choose a representation—time, z-domain, frequency, or matrix—suited to the question; estimate computational and memory cost; analyze finite-precision effects; and validate against independent theoretical or high-precision results. Reproducible experiments should record sampling rate, transform length, window, scaling, coefficient format, and software or hardware configuration.

Chapter Summary

Discrete-time DSP represents signals as indexed sequences and systems as mappings between sequences. The LTI framework reduces system analysis to convolution with an impulse response, while causality and BIBO stability can be characterized through that response and, for rational systems, through poles and the ROC. Sampling requires adequate bandwidth limitation and anti-aliasing protection; once aliasing occurs, digital processing cannot generally reverse it.

The z-transform provides a general complex-frequency description, the DTFT describes spectral content continuously over normalized frequency, and the DFT provides finite, periodic-block spectral samples. The FFT computes the DFT efficiently, enabling practical long-record filtering and analysis. Matrix formulations reveal the structure of convolution and support estimation and inverse problems. Finally, finite precision, conditioning, scaling, memory, latency, and complexity determine whether a mathematically valid method is reliable in hardware or software.

Key Terms

Discrete-time signal: A sequence indexed by integer sample number.

Impulse sequence: δ[n], equal to one at n=0 and zero elsewhere.

LTI system: A system possessing both linearity and time invariance.

Impulse response: Output of an LTI system produced by δ[n].

Linear convolution: The sum that gives the output of an LTI system from x[n] and h[n].

Causality: Dependence of an output only on present and past inputs.

BIBO stability: Bounded-input, bounded-output behavior.

Sampling: Conversion of a continuous-time waveform into values at discrete times.

Aliasing: Irreversible spectral overlap caused by insufficient sampling.

Quantization: Mapping amplitudes to a finite set of numerical levels.

z-transform: Complex-frequency transform Σx[n]z^-n.

Region of convergence: Values of z for which a z-transform converges.

Pole: A value at which a rational transform becomes unbounded.

DTFT: Fourier transform of a discrete-time sequence as a continuous periodic frequency function.

DFT: Finite set of uniformly spaced frequency samples of a finite data block.

FFT: Efficient algorithm for computing the DFT.

Spectral leakage: Spreading of DFT energy caused by finite, nonperiodic observation.

Circular convolution: Convolution of periodic finite-length sequences.

Toeplitz matrix: Matrix with constant values along each diagonal, commonly representing linear convolution.

Condition number: Measure of sensitivity of a numerical problem to perturbations.

Review Questions

Short Answer Questions

1. State the condition under which a discrete-time sinusoid is periodic.

2. Define the impulse response of an LTI system.

3. Why is an anti-aliasing filter placed before an ADC?

4. Distinguish the DTFT from the DFT.

5. What does the ROC contribute to a z-transform description?

Long Answer Questions

1. Derive the convolution representation of an LTI system from impulse decomposition.

2. Explain sampling, spectral replication, aliasing, and practical reconstruction.

3. Compare FIR and IIR implementations with respect to stability, complexity, and numerical behavior.

4. Explain how zero-padding, windowing, and periodic extension affect DFT-based spectral analysis.

5. Discuss the relationship among DFT, circulant matrices, and FFT-based convolution.

Analytical / Application Questions

1. A vibration signal contains useful content to 2 kHz and is sampled at 3 kHz. Identify the fundamental design failure and propose a corrected acquisition strategy.

2. A high-order IIR filter exhibits unexpected instability in fixed-point hardware although its floating-point poles are inside the unit circle. Analyze possible causes and recommend implementation changes.

3. An engineer forms normal equations to estimate parameters from an ill-conditioned data matrix. Explain the numerical risk and select a more reliable alternative.

22. Multiple Choice Questions with Answers

Question 1

For a causal rational LTI system to be BIBO stable, which condition is required?

A. All zeros must lie outside the unit circle

B. The ROC must include the unit circle and poles must lie inside it

C. The ROC must exclude the unit circle

D. All poles must lie on the unit circle

Correct Answer: B. The ROC must include the unit circle and poles must lie inside it

Question 2

A signal sampled at 3 kHz contains a component at 2 kHz. What is the principal issue?

A. The component is guaranteed to be reconstructed exactly

B. The component is converted into a DC component

C. The component can alias into a lower frequency

D. The DFT automatically removes the component

Correct Answer: C. The component can alias into a lower frequency

Question 3

What is the main purpose of zero-padding before using an FFT for linear convolution?

A. To increase the analog bandwidth

B. To prevent circular wraparound from corrupting linear convolution

C. To remove quantization noise completely

D. To change an IIR filter into an FIR filter

Correct Answer: B. To prevent circular wraparound from corrupting linear convolution

Question 4

Which statement correctly distinguishes the DTFT from the DFT?

A. The DTFT is finite and nonperiodic in frequency

B. The DFT applies only to continuous-time signals

C. The DTFT is continuous in frequency, while the DFT gives finite frequency samples

D. The DFT cannot represent complex signals

Correct Answer: C. The DTFT is continuous in frequency, while the DFT gives finite frequency samples

Question 5

The direct computation of an N-point DFT has approximately which asymptotic complexity?

A. O(1)

B. O(log N)

C. O(N)

D. O(N²)

Correct Answer: D. O(N²)

Question 6

Why can zero-padding make a spectrum appear smoother without improving true frequency resolution?

A. It creates additional measured information

B. It samples the underlying spectral interpolation more densely

C. It removes the effects of the observation interval

D. It increases the sampling rate of the original analog signal

Correct Answer: B. It samples the underlying spectral interpolation more densely

Question 7

Which matrix most naturally represents finite linear convolution?

A. Diagonal matrix only

B. Toeplitz matrix

C. Identity matrix only

D. Orthogonal projection matrix only

Correct Answer: B. Toeplitz matrix

Question 8

Why are second-order-section cascades often preferred for high-order IIR filters?

A. They eliminate all coefficient quantization

B. They improve numerical robustness and control internal scaling

C. They always require fewer samples than an FIR filter

D. They make every filter noncausal

Correct Answer: B. They improve numerical robustness and control internal scaling

Question 9

What is the principal effect of spectral leakage in a finite-record DFT?

A. Energy from a component spreads across neighboring bins

B. All frequencies become zero

C. The sampling frequency doubles

D. The signal becomes time invariant

Correct Answer: A. Energy from a component spreads across neighboring bins

Question 10

Why can forming normal equations be numerically undesirable for an ill-conditioned least-squares problem?

A. It changes a real problem into a continuous-time problem

B. It approximately squares the condition number

C. It prevents any matrix multiplication

D. It guarantees rank deficiency in every case

Correct Answer: B. It approximately squares the condition number