Nearest Neighbor Interpolation
One of the most common things any DSP implementation needs to do is interpolation. Here, let’s just discuss how to handle nearest neighbour interpolation.
Among all interpolants, the nearest neighbour interpolator is probably the worst one you could use with respect to signal quality. Better interpolators exist: linear interpolation, quadratic interpolation, etc. These all require multiplies, careful attention to detail to avoid overflow, and more. If you want to build an interpolator, though, the nearest neighbour interpolator is the place to start learning.
As you read below, you’ll see why a nearest neighbour interpolator is the simplest interpolator you could build.
The first step to interpolation is to set up the problem properly.
Your input is an i_data bus which will be valid any time i_stb is true.
Your output is an o_data bus, together with an o_stb qualifier. Whenever the o_stb line is true, the o_data bus will have valid data within it.
Generating the Output Clock
The next step is to handle your clock. Here, you have two options. You can generate a fractional clock based upon your system clock, or you could do the same based upon the input sampling clock. The two options will look nearly identical.
Here’s how you would generate your output timing based upon the system clock:
In this case, the fractional_system_clock_divider is given by two raised to the clock width, times the output clock rate you would like, divided by the system clock rate. The units of the two clock rates don’t matter, just as long as they are consistent.
And here’s how you would generate the output clock based upon the incoming sample clock:
In this case, the clock is set nearly identically, but the fractional divider is instead calculated with respect to the input clock rate, rather than the output clock rate.
Handling the Data Signals
On every input clock, we create a copy of the data.
On every output clock, we copy that data to the output.
Might the incoming data change multiple times between the incoming sample and the outgoing sample? Yes. Won’t this cause a problem? Yes it will. The problem this would create is called aliasing.
You can solve the aliasing problem by filtering your input signal before it comes into the resampler.
Does anyone really use this?
Nearest neighbour interpolators have a lot of problems. It’s not hard to find or see these problems. If they are so poor, are they ever used?
Have I ever used one?
I used a nearest neighbour interpolator once when I needed to resample a signal with an 1024/1023 resampler. To make it work, though, I first insisted that the signal was oversampled (8x in my case) at the output of the anti-aliasing filter. When I later compared the result with a linear interpolator, the nearest neighbour interpolator worked “good enough” for my application, and so I dropped the linear interpolator alternative for this simpler one.
The other place you may see this getting used is in a waveform transmitter when the input clock is just slower than the output clock. In this case, if a new sample isn’t presented to the transmitter by the next sample clock, the last sample can be repeated. You can see this approach used in both the PWM audio, and the FM transmitter (hack) controllers I’ve put together.
For Further Study
If you are interested in knowing more about interpolation, you can find a document describing how to do arbitrary digital interpolation here. In this blog, we’ll focus not on the generics of interpolation, but rather on how to build an interpolator.
But he, willing to justify himself, said unto Jesus, And who is my neighbour? (Luke 10:29)