UNIT 2: Digital Signal Processing Core Concepts

1.0 Discrete-Time Signals and Systems

1.1 Discrete-Time Signals

• Representation: A discrete-time signal $x[n]$ is a sequence of numbers indexed by integer $n$.

  • Graphical: Stem plot.

  • Mathematical: Formula like $$\displaystyle x[n] = a^n u[n] $$.

  • Sequence form: $\{x[0], x[1], x[2], ...\}$ or $\{..., x[-1], x[0], x[1], ...\}$.

• Typical Sequences:

  | Sequence | Definition | Properties | |----------|-------------|-------------| | Unit sample $\delta[n]$ | $$\displaystyle \delta[n] = 1 $$ for $$\displaystyle n=0 $$, $0$ otherwise | Sifting property: $$\displaystyle \sum_{k=-\infty}^{\infty} x[k]\delta[n-k] = x[n] $$ | | Unit step $u[n]$ | $$\displaystyle u[n] = 1 $$ for $n \geq 0$, $0$ otherwise | $$\displaystyle u[n] = \sum_{k=-\infty}^{n} \delta[k] $$ | | Exponential $$\displaystyle a^n u[n] $$ | Right-sided; $a$ real/complex | Stable if $$\displaystyle |a| < 1 $$ (for causal) | | Sinusoid $$\displaystyle \cos(\omega_0 n) u[n] $$ | Periodic if $$\displaystyle \omega_0/2\pi $$ rational | Always bounded | | Complex exponential $$\displaystyle e^{j\omega_0 n} $$ | $$\displaystyle e^{j\omega_0 n} = \cos(\omega_0 n) + j\sin(\omega_0 n) $$ | Fundamental for Fourier analysis |

• Energy and Power:

  • Energy: $$\displaystyle E = \sum_{n=-\infty}^{\infty} |x[n]|^2 $$. Finite for finite-duration or absolutely summable signals.

  • Power: $$\displaystyle P = \lim_{N\to\infty} \frac{1}{2N+1} \sum_{n=-N}^{N} |x[n]|^2 $$. Finite for periodic or bounded non-periodic signals.

  • Example: $$\displaystyle x[n] = a^n u[n] $$: Energy finite if $$\displaystyle |a|<1 $$; Power = 0 if $$\displaystyle |a|<1 $$, infinite if $|a| \geq 1$.

[!TIP] Exam Tip: For periodic signals, compute power over one period: $$\displaystyle P = \frac{1}{N} \sum_{n=0}^{N-1} |x[n]|^2 $$.

1.2 Classification of Discrete-Time Systems

[!TIP] Common Pitfall: For stability, check absolute summability of impulse response, not just boundedness.

1.3 Linear Time-Invariant (LTI) Systems

• Difference Equation: General $N$-th order: $$\displaystyle \sum_{k=0}^{N} a_k y[n-k] = \sum_{k=0}^{M} b_k x[n-k] $$, with $$\displaystyle a_0=1 $$ (causal form).

  • Order: $\max(N,M)$.

• Impulse Response $h[n]$: Output when $$\displaystyle x[n] = \delta[n] $$, zero initial conditions (zero-state).

  • From difference equation: solve recursively or use Z-transform ($$\displaystyle h[n] \leftrightarrow H(z) $$).

• System Properties via $h[n]$:

  • Causal: $$\displaystyle h[n] = 0 $$ for $$\displaystyle n < 0 $$.

  • Stable: $$\displaystyle \sum_{n=-\infty}^{\infty} |h[n]| < \infty $$.

  • Memory: If $h[n]$ has finite duration → FIR (memoryless if $h[0]$ only); else IIR (dynamic).

1.4 System Implementations

Direct Form I

• Block diagram: Chain of adders and delays for $y[n]$ side, separate chain for $x[n]$ side, then combine.

• Delays: $N$ delays for $N$-th order system.

• Memory: $2N$ multipliers (if feedforward/feedback coefficients differ).

Direct Form II

• Minimal delays: Only $N$ delays shared between feedforward and feedback paths.

• Memory: $N$ multipliers (more efficient).

• Sensitivity: More prone to coefficient quantization errors (poles/zeros closer to each other).

Comparison:

[!TIP] For high-order filters, use cascade or parallel forms to reduce sensitivity.

1.5 State-Space Representation

• State Equations:

$$ \mathbf{x}[n+1] = \mathbf{A} \mathbf{x}[n] + \mathbf{B} u[n], \quad y[n] = \mathbf{C} \mathbf{x}[n] + D u[n] $$

