1. Problem 1 [The Matrix]. Fix a positive integer N > 1 and consider the N × N matrix:

Φ = [bO b王 bN − 王] ,                                                        (1)

where the N ×1 column vectors bk , k = 0, . . . , N _1 are such that bk = [1   ej(2π/N )k      . . .    ej(2π/N )k(N - 1) ]T .

(a)  (1 point) Write down the matrix Φ for N = 4.  (Write all the 16 entries).

(b)  (1 point)  Find complex numbers x1 , . . . , xN  such that the entries of the matrix Φ (for arbitrary N)

satisfy the following property:

[Φ]m,e  = x Am, e = 1, . . . N.

Note:  Matrices that possess this property (that is, their rows form a geometric progression) are known as  Vandermonde matrices and have several nice properties.

(c)  (3 points)  Prove that ΦH Φ is a diagonal matrix. (Note: ΦH  denotes the conjugate transpose of the matrix Φ .  (Note: The conjugate transpose of a m × n complex-valued matrix A ∈ Cm ×n  is denoted by AH   ∈ Cm ×n  and is defined such that its entries  [AH ]k,e , k = 1, . . . , m , e = 1, . . . , n satisfy [AH ]k,e  = ╱ [A]e,k、* .  In particular, if A ∈ Rm ×n  (i.e.  it has only real entries), then AH  = AT , i.e.  the conjugate transpose is simply the transpose matrix.  Hint:  You might need to recall the geometric series formula.)

(d)  (1 point) What is the inner (dot) product〈bk , b公〉for k e ∈ {0, 1, . . . , N _ 1}.  What do you conclude about the vectors bO , b王 , . . . , bN − 王 ?

(Note: Recall here the inner product is defined in the conventional way of dot product of vectors, that is〈bk , b公〉= 1 [bk]n ([b公]n )* ).

(e)  (1 point)  Compute the inverse Φ - 1 of the matrix Φ . (Hint: From parts (c)-(e), what is ΦH Φ equal

to?)

(f)  (2 points)  Now, let s ∈ CN  be an arbitrary N dimensional complex vector and consider the system

of linear equations s = Φb. Use part (f) above, to solve for the unknown vector b.

(g)  (3 points)  Finally, let {s[n]}neZ  be a discrete-time periodic signal with period N .  Use part  (g)

above to prove that for any n ∈ Z, it holds

N - 1

s[n] =← αk ej(2T/N )kn (2)

k=0

with α0 , . . . , αN - 1  defined as

N - 1

αk  = ← s[n]e-j(2T/N )kn . (3)

n=0

2. Problem 2 [FIR]. Compute and plot the output {y[n]}n  of an FIR system with impulse response {h[n]}n  and input {x[n]}n  as shown below:

,2

『 『

『(『) 4

『 『

x[n] =『│『0(6)

『 『

『(『) 2

『 『

『

(0

, n = 0,

, n = 1,

, n = 2,

, n = 3,

, n = 4,

, otherwise

,『3

『

『

『(『) _1

『

h[n] = │0

『

『

『

『(0

, n = 0,

, n = 1,

, n = 2,

, n = 3,

, otherwise

(a)  (1 point) What is the support of the input signal? What is its length N?

(b)  (1 point) What is the support of the impulse response? What is the order M of the Filter?

(c)  (1 point) Is the filter causal? Why (not)?

(d)  (2 points) What is the length of the output signal {y[n]}n ?

(e)  (5 points)  Compute and plot the output {y[n]}n  of the FIR filter.

3. Problem 3 [Program it!]. (P.A.) Download the notebook “HW2 Convolution.ipynb” .  Answer all

the questions by filling in the missing commands. Please save your completed file as a pdf and return a hard copy. Also, upload your notebook at Canvas.

(a)  (10 points)

4. Problem 4 [Shhhh]. (P.A.) The goal of this exercise is to demonstrate the use of the running-average filter to denoise a signal.  Specifically, consider the following uncorrupted  finite-length discrete signal v[n]:

v[n] =

The signal {v[n]}n  is corrupted by additive random noise resulting in a new noisy signal s[n] as follows. For every 0 5 n 5 40, s[n] = v[n] + z[n] where z[n] is a random number (formally: a random variable). In particular, z[n] can take the values +1/2 or _1/2 with equal probability.  You can think of it this way.  At each time index n, nature tosses a (fair) coin.  If the outcome is head then s[n] = v[n] + . Otherwise, s[n] = v[n] _ .

This could model the noise of a measurement system.   Imagine a scenario where the original signal {v[n]}n  is unknown to us. Instead, we only have access to the noisy measurements {s[n]}n .

We will use a symmetric running-average system to reconstruct the original signal.

Write Python code as requested in each one of the following parts. Return a notebook with your code. Your submission should include code that is bug-free and should show the desired outputs  (such as requested plots). Use headlines to distinguish between different parts.

(a)  (1 point)  Use Python to make a stem plot of the signal v[n].

(b)  (1 point)  Use the function “numpy.random.rand” to generate a random signal {z[n]}n(4) as shown

below. 1

Make a stem plot of the vector z (eqv. of the noise signal z[n]) to make sure that it only takes values +1/2 and _1/2 as desired.  The output of “numpy.random.rand” is a (pseudo)-random number. Thus, every time you run your code, you get a different vector z and a different stem plot.

(c)  (1 point)  Use Python to compute and plot of the signal s[n] = v[n] + z[n], n ∈ Z.

(d)  (1 point)  Make a second plot that shows both {v[n]}n  and {s[n]}n .

(e)  (1 point)  Let {y[n]}n be the output of a 5-point symmetric running average filter with input-output

relation:

2

y[n] = z x[n _ k], n ∈ Z.

k=-2

Plot the output to the noisy input s[n] together with the clean signal v[n] to test whether the output of the filter is reasonably close to the original uncorrupted signal.

(f)  (1 point) What is the effect of the 5-point symmetric running average filter on the noise signal

{z[n]}?  Plot the output of the filter with {z[n]} as its input.  Below, give a short explanation of what you observe and why this is the case.

(g)  (1 point)  Try the above two parts for different odd values of the filter order, e.g. M = 3, 5, 7, ..., 11.

(For most efficient implementation, create a function that takes M and {x[n]}n as input and outputs {y[n]}n ). Write down your observations about the effects of changing filter sizes.

(h)  (2 points)  Calculate the frequency response of the (M = 5)-point symmetric filter on part (e) above.

(i)  (1 point)  Repeat part (h) above for an arbitrary odd integer M = 3, 5, 7, . . ..

(j)  (1 point) Write a Python function that takes as inputs an odd integer M  ≥ 3 and a frequency

value “ and returns the value of the frequency response of the corresponding M-point symmetric running-average filter at circular frequency “ .

(k)  (1 point)  Make plots of the frequency response of filters with M = 5, 9, 21, 33.  Comment here on

your observations. What changes on the frequency response as M increases and what does this say about the operation of the corresponding filter? What type of ideal filter is this an approximation to?

(l)  (1 point)  Let 厂1  denote the system operator of a 5-point symmetric running average filter.  Con- sider another filter with system operator 厂2  defined such that for any input {x[n]}n  it holds that 厂2 {x[n]} = x[n] _ 厂1 {x[n]}. Compute the frequency response of the new filter. What type of ideal filter is this an approximation to and why?

5. Problem 5 [Impulse].

One of the most basic discrete-time signals is the so-called unit impulse sequence, which is a discrete time function whose sample is equal to zero for all values of the time index n except n = 0, where it has unity value, that is,

,

n = 0,

n 0.

(a)  (1/2 point)  Draw a graphical representation of the signal 6[n].  The horizontal axis should indicate

the time-index value n = . . . , _2, _1, 0, 1, 2, . . . and the vertical axis the corresponding signal value. Also, plot the delayed signal 64 [n] = 6[n _ 4].

Unit impulse sequences are useful because any discrete signal can be written as a weighted lin- ear combination of shifted impulse sequences.  The time-shifting operation is used to shift the sequence 6[n] by a fixed integer value e ∈ Z to generate another sequence 6e [n] defined as follows:

6e [n] = 6[n _ e],    An ∈ Z.

The following three parts show the claim above. Let s[n] be an arbitrary discrete-time signal.

(b)  (1 point)  Prove that s[n]6[n _ e] = s[e]6[n _ e], for all integers n ∈ Z and e ∈ Z.

(c)  (1 point)  Argue that for all n ∈ Z:

s[n] =← s[n]6[n _ e].

eeZ

(d)  (1 point)  Combine Parts (b) and (c) to show that for all n ∈ Z:

s[n] =← s[e]6[n _ e].

eeZ

In words, s[n] is a weighted linear combination of shifted impulse sequences, where s[e]6[n _ e] is a unit impulse sequence of weight s[e] located at n = e.

Albeit simple, the representation in Part (d) is very important in SP as it allows us to determine the expression of the output signal of Linear Time Invariant (LTI) systems for an arbitrary input sequence, provided we know the expression for the output signal for a unit impulse sequence as the input. Let us show this!

Specifically, consider a discrete-time system and let {hk [n]}neZ  denote the response of the system to the shifted input impulse response 6[n _ k].  (Note here that {hk [n]}neZ  is not necessarily finite as in the special case of a finite impulse response system.)

(e)  (2 points)  Assume that the system is linear.  Use linearity and part (d) to show that the output

y[n] of the system relates to the input signal {s[n]}neZ  as follows:

y[n] =← s[k]hk [n],    An ∈ Z.

keZ

(f)  (2 points)  Further assume that the system is also time-invariant. Use this property and part (e) to

show that the output y[n] of the system relates to the input signal {s[n]}neZ  as follows:

y[n] =← s[k]h[n _ k],    An ∈ Z,

keZ

where {h[n]}neZ  is the impulse response of the system, i.e.  the response to the impulse response 6[n].