0.6 Digital filtering and the dft  (Page 4/13)

To see how this works, consider the first few columns. $C_0$ is a vector of all ones; it is the zero frequency sinusoid, or DC. $C_1$ is more interesting. The $i^{th}$ element of $C_1$ is $e^{j2i\pi /N}$ , which means that as $i$ goes from 0 to $N-1$ , the exponential assumes $N$ uniformly spaced points around the unit circle. This is clearer in polar coordinates, where the magnitude isalways unity and the angle is $2i\pi /N$ radians. Thus, $C_1$ is the lowest frequency sinusoid that can be represented (other than DC); it is the sinusoid that fitsexactly one period in the time interval $N{T}_s$ , where $T_s$ is the distance in time between adjacent samples. $C_2$ is similar, except that the $i^{th}$ element is $e^{j4i\pi /N}$ . Again, the magnitude is unity and the phase is $4i\pi /N$ radians. Thus, as $i$ goes from 0 to $N-1$ , the elements are $N$ uniformly spaced points which go around the circle twice.Thus, $C_2$ has frequency twice that of $C_1$ , and it represents a complex sinusoid that fits exactly two periods into thetime interval $N{T}_s$ . Similarly, $C_n$ represents a complex sinusoid of frequency $n$ times that of $C_1$ ; it orbits the circle $n$ times and is the sinusoid that fits exactly $n$ periods in the time interval $N{T}_s$ .

One subtlety that can cause confusion is that the sinusoids in $C_i$ are complex valued, yet, most signals of interest are real. Recall from Euler's identities [link] and [link] that the real-valued sine and cosine can each be written as a sum of two complex valued exponentials that have exponents with opposite signs.The DFT handles this elegantly. Consider $C_{N-1}$ . This is

which can be rewritten as

since $e^{-j2\pi }=1$ . Thus, the elements of $C_{N-1}$ are identical to the elements of $C_1$ , except that the exponents have the opposite sign, implying that the angle of the $i^{th}$ entry in $C_{N-1}$ is $-2i\pi /N$ radians. Thus, as $i$ goes from 0 to $N-1$ , the exponential assumes $N$ uniformly spaced points around the unit circle, in the opposite direction from $C_1$ . This is the meaning of what might be interpreted as “negative frequencies”that show up when taking the DFT. The complex exponential proceeds in a (negative) clockwise manner around the unit circle, ratherthan in a (positive) counterclockwise direction. But it takes both to make a real valued sine or cosine, as Euler's formula shows. For real valued sinusoids of frequency $2\pi n/N$ , both $W\left[n\right]$ and $W[N-n]$ are nonzero and equal in magnitude. Since $W\left[n\right]=W^{*}[N-n]$ by the discrete version of the symmetry property [link] , the magnitudes are equal but the phases have opposite signs.

Using the dft

Fortunately, M atlab makes it easy to do spectral analysis with the DFT by providing a number of simple commandsthat carry out the required calculations and manipulations. It is not necessary toprogram the sum [link] or the matrix multiplication [link] . The single line commands W = fft ( w ) and w = ifft ( W ) invoke efficient FFT (and IFFT) routines when possible, and relatively inefficientDFT (and IDFT) calculations otherwise. The numerical idiosyncrasies are completely transparent, with one annoying exception.In M atlab , all vectors, including W and w , must be indexed from 1 to $N$ instead of from 0 to $N-1$ .