Discrete-Time Signals And Systems - NCTU

DSP (Spring, 2020) Discrete-Time Signals and Systems Discrete-Time Signals and Systems Introduction Signal processing (system analysis and design) Analog Digital History Before 1950s: analog signals/systems 1950s: Digital computer 1960s: Fast Fourier Transform (FFT) 1980s: Real-time VLSI digital signal processors Discrete-time signals are represented as sequences of numbers A typical digital signal processing system x(t) H1(s) y(t) Digital filter A/D x[n] x(t) D/A H2(s) y[n] Equivalent analog filter y(t) 2.1 Discrete-time Signals: Sequences Continuous-time signal – Defined along a continuum of times: x(t) Continuous-time system – Operates on and produces continuous-time signals. Discrete-time signal – Defined at discrete times: x[n] Discrete-time system – Operates on and produces discrete-time signals. NCTU EE 1

DSP (Spring, 2020) Discrete-Time Signals and Systems Remarks: Digital signals usually refer to the quantized discrete-time signals. Sampling: Very often, x[n] is obtained by sampling x(t). “the nth sample of the sequence” That is, x[n] x(nT ) , T: is the sampling period. But T is often not important in the discrete-time signal analysis. t n t Basic Sequences: Unit Sample Sequence 1, 0, n Remark: n 0, n 0. It is often called the discrete-time impulse or simply impulse. (Some books call it unit pulse sequence.) Unit Step Sequence n 0, n 0. 1, u n 0, Note 1: u[0] 1, well-defined. Note 2: u[n] m [m] ; n accumulated sum of all previous impulses [n] u[n] u[n 1] NCTU EE 2

DSP (Spring, 2020) Discrete-Time Signals and Systems Exponential Sequences x[n] A n A and are real numbers -- Combining basic sequences: A n x n 0 n 0 n 0 , x[n] A nu[n] Sinusoidal Sequences x n A cos 0 n for all n A: amplitude, 0 2 f 0 : frequency, : phase It can be viewed as a sampled continuous-time sinusoidal. However, it is not always periodic! Condition for being periodic with period N: x[n] x[n N ] That is, Or, A cos 0 n A cos 0 (n N ) 0 n N 0 n 2 k , where k, n are integers (k, a fixed number; n, a running index, Hence, n ). 0 N 2 k 0 2 k / N . f0 must be a rational number. One discrete-time sinusoid corresponds to multiple continuous-time sinusoids of different frequencies. x n A cos 0 n A cos ( 0 2 r )n for all n where r is any integer Typically, we pick up the lowest frequency (r 0) under the assumption that the original continuous-time sinusoidal has a limited frequency value, 0 0 2 or 0 . This is the unambiguous frequency interval. NCTU EE 3

DSP (Spring, 2020) Discrete-Time Signals and Systems Complex Exponential Sequences x[n] A n , A A e j , and e j 0 Hence, x[n] A e j ( 0 n ) A cos( 0 n ) j A sin( 0 n ) n n n 2.2 Discrete-Time Systems A discrete-time system is defined mathematically as a transformation or operator that maps an input sequence with values y[n] T x[n] x[n] into an output sequence with values y[n] . Ideal Delay y[n] x[n nd ], n , where nd is a fixed positive integer called the delay of the system. NCTU EE 4

DSP (Spring, 2020) Discrete-Time Signals and Systems Moving Average y[n] M2 1 x[n k ] M1 M 2 1 k M1 Memoryless: If the output y[n] at every value of n depends only on the input x[n] at the same value of n. Linear: If it satisfies the principle of superposition. (a) Additivity: T x1[n] x2 [n] T x1[n] T x2 [n] (b) Homogeneity or scaling: T ax[n] aT x[n] Time-invariant (shift-invariant): A time shift or delay of the input sequence causes a corresponding shift in the output sequence. y[n] delay T y[n-n0] x[n] x[n-n0] delay T Yn0[n] e.g. y[n] x[ n] is not time-invariant. Causality: For any n0 , the output sequence value at the index n n0 depends only on the input sequence values for n n0 Stability in the bounded-input, bounded-output sense (BIBO): If and only if every bounded input sequence produces a bounded output sequence. NCTU EE 5

