Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science

Download as pdf or txt
Download as pdf or txt
You are on page 1of 12

1

MASSACHUSETTS INSTITUTE OF TECHNOLOGY


Department of Electrical Engineering and Computer Science
6.341 Discrete-Time Signal Processing
Fall 2005
MIDTERM EXAM
Tuesday, November 8, 2005
SOLUTIONS
Disclaimer: These are not meant to be full solutions, but rather an indication of how to
approach each problem.
Problem Grade Points Grader
1 /15
2 (a) /12
2 (b) /6
2 (c) /12
3 (a) /10
3 (b) /10
4 /15
5 (a) /10
5 (b) /10
Total /100
_ _
_ _
2
Problem 1 (15%)
A stable system with system function H(z) has the pole-zero diagram shown in Figure 1-1.
It can be represented as the cascade of a stable minimum-phase system H
min
(z) and a stable
all-pass system H
ap
(z).
Re(z)
Im(z)
1
2
3 4
Figure 1-1: Pole-zero diagram for H(z).
Determine a choice for H
min
(z) and H
ap
(z) (up to a scale factor) and draw their corresponding
pole-zero plots. Indicate whether your decomposition is unique up to a scale factor.
We nd a minimum-phase system H
min
(z) that has the same frequency response magnitude as
H(z) up to a scale factor. Poles and zeros that were outside the unit circle are moved to their
conjugate reciprocal locations (3 to
1
4
, to 0).
3
, 4 to
1
(1
1
z
1
)
4
H
min
(z) = K
1
(1
1
z
1
)(1
1
z
1
)
2 3
There is no need to include an explicit z term to account for the zero at the origin.
We now include all-pass terms in H
ap
(z) to move poles and zeros back to their original locations
1
z 3
in H (z). The term
13z
1
moves the pole at
1
back to 3, the term z
1
moves the zero from 0
3
to , and so on:
H
ap
(z) = z
1
z
1
3 z
1

