Using a low pass filter to interpolate signal

Question

In my DSP university textbook, the interpolation process is described as follows:

In order to represent a baseband signal $x[k]$ at an increased sampling rate with the same shapes of its time-domain and frequency-domain representations, the insertion of zeros must be followed by low pass filtering with a total bandwidth of $\frac{2 \pi}{R}$ to perform the actual interpolation, with $R$ being the upsampling factor.

The process is depicted in the following figure:

I understand well how we insert zeros between samples of the original signal (i.e. how to go from the first to the second plot of the figure), but I don’t understand how applying a low pass filter to the signal we obtain in the second plot results in the third one. To me, it looks like those zero samples magically get a value, so I would appreciate any explanation of this “magic”.

Answer 1

Answer : Applying Low Pass Filter in frequency domain, is convolving with $sinc$ in time domain.

And what is that $sinc$ exactly.

When you insert $N-1$ zeros between every sample of original sequence, it means you are up-sampling by a factor of $N$. And that will shrink the digital frequency axis by a factor of $N$. Meaning the frequency domain spectrum of up-sampled sequence will now contain $N$ copies of the original spectrum of discrete sequence inside $\omega = [-\pi, \pi]$. So, the original discrete sequence's spectrum $\in [-\pi, \pi]$ will shrink and will be contained inside $\omega = [-\frac{\pi}{N}, \frac{\pi}{N}]$.

Understand the next step like this: Now you will apply an ideal Low Pass Filter to the up-sampled spectrum. And, the cutoff frequency of that LPF would be $\frac{\pi}{N}$, because you want to suppress the other images which were pulled inside as result of zeroes insertion. This LPF of cutoff frequency $\frac{\pi}{N}$ is a $sinc$ in time-domain: $$IDFT\{ \mathcal{LPF}\{\frac{\pi}{N}\}\} = \frac{1}{N}sinc[\frac{n}{N}]$$ This $sinc[\frac{n}{N}]$ will be $0$ only at $n$ which are non-zero multiples of $N$, meaning at only those $n$ where up-sampled sequence $x_{R}[n]=x[\frac{n}{N}]$. Now when you filter the $x_{R}[n]$ with this ideal LPF, in time domain it means convolution of $x_{R}[n]$ with $\frac{1}{N}sinc[\frac{n}{N}]$. And, because $x_{R}[n]$ can also be represented as sum of time-shifted and amplitude-scaled $\delta[n]$'s, therefore, convolution simply means sum of time-shifted and amplitude-scaled $sinc$ functions. So, you get the final interpolated sequence $y[n]$ as follows: $$y[n] = x_{R}[n]*\frac{1}{N}sinc[\frac{n}{N}] $$ $$y[n] = \sum^{\infty}_{k=-\infty}x_{R}[k]\delta[n-k] * \frac{1}{N}sinc[\frac{n}{N}]$$ $$y[n] = \frac{1}{N}\sum^{\infty}_{k=-\infty}x_{R}[k]sinc[\frac{n-k}{N}]$$

These time-shifted and amplitude-scaled $sinc$'s are only non-zero where original $x[n]$ sequences' samples are located now in $x_{R}[n]$, because other $x_{R}[n]$'s are $0$ as a result of $(N-1)$ insertions of $0$. So, the total interference/contribution of all these non-zero $sinc$'s will provide the interpolated values of $y[n]$, at all these values of $n$ where $x_R[n]$ was $0$.

That is interpolation caused by ideal Low Pass Filtering of up-sampled sequences.

Answer 2

Another view which results in superior interpolation filter design is revealed by reviewing the spectrum of the signal with zeros inserted (resulting in an increase of the sampling rate by $I$ when you insert $I-1$ zeroes) and you will see that the original spectrum is replicated at integer multiples of the original sampling rate. The ideal low pass filter is the one that can pass the original spectrum with no distortion and reject all the new alias copies perfectly. (Ideal is not achievable but this defines the filter design targets to approach that). The ideal filter will interpolate the non zero values to grow the zeros to the value for the final interpolated waveform.

What is occurring, to explain the OP's question conceptually, is that the signal requires high frequency content when going from zeros to a large value in just one sample (and inserting zeros causes this to occur as evidenced by the additional high frequency content in the spectrum). This makes complete sense since the frequency content would be related to a change in magnitude versus a change in time (a big change in a short time requires high frequencies). A filter that removes the high frequencies results in the inability for the signal to change rapidly from one sample to the next (due to the memory of the previous samples which is what a filter does). A very easy way to see this occurring is with a simple moving average filter over $M$ samples when you interpolate by $M$ by inserting $M-1$ zeros; such a filter will hold the last sample as a zero-order hold, growing each zero to the last non-zero sample. This isn't a good way to do interpolation since only one non-zero sample is in the memory of the filter, but very easy to visualize. The "magic" happens with better designed filters as described in this answer which then consider many more samples to perform what is essentially interpolation with higher order polynomials.

With regards to Sinc reconstruction that is commonly used to explain "perfect" reconstruction; it is worth mentioning that Sinc reconstruction is only perfect when you can use a Sinc, but unfortunately the Sinc function extends to infinity which is impossible to do in practical realization (it is equivalent to filtering with a brickwall filter). Therefore the Sinc response is truncated in practice, which on its own results in a very poor filter, which is then typically windowed to improve performance. Ultimately, its use when truncated and windowed results in inferior reconstruction filters. Given the approach of paying attention to where the aliases actually reside in frequency, you can realize optimized filters (superior to simply truncating and windowing a Sinc function) using the multi-band filter algorithms such as least squares using firls() function that is available in MATLAB, Python and Octave. I demonstrate this in the plots below from an X4 interpolation example with $f_s = 10$ KHz. The upper plot compares options for interpolation filters with the same number of taps, showing the poor performance of a truncated Sinc in green, and then the improved windowed Sinc filter in green along with the least squares multiband filter in red. All have the same number of taps, but the multiband approach results in 10 dB better rejection of the higher frequency images (and not visible from the scale of the plot, but lower passband ripple distortion as well).

The filter magnitude for the multiband filter was shifted down to overlay with the spectrum after zero-insert showing how the multiband filter maximizes rejection where needed thus resulting in the least amount of distortion in the resulting interpolated signal.

So the spectrum above with it's replication at the higher frequencies (images) has the zeros inserted in the time domain. When those higher frequencies are removed through filtering, the spectrum represents the original signal, at the higher sampling rate, as if it was sampled directly.

A truncated and properly windowed Sinc filter will not achieve the rejection or passband performance of this filter with the same number of taps since it would provide rejection at all locations in between the aliases, while the multi-band filter maximizes the rejection where it is needed. The resulting distortion is predictable and can be traded with the desired filter complexity. This is a standard interpolation design approach for high performance and efficient interpolation (especially when converted to polyphase structures!).