Discrete-Time Fourier Transform The Discrete-Time Fourier Transform (DTFT) is the primary theoretical tool for understanding the frequency content of a discrete-time (sampled) signal. The DTFT is defined as X ω n x n ω n The inverse DTFT (IDTFT) is defined by an integral formula, because it operates on a continuous-frequency DTFT spectrum: x n 1 2 ω X k ω n The DTFT is very useful for theory and analysis, but is not practical for numerically computing a spectrum digitally, because infinite time samples means infinite computation infinite delay The transform is continuous in the discrete-time frequency, ω For practical computation of the frequency content of real-world signals, the Discrete Fourier Transform (DFT) is used.

Discrete Fourier Transform The DFT transforms N samples of a discrete-time signal to the same number of discrete frequency samples, and is defined as X k n 0 N 1 x n 2 π n k N The DFT is invertible by the inverse discrete Fourier transform (IDFT): x n 1 N k N 1 0 X k 2 n k N The DFT and IDFT are a self-contained, one-to-one transform pair for a length-N discrete-time signal. (That is, the DFT is not merely an approximation to the DTFT as discussed next.) However, the DFT is very often used as a practical approximation to the DTFT.

Relationships Between DFT and DTFT

DFT and Discrete Fourier Series The DFT gives the discrete-time Fourier series coefficients of a periodic sequence ( x n x n N ) of period N samples, or X ω 2 N X k δ ω 2 k N as can easily be confirmed by computing the inverse DTFT of the corresponding line spectrum: x n 1 2 ω 2 N X k δ ω 2 k N ω n 1 N k N 1 0 X k 2 n k N IDFT X k x n The DFT can thus be used to exactly compute the relative values of the N line spectral components of the DTFT of any periodic discrete-time sequence with an integer-length period.

DFT and DTFT of finite-length data When a discrete-time sequence happens to equal zero for all samples except for those between 0 and N1, the infinite sum in the DTFT equation becomes the same as the finite sum from 0 to N1 in the DFT equation. By matching the arguments in the exponential terms, we observe that the DFT values exactly equal the DTFT for specific DTFT frequencies ω k 2 k N . That is, the DFT computes exact samples of the DTFT at N equally spaced frequencies ω k 2 k N , or X ω k 2 k N n ∞ ∞ x n ω k n n 0 N 1 x n 2 π n k N X k

DFT as a DTFT approximation In most cases, the signal is neither exactly periodic nor truly of finite length; in such cases, the DFT of a finite block of N consecutive discrete-time samples does not exactly equal samples of the DTFT at specific frequencies. Instead, the DFT gives frequency samples of a windowed (truncated) DTFT X ^ ω k 2 k N n N 1 0 x n ω k n n ∞ ∞ x n w n ω k n X k where w n 1 0 n N 0 else Once again, X k exactly equals X ω k a DTFT frequency sample only when n n 0 N 1 x n 0

Relationship between continuous-time FT and DFT The goal of spectrum analysis is often to determine the frequency content of an analog (continuous-time) signal; very often, as in most modern spectrum analyzers, this is actually accomplished by sampling the analog signal, windowing (truncating) the data, and computing and plotting the magnitude of its DFT. It is thus essential to relate the DFT frequency samples back to the original analog frequency. Assuming that the analog signal is bandlimited and the sampling frequency exceeds twice that limit so that no frequency aliasing occurs, the relationship between the continuous-time Fourier frequency Ω (in radians) and the DTFT frequency ω imposed by sampling is ω Ω T where T is the sampling period. Through the relationship ω k 2 k N between the DTFT frequency ω and the DFT frequency index k, the correspondence between the DFT frequency index and the original analog frequency can be found: Ω 2 k N T or in terms of analog frequency f in Hertz (cycles per second rather than radians) f k N T for k in the range k between 0 and N 2 . It is important to note that k N 2 1 N 1 correspond to negative frequencies due to the periodicity of the DTFT and the DFT. In general, will DFT frequency values X k exactly equal samples of the analog Fourier transform X a at the corresponding frequencies? That is, will X k X a 2 k N T ? In general, NO. The DTFT exactly corresponds to the continuous-time Fourier transform only when the signal is bandlimited and sampled at more than twice its highest frequency. The DFT frequency values exactly correspond to frequency samples of the DTFT only when the discrete-time signal is time-limited. However, a bandlimited continuous-time signal cannot be time-limited, so in general these conditions cannot both be satisfied. It can, however, be true for a small class of analog signals which are not time-limited but happen to exactly equal zero at all sample times outside of the interval n 0 N 1 . The sinc function with a bandwidth equal to the Nyquist frequency and centered at t 0 is an example.