1
4
1 3z
1
1
1
z
1
4
The decomposition is unique up to a scale factor. We cannot include additional all-pass terms
in H
ap
(z), since it is not possible for H
min
(z) to cancel the resulting poles and zeros outside
the unit circle.
3 Name:
Re(z)
Im(z)
1
2
1
3
1
4
Figure 1-2: Pole-zero diagram for H
min
(z).
Re(z)
Im(z)
1
3
1
4
3 4
zero at
Figure 1-3: Pole-zero diagram for H
ap
(z).
_ _
4
Problem 2 (30%)
x
c
(t) x
L
[n]
C/D
x[n]
2
y
H(e
j
)
y
M
[n [n]
2
y
c
(t) ]
D/C
T T
Figure 2-1:
For parts (a) and (b) only, X
c
(j) = 0 for || > 2 10
3
and H(e
j
) is as shown in Figure
2-2 (and of course periodically repeats).
j
) H(e
A


4 4
Figure 2-2:
(12%) (a) Determine the most general condition on T, if any, so that the overall continuous-time
system from x
c
(t) to y
c
(t) is LTI.
We can simplify Figure 2-1 by replacing the expander, H(e
j
) and compressor with a
single DT LTI system. The impulse response of the equivalent DT LTI system is h[2n],
where h[n] is the inverse DTFT of H(e
j
). We saw this result in Problem Set 6 where
we derived it by polyphase decomposition and subsequent simplication. The frequency
response of the equivalent DT LTI system is
1
2
H(e
j

2
j(
) +
1
H(e
2

2
)
).
Alternatively, we can reach the same conclusion by relating Y
M
(e
j
) to X
L
(e
j
):
1
j(

2
)
)X
L
(e
j2(

2
)
)
j2 j
) =
j
Y
M
(e H(e )X
L
(e ) + H(e
2 2
2
Both X
L
() terms reduce to X
L
(e
j
), the latter because of 2 periodicity, leaving behind
the same equivalent frequency response.
The overall CT system will be LTI if there is no aliasing at the C/D converter, or if the
DT lter rejects any frequency content contaminated by aliasing. Since the equivalent DT
frequency response is 0 for

< || , the copy of X
c
(j) centred at = 0 can extend
2
3
to = 2

= without passing any aliased components. Applying the = T
2 2
mapping:

max
=
max
T = (2 10
3
)T <
3
2
and so we require that T <
3
10
3
.
4
5 Name:
(6%) (b) Sketch and clearly label the overall equivalent continuous-time frequency response H
e
(j)
that results when the condition determined in (a) holds.
H (j)


2T


2T
A/2
eff
(12%) (c) For this part only assume that X
c
(j) in Figure 2-1 is bandlimited to avoid aliasing,
i.e. X
c
(j) = 0 for ||

. For a general sampling period T , we would like to choose
T
the system H (e
j
) in Figure 2-1 so that the overall continuous-time system from x
c
(t) to
y
c
(t) is LTI for any input x
c
(t) bandlimited as above.
Determine the most general conditions on H (e
j
), if any, so that the overall CT system
is LTI. Assuming that these conditions hold, also specify in terms of H(e
j
) the overall
equivalent continuous-time frequency response H
e
(j).
The simplication in part (a) yields an equivalent DT LTI system between the C/D and
D/C converters. Thus the overall system will be LTI if x
c
(t) is appropriately bandlimited
to avoid aliasing, as assumed in this part. There are no conditions on H(e
j
).
6
Problem 3 (20%)
For this problem you may nd the information on page 12 useful.
Consider the LTI system represented by the FIR lattice structure in Figure 3-1.
x[n] y[n]
v[n]
1
2
1
2
3
3
2
2
1 1 1
z z z
Figure 3-1:
(10%) (a) Determine the system function from the input x[n] to the output v[n] (NOT y[n]).
The output v[n] is taken after two stages, so we perform the lattice recursion up to order
p = 2.
1
k
1
=
2
, k
2
= 3, k
3
= 2
a
(1)
1
= k
1
=
1
2
_ _ _ _ _ _
a
(2)
1
a
(2)
=
a
(1)
1
0
k
2
a
(1)
1
1
=
_
1
3
_
2
V (z)
2
= 1 z
1
3z
X(z)
Note the change of signs in going from a
(2)
to the system function.
k
7 Name:
(10%) (b) Let H(z) be the system function from the input x[n] to the output y[n], and let g[n] be
the result of expanding the associated impulse response h[n] by 2:
h[n] g[n] 2
The impulse response g[n] denes a new system with system function G(z).
We would like to implement G(z) using an FIR lattice structure as dened by the gure
on page 12. Determine the k-parameters necessary for an FIR lattice implementation of
G(z).
Note: You should think carefully before diving into a long calculation.
Since g[n] is h[n] expanded by 2, G(z) = H(z
2
). We replace z by z
2
in Figure 3-1. We
then expand each of the three sections as shown below:
k
p
k
p
k
p
k
p
0
0
2 1 1
z z z
The resulting owgraph for G(z) is in the form of a 6th-order FIR lattice. We read o
the six k-parameters as:
1
k
2
=
2
k
4
= 3
k
6
= 2
k
p
= 0, p = 1, 3, 5
8
Problem 4 (15%)
F
i
l
t
e
r

r
e
s
p
o
n
s
e

We nd in a treasure chest an even-symmetric FIR lter h[n] of length 2L + 1, i.e.
h[n] = 0 for |n| > L,
h[n] = h[n].
H(e
j
), the DTFT of h[n], is plotted over in Figure 4-1.
1.2
1
0.8
0.6
0.4
0.2
0
0.2
1 0.8 0.6 0.4 0.2 0 0.2 0.4 0.6 0.8 1
Normalized frequency ( radians/sample)
Figure 4-1: Plot of H(e
j
) over .
9 Name:
What can be inferred from Figure 4-1 about the possible range of values of L? Clearly explain
the reason(s) for your answer. Do not make any assumptions about the design procedure that
might have been used to obtain h[n].
As discussed in Section 7.4 of OSB, H(e
j
) can be represented as an Lth order polynomial
in cos since h[n] is even-symmetric and nite-length. An Lth order polynomial in cos can
have no more than L + 1 extrema on [0, ]. (An Lth order polynomial in x can have no more
than L 1 extrema in an open interval, but an Lth order polynomial in cos will always have
additional extrema at = 0 and = for a total of L + 1 extrema.)
H(e
j
) has 6 extrema on [0, ], so 6 L + 1 or L 5.
10
Problem 5 (20%)
In Figure 5-1, x[n] is a nite sequence of length 1024. The sequence R[k] is obtained by taking
the 1024-point DFT of x[n] and compressing the result by 2.
DFT
1024-point
X[k]
2
R[k]
2
Y [k] x[n]
IDFT
1024-point
y[n]
IDFT
512-point
r[n]
Figure 5-1:
(10%) (a) Choose the most accurate statement for r[n], the 512-point inverse DFT of R[k]. Justify
your choice in a few concise sentences.
A. r[n] = x[n], 0 n 511
B. r[n] = x[2n], 0 n 511
C. r[n] = x[n] + x[n + 512], 0 n 511
D. r[n] = x[n] + x[n + 512], 0 n 511
E. r[n] = x[n] + x[1023 n], 0 n 511
In all cases r[n] = 0 outside 0 n 511.
Answer: C
Compressing the 1024-point DFT X [k] by 2 undersamples the DTFT X(e
j
). Undersam-
pling in the frequency domain corresponds to aliasing in the time domain. In this specic
case, the second half of x[n] is folded onto the rst half, as described by statement C.
_
_
_
_
_ _
Name: 11
(10%) (b) The sequence Y [k] is obtained by expanding R[k] by 2. Choose the most accurate state-
ment for y[n], the 1024-point inverse DFT of Y [k]. Justify your choice in a few concise
sentences.
A. y[n] =
1
2
1
2
(x[n] + x[n + 512]) , 0 n 511
(x[n] + x[n 512]) , 512 n 1023
x[n], 0 n 511
B. y[n] =
x[n 512], 512 n 1023
x[n], n even
C. y[n] =
0, n odd
x[2n], 0 n 511
D. y[n] =
x[2(n 512)], 512 n 1023
E. y[n] =
1
2
(x[n] + x[1023 n]) , 0 n 1023
In all cases y[n] = 0 outside 0 n 1023.
Answer: A
We can rst think about how expanding by 2 in the time domain aects the DFT. Ex-
panding a time sequence x[n] by 2 compresses the DTFT X(e
j
) by 2 in frequency. As a
result, the 2N -point DFT of the expanded sequence samples two periods of X(e
j
) and
equals two copies of the N -point DFT X[k].
By duality, expanding the DFT R[k] by 2 corresponds to repeating r[n] back-to-back,
with an additional scaling by
1
2
. Thus statement A is correct.
Alternatively, Y [k] =
1
2
1 + (1)
k
X[k]. Modulating the DFT by (1)
k
corresponds to
a circular time shift of N/2 = 512.
END OF EXAM
_ _
12
YOU CAN USE THE BLANK PART OF THIS PAGE AS SCRATCH PAPER BUT
NOTHING ON THIS PAGE WILL BE CONSIDERED DURING GRADING
A
p+1
(z) = A
p
(z) k
p+1
B
p
(z) (1a)
(p+1)
A
p
(1/z) B
p
(z) = z (3a)
A
0
(z) = 1 and B
0
(z) = z
1
(2)
(p+1) (p)
a
k
= a
k
k
p+1
a
p
(p

)
k+1
, k = 1, . . . , p (8a)
(p+1)
(8b) a
p+1
= k
p+1
Dene:
_ _
T

p
= a
(
1
p) (p)
(p)
a
2
a
p
_ _
T
(p)
= a
(p)
a
p1
a
p p
(p)
1
Then equations (8) become:


p p

p+1
=



k
p+1



(9)
0 1
Reverse recursion:
(M ) (M )
a
(M 1)
=
a
k
+ k
M
a
M k
, k = 1, . . . , M 1 (11)
k
1 k
2
M
(M ) (M 1)
with k
M
= a
M
, k
M 1
= a
M 1
.

You might also like