Interpolation techniques for extremely limited hardware

Question

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.

Answer 1

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.

Answer 2

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.