Hi, I would like some help on where to begin and how to approach this question p

Question

Hi, I would like some help on where to begin and how to approach this question please, because I do not fully understand what the question is asking thankyou

Determine an expression for the frequency spectrum (based on DTFT) of a signal in terms of its DFT coefficients and using this relationship show that if I take the N-point DFT of a signal, set the coefficients corresponding to some frequencies to zero, and taken an IDFT to recover a time domain signal - I have not implemented a brickwall filter (i.e., an ideal filter with unity gain in the pass band, no transition band and a zero gain in the stop band).

Explanation / Answer

Let us determine how many samples are involved here. The number of samples in the time domain (of each period) is N0 = T0 T The number of samples in the frequency domain of each period is N 0 0 = Fs F0 = 1/T 1/T0 = N0.

fk = Tf[k] = Tf(kT) = T0 N0 f(kT). Fr = N X01 k=0 fke jr0k = N X01 k=0 fke j2rk/N0

fk = 1 N0 N X01 r=0 Fre jr0k = 1 N0 N X01 r=0 Fre j2rk/N0 .

If, in addition, the signal f(t) that we are dealing with is not, in fact timelimited, but we must for reasons of practicality deal with a time-limited version, we must perform some truncation. This truncation leads to spectral leakage. This also causes aliasing (creating higher spectral components than might have been in the original signal.) The spectral leakage can be reduced by increasing the window width (longer data set). This increases T0, which in turn reduces F0. (Note that F0 determines the frequency resolution.) Also observe that by this sampling property, we are getting only a partial view of the spectrum. A true spectral peak might not lie right on one of the sample values. This can be mitigated by sampling more finely (decrease F0, meaning increase T0, meaning increase N0.) Let f[k] be a discrete-time sequence, possibly obtained from a continuous-time signal by sampling, say f[k] = f(kT). Note that we are using k as the discrete time index. Suppose that we have N0 samples of the signal, where N0 is some number that we choose. (As a point for future reference, the number N0 is commonly chosen to be a power of 2, since this works most efficiently for most FFT routines.) Following the book’s notation, let

(This is the maximum representable frequency.) The number of points in the DFT can be written as N0 = T0 T , where T0 relates to the sampling rate in the frequency domain, and T relates to the sampling rate in the time domain. Observe that to increase the frequency resolution, the number of points of data N0 must be increased. We can increase N0 and improve the frequency resolution by increasing T0 (taking more data), which amounts to taking samples closer together in frequency, f0 = 1/T0, or by taking samples faster in time (increasing the sampling rate). Note: The book defined the transform in terms of fk = Tf(kT). In practice, the FFT routines simply deal with the data fk; they don’t worry about whether it is scaled or not. Since the effect of the scaling by T is to simply scale the transform, in applications it is not common to worry about the scaling either. Example 1 A signal f(t) has a duration of 2 ms and an essential bandwidth of 10 kHz. (What is its absolute bandwidth?) We want to have a spectral resolution of 100 Hz in the DFT. Determine N0, the number of points in the DFT. By the sampling theorem, we must sample at least double the highest frequency, which is B = 10000. Let Fs = 2B = 20000 samples/sec. The resolution is F0 = 100 Hz. The signal duration is T0 = 1/F0 = 10 ms. Here is an interesting thing: to get the spectral resolution we need, we need 10 ms of data, when in fact the signal only lasts for 2 ms. The solution is to take the 2 ms of data, then pad the rest with zeros. This is called zero padding. Then N0 = fs f0 = 200 In practice, we would probably want N0 to be a power of 2, so N0 = 256 is a better choice. This could be obtained by decreasing T, which would reduce aliasing, or increasing T0, which would increase the resolution. Note that zero padding cannot replace any information that is not already present in the signal. It simply refines the sampling of the spectrum that is already present.

Convolution using the DFT We have seen the convolution theorem over and over: convolution in time is the transform of multiplication in the frequency domain. By numerically computing the transform using the DFT, we can compute convolutions of sequences. There are some issues to be very careful of, however, since the DFT imposes certain requirements on the signals. We will worry later about this. For the moment, consider the computational complexity. Suppose I have a sequence x of N points and another sequence y also of N points. We know that the convolution will have 2N 1 points. Computation of each of the outputs requires approximately N2 computations. The overall complexity for computing convolution is therefore O(N2 ). But here is the neat thing: We compute the DFT of x and the DFT of y, multiply the points in the frequency domain, then transform back: Xr = DFT(xk) Yr = DFT(yk) Zr = XrYr zk = IDFT(Zr) This sure seems like the long way around the barn! But, consider the number of computations if we do the DFTs using FFTs: Each transform requires O(N log2 N) operations, the multiplication is O(N), and the inverse transform is O(N log2 N). The overall computation is O(N log2 N). (That’s how orders are computed!). So it requires fewer computations (by far!) than straightforward convolution, at least of N is large enough. This is, in fact, the way Matlab computes its convolutions

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.