unit 4

Discrete-Time Signals and Systems: 

Introduction Discrete-Time Signals and Systems

The Taxonomy of Signals: 

The Taxonomy of Signals Signal: A function that conveys information Time Amplitude analog signals continuous-time signals discrete-time signals digital signals Continuous Continuous Discrete Discrete

Signal Process Systems: 

Signal Process Systems Signal Processing System signal output Facilitate the extraction of desired information e.g., Filters Parameter estimation

Signal Process Systems: 

Signal Process Systems analog system signal output continuous-time signal continuous-time signal discrete- time system signal output discrete-time signal discrete-time signal digital system signal output digital signal digital signal

Signal Process Systems: 

A important class of systems Signal Process Systems Linear Shift-Invariant Systems. Linear Shift-Invariant Discrete-Time Systems . In particular, we ’ ll discuss

Discrete-Time Signals and Systems: 

Discrete-Time Signals--- Sequences Discrete-Time Signals and Systems

Representation by a Sequence: 

Representation by a Sequence Discrete-time system theory Concerned with processing signals that are represented by sequences . 1 2 3 4 5 6 7 8 9 10 -1 -2 -3 -4 -5 -6 -7 -8 n x ( n )

Important Sequences: 

Important Sequences Unit-sample sequence ( n ) 1 2 3 4 5 6 7 8 9 10 -1 -2 -3 -4 -5 -6 -7 -8 n  ( n ) Sometime call ( n ) a discrete-time impulse ; or an impulse

Important Sequences: 

Important Sequences Unit-step sequence u ( n ) 1 2 3 4 5 6 7 8 9 10 -1 -2 -3 -4 -5 -6 -7 -8 n u ( n ) Fact:

Important Sequences: 

Important Sequences Real exponential sequence 1 2 3 4 5 6 7 8 9 10 -1 -2 -3 -4 -5 -6 -7 -8 n x ( n ) . . . . . .

Important Sequences: 

Important Sequences Sinusoidal sequence n x ( n )

Important Sequences: 

Important Sequences Complex exponential sequence

Important Sequences: 

Important Sequences A sequence x ( n ) is defined to be periodic with period N if Example: consider must be a rational number

Energy of a Sequence: 

Energy of a Sequence Energy of a sequence is defined by

Operations on Sequences: 

Operations on Sequences Sum Product Multiplication Shift

Sequence Representation Using delay unit: 

Sequence Representation Using delay unit 1 2 3 4 5 6 7 8 9 10 -1 -2 -3 -4 -5 -6 -7 -8 n x ( n ) a 1 a 2 a 7 a -3

Discrete-Time Signals and Systems: 

Linear Shift-Invariant Systems Discrete-Time Signals and Systems

Systems: 

Systems T [ ] x ( n ) y ( n )= T [ x ( n )] Mathematically modeled as a unique transformation or operator .

Linear Systems: 

Linear Systems T [ ] x ( n ) y ( n )= T [ x ( n )]

Examples:: 

Examples : Ideal Delay System Accumulator Moving Average T [ ] x ( n ) y ( n )= T [ x ( n )]

Examples:: 

Examples : Ideal Delay System Accumulator Moving Average T [ ] x ( n ) y ( n )= T [ x ( n )] Are these system linear?

Examples:: 

Examples: A Memoryless System T [ ] x ( n ) y ( n )= T [ x ( n )] Is this system linear?

Linear Systems: 

T [ ] x ( n ) y ( n )= T [ x ( n )] Linear Systems

Shift-Invariant Systems: 

Shift-Invariant Systems x ( n ) y ( n )= T [ x ( n )] T [ ] x ( n-k ) y ( n-k ) x ( n ) y ( n ) x ( n- 1) y ( n- 1) x ( n- 2) y ( n- 2)

Shift-Invariant Systems: 

Shift-Invariant Systems x ( n ) y ( n )= T [ x ( n )] T [ ] x ( n-k ) y ( n-k ) x ( n ) y ( n ) x ( n- 1) y ( n- 1) x ( n- 2) y ( n- 2)

Linear Shift-Invariant Systems: 

