Chapter 5

Discrete Time Signal Analysis

5.1 Discrete Time Signals and Fourier Transform

Consider a discrete time sequence

x_{k} k = 0, ±1, …

Suppose Σ|x_{k}| < ∞. (By Wierstrass’s test, we have uniform convergence.)

Define the Fourier transform of x_{k} by

X(e^{iω}) = ∑_{k=−∞}^{∞} x_{k}e^{−iωk}

Now

X(e^{iω}) is automatically periodic in ω ∈ [−π, π]

Thus there is no need to consider frequencies extending beyond [−π, π]. This is the phenomenon of aliasing with higher frequencies aliased to that of a lower frequency (e^{i \frac{7π}{2} k} = e^{i \frac{π}{2} k}). We can think of the sequence x_{k} having a sampling period T = 1. In general, for a sampling period T, the Fourier transform is periodic over [−\frac{π}{T} , \frac{π}{T}]. More about sampling later.

Can think of x_{k} as the Fourier series representation of X(e^{iω}). Thus can determine x_{k} by F.S. expansion of X(e^{iω}) i.e.

x_{k} = \frac{1}{2π} ∫_{−π}^{π} X(e^{iω})e^{iωk}dω

Virtually all the results on Fourier series discussed in ECE355F apply in this setting, with the only main difference being that the periodic function X(e^{iω}) is generally complex.

There are, however, 2 results not discussed in the context of Fourier series, which we would like to describe. Product of 2 sequences

Let

m_{k} = x_{k}y_{k}

The Fourier transform of m_{k} can be determined as follows.

M(e^{iω}) = ∑_{k=−∞}^{∞} m_{k}e^{−iωk}

= ∑_{k=−∞}^{∞} x_{k} \frac{1}{2π} ∫_{−π}^{π} Y (e^{iγ})e^{iγk}dγe^{−iωk}

= \frac{1}{2π} ∫_{−π}^{π} ∑_{k=−∞}^{∞} x_{k}e^{−i(ω−γ)k}Y (e^{iγ})dγ

= \frac{1}{2π} ∫_{−π}^{π} X(e^{i(ω−γ)})Y (e^{iγ})dγ
= \frac{1}{2π} ∫_{−π}^{π} X(e^{iγ})Y (e^{i(ω−γ)})dγ

Convolution of sequences

z_{k} = ∑_{l=−∞}^{∞} x_{l}y_{k−l}

Z(e^{iω}) = ∑_{k} z_{k}e^{−iωk} = ∑_{k=−∞}^{∞} ∑_{l=−∞}^{∞} x_{l}y_{k−l}e^{−iω(k−l)}e^{−iωl}
= ∑_{l} ∑_{k} x_{l}y_{k−l}e^{−iω(k−l)}e^{−iωl}
= Y (e^{iω})X(e^{iω})

Now if x_{k} = 1, k ≥ 0 and x_{k} = 0, k < 0 (unit step), X(e^{iω}) does not exist, just as the Laplace transform of x(t) = 1 does not exist. We therefore introduce the analogue of the Laplace transform for discrete time signals, the z-transform.

5.2 Z-Transforms

Assume

|x_{k}| ≤ cr_{o}^{k}

i.e. x_{k} is exponentially (geometrically) bounded. Then for all r > r_{0}

Σ|x_{k}|r^{−k}

≤ cΣ (\frac{r_{0}}{r} )^{k} < ∞

Define z-transform of x_{k} as

X(z) = ∑_{k=0}^{∞} x_{k}z^{−k}

converges in |z| > r_{0}

r_{0}

X(z) is then an analytic function in the region of convergence. Example:

x_{k} = a^{k} k ≥ 0

X(z) = ∑_{k=0}^{∞}(az^{−1})^{k} = \frac{1}{1 − az^{−1}} |z| > |a|

Inversion integral:

x_{k} = \frac{1}{2πi} ∮ X(z)z^{k−1}dz

path inside region of convergence (from Laurent series expansion). Since

\frac{1}{2πi} ∮ Σx_{n}z^{−n}z^{k−1}dz

= \frac{1}{2πi}Σ ∮ x_{n}z^{−(n−k)} \frac{dz}{z}

(convergence uniform to permit integration term by term) = x_{k}

= Σ residues of X(z)z^{k−1} inside C

Example:

X(z) = \frac{1}{1 − az^{−1}}

x_{k} = \frac{1}{2πi} ∮ \frac{z^{k−1}}{1 − az^{−1}} dz
= \frac{1}{2πi} ∮ \frac{z^{k}}{z − a}dz = a^{k} k ≥ 0

Can also do infinite series expansion to get

\frac{1}{1 − az^{−1}} = Σa^{k}z^{−k}

. Multiplication of time sequences:

w_{k} = x_{k}y_{k}

where X(z) has region of convergence |z| > R_{0} and Y (z) has region of convergence |z| > R_{1}.

W (z) = ∑_{k} x_{k}y_{k}z^{−k} = ∑ x_{k}z^{−k} \frac{1}{2πi} ∮ Y (z)ζ^{k−1}dζ
= \frac{1}{2πi} ∮ ∑ x_{k} (\frac{z}{ζ} )^{k} Y (ζ)\frac{dζ}{ζ} = \frac{1}{2πi} ∮ X (\frac{z}{ζ} ) Y (ζ)\frac{dζ}{ζ}

where the contour integral is over a circle |z| > R_{1}. It can also be expressed as

W (z) = \frac{1}{2πi} ∮ X(ζ)Y (\frac{z}{ζ} ) \frac{dζ}{ζ}

where the contour integral is over a circle |z| > R_{0}. Since we require

|\frac{z}{ζ} | > R_{0} |ζ| > R_{1} ⇒ |z| > R_{0}R_{1}

