Unit 1: Core Concepts of Digital Signal Processing
A. Discrete-Time Signals and Systems
1. Representations of Discrete-Time Signals
-
Graphical: Plot of amplitude vs. integer index
n. -
Mathematical: Explicit formula, e.g., $$\displaystyle x[n] = a^n u[n] $$.
-
Sequence Form: Tabular or enumerated list, e.g., $$\displaystyle x[n] = \{1, 2, 3, 0, 0\} $$ for $$\displaystyle n=0,1,2,3,4 $$.
2. Classification of Discrete-Time Signals
| Class | Definition | Example |
|---|---|---|
| Periodic/Aperiodic | Periodic if $$\displaystyle x[n] = x[n+N] $$ for all $n$, smallest $N$ is period. | $$\displaystyle x[n]=\cos(0.2\pi n) $$ is periodic ($$\displaystyle N=10 $$). |
| Even/Odd | Even: $$\displaystyle x[n] = x[-n] $$. Odd: $$\displaystyle x[n] = -x[-n] $$. | $$\displaystyle x[n]=n^2 $$ is even. $$\displaystyle x[n]=n^3 $$ is odd. |
| Energy/Power | Energy: $$\displaystyle E = \sum_{n=-\infty}^{\infty} |x[n]|^2 < \infty $$. Power: $$\displaystyle P = \lim_{N\to\infty} \frac{1}{2N+1} \sum_{n=-N}^{N} |x[n]|^2 $$. | Finite-duration signals have finite energy. Periodic signals have finite power. |
3. Classification of Systems
A system is a transformation $T: x[n] \to y[n]$.
-
Linear: Superposition holds. $$\displaystyle T\{a x_1[n] + b x_2[n]\} = a y_1[n] + b y_2[n] $$.
-
Time-Invariant (TI): A time shift in input causes identical shift in output. If $x[n] \to y[n]$, then $$\displaystyle x[n-n_0] \to y[n-n_0] $$.
-
Causal: Output depends only on present and past inputs. $y[n]$ depends only on $x[k]$ for $k \leq n$.
-
Stable (BIBO): Bounded input produces bounded output. $$\displaystyle \|x[n]\|_\infty < \infty \implies \|y[n]\|_\infty < \infty $$.
-
Memoryless: Output depends only on input at same index $n$.
-
Invertible: Unique input for every output. Existence of inverse system $$\displaystyle T^{-1} $$.
4. Linear Time-Invariant (LTI) Systems
-
Impulse Response: $$\displaystyle h[n] = T\{\delta[n]\} $$. Characterizes LTI system completely.
-
Convolution Sum: $$\displaystyle y[n] = x[n] * h[n] = \sum_{k=-\infty}^{\infty} x[k] h[n-k] $$.
Properties of Convolution: Commutative, associative, distributive, shift (time-shift property).
-
Difference Equations: Represent recursive systems.
-
General form: $$\displaystyle \sum_{k=0}^{N} a_k y[n-k] = \sum_{k=0}^{M} b_k x[n-k] $$.
-
Order: $N$ (highest delay in $y[n]$).
-
Solution: $$\displaystyle y[n] = y_h[n] + y_p[n] $$ (homogeneous + particular).
-
Homogeneous: Solve characteristic equation $$\displaystyle \sum_{k=0}^{N} a_k r^{-k} = 0 $$. Roots $$\displaystyle r_i $$ give $$\displaystyle y_h[n] = \sum C_i r_i^n $$.
-
Particular: Depends on input $x[n]$ (e.g., for polynomial/exponential input, try similar form).
-
-
5. System Property Analysis (Examples)
-
Causality: Check if $$\displaystyle h[n]=0 $$ for $$\displaystyle n<0 $$ (for causal LTI). Or, if $y[n]$ depends on $$\displaystyle x[k], k>n $$.
-
Stability (BIBO): For LTI, absolutely summable impulse response: $$\displaystyle \sum_{n=-\infty}^{\infty} |h[n]| < \infty $$.
-
Linearity: Test with two inputs and superposition.
-
Time-Invariance: Apply time shift to input and compare output shift.
Exam Tip: For LTI systems, always use $h[n]$ to check causality and stability. For non-LTI, analyze the defining equation directly.
B. System Realizations
1. Direct Form I
-
Block diagram with parallel branches for each $$\displaystyle b_k $$ (feedforward) and feedback branches for each $$\displaystyle a_k $$.
-
Delays: $N$ delay elements (where $N$ = order).
-
Adders: $N$ adders (for summing feedforward and feedback terms).
2. Direct Form II (Canonical Form)
-
Combines feedforward and feedback paths to share delay elements.
-
Delays: Only $N$ delay elements (same as DF-I).
-
Structure: "Ladder" or "cascade" of second-order sections (biquads) for higher order.
-
Memory: Reduced from $2N$ (DF-I) to $N$ delays.
3. Comparison: DF-I vs DF-II
| Feature | Direct Form I | Direct Form II |
|---|---|---|
| Number of Delays | $N$ | $N$ |
| Sensitivity | Less sensitive to coefficient quantization. | More sensitive (coefficient errors affect all states). |
| Structure | Two separate networks (feedforward & feedback). | Single network with shared delays. |
| Preferred Use | Fixed-point arithmetic (less error). | Floating-point or low-order filters. |
4. State-Space Representation
-
State Vector: $$\displaystyle \mathbf{x}[n] = [x_1[n], x_2[n], ..., x_N[n]]^T $$ (minimal set of past values).
-
State Equation: $$\displaystyle \mathbf{x}[n+1] = \mathbf{A} \mathbf{x}[n] + \mathbf{B} u[n] $$.
-
Output Equation: $$\displaystyle y[n] = \mathbf{C} \mathbf{x}[n] + D u[n] $$.
-
$\mathbf{A}, \mathbf{B}, \mathbf{C}, D$ are system matrices.
5. Signal Flow Graph (SFG)
-
Nodes: Represent variables (signals).
-
Branches: Represent multiplications by gains (coefficients) and delays.
-
Mason’s Gain Formula: $$\displaystyle T = \frac{\sum_{k} P_k \Delta_k}{\Delta} $$, where $$\displaystyle P_k $$ is forward path gain, $\Delta$ is determinant of graph, $$\displaystyle \Delta_k $$ is cofactor.
Conversion: From state-space, each state variable is a node. Draw branches from $\mathbf{A}$ matrix (from $$\displaystyle x_j $$ to $$\displaystyle x_i $$ gain $$\displaystyle a_{ij} $$), $\mathbf{B}$ (input to states), $\mathbf{C}$ (states to output).
C. Z-Transform Analysis
1. Definition
-
Bilateral (Two-sided): $$\displaystyle X(z) = \sum_{n=-\infty}^{\infty} x[n] z^{-n} $$.
-
Unilateral (One-sided): $$\displaystyle X(z) = \sum_{n=0}^{\infty} x[n] z^{-n} $$ (used for causal signals with initial conditions).
2. Key Properties
| Property | Time Domain | Z-Domain | ROC |
|---|---|---|---|
| Linearity | $$\displaystyle a x_1[n] + b x_2[n] $$ | $$\displaystyle a X_1(z) + b X_2(z) $$ | Intersection of ROCs |
| Time-Shift | $$\displaystyle x[n-n_0] $$ | $$\displaystyle z^{-n_0} X(z) $$ | Same as $X(z)$, except $$\displaystyle z=0,\infty $$ |
| Scaling | $$\displaystyle a^n x[n] $$ | $X(z/a)$ | $$\displaystyle |a| \cdot R_{outer} < |z| < |a| \cdot R_{inner} $$ |
| Convolution | $x[n] * h[n]$ | $X(z) H(z)$ | At least intersection of ROCs |
| Initial Value | $x[0]$ | $$\displaystyle \lim_{z \to \infty} X(z) $$ | ROC includes $\infty$ |
| Final Value | $$\displaystyle \lim_{n\to\infty} x[n] $$ | $$\displaystyle \lim_{z \to 1} (z-1) X(z) $$ | ROC includes $$\displaystyle z=1 $$, poles of $(z-1)X(z)$ inside unit circle |
3. Region of Convergence (ROC)
-
Properties:
-
ROC cannot contain any poles.
-
ROC is a ring (or annulus) in z-plane: $$\displaystyle R_1 < |z| < R_2 $$.
-
ROC of sum is at least intersection of individual ROCs.
-
ROC is connected.
-
-
For Right-Sided Sequences: ROC is exterior of outermost pole ($$\displaystyle |z| > R_{max} $$). Includes $\infty$ → Causal.
-
For Left-Sided Sequences: ROC is interior of innermost pole ($$\displaystyle |z| < R_{min} $$). Includes $$\displaystyle z=0 $$ → Anticausal.
-
For Two-Sided Sequences: ROC is a ring between poles.
-
Stability (BIBO) for LTI: ROC must include unit circle ($$\displaystyle |z|=1 $$). For causal LTI, all poles inside unit circle.
4. Rational Z-Transform & Pole-Zero Plot
-
$$\displaystyle 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}} = B \frac{\prod (1 - c_k z^{-1})}{\prod (1 - d_k z^{-1})} $$.
-
Zeros: Roots of numerator ($$\displaystyle z = c_k^{-1} $$).
-
Poles: Roots of denominator ($$\displaystyle z = d_k^{-1} $$).
-
Stability Criterion: For causal system, all poles $$\displaystyle |p_i| < 1 $$.
5. Inverse Z-Transform Methods
-
Partial Fraction Expansion (PFE): For rational $X(z)$.
-
Causal sequence: Expand in $$\displaystyle z^{-1} $$, ROC $$\displaystyle |z| > R_{max} $$.
-
Anticausal sequence: Expand in $z$, ROC $$\displaystyle |z| < R_{min} $$.
-
Two-sided: Combine causal and anticausal parts based on ROC.
-
-
Power Series (Long Division): Directly expand $X(z)$ as $$\displaystyle \sum x[n] z^{-n} $$.
-
Contour Integration (Residue Theorem): $$\displaystyle x[n] = \frac{1}{2\pi j} \oint X(z) z^{n-1} dz $$ (theoretical).
6. System Function $H(z)$
-
Derived from difference equation: $$\displaystyle Y(z) = \sum b_k z^{-k} X(z) - \sum_{k=1}^{N} a_k z^{-k} Y(z) \implies 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}} $$.
-
Analysis via Pole-Zero Plot:
-
Magnitude Response: $$\displaystyle |H(e^{j\omega})| $$ is distance from unit circle to zeros divided by distance to poles.
-
Stability: All poles inside unit circle.
-
Causality: ROC is exterior of outermost pole.
-
7. Solving Difference Equations using Z-Transform
-
Take unilateral Z-transform of both sides (use time-shift property with initial conditions).
-
Solve for $Y(z)$.
-
Perform inverse Z-transform (usually PFE) to get $y[n]$.
D. Frequency Domain Representations
1. Discrete Fourier Series (DFS)
-
For periodic $x[n]$ with period $N$: $$\displaystyle x[n] = \sum_{k=0}^{N-1} c_k e^{j \frac{2\pi}{N} kn} $$.
-
DFS Coefficients: $$\displaystyle c_k = \frac{1}{N} \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} kn} $$.
-
Properties: Time-shift ($$\displaystyle c_k e^{-j\frac{2\pi}{N} k m} $$), frequency-shift, time-reversal, convolution (circular), Parseval's: $$\displaystyle \sum |x[n]|^2 = N \sum |c_k|^2 $$.
2. Discrete Fourier Transform (DFT)
- For finite-length sequence $x[n]$, $0 \leq n \leq N-1$:
$$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} kn}, \quad k=0,1,...,N-1$$
-
Inverse DFT (IDFT): $$\displaystyle x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j \frac{2\pi}{N} kn} $$.
-
Relationship to DFS: DFT coefficients are DFS coefficients of the periodic extension $$\displaystyle \tilde{x}[n] = \sum_{m} x[n-mN] $$.
-
DFT Matrix: $$\displaystyle \mathbf{X} = \mathbf{W}_N \mathbf{x} $$, where $$\displaystyle [\mathbf{W}_N]_{k,n} = e^{-j \frac{2\pi}{N} kn} $$.
3. Key DFT Properties
| Property | Expression |
|---|---|
| Linearity | $$\displaystyle a x_1[n] + b x_2[n] \leftrightarrow a X_1[k] + b X_2[k] $$ |
| Circular Time-Shift | $$\displaystyle x[(n-m)]_N \leftrightarrow X[k] e^{-j \frac{2\pi}{N} km} $$ |
| Circular Frequency-Shift | $$\displaystyle x[n] e^{j \frac{2\pi}{N} m n} \leftrightarrow X[(k-m)]_N $$ |
| Time Reversal | $$\displaystyle x[-n]_N \leftrightarrow X[-k]_N $$ |
| Circular Convolution | $$\displaystyle x[n] \circledast h[n] \leftrightarrow X[k] H[k] $$ |
| Parseval's Theorem | $$\displaystyle \sum_{n=0}^{N-1} |x[n]|^2 = \frac{1}{N} \sum_{k=0}^{N-1} |X[k]|^2 $$ |
| Symmetry (Real x[n]) | $$\displaystyle X[k] = X^*[N-k] $$ (conjugate symmetry). $|X[k]|$ even, $\angle X[k]$ odd. |
4. Circular Convolution Computation
-
Concentric Circles Method: Visual rotation of sequences on two circles.
-
Matrix Method: $$\displaystyle x[n] \circledast h[n] = \mathbf{x}^T \mathbf{H}_c $$, where $$\displaystyle \mathbf{H}_c $$ is circulant matrix built from $h[n]$.
5. Two-Dimensional DFT (2D DFT)
- For $M \times N$ image $x[m,n]$:
$$X[k,l] = \sum_{m=0}^{M-1} \sum_{n=0}^{N-1} x[m,n] e^{-j \frac{2\pi}{M} km} e^{-j \frac{2\pi}{N} ln}$$
-
Separability: Compute 1D DFT along rows, then along columns (or vice versa).
-
Example (2x2): For $$\displaystyle x = \begin{bmatrix} a & b \\ c & d \end{bmatrix} $$, $$\displaystyle X[0,0] = a+b+c+d $$, $$\displaystyle X[0,1] = a-b+c-d $$, etc.
E. Fast Fourier Transform (FFT)
1. Need for FFT
-
Direct DFT: $$\displaystyle O(N^2) $$ complex multiplications.
-
FFT (Radix-2): $$\displaystyle O(N \log_2 N) $$ multiplications. Huge saving for large N.
2. Decimation in Time (DIT) FFT
-
Idea: Decompose $N$-point DFT into two $$\displaystyle \frac{N}{2} $$-point DFTs of even-indexed and odd-indexed samples.
-
Butterfly: $$\displaystyle X[k] = E[k] + W_N^k O[k] $$, $$\displaystyle X[k+\frac{N}{2}] = E[k] - W_N^k O[k] $$, where $$\displaystyle W_N = e^{-j\frac{2\pi}{N}} $$.
-
Bit-Reversal Permutation: Input sequence reordered by reversing binary bits of indices before computation.
-
Example (N=8): 3 stages, each with 4 butterflies. Twiddle factors $$\displaystyle W_8^k $$.
3. Decimation in Frequency (DIF) FFT
-
Idea: Decompose output into even and odd frequency bins.
-
Butterfly: $$\displaystyle E[k] = X[k] + X[k+\frac{N}{2}] $$, $$\displaystyle O[k] = (X[k] - X[k+\frac{N}{2}]) W_N^{-k} $$.
-
Data Ordering: Input in normal order, output in bit-reversed order (opposite of DIT).
4. Comparison: DIT vs DIF
| Aspect | DIT | DIF |
|---|---|---|
| Decomposition | Time domain (even/odd samples) | Frequency domain (even/odd bins) |
| Input Order | Bit-reversed | Normal |
| Output Order | Normal | Bit-reversed |
| Butterfly | $$\displaystyle E[k] + W_N^k O[k] $$ | $(X[k] + X[k+N/2])$ |
5. FFT for Composite N (Cooley-Tukey)
-
For $$\displaystyle N = N_1 \times N_2 $$, map 1D index $n$ to 2D: $$\displaystyle n = n_1 + N_1 n_2 $$.
-
Mixed-Radix: Compute $$\displaystyle N_2 $$ smaller DFTs of length $$\displaystyle N_1 $$, then $$\displaystyle N_1 $$ DFTs of length $$\displaystyle N_2 $$, with twiddle factor multiplications in between.
-
Example (N=6=2x3):
-
Split into 3 groups of 2 points (or 2 groups of 3).
-
Compute 3 DFTs of length 2.
-
Multiply by twiddles $$\displaystyle W_6^{n_1 k_2} $$.
-
Compute 2 DFTs of length 3 on the results.
-
6. Radix-2 FFT Implementation Steps
-
Bit-reverse input sequence.
-
For $$\displaystyle s = 1 $$ to $$\displaystyle \log_2 N $$ (stages):
-
$$\displaystyle m = 2^s $$, $m/2$ butterflies per group.
-
Twiddle factor $$\displaystyle W_N^{k} $$ where $$\displaystyle k = 0,1,...,m/2-1 $$.
-
-
Output is in normal order.
Exam Tip: For $$\displaystyle N=8 $$ DIT example, always show stage-by-stage with twiddle factors $$\displaystyle W_8^0=1, W_8^1=e^{-j\pi/4}, W_8^2=e^{-j\pi/2}, W_8^3=e^{-j3\pi/4} $$.
F. Digital Filter Design
1. FIR vs IIR Filters
| Feature | FIR Filters | IIR Filters |
|---|---|---|
| Structure | Non-recursive (no feedback) | Recursive (feedback) |
| Stability | Always stable (poles only at $$\displaystyle z=0 $$) | Conditional (poles must be inside unit circle) |
| Phase | Linear phase possible (symmetric/antisymmetric $h[n]$) | Non-linear phase (except all-pass) |
| Computational Cost | Higher order for sharp transition | Lower order for same spec |
| Design Methods | Window, Frequency Sampling, Optimal | Analog prototype (Impulse Invariant, Bilinear) |
2. FIR Design: Window Method
-
Ideal Lowpass Impulse Response: $$\displaystyle h_d[n] = \frac{\omega_c}{\pi} \text{sinc}\left(\frac{\omega_c}{\pi} n\right) $$ (non-causal, infinite).
-
Window Effect: Multiply $$\displaystyle h_d[n] $$ by window $w[n]$ to make it finite and causal.
-
Gibbs Phenomenon: Ripple in stopband due to abrupt truncation.
-
Main Lobe Width: Controls transition bandwidth ($$\displaystyle \Delta \omega \approx \frac{4\pi}{N} $$ for rectangular).
-
Side Lobe Level: Controls stopband attenuation.
-
-
Common Windows:
| Window | Side Lobe (dB) | Main Lobe Width | | :--- | :--- | :--- | | Rectangular | -13 | $$\displaystyle \frac{4\pi}{N} $$ | | Hanning | -31 | $$\displaystyle \frac{8\pi}{N} $$ | | Hamming | -41 | $$\displaystyle \frac{8\pi}{N} $$ | | Blackman | -58 | $$\displaystyle \frac{12\pi}{N} $$ |
-
Design Procedure:
-
Specify $$\displaystyle \omega_c $$, $\Delta \omega$, $$\displaystyle A_s $$ (stopband atten).
-
Choose window based on $$\displaystyle A_s $$ and $\Delta \omega$ (main lobe width $\geq \Delta \omega$).
-
Determine $N$ (from window specs).
-
Compute $$\displaystyle h[n] = h_d[n] w[n] $$, $$\displaystyle n = 0,1,...,N-1 $$ (shifted to causal: $$\displaystyle n = -(N-1)/2 $$ to $(N-1)/2$).
-
-
Example (Rectangular, N=21, $$\displaystyle \omega_c=0.4\pi $$):
$$\displaystyle h[n] = \frac{0.4\pi}{\pi} \text{sinc}(0.4 (n-10)) $$, for $$\displaystyle n=0,...,20 $$.
Symmetric ($N$ odd) → linear phase. $H(\omega)$ real and even.
3. IIR Design: Analog Prototype Transformations
-
Impulse Invariant Transformation:
-
Mapping: $$\displaystyle s = \frac{1}{T} \ln(z) $$.
-
Aliasing: Poles at $$\displaystyle s = s_k $$ map to $$\displaystyle z = e^{s_k T} $$. Aliasing occurs if analog filter not bandlimited.
-
Use only for lowpass with small $T$ or bandlimited analog filters.
-
-
Bilinear Transformation:
-
Mapping: $$\displaystyle s = \frac{2}{T} \frac{1 - z^{-1}}{1 + z^{-1}} $$.
-
Pre-warping: To meet digital spec at $$\displaystyle \omega_d $$, design analog prototype at $$\displaystyle \Omega_a = \frac{2}{T} \tan(\frac{\omega_d}{2}) $$.
-
Advantages: No aliasing, stability preserved (LHP → inside unit circle), one-to-one mapping.
-
Disadvantage: Frequency warping (non-linear relation between $$\displaystyle \Omega_a $$ and $$\displaystyle \omega_d $$).
-
-
Comparison:
| Aspect | Impulse Invariant | Bilinear | | :--- | :--- | :--- | | Aliasing | Yes | No | | Frequency Warping | No | Yes (requires pre-warping) | | Stability | Preserved | Preserved | | Best For | Bandlimited lowpass | General (lowpass, highpass, bandpass) |
4. Analog Prototypes
-
Butterworth: Maximally flat passband. Monotonic magnitude. Poles on circle in LHP.
-
Chebyshev: Equiripple passband (Type I) or stopband (Type II). Sharper transition than Butterworth for same order. Poles off circle.
Exam Tip: For bilinear design, always show pre-warping step: $$\displaystyle \Omega_c = \frac{2}{T} \tan(\frac{\omega_c}{2}) $$. For impulse invariant, show mapping $$\displaystyle z = e^{sT} $$ and note aliasing.