Linear Shift-Invariant Systems T [ ] x ( n ) y ( n )= T [ x ( n )]

Linear Shift-Invariant Systems: 

Linear Shift-Invariant Systems T [ ] x ( n ) y ( n )= T [ x ( n )]

Impulse Response: 

Impulse Response T [ ] x ( n )=  ( n ) h ( n )= T [  ( n )] 0 0 0 0

Convolution Sum: 

Convolution Sum T [ ]  ( n ) h ( n ) x ( n ) y ( n ) convolution A linear shift-invariant system is completely characterized by its impulse response.

Characterize a System: 

Characterize a System h(n) x ( n ) x ( n ) *h ( n )

Properties of Convolution Math: 

Properties of Convolution Math

Properties of Convolution Math: 

Properties of Convolution Math h 1 ( n ) x ( n ) h 2 ( n ) y ( n ) h 2 ( n ) x ( n ) h 1 ( n ) y ( n ) h 1 ( n )* h 2 ( n ) x ( n ) y ( n ) These systems are identical .

Properties of Convolution Math: 

Properties of Convolution Math h 1 ( n )+ h 2 ( n ) x ( n ) y ( n ) These two systems are identical . h 1 ( n ) x ( n ) h 2 ( n ) y ( n ) +

Example: 

Example 0 1 2 3 4 5 6 y ( n )=? 0 1 2 3 4 5 6

Example: 

Example 0 1 2 3 4 5 6 k x ( k ) 0 1 2 3 4 5 6 k h ( k ) 0 1 2 3 4 5 6 k h (0  k )

Example: 

Example 0 1 2 3 4 5 6 k x ( k ) 0 1 2 3 4 5 6 k h (0  k ) 0 1 2 3 4 5 6 k h (1  k ) compute y (0) compute y (1) How to computer y ( n )?

Example: 

Example 0 1 2 3 4 5 6 k x ( k ) 0 1 2 3 4 5 6 k h (0  k ) 0 1 2 3 4 5 6 k h (1  k ) compute y (0) compute y (1) How to computer y ( n )? Two conditions have to be considered . n < N and n  N .

Example: 

Example n < N n  N

Example: 

Example n < N n  N

Impulse Response of the Ideal Delay System: 

Impulse Response of the Ideal Delay System Ideal Delay System By letting x ( n )= ( n ) and y ( n )= h ( n ) , ( n  n d ) 0 1 2 3 4 5 6 n d

Impulse Response of the Ideal Delay System: 

Impulse Response of the Ideal Delay System ( n  n d ) 0 1 2 3 4 5 6 n d ( n  n d ) Shift; or Copy

Impulse Response of the Moving Average: 

Impulse Response of the Moving Average Moving Average  M 1  0  M 2 . . . . . .  ( n  k )

Impulse Response of the Accumulator: 

Impulse Response of the Accumulator Accumulator 0 . . .

Discrete-Time Signals and Systems: 

Stability and Causality Discrete-Time Signals and Systems

Stability: 

Stability Stable systems --- every bounded input produce a bounded output (BIBO) Necessary and sufficient condition for a BIBO

Prove Necessary Condition for Stablility: 

Prove Necessary Condition for Stablility Show that if x is bounded and S <  , then y is bounded. where M = max x ( n )

Prove Sufficient Condition for Stablility: 

Prove Sufficient Condition for Stablility Show that if S =  , then one can find a bounded sequence x such that y is unbounded. Define

Causality: 

Causality Causal systems --- output for y ( n 0 ) depends only on x ( n ) with n  n 0 . A causal system whose impulse response h ( n ) satisfies

Example:: 

Example: Show that the linear shift-invariant system with impulse response h ( n )= a n u ( n ) where | a| <1 is stable.

Discrete-Time Signals and Systems: 

Linear Constant-Coefficient Difference Equations Discrete-Time Signals and Systems

N-th Order Difference Equations: 

N-th Order Difference Equations Examples: Ideal Delay System Accumulator Moving Average

Compute y(n): 

Compute y ( n )

The Ideal Delay System: 

