Zero Stuffing in gen~ (upsampling)

Robert Koster's icon

Hey peeps,

I've been digging deeper into lots of things and just searching for different options to play with when it comes to upsampling/oversampling, antialiasing and filters. I've got some examples of 4x interpolation; doing the process 4 times and then interpolating which filters out before nyquist... (from this forum thx to stkr and ernest)

but can I do a simple zero stuffing type upsampling in gen~?
I dont need the accuracy of oversampling, just the temporary higher nyquist frequency. I tried using interp, input 1 my signal, input 2 being 0 with a factor of 0.5 interpolation but I didn't appear to work. Has anyone else tried this?

Graham Wakefield's icon

I have done a 2x up and down sampling patch. It's partially working but not really in a shape to share currently, but I can maybe talk through it a bit.

The upsampling case has a signal input and two signal outputs for the odd & even signals. The input is written into a delay line. The outputs are the same delay line convolved with a sinc waveform (for the lowpass filtering), but moving through it in steps of 2. The first output is convolved with indices 0, 2, 4, .. etc, and the second output is convolved with indices 1, 3, 5, etc., which is the zero stuffing part of it.

The downsampling case is near identical, but using two inputs (both writing into a delay line each), and summing the two convolutions back to a single output.

// ASCII diagrams of upsampling:
// input signal as x[n], x[n-1], ... i.e. n[t] where t is delay index
// zero stuffed for 2x upsampling:
// n9 _  n8 _  n7 _  n6 _  n5 _  n4 _  n3 _  n2 _  n1 _  n0 _
// convolve with ideal IR kernels
// ir len == 9, buflen = 3
// out0                             _  b0 b1 b2 (1)b2 b1 b0 _
// out1                          _  b0 b1 b2 (1)b2 b1 b0 _
// IR len == 11, buflen = 4
// out0                       _  b0 b1 b2 b3  (1)b3 b2 b1 b0  _
// out1                    _  b0 b1 b2 b3  (1)b3 b2 b1 b0  _
// where b[t] indices the index into the IR buffer

// ASCII diagrams of downsampling
// in2 in1 in2 in1 in2 in1 in2 in1 in2 in1 in2 in1 in2 in1
// n6  n6  n5  n5  n4  n4  n3  n3  n2  n2  n1  n1  n0  n0
//                         _   b0  b1  b2  b3* b2  b1  b0  _
//                     _   b0  b1  b2  b3* b2  b1  b0  _
//                 _   b0  b1  b2  b3  b4* b3  b2  b1  b0  _
//             _   b0  b1  b2  b3  b4* b3  b2  b1  b0  _

The actual IR I was using was 21 samples long, computed as a sinc function under a Blackman window. Here's the genexpr for that part (assuming a [buffer~ ir_buf @samps 21]):

blackman(x) {
    return 0.42 - 0.5*cos(2*pi*x) + 0.08*cos(4*pi*x);
}
Buffer ir_buf;
// cutoff frequency in Hz
hz = in1;
// gain factor applied to all kernel to preserve throughput
gain = 2*hz/samplerate;
// if they change, recompute the IRs:
if (once || change(hz)) {
    once = 0;
    // length of the IR
    buflen = dim(ir_buf);
    sinc_midpoint = buflen-1;
    // the *conceptual* length of the IR
    // +3 because we trimmed the first & last (0), 
    // and middle occurs once
    len = buflen*2 + 1;
    // convert Hz to radians per sample
    w = hz * twopi/samplerate;
    // for each frame of the buffer:
    for (i=0; i<sinc_midpoint; i+=1) {
        // conceptual phase of the IR:
        // (i+1 because we trimmed the first 0-valued sample)
        p = (i+1)/(len-1);
        // k==0 at the dirac pulse in the centre of the sinc
        // (this is 1 sample after the buffer ends)
        // k==1 at the sample just before it, etc. etc.
        k = sinc_midpoint-i;
        // per-sample multiple/divisor for sinc:
        kw = k * w;
        // compute sinc kernel for lowpass
        lp = sin(kw)/kw;
        // sinc function is infinite, 
        // window it here to force sinc to zero at IR ends
        lp *= blackman(p);
        // write to the buffer:
        poke(ir_buf, lp * gain, i);
    }
     // lastvalue:
    poke(ir_buf, gain, sinc_midpoint);
}
Robert Koster's icon

How are you going with this Graham? Have you made much progress?

Mindaugas's icon

Interested too!

Ryan Palm's icon

:O You can do it Graham! Oversampling would be a great addition to Oopsy Daisy.

Robert Koster's icon