where $\mathbf{x}[n]$ is state vector (size $N$), $u[n]$ input, $y[n]$ output.

• Signal Flow Graph (SFG):

  • Each state variable is a node.

  • Arrows from $\mathbf{x}[n]$ to $\mathbf{x}[n+1]$ with gains from $\mathbf{A}$.

  • Arrows from $u[n]$ to states (gains from $\mathbf{B}$) and to output ($D$).

  • Output $y[n]$ from states (gains from $\mathbf{C}$).

• Example: For $$\displaystyle \mathbf{A} = \begin{bmatrix}0.5 & 1 \\ 0 & 0.5\end{bmatrix} $$, $$\displaystyle \mathbf{B} = \begin{bmatrix}1 \\ 0\end{bmatrix} $$, $$\displaystyle \mathbf{C} = [1\ 1] $$, $$\displaystyle D=0 $$:

  • Nodes: $$\displaystyle x_1[n] $$, $$\displaystyle x_2[n] $$.

  • $$\displaystyle x_1[n+1] = 0.5 x_1[n] + 1 x_2[n] + u[n] $$.

  • $$\displaystyle x_2[n+1] = 0.5 x_2[n] $$.

  • $$\displaystyle y[n] = x_1[n] + x_2[n] $$.

  • SFG: Two delay loops, with $$\displaystyle x_1 $$ fed back to itself and to $$\displaystyle x_2 $$.

[!TIP] Mason's gain rule can compute transfer function $$\displaystyle H(z) = \mathbf{C}(z\mathbf{I}-\mathbf{A})^{-1}\mathbf{B} + D $$.

2.0 Z-Transform Analysis

2.1 Definition and Properties

• Bilateral Z-Transform: $$\displaystyle X(z) = \sum_{n=-\infty}^{\infty} x[n] z^{-n} $$.

• Unilateral Z-Transform (causal systems): $$\displaystyle X(z) = \sum_{n=0}^{\infty} x[n] z^{-n} $$.

• Linearity: $$\displaystyle a x_1[n] + b x_2[n] \leftrightarrow a X_1(z) + b X_2(z) $$.

• Time Shifting:

  • Delay: $$\displaystyle x[n-n_0] \leftrightarrow z^{-n_0} X(z) $$.

  • Advance: $$\displaystyle x[n+n_0] \leftrightarrow z^{n_0} X(z) - \sum_{k=0}^{n_0-1} x[k] z^{n_0-k} $$ (unilateral).

• Scaling in z-domain: $$\displaystyle a^n x[n] \leftrightarrow X(z/a) $$.

• Convolution Property: $$\displaystyle x_1[n] * x_2[n] \leftrightarrow X_1(z) X_2(z) $$ (ROC contains intersection of individual ROCs).

• Differentiation in z-domain: $$\displaystyle \sum_{n=-\infty}^{\infty} n x[n] z^{-n-1} = -\frac{dX(z)}{dz} $$.

• Initial Value Theorem (causal): $$\displaystyle x[0] = \lim_{z\to\infty} X(z) $$.

• Final Value Theorem (if poles of $(z-1)X(z)$ inside unit circle): $$\displaystyle \lim_{n\to\infty} x[n] = \lim_{z\to 1} (z-1)X(z) $$.

• Parseval's Theorem: $$\displaystyle \sum_{n=-\infty}^{\infty} x_1[n] x_2^*[n] = \frac{1}{2\pi j} \oint_{C} X_1(z) X_2^*(1/z^*) dz^* $$.

2.2 Region of Convergence (ROC)

• Definition: Set of $z$ for which $X(z)$ converges (finite).

• For Rational $$\displaystyle X(z) = \frac{N(z)}{D(z)} $$:

  • ROC is annulus or disk bounded by poles.

  • $X(z)$ converges for $$\displaystyle |z| > r_{\text{max}} $$ (right-sided), $$\displaystyle |z| < r_{\text{min}} $$ (left-sided), $$\displaystyle r_{\text{min}} < |z| < r_{\text{max}} $$ (two-sided).

• Implications:

  | Sequence Type | ROC | Causality | Stability | |---------------|-----|-----------|-----------| | Right-sided (causal) | $$\displaystyle |z| > r_{\text{max}} $$ (outside outermost pole) | Yes | ROC includes unit circle ($$\displaystyle |z|=1 $$) | | Left-sided (anti-causal) | $$\displaystyle |z| < r_{\text{min}} $$ (inside innermost pole) | No | ROC includes unit circle | | Two-sided | $$\displaystyle r_{\text{min}} < |z| < r_{\text{max}} $$ | No | ROC includes unit circle |

