CS 248: Midterm Solutions

Question 4

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.

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.

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).