Lecture 2A: LCCDEs and System Analysis

Table of Contents

Introduction to Linear Constant Coefficient Difference Equations (LCCDEs)

Linear Constant Coefficient Difference Equations form the mathematical foundation for describing and analyzing discrete-time Linear Time-Invariant (LTI) systems. These equations are fundamental to digital signal processing because they provide a compact mathematical representation of how a system transforms input signals into output signals.

Mathematical Foundation

General Form of LCCDEs

The most general form of a Linear Constant Coefficient Difference Equation is:

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

This can be expanded as: $a_0 y[n] + a_1 y[n-1] + a_2 y[n-2] + \cdots + a_N y[n-N] = b_0 x[n] + b_1 x[n-1] + \cdots + b_M x[n-M]$

Key Parameters:

• $y[n]$: Output sequence at time index $n$
• $x[n]$: Input sequence at time index $n$
• $a_k$: Feedback coefficients (determine system poles)
• $b_k$: Feedforward coefficients (determine system zeros)
• $N$: Order of the system (highest delay in output)
• $M$: Order of the numerator (highest delay in input)

Assumptions:

1. Linearity: The equation is linear in both input and output
2. Constant Coefficients: All $a_k$ and $b_k$ are time-invariant
3. Causality: Usually $a_0 \neq 0$ for a causal system

Standard Form

We typically normalize the equation by dividing by $a_0$:

$y[n] + \frac{a_1}{a_0}y[n-1] + \cdots + \frac{a_N}{a_0}y[n-N] = \frac{b_0}{a_0}x[n] + \frac{b_1}{a_0}x[n-1] + \cdots + \frac{b_M}{a_0}x[n-M]$

This gives us the recursive form: $y[n] = -\sum_{k=1}^{N} \frac{a_k}{a_0}y[n-k] + \sum_{k=0}^{M} \frac{b_k}{a_0}x[n-k]$

Auxiliary Conditions and Uniqueness

The Uniqueness Problem

A difference equation alone does not uniquely specify the system’s behavior. For an $N$-th order system, we need exactly $N$ auxiliary conditions to determine a unique solution.

Why auxiliary conditions are needed:

1. The difference equation represents a relationship between past and present values
2. Without initial conditions, there are infinitely many solutions
3. Each solution differs by the homogeneous solution

Types of Auxiliary Conditions

1. Initial Conditions: Specify $y[-1], y[-2], \ldots, y[-N]$
2. Boundary Conditions: Specify values at specific time points
3. Initial Rest Conditions: Assume $y[n] = 0$ for $n < 0$ when $x[n] = 0$ for $n < 0$

Fundamental Example: The Accumulator System

Definition and Properties

The accumulator is one of the most fundamental discrete-time systems:

Mathematical Definition: $y[n] = \sum_{k=-\infty}^{n} x[k]$

Recursive Implementation: $y[n] = y[n-1] + x[n]$

Physical Interpretation:

• Accumulates (sums) all past and present input values
• Digital equivalent of an analog integrator
• Memory element that “remembers” all previous inputs

Efficiency Considerations

Direct Implementation: Requires storing all past inputs → $O(n)$ memory and computation Recursive Implementation: Requires only previous output → $O(1)$ memory and computation

This demonstrates why recursive implementations are preferred in practical DSP systems.

System Properties

1. Linearity: $T[ax_1[n] + bx_2[n]] = aT[x_1[n]] + bT[x_2[n]]$
2. Time-Invariance: $T[x[n-n_0]] = y[n-n_0]$ (under initial rest conditions)
3. Memory: System has infinite memory (depends on all past inputs)
4. Causality: Output depends only on present and past inputs

Solution Methods for LCCDEs

Complete Solution Structure

The complete solution to an LCCDE consists of two parts:

$y[n] = y_h[n] + y_p[n]$

where:

• $y_h[n]$: Homogeneous solution (natural response)
• $y_p[n]$: Particular solution (forced response)

Homogeneous Solution

For the homogeneous equation: $\sum_{k=0}^{N} a_k y_h[n-k] = 0$

Solution Method:

1. Assume solution of the form $y_h[n] = z^n$
2. Substitute into homogeneous equation
3. Factor out $z^{n-N}$ to get characteristic equation: $a_0 z^N + a_1 z^{N-1} + \cdots + a_N = 0$

Case 1: Distinct Roots If roots $z_1, z_2, \ldots, z_N$ are distinct: $y_h[n] = A_1 z_1^n + A_2 z_2^n + \cdots + A_N z_N^n$

Case 2: Repeated Roots If root $z_i$ has multiplicity $r$: $y_h[n] = (A_{i1} + A_{i2}n + A_{i3}n^2 + \cdots + A_{ir}n^{r-1})z_i^n + \text{other terms}$

Particular Solution

Methods for finding particular solutions:

1. Method of Undetermined Coefficients: Assume form based on input
2. Variation of Parameters: General method for any input
3. Transform Methods: Use Z-transform techniques

Detailed First-Order Example

System Setup

Consider the first-order LCCDE: $y[n] - ay[n-1] = x[n]$

with:

• Input: $x[n] = K\delta[n]$ (impulse of magnitude $K$)
• Initial condition: $y[-1] = c$

Step-by-Step Solution

Forward Recursion:

For $n = 0$: $y[0] = ay[-1] + x[0] = ac + K$

For $n = 1$: $y[1] = ay[0] + x[1] = a(ac + K) + 0 = a^2c + aK$

For $n = 2$: $y[2] = ay[1] + x[2] = a(a^2c + aK) + 0 = a^3c + a^2K$

General Pattern: $y[n] = a^{n+1}c + Ka^n u[n], \quad n \geq 0$

where $u[n]$ is the unit step function.

System Analysis

Components of the Solution:

1. Zero-input response: $a^{n+1}c$ (due to initial condition)
2. Zero-state response: $Ka^n u[n]$ (due to input)

System Properties with Non-zero Initial Conditions:

• Non-linear: Doubling input doesn’t double output due to initial condition term
• Time-variant: Shifting input doesn’t simply shift output

Initial Rest Condition (IRC)

Definition: If $x[n] = 0$ for $n < 0$, then $y[n] = 0$ for $n < 0$.

Significance:

• Ensures system linearity and time-invariance
• Makes system causal and realizable
• Standard assumption in DSP system analysis

Under IRC: $c = 0$, so $y[n] = Ka^n u[n]$

Frequency Domain Representation of LTI Systems

Fundamental Concepts

System Characterization

An LTI system is completely characterized by its impulse response $h[n]$:

Convolution Relationship: $y[n] = x[n] * h[n] = \sum_{k=-\infty}^{\infty} x[k]h[n-k] = \sum_{k=-\infty}^{\infty} h[k]x[n-k]$

Complex Exponential Response

Eigenfunction Property

Complex exponentials are eigenfunctions of LTI systems. For input $x[n] = e^{j\omega n}$ (for all $n$):

$y[n] = \sum_{k=-\infty}^{\infty} h[k] \cdot e^{j\omega(n-k)}$

$= \sum_{k=-\infty}^{\infty} h[k] \cdot e^{j\omega n} \cdot e^{-j\omega k}$

$= e^{j\omega n} \sum_{k=-\infty}^{\infty} h[k] e^{-j\omega k}$

Frequency Response Definition

The frequency response is defined as: $H(e^{j\omega}) = \sum_{k=-\infty}^{\infty} h[k]e^{-j\omega k}$

Key Properties:

1. Eigenvalue: $H(e^{j\omega})$ is the eigenvalue corresponding to eigenfunction $e^{j\omega n}$
2. DTFT: $H(e^{j\omega})$ is the Discrete-Time Fourier Transform of $h[n]$
3. Periodicity: $H(e^{j\omega})$ is periodic with period $2\pi$

Output Relationship

For complex exponential input: $x[n] = e^{j\omega n} \rightarrow y[n] = H(e^{j\omega}) e^{j\omega n}$

Practical Example: Ideal Delay System

System Definition

$y[n] = x[n-n_d]$ where $n_d$ is the delay in samples.

Impulse Response

$h[n] = \delta[n-n_d]$

Frequency Response Calculation

