Discrete Signal Processing Fundamentals Roadmap: Sampling, Interpolation, DFT, Z-Transform, and Autocorrelation

Why Bundle the Fundamentals of Discrete Signal Processing?

When you cross over from continuous-time signal processing into the discrete-time world, you immediately get hit by a flood of similar-looking acronyms and formulas — sampling theorem → DTFT → DFT/FFT → Z-transform → interpolation → correlation → compression. Reading individual articles one at a time can leave you wondering how they all actually fit together.

This blog has been steadily building out the core discrete-DSP topics in dedicated articles. The six fundamental ones are:

1. https://yuhi-sa.github.io/en/posts/20260430_sampling_theorem/1/ — Sampling theorem, Nyquist frequency, and aliasing
2. https://yuhi-sa.github.io/en/posts/20260430_signal_interpolation/1/ — Signal reconstruction and interpolation (sinc / linear / spline)
3. https://yuhi-sa.github.io/en/posts/20260505_dtft_dft_fft/1/ — The relationship between DTFT, DFT, and FFT
4. https://yuhi-sa.github.io/en/posts/20260430_z_transform/1/ — The Z-transform, transfer functions, and pole-zero analysis
5. https://yuhi-sa.github.io/en/posts/20260429_autocorrelation/1/ — Autocorrelation and cross-correlation
6. https://yuhi-sa.github.io/en/posts/20260430_dct/1/ — The discrete cosine transform (DCT)

Each is self-contained, but they all share the same mathematical backbone: how to treat a continuous-time signal as a discrete sequence. This hub stitches those six together with the surrounding topics of filter design, time-frequency analysis, and the higher-level meta-roadmap, with the goal of giving you a single picture of how to navigate the first few months of discrete signal processing.

If you have already worked through the top-level roadmap, returning to https://yuhi-sa.github.io/en/posts/20260528_dsp_ml_roadmap/1/ makes it easier to see where this hub fits in the bigger picture.

1. Learning Roadmap by Level

The right reading order for discrete DSP depends on where you are starting from. Here are four tracks.

Level 1 — Complete beginner (little continuous-signal background)

Goal: understand the difference between continuous and discrete signals, and pick up the core vocabulary around the Nyquist frequency and aliasing.

1. https://yuhi-sa.github.io/en/posts/20260225_fft/1/ — Get comfortable with the frequency representation of discrete time via an FFT primer
2. https://yuhi-sa.github.io/en/posts/20260430_sampling_theorem/1/ — Sampling theorem, Nyquist, and aliasing
3. https://yuhi-sa.github.io/en/posts/20260225_moving_average/1/ — Experience discrete-time convolution through the moving average
4. https://yuhi-sa.github.io/en/posts/20260430_signal_interpolation/1/ — First encounter with sinc interpolation

Estimated time: 2–4 weeks. The goal is to be able to confidently draw a frequency axis with numpy.fft.fftfreq.

Level 2 — Continuous-to-discrete bridge (systematizing DTFT, DFT, Z-transform)

Goal: internalize the correspondence between continuous-time Fourier/Laplace and discrete-time DTFT/Z-transform.

1. https://yuhi-sa.github.io/en/posts/20260430_sampling_theorem/1/ — The spectrum-replication formula (Eq. (5))
2. https://yuhi-sa.github.io/en/posts/20260505_dtft_dft_fft/1/ — DTFT is a continuous-frequency representation; DFT discretizes it
3. https://yuhi-sa.github.io/en/posts/20260430_z_transform/1/ — The Z-transform extends DTFT to the complex z-plane
4. https://yuhi-sa.github.io/en/posts/20260228_fft_window_psd/1/ — Window functions and PSD estimation
5. https://yuhi-sa.github.io/en/posts/20260429_autocorrelation/1/ — The Wiener–Khinchin theorem (ACF ↔ PSD)

Estimated time: 4–6 weeks.

Level 3 — Python-implementation focus (hands-on with scipy/numpy APIs)

Goal: get fluent with the practical differences between scipy.fft and numpy.fft, resampling techniques, and fast correlation.

