Description
Problem 1. (15 points) Consider the following periodic signals x[n] and z[n], with period 3 each.
Can you relate the DTFS coefficients of x[n] with the DTFS coefficients of z[n]?
0
𝑥[𝑛] 1 1
0
𝑧[𝑛]
2
1 1
(Hint: Try to find a signal y[n] of period 3 such that z[n] = x[n] ~ y[n].)
Problem 2. (20 points) Determine the DTFTs of the following sequences:
(a). (10 points) x[n] =
1
2
n−3
u[n] +
1
3
n
u[n − 1].
(b). (10 points) x[n] =
1
4
n−1
u[n] + cos
π
3
n
.
Problem 3. (a). (10 points) Determine the IDTFT of the following:
X(Ω) = π
2
· rect
Ω
π
6
· e
−j2Ω
where we define the rectangular function rect(·) as
rect
Ω
Ωc
,
1, |Ω| < Ωc
0, Ωc ≤ |Ω| ≤ π
(b). (5 points) Determine the following quantity for the same signal x[n] in (a):
X∞
n=−∞
|x[n]|
Problem 4. (25 points) Consider the DTFT X(Ω) of a particular discrete-time signal x[n].
X(Ω) = (
1, if |Ω| < ωc
0, else.
For this problem, we let ωc = π/2 and the DTFT is plotted in the figure below.
−3 −2 −1 0 1 2 3
−0.5
0
0.5
1
1.5
Ω
X(
Ω)
(a). (5 points) Use the inverse DTFT equation (or synthesis equation) and show that
x[n] = (ωc
π
, if n = 0
sin(ωcn)
πn
, else.
(b). (5 points) Now, given the above x[n], use the DTFT equation (or analysis equation) to get
the DTFT of x[n] as
X˜(Ω) = ωc
π
+
X∞
n=−∞
n6=0
sin(ωcn)
πn
e
−jΩn
.
At first sight, it it is not clear if the expression for X˜(Ω) is equal to that of X(Ω), but we will
see that this is indeed the case using MATLAB.
(c). (10 points) Consider X˜(Ω) = ωc
π +
P∞
n=−∞
n6=0
sin(ωcn)
πn
e
−jΩn. We are unable to see what X˜(Ω) is
because of the infinite number of terms in the summation. One way to get around this problem
is by truncating the summation to a finite number of terms, i.e.:
X˜(Ω) ≈
ωc
π
+
X
N
n=−N
n6=0
sin(ωcn)
πn
e
−jΩn
,
where N is an integer of our choice. On MATLAB, plot X˜(Ω) using the above approximation
for N = 1, 3, 5, 10, 20, 50. Also plot X(Ω) in each of these plots for comparison. An example
plot for N = 7 is shown in the figure below. You can use subplot() in MATLAB to plot
these.
(d). (5 points) As we increase N, what do you observe about X˜(Ω)?
2
−3 −2 −1 0 1 2 3
−0.5
0
0.5
1
1.5
N = 7
Ω
X(
Ω)
Figure 1: Plot of X˜(Ω) for N = 7 in red. X(Ω) is also plotted for comparison.
Problem 5. (25 points) In this problem, we will see how a change of basis helps in image compression. From CCLE, download the bitmap image ‘Lena.bmp’. On MATLAB, use the command
>>A = double(’Lena.bmp’);
This reads the bitmap image and stores the color scale of each pixel in a matrix. Notice that the
variable A is now a 512 × 512 matrix. Each value of the matrix corresponds to the colorscale of the
pixel in the image. To recover the image from the matrix, use the command
>>imshow(uint8(A));
This should output the following image: So now, we can forget about the image and work with
the matrix. Note that we need 512 × 512 = 262144 real values to represent this image. We will now
try to reduce the number of real values needed to represent this image, albeit at the cost of the clarity
of the image.
At this point, we introduce something called the singular-value decomposition (SVD). Any matrix
A can be decomposed as A = USV T
, where the rows of U form an orthonormal basis for the rows
of A and the columns of V
T
form an orthonormal basis for the columns of A. In effect, we are
representing the matrix A in a different orthonormal basis. Note that this is analagous to DTFS
– there we represent a signal (or a vector) in a different orthonormal basis. To understand SVD
further, you can check out any intermediate linear algebra course online. For this homework, this is
all you need to know: SVD is essentially representing a matrix using a different orthonormal basis.
The information about the bases are contained in matrices U and V and the representation of A in
these bases is given by the matrix S, which is a diagonal matrix (this matrix has non-zero values
3
only in its diagonal entries, it is zero everywhere else). The diagonal entries of S are called the
“singular values” of A.
The tasks:
(a). (20 points) On MATLAB, use the command
>>[U,S,V]=svd(A)
to get the singular value decomposition of the image matrix. Extract the diagonal entries
of S and store it in an array singvals. The array singvals now contains the singular values in decreasing order. Now, from the array singvals, extract the indices of those singular
values which are at least 0.01 of the largest singular value. You can use the MATLAB command
>>indices = find(singvals >=0.01*max(singvals))
Now construct new matrices U red,S red,V red as follows:
• U red is a matrix which contains only the columns of U corresponding to the indices
obtained above. For example, if indices=[1,4,5], then U red is a matrix with only
3 columns, where the first column of U red is the first column of U, the second column of
U red is the fourth column of U, and the third column of U red is the fifth column of U.
• S red is a diagonal matrix corresponding to the indices obtained above. For example,
if indices=[1,4,5], then S red is a 3 × 3 matrix with the 3 diagonal entries as the
first, fourth and fifth diagonal entries of S.
• V red is a matrix which contains only the columns of V corresponding to the indices
obtained above. This is similar to constructing U red from U.
Now construct an approximation of A using matrices U red,S red,V red as follows:
>>A red = U red * S red * V red’;
Use imshow() to display the image corresponding to A red.
Attach the MATLAB script you wrote above with your submission, and also the
image you obtained with A red.
(b). (5 points) Question: We saw earlier that we need 262144 real values to represent A. Similarly,
we need 262144 real values to represent A red as well. Instead, note that U red,S red,V red
contain all the information needed to construct A red. How many real values do we need to
store U red,S red,V red? How much better is this compared to storing A?
4
