Music 320 lab 8
November 320, 2000

Fourier transform: towards applications

discussion: moving from the mathematical description of the DFT to 
  practical spectrum analysis and applications

Fast Fourier Transform (FFT):

  special case of the DFT which can be computed more quickly
  only available for signals of length radix 2
    (that is, powers of 2: 2,4,8,16,...,1024, 2048, 4096....)
  "divide-and-conquer" algorithm: breaks signal into halves,
    breaks halves into halves, ....
  note that Matlab only implements the FFT, not the DFT
    non-radix 2 lengths are automatically zero-padded to the next
      available radix 2 length, computed, and resampled to the 
      original length

zero-padding:

  improves our ability to interpret spectra
  peaks (and window transforms) become easier to resolve
  zero-padding in time <-> ideal bandlimited interpolation in frequency
  remember that zero-padding does not alter definition of spectrum;
    it only improves our ability to resolve that spectrum (i.e., there
    are more points outlining the same curve)

  [Matlab examples]

Short-Time Fourier Transform (STFT):

  enables spectrogram, sinusoidal modelling, FFT-based convolution,
    etc.

  analysis of time-varying signals:
    we may compute the Fourier transform of a very long signal
      (for instance, a recorded piece of music)
    however, this is undesirable -
      - extremely expensive to compute
      - gives only the average spectrum over the entire signal

    instead, we prefer to segment a signal and analyze each segment
      separately
      - window a segment of the time-domain signal
        (this is unavoidable -- any truncation is equivalent to
        rectangular windowing; so, choose a window with the most
        desirable transform with the application)
      - zeropad the segment
      - calculate the FFT of the zeropadded segment
      - "hop" to the next segment (the hop size is typically *not*
        the window length)
      - repeat the process for the next segment

  constant overlap-add (COLA)
    if we wish to reconstruct our time-domain signal from these spectral
      frames, our windows must obey the constant overlap-add constraint
    the hopped windows must sum to a constant:
      summation over m of w(n-mR) = 1
      where m is the window index, n is the time index, R is the hop size,
        and w(n) the window function
    happily, many of our typical windows can be made to obey the COLA
      constraint:
        rectangular window at R=M, R=M/2
        Bartlett window at R=M/2
        Hamming window at R=M/2, R=M/4
        any window with R=1("sliding FFT")

        [Matlab examples]

  spectrogram as an implementation/visualization of the STFT
    frequency resolution: larger n = more analysis bins = more resolution
      resolution is also affected by the window transform: 
        how many bins wide is the mainlobe?
    time-frequency tradeoff: longer n for better spectral resolution means
      less certainty about time location
        analog to the Heisenberg uncertainty principle    
    short hop sizes (R