FOURIER ANALYSIS OF [DISCRETE-TIME](#page-14-0) SIGNALS

← Back to LINEAR SYSTEMS AND SIGNALS Overview

PROBLEMS

[Note: In many problems, the plots of spectra are shown as functions of frequency f Hz for convenience, although we have labeled them as functions of ω as X(ω), Y(ω), etc.]

• 8.1-1 If f^s is the Nyquist rate for signal x(t), determine the Nyquist rate for each of the following signals:

  • (a) *^y*a(t) ^{= d} dt x(t)
  • (b) yb(t) = x(t) cos(2πf0t)
  • (c) yc(t) = x(t+a)+x(t−b), for real constants a and b
  • (d) yd(t) = x(at), for real a > 0

• 8.1-2 Figure P8.1-2 shows Fourier spectra of signals x1(t) and x2(t). Determine the Nyquist sampling rates for signals x1(t), x2(t), x^{2 1}(t), x^{3 2}(t), and x1(t)x2(t).

• 8.1-3 A signal x(t) has a bandwidth of B = 1000 Hz. For a positive integer N, what is the Nyquist rate for the signal ^y(t) ^{= x}N(t)?

• 8.1-4 Determine the Nyquist sampling rate and the Nyquist sampling interval for the signals: (a) sinc2(100πt)

  • (b) 0.01 sinc2(100πt)

Figure P8.1-2

836 CHAPTER 8 SAMPLING: THE BRIDGE FROM CONTINUOUS TO DISCRETE

• (c) sinc(100πt)+3sinc2(60πt)
• (d) sinc(50πt)sinc(100πt)
• 8.1-5 (a) Sketch |X(ω)|, the amplitude spectrum of a signal x(t) = 3 cos 6πt + sin 18πt + 2 cos(28 − )πt, where is a very small number → 0. Determine the minimum sampling rate required to be able to reconstruct x(t) from these samples.
  • (b) Sketch the amplitude spectrum of the sampled signal when the sampling rate is 25% above the Nyquist rate (show the spectrum over the frequency range ±50 Hz only). How would you reconstruct x(t) from these samples?
• 8.1-6 (a) Derive the sampling theorem by considering the fact that the sampled signal x(t) = x(t)δ*^T* (t), and using the frequency-convolutionpropertyinEq.(7.34).
  • (b) For a sampling train consisting of shifted unit impulses at instants nT + τ instead of at nT (for all positive and negative integer values of n), find the spectrum of the sampled signal.
• 8.1-7 A signal is bandlimited to 12 kHz. The band between 10 and 12 kHz has been so corrupted by excessive noise that the information in this band is nonrecoverable. Determine the minimum sampling rate for this signal so that the uncorrupted portion of the band can be recovered. If we were to filter out the corrupted

spectrum prior to sampling, what would be the minimum sampling rate?

• 8.1-8 A continuous-time signal x(t) = ((t − 1)/2) is sampled at three rates: 10, 2, and 1 Hz. Sketch the resulting sampled signals. Because x(t) is timelimited, its bandwidth is infinite. However, most of its energy is concentrated in a small band. Determine a reasonable minimum sampling rate that will allow reconstruction of this signal with a small error. The answer is not unique. Make a reasonable assumption of what you define as a “negligible” or “small” error.
• 8.1-9 (a) A signal ^x(t) ⁼ 5 sinc2 (5πt) ⁺ cos 20π*^t* is sampled at a rate of 10 Hz. Find the spectrum of the sampled signal. Can x(t) be reconstructed by lowpass filtering the sampled signal?
  • (b) Repeat part (a) for a sampling frequency of 20 Hz. Can you reconstruct the signal from this sampled signal? Explain.
  • (c) If ^x(t) ⁼ 5 sinc2 (5πt) ⁺ sin 20πt, can you reconstruct x(t) from the samples of x(t) at a rate of 20 Hz? Explain your answer with spectral representation(s).
  • (d) For ^x(t) ⁼ 5 sinc2 (5πt) ⁺ sin 20πt, can you reconstruct x(t) from the samples of x(t) at a rate of 21 Hz? Explain your answer with spectral representation(s). Comment on your results.
• 8.1-10 (a) The highest frequency in the spectrum X(ω) (Fig. P8.1-10a) of a bandpass signal x(t)

Figure P8.1-10

is 30 Hz. Hence, the minimum sampling frequency needed to sample x(t) is 60 Hz. Show the spectrum of the signal sampled at a rate of 60 Hz. Can you reconstruct x(t) from these samples? How?

• (b) A certain busy student looks at X(ω), concludes that its bandwidth is really 10 Hz, and decides that the sampling rate 20 Hz is adequate for sampling x(t). Sketch the spectrum of the signal sampled at a rate of 20 Hz. Can x(t) be reconstructed from these samples?
• (c) The same student, using the same reasoning, looks at Y(ω) in Fig. P8.1-10b, the spectrum of another bandpass signal y(t), and concludes that the sampling rate of 20 Hz can be used to sample y(t). Sketch the spectrum of the signal y(t) sampled at a rate of 20 Hz. Can y(t) be reconstructed from these samples?
• 8.1-11 A signal x(t) whose spectrum X(ω), as shown in Fig. P8.1-11, is sampled at a frequency fs = f¹ + f² Hz. Find all the sample values of x(t) merely by inspection of X(ω).
• 8.1-12 As described in Sec. 8.1-1, practical sampling can be achieved by multiplying a signal x(t) by a periodic train of pulses pT (t). The pulse train pT (t) can be created by the periodic replication of some pulse p(t) as

$$p_T(t) = \sum_{k=-\infty}^{\infty} p(t - kT)$$

It is desired to sample a signal at a rate f^s = 100 Hz, and two pulses are under consideration:

$$p_a(t) = -\frac{1}{4}u(t) + \frac{5}{4}u(t - \frac{2T}{20}) +$$ $$-\frac{5}{4}u(t - \frac{3T}{20}) + \frac{1}{4}u(t - \frac{5T}{20})$$

and

$$p_{\rm b}(t) = e^{-t/T} \left[ u(t) - u(t - 1.5T) \right]$$

• (a) Plot pT (t) using pa(t) over 0 ≤ t ≤ 4T.
• (b) Plot pT (t) using pb(t) over 0 ≤ t ≤ 4T.
• (c) Which pulse, pa(t) or pb(t), is more suitable as a sampling pulse? Carefully explain your answer.
• 8.1-13 In digital data transmission over a communication channel, it is important to know the upper theoretical limit on the rate of digital pulses that can be transmitted over a channel of bandwidth B Hz. In digital transmission, the relative shape of the pulse is not important. We are interested in knowing only the amplitude represented by the pulse. For instance, in binary communication, we are interested in knowing whether the received pulse amplitude is 1 or −1 (positive or negative). Thus, each pulse represents one piece of information. Consider one independent amplitude value (not necessarily binary) as one piece of information. Show that 2B independent pieces of information per second can be transmitted correctly (assuming no noise) over a channel of bandwidth B Hz. This important principle in communication theory states that 1 Hz of bandwidth can transmit two independent pieces of information per second. It represents the upper rate of pulse transmission over a channel without any error in reception in the absence of noise. [Hint: According to the interpolation formula [Eq. (8.6)], a continuous-time signal of bandwidth B Hz can be constructed from 2B pieces of information/second.]
• 8.1-14 This example is one of those interesting situations leading to a curious result in the category of defying gravity. The sinc function can be recovered from its samples taken at extremely low frequencies in apparent defiance of the sampling theorem.

Consider a sinc pulse x(t) = sinc(4πt) for which X(ω) = (1/4)rect(ω/8π ). The bandwidth of x(t) is B = 2 Hz, and its Nyquist rate is 4 Hz.

Figure P8.1-11

• (a) Sample x(t) at a rate 4 Hz and sketch the spectrum of the sampled signal.
• (b) To recover x(t) from its samples, we pass the sampled signal through an ideal lowpass filter of bandwidth B = 2 Hz and gain G = T = 1/4. Sketch this system and show that for this system H(ω)=(1/4)rect(ω/8π ). Show also that when the input is the sampled x(t) at a rate 4 Hz, the output of this system is indeed x(t), as expected.
• (c) Now sample x(t) at half the Nyquist rate, at 2 Hz. Apply this sampled signal at the input of the lowpass filter used in part (b). Find the output.
• (d) Repeat part (c) for the sampling rate 1 Hz.
• (e) Show that the output of the lowpass filter in part (b) is x(t) to the sampled x(t) if the sampling rate is 4/N, where N is any positive integer. This means that we can recover x(t) from its samples taken at an arbitrarily small rate by letting N → ∞.
• (f) The mystery may be clarified a bit by examining the problem in the time domain. Find the samples of x(t) when the sampling rate is 2/N (N integer).
• 8.2-1 A signal x(t) = sinc (200πt) is sampled (multiplied) by a periodic pulse train pT (t) represented in Fig. P8.2-1. Find and sketch the spectrum of the sampled signal. Explain whether you will be able to reconstruct x(t) from these samples. Find the filter output if the sampled signal is passed through an ideal lowpass filter of bandwidth 100 Hz and unit gain. What is the filter output if its bandwidth B Hz is between 100 and 150 Hz? What happens if the bandwidth exceeds 150 Hz?
• 8.2-2 Show that the circuit in Fig. P8.2-2 is a realization of the causal ZOH (zero-order hold) circuit. You can do this by showing that the unit impulse response h(t) of this circuit is indeed equal to that in Eq. (8.5) delayed by T/2 seconds to make it causal.

Figure P8.2-2

• 8.2-3 (a) A first-order hold circuit (FOH) can also be used to reconstruct a signal x(t) from its samples. The impulse response of this circuit is h(t) = (t/2T), where T is the sampling interval. Consider a typical sampled signal x(t) and show that this circuit performs the linear interpolation. In other words, the filter output consists of sample tops connected by straight-line segments. Follow the procedure discussed in Sec. 8.2 (Fig. 8.5c).
  • (b) Determine the frequency and magnitude responses of this filter, and compare it with (i) the ideal filter required for signal reconstruction and (ii) a ZOH circuit.
  • (c) This filter, being noncausal, is unrealizable. By delaying its impulse response, the filter can be made realizable. What is the minimum delay required to make it realizable? How would this delay affect the reconstructed signal and the filter frequency response?
  • (d) Show that the causal FOH circuit in part (c) can be realized by the ZOH circuit depicted in Fig. P8.2-2 followed by an identical filter in cascade.
• 8.2-4 Suppose signal x(t)=sin(2πt/8)(u(t)−u(t −8)) is sampled at a rate fs = 1 Hz to generate signal x[n].
  • (a) Sketch x(t) and x[n].
  • (b) Has aliasing occurred in sampling x(t) to produce x[n]? Explain.
  • (c) Sketch the output xˆ(t) produced when x[n] is applied to the causal ZOH reconstructor of Prob. 8.2-2. How does xˆ(t) compare with x(t)?

Figure P8.2-1

• (d) Sketch the output xˆ(t) produced when x[n] is applied to the FOH reconstructor of Prob.8.2-3.Howdoesxˆ(t)comparewithx(t)?
• 8.2-5 Repeat Prob. 8.2-4 for the signal x(t) = cos(2πt/8)(u(t)−u(t −8)).
• 8.2-6 Is it possible to sample a physically realizable (nonzero) signal x(t) with a physically realizable system without aliasing? If possible, explain what conditions must be met. If not possible, explain why not.
• 8.2-7 In the text, for sampling purposes, we used timelimited narrow pulses such as impulses or rectangular pulses of width less than the sampling interval T. Show that it is not necessary to restrict the sampling pulse width. We can use sampling pulses of arbitrarily large duration and still be able to reconstruct the signal x(t) as long as the pulse rate is no less than the Nyquist rate for x(t).

Consider x(t) to be bandlimited to B Hz. The sampling pulse to be used is an exponential e−atu(t). We multiply x(t) by a periodic train of exponential pulses of the form e−atu(t) spaced T seconds apart. Find the spectrum of the sampled signal, and show that x(t) can be reconstructed from this sampled signal provided the sampling rate is no less than 2B Hz or T < 1/2B. Explain how you would reconstruct x(t) from the sampled signal.

• 8.2-8 In Ex. 8.2, the sampling of a signal x(t) was accomplished by multiplying the signal by a pulse train pT (t), resulting in the sampled signal depicted in Fig. 8.4d. This procedure is known as the natural sampling. Figure P8.2-8 shows the so-called flat-top sampling of the same signal ^x(t) ⁼ sinc2 (5πt).
  • (a) Show that the signal x(t) can be recovered from flat-top samples if the sampling rate is no less than the Nyquist rate.
  • (b) Explain how you would recover x(t) from the flat-top samples.
  • (c) Find the expression for the sampled signal spectrum X(ω) and sketch it roughly.
• 8.2-9 A sinusoid of frequency f⁰ Hz is sampled at a rate fs = 20 Hz. Find the apparent frequency of the sampled signal if f⁰ is:
  • (a) 8 Hz
  • (b) 12 Hz

(c) 20 Hz

• (d) 22 Hz
• (e) 32 Hz
• 8.2-10 A sinusoid of unknown frequency f⁰ is sampled at a rate 60 Hz. The apparent frequency of the samples is 20 Hz. Determine f⁰ if it is known that f⁰ lies in the range:
  • (a) 0–30 Hz
  • (b) 30–60 Hz
  • (c) 60–90 Hz
  • (d) 90–120 Hz
• 8.2-11 A signal x(t) = 3 cos 6πt+cos 16πt+2 cos 20πt is sampled at a rate 25% above the Nyquist rate. Sketch the spectrum of the sampled signal. How would you reconstruct x(t) from these samples? If the sampling frequency is 25% below the Nyquist rate, what are the frequencies of the sinusoids present in the output of the filter with cutoff frequency equal to the folding frequency? Do not write the actual output; give just the frequencies of the sinusoids present in the output.
• 8.2-12 A complex signal x(t) has a spectrum given as

$$X(\omega) = \begin{cases} \omega & 0 \le \omega \le 2\pi 10 \\ 0 & \text{otherwise} \end{cases}$$

Let x(t) be sampled at rate f^s = 24 Hz to produce signal x(t) with spectrum X(ω).

• (a) Sketch X(ω).

• (b) Has aliasing occurred in sampling x(t) to produce x(t)? Explain.

• (c) Can x(t) be exactly recovered from x(t)? Explain.

• 8.2-13 Repeat Prob. 8.2-12 for the sampling rate f^s = 16 Hz.

• 8.2-14 Repeat Prob. 8.2-12 for the sampling rate f^s = 8 Hz.

• 8.2-15 (a) Show that the signal x(t), reconstructed from its samples x(nT), using Eq. (8.6) has a bandwidth B ≤ 1/2T Hz.

  • (b) Show that x(t) is the smallest bandwidth signal that passes through samples x(nT). [Hint: Use the reductio ad absurdum method.]

• 8.2-16 In digital communication systems, the efficient use of channel bandwidth is ensured by transmitting digital data encoded by means of bandlimited pulses. Unfortunately, bandlimited pulses are non-timelimited; that is, they have infinite duration, which causes pulses representing successive digits to interfere and cause errors in the reading of true pulse values. This difficulty can be resolved by shaping a pulse p(t) in such a way that it is bandlimited, yet causes zero interference at the sampling instants. To transmit R pulses per second, we require a minimum bandwidth R/2 Hz (see Prob. 8.1-13). The bandwidth of p(t) should be R/2 Hz, and its samples, in order to cause no interference at all other sampling instants, must satisfy the condition

$$p(nT) = \begin{cases} 1 & n = 0 \quad T = \frac{1}{R} \\ 0 & n \neq 0 \end{cases}$$

Because the pulse rate is R pulses per second, the sampling instants are located at intervals of 1/R seconds. Hence, the foregoing condition ensures that any given pulse will not interfere with the amplitude of any other pulse at its center. Find p(t). Is p(t) unique in the sense that no other pulse satisfies the given requirements?

8.2-17 The problem of pulse interference in digital data transmission was outlined in Prob. 8.2-16, where we found a pulse shape p(t) to eliminate the interference. Unfortunately, the pulse found is not only noncausal, (and unrealizable) but also has a serious drawback: because of its slow decay (as 1/t), it is prone to severe interference due to small parameter deviation. To make the pulse decay rapidly, Nyquist proposed relaxing the bandwidth requirement from R/2 Hz to kR/2 Hz with 1 ≤ k ≤ 2. The pulse must still have a property of noninterference with other pulses, for example,

$$p(nT) = \begin{cases} 1 & n = 0 \\ 0 & n \neq 0 \end{cases} \qquad T = \frac{1}{R}$$

Show that this condition is satisfied only if the pulse spectrum P(ω) has an odd symmetry about the set of dotted axes, as shown in Fig. P8.2-17. The bandwidth of P(ω) is kR/2 Hz (1 ≤ k ≤ 2).

8.2-18 The Nyquist samples of a signal x(t) bandlimited to B Hz are

$$x(nT) = \begin{cases} 1 & n = 0, 1 \\ 0 & \text{all } n \neq 0, 1 \end{cases} \qquad T = \frac{1}{2B}$$

Show that

$$x(t) = \frac{\operatorname{sinc}(2\pi Bt)}{1 - 2Bt}$$

This pulse, known as the duobinary pulse, is used in digital transmission applications.

Figure P8.2-17

8.2-19 A signal bandlimited to B Hz is sampled at a rate fs = 2B Hz. Show that

$$\int_{-\infty}^{\infty} x(t) dt = T \sum_{-\infty}^{\infty} x(nT)$$ $$\int_{-\infty}^{\infty} |x(t)|^2 dt = T \sum_{-\infty}^{\infty} |x(nT)|^2$$

[Hint: Use the orthogonality property of the sinc function in Prob. 7.6-6.]

• 8.2-20 Prove that a signal cannot be simultaneously timelimited and bandlimited. [Hint: Show that a contrary assumption leads to contradiction. Assume a signal to be simultaneously timelimited and bandlimited so that X(ω) = 0 for |ω| ≥ 2πB. In this case, X(ω) = X(ω)rect(ω/4πB ) for B > B. This fact means that x(t) is equal to x(t) ∗ 2B sinc (2πB t). The latter cannot be timelimited because the sinc function tail extends to infinity.]

• 8.3-1 Physically implementable digital systems, such as smartphones and computers, require that signals be both time-sampled and amplitude-quantized.

  • (a) Why is time sampling necessary? When does time sampling result in unrecoverable changes to the signal?
  • (b) Why is amplitude-quantization necessary? When does amplitude quantization result in unrecoverable changes to the signal?

• 8.3-2 Typical analog-to-digital converters (ADCs) operate over a range of input amplitudes [−Vref,Vref]. Why is it desirable to condition the input x(t) to an ADC so that its maximum magnitude is close to, but does not exceed, Vref? What happens if the maximum magnitude of x(t) is greater than Vref? What happens if the maximum magnitude of x(t) is much smaller than Vref?

• 8.3-3 A compact disc (CD) records audio signals digitally by means of a binary code. Assume an audio signal bandwidth of 15 kHz.

  • (a) What is the Nyquist rate?
  • (b) If the Nyquist samples are quantized into 65,536 levels (L = 65,536) and then binary-coded, what number of binary digits is required to encode a sample?

• (c) Determine the number of binary digits per second (bits/s) required to encode the audio signal.

• (d) For practical reasons discussed in the text, signals are sampled at a rate well above the Nyquist rate. Practical CDs use 44,100 samples/s. If L = 65,536, determine the number of pulses per second required to encode the signal.

• 8.3-4 A TV signal (video and audio) has a bandwidth of 4.5 MHz. This signal is sampled, quantized, and binary-coded.

  • (a) Determine the sampling rate if the signal is to be sampled at a rate 20% above the Nyquist rate.
  • (b) If the samples are quantized into 1024 levels, what number of binary pulses is required to encode each sample?
  • (c) Determine the binary pulse rate (bits/s) of the binary-coded signal.

• 8.3-5 (a) In a certain A/D scheme, there are 16 quantization levels. Give one possible binary code and one possible quaternary (4-ary) code. For the quaternary code, use 0, 1, 2, and 3 as the four symbols. Use the minimum number of digits in your code.

  • (b) To represent a given number of quantization levels L, we require a minimum of bM digits for an M-ary code. Show that the ratio of the number of digits in a binary code to the number of digits in a quaternary (4-ary) code is 2, that is, b2/b⁴ = 2.

• 8.3-6 Five telemetry signals, each of bandwidth 1 kHz, are quantized and binary-coded. These signals are time-division multiplexed (signal bits interleaved). Choose the number of quantization levels so that the maximum error in sample amplitudes is no greater than 0.2% of the peak signal amplitude. The signals must be sampled at least 20% above the Nyquist rate. Determine the data rate (bits per second) of the multiplexed signal.

• 8.4-1 A triangle function x(t) = (t/5) has spectrum X(ω). Sketch the corresponding time-domain signal xT⁰ (t) if X(ω) is sampled at the following rates:

  • (a) f⁰ = 10 samples/Hz
  • (b) f⁰ = 5 samples/Hz

• (c) f⁰ = 4 samples/Hz

• (d) f⁰ = 2.5 samples/Hz

• 8.4-2 The Fourier transform of a signal x(t), bandlimited to B Hz, is X(ω). The signal x(t) is repeated periodically at intervals T, where T = 1.25/B. The resulting signal y(t) is

$$y(t) = \sum_{-\infty}^{\infty} x(t - nT)$$

Show that y(t) can be expressed as

$$y(t) = C_0 + C_1 \cos(1.6\pi Bt + \theta_1)$$

where

$$C_0 = \frac{1}{T}X(0)$$ $$C_1 = \frac{2}{T} \left| X\left(\frac{2\pi}{T}\right) \right|$$

and

$$\theta_1 = \angle X \left( \frac{2\pi}{T} \right)$$

Recall that a bandlimited signal is not timelimited, and hence has infinite duration. The periodic repetitions are all overlapping.

• 8.5-1 For a signal x(t) that is timelimited to 10 ms and has an essential bandwidth of 10 kHz, determine N0, the number of signal samples necessary to compute a power-of-2 FFT with a frequency resolution f⁰ of at least 50 Hz. Explain whether any zero padding is necessary.

• 8.5-2 To compute the DFT of signal x(t) in Fig. P8.5-2, write the sequence xn (for n = 0 to N⁰ − 1) if the frequency resolution f⁰ must be at least 0.25 Hz. Assume the essential bandwidth (the folding frequency) of x(t) to be at least 3 Hz. Do not compute the DFT; just write the appropriate sequence xn.

• 8.5-3 Suppose we want to sample a finite-duration signal x(t) that occupies 0 ≤ t ≤ T.

• (a) Devise a way to use the DFT to help select a suitable sampling rate f^s for signal x(t). [Hint: Consider the characteristics of an oversampled signal’s DFT spectrum.]

• (b) Test the method you devised in part (a) using the signal ^x(t) ⁼ (t−^{1 2} ). Use MAT-LAB to compute any needed DFTs. What value f^s seems reasonable for this signal?

• 8.5-4 Choose appropriate values for N⁰ and T and compute the DFT of the signal e−^t u(t). Use two different criteria for determining the effective bandwidth of e−^t u(t). As the bandwidth, use the frequency at which the amplitude response drops to 1% of its peak value (at ω = 0). Next, use the 99% energy criterion for determining the bandwidth (see Ex. 7.20).

• 8.5-5 Repeat Prob. 8.5-4 for the signal

$$x(t) = \frac{2}{t^2 + 1}$$

• 8.5-6 For the signals x(t) and g(t) represented in Fig. P8.5-6, write the appropriate sequences xn and gn necessary for the computation of the convolution of x(t) and g(t) using DFT. Use T = 1/8.
• 8.5-7 For this problem, interpret the N-point DFT as an N-periodic function of r. To stress this fact, we shall change the notation Xr to X(r). Are the following frequency-domain signals valid DFTs? Answer yes or no. For each valid DFT, determine the size N of the DFT and whether the time-domain signal is real.
  • (a) X(r) = j−π
  • (b) X(r) = sin(r/10)
  • (c) X(r) = sin(πr/10)
  • (d) ^X(r) ⁼ (1+j)/√² r
  • (e) X(r) = #r + π$¹⁰ where #·$¹⁰ denotes the modulo-N operation.
• 8.7-1 MATLAB’s fft command computes the DFT of a vector x assuming the first sample occurs at time n = 0. Given that X = fft(x) has already

been computed, derive a method to correct X to reflect an arbitrary starting time n = n0.

• 8.7-2 Consider a complex signal composed of two closely spaced complex exponentials: x1[n] = ej2πn30/^{100 +} ej2πn33/100. For each of the following cases, plot the length-N DFT magnitude as a function of frequency fr, where fr = r/N.
  • (a) Compute and plot the DFT of x1[n] using 10 samples (0 ≤ n ≤ 9). From the plot, can both exponentials be identified? Explain.
  • (b) Zero-pad the signal from part (a) with 490 zeros and then compute and plot the 500-point DFT. Does this improve the picture of the DFT? Explain.
  • (c) Compute and plot the DFT of x1[n] using 100 samples (0 ≤ n ≤ 99). From the plot, can both exponentials be identified? Explain.
  • (d) Zero-pad the signal from part (c) with 400 zeros and then compute and plot the 500-point DFT. Does this improve the picture of the DFT? Explain.
• 8.7-3 Repeat Prob. 8.7-2, using the complex signal ^x2[n] = ej2πn30/^{100 +}ej2πn31.5/100.
• 8.7-4 Consider a complex signal composed of a dc term and two complex exponentials: y1[n] = ^{1 +} ej2πn30/^{100 +} 0.5 ^∗ ej2πn43/100. For each of the following cases, plot the length-N DFT magnitude as a function of frequency fr, where fr = r/N.
  • (a) Use MATLAB to compute and plot the DFT of y1[n] with 20 samples (0 ≤ n≤19). From the plot, can the two non-dc exponentials be identified? Given the amplitude relation between the two, the lower-frequency peak should be twice as large as the higher-frequency peak. Is this the case? Explain.
  • (b) Zero-pad the signal from part (a) to a total length of 500. Does this improve locating the two non-dc exponential components? Is

the lower-frequency peak twice as large as the higher-frequency peak? Explain.

• (c) MATLAB’s signal-processing toolbox function window allows window functions to be easily generated. Generate a length-20 Hanning window and apply it to y1[n]. Using this windowed function, repeat parts (a) and (b). Comment on whether the window function helps or hinders the analysis.

• 8.7-5 Repeat Prob. 8.7-4, using the complex signal ^y2[n] = ¹+ej2πn30/^{100 +}0.5ej2πn38/100.

• 8.7-6 This problem investigates the idea of zero padding applied in the frequency domain. When asked, plot the length-N DFT magnitude as a function of frequency fr, where fr = r/N.

  • (a) In MATLAB, create a vector x that contains one period of the sinusoid x[n] = cos((π/2)n). Plot the result. How “sinusoidal” does the signal appear to be?
  • (b) Use the fft command to compute the DFT X of vector x. Plot the magnitude of the DFT coefficients. Do they make sense?
  • (c) Zero-pad the DFT vector to a total length of 100 by inserting the appropriate number of zeros in the middle of the vector X. Call this zero-padded DFT sequence Y. Why are zeros inserted in the middle rather than the end? Take the inverse DFT of Y and plot the result. What similarities exist between the new signal y and the original signal x? What are the differences between x and y? What is the effect of zero padding in the frequency domain? How is this type of zero padding similar to zero padding in the time domain?
  • (d) Derive a general modification to the procedure of zero padding in the frequency domain to ensure that the amplitude of the resulting time-domain signal is left unchanged.

• (e) Consider one period of a square wave described by the length-8 vector [1111 −1 −1 −1 −1]. Zero-pad the DFT of this vector to a length of 100, and call the result S. Scale S according to part (d), take the inverse DFT, and plot the result. Does the new time-domain signal s[n] look like a square wave? Explain.

• 8.7-7 The quantized output x^q of a truncating asymmetric converter is given as

$$\textstyle x_\mathrm{q} = \frac{x_\mathrm{max}}{2^{B-1}} \lfloor \frac{x}{x_\mathrm{max}} 2^{B-1} \frac{1}{2} \rfloor$$

Any values outside the 2*^B* allowable levels should be clamped to the nearest level.

• (a) Similar to Fig. 8.31, plot the transfer characteristics for a 3-bit version of this quantizer.
• (b) Apply 3-bit truncating asymmetric quantization to a 1 Hz cosine sampled at f^s = 50 Hz over 1 second. Plot the original signal

x(t), the quantized signal xq(t), and the magnitude spectra of both. How does truncating asymmetric quantization compare to the results of asymmetric rounding quantization shown in Fig. 8.33?

8.7-8 The quantized output x^q of a symmetric truncating converter is given as

$$x_{\mathbf{q}} = \frac{x_{\max}}{2^{B-1}} \left( \lfloor \frac{x}{x_{\max}} 2^{B-1} - \frac{1}{2} \rfloor + \frac{1}{2} \right)$$

Any values outside the 2*^B* allowable levels should be clamped to the nearest level.

• (a) Similar to Fig. 8.31, plot the transfer characteristics for a 3-bit version of this quantizer.
• (b) Apply 3-bit truncating symmetric quantization to a 1 Hz cosine sampled at f^s = 50 Hz over 1 second. Plot the original signal x(t), the quantized signal xq(t), and the magnitude spectra of both. How does truncating symmetric quantization compare to the results of asymmetric rounding quantization shown in Fig. 8.33?

FOURIER ANALYSIS OF DISCRETE-TIME SIGNALS

In Chs. 6 and 7, we studied the ways of representing a continuous-time signal as a sum of sinusoids or exponentials. In this chapter we shall discuss similar development for discrete-time signals. Our approach is parallel to that used for continuous-time signals. We first represent a periodic x[n] as a Fourier series formed by a discrete-time exponential (or sinusoid) and its harmonics. Later we extend this representation to an aperiodic signal x[n] by considering x[n] as a limiting case of a periodic signal with the period approaching infinity.

9.1 DISCRETE-TIME FOURIER SERIES (DTFS)

A continuous-time sinusoid cosωt is a periodic signal regardless of the value of ω. Such is not the case for the discrete-time sinusoid cosn (or exponential ejⁿ). A sinusoid cosn is periodic only if /2π is a rational number. This can be proved by observing that if this sinusoid is N⁰ periodic, then

$$\cos\Omega(n+N_0)=\cos\Omega n$$

This is possible only if

N⁰ = 2πm m integer

Here, both m and N⁰ are integers. Hence, /2π = m/N⁰ is a rational number. Thus, a sinusoid cosn (or exponential ejⁿ) is periodic only if

$$\frac{\Omega}{2\pi} = \frac{m}{N_0}$$

a rational number

When this condition (/2π a rational number) is satisfied, the period N⁰ of the sinusoid cosn is given by

$$N_0 = m\left(\frac{2\pi}{\Omega}\right) \tag{9.1}$$

To compute N0, we must choose the smallest value of m that will make m(2π/) an integer. For example, if = 4π/17, then the smallest value of m that will make m(2π/) = m(17/2) an integer is 2. Therefore,

$$N_0 = m\left(\frac{2\pi}{\Omega}\right) = 2\left(\frac{17}{2}\right) = 17$$

However, a sinusoid cos(0.8n) is not a periodic signal because 0.8/2π is not a rational number.

9.1-1 Periodic Signal Representation by Discrete-Time Fourier Series

A continuous-time periodic signal of period T⁰ can be represented as a trigonometric Fourier series consisting of a sinusoid of the fundamental frequency ω⁰ = 2π/T0, and all its harmonics. The exponential form of the Fourier series consists of exponentials ej0*^t* , e±jω0*^t* , e±j2ω0*^t* , e±j3ω0*^t* ,… .

A discrete-time periodic signal can be represented by a discrete-time Fourier series using a parallel development. Recall that a periodic signal x[n] with period N⁰ is characterized by the fact that

$$x[n] = x[n+N_0]$$

The smallest value of N⁰ for which this equation holds is the fundamental period. The fundamental frequency is ⁰ = 2π/N⁰ rad/sample. An N0-periodic signal x[n] can be represented by a discrete-time Fourier series made up of sinusoids of fundamental frequency ⁰ = 2π/N⁰ and its harmonics. As in the continuous-time case, we may use a trigonometric or an exponential form of the Fourier series. Because of its compactness and ease of mathematical manipulations, the exponential form is preferable to the trigonometric. For this reason, we shall bypass the trigonometric form and go directly to the exponential form of the discrete-time Fourier series.

The exponential Fourier series consists of the exponentials ej0*ⁿ, e±j0ⁿ, e±j20ⁿ, …, e±jn0ⁿ*, …, and so on. There would be an infinite number of harmonics, except for the property proved in Sec. 5.5-1, that discrete-time exponentials whose frequencies are separated by 2π (or integer multiples of 2π) are identical because

$$e^{i(\Omega \pm 2\pi m)n} = e^{i\Omega n} e^{\pm 2\pi mn} = e^{i\Omega n} \qquad m \text{ integer}$$

The consequence of this result is that the rth harmonic is identical to the (r + N0)th harmonic. To demonstrate this, let gn denote the nth harmonic ejn0*ⁿ*. Then

$$g_{r+N_0} = e^{j(r+N_0)\Omega_0 n} = e^{j(r\Omega_0 n + 2\pi n)} = e^{j r\Omega_0 n} = g_r$$

and

$$g_r = g_{r+N_0} = g_{r+2N_0} = \cdots = g_{r+mN_0}$$

m integer

Thus, the first harmonic is identical to the (N⁰ +1)th harmonic, the second harmonic is identical to the (N⁰ +2)th harmonic, and so on. In other words, there are only N⁰ independent harmonics, and their frequencies range over an interval 2π (because the harmonics are separated by ⁰ = 2π/N0). This means that, unlike the continuous-time counterpart, the discrete-time Fourier series has only a finite number (N0) of terms. This result is consistent with our observation in Sec. 5.5-1 that all discrete-time signals are bandlimited to a band from −π to π. Because the harmonics are separated by ⁰ = 2π/N0, there can only be N⁰ harmonics in this band. We also saw that this band can be taken from 0 to 2π or any other contiguous band of width 2π. This means we may

choose the N⁰ independent harmonics ejr0*ⁿ* over 0 ≤ r ≤ N⁰ −1, or over −1 ≤ r ≤ N⁰ −2, or over 1 ≤ r ≤ N0, or over any other suitable choice for that matter. Every one of these sets will have the same harmonics, although in different order.

Let us consider the first choice, which corresponds to exponentials ejr0*ⁿ* for r = 0, 1, 2, … , N⁰ −1. The Fourier series for an N0-periodic signal x[n] consists of only these N⁰ harmonics, and can be expressed as

$$x[n] = \sum_{r=0}^{N_0 - 1} \mathcal{D}_r e^{jr\Omega_0 n} \qquad \Omega_0 = \frac{2\pi}{N_0}$$

To compute coefficients ^Dr, we multiply both sides by ^e−jm0*ⁿ* and sum over ⁿ from ^{n =} 0 to (N^{0 −}1). ^N

$$\sum_{n=0}^{N_0-1} x[n]e^{-jm\Omega_0 n} = \sum_{n=0}^{N_0-1} \sum_{r=0}^{N_0-1} \mathcal{D}_r e^{j(r-m)\Omega_0 n}$$

(9.2)

The right-hand sum, after interchanging the order of summation, results in

$$\sum_{r=0}^{N_0-1} \mathcal{D}_r \left[ \sum_{n=0}^{N_0-1} e^{j(r-m)\Omega_0 n} \right]$$

The inner sum, according to Eq. (8.15) in Sec. 8.5, is zero for all values of r = m. It is nonzero with a value N⁰ only when r = m. This fact means the outside sum has only one term DmN⁰ (corresponding to r = m). Therefore, the right-hand side of Eq. (9.2) is equal to DmN0, and

$$\sum_{n=0}^{N_0-1} x[n]e^{-jm\Omega_0 n} = \mathcal{D}_m N_0$$

and

$$\mathcal{D}_m = \frac{1}{N_0} \sum_{n=0}^{N_0 - 1} x[n] e^{-jm\Omega_0 n}$$

We now have a discrete-time Fourier series (DTFS) representation of an N0-periodic signal x[n] as

$$x[n] = \sum_{r=0}^{N_0 - 1} \mathcal{D}_r e^{jr\Omega_0 n}$$

\n(9.3)

where

$$\mathcal{D}_r = \frac{1}{N_0} \sum_{n=0}^{N_0 - 1} x[n] e^{-j r \Omega_0 n} \qquad \Omega_0 = \frac{2\pi}{N_0}$$

\n(9.4)

Observe that DTFS Eqs. (9.3) and (9.4) are identical (within a scaling constant) to the DFT Eqs. (8.13) and (8.12).† Therefore, we can use the efficient FFT algorithm to compute the DTFS coefficients.

^† If we let ^x[n] = ^N0xk and ^{Dr =} Xr, Eqs. (9.3) and (9.4) are identical to Eqs. (8.13) and (8.12), respectively.

9.1-2 Fourier Spectra of a Periodic Signal ^x[n]

The Fourier series consists of N⁰ components

$$\mathcal{D}_0, \mathcal{D}_1 e^{j\Omega_0 n}, \mathcal{D}_2 e^{j2\Omega_0 n}, \dots, \mathcal{D}_{N_0-1} e^{j(N_0-1)\Omega_0 n}$$

The frequencies of these components are 0, 0, 20, …, (N⁰ − 1)0, where ⁰ = 2π/N0. The amount of the rth harmonic is Dr. We can plot this amount D^r (the Fourier coefficient) as a function of index r or frequency . Such a plot, called the Fourier spectrum of x[n], gives us, at a glance, the graphical picture of the amounts of various harmonics of x[n].

In general, the Fourier coefficients D^r are complex, and they can be represented in the polar form as

$$\mathcal{D}_r = |\mathcal{D}_r|e^{j\angle{\mathcal{D}_r}}$$

The plot of |Dr| versus is called the amplitude spectrum and that of D^r versus is called the angle (or phase) spectrum. These two plots together are the frequency spectra of x[n]. Knowing these spectra, we can reconstruct or synthesize x[n] according to Eq. (9.3). Therefore, the Fourier (or frequency) spectra, which are an alternative way of describing a periodic signal x[n], are in every way equivalent (in terms of the information) to the plot of x[n] as a function of n. The Fourier spectra of a signal constitute the frequency-domain description of x[n], in contrast to the time-domain description, where x[n] is specified as a function of index n (representing time).

The results are very similar to the representation of a continuous-time periodic signal by an exponential Fourier series except that, generally, the continuous-time signal spectrum bandwidth is infinite and consists of an infinite number of exponential components (harmonics). The spectrum of the discrete-time periodic signal, in contrast, is bandlimited and has at most N⁰ components.

PERIODIC EXTENSION OF FOURIER SPECTRUM

We now show that if φ[r] is an N0-periodic function of r, then

$$\sum_{r=0}^{N_0-1} \phi[r] = \sum_{r=(N_0)} \phi[r] \tag{9.5}$$

where r = #N0$ indicates summation over any N⁰ consecutive values of r. Because φ[r] is N⁰ periodic, the same values repeat with period N0. Hence, the sum of any set of N⁰ consecutive values of φ[r] must be the same no matter the value of r at which we start summing. Basically, it represents the sum over one cycle.

To apply this result to the DTFS, we observe that e−jr0*ⁿ* is N⁰ periodic because

$$e^{-jr\Omega_0(n+N_0)} = e^{-jr\Omega_0 n}e^{-j2\pi r} = e^{-jr\Omega_0 n}$$

Therefore, if x[n] is N⁰ periodic, x[n]e−jr0*ⁿ* is also N⁰ periodic. Hence, from Eq. (9.4), it follows that ^Dr is also ^N0 periodic, as is ^Drejr0*ⁿ*. Now, because of Eq. (9.5), we can express Eqs. (9.3) and (9.4) as

$$x[n] = \sum_{r = \langle N_0 \rangle} \mathcal{D}_r e^{jr\Omega_0 n} \tag{9.6}$$

9.1 Discrete-Time Fourier Series (DTFS) 849

and

$$\mathcal{D}_r = \frac{1}{N_0} \sum_{n = \langle N_0 \rangle} x[n] e^{-j r \Omega_0 n} \tag{9.7}$$

If we plot D^r for all values of r (rather than only 0 ≤ r ≤ N⁰ − 1), then the spectrum D^r is N⁰ periodic. Moreover, Eq. (9.6) shows that x[n] can be synthesized not only by the N⁰ exponentials corresponding to 0 ≤ r ≤ N⁰ − 1, but also by any successive N⁰ exponentials in this spectrum, starting at any value of r (positive or negative). For this reason, it is customary to show the spectrum D^r for all values of r (not just over the interval 0 ≤ r ≤ N⁰ − 1). Yet we must remember that to synthesize x[n] from this spectrum, we need to add only N⁰ consecutive components. All these observations are consistent with our discussion in Ch. 5, where we showed that a sinusoid of a given frequency is equivalent to multitudes of sinusoids, all separated by integer multiple of 2π in frequency.

Along the scale, D^r repeats every 2π intervals, and along the r scale, D^r repeats at intervals of N0. Equations (9.6) and (9.7) show that both x[n] and its spectrum D^r are N⁰ periodic and both have exactly the same number of components (N0) over one period.

Equation (9.7) shows that D^r is complex in general, and D−^r is the conjugate of D^r if x[n] is real. Thus,

$$|\mathcal{D}_r| = |\mathcal{D}_{-r}|$$

and $\angle \mathcal{D}_r = -\angle \mathcal{D}_{-r}$

so that the amplitude spectrum |Dr| is an even function , and D^r is an odd function of r (or ). All these concepts will be clarified by the examples to follow. The first example is rather trivial and serves mainly to familiarize the reader with the basic concepts of DTFS.

EXAMPLE 9.1 Discrete-Time Fourier Series of a Sinusoid

Find the discrete-time Fourier series (DTFS) for x[n] = sin 0.1πn (Fig. 9.1a). Sketch the amplitude and phase spectra.

In this case, the sinusoid sin 0.1πn is periodic because /2π = 1/20 is a rational number and the period N⁰ is [see Eq. (9.1)]

$$N_0 = m\left(\frac{2\pi}{\Omega}\right) = m\left(\frac{2\pi}{0.1\pi}\right) = 20m$$

The smallest value of m that makes 20m an integer is m = 1. Therefore, the period N⁰ = 20 so that ⁰ = 2π/N⁰ = 0.1π, and from Eq. (9.6),

$$x[n] = \sum_{r=\langle 20 \rangle} \mathcal{D}_r e^{j0.1\pi rn}$$

where the sum is performed over any 20 consecutive values of r. We shall select the range −10 ≤ r < 10 (values of r from −10 to 9). This choice corresponds to synthesizing x[n] using

Figure 9.1 Discrete-time sinusoid sin 0.1πn and its Fourier spectra.

the spectral components in the fundamental frequency range (−π ≤ <π). Thus,

$$x[n] = \sum_{r=-10}^{9} \mathcal{D}_r e^{j0.1\pi rn}$$

where, according to Eq. (9.7),

$$\mathcal{D}_r = \frac{1}{20} \sum_{n=-10}^{9} \sin 0.1 \pi n e^{-j0.1 \pi r n}$$

=

$$\frac{1}{20} \sum_{n=-10}^{9} \frac{1}{2j} (e^{j0.1 \pi n} - e^{-j0.1 \pi n}) e^{-j0.1 \pi r n}$$

=

$$\frac{1}{40j} \left[ \sum_{n=-10}^{9} e^{j0.1 \pi n (1-r)} - \sum_{n=-10}^{9} e^{-j0.1 \pi n (1+r)} \right]$$

In these sums, r takes on all values between −10 and 9. From Eq. (8.15), it follows that the first sum on the right-hand side is zero for all values of r except r = 1, when the sum is equal to N⁰ = 20. Similarly, the second sum is zero for all values of r except r = −1, when it is equal to N⁰ = 20. Therefore,

$$\mathcal{D}_1 = \frac{1}{2j} \qquad \text{and} \qquad \mathcal{D}_{-1} = -\frac{1}{2j}$$

and all other coefficients are zero. The corresponding Fourier series is given by

$$x[n] = \sin 0.1\pi n = \frac{1}{2j} (e^{j0.1\pi n} - e^{-j0.1\pi n})$$

\n(9.8)

Here the fundamental frequency ⁰ = 0.1π, and there are only two nonzero components:

$$\mathcal{D}_1 = \frac{1}{2j} = \frac{1}{2}e^{-j\pi/2}$$

and $\mathcal{D}_{-1} = -\frac{1}{2j} = \frac{1}{2}e^{j\pi/2}$

Therefore,

$$|\mathcal{D}_1| = |\mathcal{D}_{-1}| = \frac{1}{2} \quad \text{and} \quad \angle \mathcal{D}_1 = -\frac{\pi}{2}, \ \angle \mathcal{D}_{-1} = \frac{\pi}{2}$$

Sketches of D^r for the interval (−10 ≤ r < 10) appear in Figs. 9.1b and 9.1c. According to Eq. (9.8), there are only two components corresponding to r = 1 and −1. The remaining 18 coefficients are zero. The rth component D^r is the amplitude of the frequency r⁰ = 0.1rπ. Therefore, the frequency interval corresponding to −10 ≤ r < 10 is −π ≤ <π, as depicted in Figs. 9.1b and 9.1c. This spectrum over the range −10 ≤ r < 10 (or −π ≤ < π) is sufficient to specify the frequency-domain description (Fourier series), and we can synthesize x[n] by adding these spectral components. Because of the periodicity property discussed in this section, the spectrum D^r is a periodic function of r with period N⁰ = 20. For this reason, we repeat the spectrum with period N⁰ = 20 (or = 2π), as illustrated in Figs. 9.1b and 9.1c, which are periodic extensions of the spectrum in the range −10 ≤ r < 10. Observe that the amplitude spectrum is an even function and the angle or phase spectrum is an odd function of r (or ), as expected.

The result [Eq. (9.8)] is a trigonometric identity and could have been obtained immediately without the formality of finding the Fourier coefficients. We have intentionally chosen this trivial example to introduce the reader gently to the new concept of the discrete-time Fourier series and its periodic nature. The Fourier series is a way of expressing a periodic signal x[n] in terms of exponentials of the form ejr0*ⁿ* and its harmonics. The result in Eq. (9.8) is merely a statement of the (obvious) fact that sin 0.1πn can be expressed as a sum of two exponentials ej0.1π*ⁿ* and e−j0.1π*ⁿ*.

Because of the periodicity of the discrete-time exponentials ejr0*ⁿ*, the Fourier series components can be selected in any range of length N⁰ = 20 (or = 2π). For example, if