High-performance and low-complexity implementation of fixed-coefficient FIR filters

• Main Author: Lou, Xin
• Other Authors: Yu Yajun
• Format: Theses and Dissertations
• Language: English
• Published: 2016
• Subjects: DRNTU::Engineering
• Online Access: http://hdl.handle.net/10356/69029
• Institution: Nanyang Technological University

The explosive growth of communication and multimedia applications have put forward a demand for high-performance digital signal processing (DSP). Digital finite impulse response (FIR) filtering is one of the most important operations in many DSP applications. For high-performance and low-complexity implementation of FIR filters, the transposed direct form (TDF) structure is preferred over the direct form due to its inherent pipelined structure and compact constant multiplier implementation. In TDF FIR filters, the input variable is concurrently multiplied by a set of filter coefficients, which is referred to as multiple constant multiplication (MCM). The products generated by the MCM block are delayed and accumulated to produce the filter outputs. For fixed coefficient FIR filters, the MCM blocks can be realized by shift-add networks. The design of efficient MCM blocks has been intensively studied in the past two decades. Earlier MCM algorithms focus on minimizing the number of adders or adder depth to reduce the area complexity or critical path delay of MCM blocks, respectively. Although the bit-level information of adders has been taken into consideration to further reduce the area complexity, the critical path delay is still measured coarsely using adder depth in most of the literatures. Moreover, though the product-accumulation line of TDF FIR filters contribute significant amount of delay, it is omitted in most of the existing works. In this thesis, the gate-level information is taken into consideration in analyzing the delay of MCM blocks and FIR filters. It is noted that the propagation of carries within adders instead of signal propagation along the adder stages, dominates the critical path. Based on this observation, several methods are proposed for the optimization of both the MCM block and the product-accumulation line. First, a signal path based delay model is proposed for precise estimation of critical path delay of MCM blocks. A dual objective configuration optimization (DOCO) algorithm is developed to optimize the shift-add network configuration of MCM blocks. A genetic algorithm (GA)-based technique is further proposed to search for necessary intermediate fundamentals needed to construct the shift-add network. It is shown that the proposed DOCO+GA-based technique generates area-time efficient MCM solutions. Moreover, based on systematic analysis of delay, the theoretical lower bound of critical path delay of MCM blocks is derived. The necessary conditions for achieving the lower bound of critical path delay are discussed. A GA-based approach, with a heuristic algorithm to generate the initial population, is proposed to search for low complexity MCM solutions with lower bound critical path delay. The possible trade-off between the lower bound of critical path delay and area complexity is also discussed. Furthermore, the systematic delay analysis of TDF FIR filters is presented. Based on that, a retiming technique is proposed for the reduction of critical path of TDF FIR filters. By using the proposed technique, the increment of delay caused by the structural adders can be either completely eliminated or minimized at the cost of very small area overhead. Last, a novel approach for the minimization of sign-extension overhead in MCM blocks is proposed. The proposed method can be applied not only to MCM blocks of FIR filters, but also to MCM blocks of any other applications. It is shown that the proposed technique outperforms the existing sign-extension optimization methods in terms of overall area-delay performance.