[SOLVED] Ece113, digital signal processing midterm exam

1. (10 points) Quick Review
Carefully read each statement below and identify it as True or False, and briefly explain
your reason in one or two sentences.
1. Discrete-time sinusoids are always periodic in time.
True or False? Why?
2. Discrete-time Fourier Transforms are always periodic in frequency.
True or False? Why?
3. A finite-precision Direct Form I realization of a digital filter will have a higher
chance for internal overflow compared to Direct Form II.
True or False? Why?
4. Regardless of the window function used, zero-padding a discrete-time sequence will
always lead to smaller spectral leakage.
True or False? Why?
5. The phase of the DTFT of an even-symmetric real-valued signal will always be 0
or 180◦
.
True or False? Why?
6. Downsampling a lowpass sequence by a factor D will never lead to aliasing as long
as the discrete-time sequence does not have any energy within the the frequency
range of [ π
D
, π] rad/sample.
True or False? Why?
7. Upsampling by a factor I may lead to aliasing if the discrete-time sequence has any
energy within the frequency range of [ π
I
, π] rad/sample.
True or False? Why?
8. Any discrete-time sequence of length N or less can always be represented by its
N-point DFT.
True or False? Why?
9. The minimum sampling rate to avoid aliasing for a real-valued bandpass signal with
its single-side band (i.e., over positive frequencies) limited to B (i.e., FH −FL = B)
Hz would always be 2B.
True or False? Why?
10. An N-point circular convolution of a sequence with length N1 with another sequence
of length N2 will always be equal to the linear convolution of the two sequences
within the range [0, N − 1] as long as N ≥ max(N1, N2).
True or False? Why?

2. (18 points) LCCDE, Direct Form Structures:
A second-order LTI system is described by the following Linear Constant Coefficient
Difference Equation:
y(n) − 0.1y(n − 1) − 0.72y(n − 2) = 5x(n − 1) (1)
Assume the following initial conditions for the system:
y(−2) = 1.25, y(−1) = −1
(a) (3 points) Write the characteristic equation of the system, find the natural frequencies (modes), and write the form of the homogeneous response of the system.
(b) (1 point) Is this system BIBO stable? Why or why not?
(c) (6 points) Find the complete system response, y(n), n ≥ 0, to the input sequence
x(n) = ( 1
5
)
nu(n), where u(n) is the unit step sequence.
(d) (1 point) How would the form of the response change if the input was x(n) =
0.9
nu(n) instead? You don’t need to find the values of the constants again. Just
indicate if you think the form of the response would change and if so, how?
(e) (4 points) Given the same initial conditions and the same input as in Part (c),
determine the zero-input and the zero-state responses of this system.
(f) (3 points) Draw the signal flow graph for the Transposed Direct Form II realization
of this system.
3. (15 points) LTI Systems, DTFT, Frequency Response:
The impulse response of an LTI system, h(n), is shown below (h(n) = 0 for all other
time indices not shown on the plot):

