fird

fird is an open-source toolbox for optimizing FIR filters. The focus is currently on linear programming-based design of linear-phase FIR filters, but the capabilities are expected to expand in the future.

The key thing to note is that fird clearly separates Objective and Constraint. This means that some things, the constraints, will always be met, while the objective will be optimized. Hence, you have to decide if you want to, e.g., minimize the complexity of the filter subject to a frequency response specification (which will be met or you will get an error) or if you want to minimize the approximation error for a given implementation complexity. In many papers, these two things are mixed up, where statements like the following (made up, but you hopefully get the idea) make things very arbitrary:

their method reaches -80 dB with 40 multipliers, but our much better method reaches -70 dB with only 30 multipliers

With fird, you must decide: do you want to minimize the error with 40 multipliers, or do you want to minimize the number of multipliers with a -70 dB error? By the way, you will get exactly what you ask for, nothing more, nothing less, and the solution will be optimal. And nothing prohibits you from trying both approaches and any intermediate ones and comparing the results.

There are constraints and objectives for both frequency-response specifications and implementation complexity. And you can combine multiple constraints of different types, so no problem maximizing a filter’s stopband attenuation while constraining the passband ripple and the number of non-zero multipliers.

Features

Features include

  • Specify the frequency-response of filters using a function or piecewise linear approximation.

  • Design one stage of a multistage filter, taking the other filters into consideration, using the frequency-response of the cascaded filters.

  • Design filters with even or odd symmetry.

  • Finite word-length coefficients with a given number of fractional bits.

  • Control the number of non-zero coefficients (multipliers) directly.

  • Built-in plotting of constraints and objectives in Matplotlib figures.

  • Bound coefficient values (useful to set some coefficients to zero).

  • Bugs and surprises.

Features (do not yet) include

  • Least-squares design.

  • Complex-valued filters.

  • Joint design of cascaded filters (non-convex problem).

  • Fully tested code without any issues or limitations.

  • Farrow filter design.

  • Minimizing the filter order.

  • Bounding coefficient values.

  • Designing filters with power-of-two coefficients (except that all coefficients are powers-of-two…)

  • Get results as APyTypes fixed-point numbers.

Features (will probably never) include

  • Multi-objective optimization: If you have a valid use case for this, please open an issue to discuss it.

  • IIR filters: Not that there isn’t a need for it, but one should the design filters that are stable under finite word-length implementation by construction, i.e., wave digital filters and then one have to select a structure etc. So probably a completely different toolbox.

A note on (mixed integer) linear programming solvers

fird currently uses puLP as the interface to linear programming solvers. puLP supports multiple different solvers, both open-source and commercial, and you can select which one to use when you call solve. By default, the open-source CBC solver is used, which is installed with puLP.

The choice of solver can have a significant impact on the performance (speed and memory usage) of the design process, especially for fixed-point and/or sparse designs. There may also be numerical difficulties, especially for significantly overdesigned filters (think reaching 400 dB stopband attenuation).

However, it should also be noted that while it can be annoying to have to wait for a solution, it will in most cases still only correspond to a short period of the total design and implementation time. Hence, arguments like

our heuristic method only takes 10 seconds instead of linear programming which takes 1 minute (although the results are not optimal)

are not really valid.

If you want to speed up the design process, there are tricks (to be implemented), but the easiest way is probably to get, e.g., Gurobi or CPLEX (which are both free for academic use) and significantly faster than CBC in many cases. If you are not in academia, you may just want to go get a coffee. Or simply work with something else for a bit.

Given time etc, there may be benchmarks of different solvers for typical FIR filter design problems in the future.

References

A good reference for FIR filter design using linear programming is:

Most of the things possible in METEOR are currently possible in fird. As well as things not possible with METEOR.

Overview