[!TIP] Key: For causal and stable LTI system, ROC is outside all poles and includes unit circle → all poles inside unit circle.

2.3 Inverse Z-Transform Methods

1. Partial Fraction Expansion (PFE):

   • For rational $X(z)$, expand into simpler terms.

   • ROC determines sequence type:

     • ROC $$\displaystyle |z|>r $$: causal terms ($$\displaystyle a^n u[n] $$).

     • ROC $$\displaystyle |z|<r $$: anti-causal terms ($$\displaystyle -a^n u[-n-1] $$).

   • Example: $$\displaystyle X(z) = \frac{1}{(1-az^{-1})(1-bz^{-1})} = \frac{A}{1-az^{-1}} + \frac{B}{1-bz^{-1}} $$.

2. Power Series Expansion (long division): Directly read $x[n]$ as coefficients of $$\displaystyle z^{-n} $$ series.

3. Contour Integration (Residue Theorem): $$\displaystyle x[n] = \frac{1}{2\pi j} \oint_{C} X(z) z^{n-1} dz $$ (theoretical).

2.4 Rational Z-Transform and Pole-Zero Analysis

• System Function: $$\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}} = \frac{B(z)}{A(z)} $$.

• Poles: Roots of $$\displaystyle A(z)=0 $$ (denominator). Zeros: Roots of $$\displaystyle B(z)=0 $$ (numerator).

• Pole-Zero Plot: Poles (×), zeros (○) on z-plane.

• Stability (causal): All poles strictly inside unit circle ($$\displaystyle |p_i| < 1 $$).

• Frequency Response: Evaluate $H(z)$ on unit circle: $$\displaystyle H(e^{j\omega}) = H(z)|_{z=e^{j\omega}} $$.

  • Magnitude/phase from distances/angles to poles/zeros.

• Significance:

  • Poles near unit circle → sharp resonance, long impulse response.

  • Zeros on unit circle → notch filter (zero gain at that frequency).

[!TIP] Gibbs Phenomenon: Sharp cutoff in FIR → oscillations in frequency response due to slow decay of sinc.

2.5 Solving Difference Equations Using Z-Transform

• Steps:

  1. Take unilateral Z-transform of both sides (include initial conditions via time-shift property).

  2. Solve for $Y(z)$.

  3. Partial fraction expansion.

  4. Inverse Z-transform using ROC (causal → ROC outside outermost pole).

• Example: $$\displaystyle y[n] - 0.5 y[n-1] + 0.25 y[n-2] = x[n] $$, $$\displaystyle x[n]=\delta[n] $$, $$\displaystyle y[-1]=1 $$, $$\displaystyle y[-2]=0 $$.

  • Transform: $$\displaystyle Y(z) - 0.5(z^{-1}Y(z) + y[-1]) + 0.25(z^{-2}Y(z) + z^{-1}y[-1] + y[-2]) = 1 $$.

  • Solve: $$\displaystyle Y(z)(1 - 0.5z^{-1} + 0.25z^{-2}) = 1 + 0.5 y[-1] - 0.25 z^{-1} y[-1] = 1 + 0.5(1) - 0.25 z^{-1}(1) = 1.5 - 0.25 z^{-1} $$.

  • $$\displaystyle Y(z) = \frac{1.5 - 0.25 z^{-1}}{1 - 0.5z^{-1} + 0.25z^{-2}} $$.

  • Poles at $$\displaystyle z = 0.25 \pm j0.43 $$ (inside unit circle). Inverse gives $y[n]$.

3.0 Discrete Fourier Series and Discrete Fourier Transform

3.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} $$, periodic in $k$ with period $N$.

• Properties (for periodic sequences):

  | Property | Time Domain | Frequency Domain | |----------|-------------|------------------| | Linearity | $$\displaystyle a x_1[n] + b x_2[n] $$ | $$\displaystyle a c_{1,k} + b c_{2,k} $$ | | Time Shifting | $$\displaystyle x[n-n_0] $$ | $$\displaystyle c_k e^{-j\frac{2\pi}{N} k n_0} $$ | | Frequency Shifting | $$\displaystyle x[n] e^{j\frac{2\pi}{N} m n} $$ | $$\displaystyle c_{k-m} $$ | | Time Reversal | $x[-n]$ | $$\displaystyle c_{-k} = c_{N-k} $$ | | Convolution | $$\displaystyle x_1[n] * x_2[n] $$ (circular) | $$\displaystyle N c_{1,k} c_{2,k} $$ | | Parseval | $$\displaystyle \frac{1}{N}\sum_{n=0}^{N-1} |x[n]|^2 = \sum_{k=0}^{N-1} |c_k|^2 $$ | — |