For input $x[n] = e^{j\omega n}$: $y[n] = e^{j\omega(n-n_d)} = e^{-j\omega n_d} \cdot e^{j\omega n}$

Therefore: $H(e^{j\omega}) = e^{-j\omega n_d}$

Analysis of Delay System

Magnitude Response: $|H(e^{j\omega})| = |e^{-j\omega n_d}| = 1$ (All frequencies pass through with equal magnitude)

Phase Response: $\arg[H(e^{j\omega})] = -\omega n_d$ (Linear phase - constant group delay)

Group Delay: $\tau_g = -\frac{d}{d\omega}\arg[H(e^{j\omega})] = n_d$

Sinusoidal Steady-State Response

Input Signal Decomposition

For sinusoidal input $x[n] = A\cos(\omega_0 n + \phi)$:

Using Euler’s formula: $x[n] = \frac{A}{2}e^{j\phi}e^{j\omega_0 n} + \frac{A}{2}e^{-j\phi}e^{-j\omega_0 n}$

System Response

$y[n] = \frac{A}{2}e^{j\phi}H(e^{j\omega_0})e^{j\omega_0 n} + \frac{A}{2}e^{-j\phi}H(e^{-j\omega_0})e^{-j\omega_0 n}$

Since $H(e^{j\omega})$ is generally complex: $H(e^{j\omega_0}) = |H(e^{j\omega_0})|e^{j\theta_0}$

For real impulse response: $H(e^{-j\omega_0}) = H^*(e^{j\omega_0})$

Final Sinusoidal Response

$y[n] = A|H(e^{j\omega_0})|\cos(\omega_0 n + \phi + \theta_0)$

where:

• Amplitude is scaled by $|H(e^{j\omega_0})|$
• Phase is shifted by $\arg[H(e^{j\omega_0})]$

Frequency Selective Filters

Classification of Filters

Low-Pass Filters

Characteristics:

• Pass low frequencies: $|H(e^{j\omega})| \approx 1$ for $|\omega| < \omega_c$
• Attenuate high frequencies: $|H(e^{j\omega})| \approx 0$ for $|\omega| > \omega_c$
• Cutoff frequency: $\omega_c$

Applications:

• Anti-aliasing filters
• Noise reduction
• Smoothing operations

High-Pass Filters

Characteristics:

• Attenuate low frequencies: $|H(e^{j\omega})| \approx 0$ for $|\omega| < \omega_c$
• Pass high frequencies: $|H(e^{j\omega})| \approx 1$ for $|\omega| > \omega_c$

Applications:

• Edge detection
• DC removal
• High-frequency noise emphasis

Band-Pass Filters

Characteristics:

• Pass frequencies in band: $\omega_1 < |\omega| < \omega_2$
• Attenuate frequencies outside band

Applications:

• Communication systems
• Audio equalizers
• Spectral analysis

Band-Stop (Notch) Filters

Characteristics:

• Attenuate frequencies in band: $\omega_1 < |\omega| < \omega_2$
• Pass frequencies outside band

Applications:

• Power line interference removal
• Narrow-band noise elimination

Filter Design Parameters

Key Specifications

1. Passband: Frequencies that should pass through
2. Stopband: Frequencies that should be attenuated
3. Transition band: Region between passband and stopband
4. Ripple: Allowable variation in passband and stopband
5. Roll-off rate: Steepness of transition

DTFT Analysis and System Response

Mathematical Foundation

Transform Pair Definition

The DTFT provides a frequency domain representation of discrete-time signals:

Analysis Equation (Forward Transform): $X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n}$

Synthesis Equation (Inverse Transform): $x[n] = \frac{1}{2\pi} \int_{-\pi}^{\pi} X(e^{j\omega})e^{j\omega n} d\omega$

Properties of the DTFT

Fundamental Properties:

1. Periodicity: $X(e^{j(\omega + 2\pi)}) = X(e^{j\omega})$
2. Linearity: $ax_1[n] + bx_2[n] \leftrightarrow aX_1(e^{j\omega}) + bX_2(e^{j\omega})$
3. Time Shifting: $x[n-n_0] \leftrightarrow e^{-j\omega n_0}X(e^{j\omega})$
4. Frequency Shifting: $e^{j\omega_0 n}x[n] \leftrightarrow X(e^{j(\omega-\omega_0)})$
5. Time Reversal: $x[-n] \leftrightarrow X(e^{-j\omega})$
6. Conjugation: $x^*[n] \leftrightarrow X^*(e^{-j\omega})$

