Sampling Theorem, FFT, Z-Transform and Convolution
Nyquist sampling, aliasing, DFT resolution and leakage, the FFT, Z-transform, poles, zeros, minimum phase and discrete convolution for CSIR NET geophysics.
- 21 min
On this page · 13 sections
Prerequisites
- Continuous and Discrete Signals, Fourier Series and Transforms — the comb-to-comb pair and the rule “discrete here, periodic there”.
- Auto- and Cross-Correlation and LTI Systems — convolution, impulse response, causality and stability.
- A/D and D/A Converters, Microprocessors and Microcontrollers — the hardware that samples and quantises a geophone voltage.
The Hook: A 50 Hz Hum That Was Not There
How CSIR NET asks it. Part C Geophysics: Nyquist frequency for a sample interval, the alias of a given frequency, frequency resolution of a record, operation counts for the FFT, Z-transforms with their regions of convergence, stability and minimum phase from pole–zero positions, and linear versus circular convolution of short sequences.
Sampling
Ideal sampling
Sampling at interval \( \Delta t \) multiplies \( x(t) \) by an impulse comb. Multiplication in time is convolution in frequency, and the comb’s transform is another comb with spacing \( f_s = 1/\Delta t \). So the spectrum of the sampled signal is the original spectrum repeated every \( f_s \):
$$X_s(f) = \frac{1}{\Delta t}\sum_{k=-\infty}^{\infty} X(f - k f_s).$$If \( X(f) \) is zero above \( f_{\max} \) and \( f_s > 2f_{\max} \), the copies do not overlap and the original can be recovered by a low-pass filter. If they overlap, the tails of neighbouring copies add into the base band: aliasing.
The sampling theorem
The theorem is usually credited to Nyquist and Shannon. Terms to keep apart:
| Term | Meaning |
|---|---|
| Nyquist frequency \( f_N \) | \( f_s/2 = 1/(2\Delta t) \): highest frequency a given sampling can represent |
| Nyquist rate | \( 2f_{\max} \): minimum sampling rate a given signal needs |
| Folding frequency | another name for \( f_N \): frequencies fold about it |
| Sample interval | \( f_s \) | Nyquist frequency |
|---|---|---|
| 0.5 ms | 2,000 Hz | 1,000 Hz |
| 1 ms | 1,000 Hz | 500 Hz |
| 2 ms | 500 Hz | 250 Hz |
| 4 ms | 250 Hz | 125 Hz |
| 1 h (tide gauge) | 1 per hour | 0.5 cycle per hour |
Why “strictly greater”. A sinusoid exactly at \( f_N \) may be sampled at its zero crossings and vanish. Sampling at exactly \( 2f_{\max} \) is not enough for a sinusoid at \( f_{\max} \).
Finding the alias
A frequency \( f \) sampled at \( f_s \) appears at
$$f_a = \lvert f - k f_s\rvert, \quad k = \text{integer that brings } f_a \text{ into } [0, f_N].$$Picture the frequency axis folded like a paper fan at \( f_N, 2f_N, 3f_N, \dots \); every frequency lands somewhere in \( [0, f_N] \).
| \( \Delta t \) | \( f_N \) | True \( f \) | Apparent \( f_a \) |
|---|---|---|---|
| 4 ms | 125 Hz | 200 Hz | \( 250 - 200 = 50 \) Hz |
| 2 ms | 250 Hz | 300 Hz | \( 500 - 300 = 200 \) Hz |
| 2 ms | 250 Hz | 600 Hz | \( 600 - 500 = 100 \) Hz |
| 4 ms | 125 Hz | 500 Hz | \( 500 - 2(250) = 0 \) Hz (appears as DC) |
Anti-alias filter. Aliasing cannot be removed after sampling, so field systems apply an analog low-pass filter before the digitiser, with its cut-off set below \( f_N \) (because real filters roll off gradually). Resampling a digital trace to a coarser interval needs a digital anti-alias filter first for the same reason.
Spatial aliasing
Receivers at spacing \( \Delta x \) sample the wavefield in space. The spatial Nyquist wavenumber is \( 1/(2\Delta x) \) cycles per metre. An event crossing the spread with apparent velocity \( v_{app} \) has horizontal wavelength \( v_{app}/f \), so it is aliased in space when
$$f > \frac{v_{app}}{2\Delta x}.$$Steep dips (low \( v_{app} \)) and high frequencies alias first. Spatially aliased events appear with the wrong dip on f–k plots and migrate wrongly.
Quantisation
Each sample is also rounded to a finite number of levels. For an ideal \( b \)-bit converter the dynamic range is about \( 6b \) dB (each bit doubles the number of levels, and \( 20\log_{10}2 \approx 6.02 \) dB). Quantisation adds a small, roughly white noise; sampling, if done above the Nyquist rate, loses nothing.
The Discrete Fourier Transform
For \( N \) samples \( x[0], \dots, x[N-1] \) at interval \( \Delta t \):
$$X[k] = \sum_{n=0}^{N-1} x[n]\,e^{-i2\pi kn/N}, \qquad x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k]\,e^{i2\pi kn/N}.$$| Quantity | Value |
|---|---|
| Record length | \( T = N\Delta t \) |
| Frequency spacing (bin width) | \( \Delta f = 1/(N\Delta t) = 1/T \) |
| Frequency of bin \( k \) | \( k\Delta f \) for \( k \le N/2 \); bins above \( N/2 \) are negative frequencies |
| Highest frequency | \( f_N = (N/2)\Delta f = 1/(2\Delta t) \) |
| Real input | \( X[N - k] = X^{*}[k] \): only \( N/2 + 1 \) bins are independent |
Short sample interval gives high Nyquist; long record gives fine frequency spacing. The two are controlled separately: \( \Delta t \) fixes \( f_N \), \( T \) fixes \( \Delta f \).
Resolution, zero padding and leakage
- Resolution (Rayleigh criterion). Two sinusoids closer than about \( 1/T \) in frequency cannot be separated in the spectrum of a record of length \( T \). In tidal analysis, separating M2 (period about 12.42 h) from S2 (12.00 h) needs \( T \ge 1/\lvert f_{S2} - f_{M2}\rvert \approx 355 \) h, roughly 15 days: the spring–neap cycle.
- Zero padding appends zeros before the DFT. It gives more closely spaced samples of the same underlying spectrum (smoother plot, better peak location) but does not improve resolution, which depends on the true record length.
- Leakage. The DFT treats the record as one period of a periodic signal. If the record does not hold a whole number of cycles of a sinusoid, the wrap-around has a jump, and energy leaks into neighbouring bins along the sinc side lobes of the boxcar window.
- Tapers (windows). Multiplying by a smooth window (Hann, Hamming, cosine taper) lowers the side lobes and reduces leakage, at the cost of a wider main lobe and so slightly poorer resolution.
| Window | Main lobe | Side lobes | Use |
|---|---|---|---|
| Boxcar (none) | narrowest | highest | well-separated equal-amplitude lines |
| Hann, Hamming | about twice as wide | much lower | general spectral analysis |
| Cosine (Tukey) taper | intermediate | intermediate | tapering trace ends before filtering |
Fast Fourier Transform (FFT)
A direct DFT needs about \( N^2 \) complex multiplications. The FFT, published by Cooley and Tukey in 1965, reorganises the sum. For \( N = 2^m \) (radix-2), split the sequence into even- and odd-indexed halves:
$$X[k] = E[k] + W_N^{k}\,O[k], \qquad X[k + N/2] = E[k] - W_N^{k}\,O[k], \qquad W_N = e^{-i2\pi/N}.$$Each half is an \( N/2 \)-point DFT, so the problem halves at every stage. There are \( \log_2 N \) stages, each of \( N/2 \) “butterflies” with one complex multiplication:
$$\text{direct DFT} \approx N^2, \qquad \text{radix-2 FFT} \approx \frac{N}{2}\log_2 N \quad \text{complex multiplications.}$$| \( N \) | \( N^2 \) | \( \frac{N}{2}\log_2 N \) | Speed-up |
|---|---|---|---|
| 256 | 65,536 | 1,024 | 64 |
| 1,024 | 1,048,576 | 5,120 | about 205 |
| 4,096 | 16,777,216 | 24,576 | about 683 |
Radix-2 needs \( N \) to be a power of 2, so traces are zero-padded up to the next power. The input or output appears in bit-reversed order in the in-place algorithm. The FFT computes exactly the DFT; it is not an approximation.
graph LR
A["Analog signal"] --> B["Anti-alias
low-pass filter"]
B --> C["Sample at Δt
and quantise"]
C --> D["Taper the ends"]
D --> E["Zero-pad to 2^m"]
E --> F["FFT"]
F --> G["Amplitude and
phase spectra"]Discrete Convolution
For sequences \( x \) (length \( N \)) and \( h \) (length \( M \)):
$$y[n] = \sum_k x[k]\,h[n - k], \qquad \text{length } N + M - 1.$$Convolution is polynomial multiplication. Write each sequence as a polynomial in a delay variable and multiply:
$$x = [2, 1, -1],\; h = [1, -1, 2]: \quad (2 + z - z^2)(1 - z + 2z^2) = 2 - z + 2z^2 + 3z^3 - 2z^4 .$$So \( y = [2, -1, 2, 3, -2] \). The “flip and slide” table method gives the same answer.
Circular convolution and the DFT
Multiplying two \( N \)-point DFTs and inverting gives circular convolution: the tail beyond \( N \) wraps around onto the start. With the example above and \( N = 3 \):
$$y_c = [2 + 3,\; -1 + (-2),\; 2] = [5, -3, 2].$$To get linear convolution with FFTs (“fast convolution”), zero-pad both sequences to at least \( N + M - 1 \) points before transforming. For long filters this is much faster than direct summation.
The Z-Transform
Definition and region of convergence
$$X(z) = \sum_{n=-\infty}^{\infty} x[n]\,z^{-n}, \qquad z \text{ complex}.$$The region of convergence (ROC) is the set of \( z \) for which the sum converges. It is an annulus centred on the origin and never contains a pole. The same \( X(z) \) with different ROCs describes different sequences, so the ROC is part of the answer.
| \( x[n] \) | \( X(z) \) | ROC |
|---|---|---|
| \( \delta[n] \) | 1 | all \( z \) |
| \( \delta[n - k] \) | \( z^{-k} \) | all \( z \) except 0 (for \( k > 0 \)) |
| \( u[n] \) | \( \dfrac{1}{1 - z^{-1}} \) | \( \lvert z\rvert > 1 \) |
| \( a^n u[n] \) (causal) | \( \dfrac{1}{1 - az^{-1}} \) | \( \lvert z\rvert > \lvert a\rvert \) |
| \( -a^n u[-n - 1] \) (anticausal) | \( \dfrac{1}{1 - az^{-1}} \) | \( \lvert z\rvert < \lvert a\rvert \) |
| \( n a^n u[n] \) | \( \dfrac{az^{-1}}{(1 - az^{-1})^2} \) | \( \lvert z\rvert > \lvert a\rvert \) |
| finite-length sequence | polynomial in \( z^{-1} \) (and \( z \)) | all \( z \) except possibly 0 or \( \infty \) |
| Sequence type | ROC |
|---|---|
| Right-sided (causal) | outside the outermost pole |
| Left-sided (anticausal) | inside the innermost pole |
| Two-sided | a ring between two poles |
Properties
| Property | Sequence | Z-transform |
|---|---|---|
| Linearity | \( ax + by \) | \( aX + bY \) |
| Delay | \( x[n - k] \) | \( z^{-k}X(z) \) |
| Convolution | \( x * h \) | \( X(z)H(z) \) |
| Time reversal | \( x[-n] \) | \( X(1/z) \) |
| Exponential weighting | \( a^n x[n] \) | \( X(z/a) \) |
| Multiplication by \( n \) | \( n\,x[n] \) | \( -z\,dX/dz \) |
| Initial value (causal) | \( x[0] \) | \( \lim_{z\to\infty}X(z) \) |
| Final value | \( x[\infty] \) | \( \lim_{z\to1}(1 - z^{-1})X(z) \), if poles of \( (1 - z^{-1})X \) lie inside the unit circle |
Link to the Fourier transform. On the unit circle \( z = e^{i\Omega} \), the Z-transform becomes the DTFT, provided the ROC includes \( \lvert z\rvert = 1 \). The DFT samples it at \( N \) equally spaced points round the circle. The mapping \( z = e^{s\Delta t} \) links it to the Laplace transform: the left half of the s-plane maps inside the unit circle.
Transfer functions, poles, zeros and stability
A recursive filter (difference equation) such as \( y[n] - 0.5\,y[n-1] = x[n] \) transforms to
$$H(z) = \frac{Y(z)}{X(z)} = \frac{1}{1 - 0.5z^{-1}} = \frac{z}{z - 0.5}: \quad \text{zero at } 0,\ \text{pole at } 0.5 .$$| Condition | Pole–zero statement |
|---|---|
| Causal | ROC outside the outermost pole |
| Stable | ROC includes the unit circle |
| Causal and stable | all poles inside the unit circle |
| FIR filter | no poles except at \( z = 0 \): always stable |
| IIR (recursive) filter | poles away from the origin: check them |
Inverse Z-transform for exams: partial fractions plus the table, or long division into a power series in \( z^{-1} \) (which yields the samples one by one).
Minimum, maximum and mixed phase
Among all causal, stable wavelets with the same amplitude spectrum, the minimum-phase one has its energy concentrated as early as possible (its partial energy \( \sum_{n=0}^{m}w[n]^2 \) rises fastest), and its inverse is also causal and stable. The maximum-phase one is its time reverse, with energy late. Anything in between is mixed phase.
The test depends on which convention the book uses for the delay operator:
| Convention | Wavelet polynomial | Minimum phase when |
|---|---|---|
| Engineering (DSP) | \( W(z) = w_0 + w_1 z^{-1} + w_2 z^{-2} + \cdots \) | all zeros inside \( \lvert z\rvert = 1 \) |
| Geophysics (Robinson–Treitel style, \( Z \) = unit delay) | \( W(Z) = w_0 + w_1 Z + w_2 Z^2 + \cdots \) | all roots outside \( \lvert Z\rvert = 1 \) |
Both describe the same physics. For a two-term dipole \( (a, b) \): minimum phase if \( \lvert a\rvert > \lvert b\rvert \) (bigger value first), maximum phase if \( \lvert a\rvert < \lvert b\rvert \). The dipoles \( (1, -0.5) \) and \( (-0.5, 1) \) have the same amplitude spectrum and the same autocorrelation; only the first is minimum phase. A wavelet made of \( m \) dipoles has \( 2^m \) versions with the same amplitude spectrum, obtained by reversing dipoles one at a time; exactly one is minimum phase.
Memory Tricks
Don’t Confuse
| Pair | First | Second |
|---|---|---|
| Nyquist frequency vs Nyquist rate | \( f_s/2 \), property of the sampling | \( 2f_{\max} \), property of the signal |
| Resolution vs bin spacing after padding | set by true record length \( T \) | made finer by zero padding, no new information |
| Leakage vs aliasing | non-integer cycles in the window; fixed by tapering | sampling too slowly; fixed only by filtering before sampling |
| Linear vs circular convolution | length \( N + M - 1 \) | length \( N \), tail wraps round |
| DFT vs FFT | the transform | an algorithm that computes it exactly |
| Causal ROC vs stable ROC | outside outermost pole | includes the unit circle |
| Engineering vs geophysics minimum phase | zeros inside \( \lvert z\rvert = 1 \) (in \( z^{-1} \)) | roots outside \( \lvert Z\rvert = 1 \) (in \( Z \)) |
Common Mistakes
Practice
All questions below are original practice questions written for this page. They are not from any CSIR NET paper.
Level 1: Foundation
- What is the Nyquist frequency for a 4 ms sample interval?
- What is the length of the linear convolution of a 50-sample trace with a 30-sample filter?
- Where must the poles of a causal, stable discrete-time system lie?
Answers
- 125 Hz, since \( 1/(2 \times 0.004) = 125 \).
- 79 samples (\( 50 + 30 - 1 \)).
- Strictly inside the unit circle, \( \lvert z\rvert < 1 \) (engineering \( z^{-1} \) convention).
Level 2: Part B Style
Practice Q1. A 340 Hz signal is digitised at a 2.5 ms sample interval without an anti-alias filter. It appears in the digital record at:
(a) 340 Hz (b) 200 Hz (c) 140 Hz (d) 60 Hz
Answer: (d) 60 Hz
\( f_s = 1/0.0025 = 400 \) Hz, \( f_N = 200 \) Hz. 340 Hz is above \( f_N \), so it folds to \( \lvert 340 - 400\rvert = 60 \) Hz. Equivalently, it lies 140 Hz above \( f_N \) and folds to \( 200 - 140 = 60 \) Hz. (a) ignores aliasing. (b) is the Nyquist frequency itself. (c) is \( 340 - 200 \), the distance above \( f_N \) rather than the folded frequency.
Practice Q2. A trace of 512 samples at 4 ms is transformed with the DFT. The frequency spacing of the spectrum is closest to:
(a) 0.24 Hz (b) 0.49 Hz (c) 0.98 Hz (d) 125 Hz
Answer: (b) 0.49 Hz
\( T = 512 \times 0.004 = 2.048 \) s, so \( \Delta f = 1/T \approx 0.488 \) Hz. (c) uses 256 samples (half the record). (a) uses \( 1/(2T) \). (d) is the Nyquist frequency. There are \( 512/2 + 1 = 257 \) independent bins from 0 to 125 Hz.
Practice Q3. For \( x[n] = (0.8)^n u[n] \), which is correct?
(a) \( X(z) = 1/(1 - 0.8z^{-1}) \), ROC \( \lvert z\rvert > 0.8 \); the DTFT exists (b) \( X(z) = 1/(1 - 0.8z^{-1}) \), ROC \( \lvert z\rvert < 0.8 \); the DTFT exists (c) \( X(z) = 1/(1 - 0.8z) \), ROC \( \lvert z\rvert > 1.25 \); the DTFT does not exist (d) \( X(z) = 0.8/(1 - z^{-1}) \), ROC \( \lvert z\rvert > 1 \)
Answer: (a)
\( \sum_{n\ge0}(0.8z^{-1})^n = 1/(1 - 0.8z^{-1}) \) converges for \( \lvert z\rvert > 0.8 \). That ROC contains the unit circle, so the DTFT exists (the sequence is absolutely summable). (b) is the ROC of an anticausal sequence. (c) uses \( z \) instead of \( z^{-1} \). (d) confuses it with a scaled step.
Practice Q4. For a 4,096-point transform, the ratio of complex multiplications needed by a direct DFT to those needed by a radix-2 FFT is about:
(a) 12 (b) 341 (c) 683 (d) 4,096
Answer: (c) about 683
Direct: \( N^2 = 16{,}777{,}216 \). FFT: \( (N/2)\log_2 N = 2{,}048 \times 12 = 24{,}576 \). Ratio \( = 2N/\log_2 N = 8{,}192/12 \approx 683 \). (b) uses \( N\log_2 N \) for the FFT. (a) is \( \log_2 N \). (d) is \( N \).
Level 3: Part C Style
Practice Q5. \( x = [1, -2, 3] \) and \( h = [2, 1, -1] \), both starting at \( n = 0 \). Which pair gives the 5-point linear convolution and the 3-point circular convolution, in that order?
(a) \( [2, -3, 3, 5, -3] \) and \( [7, -6, 3] \) (b) \( [2, -3, 3, 5, -3] \) and \( [2, -3, 3] \) (c) \( [2, -3, 7, 5, -3] \) and \( [7, -6, 7] \) (d) \( [-1, 3, -3, -1, 6] \) and \( [-2, 9, -3] \)
Answer: (a)
Linear: \( (1 - 2z + 3z^2)(2 + z - z^2) = 2 - 3z + 3z^2 + 5z^3 - 3z^4 \), so \( [2, -3, 3, 5, -3] \). Check the middle term: \( x[0]h[2] + x[1]h[1] + x[2]h[0] = -1 - 2 + 6 = 3 \).
Circular (\( N = 3 \)): fold samples 3 and 4 back onto 0 and 1: \( [2 + 5, -3 - 3, 3] = [7, -6, 3] \).
(b) truncates instead of wrapping. (c) takes \( x[1]h[1] \) as \( +2 \) instead of \( -2 \) at \( n = 2 \). (d) multiplies by the reversed \( h = [-1, 1, 2] \), which computes a correlation, not a convolution. To get the linear result with FFTs, pad both to at least 5 points.
Practice Q6. An hourly sea-level record contains two diurnal oscillations with periods of 24.0 h and 25.0 h. Which statement is correct?
(a) Hourly sampling aliases both oscillations, so the analysis is impossible (b) The record must be at least about 25 days long to resolve the two peaks (c) A 3-day record is enough if it is zero-padded to 30 days (d) The record must be at least 25 h long, one period of the slower oscillation
Answer: (b)
\( f_1 = 1/24 \approx 0.04167 \) cph and \( f_2 = 1/25 = 0.04 \) cph. Difference \( = 1/24 - 1/25 = 1/600 \) cph. Rayleigh criterion: \( T \ge 600 \) h \( = 25 \) days.
(a) is wrong: the Nyquist frequency of hourly data is 0.5 cph, far above 0.04 cph. (c) is wrong: zero padding interpolates the spectrum but does not improve resolution. (d) gives one cycle of one oscillation, which says nothing about separating two close frequencies.
Practice Q7. A causal filter has \( H(z) = \dfrac{1 - 2z^{-1}}{1 - 0.5z^{-1}} \). Consider:
- The filter is stable.
- The filter is minimum phase.
- \( \lvert H(e^{i\Omega})\rvert = 2 \) at every frequency.
- Its causal inverse is stable.
Which are correct?
(a) 1 and 2 only (b) 1 and 3 only (c) 1, 3 and 4 only (d) 2, 3 and 4 only
Answer: (b) 1 and 3 only
Pole at \( z = 0.5 \), zero at \( z = 2 \).
- True. Causal with its only pole inside the unit circle.
- False. In the \( z^{-1} \) convention, minimum phase needs zeros inside the unit circle; this zero is at 2.
- True. Write \( 1 - 2z^{-1} = -2z^{-1}(1 - 0.5z) \). On the unit circle \( \lvert 1 - 0.5e^{i\Omega}\rvert = \lvert 1 - 0.5e^{-i\Omega}\rvert \), so \( \lvert H\rvert = 2 \) everywhere: a scaled all-pass filter. Check: \( \Omega = 0 \) gives \( \lvert -1/0.5\rvert = 2 \); \( \Omega = \pi \) gives \( 3/1.5 = 2 \).
- False. The inverse \( (1 - 0.5z^{-1})/(1 - 2z^{-1}) \) has a pole at 2; made causal, it is unstable. This is exactly why non-minimum-phase wavelets cannot be inverted by a causal, stable filter.
Quick Revision Table
| Idea | Fact or formula |
|---|---|
| Sampled spectrum | copies of \( X(f) \) every \( f_s = 1/\Delta t \) |
| Sampling theorem | \( f_s > 2f_{\max} \); sinc interpolation recovers \( x(t) \) |
| Nyquist frequency | \( f_N = 1/(2\Delta t) \): 4 ms → 125 Hz; 2 ms → 250 Hz |
| Alias | \( f_a = \lvert f - kf_s\rvert \) in \( [0, f_N] \) |
| Spatial aliasing | \( f > v_{app}/(2\Delta x) \) |
| Quantisation | about 6 dB dynamic range per bit |
| DFT | \( X[k] = \sum x[n]e^{-i2\pi kn/N} \); \( \Delta f = 1/(N\Delta t) \) |
| Resolution | about \( 1/T \); zero padding does not improve it |
| Leakage | non-integer cycles in window; reduce with tapers |
| FFT | \( (N/2)\log_2 N \) vs \( N^2 \); exact, needs \( N = 2^m \) for radix-2 |
| Convolution | polynomial product; length \( N + M - 1 \) |
| Circular convolution | DFT product; pad to \( \ge N + M - 1 \) for linear result |
| Z-transform | \( X(z) = \sum x[n]z^{-n} \); delay \( z^{-k} \); convolution → product |
| \( a^n u[n] \) | \( 1/(1 - az^{-1}) \), \( \lvert z\rvert > \lvert a\rvert \) |
| Causal + stable | all poles inside \( \lvert z\rvert = 1 \) |
| Minimum phase | zeros inside (in \( z^{-1} \)); dipole \( (a, b) \) with \( \lvert a\rvert > \lvert b\rvert \) |
Key Takeaways
What’s Next
- Filters, Deconvolution and Fractal Analysis: designing filters, inverting wavelets, and describing signals that have no characteristic scale.
- Fourier Transforms, Lock-in Detection, Box-car Integration and Modulation: the Physical Sciences view of sampling, aliasing and signal recovery.
- Signal Processing: back to the chapter overview.