1. https://yuhi-sa.github.io/en/posts/20260430_signal_interpolation/1/ — scipy.signal.resample, resample_poly, decimate
2. https://yuhi-sa.github.io/en/posts/20260429_autocorrelation/1/ — numpy.correlate and FFT-based \(O(N\log N)\) computation
3. https://yuhi-sa.github.io/en/posts/20260430_dct/1/ — scipy.fft.dct, MDCT, 2-D DCT
4. https://yuhi-sa.github.io/en/posts/20260430_z_transform/1/ — scipy.signal.tf2zpk, freqz
5. https://yuhi-sa.github.io/en/posts/20260505_dtft_dft_fft/1/ — numpy.fft.fft and zero-padding

Estimated time: 6–8 weeks.

Level 4 — Applications (filter design, time-frequency analysis, ML preprocessing)

Goal: connect the fundamentals of discrete DSP into the filter-design hub, time-frequency hub, and ML time-series hub.

1. https://yuhi-sa.github.io/en/posts/20260522_filter_design_guide/1/ — Move on to the filter-design guide hub
2. https://yuhi-sa.github.io/en/posts/20260524_time_frequency_guide/1/ — Move on to the time-frequency analysis hub
3. https://yuhi-sa.github.io/en/posts/20260525_ml_timeseries_guide/1/ — Move on to the ML time-series hub
4. https://yuhi-sa.github.io/en/posts/20260528_dsp_ml_roadmap/1/ — The overall DSP/ML meta-roadmap

Estimated time: 8–12 weeks running in parallel.

2. Bridging Continuous Signals to Discrete Signals

Converting a continuous-time signal \(x(t)\) into a discrete-time sequence \(x[n]\) is the starting point of this entire series.

The sampling theorem (Nyquist–Shannon)

A band-limited signal \(x(t)\) (with \(X(f) = 0\) for \(|f| > f_{\max}\) ) can be perfectly recovered from samples \(\{x[n]\}\) provided the sampling rate \(f_s\) satisfies

\[f_s > 2 f_{\max}.\]

The full proof, the spectrum-replication formula, and implementation examples live in https://yuhi-sa.github.io/en/posts/20260430_sampling_theorem/1/.

Spectra before and after sampling

Domain	Representation	Periodicity
Continuous time	\(X(f)\)	Aperiodic
Discrete time	\(X(e^{j\omega})\) (DTFT)	\(2\pi\) -periodic (frequency wraps)
Discrete time + frequency	\(X[k]\) (DFT)	Period \(N\) in both time and frequency

The discretization from DTFT to DFT, and the FFT as a fast algorithm for it, are covered in detail in https://yuhi-sa.github.io/en/posts/20260505_dtft_dft_fft/1/.

Mitigating aliasing

The role of the analog LPF (the anti-aliasing filter) before sampling, and the AAF design used before downsampling, are discussed both in https://yuhi-sa.github.io/en/posts/20260430_sampling_theorem/1/ and — from a filter-design perspective — in https://yuhi-sa.github.io/en/posts/20260522_filter_design_guide/1/, https://yuhi-sa.github.io/en/posts/20260223_lowpass_filter/1/, and https://yuhi-sa.github.io/en/posts/20260226_butterworth/1/.

3. Frequency Representations of Discrete-Time Signals

The DTFT / DFT / FFT hierarchy

The relationship between the three can be summarized in one line each:

• DTFT: a continuous frequency representation of \(x[n]\) (\(\omega \in [0, 2\pi)\) )
• DFT: the finite-length version obtained by sampling the DTFT at \(N\) equally spaced points on the frequency axis
• FFT: an algorithm that computes the DFT in \(O(N \log N)\) time

See https://yuhi-sa.github.io/en/posts/20260505_dtft_dft_fft/1/ for the full treatment.

DTFT / DFT / FFT comparison table

Axis	DTFT	DFT	FFT
Time axis	Discrete \(n \in \mathbb{Z}\)	Discrete \(n = 0, \dots, N-1\)	Discrete \(n = 0, \dots, N-1\)
Frequency axis	Continuous \(\omega \in [0,2\pi)\)	Discrete \(k = 0, \dots, N-1\)	Discrete \(k = 0, \dots, N-1\)
Computational cost	Analytical (closed form)	\(O(N^2)\)	\(O(N \log N)\)
Main use	Theoretical analysis	Numerical spectrum evaluation	Standard in practice
Primary API	(closed form)	Direct computation	numpy.fft.fft

Relationship to the Z-transform

The DTFT is the Z-transform \(X(z)\) restricted to the unit circle \(z = e^{j\omega}\) . Working in the Z-domain lets you see poles, zeros, the frequency response, and stability all at once, which makes it the theoretical foundation of filter design. For the details see https://yuhi-sa.github.io/en/posts/20260430_z_transform/1/.