[!TIP] Circular convolution: $$\displaystyle (x_1 * x_2)[n] = \sum_{m=0}^{N-1} x_1[m] x_2[(n-m) \mod N] $$.

3.2 Discrete Fourier Transform (DFT)

• For finite-length $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,...,N-1. $$

• Inverse DFT (IDFT):

$$ x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2\pi}{N} kn}. $$

• Relation to DFS: DFT of length-$N$ sequence = DFS coefficients of its periodic extension with period $N$.

• Properties (state and prove key ones):

  | Property | Expression | |----------|-------------| | Linearity | $$\displaystyle a x_1[n] + b x_2[n] \leftrightarrow a X_1[k] + b X_2[k] $$ | | Circular Time Shifting | $$\displaystyle x[(n-n_0)\mod N] \leftrightarrow X[k] e^{-j\frac{2\pi}{N} k n_0} $$ | | Circular Frequency Shifting | $$\displaystyle x[n] e^{j\frac{2\pi}{N} m n} \leftrightarrow X[(k-m)\mod N] $$ | | Time Reversal | $$\displaystyle x[(-n)\mod N] \leftrightarrow X[(-k)\mod N] $$ | | Conjugation | $$\displaystyle x^*[n] \leftrightarrow X^*[(-k)\mod N] $$ | | Circular Convolution | $$\displaystyle x_1[n] \circledast x_2[n] \leftrightarrow X_1[k] X_2[k] $$ | | Parseval | $$\displaystyle \sum_{n=0}^{N-1} |x[n]|^2 = \frac{1}{N} \sum_{k=0}^{N-1} |X[k]|^2 $$ |

[!TIP] Proof Sketch: Use IDFT expression and substitute for linearity/circular shift.

3.3 Circular Convolution

• Definition: $$\displaystyle (x_1 \circledast x_2)[n] = \sum_{m=0}^{N-1} x_1[m] x_2[(n-m) \mod N] $$.

• Difference from Linear: Linear convolution length $$\displaystyle L_1+L_2-1 $$; circular assumes periodic extension, length $N$.

• Computation Methods:

  1. Concentric Circles Method (graphical):

     • Write $$\displaystyle x_1[n] $$ on outer circle (clockwise), $$\displaystyle x_2[n] $$ on inner (counterclockwise).

     • Rotate inner circle by $n$ steps, multiply corresponding points, sum.

  2. Matrix Method: $$\displaystyle \mathbf{y} = \mathbf{X}_1 \mathbf{x}_2 $$, where $$\displaystyle \mathbf{X}_1 $$ is circulant matrix with first row $$\displaystyle x_1[0], x_1[N-1], ..., x_1[1] $$.

• Example: $$\displaystyle x_1 = \{1,2,3,4\} $$, $$\displaystyle x_2 = \{1,5,1,3\} $$, $$\displaystyle N=4 $$:

  • $$\displaystyle y[0] = 1\cdot1 + 2\cdot3 + 3\cdot2 + 4\cdot5 = 1+6+6+20=33 $$.

  • $$\displaystyle y[1] = 1\cdot5 + 2\cdot1 + 3\cdot3 + 4\cdot2 = 5+2+9+8=24 $$.

  • $$\displaystyle y[2] = 1\cdot1 + 2\cdot5 + 3\cdot1 + 4\cdot3 = 1+10+3+12=26 $$.

  • $$\displaystyle y[3] = 1\cdot3 + 2\cdot1 + 3\cdot5 + 4\cdot1 = 3+2+15+4=24 $$.

  • Result: $\{33, 24, 26, 24\}$.

4.0 Fast Fourier Transform (FFT) Algorithms

4.1 FFT Fundamentals

• DFT Complexity: $$\displaystyle O(N^2) $$ multiplications/additions.

• FFT Goal: $$\displaystyle O(N \log_2 N) $$ via divide-and-conquer.

• Key Idea: Split $N$-point DFT into smaller DFTs (radix-2: even/odd indices).

