# Interpolation techniques for extremely limited hardware

I am trying to playback samples on a retro-computer. The hardware is extremely limited, so I am forced to use software PWM as my main method of playback. The limitations of the platform mean that I cannot use a particularly high PWM frequency and the resulting sample resolution is unlikely to exceed 5 or 6 bits. Let us say just for the sake of definiteness that my PWM frequency is about 20 kHz.

Now, my hardware is also quite limited in terms of memory. Samples recorded at 20 kHz are not really practical. As a way of compromise, I am trying to use samples recorded at 5 or 10 kHz, i.e. at frequencies that are factor of 2 or 4 lower than my PWM frequency. I need to interpolate, but sophisticated processing is basically impossible. I tried simple "upsampling" (i.e. inserting zeros between existing samples) and it produces quite a lot of ringing artefacts. I also tried "zero-order hold" and "first-order hold", as defined in What are the relative merits of various upsampling schemes? Frankly, I cannot easily choose between the latter two; both ways are better than simply inserting zeros, but the ringing in both cases is still substantial.

Clearly, more sophisticated filtering is required. My problem is that software PWM is expensive and my computer is weak. All computations will have to take place in 8-bit registers. There is no hardware multiplication/division (except for multiplications/divisions by 2 done by shifting). A FIR filter can probably be implemented by using look-up tables, but I guess no more that 3-5 filter taps are plausible.

So, the question is, what filtering methods are likely to give me the most bang for a buck the least ringing for my very limited platform? Should I try to experiment with FIR filters tweaked to get 8-bit friendly numbers or should I do something entirely different? What filtering strategies do you think are likely to work best in the limited computing environment?

In terms of my homework, I did read through the post cited above and several other posts related to it. I've done some reading on Google. I understand how to construct moving averages, including polynomials (="higher order holds"), but the discussions seem to suggest that they are not the best option. FFT is impossible. I am currently playing with various 3-5 tap FIR filters, which seem to work, but are approximately maximum that I can do computationally. I tried to implement CIC filter (and failed to get a decent result). I have not looked at IIR filters yet. So, basically, I am asking this question in the hope that you could help me to focus on something a bit more specific, maybe a family of filters that are more likely to be useful in my case, maybe even specific filters.

• What do you mean you have ringing? Do you have some kind of anti-imaging filter (analog filter) at the output of your PWM?
– Ben
Nov 20 '17 at 19:09
• This is a software PWM, so no anti-imaging filter is possible. There will be some effective filtering (analogue circuts in my retro-computer are pretty basic), but I cannot really rely on that for anything useful. I believe that my main problem is caused by aliasing artefacts. Nov 20 '17 at 19:15
• I know it's a software PWM. I mean did you acquire any real output data on an oscilloscope? Is it straight from the CPU pin or is there some kind of filter? If you grabbed the data from a scope, were you grounded with a short ground probe?
– Ben
Nov 20 '17 at 20:12
• I did not try to capture the signal off the hardware, because I do most of my work in emulated environment. I'll do some hardware tests to see what kinds of artefacts I'm getting more precisely; it is not the CPU that drives the output pin, but there is another chip that is responsible for sound. Nov 20 '17 at 23:27
• If you're purely in the digital world then you should not see any ringing at the output... Unless you have some kind of anti-aliasing thing going on...
– Ben
Nov 21 '17 at 13:39

For retro hardware, the low pass filter after the PWM is probably the inertia of the speaker cone and/or your ear's internals. So first make sure the ringing isn't beyond your requirements at the full PWM sample rate, or due to quantization (use some tiny 20kHz sample rate waveform loops for testing).

For upsampling, I might try a zero or first order hold followed by an IIR filter (1st order or a biquad low-pass) chosen so that it only has a tiny number of "1"'s in the binary coefficients, allowing shift-and-add recursive filtering with deterministic latency. If you can find coefficients with a tiny enough number of "1"'s in total, a cascade of biquad IIR's is also possible.

