#
CS 248: Midterm Solutions

##
Question 4

*Grader: Pat Hanrahan *
### 4a [5 points]

Convolving a function in the spatial domain with a sinc function is
impractical because the sinc function has infinite extent. The time to
compute each output sample is proportional to the width of the filter.
A box filter, which has unit width, takes the minimum amount of time.
Another advantage of the box function is that it's value is 1, thus
no multiplications are needed. The sinc function
takes on continuous values between -1 and 1, these
must be evaluated and multiplied times the original function.
#### Grading

Full credit was given if you said the problem was the infinite extent.
3 points were given for the 2nd answer. Many people answered that the box
function was a good approximation to the sinc function, and I gave 2 points
for that answer.
### 4b [7.5 points]

Since in general the signal to be sampled may contain high frequencies,
it should be filtered before sampling to remove frequencies above the
Nyquist frequency. The correct filter is an ideal low-pass filter. Drawn
in the frequency domain, the ideal low-pass filter is a box filter centered
at the origin and extending to the Nyquist frequency (1/2 the sampling
frequency).
The fourier transform of box function in frequency space is a sinc function
in the spatial domain. And the analoque to multiplication is convolution.
Thus, to perfectly low-pass filter the signal requires a convolution with
a sinc function, and by the reasons described in 4A, this is impractical.

Much more practical is to convolve with a box function. However, convolving
with a box function in the spatial domain corresponds to multiplying by
a sinc function in the frequency domain. However, a sinc function in the
frequency domain is not a perfect low-pass filter. Therefore it does not
remove all the frequencies above the Nyquist frequency. If the signal is
subsequently sampled, then the filtered function will be duplicated and
these high frequencies will cause aliasing.

#### Grading

The most common mistake was to think we wanted you to apply the box
filter in *frequency* space. 4 points were given if you described
this properly.
Some people correctly showed the multiplication of the sinc function times
the original function in frequency space, but forgot to draw or describe
the effects of sampling. 2 points were taken away if you did not address
whether aliasing occurs.

### 4c [7.5 points]

The sampling process introduces copies of the function's spectra at integer
multiples of the sampling frequency. Assuming the function is bandlimited,
no aliasing occurs; that is, these copies do not overlap. The original
function may be reconstructed by filtering with an ideal low-pass filter. This
has the effect of removing all the copies of the function in frequency space.
Analyzing the situation in the spatial domain, applying the ideal low-pass
filter corresponds to convolving the sampled signal with a sinc function. In
effect, interpolating the samples with a sinc. Unfortunately, this is impractical.

A common approximation is to reconstruct with a box function.
This corresponds to setting each pixel in a image to a constant colored square.
The error introduced by this approximation is easy to analyze
in frequency space. Instead of multiplying the sampled spectra by
a box filter, we multiply it by a sinc filter. The sinc function, however,
is not 0 outside the Nyquist frequency, and so the copies of the spectra
introduced by the sampling process are attenuated, but not removed. This
causes an effect called *post-aliasing*. A figure describing this
process is contained in the Notes on Signal Processing (Figure 16).

#### Grading

The most common mistake was to show a box filter in frequency space,
not a sinc filter. 4 points were given for this answer.