I've been playing around with for loops and convolution trying to get something going myself but I keep going around in circles at this point :(
I've tried a few different things and I think the issue is the iteration & index of buffers not lining up all the time and perhaps that the second filter should be processing the zeros? in any case, heres an example;

// declare buffers:
Data input(64);
Data effect(64);
Data output(64);
// the impulse response: (14 zero crossings, kaiser window)
Buffer IR("sinc");
// the length of the IR:
len = dim(IR);
// declare variables for sums and output:
filter = 0;
FX_init = 0;
FX_filter = 0;
Out = 0;
// for loop
for (i=1; i<len; i+=2) {

    //store input samples
    poke(input,in1,i,0,0);

    // Read IR:
    // (by default peek will ignore out-of-bound indices)
    FIR = peek(IR, i, 0);        

    // len-i is to reverse buffer for convolution of input
    In = peek(input, (len-i), 0);

    // accumulate their product:
    filter += FIR * In;

    //inserts zeros by only placing samples at iteration points
    poke(effect,filter,i,0,0);

    //read (&scale from 1st sinc filter)
    FX_init = peek(effect, len-i, 0)*0.812;

    //read IR again
    FIR2 = peek(IR, i, 0);

    //apply effect and filter (skipping zeros coz we can?)
    FX_apply = tanh(FX_init);
    FX_filter += FIR2 * FX_apply;

    //store & read to decimate
    poke(output,FX_filter,i,0,0);
    Out = peek(output, i, 0);

}

Out1 = Out;

FYI - Ive kind of been using this as some sort of guide; https://www.willpirkle.com/app-notes/multiratepolyphase/

damu's icon

I'm also really interested in this. Robert, did you get any further?

Robert Koster's icon

Not really @DAMU but perhaps @Graham Wakefield can tease us with his updated Oversampling example which is coming in the next gen~ book :P ???

damu's icon

There's a new book coming? That's exciting. Do you know when that is due? I've still been working on this as much as possible but my DSP knowledge isn't enough to do anything better than rudimentary upsampling.

Ernest's icon

Hi folks

There is a 2x spline upsampler and downsampler in the 5D filter. I optimized the coefficients so it doesnt use much CPU.

damu's icon

Hi Ernest, thank you so much for replying. I have looked at the relevant parts of the 5D filter and i'm quite confused about which pieces to use to make a more general up/downsampling algorithm in gen~

I'd ideally like to make a 16/32/64x version which works like poly~ and allows me to do weird synthesis/waveshaping techniques in gen~ with minimal aliasing.

Following Will Pirkles methods outlined above, I understand the general principles of how this is done but I definitely need some more guidance on how to implement it. I have purchased Graham and Gregory's new book today which will perhaps enlighten me when it arrives on Friday.

I totally understand if you'd rather not get dragged into this as I understand it isn't a trivial matter, but any more light you could shed on the answer would be very much appreciated.

Robert Koster's icon

That little oversampling algorithm is pretty cool ernest. I noticed a similar one for the SVF.
I haven't managed to get either of those to work in a more general context though, I got either the incorrect output or no output, not sure why. I'll revisit all this oversampling stuff again soon.

damu's icon

I just finished reading Generating Sound and it says that oversampling will be discussed in Book 2, which is exciting. I wonder if we can get a sneek preview if I ask Graham politely one more time?..

Robert Koster's icon

I've done a bit more digging into Will Pirkle's code, but one thing still stumps me...

lets assume we are doing 4x OS with an FIR of 512 taps;

- the FIR is split into 4 'sub band filters' - 128 taps each
- interpolation uses reverse indexing (eg; i-- instead of i++)
- due to zero stuffing we perform gain compensation (multiply input by the OS ratio)
- 4x convolution processes are performed on each input sample (parallel)
- this results in 4 new outputs for every new sample

... then we process each sample individually, let's say with tanh, that means theres 4 parallel process taking place and we store these 4 samples into a buffer for the decimator.

- then the decimator is the same as the interpolator but with forward indexing (i++)
- we accumulate these 4 samples into a single sample for output.


Now for the questions... At first I would assume we need a 128 tap buffer for the input to convolve/interpolate but then why does the decimator only use 4 samples for the input? If we don't need it then are we still performing 512 (128 * 4) multiplications (convolution) on each sample input sample? how do we step through 128 indexes (sub band filters) within 1 sample frame?

I think after knowing that we can crack this 🤓

Robert Koster's icon

a kind individual posted a reaktor tutorial and ported it over to gen objects , then i iterated it a little by reversing the order of the output from the interpolator and increased the taps and it works, but its terribly inefficient (uses 10x as much cpu as poly but is linear phase).

