Discrete-Time Signals and Systems
Unit Impulse Sequence
\delta[n] = \begin{cases} 1 & n=0 \\ 0 & n\neq 0 \end{cases}
| Symbol | Description | Unit |
|---|---|---|
| \delta[n] | Unit impulse (Kronecker delta) | dimensionless |
| n | Discrete time index | dimensionless |
Worked example
Evaluate x[n] = 3\delta[n-2] + 5\delta[n] - 2\delta[n+1] at n = -1, 0, 1, 2.
Given: x[n] = 3\delta[n-2] + 5\delta[n] - 2\delta[n+1]
- At n = -1: \delta[-1-2]=0, \delta[-1]=0, \delta[-1+1]=\delta[0]=1 → x[-1] = 0 + 0 - 2(1) = -2
- At n = 0: \delta[0-2]=0, \delta[0]=1, \delta[0+1]=\delta[1]=0 → x[0] = 0 + 5(1) - 0 = 5
- At n = 1: \delta[1-2]=0, \delta[1]=0, \delta[1+1]=\delta[2]=0 → x[1] = 0
- At n = 2: \delta[2-2]=\delta[0]=1, \delta[2]=0, \delta[2+1]=0 → x[2] = 3(1) = 3
Answer: x[-1]=-2, x[0]=5, x[1]=0, x[2]=3
Discrete-Time Convolution
y[n] = x[n] * h[n] = \sum_{k=-\infty}^{\infty} x[k]\, h[n-k]
| Symbol | Description | Unit |
|---|---|---|
| y[n] | Output sequence | dimensionless |
| x[n] | Input sequence | dimensionless |
| h[n] | Impulse response | dimensionless |
Worked example
Find y[n] = x[n] * h[n] where x[n] = {1, 2, 3} and h[n] = {1, 1} (both starting at n=0).
Given: x = [1, 2, 3], h = [1, 1]
- Length of y = (3) + (2) - 1 = 4 samples.
- y[0] = x[0]h[0] = 1×1 = 1
- y[1] = x[0]h[1] + x[1]h[0] = 1×1 + 2×1 = 3
- y[2] = x[1]h[1] + x[2]h[0] = 2×1 + 3×1 = 5
- y[3] = x[2]h[1] = 3×1 = 3
Answer: y[n] = {1, 3, 5, 3}
Energy of a Discrete-Time Signal
E = \sum_{n=-\infty}^{\infty} |x[n]|^2
| Symbol | Description | Unit |
|---|---|---|
| E | Signal energy | joules (normalised) |
| x[n] | Discrete-time signal | dimensionless |
Worked example
Compute the energy of x[n] = {2, -1, 3, 0, -2}.
Given: x = [2, -1, 3, 0, -2]
- E = |2|² + |-1|² + |3|² + |0|² + |-2|²
- E = 4 + 1 + 9 + 0 + 4
- E = 18
Answer: E = 18
BIBO Stability Condition
\sum_{n=-\infty}^{\infty} |h[n]| < \infty
| Symbol | Description | Unit |
|---|---|---|
| h[n] | System impulse response | dimensionless |
Worked example
Is the system h[n] = (0.5)^n u[n] BIBO stable?
Given: h[n] = (0.5)^n u[n]
- Sum = \sum_{n=0}^{\infty} (0.5)^n = geometric series with r = 0.5
- Sum = 1/(1 - 0.5) = 1/0.5 = 2
- Since 2 < ∞, the condition is satisfied.
Answer: System is BIBO stable; sum = 2.
Z-Transform
Bilateral Z-Transform
X(z) = \sum_{n=-\infty}^{\infty} x[n]\, z^{-n}
| Symbol | Description | Unit |
|---|---|---|
| X(z) | Z-transform of x[n] | dimensionless |
| z | Complex variable | dimensionless |
| n | Discrete time index | dimensionless |
Worked example
Find the Z-transform of x[n] = (0.8)^n u[n].
Given: x[n] = (0.8)^n u[n]
- X(z) = \sum_{n=0}^{\infty} (0.8)^n z^{-n} = \sum_{n=0}^{\infty} (0.8/z)^n
- This is a geometric series: converges when |0.8/z| < 1, i.e., |z| > 0.8
- X(z) = 1/(1 - 0.8z^{-1}) = z/(z - 0.8)
Answer: X(z) = z/(z - 0.8), ROC: |z| > 0.8
Z-Transform Time-Shift Property
\mathcal{Z}\{x[n-k]\} = z^{-k} X(z)
| Symbol | Description | Unit |
|---|---|---|
| k | Integer delay in samples | samples |
| X(z) | Z-transform of x[n] | dimensionless |
Worked example
If X(z) = z/(z-0.5), find the Z-transform of x[n-3].
Given: X(z) = z/(z-0.5), k=3
- Apply time-shift property: Z{x[n-3]} = z^{-3} X(z)
- = z^{-3} · z/(z-0.5)
- = z^{-2}/(z-0.5)
- = 1/(z^2(z-0.5))
Answer: Z{x[n-3]} = z^{-2}/(z-0.5)
Inverse Z-Transform (Partial Fractions)
x[n] = \mathcal{Z}^{-1}\{X(z)\} = \frac{1}{2\pi j} \oint X(z) z^{n-1}\, dz
| Symbol | Description | Unit |
|---|---|---|
| X(z) | Z-transform | dimensionless |
| x[n] | Recovered time-domain sequence | dimensionless |
Worked example
Find x[n] given X(z) = z²/((z-0.5)(z-0.25)) with ROC |z|>0.5, using partial fractions.
Given: X(z)/z = z/((z-0.5)(z-0.25))
- Write X(z)/z = A/(z-0.5) + B/(z-0.25)
- A = z/(z-0.25)|_{z=0.5} = 0.5/(0.5-0.25) = 0.5/0.25 = 2
- B = z/(z-0.5)|_{z=0.25} = 0.25/(0.25-0.5) = 0.25/(-0.25) = -1
- X(z) = 2z/(z-0.5) - z/(z-0.25)
- Inverse: x[n] = 2(0.5)^n u[n] - (0.25)^n u[n]
Answer: x[n] = [2(0.5)^n - (0.25)^n] u[n]
Transfer Function of a Discrete-Time System
H(z) = \frac{Y(z)}{X(z)} = \frac{\sum_{k=0}^{M} b_k z^{-k}}{1 + \sum_{k=1}^{N} a_k z^{-k}}
| Symbol | Description | Unit |
|---|---|---|
| b_k | Numerator (feedforward) coefficients | dimensionless |
| a_k | Denominator (feedback) coefficients | dimensionless |
Worked example
A system has difference equation y[n] = 0.5y[n-1] + x[n] + 0.3x[n-1]. Find H(z).
Given: a_1 = -0.5, b_0 = 1, b_1 = 0.3
- Take Z-transform: Y(z) = 0.5z^{-1}Y(z) + X(z) + 0.3z^{-1}X(z)
- Y(z)(1 - 0.5z^{-1}) = X(z)(1 + 0.3z^{-1})
- H(z) = (1 + 0.3z^{-1})/(1 - 0.5z^{-1})
- Multiply numerator and denominator by z: H(z) = (z + 0.3)/(z - 0.5)
Answer: H(z) = (z + 0.3)/(z - 0.5)
Discrete Fourier Transform (DFT)
N-Point DFT
X[k] = \sum_{n=0}^{N-1} x[n]\, e^{-j2\pi kn/N}, \quad k = 0, 1, \ldots, N-1
| Symbol | Description | Unit |
|---|---|---|
| X[k] | DFT output (frequency-domain) | dimensionless |
| N | DFT length | samples |
| k | Frequency index | dimensionless |
Worked example
Compute the 4-point DFT of x[n] = {1, 2, 3, 4}.
Given: x = [1,2,3,4], N=4, W_4 = e^{-j2π/4} = e^{-jπ/2} = -j
- X[0] = x[0]+x[1]+x[2]+x[3] = 1+2+3+4 = 10
- X[1] = x[0] + x[1](−j) + x[2](−j)² + x[3](−j)³ = 1 + 2(−j) + 3(−1) + 4(j) = (1−3) + j(4−2) = −2 + 2j
- X[2] = 1 + 2(−1) + 3(1) + 4(−1) = 1−2+3−4 = −2
- X[3] = 1 + 2(j) + 3(−1) + 4(−j) = (1−3) + j(2−4) = −2 − 2j
Answer: X[k] = {10, −2+2j, −2, −2−2j}
Inverse DFT (IDFT)
x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k]\, e^{j2\pi kn/N}
| Symbol | Description | Unit |
|---|---|---|
| x[n] | Recovered time-domain sequence | dimensionless |
| X[k] | DFT coefficients | dimensionless |
Worked example
Verify IDFT recovers x[0] from X[k] = {10, −2+2j, −2, −2−2j} with N=4.
Given: N=4, k=0,1,2,3
- x[0] = (1/4)[X[0]e^0 + X[1]e^0 + X[2]e^0 + X[3]e^0]
- = (1/4)[10 + (−2+2j) + (−2) + (−2−2j)]
- = (1/4)[10 − 2 − 2 − 2 + j(2−2)]
- = (1/4)(4) = 1
Answer: x[0] = 1 ✓
DFT Circular Convolution
y[n] = x_1[n] \circledast x_2[n] \Leftrightarrow Y[k] = X_1[k] \cdot X_2[k]
| Symbol | Description | Unit |
|---|---|---|
| \circledast | N-point circular convolution operator | dimensionless |
Worked example
Find 4-point circular convolution of x1=[1,2,0,0] and x2=[1,1,0,0].
Given: x1=[1,2,0,0], x2=[1,1,0,0], N=4
- y[0] = x1[0]x2[0]+x1[3]x2[1]+x1[2]x2[2]+x1[1]x2[3] = 1·1+0·1+0·0+2·0 = 1
- y[1] = x1[1]x2[0]+x1[0]x2[1]+x1[3]x2[2]+x1[2]x2[3] = 2·1+1·1+0+0 = 3
- y[2] = x1[2]x2[0]+x1[1]x2[1]+x1[0]x2[2]+x1[3]x2[3] = 0+2·1+0+0 = 2
- y[3] = x1[3]x2[0]+x1[2]x2[1]+x1[1]x2[2]+x1[0]x2[3] = 0+0+0+0 = 0
Answer: y[n] = {1, 3, 2, 0}
Fast Fourier Transform (FFT)
Radix-2 DIT FFT Butterfly
\begin{aligned} A' &= A + W_N^r B \\ B' &= A - W_N^r B \end{aligned}, \quad W_N^r = e^{-j2\pi r/N}
| Symbol | Description | Unit |
|---|---|---|
| W_N^r | Twiddle factor | dimensionless |
| A, B | Input nodes to butterfly | dimensionless |
| r | Twiddle factor exponent | dimensionless |
Worked example
Compute one butterfly with A=3+j, B=1−j, W_8^1 = e^{-jπ/4} = (1−j)/√2 ≈ 0.707−0.707j.
Given: A=3+j, B=1−j, W=0.707−0.707j
- W·B = (0.707−0.707j)(1−j) = 0.707−0.707j−0.707j+0.707j² = 0.707−1.414j−0.707 = −1.414j
- A' = A + W·B = (3+j) + (−1.414j) = 3 + (1−1.414)j = 3 − 0.414j
- B' = A − W·B = (3+j) − (−1.414j) = 3 + (1+1.414)j = 3 + 2.414j
Answer: A' = 3 − 0.414j, B' = 3 + 2.414j
FFT Computational Complexity
\text{Complex multiplications} = \frac{N}{2} \log_2 N
| Symbol | Description | Unit |
|---|---|---|
| N | DFT length (must be power of 2 for radix-2) | samples |
Worked example
Compare multiplications needed for direct DFT vs. FFT for N=1024.
Given: N=1024
- Direct DFT: N² = 1024² = 1,048,576 multiplications
- FFT: (N/2)log2(N) = 512 × log2(1024) = 512 × 10 = 5120 multiplications
- Speed-up ratio = 1,048,576 / 5,120 = 204.8×
Answer: FFT requires 5120 vs. 1,048,576 for direct DFT — ~205× faster
FIR Filter Design
FIR Filter Output
y[n] = \sum_{k=0}^{M} b_k\, x[n-k]
| Symbol | Description | Unit |
|---|---|---|
| M | Filter order (number of taps minus 1) | dimensionless |
| b_k | Filter coefficients | dimensionless |
Worked example
A 3-tap FIR filter has coefficients b=[0.25, 0.5, 0.25]. Find y[2] given x={1,2,3,4}.
Given: b=[0.25,0.5,0.25], x=[1,2,3,4], n=2
- y[2] = b0·x[2] + b1·x[1] + b2·x[0]
- = 0.25×3 + 0.5×2 + 0.25×1
- = 0.75 + 1.0 + 0.25
- = 2.0
Answer: y[2] = 2.0
Window Method — Ideal LPF Impulse Response
h_d[n] = \frac{\omega_c}{\pi}\, \text{sinc}\!\left(\frac{\omega_c n}{\pi}\right) = \frac{\sin(\omega_c n)}{\pi n}
| Symbol | Description | Unit |
|---|---|---|
| \omega_c | Cutoff frequency in rad/sample | rad/sample |
| n | Sample index (centred at 0) | dimensionless |
Worked example
Find h_d[1] and h_d[-1] for an ideal LPF with ω_c = π/4.
Given: ω_c = π/4, n = ±1
- h_d[n] = sin(ω_c·n)/(π·n)
- h_d[1] = sin(π/4)/(π·1) = (√2/2)/π = 0.7071/3.1416 = 0.2251
- h_d[-1] = sin(−π/4)/(π·(−1)) = (−√2/2)/(−π) = 0.2251
- Note: h_d[n] is symmetric (linear phase)
Answer: h_d[1] = h_d[−1] = 0.2251
Hamming Window
w[n] = 0.54 - 0.46\cos\!\left(\frac{2\pi n}{M}\right), \quad 0 \le n \le M
| Symbol | Description | Unit |
|---|---|---|
| M | Filter order | dimensionless |
| w[n] | Window coefficient | dimensionless |
Worked example
Find the Hamming window coefficients for M=4 (5-tap filter) at n=0,1,2,3,4.
Given: M=4
- w[0] = 0.54 − 0.46cos(0) = 0.54 − 0.46 = 0.08
- w[1] = 0.54 − 0.46cos(π/2) = 0.54 − 0 = 0.54
- w[2] = 0.54 − 0.46cos(π) = 0.54 + 0.46 = 1.00
- w[3] = w[1] = 0.54 (symmetric)
- w[4] = w[0] = 0.08 (symmetric)
Answer: w = {0.08, 0.54, 1.00, 0.54, 0.08}
IIR Filter Design
Bilinear Transformation
s = \frac{2}{T_s}\cdot\frac{z - 1}{z + 1}
| Symbol | Description | Unit |
|---|---|---|
| s | Analog complex frequency | rad/s |
| T_s | Sampling period | s |
| z | Digital complex variable | dimensionless |
Worked example
A first-order Butterworth LPF has H(s) = 1/(s+1). Convert to digital using bilinear transform with T_s = 0.1 s.
Given: H(s)=1/(s+1), T_s=0.1
- Substitute s = (2/0.1)·(z−1)/(z+1) = 20(z−1)/(z+1)
- H(z) = 1/[20(z−1)/(z+1) + 1] = (z+1)/[20(z−1)+(z+1)]
- Denominator = 20z−20+z+1 = 21z−19
- H(z) = (z+1)/(21z−19) = (1+z^{-1})/(21−19z^{-1})
Answer: H(z) = (1+z^{-1})/(21−19z^{-1})
Frequency Warping in Bilinear Transform
\Omega_a = \frac{2}{T_s} \tan\!\left(\frac{\omega_d}{2}\right)
| Symbol | Description | Unit |
|---|---|---|
| \Omega_a | Pre-warped analog frequency | rad/s |
| \omega_d | Desired digital frequency | rad/sample |
| T_s | Sampling period | s |
Worked example
Design a digital LPF with cutoff at ω_d = π/4 rad/sample using bilinear transform with T_s = 1 s. Find the pre-warped analog cutoff.
Given: ω_d = π/4, T_s = 1
- Ω_a = (2/1) × tan(π/8)
- tan(π/8) = tan(22.5°) ≈ 0.4142
- Ω_a = 2 × 0.4142 = 0.8284 rad/s
Answer: Pre-warped analog cutoff Ω_a = 0.8284 rad/s
Butterworth Filter Order
N \geq \frac{\log\!\left(\dfrac{10^{0.1A_s}-1}{10^{0.1A_p}-1}\right)}{2\log\!\left(\dfrac{\Omega_s}{\Omega_p}\right)}
| Symbol | Description | Unit |
|---|---|---|
| A_p | Passband ripple in dB | dB |
| A_s | Stopband attenuation in dB | dB |
| \Omega_p, \Omega_s | Passband and stopband frequencies | rad/s |
Worked example
Find minimum Butterworth order for A_p=3 dB, A_s=20 dB, Ω_p=1 rad/s, Ω_s=2 rad/s.
Given: A_p=3, A_s=20, Ω_p=1, Ω_s=2
- Numerator term: log((10^2 − 1)/(10^0.3 − 1)) = log((100−1)/(2−1)) = log(99/1) = log(99) = 1.9956
- Denominator term: 2×log(2/1) = 2×0.3010 = 0.6020
- N ≥ 1.9956/0.6020 = 3.31
- Round up: N = 4
Answer: Minimum Butterworth order N = 4
Power Spectral Density and Correlation
Autocorrelation of a Deterministic Sequence
R_{xx}[l] = \sum_{n=-\infty}^{\infty} x[n]\, x[n-l]
| Symbol | Description | Unit |
|---|---|---|
| R_{xx}[l] | Autocorrelation at lag l | dimensionless |
| l | Lag index | samples |
Worked example
Find R_{xx}[0] and R_{xx}[1] for x[n]={1,2,1} (n=0,1,2).
Given: x=[1,2,1]
- R_{xx}[0] = x[0]²+x[1]²+x[2]² = 1+4+1 = 6
- R_{xx}[1] = x[1]x[0]+x[2]x[1] = 2×1+1×2 = 4
- Note: R_{xx}[0] ≥ |R_{xx}[l]| always (6 ≥ 4 ✓)
Answer: R_{xx}[0] = 6, R_{xx}[1] = 4
Power Spectral Density (Wiener-Khinchin)
S_{xx}(e^{j\omega}) = \sum_{l=-\infty}^{\infty} R_{xx}[l]\, e^{-j\omega l}
| Symbol | Description | Unit |
|---|---|---|
| S_{xx}(e^{j\omega}) | Power spectral density | W/Hz (normalised) |
| R_{xx}[l] | Autocorrelation sequence | dimensionless |
Worked example
A WSS process has R_{xx}[0]=4, R_{xx}[1]=R_{xx}[-1]=2, all others zero. Find S_{xx} at ω=0 and ω=π.
Given: R_{xx}[0]=4, R_{xx}[±1]=2
- S_{xx}(e^{jω}) = R[−1]e^{jω} + R[0] + R[1]e^{−jω} = 2e^{jω} + 4 + 2e^{−jω} = 4 + 4cos(ω)
- At ω=0: S = 4 + 4cos(0) = 4+4 = 8
- At ω=π: S = 4 + 4cos(π) = 4−4 = 0
Answer: S_{xx}(1)=8, S_{xx}(−1)=0
Quick reference
| Formula | Expression |
|---|---|
| Discrete Convolution | y[n] = \sum_k x[k] h[n-k] |
| N-Point DFT | X[k] = \sum_{n=0}^{N-1} x[n] e^{-j2\pi kn/N} |
| IDFT | x[n] = (1/N)\sum_{k=0}^{N-1} X[k] e^{j2\pi kn/N} |
| Z-Transform | X(z) = \sum_n x[n] z^{-n} |
| Time-Shift Property | x[n-k] \leftrightarrow z^{-k}X(z) |
| BIBO Stability | \sum_n |h[n]| < \infty |
| FFT Complexity | (N/2)\log_2 N |
| Bilinear Transform | s = (2/T_s)(z-1)/(z+1) |
| Frequency Warping | \Omega_a = (2/T_s)\tan(\omega_d/2) |
| Hamming Window | w[n] = 0.54 - 0.46\cos(2\pi n/M) |
| FIR Output | y[n] = \sum_{k=0}^{M} b_k x[n-k] |
| Autocorrelation | R_{xx}[l] = \sum_n x[n]x[n-l] |
| PSD (Wiener-Khinchin) | S_{xx}(e^{j\omega}) = \sum_l R_{xx}[l] e^{-j\omega l} |
| Butterworth Order | N \geq \log[(10^{0.1A_s}-1)/(10^{0.1A_p}-1)] / 2\log(\Omega_s/\Omega_p) |
| Signal Energy | E = \sum_n |x[n]|^2 |
Exam tips
- GATE consistently asks you to compute 4-point or 8-point DFT values directly — memorise W_4 = −j and W_8 = (1−j)/√2 to save calculation time.
- In IIR filter design questions, always pre-warp the cutoff frequency before applying the bilinear transform; missing this step is the single most common error examiners penalise.
- For Z-transform ROC problems, examiners specifically check whether you correctly associate causal sequences with exterior ROC (|z| > |pole|) and anti-causal with interior ROC.
- Circular convolution versus linear convolution is a favourite distinction — expect a question asking you to identify which length of DFT avoids time-aliasing.
- When computing FFT butterfly stages, show the twiddle factor W_N^r explicitly at each stage; partial credit depends on demonstrating correct stage-by-stage indexing.
- FIR filter symmetry conditions for linear phase (Types I–IV) appear regularly; remember that Type II filters always have a zero at z = −1.