DSP (Spring, 2020) Discrete-Time Signals and Systems Linear Time-invariant (LTI) Systems A linear system is completely characterized by its impulse response. (1) Sequence as a sum of delayed impulses: x[n] x[m] [n m] m (2) An LTI system due to x[n] [n] (3) x[n] [n] input y[n] h[n] (impulse response) yields m m x[m] [n m] yields y[n ] x[m]h[n m] Convolution sum: f 3 [ n ] f1 [ m ] f 2 [ n m ] f1 [ n ] f 2 [ n ] m Procedure of convolution 1. Time-reverse: h[m] h[ m] 2. Choose an n value 3. Shift h[ m] 4. Multiplication: h[n m] x[n] h[n m] by n: 5. Summation over m: y[n] x[m]h[n m] m Choose another n value, go to Step 3. NCTU EE 6

DSP (Spring, 2020) Discrete-Time Signals and Systems Properties of LTI Systems The properties of an LTI system can be observed from its impulse response. Commutative: x[n] h[n] h[n] x[n] Distributive: x[n] (h1[n] h2 [n]) x[n] h1[n] x[n] h2 [n] Cascade connection: h[n] h1[n] h2 [n] Parallel connection: h[n] h1[n] h2 [n] BIBO stability: If h[n] is absolutely summable , i.e., h[k ] S k Casual sequence Causal system: Memoryless LTI: NCTU EE h[n] 0, n 0 h[n] k [n] 7

DSP (Spring, 2020) Discrete-Time Signals and Systems Some frequently used systems: -- Ideal Delay h[n] [n nd ] y[n] x[n nd ] -- Moving Average y[n] M2 1 1 , M1 n M 2 x [ n k ] h[n] M 1 M 2 1 M1 M 2 1 k M1 0, otherwise -- Accumulator y[n] n h[n] u[n] , unit step x[k ] k Finite-duration Impulse Response (FIR): Its impulse response has only a finite number of nonzero samples. -- FIR systems are always stable. Infinite-duration Impulse Response (IIR): Its impulse response is infinite in duration. Inverse System: h[n] x[n] g[n] y[n] x[n] System g[n] is the inverse of h[n] h[n] g[n] [n] NCTU EE 8

DSP (Spring, 2020) Discrete-Time Signals and Systems Linear Constant-Coefficient Difference Equations An important class of LTI system is described by linear constant-coefficient equation. Difference Equation: (general form) N ak y[n k ] k 0 M bm x[n m] m 0 First-order system: Solution: y[n] ay[n 1] bx[n] y[n] y p [n] yh [n] particular solution homogeneou s solution Homogeneous solution: N ak y[n k ] 0 (x[n] 0) k 0 Particular solution: (experience!) Frequency-Domain Representation Eigenfunction and eigenvalue What is eigenfunction of a system T{.}? Cf [n] T f [n] , where C is a complex constant, eigenvalue. The output waveform has the same shape of the input waveform. The complex exponential sequence is the eigenfunction of any LTI system. x[n] e j n H ( e j ) h[k ]e LTI h[n] y[n] H (e j )e j n j k k Magnitude: H ( e j ) Phase: H (e j ) H (e j ) is periodic. The above eigenfunction analysis is valid when the input is applied to the system at n . NCTU EE 9