The Ideal Delay System Delay Delay Delay . . . x ( n ) y ( n ) n d sample delays x ( n ) y ( n )

The Moving Average: 

The Moving Average

The Moving Average: 

The Moving Average Attenuator + M +1 sample delay Accumulator system + _

Discrete-Time Signals and Systems: 

Frequency-Domain Representation of Discrete-Time Signals and Systems Discrete-Time Signals and Systems

Sinusoidal and Complex Exponential Sequences: 

Sinusoidal and Complex Exponential Sequences Play an important role in DSP LTI h ( n )

Frequency Response: 

Frequency Response eigenvalue eigenfunction

Frequency Response: 

Frequency Response magnitude phase

Example: The Ideal Delay System: 

Example: The Ideal Delay System magnitude phase

Example: The Ideal Delay System: 

Example: The Ideal Delay System

Periodic Nature of Frequency Response: 

Periodic Nature of Frequency Response

Periodic Nature of Frequency Response: 

Periodic Nature of Frequency Response   2 3 4 2 3 4

Periodic Nature of Frequency Response: 

Periodic Nature of Frequency Response   2 3 4 2 3 4 Generally, we choose  To represent one period in frequency domain.

Periodic Nature of Frequency Response: 

Periodic Nature of Frequency Response   Low Frequency High Frequency High Frequency

Ideal Frequency-Selective Filters: 

Ideal Frequency-Selective Filters    c  c 1    a  a 1  b  b    a  a 1  b  b Lowpass Filter Bandstop Filter Highpass Filter

Moving Average: 

Moving Average h ( n ) 0 0 M

Moving Average: 

Moving Average

Moving Average: 

Moving Average M =4 Lowpass Try larger M

Discrete-Time Signals and Systems: 

Representation of Sequences by Fourier Transform Discrete-Time Signals and Systems

Fourier Transform Pair: 

Fourier Transform Pair Analysis Synthesis Inverse Fourier Transform (IFT) Fourier Transform (FT)

Prove: 

Prove n = m

Prove: 

n  m Prove

Prove: 

= x ( n ) Prove

Notations: 

Notations Analysis Synthesis Inverse Fourier Transform (IFT) Fourier Transform (FT)

Real and Imaginary Parts : 

Real and Imaginary Parts Fourier Transform (FT) is a complex-valued function

Magnitude and Phase: 

Magnitude and Phase magnitude phase

Discrete-Time Signals and Systems: 

Discrete-Time Signals and Systems Symmetry Properties of Fourier Transform

Conjugate-Symmetric and Conjugate-Antiymmetric Sequences: 

Conjugate-Symmetric and Conjugate-Antiymmetric Sequences Conjugate-Symmetric Sequence Conjugate-Antisymmetric Sequence Called an even sequence if it is real. Called an odd sequence if it is real.

Sequence Decomposition: 

Sequence Decomposition Any sequence can be expressed as the sum of a conjugate-symmetric one and a conjugate-antisymmetric one , i.e., Conjugate Symmetric Conjugate Antiymmetric

Function Decomposition: 

Function Decomposition Any function can be expressed as the sum of a conjugate-symmetric one and a conjugate-antisymmetric one , i.e., Conjugate Symmetric Conjugate Antiymmetric

Conjugate-Symmetric and Conjugate-Antiymmetric Functions: 

Conjugate-Symmetric and Conjugate-Antiymmetric Functions Conjugate-Symmetric Function Conjugate-Antisymmetric Function Called an even function if it is real. Called an odd function if it is real.

Symmetric Properties: 

Symmetric Properties     magnitude phase     magnitude phase

Symmetric Properties: 

Symmetric Properties     magnitude phase     magnitude phase

Symmetric Properties: 

Symmetric Properties     magnitude phase     magnitude phase

Symmetric Properties: 

Symmetric Properties

Symmetric Properties: 

Symmetric Properties

Symmetric Properties for Real Sequence x(n): 

Symmetric Properties for Real Sequence x ( n )     magnitude phase Facts: 1. real part is even 2. Img. part is odd 3. Magnitude is even 4. Phase is odd 

Discrete-Time Signals and Systems: 

