m10351 Digital Signal Processing Problems 2.36 2001/08/22 2009/06/11 11:01:34.501 GMT-5 Don Johnson Don Johnson dhj@rice.edu Don Johnson Don Johnson dhj@rice.edu Brent Michael Hendricks Brent Hendricks brentmh@rice.edu Jeffrey M Silverman Jeffrey Silverman JSilverman@astro.berkeley.edu Erin Snavely Erin Snavely ernsnave@alumni.rice.edu Don Johnson Don Johnson dhj@rice.edu elec241 problems Science and Technology (Blank Abstract) en

The signal s t is bandlimited to 4 kHz. We want to sample it, but it has been subjected to various signal processing manipulations. What sampling frequency (if any works) can be used to sample the result of passing s t through an RC highpass filter with R 10 kΩ and C 8 nF ? What sampling frequency (if any works) can be used to sample the derivative of s t ? The signal s t has been modulated by an 8 kHz sinusoid having an unknown phase: the resulting signal is s t 2 f 0 t φ , with f 0 8 kHz and φ ? Can the modulated signal be sampled so that the original signal can be recovered from the modulated signal regardless of the phase value φ? If so, show how and find the smallest sampling rate that can be used; if not, show why not.

Using the properties of the Fourier series can ease finding a signal's spectrum. Suppose a signal s t is periodic with period T. If ck represents the signal's Fourier series coefficients, what are the Fourier series coefficients of s t T 2 ? Find the Fourier series of the signal p t shown in . Suppose this signal is used to sample a signal bandlimited to 1 T Hz . Find an expression for and sketch the spectrum of the sampled signal. Does aliasing occur? If so, can a change in sampling rate prevent aliasing; if not, show how the signal can be recovered from these samples.

A signal processing engineer from Texas A&M claims to have developed an improved sampling scheme. He multiplies the bandlimited signal by the depicted periodic pulse signal to perform sampling ().

Find the Fourier spectrum of this signal. Will this scheme work? If so, how should T S be related to the signal's bandwidth? If not, why not?

The signal s t has the indicated spectrum.

What is the minimum sampling rate for this signal suggested by the Sampling Theorem? Because of the particular structure of this spectrum, one wonders whether a lower sampling rate could be used. Show that this is indeed the case, and find the system that reconstructs s t from its samples.

If a signal is bandlimited to W Hz, we can sample it at any rate 1 Ts 2 W and recover the waveform exactly. This statement of the Sampling Theorem can be taken to mean that all information about the original signal can be extracted from the samples. While true in principle, you do have to be careful how you do so. In addition to the rms value of a signal, an important aspect of a signal is its peak value, which equals s t . Let s t be a sinusoid having frequency W Hz. If we sample it at precisely the Nyquist rate, how accurately do the samples convey the sinusoid's amplitude? In other words, find the worst case example. How fast would you need to sample for the amplitude estimate to be within 5% of the true value? Another issue in sampling is the inherent amplitude quantization produced by A/D converters. Assume the maximum voltage allowed by the converter is Vmax volts and that it quantizes amplitudes to b bits. We can express the quantized sample Q s n Ts as s n Ts ε t , where ε t represents the quantization error at the n th sample. Assuming the converter rounds, how large is maximum quantization error? We can describe the quantization error as noise, with a power proportional to the square of the maximum error. What is the signal-to-noise ratio of the quantization error for a full-range sinusoid? Express your result in decibels.

An A/D converter has a curious hardware problem: Every other sampling pulse is half its normal amplitude ().

Find the Fourier series for this signal. Can this signal be used to sample a bandlimited signal having highest frequency W 1 2 T ?

Commercial digital-to-analog converters don't work this way, but a simple circuit illustrates how they work. Let's assume we have a B-bit converter. Thus, we want to convert numbers having a B-bit representation into a voltage proportional to that number. The first step taken by our simple converter is to represent the number by a sequence of B pulses occurring at multiples of a time interval T. The presence of a pulse indicates a “1” in the corresponding bit position, and pulse absence means a “0” occurred. For a 4-bit converter, the number 13 has the binary representation 1101 ( 13 10 1 2 3 1 2 2 0 2 1 1 2 0 ) and would be represented by the depicted pulse sequence. Note that the pulse sequence is “backwards” from the binary representation. We'll see why that is.

