Short-Time Fourier Analysis

Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.341: Discrete-Time Signal Processing Lecture 21 Short-Time Fourier Analysis Reading: Sections 10.1 - 10.5 in Oppenheim, Schafer & Buck (OSB). In the discussion of spectral analysis of deterministic signals, the signal is usually processed by a system as shown in OSB Figure 10.1, where the DFT is applied, possibly with windowing to satisfy its finite-length requirement. In OSB Figure 10.2 are Fourier transforms associated with this system. While the output of this system represents the active signal, in more complex signals such as speech or music where the signal properties change over time, it is clearly more meaningful to refer to the changing frequency content over a smaller time interval rather than over an infinite time interval. The next figure is an example of a speech waveform that possesses high spectral locality in time: Example of a speech waveform illustrating different classes of sounds. The utterance is “should we chase ...” (Reproduced from Chapter 3, A.V. Oppenheim, Applications of Digital Signal Processing.) 1 Traditionally, such analysis is carried out by spectrum analyzers which were banks of filters. We will see later in this lecture how a filter bank carries out this task. Next time we will incorporate the FFT into the filter bank implementation. The Time-Dependent Fourier Transform Also known as the short-time Fourier transform (STFT), the time-dependent Fourier transform (TDFT) of a signal x[n] is defined as X[n, λ) = ∞ � x[n + m]w[m]e−jλm , m=−∞ where w[n] is a window sequence. As time progresses, the signal slides past the fixed window. Here we use λ as the frequency variable to distinguish from the conventional DTFT, and the mixed bracket-parenthesis notation X[n, λ) to notate that n is a discrete variable while λ is a continuous variable. As an illustration of how the window w[n] is positioned relative to the shifted signal, OSB Figure 10.11 shows a linear chirp signal with the window superimposed. The signal being shifted through time is x[n] = cos(ωo n2 ), ωo = 2π × 7.5 × 10−6 . Its instantaneous frequency is 2ωo n (hence the name ‘linear chirp’). w[n] used is a Hamming window of length 400. Over the finite duration of the window, the frequency content of the signal changes only slightly by 400ωo = 2π(0.003). We can see the linearity of the signal’s frequency content from OSB Figure 10.12, a STFT magnitude plot where the vertical axis represents continuous frequency λ and the horizontal axis represents discrete time n. Such a magnitude plot is referred to as a spectrogram. The Effect of the Window From the definition of STFT, we see that X[n, λ) = DTFT{x[n + m]w[m]} = For a fixed n, X[n, λ) = 1 2π � 2π 1 DTFT{x[n + m]} ∗ DTFT{w[m]} 2π ejθn X(ejθ )W (ej(λ−θ) )dθ . 0 This is the convolution between the window W (ejω ) and the shifted input sequence. The mainlobe width of W (ejω ) determines how well the components of the signal frequency spectrum can be resolved and the sidelobe amplitude determines the amount of leakage from these compo­ nents into their neighbors. Again, trade-offs exist when selecting a proper window for short-time Fourier analysis (STFA). OSB Table 7.1 in Section 7.2 quantitatively illustrates such trade-offs. 2 Sampling in Frequency and Time Since λ is continuous, explicitly computing X[n, λ) can be done only for a finite set of sample values. Sampling X[n, λ) at N equally spaced frequencies gives the DFT of the windowed sequence: X[n, k] = X[n, λ)|λ= 2πk = N -point DFT{x[n + m]w[m]} . N If the window is of length L and starts at m = 0, i.e., w[m] = 0 except for 0 ≤ M ≤ L − 1, by properties of the inverse DFT, the windowed sequence can be recovered as long as N ≥ L: N −1 2π 1 � x[n + m]w[m] = X[n, k]ej N km N 0≤M ≤L−1. k=0 The sequence values x[n] within the interval [n, n + L − 1] can be subsequently computed. Given the STFT of a sequence at time no and exact form of the window, we are able to synthesize x[n] for no ≤ n ≤ no + L − 1. This suggests that the frequency sampled STFT is redundant, thus can be further downsampled in time. Such a sampled STFT is defined as X[rR, k] = X[rR, L−1 � 2π 2πk ]= x[rR + m]w[m]e−j N km , N m=0 where −∞ < r < ∞, 0 ≤ k ≤ N − 1, and R is the sampling interval in the time domain. Exact reconstruction of the signal is possible if R ≤ L ≤ N . An alternative notation for X[rR, k] is Xr [k]. OSB Figure 10.15 shows the region of support for X[n, λ) in the [n, λ)-plane as lines and for Xr [k] = X[rR, k] as discrete grid points. The amount R by which the window slides from block to block depends on how fast the frequency of the signal changes, and the length L of the window should be chosen according to the desired frequency resolution (long window), or time resolution (short window). Modulated Filter Banks for Short-Time Fourier Analysis A common method for short-time Fourier analysis before the development of the FFT is to use a filter bank in which each filter has the same frequency response shape, but different center frequencies. An example is shown below where the prototype lowpass filter is shifted N − 1 times to obtain a bank of N filters with complex impulse responses. 3 In this system, the output yk [n] from filter hk [n] to the downsampler satisfies the following equation: yk [n] = ∞ � ejωk r h0 [r]x[n − r] = r=−∞ ∞ � e−jωk r h0 [−r]x[n + r] r=−∞ = DTFT{x[n + r]h0 [−r]}|ω=ωk . Let the window sequence be w[m] = h0 [−m], then yk [n] = X[n, λ)|ω=ωk . This is the STFT of x[n] sampled at ω = ωk . If h0 [−r] is N -point long, and ωk = yk [n] = X[n, k] = N -point DFT{x[n + r]h0 [−r]} . 4 2πk N , then The downsampler with rate R removes time redundancies in yk [n] to obtain vk [n] = X[nR, k]. Because of the existence of the downsampler, a polyphase implementation for this filter bank is possible, we will explore in detail how this is carried out in the next lecture. In typical spectral analysis of filter banks, the filter frequency spacing ωk is chosen to be approximately equal to the filter bandwidth. Also, we typically look at the magnitude of the outputs only, although the filter impulse responses are complex. OSB Figure 10.16 shows the frequency response for sets of bandpass filters obtained from rectangular and Kaiser windows. The Kaiser window has narrower sidelobes but a wider mainlobe. In either case, the filter responses overlap significantly and are of infinitely length. Nonetheless, it can be shown that time aliasing of the reconstructed signal does not occur when inverting the time and frequency sampled TDFT, hence exact reconstruction is possible. Problem 10.40 in OSB illustrates this point. In addition to using filter banks, the short-time Fourier analysis can also be performed with only one filter h0 [n] by sliding the signal x[n] in frequency, i.e., modulate x[n] with ejωk n for different ωk values and filter the modulated signal with h0 [n] to obtain yk [n]. The short-time Fourier transform plays a significant role in discrete-time processing of speech. For a much more detailed discussion of this topic, see OSB Section 10.5 and Chapter 3 Digital processing of Speech, A. V. Oppenheim, Applications of Digital Signal Processing, downloadable through the MIT RLE Digital Signal Processing Group web site at http://www.rle.mit.edu/dspg/documents/DigitalSpeech.pdf 5