Last week, I published a post on adaptive filtering. It was long overdue, but I actually had one other project on hold for even longer: allowing a user to specify a filter template and let Audio Toolkit figure out a FIR filter from this template.

Remez/Parks & McClellan algorithm

The most famous algorithm is the Remez/Parks & McClellan algorithm. In Matlab, it’s called remez, but Remez is actually a more generic algorithm than just FIR determination.

The algorithm starts by selecting a few random points on the templates where the user set non-zero weights. The zero weights are usually the transition zones, which means that the filter can roam free in these sections. Usually, you don’t want to have them too big, especially in bandpass filters. As the resulting filter has ripples, this means that you can select the weight of each bandwidth in the template. Where the ripples should be small, use a big weight, where they don’t matter, use a small one.

Then, the Remez algorithm is all about moving these points to the maximum of the difference between the template and the actual filter. At the end, the result is an optimal filter around the given template, for a given order.

The determination of the result rests often on the selection of the starting points. If all starting points are in only one bandwidth, then the determination of the filter is wrong. As such, Audio Toolkit selects points that are equidistant so that all bandwidths are covered. Of course, if one bandwidth is too small, then the determination will fail.

Demo

There are many good papers on the Remez algorithm for FIR determination so I won’t take the time to rehash something that lots of people did far better than I could. But I’ll try to explain how it goes on a simple example, with the Python script that was used as the reference test case for the development of the plugin.

Instead of using the equidistant start, I used the set of indices coming from the paper I used (and same for the template). As such, the indices are:

[51 101 341 361 531 671 701 851]

After the optimization, we get the following error function:

The maximum error is 0.0325 in that case. The algorithm then selects new iterations for the next iteration, at the minimum and maximum of the current error function:

[  0 151 296 409 512 595 744 877]

From these indices, we compute the optimal parameters again and then get a new error function (notice that the highlighted points correspond to the previous min/max)

The maximum error is now 0.162. And we start the selection process again:

[  0 163 320 409 512 579 718 874]

Once again, we get a new error function:

The max error is a little bit bigger and is now 0.169. We select new indices:

[  0 163 320 409 512 579 718 874]

The indices are identical, and at the next iteration, the search for the best stops.

The resulting filter has the following transfer function (the template is in red)

Conclusion

There is finally a way of designing filters in Audio Toolkit that don’t require you to go to Matlab or Python. This can be quite efficient to design a linear phase filter on the fly in a plugin. There is probably more work to be done in terms of optimization, but the processing part itself is already fully optimized.