This signal serves as the input to a first-order RC lowpass filter. We want to design the filter and the parameters Δ and T so that the output voltage at time 4 T (for a 4-bit converter) is proportional to the number. This combination of pulse creation and filtering constitutes our simple D/A converter. The requirements are The voltage at time t 4 T should diminish by a factor of 2 the further the pulse occurs from this time. In other words, the voltage due to a pulse at 3T should be twice that of a pulse produced at 2T, which in turn is twice that of a pulse at T, etc. The 4-bit D/A converter must support a 10 kHz sampling rate. Show the circuit that works. How do the converter's parameters change with sampling rate and number of bits in the converter?

Find the Fourier transforms of the following sequences, where s n is some sequence having Fourier transform S 2 f . 1 n s n s n 2 f0 n x n s n 2 n even 0 n odd n s n

Find the indicated spectra for the following signals. The discrete-time Fourier transform of s n 4 n 2 n -1 0 1 0 otherwise The discrete-time Fourier transform of s n n n -2 -1 0 1 2 0 otherwise The discrete-time Fourier transform of s n 4 n n 0 … 7 0 otherwise The length-8 DFT of the previous signal.

Sammy loves to whistle and decides to record and analyze his whistling in lab. He is a very good whistler; his whistle is a pure sinusoid that can be described by sa t 4000t . To analyze the spectrum, he samples his recorded whistle with a sampling interval of TS 2.5 10-4 to obtain sn sa n TS . Sammy (wisely) decides to analyze a few samples at a time, so he grabs 30 consecutive, but arbitrarily chosen, samples. He calls this sequence xn and realizes he can write it as xn 4000n TS θ ,   n 0 … 29 Did Sammy under- or over-sample his whistle? What is the discrete-time Fourier transform of xn and how does it depend on θ? How does the 32-point DFT of xn depend on θ?

We can find the input-output relation for a discrete-time filter much more easily than for analog filters. The key idea is that a sequence can be written as a weighted linear combination of unit samples. Show that x n i i x i δ n i where δ n is the unit-sample. δ n 1 n 0 0 If h n denotes the unit-sample response—the output of a discrete-time linear, shift-invariant filter to a unit-sample input—find an expression for the output. In particular, assume our filter is FIR, with the unit-sample response having duration q 1 . If the input has duration N, what is the duration of the filter's output to this signal? Let the filter be a boxcar averager: h n 1 q 1 for n 0 … q and zero otherwise. Let the input be a pulse of unit height and duration N. Find the filter's output when N q 1 2 , q an odd integer.

A digital filter has the depicted unit-sample reponse.

What is the difference equation that defines this filter's input-output relationship? What is this filter's transfer function? What is the filter's output when the input is n 4 ?

Consider a FIR filter governed by the difference equation y n 13 x n 2 23 x n 1 x n 23 x n 1 13 x n 2 Find this filter's unit-sample response. Find this filter's transfer function. Characterize this transfer function (i.e., what classic filter category does it fall into). Suppose we take a sequence and stretch it out by a factor of three. x n s n 3 m m … -1 0 1 … n 3 m 0 Sketch the sequence x n for some example s n . What is the filter's output to this input? In particular, what is the output at the indices where the input x n is intentionally zero? Now how would you characterize this system?

Much of physics is governed by differntial equations, and we want to use signal processing methods to simulate physical problems. The idea is to replace the derivative with a discrete-time approximation and solve the resulting differential equation. For example, suppose we have the differential equation t y t a y t x t and we approximate the derivative by t n T t y t y n T y n 1 T T where T essentially amounts to a sampling interval. What is the difference equation that must be solved to approximate the differential equation? When x t u t , the unit step, what will be the simulated output? Assuming x t is a sinusoid, how should the sampling interval T be chosen so that the approximation works well?

