Question 9.2: (a) Using a 10-point DFT, i.e. N=10, show how Eq. (9.45) can......

Part (a)
Figure 9.5, (a), (b) and (c) illustrate a possible, but inefficient, implementation of Eq. (9.45). The sampled values x_{0}, x_{1}, x_{2}, . . . x_{9} are shown at (a) as dots. Since the whole period, from j = 0 to 10, is 0.5 s long, these values are at 0.05 s intervals. Writing Eq. (9.45) in the form:

discretized values of the functions \cos (2\pi jk/N)  \mathrm{and}  -\sin (2\pi jk/N) are shown in Fig. 9.5 at (b) and (c), respectively, for k = 3 in this case.

From Eq. (B), the real part of x_{j}e^{-\mathrm{i}(\frac{2\pi jk}{N} )}, for k = 3, is given by multiplying together corresponding discrete values in Fig. 9.5, at (a) and (b), for all values of j, from 0 to 9, summing the products, and finally multiplying by 1/N. A similar process, multiplying the discrete values in (a) and (c), summing and multiplying by 1/N gives the imaginary part of X_{k}.

These operations are shown in Table 9.1, from which the real and imaginary parts of X_{3} ( i.e. X_{k}  \mathrm{for}  k = 3) are seen to be 0.05 and 0, respectively.

Part (b)
Repeating Table 9.1 for all the other values of k, we can produce Table 9.2, showing the real and imaginary parts of X_{k} for k = 0, 1, 2, . . . , 9. For comparison, the Fourier coefficients used to calculate the original values of x{j} are also shown.

We can convert the discrete values of k to discrete frequencies, f, in hertz, using Eq. (9.43a): f = k/T (k = 0, 1, 2 , . . . , N – 1). Since T = 0.5 s, then f = 2k.

It can be seen from Table 9.2 that the DFT results are, in fact, related to the Fourier coefficients, a_{n}  \mathrm{and}  b_{n}, where the latter exist, as predicted by Eq. (9.47b):

It can also be seen from Table 9.2, however, that the DFT has introduced ‘spurious’ values of X_{k} at values of k greater than 5, or N/2, corresponding to f > 10 Hz. These have been produced by the DFT itself, and have nothing to do with the original input data, which clearly contained no components above n = k = 4. This phenomenon is discussed next.
Part (c)
The spurious values of X_{k} can be explained by Fig. 9.6(a) and (b). These show (as solid lines) the multiplying functions\cos (2\pi jk/N)  \mathrm{and}  -\sin (2\pi jk/N) , respectively, for k = 7. When sampled at j = 0, 1, 2, . . . , 9, however, these become aliased, and the sampled values, joined by a dotted line, are, for the cosine function, Fig. 9.6(a), precisely the same as those shown in Fig. 9.5(b), which were computed for k = 3. The DFT cannot distinguish between the genuine cosine function for k = 3 and the aliased cosine function for k = 7, and so produces the same output.

The ( -sine) function, for k = 7, as shown in Fig. 9.6(b), is similarly aliased, but in this case it will be seen that the sampled version, also joined by a dotted line, is reversed in sign with respect to Figure 9.5(c).

The same effect occurs for all values of k greater than five, in this example, or, in general, for values of k greater than N/2, and the overall effect is that

In Table 9.2 it will be noticed that all the DFT results follow this pattern. The effect is intentional, and is simply due to the way the standard complex DFT is defined.

The indicated components at and below k = N/2 are correct, but the coefficients above k = N/2 are spurious, and must not be interpreted as Fourier coefficients at the frequencies indicated. They are there for good reason, however, and the following should be noted:

(1) The IDFT, in the form of Eq. (9.46), needs the ‘spurious’ values of X_{k} in order to reproduce the time series x_{j} correctly.

(2) As shown in Section 9.1.3, in the two-sided complex Fourier series, the components at negative frequencies are the complex conjugates of those at the corresponding positive frequencies, which is just what the ‘spurious’ components are, except that they appear at values of k that are N points to the right of their correct positions.

It can be seen that the standard DFT deliberately uses aliasing to make it reversible, but it is the cosine and sine multiplying functions that are aliased, not the input data, and nothing is lost in the process. Aliasing of data, as discussed in Section 9.3, is different, and a potentially serious problem.