Efficient multiplierless filter designs for fixed-coefficient and adaptive filtering

The multiplier is the most power and area consuming element in modern digital signal processing. For this reason, there has been extensive research in pursuit of realizing smaller and faster multipliers. When implementing a digital filter, an efficient alternative technique is to build a multiplierless filter by expressing the filter's coefficients as sums of signed-powers-of-two (SPT) numbers. The coefficient multiplications in these filters are performed by only a few shift-and-add operations. However, the best strategy to design a filter with SPT coefficients still remains an open research topic. Existing discrete optimization algorithms which yields optimum solutions for FIR filters with fixed-point binary coefficients do not produce optimum results in designing filters with SPT coefficients. In the first part of this dissertation, we develop two algorithms for the design of fixed-coefficient multiplierless FIR filters with different application emphases.; The first design algorithm aims at designing general multiplierless transversal FIR filters whose implementation complexity is directly proportional to the total number of SPT terms employed. Formulating the design problem as a dynamic-programming-like recursive optimization problem, our algorithm designs filters by performing a trellis search that is similar to the Viterbi algorithm. The use of a trellis search effectively optimizes the filter's frequency response for a given hardware complexity budget. It has been shown, by several design examples, that the proposed algorithm often designs FIR filters that require lower implementation cost than the ones designed by other existing methods.; The second algorithm proposed here is a fast design procedure specially targeted for filters with the prefilter-equalizer structure. The SPT coefficients of the equalizer are obtained by passing copies of its infinite-precision impulse response through a high order sigma-delta modulator with a canonic signed digit (CSD) quantizer at the output. The use of higher order sigma-delta modulation provides more flexibility in moving the quantization error than the previously proposed first-order modulation [1], therefore, it results in superior frequency characteristics for the designed filters.; In the later half of the dissertation, it is demonstrated that the SPT concept can also be extended to implement a multiplierless adaptive filter. The enabling technique is a high-speed two's complement binary number to SPT-terms conversion circuit and an efficient parallel shifter. The design, which could require just 76% of the area of a conventional Booth multiplier, yields comparable filtering performances when employed in the adaptive filter applications.; Finally, the proposed fast SPT conversion and the simplified shifter also find good applications in a programmable filter with recursive computation architecture. Several design examples, along with a simple optimization algorithm, are described in the last part of the dissertation.