We still need to design and run the filter at the original sr to get it down to 64 taps and then skip all the zeros and we should be onto a winner.

damu's icon

What a great idea. I should have thought to look for something in reaktor. It sounds good to me. Is the redesigned filter intended to lower the cpu or improve the sound quality?

Is it possible to oversample by 8x, 32x using this method? Or would I need to redesign the filters again?

Robert Koster's icon

because it is objects and not code, each OS case would have to be a different patch (or at least one very big patch with lots of switching which would probs be less efficient again). I'm working on doing it all in codebox so that changes can be made dynamically but im trying to get it as optimized as possible first. I'm certain that im missing something simple again.

But I think with linear phase oversampling we have to expect more resources being used than IIR filters used with poly. I'm hoping that we can get it so its related to the os ratio. eg; 4x OS uses 4x more cpu than poly up4. The goal should be better aliasing rejection and linear phase filtering at the cost of slightly more cpu.

I'm pretty determined to get this going...

Wilson Ryan's icon

"kind individual" here. I've updated the patch slightly to use a welch window. Note that other windows are left in the codebox for anyone who wants to futz around. I'm personally quite happy with the current filter performance as the rolloff compared to poly~'s implementation is only really noticeable above 18kHz.

tanh comparisons, Red: gen~ 4x oversampled, Blue: poly~ up 4

Right now this version of 4x oversampling is only using 1.6x the resources as the poly~ comparison, at least on my system.

@damu: this shouldn't be that awful to manually expand out to higher oversampling ratios if you wanted. You'd need to break up the polyphase filter core slightly but it's not that annoying to deal with.

Max Patch
Copy patch and select New From Clipboard in Max.

Robert Koster's icon

that patch doesn't seem to load properly on my end as I have no output from the gen~ patcher (EDIT; Max was just freaking out, works fine) but I'll upload my codebox example shortly with your new windowing functions and have the oversampling as functions so its easier to integrate into a patcher. I was trying all different ways of doing things but only your way has worked so far so not sure how much more we can optimize it.

Robert Koster's icon
Max Patch
Copy patch and select New From Clipboard in Max.

^ Here it all is as genexpr which made it about twice as efficient for me. I started putting it into functions but was getting too many errors, so this will do for now. I still haven't put it in a M4L device yet to get a better measure of performance but at least we can say its done, I guess. Hopefully others can improve it more.

damu's icon

Thanks for commenting the code so thoroughly. I'm determined to understand this. I will try to make an adapted 16x version when I have a free day as that should make the process clear to me.

At present this works well for processing a signal, you've used tanh for the example. How could I create some oversampled oscillator using this same architecture?

Robert Koster's icon

There are other ways to oversample an oscillator that are more efficient, this approach would be more suitable for non-linear processing such as tanh (or any waveshaper, limiter etc). In the latest gen~ book there are examples of sinc-interpolation with mip mapping which is ideal for wavetable oscillators.

I'm positive there are many ways we can get this more efficient. Perhaps different filter arrays for each filter might speed things up, using fractional delay lines for the filters so the filters can be symmetrical, doing 2 steps of up/down sampling with diff filters to achieve the same oversampling and manually fine tuning each filter in various ways. This definitely isn't a trivial thing and very much based on the needs of the developer, I assume that each developer has their own tweaks or ways they like to do things.

Robert Koster's icon

so 5x OS allows for an odd length FIR and with 65 taps and hann window theres a latency of 12 samples and the aliasing rejection is better than poly and uses just under 2x as much cpu as poly. I tried an oversampling ratio of 9 but more oversampling didn't get me better aliasing rejection and used more cpu. so this seems like the best compromise. Time to try it in some M4L devices...

Max Patch
Copy patch and select New From Clipboard in Max.

Wilson Ryan's icon

God damn, this is running very well. I'll also take a stab at modifying it to run a little faster. Right now on my M1 system it's showing just shy of 3x against poly~. Worst case I'll just convert it so the functions are easy to call for anyone who wants to incorporate it into their processes. Thanks for the sweet update!

Edit: at this point, it may make sense for us to try building out a library. I also want to make a real lightweight 2xOS version with a half band filter IIR frontend.

Robert Koster's icon

Hey peeps, little update. I implemented a similar iteration of the oversampling I last posted, in an update for my GMaudio Clipper device. I've been waiting two years for this to come a reality 🥳 I wrote a little article about the oversampling here;
https://fixationstudios.com.au/the-best-clipper-for-ableton-live/

Gussi's icon

