Skip to content

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 read
  • Updated
On this page · 13 sections
  1. Prerequisites
  2. The Hook: A 50 Hz Hum That Was Not There
  3. Sampling
  4. The Discrete Fourier Transform
  5. Discrete Convolution
  6. The Z-Transform
  7. Memory Tricks
  8. Don’t Confuse
  9. Common Mistakes
  10. Practice
  11. Quick Revision Table
  12. Key Takeaways
  13. What’s Next

Prerequisites

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:

TermMeaning
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 frequencyanother name for \( f_N \): frequencies fold about it
Sample interval\( f_s \)Nyquist frequency
0.5 ms2,000 Hz1,000 Hz
1 ms1,000 Hz500 Hz
2 ms500 Hz250 Hz
4 ms250 Hz125 Hz
1 h (tide gauge)1 per hour0.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 ms125 Hz200 Hz\( 250 - 200 = 50 \) Hz
2 ms250 Hz300 Hz\( 500 - 300 = 200 \) Hz
2 ms250 Hz600 Hz\( 600 - 500 = 100 \) Hz
4 ms125 Hz500 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}.$$
QuantityValue
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.
WindowMain lobeSide lobesUse
Boxcar (none)narrowesthighestwell-separated equal-amplitude lines
Hann, Hammingabout twice as widemuch lowergeneral spectral analysis
Cosine (Tukey) taperintermediateintermediatetapering 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
25665,5361,02464
1,0241,048,5765,120about 205
4,09616,777,21624,576about 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] \)1all \( 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 sequencepolynomial in \( z^{-1} \) (and \( z \))all \( z \) except possibly 0 or \( \infty \)
Sequence typeROC
Right-sided (causal)outside the outermost pole
Left-sided (anticausal)inside the innermost pole
Two-sideda ring between two poles

Properties

PropertySequenceZ-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 .$$
ConditionPole–zero statement
CausalROC outside the outermost pole
StableROC includes the unit circle
Causal and stableall poles inside the unit circle
FIR filterno poles except at \( z = 0 \): always stable
IIR (recursive) filterpoles 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:

ConventionWavelet polynomialMinimum 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

PairFirstSecond
Nyquist frequency vs Nyquist rate\( f_s/2 \), property of the sampling\( 2f_{\max} \), property of the signal
Resolution vs bin spacing after paddingset by true record length \( T \)made finer by zero padding, no new information
Leakage vs aliasingnon-integer cycles in the window; fixed by taperingsampling too slowly; fixed only by filtering before sampling
Linear vs circular convolutionlength \( N + M - 1 \)length \( N \), tail wraps round
DFT vs FFTthe transforman algorithm that computes it exactly
Causal ROC vs stable ROCoutside outermost poleincludes the unit circle
Engineering vs geophysics minimum phasezeros 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

  1. What is the Nyquist frequency for a 4 ms sample interval?
  2. What is the length of the linear convolution of a 50-sample trace with a 30-sample filter?
  3. Where must the poles of a causal, stable discrete-time system lie?
Answers
  1. 125 Hz, since \( 1/(2 \times 0.004) = 125 \).
  2. 79 samples (\( 50 + 30 - 1 \)).
  3. 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:

  1. The filter is stable.
  2. The filter is minimum phase.
  3. \( \lvert H(e^{i\Omega})\rvert = 2 \) at every frequency.
  4. 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 \).

  1. True. Causal with its only pole inside the unit circle.
  2. False. In the \( z^{-1} \) convention, minimum phase needs zeros inside the unit circle; this zero is at 2.
  3. 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 \).
  4. 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

IdeaFact or formula
Sampled spectrumcopies 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) \)
Quantisationabout 6 dB dynamic range per bit
DFT\( X[k] = \sum x[n]e^{-i2\pi kn/N} \); \( \Delta f = 1/(N\Delta t) \)
Resolutionabout \( 1/T \); zero padding does not improve it
Leakagenon-integer cycles in window; reduce with tapers
FFT\( (N/2)\log_2 N \) vs \( N^2 \); exact, needs \( N = 2^m \) for radix-2
Convolutionpolynomial product; length \( N + M - 1 \)
Circular convolutionDFT 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 + stableall poles inside \( \lvert z\rvert = 1 \)
Minimum phasezeros inside (in \( z^{-1} \)); dipole \( (a, b) \) with \( \lvert a\rvert > \lvert b\rvert \)

Key Takeaways

What’s Next

Advertisement
Advertisement