Resampling¶

Context¶

Let the discrete time signal $x_1[n]$ be the samples of a continuous time signal $x(t)$ sampled at some interval $T_1$:

\[ x_1[n] = x(t - n \cdot \frac{1}{T_1}) \]

We want to convert $x_1[n]$ to $x_2[n]$, where $x_2[n]$ is the samples of $x(t)$, but sampled at a different interval $T_2$.

Here we assume $\frac{T_1}{T_2}$ is rational, in other words, there exists some integer $L$ and $M$ that

\[ \frac{T_1}{T_2} = \frac{L}{M} \]

For example, we may want to convert a WAV data of 44100Hz sampling rate to 48000Hz sampling rate.

Problem¶

How do we convert $x_1[n]$ to $x_2[n]$?

Solution¶

This resampling problem can be solved by two steps

Upsample $x_1[n]$ by the integer factor $L$
Downsample the outcome of the previous step by the integer factor $M$

Upsampling¶

Upsampling is typically done by two steps

Create a zero-inserted sequence from the original signal
Smooth out the discontinuities with a lowpass filter. This filter is sometimes referred to as the interpolation filter

Let the zero-inserted sequence be $x_{1,L}[n]$, where

$$

x_{1,L}[n] = \left{ \begin{array}{cc} x_1[m] & m = \frac{n}{L} \ 0 & otherwise \end{array} \right. $$

Let $X(f)$ be the Fourier transform of $x(t)$. The discrete-time Fourier transform of $x_{1,L}[n]$ and $x_1[n]$ are basically identical, for both of them are essentially

\[ \sum_n{ x(nT_1) e^{j 2 \pi f nT_1} } = \frac{1}{T_1} \sum_k{ X(f - \frac{k}{T_1} }) \]

However, the true "upsampled by factor $L$" signal should be of DTFT

\[ \frac{L}{T_1} \sum_k{ X(f - \frac{kL}{T_1} }) \]

If $x(t)$ is band-limited, of bandwidth $W < \frac{0.5}{T_1}$, then we can design an ideal low-pass filter (LPF) of cut-off frequency $\frac{0.5}{T_1}$, and filter $x_{1,L}[n]$ with this LPF. The DTFT of the filtered $x_{1,L}[n]$ will be $\frac{L}{T_1} \sum_k{ X(f - \frac{kL}{T_1} })$ as desired.

Downsampling¶

Downsampling is typically done by two steps

Apply an anti-aliasing low-pass filter to the original signal
Decimate the filtered signal by a integer factor M.

Combining Upsampling and Downsampling¶

The overall data flow can be described as follows

x1[n] ---> zero-insertion ---> interpolation filter h[n] ---> anti-aliasing filter f[n] ---> decimation ---> x2[n]
                         x1,L[n]   \                                              /     y[n]
                                    -----------------------v----------------------
                                                           g[n]

The interpolation filter $h[n]$ and the anti-aliasing filter $f[n]$ can be combined into one filter $g[n]$ to reduce the computation.

First, zero-pad $g[n]$ so that its length becomes a multiple of $L$. Here we assume the length of the zero-padded $g[n]$ is $qL$, where $q$ is an positive integer.

Let $y[n]$ be the output of $g[n]$, then

\[ \begin{align} y[n] &= x_{1,L}[n] * g[n] \\ &= \sum_{k=0}^{qL-1}( x_{1,L}[n-k]g[k] ) \\ \end{align} \]

Because $x_{1,L}[n-k]=0$ when $(n-k)$ is not multiple of $L$, we can rewrite $y[n]$ as

\[ \begin{align} y[n] &= \left\{ \begin{array}{cc} \sum_{j=0}^{q-1}x_1[\frac{n}{L}-j] \cdot g[L \cdot j] & \mod(n,L)=0 \\ \sum_{j=0}^{q-1}x_1[\frac{n-1}{L}-j] \cdot g[L \cdot j + 1] & \mod(n,L)=1 \\ \vdots \\ \sum_{j=0}^{q-1}x_1[\frac{n-(L-1)}{L}-j] \cdot g[L \cdot j + L-1] & \mod(n,L)=L-1 \\ \end{array} \right. \end{align} \]

Following table illustrates the computation of $y[n]$:


g[0]	g[1]	g[2]	...	g[L]	g[L+1]	g[L+2]	...	g[2L]	g[2L+1]	g[2L+2]	...	g[qL-1]
x1[q]	0	0	...	x1[q-1]	0	0	...	x1[q-2]	0	0	...	0	y[qL] = x1[q]g[0] + x1[q-1]g[L] + ...
0	x1[q]	0	...	0	x1[q-1]	0	...	0	x1[q-2]	0	...	0	y[qL+1] = x1[q]g[1] + x1[q-1]g[L+1] + ...
0	0	x1[q]	...	0	0	x1[q-1]	...	0	0	x1[q-2]	...	0	y[qL+2] = x1[q]g[2] + x1[q-1]g[L+2] + ...

Note that the computation of $y[n]$ above can be viewed as $x_1[n]$ filtered by a filter bank $\{g_0[n], g_1[n], g_2[n], ... , g_{L-1}[n] \}$ where

\[ g_i[n] = \{g[0+i], g[L+i], g[2L+i], ... g[(q-1)L+i]\} \]

This filter bank is called the polyphase filter.

With the "polyphase filter" approach, computing one sample of $y[n]$ requires only $q$ multiplications and $q-1$ additions (instead of $qL$ multiplications and $qL-1$ additions as the typical convolution requires). Also, only 1 out of $M$ samples of $y[n]$ needs to be computed because the rest will be decimated anyway.