• Bit-Reversal Permutation (DIT): Input indices reversed in binary order before butterfly computation.

  • Example: $$\displaystyle N=8 $$, index 3 (011) → 4 (100).

4.2 Decimation in Time (DIT) FFT

• Decomposition: Separate even-indexed and odd-indexed samples:

$$ X[k] = \sum_{n=0}^{N/2-1} x[2n] W_N^{2nk} + \sum_{n=0}^{N/2-1} x[2n+1] W_N^{(2n+1)k}, $$

where $$\displaystyle W_N = e^{-j2\pi/N} $$.

• $$\displaystyle = E[k] + W_N^k O[k] $$, with $$\displaystyle E[k] = \sum x[2n] W_{N/2}^{nk} $$, $$\displaystyle O[k] = \sum x[2n+1] W_{N/2}^{nk} $$.

• Note: $E[k]$, $O[k]$ are $(N/2)$-point DFTs, periodic with period $N/2$.

• Butterfly (basic unit):

$$ \begin{aligned} X[k] &= E[k] + W_N^k O[k] \\ X[k+N/2] &= E[k] - W_N^k O[k] \end{aligned} $$

for $$\displaystyle k=0,...,N/2-1 $$.

• Example: 8-point DIT:

  1. Bit-reverse input order.

  2. Stage 1: 4 butterflies with $$\displaystyle W_8^0=1 $$.

  3. Stage 2: 2 butterflies with $$\displaystyle W_8^0=1 $$, $$\displaystyle W_8^2=-j $$.

  4. Stage 3: 1 butterfly with $$\displaystyle W_8^0=1 $$, $$\displaystyle W_8^1=e^{-j\pi/4} $$.

4.3 Decimation in Frequency (DIF) FFT

• Decomposition: Split frequency indices into even/odd $k$:

$$ X[2k] = \sum_{n=0}^{N-1} x[n] (W_N^{2})^{kn} = \sum_{n=0}^{N-1} x[n] W_{N/2}^{kn}, $$

$$ X[2k+1] = \sum_{n=0}^{N-1} x[n] W_N^{n} W_{N/2}^{kn}. $$

• Butterfly:

$$ \begin{aligned} E[k] &= x[n] + x[n+N/2] \\ O[k] &= (x[n] - x[n+N/2]) W_N^{n} \end{aligned} $$

for $$\displaystyle n=0,...,N/2-1 $$.

• Example: 8-point DIF:

  1. No bit-reversal (output in order).

  2. Stage 1: Combine $x[n]$ with $x[n+4]$, multiply difference by $$\displaystyle W_8^n $$.

  3. Stage 2: Combine with $$\displaystyle W_8^0=1 $$, $$\displaystyle W_8^2=-j $$.

  4. Stage 3: Combine with $$\displaystyle W_8^0=1 $$, $$\displaystyle W_8^1=e^{-j\pi/4} $$.

[!TIP] DIT: bit-reverse input, natural output. DIF: natural input, bit-reverse output.

4.4 FFT for Composite N (Cooley-Tukey)

• Mixed-Radix: $$\displaystyle N = N_1 \times N_2 $$.

• Index Mapping: $$\displaystyle n = n_1 + N_1 n_2 $$, $$\displaystyle k = k_2 + N_2 k_1 $$.

  • $$\displaystyle N_1 $$-point DFTs on "rows", then $$\displaystyle N_2 $$-point DFTs on "columns".

• Twiddle Factors: $$\displaystyle W_N^{n_1 k_2} $$ between stages.

• Example: $$\displaystyle N=6 = 2 \times 3 $$, $$\displaystyle x[n] = \{1,2,3,4,5,6\} $$.

  1. First stage (by 2): Split into even/odd: $$\displaystyle x_{\text{even}} = \{1,3,5\} $$, $$\displaystyle x_{\text{odd}} = \{2,4,6\} $$.

     • Compute 3-point DFT of each: $E[k]$, $O[k]$, $$\displaystyle k=0,1,2 $$.

  2. Second stage (by 3): For each $k$, combine:

$$ X[k] = E[k] + W_6^{k} O[k], \quad X[k+3] = E[k] - W_6^{k} O[k]. $$

 Twiddles: $$\displaystyle W_6^0=1 $$, $$\displaystyle W_6^1=e^{-j\pi/3} $$, $$\displaystyle W_6^2=e^{-j2\pi/3} $$.

• Decomposition Steps:

  • Choose factor order (e.g., $$\displaystyle N_1=2 $$, $$\displaystyle N_2=3 $$).

  • Map indices, compute smaller DFTs, multiply by twiddles, combine.

