Information theoretic approach to complexity reduction of FIR filter design
Chang, Chip Hong
Vinod, Achutavarrier Prasad
Date of Issue2008
School of Electrical and Electronic Engineering
This paper presents a new paradigm of design.methodology to reduce the complexity of application-specific finite-impulse response (FIR) digital filters. A new adder graph data structure called the multiroot binary partition graph (MBPG) is proposed for the formulation of the multiple onstant multiplication problem of FIR filter design. The set of coefficients in any fixed point representation is partitioned into symbols so that common subexpression identification and elimination become congruent to information parsing for data compression. A minimum number of different pairs or groups of symbols and residues can be used to code a set of coefficients based on their probability and conditional probability of occurrence. This ingenious concept enables the notion of entropy to be applied as a quantitative measure to evaluate the coding density of different compositions of symbols towards a set of coefficients. The minimal vertex set MBPG synthesized by our proposed information theoretic approach results in direct correspondences between the vertices and adders, and edges and physical interconnections. Unlike the common subexpression elimination algorithms based on other graph data structures, the symbol-level information carried in each vertex and the graph isomorphism of MBPG promise further fine-grain optimization in a reduced search space. One such optimization that has been exploited in this paper is the shift-inclusive computation reordering to minimize the width of every two’s complement adder to further reduce the implementation cost and the critical path delay of the filter. Experiment results show that the proposed algorithm can contribute up to 19.30% reductions in logic complexity and up to 61.03% reduction in critical path delay over other minimization methods.
DRNTU::Engineering::Electrical and electronic engineering
IEEE transactions on circuits and systems—I
© 2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder. http://www.ieee.org/portal/site This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.