Interpolating a DFT

International Standard Book Number — Click for https://mathworld.wolfram.com/ISBN.html

Click for https://ccrma.stanford.edu/~jos/mdft/Zero_Padding.html

Fast Fourier Transforms (FFT) are fast algorithms for computing the Discrete Fourier Transform (DFT) — Click for https://ccrma.stanford.edu/~jos/mdft/Fast_Fourier_Transform_FFT.html

To downsample a signal by the factor N means to form a new signal consisting of every Nth sample of the original signal. — Click for https://ccrma.stanford.edu/~jos/mdft/Downsampling_Operator.html

Sampling is the process of converting a continuous-time signal into a discrete-time signal. — Click for http://ccrma.stanford.edu/~jos/mdft/Sampling_Theory.html

Matlab is a high-level scripting language for scientific computing — Click for https://ccrma.stanford.edu/~jos/matlab/

The aliased sinc function is obtained from the sinc function by applying the aliasing operator. It arises in digital audio as the spectrum of a sampled rectangular pulse. — Click for https://ccrma.stanford.edu/~jos/sasp/Rectangular_Window.html

The Fourier transform of a signal is a frequency-domain function — Click for https://ccrma.stanford.edu/~jos/mdft/

The spectrum of a signal gives the distribution of signal energy as a function of frequency. — Click for http://ccrma.stanford.edu/~jos/mdft/Example_Applications_DFT.html

Click for https://ccrma.stanford.edu/~jos/mdft/Zero_Padding.html

The Discrete Time Fourier Transform (DTFT) is the appropriate Fourier transform for discrete-time signals of arbitrary length. It can be obtained as the limit of a Discrete Fourier Transform (DFT) as its length goes to infinity. — Click for https://ccrma.stanford.edu/~jos/mdft/Discrete_Time_Fourier_Transform.html

Spectrum analysis of sound is analogous to decomposing white light into its component colors by means of a prism — Click for https://ccrma.stanford.edu/~jos/mdft/Example_Applications_DFT.html

The Discrete Fourier Transform (DFT) computes a discrete-frequency spectrum from a discrete-time signal of finite length. — Click for https://ccrma.stanford.edu/~jos/mdft/

Interpolating a DFT

Starting with a sampled spectrum $X(\omega_k)$ , $k=0,1,\ldots,N-1$ , typically obtained from a DFT, we can interpolate by taking the DTFT of the IDFT which is not periodically extended, but instead zero-padded [264]:^3.8

$\begin{eqnarray*} X(\omega) &=& \hbox{\sc DTFT}(\hbox{\sc ZeroPad}_{\infty}(\hbox{\sc IDFT}_N(X)))\\ &\isdef & \sum_{n=-N/2}^{N/2-1}\left[\frac{1}{N}\sum_{k=0}^{N-1}X(\omega_k) e^{j\omega_k n}\right]e^{-j\omega n}\\ &=& \sum_{k=0}^{N-1}X(\omega_k) \left[\frac{1}{N}\sum_{n=-N/2}^{N/2-1} e^{j(\omega_k-\omega) n}\right]\\ &=& \sum_{k=0}^{N-1}X(\omega_k)\,\hbox{asinc}_N(\omega-\omega_k)\\ &=& \left<X,\hbox{\sc Sample}_N\{\hbox{\sc Shift}_{\omega}(\hbox{asinc}_N)\}\right> \end{eqnarray*}$

(The aliased sinc function, $\hbox{asinc}_N(\omega)$ , is derived in §3.1.) Thus, zero-padding in the time domain interpolates a spectrum consisting of

samples around the unit circle by means of `` $\hbox{asinc}_N$ interpolation.'' This is ideal, time-limited interpolation in the frequency domain using the aliased sinc function as an interpolation kernel. We can almost rewrite the last line above as $X(\omega)=(X\ast \hbox{asinc}_N)_\omega$ , but such an expression would normally be defined only for $\omega=\omega_l=2\pi l/N$ , where

is some integer, since

is discrete while $\hbox{asinc}_N$ is continuous.

Figure F.1 lists a matlab function for performing ideal spectral interpolation directly in the frequency domain. Such an approach is normally only used when non-uniform sampling of the frequency axis is needed. For uniform spectral upsampling, it is more typical to take an inverse FFT, zero pad, then a longer FFT, as discussed further in the next section.

Interpolating a DFT

``Spectral Audio Signal Processing'', by Julius O. Smith III, W3K Publishing, 2011, ISBN 978-0-9745607-3-1. Copyright © 2022-02-28 by Julius O. Smith III Center for Computer Research in Music and Acoustics (CCRMA), Stanford University

``Spectral Audio Signal Processing'', by Julius O. Smith III, W3K Publishing, 2011, ISBN 978-0-9745607-3-1.
Copyright © 2022-02-28 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA), Stanford University