4.5 Radix-2 FFT Implementation (Example)

• Sequence: $$\displaystyle x[n] = \{1,1,1,0,0,0,0,0\} $$, $$\displaystyle N=8 $$.

• DIT Steps:

  1. Bit-reverse: $$\displaystyle \{x[0],x[4],x[2],x[6],x[1],x[5],x[3],x[7]\} = \{1,0,1,0,1,0,0,0\} $$.

  2. Stage 1 (4 butterflies, $$\displaystyle W_8^0=1 $$):

     • $(1,0) \to (1,1)$; $(1,0) \to (1,1)$; $(1,0) \to (1,1)$; $(0,0) \to (0,0)$.

     • After stage 1: $\{1,1, 1,1, 1,1, 0,0\}$.

  3. Stage 2 (2 butterflies, $$\displaystyle W_8^0=1 $$, $$\displaystyle W_8^2=-j $$):

     • First pair: $(1,1)$ with $$\displaystyle W_8^0=1 $$: $\to (2,0)$, $(0,0)$.

     • Second pair: $(1,1)$ with $$\displaystyle W_8^2=-j $$: $\to (1-j, 1+j)$.

     • After stage 2: $\{2,0, 1-j, 1+j, 0,0, 0,0\}$.

  4. Stage 3 (1 butterfly, $$\displaystyle W_8^0=1 $$, $$\displaystyle W_8^1=e^{-j\pi/4} $$):

     • Combine first half with twiddle $$\displaystyle W_8^0=1 $$: $\to (3-j, 1+j)$.

     • Combine second half with twiddle $$\displaystyle W_8^1 $$: $$\displaystyle \to (1-j - (1+j)e^{-j\pi/4}, ...) $$.

     • Final $X[k]$: $\{3, 1-j, -j, 1+j, 3, 1+j, j, 1-j\}$ (verify symmetry).

[!TIP] Always verify conjugate symmetry for real inputs: $$\displaystyle X[N-k] = X^*[k] $$.

5.0 Multidimensional DFT

5.1 Two-Dimensional 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^{-j2\pi(\frac{km}{M} + \frac{ln}{N})}. $$

• Separability: Compute 1D DFT on rows (length $N$), then on columns (length $M$).

  • $$\displaystyle X[k,l] = \sum_{m=0}^{M-1} \left[ \sum_{n=0}^{N-1} x[m,n] e^{-j2\pi ln/N} \right] e^{-j2\pi km/M} $$.

• Example: $2\times2$ matrix $\begin{bmatrix}1 & 2 \\ 3 & 4\end{bmatrix}$.

  1. Row DFT (N=2): Row1: $\{1,2\} \to \{3, -1\}$; Row2: $\{3,4\} \to \{7, -1\}$.

  2. Column DFT (M=2): Col1: $\{3,7\} \to \{10, -4\}$; Col2: $\{-1,-1\} \to \{-2, 0\}$.

  3. Result: $\begin{bmatrix}10 & -2 \\ -4 & 0\end{bmatrix}$.

• Applications: Image filtering, compression, enhancement in frequency domain.

6.0 Digital Filter Design

6.1 FIR Filter Design Using Window Method

• Ideal Low-pass Filter (brick-wall):

  • Frequency response: $$\displaystyle H_d(e^{j\omega}) = 1 $$ for $$\displaystyle |\omega| \leq \omega_c $$, $0$ for $$\displaystyle \omega_c < |\omega| \leq \pi $$.

  • Impulse response: $$\displaystyle h_d[n] = \frac{\omega_c}{\pi} \text{sinc}\left(\frac{\omega_c n}{\pi}\right) $$, non-causal, infinite duration.

• Window Method Steps:

  1. Specify cutoff $$\displaystyle \omega_c $$ (e.g., $0.4\pi$), filter length $N$ (odd for symmetric linear phase).

  2. Compute ideal $$\displaystyle h_d[n] = \frac{\omega_c}{\pi} \frac{\sin(\omega_c n)}{\omega_c n} $$ for $$\displaystyle n = -(N-1)/2, ..., (N-1)/2 $$.

  3. Shift to causal: $$\displaystyle h[n] = h_d[n - (N-1)/2] $$.

  4. Apply window $w[n]$ (length $N$): $$\displaystyle h_{\text{window}}[n] = h[n] w[n] $$, $$\displaystyle n=0,...,N-1 $$.