Discrete-Time Signals and Systems Fourier Transform Theorems

Linearity: 

Linearity

Time Shifting  Phase Change: 

Time Shifting  Phase Change

Frequency Shifting Signal Modulation: 

Frequency Shifting Signal Modulation

Time Reversal: 

Time Reversal

Differentiation in Frequency: 

Differentiation in Frequency

The Convolution Theorem: 

The Convolution Theorem

The Modulation or Window Theorem: 

The Modulation or Window Theorem

Parseval’s Theorem: 

Parseval ’ s Theorem Facts: Letting =0, then proven.

Parseval’s Theorem Energy Preserving: 

Parseval ’ s Theorem Energy Preserving

Example: Ideal Lowpass Filter: 

Example: Ideal Lowpass Filter

Example: Ideal Lowpass Filter: 

Example: Ideal Lowpass Filter The ideal lowpass fileter Is noncausal.

Example: Ideal Lowpass Filter: 

Example: Ideal Lowpass Filter The ideal lowpass fileter Is noncausal. To approximate the ideal lowpass filter using a window .

Example: Ideal Lowpass Filter: 

-4 -3 -2 -1 0 1 2 3 4 -1 0 1 2 M =3 -4 -3 -2 -1 0 1 2 3 4 -1 0 1 2 M =5 -4 -3 -2 -1 0 1 2 3 4 -1 0 1 2 M =19 Example: Ideal Lowpass Filter

Discrete-Time Signals and Systems: 

Discrete-Time Signals and Systems Existence of Fourier Transform

Key Issue: 

Key Issue Analysis Synthesis Does X ( e j  ) exist for all  ? We need that | X ( e j  )| <  for a ll 

Sufficient Condition for Convergence: 

Sufficient Condition for Convergence

More On Convergence: 

More On Convergence Define Uniform Convergence Mean-Square Convergence

Discrete-Time Signals and Systems: 

Discrete-Time Signals and Systems Important Transform Pairs

Fourier Transform Pairs: 

Fourier Transform Pairs Sequence Fourier Transform

Fourier Transform Pairs: 

Fourier Transform Pairs Sequence Fourier Transform

Fourier Transform Pairs: 

Fourier Transform Pairs Sequence Fourier Transform

Discrete-time Fourier Transform: 

Discrete-time Fourier Transform Dr.Praveen Kumar Maduri

Slide 112: 

Derivation of the Discrete-time Fourier Transform

Slide 113: 

Recall DTFS pair where

Slide 114: 

The limit of integration is over any interval of 2 p in w Periodic in w with period 2 p Thus,

DTFT Pair: 

DTFT Pair

Conditions for Convergence : 

Conditions for Convergence

Slide 117: 

Examples

Slide 120: 

IDTFT

Slide 121: 

6) Complex Exponentials

DTFT of Periodic Signals: 

DTFT of Periodic Signals Recall the following DTFT pair: Represent periodic signal x [ n ] in terms of DTFS:

Slide 123: 

Example: A discrete-time Sine Function

Slide 124: 

Example: A discrete-time Periodic Impulse Train The DTFS coefficients for this signal are: c k

Properties of DTFT: 

Properties of DTFT

Properties of DTFT: 

Properties of DTFT

Convolution Property: 

Convolution Property

Multiplication Property: 

Multiplication Property

DTFT: 

DTFT if exists (4.11.1) What’s about convergence??? 1. Absolute convergence: (4.11.4) (4.11.5) (4.11.2) (4.11.3)

DTFT (cont): 

DTFT (cont) must be 2. Mean-square convergence: The total energy of the error must approach zero, not an error itself! (4.12.1) Absolutely summable sequences always have finite energy. However, finite energy sequences are not necessary absolutely summable.

IDTFT: 

IDTFT IDTFT: (4.13.1) (4.13.2) Combining (4.11.1) and (4.12.2) (4.13.3) (4.13.4) shows where x n “lives” in the frequency domain.

Back to ideal filters: 

