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

Observe that the convolution of discrete-time sequences appears in the reconstruction formula [link] , and that [link] parallels continuous-time convolution in [link] with the integral replaced by a sum and the impulse response $h\left(t\right)$ replaced by $h\left[k\right]$ .

The discrete-time counterpart of the Fourier transform is the discrete Fourier transform (DFT).Like the Fourier transform, the DFTdecomposes signals into their constituent sinusoidal components. Like the Fourier transform, the DFT provides anelegant way to understand the behavior of LTI systems by looking at the frequency response(which is equal to the DFT of the impulse response).Like the Fourier transform, the DFT is an invertible, information preserving transformation.

The DFT differs from the Fourier transform in three useful ways. First, it applies to discrete-time sequences,which can be stored and manipulated directly in computers (rather than to analog waveforms, which cannot be directly storedin digital computers). Second, it is a sum rather than an integral, and so is easyto implement in either hardware or software. Third, it operates on a finite data record, rather than anintegration over all time. Given a data record (or vector) $w\left[k\right]$ of length $N$ , the DFT is defined by

for $n=0,1,2,...,N-1$ . For each value $n$ , [link] multiplies each term of the data by a complex exponential, and then sums.Compare this to the Fourier transform; for each frequency $f$ , [link] multiplies each point of the waveform by a complex exponential, and then integrates.Thus $W\left[n\right]$ is a kind of frequency function in the same way that $W\left(f\right)$ is a function of frequency. The next section will make this relationship explicitby showing how $e^{-j(2\pi /N)nk}$ can be viewed as a discrete time sinusoid with frequency proportional to $n$ . Just as a plot of the frequencyfunction $W\left(f\right)$ is called the spectrum of the signal $w\left(t\right)$ , plots of the frequency function $W\left[n\right]$ are called the (discrete) spectrum of the signal $w\left[k\right]$ . One source of confusion is that the frequency $f$ in the Fourier transform can take on any value while the frequenciespresent in [link] are all integer multiples $n$ of a single fundamental with frequency $2\pi /N$ . This fundamental is precisely the sinewave with period equal to the length $N$ of the window over which the DFT is taken. Thus, the frequencies in [link] are constrained to a discrete set; these are the “discrete frequencies” of the section title.

The most common implementation of the DFT is called the fast Fourier transform (FFT), which is an elegant way to rearrange the calculations in [link] so that it is computationally efficient. For all purposes other thannumerical efficiency, the DFT and the FFT are synonymous.

Like the Fourier transform, the DFT is invertible. Its inverse, the IDFT, is defined by

for $k=0,1,2,...,N-1$ . The IDFT takes each point of the frequency function $W\left[n\right]$ , multiplies by a complex exponential, and sums. Compare thiswith the IFT; takes each point of the frequency function $W\left(f\right)$ , multiplies by a complex exponential, and integrates. Thus, the Fourier transform and the DFT translate fromthe time domain into the frequency domain, while the inverse Fourier transform and the IDFT translate from frequencyback into time.