Zero-Padding If more than N equally spaced frequency samples of a length-N signal are desired, they can easily be obtained by zero-padding the discrete-time signal and computing a DFT of the longer length. In particular, if LN DTFT samples are desired of a length-N sequence, one can compute the length- LN DFT of a length- LN zero-padded sequence z n x n 0 n N 1 0 N n L N 1 X w k 2 k L N n N 1 0 x n 2 k n L N n L N 1 0 z n 2 k n L N DFT L N z n Note that zero-padding interpolates the spectrum. One should always zero-pad (by about at least a factor of 4) when using the DFT to approximate the DTFT to get a clear picture of the DTFT. While performing computations on zeros may at first seem inefficient, using FFT algorithms, which generally expect the same number of input and output samples, actually makes this approach very efficient. shows the magnitude of the DFT values corresponding to the non-negative frequencies of a real-valued length-64 DFT of a length-64 signal, both in a "stem" format to emphasize the discrete nature of the DFT frequency samples, and as a line plot to emphasize its use as an approximation to the continuous-in-frequency DTFT. From this figure, it appears that the signal has a single dominant frequency component.

Spectrum without zero-padding Stem plot Line Plot Magnitude DFT spectrum of 64 samples of a signal with a length-64 DFT (no zero padding) Zero-padding by a factor of two by appending 64 zero values to the signal and computing a length-128 DFT yields . It can now be seen that the signal consists of at least two narrowband frequency components; the gap between them fell between DFT samples in , resulting in a misleading picture of the signal's spectral content. This is sometimes called the picket-fence effect, and is a result of insufficient sampling in frequency. While zero-padding by a factor of two has revealed more structure, it is unclear whether the peak magnitudes are reliably rendered, and the jagged linear interpolation in the line graph does not yet reflect the smooth, continuously-differentiable spectrum of the DTFT of a finite-length truncated signal. Errors in the apparent peak magnitude due to insufficient frequency sampling is sometimes referred to as scalloping loss.

Spectrum with factor-of-two zero-padding Stem plot Line Plot Magnitude DFT spectrum of 64 samples of a signal with a length-128 DFT (double-length zero-padding) Zero-padding to four times the length of the signal, as shown in , clearly shows the spectral structure and reveals that the magnitude of the two spectral lines are nearly identical. The line graph is still a bit rough and the peak magnitudes and frequencies may not be precisely captured, but the spectral characteristics of the truncated signal are now clear.

Spectrum with factor-of-four zero-padding Stem plot Line Plot Magnitude DFT spectrum of 64 samples of a signal with a length-256 zero-padded DFT (four times zero-padding) Zero-padding to a length of 1024, as shown in yields a spectrum that is smooth and continuous to the resolution of the computer screen, and produces a very accurate rendition of the DTFT of the truncated signal.

Spectrum with factor-of-sixteen zero-padding Stem plot Line Plot Magnitude DFT spectrum of 64 samples of a signal with a length-1024 zero-padded DFT. The spectrum now looks smooth and continuous and reveals all the structure of the DTFT of a truncated signal. The signal used in this example actually consisted of two pure sinusoids of equal magnitude. The slight difference in magnitude of the two dominant peaks, the breadth of the peaks, and the sinc-like lesser side lobe peaks throughout frequency are artifacts of the truncation, or windowing, process used to practically approximate the DFT. These problems and partial solutions to them are discussed in the following section.

Effects of Windowing Applying the DTFT multiplication property X ω k n ∞ ∞ x n w n ω k n 1 2 X ω k W ω k we find that the DFT of the windowed (truncated) signal produces samples not of the true (desired) DTFT spectrum X ω , but of a smoothed verson X ω W ω . We want this to resemble X ω as closely as possible, so W ω should be as close to an impulse as possible. The window w n need not be a simple truncation (or rectangle, or boxcar) window; other shapes can also be used as long as they limit the sequence to at most N consecutive nonzero samples. All good windows are impulse-like, and represent various tradeoffs between three criteria: main lobe width: (limits resolution of closely-spaced peaks of equal height) height of first sidelobe: (limits ability to see a small peak near a big peak) slope of sidelobe drop-off: (limits ability to see small peaks further away from a big peak) Many different window functions have been developed for truncating and shaping a length-N signal segment for spectral analysis. The simple truncation window has a periodic sinc DTFT, as shown in . It has the narrowest main-lobe width, 2 N at the -3 dB level and 4 N between the two zeros surrounding the main lobe, of the common window functions, but also the largest side-lobe peak, at about -13 dB. The side-lobes also taper off relatively slowly.