DCT is the even-symmetric counterpart of DFT

For real signals where you want to avoid the Gibbs phenomenon at the boundaries and concentrate energy into low-frequency coefficients, the DCT is the natural choice. It is used in nearly every lossy compression standard — JPEG, MP3, H.264, and so on. See https://yuhi-sa.github.io/en/posts/20260430_dct/1/ for details.

4. Mathematical Operations on Discrete Signals

Z-transform and transfer functions

Taking the Z-transform of both sides of a difference equation

\[\sum_{k=0}^{N} a_k\, y[n-k] = \sum_{k=0}^{M} b_k\, x[n-k]\]

yields the transfer function

\[H(z) = \frac{Y(z)}{X(z)} = \frac{\sum_k b_k z^{-k}}{\sum_k a_k z^{-k}} = \frac{B(z)}{A(z)}.\]

The system is BIBO stable iff all poles lie strictly inside the unit circle. See https://yuhi-sa.github.io/en/posts/20260430_z_transform/1/ for the full discussion. Reading https://yuhi-sa.github.io/en/posts/20260430_phase_group_delay/1/ alongside it adds a more concrete picture of stability, frequency response, and group delay.

Autocorrelation and cross-correlation

The autocorrelation function (ACF) is used to detect periodicity in a signal, while the cross-correlation function (CCF) is used for delay estimation. By the Wiener–Khinchin theorem, the Fourier transform of the ACF is the power spectral density (PSD):

\[S_{xx}(f) = \mathcal{F}\{R_{xx}(\tau)\}.\]

With the FFT, this can be computed in \(O(N \log N)\) time. See https://yuhi-sa.github.io/en/posts/20260429_autocorrelation/1/.

Convolution and correlation

The article https://yuhi-sa.github.io/en/posts/20260502_convolution_correlation/1/, which organizes the relationship among convolution, correlation, and the Wiener–Khinchin theorem, makes a natural complement to this section.

5. Interpolation and Reconstruction

Recovering the continuous signal \(x(t)\) from its samples \(x[n]\) — reconstruction — and adjusting the sampling rate — interpolation — are two sides of the same coin.

Comparison of major interpolation methods

Method	Frequency response	Cost	Main use	API
sinc (ideal)	Ideal LPF	Infinite sum (must truncate)	Theoretical reconstruction (sampling thm.)	numpy.sinc
Linear	\(\text{sinc}^2\) roll-off	\(O(N)\)	Lightweight visualization, low-quality audio	numpy.interp
Cubic	Steeper roll-off	\(O(N)\)	Image resizing	scipy.interpolate.interp1d
Spline	Smooth \(C^2\) continuity	\(O(N)\)	Numerical analysis, physics simulations	scipy.interpolate.CubicSpline
FFT resampling	Equivalent sinc via FFT	\(O(N \log N)\)	Resampling at arbitrary ratios	scipy.signal.resample
Polyphase	Built-in anti-aliasing	\(O(N)\)	High-efficiency resampling	scipy.signal.resample_poly

For theory and implementation details see https://yuhi-sa.github.io/en/posts/20260430_signal_interpolation/1/.

Upsampling and downsampling

• Decimation: AAF → keep one sample out of every \(M\) . Use scipy.signal.decimate.
• Interpolation: zero-insertion → image-rejection LPF. Use scipy.signal.resample_poly.

If you want to dig into LPF design, move on to https://yuhi-sa.github.io/en/posts/20260223_lowpass_filter/1/, https://yuhi-sa.github.io/en/posts/20260226_butterworth/1/, and https://yuhi-sa.github.io/en/posts/20260226_fir_iir/1/.

6. Applications — Connecting to the Surrounding Hubs

A. Filter design

Every operation that reshapes the frequency response of a discrete signal ultimately reduces to placing poles and zeros in the Z-domain. Once you have internalized the Z-transform and the DTFT in this hub, the natural next step is https://yuhi-sa.github.io/en/posts/20260522_filter_design_guide/1/, which covers how to choose among IIR/FIR, Butterworth/Chebyshev/Bessel, and notch/bandpass designs. Concrete articles:

• https://yuhi-sa.github.io/en/posts/20260226_butterworth/1/ — Butterworth
• https://yuhi-sa.github.io/en/posts/20260314_chebyshev_filter/1/ — Chebyshev
• https://yuhi-sa.github.io/en/posts/20260316_bessel_filter/1/ — Bessel
• https://yuhi-sa.github.io/en/posts/20260226_fir_iir/1/ — FIR vs IIR
• https://yuhi-sa.github.io/en/posts/20260228_notch_filter/1/ — Notch
• https://yuhi-sa.github.io/en/posts/20260312_bandpass_filter/1/ — Bandpass
• https://yuhi-sa.github.io/en/posts/20260313_highpass_filter/1/ — Highpass
• https://yuhi-sa.github.io/en/posts/20260223_lowpass_filter/1/ — Lowpass

B. Time-frequency analysis

Sliding a windowed DFT/FFT along time gives you the STFT, and adapting the resolution to the time scale gives you wavelets. The hub is https://yuhi-sa.github.io/en/posts/20260524_time_frequency_guide/1/.

• https://yuhi-sa.github.io/en/posts/20260429_stft/1/ — STFT
• https://yuhi-sa.github.io/en/posts/20260226_wavelet/1/ — Wavelet transform
• https://yuhi-sa.github.io/en/posts/20260318_hilbert_transform/1/ — Hilbert transform
• https://yuhi-sa.github.io/en/posts/20260528_mode_decomposition/1/ — EMD/VMD/SSA

C. Machine-learning preprocessing

A pipeline that feeds features such as STFT average power, wavelet energy, and autocorrelation lags into an ML model is centralized in https://yuhi-sa.github.io/en/posts/20260525_ml_timeseries_guide/1/. Concrete examples:

• https://yuhi-sa.github.io/en/posts/20260228_timeseries_anomaly/1/ — Time-series anomaly detection
• https://yuhi-sa.github.io/en/posts/20260226_arima/1/ — ARIMA (order selection via ACF/PACF)
• https://yuhi-sa.github.io/en/posts/20260317_lstm_timeseries/1/ — LSTM time-series

D. Returning to the meta-roadmap

The meta-roadmap that ties the five major hubs together with this one is https://yuhi-sa.github.io/en/posts/20260528_dsp_ml_roadmap/1/. It is the right place to come back to whenever you want to revisit the level-based learning paths.

7. Learning Checklist

A 14-item self-check to see whether the continuous-to-discrete bridge has really sunk in.

Sampling and interpolation

1. You can articulate the difference between the Nyquist frequency and the Nyquist rate
2. You can write the spectrum-replication formula \(X_s(f) = f_s \sum_k X(f - k f_s)\)
3. You can compute the aliased frequency \(|f - \text{round}(f/f_s) \cdot f_s|\) by hand
4. You can explain the frequency-response difference between sinc and linear interpolation (the \(\text{sinc}^2\) roll-off)
5. You can describe when to use scipy.signal.resample versus resample_poly

DTFT, DFT, and FFT

6. You can instantly say “DTFT is a continuous-frequency representation, DFT is its discrete version, FFT is a fast DFT algorithm”
7. You can produce a correct frequency axis from numpy.fft.fft output length using fftfreq
8. You can articulate that zero-padding adds no new information — it just samples the DTFT more densely

Z-transform and transfer functions

9. You can show with a difference equation that \(z^{-1}\) corresponds to a one-sample delay
10. You can state the BIBO-stability condition: all poles strictly inside the unit circle
11. You can geometrically interpret \(H(e^{j\omega})\) in terms of distances from poles and zeros

Autocorrelation and DCT

12. You can instantly say “the Fourier transform of the ACF equals the PSD (Wiener–Khinchin)”
13. You can articulate the difference between ACF and CCF (the latter being for delay estimation)
14. You can summarize in one line why DCT outperforms DFT for compression (even-symmetric extension → no boundary Gibbs)

8. Common Stumbling Blocks — Q&A

Q1. What is the intuition behind the sampling theorem?

The intuition: “Components that oscillate faster than the sample interval are indistinguishable from slower ones if you look only at the samples.” In the frequency domain, the spectrum is replicated every \(f_s\) across the entire frequency axis, so as long as the replicas do not overlap (i.e., \(f_s > 2 f_{\max}\) ), an ideal LPF can pull out a single copy. Equations and figures are in https://yuhi-sa.github.io/en/posts/20260430_sampling_theorem/1/.

