The spectrum of a signal is given by its Fourier transform. In order to compute it, we need all the samples of the signal. Therefore, the spectrum is a characteristic of the whole signal. However, in many applications (e.g., in speech processing) one needs to find the spectrum of a short section of the signal. In order to do this, we define a length- \(N\) sliding window \(x_{\mathrm{i}}(n)\) of the signal \(x(n)\) as

\[x_{\mathrm{i}}(n)=x(n+i-N+1) \text {, for }-\infty

That is, we take \(N\) samples of \(x(n)\) starting from position \(i\) backwards. We then define the short-time spectrum of \(x(n)\) at the position \(i\) as the DFT of \(x_{\mathrm{i}}(n)\); that is:

\[X(k, i)=\sum_{n=0}^{N-1} x_{\mathrm{i}}(n) W_{N}^{k n}, \text { for } 0 \leq k \leq N-1, \text { for }-\infty

Therefore, we have, for each frequency \(k\), a signal \(X(k, i),-\infty

(a) Show that the short-time spectrum can be efficiently computed with a bank of \(N\) IIR filters having the following transfer function for frequency \(k\) :

\[H_{k}(z)=\frac{1-z^{-N}}{W_{N}^{k}-z^{-1}}, \quad 0 \leq k \leq N-1 .\]

(b) Compare, in terms of the number of complex additions and multiplications, the complexity of the computations of the short-time spectrum using the above formula for \(H_{k}(z)\) with that using the FFT algorithm.

(c) Discuss whether it is advantageous or not, in terms of arithmetic operations, to use the above formula for \(H_{k}(z)\) to compute a linear convolution using the overlap-and-add method. Repeat this item for the overlap-and-save method.
A good coverage of recursive computations of sinusoidal transforms can be found in Liu et al. (1994).