Let's explore the DFT and its properties. What is the length-K DFT of length-N boxcar sequence, where N K ? Consider the special case where K 4 . Find the inverse DFT of the product of the DFTs of two length-3 boxcars. If we could use DFTs to perform linear filtering, it should be true that the product of the input's DFT and the unit-sample response's DFT equals the output's DFT. So that you can use what you just calculated, let the input be a boxcar signal and the unit-sample response also be a boxcar. The result of part (b) would then be the filter's output if we could implement the filter with length-4 DFTs. Does the actual output of the boxcar-filter equal the result found in the previous part? What would you need to change so that the product of the DFTs of the input and unit-sample response in this case equaled the DFT of the filtered output?

Just to determine how fast the FFT algorithm really is, we can take advantage of MATLAB's fft function. If x is a length-N vector, fft(x) computes the length-N transform using the most efficient algorithm it can. In other words, it does not automatically zero-pad the sequence and it will use the FFT algorithm if the length is a power of two. Let's count the number of arithmetic operations the fft program requires for lengths ranging from 2 to 1024. For each length to be tested, generate a vector of random numbers, calculate the vector's transform, and determine how long it took. The program illustrates the computations. Plot the vector of computation times. What lengths consume the most computations? What complexity do they seem to have? What lengths have the fewest computations? for n=2:1024, x = randn(1,n); t_start = cputime; fft(x); time(n) = cputime - t_start; end

Sammy is faced with computing lots of discrete Fourier transforms. He will, or course, use the FFT algorithm, but he is behind schedule and needs to get his results as quickly as possible. He gets the idea of computing two transforms at one time by computing the transform of s n s1 n s2 n , where s1 n and s2 n are two real-valued signals of which he needs to compute the spectra. The issue is whether he can retrieve the individual DFTs from the result or not. What will be the DFT Sk of this complex-valued signal in terms of S1 k and S2 k , the DFTs of the original signals? Sammy's friend, an Aggie who knows some signal processing, says that retrieving the wanted DFTs is easy: “Just find the real and imaginary parts of Sk .” Show that this approach is too simplistic. While his friend's idea is not correct, it does give him an idea. What approach will work? Hint: Use the symmetry properties of the DFT. How does the number of computations change with this approach? Will Sammy's idea ultimately lead to a faster computation of the required DFTs?

The discrete cosine transform of a length-N sequence is defined to be Sc k n 0 N 1 sn 2nk 2N Note that the number of frequency terms is 2N 1 : k 0 … 2N 1 . Find the inverse DCT. Does a Parseval's Theorem hold for the DCT? You choose to transmit information about the signal s n according to the DCT coefficients. You could only send one, which one would you send?

A digital filter is described by the following difference equation: yn a y n 1 a xn x n 1 , a 1 2 What is this filter's unit sample response? What is this filter's transfer function? What is this filter's output when the input is n 4 ?

A digital filter is determined by the following difference equation. y n y n 1 x n x n 4 Find this filter's unit sample response. What is the filter's transfer function? Find the filter's output when the input is the sinusoid n 2 .

A filter has an input-output relationship given by the difference equation y n 14 x n 12 x n 1 14 x n 2 . What is the filter's transfer function? How would you characterize it? What is the filter's output when the input equals n 2 ? What is the filter's output when the input is the depicted discrete-time square-wave ()?

We have a filter with the transfer function H 2 f 2 f 2 f operating on the input signal xn δn δ n 2 that yields the output yn . What is the filter's unit-sample response? What is the discrete-Fourier transform of the output? What is the time-domain expression for the output?

A discrete-time system is governed by the difference equation y n y n 1 x n x n 1 2 Find the transfer function for this system. What is this system's output when the input is n 2 ? If the output is observed to be y n δ n δ n 1 , then what is the input?

A digital filter has an input-output relationship expressed by the difference equation y n x n x n 1 x n 2 x n 3 4 . Plot the magnitude and phase of this filter's transfer function. What is this filter's output when x n n 2 2 2 n 3 ?

The signal x n equals δ n δ n 1 . Find the length-8 DFT (discrete Fourier transform) of this signal. You are told that when x n served as the input to a linear FIR (finite impulse response) filter, the output was y n δ n δ n 1 2 δ n 2 . Is this statement true? If so, indicate why and find the system's unit sample response; if not, show why not.

A discrete-time, shift invariant, linear system produces an output y n 1 -1 0 0 … when its input x n equals a unit sample. Find the difference equation governing the system. Find the output when x n 2 f0 n . How would you describe this system's function?