Rectangular window Magnitude of boxcar window spectrum Length-64 truncation (boxcar) window and its magnitude DFT spectrum The Hann window (sometimes also called the hanning window), illustrated in , takes the form w n 0.5 0.5 2 n N 1 for n between 0 and N 1 . It has a main-lobe width (about 3 N at the -3 dB level and 8 N between the two zeros surrounding the main lobe) considerably larger than the rectangular window, but the largest side-lobe peak is much lower, at about -31.5 dB. The side-lobes also taper off much faster. For a given length, this window is worse than the boxcar window at separating closely-spaced spectral components of similar magnitude, but better for identifying smaller-magnitude components at a greater distance from the larger components.

Hann window Magnitude of Hann window spectrum Length-64 Hann window and its magnitude DFT spectrum The Hamming window, illustrated in , has a form similar to the Hann window but with slightly different constants: w n 0.538 0.462 2 n N 1 for n between 0 and N 1 . Since it is composed of the same Fourier series harmonics as the Hann window, it has a similar main-lobe width (a bit less than 3 N at the -3 dB level and 8 N between the two zeros surrounding the main lobe), but the largest side-lobe peak is much lower, at about -42.5 dB. However, the side-lobes also taper off much more slowly than with the Hann window. For a given length, the Hamming window is better than the Hann (and of course the boxcar) windows at separating a small component relatively near to a large component, but worse than the Hann for identifying very small components at considerable frequency separation. Due to their shape and form, the Hann and Hamming windows are also known as raised-cosine windows.

Hamming window Magnitude of Hamming window spectrum Length-64 Hamming window and its magnitude DFT spectrum Standard even-length windows are symmetric around a point halfway between the window samples N 2 1 and N 2 . For some applications such as time-frequency analysis, it may be important to align the window perfectly to a sample. In such cases, a DFT-symmetric window that is symmetric around the N 2 -th sample can be used. For example, the DFT-symmetric Hamming window is w n 0.538 0.462 2 n N . A DFT-symmetric window has a purely real-valued DFT and DTFT. DFT-symmetric versions of windows, such as the Hamming and Hann windows, composed of few discrete Fourier series terms of period N, have few non-zero DFT terms (only when not zero-padded) and can be used efficiently in running FFTs.The main-lobe width of a window is an inverse function of the window-length N ; for any type of window, a longer window will always provide better resolution. Many other windows exist that make various other tradeoffs between main-lobe width, height of largest side-lobe, and side-lobe rolloff rate. The Kaiser window family, based on a modified Bessel function, has an adjustable parameter that allows the user to tune the tradeoff over a continuous range. The Kaiser window has near-optimal time-frequency resolution and is widely used. A list of many different windows can be found here. shows 64 samples of a real-valued signal composed of several sinusoids of various frequencies and amplitudes.

64 samples of an unknown signal shows the magnitude (in dB) of the positive frequencies of a length-1024 zero-padded DFT of this signal (that is, using a simple truncation, or rectangular, window).

Magnitude (in dB) of the zero-padded DFT spectrum of the signal in using a simple length-64 rectangular window From this spectrum, it is clear that the signal has two large, nearby frequency components with frequencies near 1 radian of essentially the same magnitude. shows the spectral estimate produced using a length-64 Hamming window applied to the same signal shown in .

Magnitude (in dB) of the zero-padded DFT spectrum of the signal in using a length-64 Hamming window The two large spectral peaks can no longer be resolved; they blur into a single broad peak due to the reduced spectral resolution of the broader main lobe of the Hamming window. However, the lower side-lobes reveal a third component at a frequency of about 0.7 radians at about 35 dB lower magnitude than the larger components. This component was entirely buried under the side-lobes when the rectangular window was used, but now stands out well above the much lower nearby side-lobes of the Hamming window. shows the spectral estimate produced using a length-64 Hann window applied to the same signal shown in .

Magnitude (in dB) of the zero-padded DFT spectrum of the signal in using a length-64 Hann window The two large components again merge into a single peak, and the smaller component observed with the Hamming window is largely lost under the higher nearby side-lobes of the Hann window. However, due to the much faster side-lobe rolloff of the Hann window's spectrum, a fourth component at a frequency of about 2.5 radians with a magnitude about 65 dB below that of the main peaks is now clearly visible.This example illustrates that no single window is best for all spectrum analyses. The best window depends on the nature of the signal, and different windows may be better for different components of the same signal. A skilled spectrum analysist may apply several different windows to a signal to gain a fuller understanding of the data.