4 CHAPTER 5. DISCRETE TIME SIGNAL ANALYSIS Convolution of (causal) time sequences:

w_{k} = ∑_{l=0}^{k} x_{l}y_{k−l}

W (z) = ∑_{k=0}^{∞} ∑_{l=0}^{k} x_{l}y_{k−l}z^{−k}
= ∑_{l=0}^{∞} ∑_{k=l}^{∞} x_{l}y_{k−l}z^{−(k−l)}z^{−l}
= ∑_{l=0}^{∞} ∑_{j=0}^{∞} x_{l}y_{j}z^{−j}z^{−l} = X(z)Y (z)

Multiplication by a^{k}:

Z\{a^{k}x_{k}\} = X (\frac{z}{a})

since

∑ a^{k}x_{k}z^{−k} = ∑ x_{k} (\frac{z}{a})^{−k}

If

|x_{k}| ≤ cr^{k}
⇒ |a^{k}x_{k}| ≤ c[|a|r]^{k}
⇒ |z| > |a|r is region of convergence

Translation:

∑_{k=0}^{∞} x_{k−m}z^{−k} = ∑_{k=0}^{m−1} x_{k−m}z^{−k} + z^{−m}X(z)
= x_{−m} + z^{−1}x_{−m+1} + … + x_{−1}z^{−m+1} + z^{−m}X(z)
∑_{k=0}^{∞} x_{k+m}z^{−k} = ∑_{k=0}^{∞} x_{k+m}z^{−(k+m)}z^{m}
= ∑_{l=+m}^{∞} x_{l}z^{−l}z^{+m} = z^{m}X(z) − ∑_{l=0}^{m−1} x_{l}z^{−l}z^{+m}
= z^{m}X(z) − {z^{m}x_{0} + z^{m−1}x_{1} + … + zx_{m−1}}

Initial value:

f(z) = ∑_{k=0}^{∞} f_{k}z^{−k} = f_{0} + ∑_{1}^{∞} f_{k}z^{−k}
⇒ f_{0} = lim_{z→∞} f(z)

Final value: Assume f_{k} ⟶_{z→∞}A < ∞. Then

lim ; \begin{matrix}z → 1 \\ z > 1 real \end{matrix} (z − 1)F (z) = A

5.2. Z-TRANSFORMS 5 Proof: Put f_{k} = A + b_{k} b_{k} → 0. Then

F (z) = \frac{Az}{z − 1} + ∑_{0}^{∞} b_{k}z^{−k}

Second converges since b_{k} → 0, |b_{k}| < B. Hence F (z) analytic for |z| > 1.

To show lim_{z→1^{+}}(z − 1) ∑ \frac{b_{k}}{z^{k}} = 0. Given ϵ > 0, choose N so large that |b_{n}| < \frac{1}{2}ϵ, n ≥ N. Then

|(z − 1) ∑_{N}^{∞} \frac{b_{n}}{z^{n}} | ≤ (z − 1)\frac{ϵ}{2} ∑_{N}^{∞} \frac{1}{z^{n}}
= \frac{ϵ}{2}(z − 1)\frac{1}{z^{N}} \frac{z}{z − 1} = \frac{ϵ}{2z^{N−1}} < \frac{ϵ}{2}

On the other hand |(z − 1) ∑_{0}^{N−1} \frac{b_{n}}{z^{n}} | < \frac{ϵ}{2} for |z − 1| < δ with δ sufficiently small ⇒ result. Solving difference equations:

y_{k} + a_{1}y_{k−1} + … + a_{n}y_{k−n}
= b_{0}u_{k} + … + b_{m}u_{k−m} with u_{k} = 0, k < 0.

Putting a_{0} = 1, we can write the above equation as

∑_{j=0}^{n} a_{j}y_{k−j} = ∑_{j=0}^{m} b_{j}u_{k−j}

Taking z-transform of the left hand side gives

∑_{0}^{∞} y_{k}z^{−k} + … = Y (z) + a_{1}z^{−1}Y (z) + …
= A(z)Y (z) + ∑_{j=0}^{n} ∑_{k=0}^{j−1} a_{j}y_{k−j}z^{−k}

∴ Y (z) = \frac{ic(z)}{A(z)} + \frac{B(z)}{A(z)}U(z)

where ic(z) is a polynomial depending on the initial condition. Example:

y(k + 2) + y(k + 1) = u(k + 1) − u(k)

or

y(k) + y(k − 1) = u(k − 1) − u(k − 2)

u(−2) = u(−1) = 0 u(k) = (\frac{1}{2})^{k} k ≥ 0

y(−1) = 2

Taking transforms

Y (z) + z^{−1}Y (z) + y(−1) = z^{−1}U(z) − z^{−2}U(z)

(1 + z^{−1})Y (z) = −2 + z^{−1} − z^{−2}U(z)

Y (z) = −\frac{2}{1 + z^{−1}} + \frac{z^{−1} − z^{−2}}{1 + z^{−1}} U(z)

6 CHAPTER 5. DISCRETE TIME SIGNAL ANALYSIS Since

U(z) = \frac{1}{1 − \frac{1}{2}z^{−1}}

Y (z) = −\frac{2z}{z + 1} + \frac{z − 1}{(z + 1)(z − \frac{1}{2})}

Partial fraction expansion gives

Y (z) = \frac{−2z}{z + 1} + \frac{4/3}{z + 1} − \frac{1/3}{z − 1/2}

Noting that the z-transform of a^{n} is \frac{z}{z−a} and that \frac{a}{z+a} = 1 − \frac{z}{z+a}, we get

y(k) = −2(−1)^{k} + \frac{4}{3}(δ(k) − (−1)^{k}) + 2 (\frac{1}{3}) [δ(k) − (\frac{1}{2})^{k}]