Q2. What is the difference between DTFT, DFT, and FFT?

• DTFT: discrete in time, continuous in frequency (theoretical use)
• DFT: discrete and finite in both time and frequency (numerical use)
• FFT: an algorithm that computes the DFT quickly (the output is identical to a DFT)

See https://yuhi-sa.github.io/en/posts/20260505_dtft_dft_fft/1/ for full detail.

Q3. What is the relationship between the Z-transform and the Fourier transform?

The DTFT is the Z-transform \(X(z)\) restricted to the unit circle \(z = e^{j\omega}\) . Conversely, the Z-transform is the analytic continuation of the DTFT into the complex \(z\) -plane — viewed this way, the stability condition (poles inside the unit circle) drops out naturally. See https://yuhi-sa.github.io/en/posts/20260430_z_transform/1/.

Q4. What is the difference between autocorrelation and cross-correlation?

• ACF: similarity between a signal and a delayed copy of itself → periodicity detection
• CCF: similarity between two different signals → delay estimation

The ACF attains its maximum at \(\tau = 0\) ; for the CCF, the \(\tau\) at which the maximum occurs is exactly the estimated delay. See https://yuhi-sa.github.io/en/posts/20260429_autocorrelation/1/.

Q5. DCT or DFT — which should I use?

If your input is real-valued and you want to concentrate energy in the low-order coefficients (i.e., compress), use the DCT. If you need a complex spectrum or a frequency response, use the DFT/FFT. Internally the DCT is computed via an even-symmetric extension plus an FFT, so the asymptotic cost is the same \(O(N \log N)\) . Details in https://yuhi-sa.github.io/en/posts/20260430_dct/1/.

Q6. Is sinc interpolation usable in practice?

The ideal sinc is an infinite sum, so in practice you truncate to a finite length and multiply by a window function. There is a trade-off between truncation error and window side-lobes. In real code, prefer scipy.signal.resample (FFT-equivalent) or resample_poly (polyphase). See https://yuhi-sa.github.io/en/posts/20260430_signal_interpolation/1/.

Q7. I always get confused by the FFT frequency axis.

Always use np.fft.fftfreq(N, d=1/fs) or np.fft.rfftfreq(N, d=1/fs). Writing it out by hand is error-prone — signs and ordering are easy to get wrong. Window functions and PSD units (including normalization) are organized in https://yuhi-sa.github.io/en/posts/20260228_fft_window_psd/1/.

9. Related Hubs and Articles

The six articles bundled by this hub

• https://yuhi-sa.github.io/en/posts/20260430_sampling_theorem/1/ — Sampling theorem
• https://yuhi-sa.github.io/en/posts/20260430_signal_interpolation/1/ — Signal interpolation
• https://yuhi-sa.github.io/en/posts/20260505_dtft_dft_fft/1/ — DTFT/DFT/FFT
• https://yuhi-sa.github.io/en/posts/20260430_z_transform/1/ — Z-transform
• https://yuhi-sa.github.io/en/posts/20260429_autocorrelation/1/ — Autocorrelation
• https://yuhi-sa.github.io/en/posts/20260430_dct/1/ — DCT

Connected hubs

• https://yuhi-sa.github.io/en/posts/20260522_filter_design_guide/1/ — Filter-design guide hub
• https://yuhi-sa.github.io/en/posts/20260524_time_frequency_guide/1/ — Time-frequency analysis hub
• https://yuhi-sa.github.io/en/posts/20260525_ml_timeseries_guide/1/ — Machine-learning time-series hub
• https://yuhi-sa.github.io/en/posts/20260528_dsp_ml_roadmap/1/ — DSP/ML meta-roadmap

Supporting articles

• https://yuhi-sa.github.io/en/posts/20260225_fft/1/ — FFT primer
• https://yuhi-sa.github.io/en/posts/20260228_fft_window_psd/1/ — Window functions and PSD
• https://yuhi-sa.github.io/en/posts/20260502_convolution_correlation/1/ — Convolution and correlation
• https://yuhi-sa.github.io/en/posts/20260430_phase_group_delay/1/ — Phase and group delay
• https://yuhi-sa.github.io/en/posts/20260225_moving_average/1/ — Moving average

The fundamentals of discrete signal processing are the launchpad for filter design, time-frequency analysis, and machine-learning time series alike. Use this hub as a base camp and head into whichever direction your goals point to.