From continuous waves to finite lists of numbers — the tradeoffs that make all of digital signal processing possible.
The word digital comes from digitus, Latin for finger. When you count on your fingers, you use discrete values: 1, 2, 3, ... You can't hold up 2.7 fingers. Computers are the same — they store information as lists of numbers, nothing more.
But the world is continuous. Sound pressure varies smoothly over time. Light intensity changes gradually across an image. Temperature flows without jumps. So how does a computer represent a continuous signal?
It doesn't. Not exactly. Instead, it takes samples — snapshots at regular intervals — and quantizes each sample to the nearest allowed level. This introduces two fundamental tradeoffs that define all of digital signal processing:
This entire lecture is about understanding these tradeoffs precisely. When can we sample and perfectly reconstruct? When does quantization become visible? What mathematical objects represent these discrete signals?
Pilanci defines three terms that frame this course:
Together: Digital Signal Processing is the art of manipulating sequences of numbers to extract meaning from the world.
The smooth teal curve is a continuous signal. The orange dots are samples taken at regular intervals. Adjust the sampling rate to see when the dots capture the shape well — and when they don't.
With 60 samples, the dots trace the curve almost perfectly. Drop to 4, and you can barely tell what the original signal was. This is the sampling tradeoff in action.
Before we can do anything with signals, we need precise notation. Pilanci distinguishes three types of signals, each mapping from a different domain to a different range:
| Type | Notation | Domain → Range | Example |
|---|---|---|---|
| Discrete | x[n] | ℤ → ℂ (or ℝ) | Average Dow-Jones index in year n |
| Continuous | x(t) | ℝ → ℂ (or ℝ) | Temperature at time t |
| Digital | xdig[n] | ℤ → ℤ | 8-bit audio sample at index n |
x[n] = discrete. Parentheses x(t) = continuous. The argument tells you everything: n ∈ ℤ means integer-indexed, t ∈ ℝ means continuous.The discrete signal x[n] is a function from the integers to the complex numbers. Each integer n maps to exactly one complex (or real) value. Think of it as an infinite sequence: ..., x[−2], x[−1], x[0], x[1], x[2], ...
The digital signal xdig[n] goes one step further — the output is also restricted to integers. This is what actually lives in computer memory after quantization.
The simplest possible discrete signal is the delta sequence (also called the unit impulse):
It's zero everywhere except at n = 0, where it equals 1. Why is this useful? Because any discrete signal can be written as a sum of shifted deltas:
This is called the sifting property. Each term x[k]·δ[n−k] is zero everywhere except at n=k, where it contributes the value x[k]. Sum them all up and you reconstruct the original signal. The deltas form a basis — any signal is a weighted combination of shifted impulses.
The unit step "turns on" at n = 0. Before zero: silence. After zero: constant 1. It's the switch that says "start now."
This signal starts at 1 (when n=0) and decays toward zero. The rate of decay depends on |a|: closer to 1 means slow decay, closer to 0 means fast. The u[n] factor ensures the signal is zero for negative n (it "starts" at the origin).
Toggle between δ[n], u[n], and exponential decay. For the exponential, adjust the decay rate |a|.
The most important signal in all of signal processing is the complex exponential:
where:
By Euler's formula, the real part gives us a cosine:
The frequency in cycles per sample is f = ω0 / (2π). This tells you how many full oscillations occur per sample index.
In continuous time, every sinusoid cos(Ω0t) is periodic with period 2π/Ω0. But in discrete time, something surprising happens: not all sinusoids are periodic!
A discrete signal x̃[n] is periodic with period N if there exists an integer N > 0 such that:
For cos(ω0n) to be periodic with period N, we need:
This requires ω0N = 2πk for some integer k (a full number of cycles in N samples). Solving:
Setting M = 2k, we get ω0 = (M/N)π where M and N are integers. Conversely, if ω0 = (M/N)π, then the period is N/gcd(M,N) (the smallest N that works).
In continuous time, for any Ω0, the period T = 2π/Ω0 is a valid real number. But in discrete time, the period N must be a positive integer. That constraint forces ω0 to be a rational multiple of π.
Example: x[n] = cos(n). Here ω0 = 1. Is 1/π rational? No! So cos(n) is not periodic as a discrete signal, even though the continuous version cos(t) is periodic with period 2π.
Example: x[n] = cos(πn/4). Here ω0 = π/4 = (1/4)π. Since 1/4 is rational, this IS periodic. The period is N = 2π/(π/4) · (1/(2π)) · N... more directly: we need (π/4)N = 2πk, so N = 8k. Smallest period: N = 8.
Set the frequency ω0. When ω0/π is rational, the signal repeats (shown in green). When irrational, it never repeats exactly (red).
We have a continuous signal xa(t) — maybe a sound wave, maybe a voltage from a sensor. To get it into a computer, we sample it at regular intervals:
where T is the sampling period (seconds between samples) and 1/T is the sampling frequency (samples per second, in Hz).
The critical question: can we recover xa(t) from x[n]? Under what conditions is no information lost?
"Completely determined" means you can perfectly reconstruct the original continuous signal from the samples alone. No information is lost. This is remarkable — infinitely many values of xa(t) are captured by a countable set of samples.
If you sample too slowly (T > 1/(2B), or equivalently, sampling rate < 2B), you get aliasing: different continuous signals produce the same samples. The high-frequency content "folds over" and masquerades as a lower frequency. Once aliased, the information is permanently lost — no algorithm can undo it.
Consider xa(t) = cos(2πf0t). Its bandwidth is B = f0. Nyquist says: sample at rate ≥ 2f0, i.e., T ≤ 1/(2f0).
If we sample at exactly the Nyquist rate, T = 1/(2f0):
which alternates between +1 and −1 — just barely capturing the oscillation.
If we under-sample (say T = 1/f0):
The cosine looks like a constant! All oscillation information is lost.
You've seen this in movies: a wheel spinning at high speed appears to rotate slowly backward, or even stand still. This is aliasing in action. Film cameras sample at ~24 frames per second. If the spokes of a wheel rotate at nearly 24 Hz (or a multiple), the discrete samples can't distinguish the true rotation from a much slower (or reversed) one.
The human eye has a similar "sampling rate" of approximately T = 1/25 seconds. Stroboscopic lighting exploits this same effect.
The teal curve is the true signal cos(2πf0t). The orange dots are samples. The dashed red curve is the aliased frequency that the samples "see." When sampling rate ≥ 2f0, no alias appears.
Sampling converts a continuous-time signal to discrete-time. But the amplitude is still continuous — each sample x[n] can be any real number. A computer can't store infinitely precise real numbers. It must quantize: map each continuous amplitude to the nearest value from a finite set of allowed levels.
With B bits, we have 2B levels. The more bits, the finer the resolution:
| Bits (B) | Levels (2B) | Application |
|---|---|---|
| 1 | 2 | Binary image (black/white) |
| 3 | 8 | Heavily compressed audio (lo-fi) |
| 8 | 256 | Standard grayscale image, telephone audio |
| 16 | 65,536 | CD-quality audio |
| 24 | 16,777,216 | Professional audio (studio) |
The simplest quantizer divides the amplitude range [−Xmax, Xmax] into 2B equal intervals. Each interval maps to its midpoint. The step size (distance between adjacent levels) is:
The quantization error (the difference between the true value and the quantized value) is bounded by ±Δ/2. As B increases, Δ shrinks and the error becomes negligible.
Quantizing images: A standard grayscale image uses 8 bits per pixel (256 shades). Drop to 4 bits (16 shades) and you see banding — smooth gradients become visible steps. Drop to 1 bit and you get pure black-and-white.
Quantizing audio: 24-bit audio is indistinguishable from analog for human ears. 8-bit audio has audible "graininess" (think retro video game sounds). 3-bit audio is barely recognizable — extreme distortion.
The smooth teal curve is the original signal. The orange staircase is the quantized version. Reduce bits to see increasing distortion.
A finite-length signal of length N is just a vector in ℂN (or ℝN). And vectors can be expressed in different bases. The signal doesn't change — only its representation changes.
Here y(0)[n], ..., y(M−1)[n] are the basis signals, and c[0], ..., c[M−1] are the expansion coefficients — the coordinates of x in this new basis.
The collection of shifted deltas δ[n], δ[n−1], ..., δ[n−(N−1)] is a basis. If we set c[m] = x[m]:
This is the standard basis (or canonical basis). The coefficients are just the signal values themselves. It's also orthonormal — the deltas are mutually orthogonal and each has norm 1.
Pilanci gives four powerful motivations:
If our basis y(0)[n], ..., y(N−1)[n] is orthonormal — meaning all basis vectors are mutually orthogonal and have norm 1:
— then computing the coefficients is trivial: just take inner products!
And reconstruction is:
For length-2 signals, the standard basis is δ0 = [1, 0]T, δ1 = [0, 1]T. Another basis (the Hadamard basis):
These are orthogonal (inner product = −1+1 = 0) but not norm-1. Normalizing: divide each by ‖xi‖ = √2.
The most important orthonormal basis for length-N complex signals:
This is the normalized Fourier basis. Each basis vector wm oscillates at a different frequency. The expansion coefficients c[m] = ⟨wm, x⟩ are the Discrete Fourier Transform (DFT) of x. They tell you "how much" of each frequency is present in the signal.
Create a signal in the standard basis (click to set sample values). Then view its representation in the Hadamard or Fourier basis. The signal is the same — only the coordinates change.
How "big" is a signal? We need a way to measure the total content of a signal — its energy.
This is the sum of squared magnitudes over all samples. If this sum converges (is finite), we call x[n] square summable — it lives in the space ℓ2.
Example: The exponential decay x[n] = 0.5n u[n] has energy E = ∑n=0∞ 0.25n = 1/(1−0.25) = 4/3. Finite!
Example: The unit step u[n] has energy E = ∑n=0∞ 1 = ∞. Not square summable.
For signals with infinite energy (like u[n] or periodic signals), we define power as energy per unit time:
For finite-length signals (vectors in ℂN), the inner product is:
where x*[k] is the complex conjugate of x[k]. Two vectors are orthogonal (x ⊥ y) when ⟨x, y⟩ = 0.
This is the ℓ2-norm (or 2-norm). In ℝ2, it's just the length of the vector — the distance from the origin.
For real vectors in ℝ2, the inner product relates to the angle θ between vectors:
When θ = π/2 (perpendicular), cosθ = 0, so the inner product is zero. This is the geometric meaning of orthogonality.
The inner product can never exceed the product of norms. Equality holds only when x and y are parallel (one is a scalar multiple of the other). This bounds how "aligned" two signals can be.
A deep result we'll prove in a later lecture: for an orthonormal basis, the energy in the original domain equals the energy in the transformed domain:
Changing basis doesn't create or destroy energy — it just redistributes it among coefficients. This is Parseval's theorem, and it's why the Fourier transform "preserves" signal energy.
Drag the two vectors and observe their inner product. When perpendicular, the inner product is zero. The Cauchy-Schwarz bound is shown as a ceiling.
You've covered the foundations of discrete signals. Let's consolidate everything into reference cards you can return to.
| Symbol | Meaning |
|---|---|
| x[n] | Discrete signal, domain ℤ, range ℂ or ℝ |
| x(t) | Continuous signal, domain ℝ, range ℂ or ℝ |
| xdig[n] | Digital signal, domain ℤ, range ℤ |
| δ[n] | Delta (impulse): 1 at n=0, 0 elsewhere |
| u[n] | Unit step: 1 for n≥0, 0 for n<0 |
| ejω0n | Complex exponential at frequency ω0 rad/sample |
| ⟨x, y⟩ | Inner product = ∑ x*[k]y[k] |
| ‖x‖ | Norm = √⟨x,x⟩ |
| T | Sampling period (seconds) |
| 1/T = fs | Sampling frequency (Hz) |
| B | Bits per sample (quantization) |
Enter ω0 as a fraction of π. The tool tells you if the signal is periodic and what the fundamental period is.
| Theorem | Statement |
|---|---|
| Periodicity | cos(ω0n) periodic iff ω0 = (M/N)π, M,N ∈ ℤ |
| Nyquist-Shannon | Bandwidth B ⇒ sample at ≥ 2B for perfect reconstruction |
| Sifting Property | x[n] = ∑ x[k]δ[n−k] (any signal = sum of shifted impulses) |
| Cauchy-Schwarz | |⟨x,y⟩| ≤ ‖x‖·‖y‖ |
| Parseval | ∑|x[n]|² = ∑|c[k]|² in any orthonormal basis |
Lecture 3 will dive deeper into quantization noise — modeling the error introduced by quantization as a random process, and analyzing its statistics (mean, variance, power spectrum). We'll also explore the Discrete Fourier Transform in detail and see how the Fourier basis enables spectral analysis.