If anyone is interested, i implemented a somewhat "efficient" oversampling patch, with a polyphase half-band, symmetric FIR, multi-stage 2x interpolator as the reconstruction filter, or anti-imaging filter, and another polyphase FIR as the final anti-aliasing filter, all running inside an oversampled "poly~ up 8" patch with @resampling 0, so the built in IIR filters are disabled...

My tests showed that poly does ZOH of the input signal (zero-order hold), meaning the input sample is held for n samples where n = oversampling factor. But its easy to turn it into zero-stuffed signal, by just filtering input with a counter in gen, that matches the OS factor, like this:

c = counter(1,0,8,init=7);
y = !c ? in1 : 0;

If you strictly want a zero stuffed signal, running inside poly~ using oversampling. My polyphase implementation, doesnt require this though, since you can just make the algorithm, pretend the signal is zero-stuffed.

If anyone is interested, i can share the patches, and maybe make a short tutorial when i have the time.

Roman Thilenius's icon

would be interesting to see - or maybe you can explain it... what would be better as using [delay 1] for the last N instead of buffir?

the built in uses only 23 taps when i remember right. that is the first reason why you would like to use your own.

Roman Thilenius's icon

in regards to the generator question above i´d like to add that for a synthesizer you usually do not need to use FIR N-filters, as phase normally does not matter - as long as everything which potentially runs in parallel is upsampled the same way.

in an 16x OS FM synth you would rather use two steps and e.g. first go to 88 kHz using a cheap IIR lowpass @ 50 Hz and then add a HQ halfband filter only for going from x2 to x1.

many SRC applications also still do it this way, and waiting time / CPU consumption time would not matter much here.

Gussi's icon

The general idea for a reconstructed smooth 8x waveform of the input signal, in my patch is this:

Use three 2x interpolator stages, running at progressively higher rates, if we are doing 8x oversampling. for 16x we need four stages, for 32x we need five etc.

First stage takes a zero-stuffed signal like this from our original 44.1k signal, inside 8x:
x0 0 0 0 0 0 0 0,
x1 0 0 0 0 0 0 0,
x2 0 0 0 0 0 0 0,
and effectively turning it into a higher resolution 88.2k even/odd signal like this:
e e e e o o o o, (from x0)
e e e e o o o o (from x1),
e e e e o o o o (from x2),
This stage only runs once every 8 samples, or with a period of 8, and holds the even sample for 4 samples, then the odd for 4 samples..

Then second stage, increases the resolution further, and runs with a period of 4, producing:
e e o o e e o o, (for x0),
e e o o e e o o, (for x1),
e e o o e e o o, (for x2),
This stage only runs once every 4 samples, or with a period of 4, and holds the even sample for 2 samples, then the odd for 2 samples..

Then the third and final stage outputs our target 8x waveform at 352.8kHz, producing:
e o e o e o e o, (for x0),
e o e o e o e o, (for x1),
e o e o e o e o, (for x2),

We now have 8 unique samples @8x per our 1 original sample @1x, reconstructed from the ZOH signal, ie: x0 x0 x0 x0 x0 x0 x0 x0, x1 x1 x1 x1 x1 x1 x1 x1, x2 x2 x2 x2 x2 x2 x2 x2..

I implemented the multistage reconstruction filter with halfband FIR's, reducing convolution size by half, then also using symmetric FIR coeffs so we only do around a quarter of the the multiplies of a fulltap FIR, at the cost of more lookups. I used tap sizes per stage that decrease, in order to somewhat equalize the cost per stage, but you can tweak these to your needs. stage 1 used 64 taps, but only computed once every 8 samples, stage 2 used 32 taps, computed once every 4 samples, stage 3 used 16 taps computed once every 2 samples. SO they are roughly equal in terms of cpu usage per stage..

Then we have a nice and smooth 8x waveform, we can clip, saturate, limit , with a more precise ISP awareness etc. Much more accurate, and a consistent peak level, compared to poly~s built in "high quality filters", which i think are IIR and not FIR, but i am not sure. I tried doing some cancellation tests, that suggested a group delay of around 3-4-5 samples, but it didn't increase much beyond that, even at very high OS factors. so whatever filters they use, they don't seem to increase the group delay by much, with the OS factor...

But we still want to apply a final Anti-aliasing filter, in order to avoid harmonics above nyquist for 44.1k, this can be implemented as a polyphase, essentially doing another "half" symmetric FIR convolution, but only once every 8th sample, since thats the only surviving sample post decimation. This is 1/8 the cost of using buffir~ inside 8x, which can be quite expensive at say 128/256 taps, since the sampling rate is 8x. But with the polyphase, ie only filter the 1/8 sample we see back in 44.1k, its alot better.