(a) (1 point) Is this system causal? Why or why not?
(b) (1 point) Is this system BIBO stable? Why or why not?
(c) (6 points) Obtain the system frequency response H(ω) in closed form (i.e., no Σ0
s).
(Hint: Try to represent h(n) in terms of some known signals for which you may
already know the DTFT, and take advantage of the DTFT properties.)
(d) (3 points) Using MATLAB, plot the magnitude and phase responses for this system
over the frequency range −π ≤ ω ≤ π (rad/sample).
(e) (4 points) Determine the steady-state response of this system to the following input
signal:
x(n) = 1 + 5(−1)n + sin(π
2
n) (2)
4. (12 points) Autocorrelation, DTFT:
For this problem, you need to think about the properties of autocorrelation sequences,
including the correlation property of DTFT.
(a) (2 points) Can the discrete pulse sequence below be a valid autocorrelation sequence? Why or why not? Please explain.
rxx(n) = u(n) − u(n − N) = Π(n −
N−1
2
N
) (3)
u(n) is the unit step sequence, and Π denotes a pulse. Assume N odd.
(b) (2 points) How about the following pulse sequence centered around n = 0? Can it
be a valid autocorrelation sequence? Why or why not? Please explain.
rxx(n) = u(n + N) − u(n − N − 1) = Π( n
2N + 1
) (4)
(c) (2 points) How about the following triangle sequence? Can it be a be valid autocorrelation sequence? Why or why not? Please explain.
rxx(n) = Λ( n
2N + 1
) = (
(1 −
|n|
N
) |n| ≤ N
0 otherwise
(5)
(d) (3 points) Consider a discrete-time sequence x(n), and assume y(n) to be its delayed version, i.e., y(n) = x(n − n0). Write the autocorrelation sequence for y(n) in
terms of the autocorrelation for x(n), i.e., write ryy(n) in terms of rxx(n).
(e) (3 points) Given a discrete-time sequence x(n), let y(n) = e
jω0nx(n). Again, write
ryy(n) in terms of rxx(n).

5. (10 points) DFT Spectral Analysis:
A system for discrete-time spectral analysis of a continuous-time signal is shown below:
where w(n) is the window function. We have implemented this system in the MATLAB
code snippet shown below:
As shown in the code, we have obtained the 64-point FFT of a two-tone signal corrupted
with Additive White Gaussian Noise (AWGN). One run of this code has produced the
following power spectrum plot:

Clearly the above spectral representation leaves much to be desired and one would have
a hard time identifying the two tones in the signal.
Suppose you cannot change anything with the signal itself. That is, you have the given
two-tone signal, sampled at the rate of Fs = 8.5 KHz, and with 10dB Signal-to-Noise
Ratio (SNR).
(a) (4 points) Describe ALL the different techniques you can use to improve the spectral representation of this signal, and explain how each technique can help.
(b) (6 points) Use the given code as your starting point (you can download it from
CCLE if you don’t want to type again!), and modify it by implementing the different techniques you proposed in Part (a), and show how you have improved the
spectral representation of the given signal. Please include a printout of your modified MATLAB code along with the improved spectral plot and discuss.
6. (14 points) DTFT, Sample Rate Conversion:
Consider the system below where two continuous-time signals xa(t) and ya(t), with
the given spectrum (CTFT) are first sampled at different rates, then downsampled and
upsampled respectively in order to have the same sampling rate, also multiplied by tones,
and eventually passed through an ideal highpass and an ideal lowpass filter respectively,
and finally added up, forming a composite signal z(n).

(a) (8 points) Plot the magnitude DTFT of x1(n), x2(n), x3(n), y1(n), y2(n), and y3(n)
over −2π < ω < 2π, showing as much detail as possible, including all important
corner and/or center frequencies as well as the magnitudes. Show the important
points on the frequency axis both in terms of rad/sample as well as Hertz.
(b) (2 points) Plot the magnitude DTFT of the composite signal z(n) over −2π < ω <
2π, showing as much detail as possible.
(c) (4 points) Can you draw a block diagram of a similar system (i.e., using ideal
filters, downsampling/upsampling, and modulation) that can be used to recover
the individual signals x1(n) and y1(n) from the composite signal z(n)?
7. (8 points) DFT/IDFT, Linear vs. Circular Convolution:
Orthogonal Frequency Division Multiplexing (OFDM) is a digital transmission scheme
used in many modern communication systems, including WLAN and LTE/5G cellular
systems. It is a scheme where the high-rate data is partitioned and transmitted over
multiple orthogonal narrowband (lower-rate) subcarriers. Its main benefit is to cope
with severe multipath fading channels without requiring complex channel equalization
filters. The diagram below shows the high-level architecture for a typical WLAN OFDM
transmitter and receiver.
For this problem, we are only focusing on the colored blocks, i.e., FFT/IFFT and Cyclic
Prefix insertion/removal. As shown, on the transmitter side, an Inverse-FFT (IFFT)
block is used to generate the OFDM symbols. In doing so, the samples to be transmitted
are treated as the frequency-domain scaling on the different subcarriers, and the IFFT
block then generates the corresponding OFDM symbols in the time domain. As shown,
the opposite occurs on the receiver side, where an FFT engine translates the timedomain received samples into the frequency domain whereby the scalings on the different

subcarriers (based on the received OFDM symbol) will then be processed through the
receiver chain and the received bits will ultimately be decoded and passed onto the
higher layers.
(a) (5 points) For Time Division Duplexing (TDD) systems such as WLAN, which can
only transmit or receive at any given instant, i.e., no simultaneous transmit/receive,
an efficient hardware implementation would be to re-use the same FFT engine for
both Inverse-FFT processing in the transmitter and the FFT processing in the
receiver. Using the DFT definition, show why/how the following implementation
would actually work. x(n)’s are the time-domain samples and X(k)’s are the corresponding DFT samples.
(b) (3 points) Also shown in the WLAN transceiver architecture are the Cyclic Prefix
insertion (on Tx side) and removal (on Rx side). The Cyclic Prefix appends a
portion at the end of the OFDM symbol to its beginning. This is shown in the
figure below (copied from dspillustrations.com).
One purpose for this is just to add Guard Interval between consecutive OFDM
symbols in order to avoid inter-symbol interference. But the guard interval did not
have to be in the particular format of a Cyclic Prefix. So another key purpose
for Cyclic Prefix insertion has to do with linear versus circular convolution. Note
that we may model our wireless channel as an LTI system with frequency response
samples (i.e., DFT) of H(k). So from what you know about linear versus circular
convolution, can you explain the second benefit of inserting the Cyclic Prefix in the
OFDM symbol?

8. (13 points) Sampling, DFT, FFT:
Sampling a continuous-time baseband (lowpass) signal, xa(t), over a duration of 1 second,
has generated 4096 samples.
(a) (2 points) Assuming there was no aliasing, what would be the highest frequency in
the spectrum of xa(t)?
(b) (2 points) If we obtain the 4096-point FFT of the available samples, what would
be the frequency spacing in Hertz between each two adjacent frequency bins?
(c) (2 points) Suppose we are only interested in the frequency bins within the range
100 ≤ F ≤ 500 Hz. How many complex multiplications would be needed to calculate these frequency bins using the direct 4096-point DFT computation?
(d) (2 points) How many complex multiplications would be needed to obtain all 4096
bins if we use Decimation-in-Time Radix-2 4096-point FFT algorithm instead?
Compare with the number you found in Part (c) for only a subset of frequency
bins.
(e) (2 points) How many complex multiplications would be needed to obtain all 4096
bins if we use Decimation-in-Frequency Radix-2 4096-point FFT algorithm instead?
Compare with your numbers in Part (c) and (d).
(f) (3 points) Suppose we only need m bins from an N-point FFT. What would be
the largest m (expressed in terms of N) before the Decimation-in-Time Radix2 N-point FFT becomes more computationally efficient than the direct N-point
DFT calculation? What would be the actual value for the 4096-point DFT (i.e.,
N = 4096) in this problem?