A discrete-time system has transfer function H 2 f . A signal x n is passed through this system to yield the signal w n . The time-reversed signal w n is then passed through the system to yield the time-reversed output y n . What is the transfer function between x n and y n ?

The slang word “hum” represents power line waveforms that creep into signals because of poor circuit construction. Usually, the 60 Hz signal (and its harmonics) are added to the desired signal. What we seek are filters that can remove hum. In this problem, the signal and the accompanying hum have been sampled; we want to design a digital filter for hum removal. Find filter coefficients for the length-3 FIR filter that can remove a sinusoid having digital frequency f0 from its input. Assuming the sampling rate is fs to what analog frequency does f0 correspond? A more general approach is to design a filter having a frequency response magnitude proportional to the absolute value of a cosine: H 2 f ∝ f N . In this way, not only can the fundamental but also its first few harmonics be removed. Select the parameter N and the sampling rate so that the frequencies at which the cosine equals zero correspond to 60 Hz and its odd harmonics through the fifth. Find the difference equation that defines this filter.

Thinking that digital implementations are always better, our clever engineer wants to design a digital AM receiver. The receiver would bandpass the received signal, pass the result through an A/D converter, perform all the demodulation with digital signal processing systems, and end with a D/A converter to produce the analog message signal. Assume in this problem that the carrier frequency is always a large even multiple of the message signal's bandwidth W . What is the smallest sampling rate that would be needed? Show the block diagram of the least complex digital AM receiver. Assuming the channel adds white noise and that a b-bit A/D converter is used, what is the output's signal-to-noise ratio?

A problem on Samantha's homework asks for the 8-point DFT of the discrete-time signal δ n 1 δ n 7 . What answer should Samantha obtain? As a check, her group partner Sammy says that he computed the inverse DFT of her answer and got δ n 1 δ n 1 . Does Sammy's result mean that Samantha's answer is wrong? The homework problem says to lowpass-filter the sequence by multiplying its DFT by H k 1 k 0 1 7 0 and then computing the inverse DFT. Will this filtering algorithm work? If so, find the filtered output; if not, why not?

Because a trading week lasts five days, stock markets frequently compute running averages each day over the previous five trading days to smooth price fluctuations. The technical stock analyst at the Buy-Lo--Sell-Hi brokerage firm has heard that FFT filtering techniques work better than any others (in terms of producing more accurate averages). What is the difference equation governing the five-day averager for daily stock prices? Design an efficient FFT-based filtering algorithm for the broker. How much data should be processed at once to produce an efficient algorithm? What length transform should be used? Is the analyst's information correct that FFT techniques produce more accurate averages than any others? Why or why not?

RU Electronics wants to develop a filter that would be used in analog applications, but that is implemented digitally. The filter is to operate on signals that have a 10 kHz bandwidth, and will serve as a lowpass filter. What is the block diagram for your filter implementation? Explicitly denote which components are analog, which are digital (a computer performs the task), and which interface between analog and digital worlds. What sampling rate must be used and how many bits must be used in the A/D converter for the acquired signal's signal-to-noise ratio to be at least 60 dB? For this calculation, assume the signal is a sinusoid. If the filter is a length-128 FIR filter (the duration of the filter's unit-sample response equals 128), should it be implemented in the time or frequency domain? Assuming H 2 f is the transfer function of the digital filter, what is the transfer function of your system?

Because of the slowness of the Internet, lossy signal compression becomes important if you want signals to be received quickly. An enterprising 241 student has proposed a scheme based on frequency-domain processing. First of all, he would section the signal into length-N blocks, and compute its N-point DFT. He then would discard (zero the spectrum) at half of the frequencies, quantize them to b-bits, and send these over the network. The receiver would assemble the transmitted spectrum and compute the inverse DFT, thus reconstituting an N-point block. At what frequencies should the spectrum be zeroed to minimize the error in this lossy compression scheme? The nominal way to represent a signal digitally is to use simple b-bit quantization of the time-domain waveform. How long should a section be in the proposed scheme so that the required number of bits/sample is smaller than that nominally required? Assuming that effective compression can be achieved, would the proposed scheme yield satisfactory results?