• Common Windows (mainlobe width, sidelobe attenuation):

  | Window | Mainlobe (rad) | Sidelobe (dB) | |--------|----------------|---------------| | Rectangular | $4\pi/N$ | -13 | | Hanning | $8\pi/N$ | -31 | | Hamming | $8\pi/N$ | -41 | | Blackman | $12\pi/N$ | -58 |

• Trade-off: Wider mainlobe → sharper transition but more ripple.

• Example: $$\displaystyle N=21 $$, $$\displaystyle \omega_c = 0.4\pi $$, rectangular window.

  • $$\displaystyle h_d[n] = \frac{0.4\pi}{\pi} \text{sinc}(0.4 n) = 0.4 \text{sinc}(0.4 n) $$ for $$\displaystyle n=-10,...,10 $$.

  • Shift: $$\displaystyle h[n] = h_d[n-10] $$, $$\displaystyle n=0,...,20 $$.

  • Apply $$\displaystyle w[n]=1 $$ (rectangular) → $$\displaystyle h_{\text{final}}[n] = h[n] $$.

  • Coefficients: $$\displaystyle h[10] = 0.4 $$ (center), symmetric.

[!TIP] Gibbs phenomenon: Ripples in passband/stopband due to abrupt truncation. Use windows to reduce.

6.2 IIR Filter Design Methods

Impulse Invariant Method

• Mapping: Sample analog impulse response $$\displaystyle h_a(t) $$: $$\displaystyle h[n] = T h_a(nT) $$, where $T$ sampling period.

• Z-transform: $$\displaystyle H(z) = \sum_{n=-\infty}^{\infty} h[n] z^{-n} = \frac{1}{T} \sum_{k=-\infty}^{\infty} H_a\left(s = \frac{j\Omega + j2\pi k}{T}\right) $$.

• Aliasing: Replicated analog frequency responses sum → bandlimited analog prototype required.

• Example: $$\displaystyle H_a(s) = \frac{1}{s+1} $$, $$\displaystyle T=1 $$.

  • $$\displaystyle h_a(t) = e^{-t} u(t) $$.

  • $$\displaystyle h[n] = e^{-n} u[n] $$.

  • $$\displaystyle H(z) = \frac{1}{1 - e^{-1} z^{-1}} = \frac{z}{z - 0.3679} $$.

• Limitation: Aliasing if analog filter not bandlimited.

Bilinear Transformation

• Mapping: $$\displaystyle s = \frac{2}{T} \frac{1 - z^{-1}}{1 + z^{-1}} $$ (or $$\displaystyle z = \frac{1 + sT/2}{1 - sT/2} $$).

• Properties:

  • Stability preserved: LHP ($$\displaystyle \text{Re}(s)<0 $$) $\to$ inside unit circle.

  • Frequency mapping: $$\displaystyle \omega = \frac{2}{T} \tan(\Omega T/2) $$ (nonlinear, pre-warping needed).

• Design Steps:

  1. Pre-warp digital specs: $$\displaystyle \Omega_d = \frac{2}{T} \tan(\omega_d/2) $$.

  2. Design analog prototype $$\displaystyle H_a(s) $$ with $$\displaystyle \Omega_c = \Omega_d $$.

  3. Apply bilinear transform: replace $s$ by $$\displaystyle \frac{2}{T}\frac{1-z^{-1}}{1+z^{-1}} $$.

• Example: Design high-pass IIR, digital $$\displaystyle \omega_c = 0.5\pi $$, Butterworth order 2, $$\displaystyle T=1 $$.

  1. Pre-warp: $$\displaystyle \Omega_c = 2 \tan(0.5\pi/2) = 2 \tan(\pi/4) = 2 $$.

  2. Analog high-pass Butterworth (order 2, $$\displaystyle \Omega_c=2 $$): $$\displaystyle H_a(s) = \frac{s^2}{s^2 + \sqrt{2}\cdot2 s + 4} $$.

  3. Bilinear: $$\displaystyle s = 2\frac{1-z^{-1}}{1+z^{-1}} $$.

     • Substitute, simplify to get $H(z)$.

[!TIP] Pre-warping is crucial: design analog filter at warped frequency to get correct digital cutoff.

6.3 Comparison of IIR and FIR Filters

6.4 Comparison of Butterworth and Chebyshev Filters

[!TIP] Chebyshev Type II: equiripple in stopband, flat passband.

7.0 Short Note Topics (Recurring)

7.1 Rational Z-Transform