Comprehensive Example: Two-Point Moving Average

System Definition

Consider the two-point moving average filter: $y[n] = \frac{1}{2}x[n-1] + \frac{1}{2}x[n-2]$

Impulse response: $h[n] = \frac{1}{2}\delta[n-1] + \frac{1}{2}\delta[n-2]$

DTFT Calculation

Step 1: Apply definition $H(e^{j\omega}) = \sum_{n=-\infty}^{\infty} h[n] e^{-j\omega n} = \frac{1}{2}e^{-j\omega} + \frac{1}{2}e^{-j2\omega}$

Step 2: Factor common terms $H(e^{j\omega}) = \frac{1}{2}e^{-j\omega}(1 + e^{-j\omega})$

Step 3: Use Euler’s formula $1 + e^{-j\omega} = 1 + \cos(\omega) - j\sin(\omega) = 2\cos(\omega/2)e^{-j\omega/2}$

Step 4: Combine results $H(e^{j\omega}) = \frac{1}{2}e^{-j\omega} \cdot 2\cos(\omega/2)e^{-j\omega/2} = e^{-j3\omega/2}\cos(\omega/2)$

Complete Analysis

Magnitude Response: $|H(e^{j\omega})| = |\cos(\omega/2)|$

Phase Response:

For $\cos(\omega/2) \geq 0$: $\arg[H(e^{j\omega})] = -\frac{3\omega}{2}$

For $\cos(\omega/2) < 0$: $\arg[H(e^{j\omega})] = -\frac{3\omega}{2} + \pi$

Filter Characteristics:

• Type: Low-pass filter
• DC Gain: $|H(e^{j0})| = 1$
• Nyquist Gain: $|H(e^{j\pi})| = 0$
• First Zero: At $\omega = \pi$ (Nyquist frequency)
• Group Delay: $\tau_g = 1.5$ samples

Physical Interpretation

This filter:

1. Averages two consecutive samples with equal weight
2. Smooths the input signal by reducing high-frequency components
3. Introduces delay of 1.5 samples on average
4. Completely removes signals at the Nyquist frequency

The $\cos(\omega/2)$ magnitude response shows the characteristic low-pass filtering behavior, with gradual roll-off from DC to Nyquist frequency.

System Stability and Pole-Zero Analysis

Stability Analysis for LTI Systems

Bounded-Input Bounded-Output (BIBO) Stability

Definition: A system is BIBO stable if every bounded input produces a bounded output.

Mathematical Condition: For LTI systems, BIBO stability is equivalent to: $\sum_{n=-\infty}^{\infty} |h[n]| < \infty$

This means the impulse response must be absolutely summable.

Relationship to System Poles

For systems described by LCCDEs, stability is determined by the characteristic equation roots (poles):

Stability Condition: All poles must lie inside the unit circle in the z-plane: $|z_i| < 1 \text{ for all poles } z_i$

Connection Between Time and Frequency Domain

Stable System: $\sum |h[n]| < \infty$ ⟹ DTFT exists and is continuous

Unstable System: Some poles outside unit circle ⟹ DTFT may not exist in classical sense

Practical Design Considerations

Computational Efficiency

Direct Form Implementation: Requires $N+M+1$ multiplications per output sample

Factored Form: May reduce computational complexity and improve numerical stability

Cascade/Parallel Forms: Break complex systems into simpler subsystems

Numerical Issues

1. Coefficient Quantization: Limited precision affects pole locations
2. Round-off Noise: Accumulates in recursive structures
3. Overflow: Large intermediate values in fixed-point implementations

Real-Time Constraints

1. Causality: System must be implementable with finite delay
2. Memory Requirements: Practical systems have finite memory
3. Processing Time: Computations must complete within sample period

This comprehensive framework provides the mathematical foundation for analyzing and designing discrete-time LTI systems using LCCDEs and frequency domain techniques.