Back to ideal filters Ideal LPF:   2 0 1  c Using IDTFT: The response in (4.14.2) is not absolutely summable , therefore, the filter is not BIBO stable ! The response in (4.14.2) is not causal and is of an infinite length. (4.14.1) (4.14.2) As a result, the filter in (4.14.1) is not realizable . Similar derivations show that none of the ideal filters in slide 9 is realizable.

DTFT properties: 

DTFT properties (4.15.1) (4.15.2) (4.15.3) (4.15.4) (4.15.5) (4.15.6) continuous, periodic functions (4.15.6)

DTFTs of commonly used sequences: 

DTFTs of commonly used sequences

DTFT examples: 

DTFT examples ½ of DC value of u n (4.17.1) (4.17.2) (4.17.3) (4.17.4) (4.17.5) (4.17.6)

DTFT examples (cont): 

DTFT examples (cont) We can re-work the Parseval’s theorem (4.15.6) as follows: energy density (spectrum) Autocorrelation function: (4.18.1) (4.18.2)

DTFT examples (cont 2): 

DTFT examples (cont 2) One obvious problem with DTFT is that we can never compute it since x n needs to be known everywhere ! which is impossible! Therefore, DTFT is not practical to compute. Often, a finite dimension LTI system is described by LCCDE: (4.19.2) practical (finite dimensions) Prediction of steady-state behavior of LCCDE (4.19.1)

How to measure frequency response of an actual (unknown) filter?: 

How to measure frequency response of an actual (unknown) filter? 1. Perform two I/O experiments: 2. Analyze these measurements and form: That’s a good way to measure/estimate a frequency response for every . (4.20.1) (4.20.2) (4.20.3) (4.20.4) (4.20.5)

Slide 139: 

Objectives: Derivation of the DTFT Transforms of Common Signals Properties of the DTFT Lowpass and Highpass Filters Resources: Wiki: Discete -Time Fourier Transform JOS: DTFT Derivation MIT 6.003: Lecture 9 CNX: DTFT Properties SKM: DTFT Properties LECTURE 16: DISCRETE-TIME FOURIER TRANSFORM Audio: URL:

Slide 140: 

Discrete-Time Fourier Series Assume x [ n ] is a discrete-time periodic signal. We want to represent it as a weighted-sum of complex exponentials: Note that the notation < N > refers to performing the summation over an N samples which constitute exactly one period. We can derive an expression for the coefficients by using a property of orthogonal functions (which applies to the complex exponential above): Multiplying both sides by and summing over N terms: Interchanging the order of summation on the right side: We can show that the second sum on the right equals N if k = r and 0 if k  r :

Slide 141: 

Discrete-Time Fourier Series (Cont.) This provides a closed-form expression for the Discrete-Time Fourier Series: Note that the DT Fourier Series coefficients can be interpreted as in the CT case – they can be plotted as a function of frequency ( k  0 ) and demonstrate the a periodic signal has a line spectrum. As expected, this DT Fourier Series (DTFS) obeys the same properties we have seen for the CTFS and CTFT. Next, we will apply the DTFS to nonperiodic signals to produce the Discrete-Time Fourier Transform (DTFT).

Slide 142: 

Periodic Extension Assume x [ n ] is an aperiodic, finite duration signal. Define a periodic extension of x [ n ] : Note that: We can apply the complex Fourier series: Define: . Note this is periodic in  with period 2  . This implies: . Note that these are evenly spaced samples of our definition for .

Slide 143: 

Derive an inverse transform: As This results in our Discrete-Time Fourier Transform: Notes: The DTFT and inverse DTFT are not symmetric. One is integration over a finite interval ( 2π ), and the other is summation over infinite terms. The signal, x [ n ] is aperiodic, and hence, the transform is a continuous function of frequency. (Recall, periodic signals have a line spectrum.) The DTFT is periodic with period 2  . Later we will exploit this property to develop a faster way to compute this transform. The Discrete-Time Fourier Transform

Slide 144: 