Roman Thilenius's icon

oh, i completely misunderstood your first post, i thought you switched the topic and talked about downsampling filters (which is in poly~ a science for itself how to get the signals out pf poly~, i ended up with a double buffering method back in the days...)

so ignore my second post, which is off topic. :(

eventually i am still overwhelmed by your abbreviation / optimisation, but of course anything which can shorten the latency for realtime situations is appreciated.

when i am not mistaken what i do is pretty common, as it is difficult enough i never thought about optimising it. the only fancy thing i do is that my abstractions can be switched to different tap lenghts.

my transferfunction for OS x8 is basically weighting->sinc->hamming

expr ( ($f1 != $f2) x (($f3 x sin((1.5707963267948966) x ($f1 - $f2))) / ((3.141592653589793) x ($f1 - $i2))) + ($f1 == $f2) ) x (0.54 - 0.46 cos((6.283185307179586) x $f1 / (2 x $f2)))

where f2 is the FIR lenght (e.g. counter 1-127) and f3 the OS factor.

and input is 1 0 0 0 0 0 0 0 as you can guess.

(extra parentheses around 64 bit values only required for 32 bit max)

the zero padding itself causes a latency of 0 - but getting the filters shorter by stacking multiple filters would be welcome!

(it would also be very helpful if the forum software would not always steal my * signs! hmrrrmblfxgrft!)

Gussi's icon

Poly~ is "most likely" applying an IIR lowpass on the input signal after its been duplicated as a ZOH stream, then probably another IIR lowpass as the anti aliasing filter on the output before decimation?.. If anyone has more specifics on the filters I'd love to know more? It is not uncommon to use the same lowpass as reconstruction filter, or interpolation filter on raw 8x samples, and as the antialiasing filter. This is fine for many use cases, but if you want explicit control over the actual filters used when up/down sampling with poly~, and only use poly~ as the higher sample rate host block for audio processors or synths/generators, I would want to turn off @resampling 0, disabling the "built in" filters, and use my own FIR like i mentioned above.

All poly does at that point, if you don't filter yourself, is decimate the output, by grabbing sample 0, then ignoring the next 7 samples, then output sample 8, then ignore next 7 samples, then sample 16... etc..

That's why the polyphase FIR before the output stage, can be reduced to only run once every 8 samples.. the other 7 are discarded anyway. And it uses 1/8 cpu because of it. My AA FIR uses 0.6% cpu at 8x, for a 260 tap filter at the moment. If i didnt polyphase and just use buffir, it would use around 5%.

Regarding coefficients, i prefer using jitter matrices to generate these with a dynamically sized matrix, using float64 precision in a jit.gen codebox, then maybe Blackman-Harris or kaiser windowed ideal sinc filters or equiripple. Depends on the task i guess.

One note, i used this in a mastering lookahead limiter and other mastering processors, where latency isn't really an issue. So i don't mind large tap sizes, as long as the code is somewhat efficient. It's not intended for live use. But you could just shorten the tap counts for the reconstruction filters to get shorter latency, if that's the goal. I want precision for the oversampled waveform, in order to detect inter-sample peaks (ISP), and limit those in the limiter as an example.

But the half-band interpolator stack is a general purpose solution for reconstruction filters.

If anyone wants to look at patches let me know, don't want to spam the forums with code, unless someone is interested. I just saw this "old" post by now, and realized i had just been working on this with poly~ and gen~ the past weeks..

Roman Thilenius's icon

"That's why the polyphase FIR before the output stage, can be reduced to only run once every 8 samples.. the other 7 are discarded anyway."

... apply delay 8, delay 7, delay 6 to the upsampled music signal, run them through the filters, write them into buffers and then read the buffers out from outside the poly where you finally sum the parts?
then all 7 transfer functions of your standard polyphase FIR 1/8-band filter are required - and actually do their job.
the latency is 1 sample (of the outside world) plus one vector for the double buffering.

but back to upsampling.

what i had in mind when you saw your post is that sinc filters in DACs are realised by huge comb arrays (CIC modules). it is done there like this because of ... low latency.
so maybe something like that can be realized in software, too? preferably with comb or teeth, if need be with gen~.

i am interested in both paths; "optimal latency" as well as "optimal quality", where delays or CPU hunger do not matter.

the "normal" way would be to nest 3 polys and do x 2 x 2 x 2 - then 127 taps each can be considered mastering quality - but of course nobbody wants to patch things like that.

if you could post a small screenshot of how you upsample we might understand better and maybe comment it. :)

Roman Thilenius's icon

and you ´re of course right with blackman beeing sharper.