No icon

A Lattice Basis Reduction Approach for the Design of Finite Word length FIR Filters

A Lattice Basis Reduction Approach for the Design of Finite Word length FIR Filters


Many applications of finite impulse response (FIR) digital filters impose strict format constraints for the filter coefficients. Such requirements increase the complexity of determining optimal designs for the problem at hand. We introduce a fast and efficient method, based on the computation of good nodes for polynomial interpolation and Euclidean lattice basis reduction.

Experiments show that it returns quasi-optimal finite word length FIR filters; compared to previous approaches it also scales remarkably well. It also proves useful for accelerating the determination of optimal finite word length FIR filters.



The straightforward approach, which we call “naive rounding”, consisting in rounding each coefficient of the infinite precision response to the nearest coefficient fitting the imposed constraints, may, even in very simple cases, yield results which are far from optimal mentions an example where a 30 dB improvement is observed).

Another natural approach is to consider all the possible responses that we get by rounding up or down the coefficients of the infinite precision response. A first major drawback of this idea is that the number of possibilities is exponential in the degree of the filter.



To successfully cope with larger degrees, faster heuristics have also been proposed. They produce results that are in many cases, quasi-optimal and can help speed up exact solvers.

The approach introduced in based on error spectrum shaping techniques, is routinely used inside MATLABTM for FIR coefficient As illustrated by Section VI, it returns results that are most of the time better than those computed by competing methods;

When compared to exact MILP-based approaches (which are executed to completion or only for a limited time, depending on the degree), we often find the same result.

Comment As:

Comment (0)