Design methodologies for complexity reduction of FIR filters

• Main Author: Faust, Mathias
• Other Authors: Chang Chip Hong
• Format: Theses and Dissertations
• Language: English
• Published: 2014
• Subjects: DRNTU::Engineering::Electrical and electronic engineering::Electronic systems::Signal processing; DRNTU::Engineering::Computer science and engineering::Hardware::Arithmetic and logic structures; DRNTU::Engineering::Electrical and electronic engineering::Integrated circuits
• Online Access: https://hdl.handle.net/10356/61746
• Institution: Nanyang Technological University

Digital signal processing is ubiquitous and many new applications have been developed for portable wireless communication devices due to the demand for connectivity. Versatile applications running on smaller, faster and energy efficient digital signal processors impose tremendous challenges in the design of the channelizers and signal conditioning circuits after the analog-to-digital conversion. With the advance in VLSI technology, FIR digital filter and other convolution like calculations can be implemented by dedicated hardware to address the needs for high throughput applications such as those in the communication system frontend. Over the past two decades of research, the transposed direct form structure has gained a strong foothold for high-speed application specific integrated circuit (ASIC) implementation of FIR filters. In this architecture, the coefficient multipliers can be grouped into a Multiple Constant Multiplication (MCM) block and implemented multiplication free. The optimization of the number of adders required in the MCM block has been a main subject of research in many leading publications on circuits and systems, and design automation. The design methodologies have advanced from simple minimization algorithms to exact, guaranteed minimal adder algorithms and powerful heuristic algorithms that can tailor the solutions to specific area and delay constraints. The time delayed accumulation of the outputs from the MCM block to produce the final output of the FIR filter can be grouped into a Structural Adder (SA) block. Although this block occupies a substantial part of the overall area of the filter, it has never been a target of complexity reduction in existing optimization algorithms. In this thesis, the design methodologies for optimizing the MCM block are reviewed and discussed. New methods for the optimization of the MCM as well as SA blocks are proposed. First of all, a platform for design automation of FIR filters is introduced with enhanced features added onto this tool for result generation and functional verification. For research convenience and fair evaluation of MCM and SA optimization algorithms, a new benchmark suite has been established and introduced in this thesis. A novel graph based MCM optimization method aimed at minimizing the critical path delay is proposed and extended to deal with the reconfigurable MCM problem. Based on the analysis of the bit-level signals, two new methods for optimizing the MCM block at the bit-level are proposed. One of which targets Field Programmable Gate Array (FPGA) implementation and the other addresses the demand of very high-speed applications in ASIC implementation. A key discovery of this thesis is the optimiza- tion opportunity of SA block. Two SA block optimization methods have been proposed, one for the SAs implemented in two’s complement representation and one for the offset representation. In essence, the methods strive for a positive tradeoff between combinational logic and registers to reduce the implementation cost. Pipelining and bit width reduction techniques for SA block optimization are also proposed. By making use of the existing registers in the tapdelay line of SA block, only a small percentage of additional registers need to be introduced to allows for pipelining. A new method has also be introduced to gradually reduce the bit width of the operators in the SA block towards the output with a very small sacrifice of the output precision. Finally, very high-speed circuit architectures for the conversions from Binary to Canonical Signed Digit (CSD) and from CSD to Binary representations are proposed. These components can be used to speed up and simplify the implementation of adaptive filters.