DSP (Spring, 2020) Discrete-Time Signals and Systems Fourier Transform of Sequences Interpretation: Decompose an “arbitrary” sequence into “sinusoidal components” of different frequencies. DTFT: Discrete-time Fourier Transform Analysis: X (e j ) x[n]e j n F{x[n]} n Synthesis: x[n] 1 2 X (e x[n] X (e j ) Remarks: j )e j n d F 1{ X (e j )} Discrete-Time Fourier Transform pair Fourier transform is also called Fourier spectrum. X (e j ) X (e j ) Magnitude spectrum: Phase spectrum: X (e j ) X (e j ) . 2 . is continuous in frequency, is “periodic” with period Does every x[n] have DTFT? Convergence conditions: “error” 0 as N (samples) (A) Absolutely summable x[n] (uniform convergence) n (B) Finite energy (square-summable) 2 x[n ] mean-square error 0 (mean-square convergence) n Gibbs phenomenon NCTU EE 10

DSP (Spring, 2020) Discrete-Time Signals and Systems DTFT of Special Functions -- Impulse [n] 1 [n n0 ] e j n0 -- Constant 1 2 ( 2 r ) ; An periodic impulse train. r Note: This is the analog impulse (delta) function. -- Cosine sequence cos( 0 n ) e j ( 0 2 k ) e j ( 0 2 k ) k -- Complex exponential e j 0 n 2 ( 0 2 r ) r -- Unit step 1 u[n] ( 2 r ) 1 e j r Symmetry Properties of Fourier Transform Any (complex) x[n] can be decomposed into x[n] xe [n] x0 [n] where Conjugate-symmetric part: xe [n] ( x[n] x * [ n]) / 2 Conjugate-antisymmetric part: x0 [n] ( x[n] x * [ n]) / 2 Remark: x[n] is conjugate-symmetric if x[n] x * [ n] x[n] is conjugate-antisymmetric if x[n] x * [ n] On the other hand, Key 1: X (e j ) Re[ X (e j )] j Im[ X (e j )] xe [n] Re[ X (e j )] , xo [n] j Im[ X (e j )] Similarly, X (e j ) can be decomposed into X (e j ) X e (e j ) X o (e j ) NCTU EE 11

DSP (Spring, 2020) Discrete-Time Signals and Systems where X e (e j ) is the conjugate-symmetric part and X o (e j ) is the conjugate-antisymmetric part Key 2: Re[ x[n]] X e (e j ) , j Im[ x[n]] X o (e j ) Special case 1: If x[n] is real, X (e j ) is conjugate symmetric (magnitude –even, phase – odd) Special case 2: If x[n] is conjugate-symmtric, X (e j ) is real. Real Imaginary Magnitude Phase NCTU EE 12

DSP (Spring, 2020) Discrete-Time Signals and Systems Fourier Transform Theorems -- Linearity If x[n] X (e j ) then y[n] Y (e j ) and ax[n] by[n] aX (e j ) bY (e j ) -- Time Shift If x[n] X (e j ) then x[n nd ] X (e j )e j nd -- Frequency Modulation If X (e j ) x[n] then e j 0 n x[n] X (e j ( 0 ) ) --Time Reversal x[n] X ( e j ) then x[-n] X ( e j ) If -- Differentiation in frequency If x[n] X ( e j ) then nx[n] NCTU EE dX (e j ) j d 13

DSP (Spring, 2020) Discrete-Time Signals and Systems -- Convolution If then x[n] X (e j ) and h[n] H (e j ) x[n] h[n] X (e j ) H (e j ) -- Multiplication If then x[n] x[n]w[n] X (e j ) 1 2 and X (e j w[n] W (e j ) )W (e j ( ) )d -- Parseval’s Theorem If then x[n] E X ( e j ) 1 x[n] 2 2 X (e j ) 2 d n NCTU EE 14

DSP (Spring, 2020) NCTU EE Discrete-Time Signals and Systems 15

2.1 Discrete-time Signals: Sequences Continuous-time signal - Defined along a continuum of times: x(t) Continuous-time system - Operates on and produces continuous-time signals. Discrete-time signal - Defined at discrete times: x[n] Discrete-time system - Operates on and produces discrete-time signals. x(t) y(t) H (s) D/A Digital filter .