On the data preparation side, you can pre-noise-filter your samples on a more powerful system, instead of just depending on the retro-CPU's quantization. You an also simulate your retro system's output filter, and tune the noise filtering to move some of the noise outside the passband.

• I never properly thought about the analogue circuits. One of the reasons is to do with the fact that different models of hardware would have different sound circuits, so I thought that it would be more productive to focus on "pure" signal at the output pin. So, your point, if I understood it correctly, is that PWM itself can generate audible artefacts below PWM frequency. Can you recommend something to read about it? Thank you for your comments about specific filtering scheme (I'll have to read up on IIR, but it is OK). Nov 20 '17 at 23:23

I'd think linear interpolation is good enough, because the quality specs are so low otherwise. The poor image suppression of zero-order hold and linear interpolation can even be considered a benefit because then there's at least some high-frequency content. It's a matter of taste.

For a factor of 2, I'd recommend a finite impulse response (FIR) filter with coefficients {-1/16, 0, 9/16, 1, 9/16, 0, -1/16} (Filter 1) running at 20 kHz on the 10 kHz-sampled signal with the sampling frequency doubled by zero stuffing. Of the family of FIR filters with coefficients {b, 0, a, 1, a, 0, b}, the filter with a = 9/16, b = -1/16 has the maximum number of vanishing derivatives of the magnitude frequency response $|2b\cos(3\omega) + 2a\cos(\omega) + 1|$ at $\omega = 0$, making both the pass band and the stop band flat, while having a 0 Hz gain of 2 which compensates for the effective gain of 1/2 of zero stuffing. Also note for optimization that 9/16 = 1/2 + 1/16.

For a factor of 4, you could do the above to go from a sampling frequency of 5 kHz to 10 kHz, and then linearly interpolate to 20 kHz, by taking the average of successive samples to get the in-between samples. The combined operation is equivalent to the filter {b/2, b, b/2, 0, a/2, a, (1+a)/2, 1, (1+a)/2, a, a/2 0, b/2, b, b/2} (Filter 2) and has a magnitude frequency response of $|b\cos(7\omega) +$ $2b\cos(6\omega) +$ $b\cos(5\omega) +$ $a\cos(3\omega) +$ $2a\cos(2\omega) +$ $(1 + a)\cos(\omega) + 1|.$ The magnitude frequency response no longer has the same number of vanishing derivatives, which could be restored by using a = 37/64, b = -5/64 (Filter 3), but the difference would be marginal and not worth the extra cost if hardware multiplications are not available.

Figure 1. Magnitude frequency response of filter 1 (red), filter 2 (blue), filter 3 (purple).

A drawback of these methods over zero-order hold and linear interpolation is that they may overshoot, exceeding the range of the original signal by factor of $|a|+|b|$ in the worst case.

For a factor of 4, if you can afford to, you could use filter 1 twice, first to go from 5 kHz to 10 kHz, and then to go from 10 kHz to 20 kHz (Filter 4):

Figure 2. Frequency responses of filter 2 (blue) and filter 4 (red). Filter 4 has a flatter pass band and better image attenuation.

You should hard-code the multiplications by coefficients for each possible fractional part of the time variable, and take advantage of the distributive property of division (impelmented by right shift) over addition and subtraction, for example a/4 + b/4 = (a + b)/4. This gives more efficient code than storing the coefficients numerically.

You could improve image attenuation further by approximate equiripple or least squares designs, but that would require using more complicated coefficients.

By the way, it often takes less bits to store the difference between successive samples than it takes to store the samples as such.

• Many thanks for specific schemes, because it is definitely useful for me to learn this mode of thinking better. I can definitely hear too many artefacts when using simple linear interpolation; I understand what you mean regarding "at least some high frequency content", but at least for the samples I used for testing there is definitely benefit in using stronger filters. Nov 20 '17 at 23:39