• Definition: $$\displaystyle X(z) = \frac{B(z)}{A(z)} = \frac{\sum_{k=0}^{M} b_k z^{-k}}{1 + \sum_{k=1}^{N} a_k z^{-k}} $$.

• Poles/Zeros: Zeros from $$\displaystyle B(z)=0 $$, poles from $$\displaystyle A(z)=0 $$.

• ROC:

  • For causal: $$\displaystyle |z| > \max|p_i| $$.

  • For anti-causal: $$\displaystyle |z| < \min|p_i| $$.

• Causality & Stability:

  • Causal $\iff$ ROC outside outermost pole.

  • Stable $\iff$ ROC includes unit circle $\iff$ all poles inside unit circle (for causal).

• Example: $$\displaystyle X(z) = \frac{1}{1 - 0.5z^{-1}} $$: pole at $$\displaystyle z=0.5 $$, ROC $$\displaystyle |z|>0.5 $$ → causal, stable.

7.2 Properties of DFS

1. Linearity: $$\displaystyle a x_1[n] + b x_2[n] \leftrightarrow a c_{1,k} + b c_{2,k} $$.

2. Time Shifting: $$\displaystyle x[n-n_0] \leftrightarrow c_k e^{-j\frac{2\pi}{N}kn_0} $$.

3. Frequency Shifting: $$\displaystyle x[n] e^{j\frac{2\pi}{N}mn} \leftrightarrow c_{k-m} $$.

4. Time Reversal: $$\displaystyle x[-n] \leftrightarrow c_{-k} $$.

5. Convolution: $$\displaystyle x_1[n] \circledast x_2[n] \leftrightarrow N c_{1,k} c_{2,k} $$.

6. Parseval: $$\displaystyle \frac{1}{N}\sum_{n=0}^{N-1} |x[n]|^2 = \sum_{k=0}^{N-1} |c_k|^2 $$.

7. Duality: $$\displaystyle c_n \leftrightarrow N x[-k] $$.

7.3 Discrete-Time Signals

• Representations:

  • Graphical: Stem plot.

  • Mathematical: $$\displaystyle x[n] = \text{expression} $$.

  • Sequence: $\{..., x[-1], x[0], x[1], ...\}$.

• Typical Sequences:

  • $\delta[n]$: unit sample.

  • $u[n]$: unit step.

  • $$\displaystyle a^n u[n] $$: exponential (causal).

  • $$\displaystyle \cos(\omega_0 n) $$: sinusoid.

  • $$\displaystyle e^{j\omega_0 n} $$: complex exponential.

• Energy: $$\displaystyle E = \sum_{n=-\infty}^{\infty} |x[n]|^2 $$.

• Power: $$\displaystyle P = \lim_{N\to\infty} \frac{1}{2N+1} \sum_{n=-N}^{N} |x[n]|^2 $$.

  • Periodic: $$\displaystyle P = \frac{1}{N} \sum_{n=0}^{N-1} |x[n]|^2 $$.

7.4 Decomposition for Composite N (Cooley-Tukey)

• Idea: $$\displaystyle N = N_1 N_2 $$, compute $$\displaystyle N_1 $$ DFTs of length $$\displaystyle N_2 $$, then $$\displaystyle N_2 $$ DFTs of length $$\displaystyle N_1 $$.

• Index Mapping: $$\displaystyle n = n_1 + N_1 n_2 $$, $$\displaystyle k = k_2 + N_2 k_1 $$.

• Twiddle Factors: $$\displaystyle W_N^{n_1 k_2} $$ between stages.

• Example: $$\displaystyle N=6=2\times3 $$ for $$\displaystyle x[n]=\{1,2,3,4,5,6\} $$.

  1. Stage 1 (by 2): Even/odd split → two 3-point DFTs.

  2. Stage 2 (by 3): Combine with twiddles $$\displaystyle W_6^k $$.

• Advantage: Reduces complexity from $$\displaystyle O(N^2) $$ to $O(N \log N)$ for composite $N$.

[!TIP] For mixed-radix, choose factors to minimize twiddle factor multiplications. Radix-2 most common for powers of 2.

Final Notes for Exam:

• Always state assumptions (causality, zero ICs) when solving.

• For stability, compute $$\displaystyle \sum |h[n]| $$ or check poles.

• For FFT, show butterfly diagram and twiddle factors.

• For filter design, list steps clearly and plot frequency response sketch.

• Box key results: Transfer functions, filter coefficients, DFT values.