Example: Unit Pulse and Unit Step Unit Pulse: The spectrum is a constant (and periodic over the range [-  ,  ] . Shifted Unit Pulse: Time delay produces a phase shift linearly proportional to  . Note that these functions are also periodic over the range [-  ,  ] . Unit Step: Since this is not a time-limited function, it has no DTFT in the ordinary sense. However, it can be shown that the inverse of this function is a unit step:

Slide 145: 

Example: Exponential Decay Consider an exponentially decaying signal:

Slide 146: 

The Spectrum of an Exponentially Decaying Signal Lowpass Filter: Highpass Filter:

Slide 147: 

Finite Impulse Response Lowpass Filter The frequency response of a time-limited pulse is a lowpass filter. We refer to this type of filter as a finite impulse response (FIR) filter. In the CT case, we obtained a sinc function (sin(x)/x) for the frequency response. This is close to a sinc function, and is periodic with period 2  .

Slide 148: 

Example: Ideal Lowpass Filter (Inverse) The Ideal Lowpass Filter Is Noncausal !

Slide 149: 

Properties of the DTFT Periodicity: Linearity: Time Shifting: Frequency Shifting: Example: Note the role periodicity plays in the result.

Slide 150: 

Properties of the DTFT (Cont.) Time Reversal: Conjugate Symmetry: Also: Differentiation in Frequency: Parseval’s Relation: Convolution:

Slide 151: 

Properties of the DTFT (Cont.) Time-Scaling:

Slide 152: 

Example: Convolution For A Sinewave

Slide 153: 

Summary Introduced the Discrete-Time Fourier Transform (DTFT) that is the analog of the Continuous-Time Fourier Transform. Worked several examples. Discussed properties:

Absolute and Square Summability: 

Absolute and Square Summability Absolute summability is sufficient condition for DTFT Some sequences may not be absolute summable but only square summable To represent square summable sequences with DTFT We can relax the uniform convergence condition Convergence is in mean-squared sense Error does not converge to zero for every value of  The mean-squared value of the error over all  does Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 154

Example: Ideal Lowpass Filter: 

Example: Ideal Lowpass Filter The periodic DTFT of the ideal lowpass filter is The inverse can be written as Not causal Not absolute summable but it has a DTFT? The DTFT converges in the mean-squared sense Role of Gibbs phenomenon Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 155

Example: Generalized DTFT : 

Example: Generalized DTFT DTFT of Not absolute summable Not even square summable But we define its DTFT as a pulse train Let’s place into inverse DTFT equation Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 156

Symmetric Sequence and Functions: 

Symmetric Sequence and Functions Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 157 Conjugate-symmetric Conjugate-antisymmetric Sequence Function

Symmetry Properties of DTFT: 

Symmetry Properties of DTFT Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 158 Sequence x[n] Discrete-Time Fourier Transform X( e j  ) x * [n] X * (e -j  ) x * [-n] X * (e j  ) Re{x[n]} X e (e j  ) (conjugate-symmetric part) jIm{x[n]} X o (e j  ) (conjugate-antisymmetric part) x e [n] X R (e j  ) = Re{X(e j  ) } x o [n] jX I (e j  ) = jIm{X(e j  ) } Any real x[n] X(e j  ) =X * (e -j  ) (conjugate symmetric) Any real x[n] X R (e j  ) =X R (e -j  ) (real part is even) Any real x[n] X I (e j  ) =-X I (e -j  ) (imaginary part is odd) Any real x[n] |X(e j  )| =|X(e -j  )| (magnitude is even) Any real x[n]  X(e j  ) =-  X(e -j  ) (phase is odd) x e [n] X R (e j  ) x o [n] jX I ( e j  )

Example: Symmetry Properties: 

Example: Symmetry Properties DTFT of the real sequence x[n]= a n u [n ] Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 159 DTFT of the real sequence x[n]= a n u [n ]

Fourier Transform Theorems: 

Fourier Transform Theorems Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 160 Sequence DTFT x[n] y[n] X(e j  ) Y(e j  ) ax[n]+by[n] aX(e j  )+b Y(e j  ) x[n-n d ] x[-n] X(e -j  ) nx[n] x[n]  y[n] X(e j  ) Y(e j  ) x[n]y[n]

Slide 161: 

Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 161 Fourier Transform Pairs [n-n o ] 1 a n u[n] |a|<1 u[n] cos(  o n+)