Digital Signal Processing Problems 2.33 2001/08/22 2008/07/31 18:13:42.527 GMT-5 Don Johnson dhj@rice.edu Don Johnson dhj@rice.edu Brent Michael Hendricks brentmh@rice.edu Jeffrey M Silverman JSilverman@astro.berkeley.edu Erin Snavely ernsnave@alumni.rice.edu elec241 problems (Blank Abstract)

Sampling and Filtering 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.

Non-Standard Sampling 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.

Pulse Signal

A Different Sampling Scheme 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?

Bandpass Sampling 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.

Sampling Signals 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.

Hardware Error 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 ?

Simple D/A Converter 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?

Discrete-Time Fourier Transforms 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

Spectra of Finite-Duration Signals 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.

Just Whistlin' 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 θ?

Discrete-Time Filtering 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 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 ?

A Special Discrete-Time Filter 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?

Simulating the Real World 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?

The DFT 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?

The Fast Fourier Transform 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?

Program

DSP Tricks 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?

Discrete Cosine Transform (DCT) 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 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 ?

Another Digital Filter 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 .

Yet Another Digital Filter 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 ()?

A Digital Filter in the Frequency Domain 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?

Digital Filters 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?

Digital Filtering 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 ?

Detective Work 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?

Time Reversal has Uses 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 ?

Removing “Hum” 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.

Digital AM Receiver 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?

DFTs 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?

Stock Market Data Processing 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?

Digital Filtering of Analog Signals 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?

Signal Compression 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?