08-11-2012, 02:01 PM
Design of Digit-Serial FIR Filters: Algorithms, Architectures, and a CAD Tool
digit filter.pdf (Size: 1.04 MB / Downloads: 101)
Abstract
In the last two decades, many efficient algorithms
and architectures have been introduced for the design of lowcomplexity
bit-parallel multiple constant multiplications (MCM)
operation which dominates the complexity of many digital signal
processing systems. On the other hand, little attention has been
given to the digit-serial MCM design that offers alternative lowcomplexity
MCM operations albeit at the cost of an increased
delay. In this paper, we address the problem of optimizing the
gate-level area in digit-serial MCM designs and introduce highlevel
synthesis algorithms, design architectures, and a computeraided
design tool. Experimental results show the efficiency of the
proposed optimization algorithms and of the digit-serial MCM
architectures in the design of digit-serial MCM operations and
finite impulse response filters.
INTRODUCTION
FINITE impulse response (FIR) filters are of great
importance in digital signal processing (DSP) systems
since their characteristics in linear-phase and feed-forward
implementations make them very useful for building stable
high-performance filters. The direct and transposed-form FIR
filter implementations are illustrated in Fig. 1(a) and (b),
respectively. Although both architectures have similar complexity
in hardware, the transposed form is generally preferred
because of its higher performance and power efficiency [1].
The multiplier block of the digital FIR filter in its transposed
form [Fig. 1(b)], where the multiplication of filter coefficients
with the filter input is realized, has significant impact on
the complexity and performance of the design because a
large number of constant multiplications are required.
Boolean Satisfiability
A Boolean function ϕ : {0, 1}n → {0, 1} can be denoted by
a propositional formula. The conjunctive normal form (CNF)
is a representation of a propositional formula consisting of
a conjunction of propositional clauses where each clause is
a disjunction of literals and a literal l j is either a variable
x j or its complement x j . Note that, if a literal of a clause
assumes value 1, then the clause is satisfied. If all literals of
a clause assume the value 0, then the clause is unsatisfied.
The satisfiability (SAT) problem is to find an assignment on
n variables of the Boolean formula in CNF that evaluates the
formula to 1, or to prove that the formula is equal to the
constant 0.
A combinational circuit is a directed acyclic graph with
nodes corresponding to logic gates and directed edges corresponding
to wires connecting the gates. Incoming edges of a
node are called fanins and outgoing edges are called fanouts.
The primary inputs of the network are the nodes without
fanins. The primary outputs are the nodes without fanouts.
Related Work
The exact CSE algorithms that formalize the MCM problem
as a 0–1 ILP problem were introduced in [23] and [24].
In these algorithms, the target constants are defined under
a number representation and all possible implementations of
constant multiplications are extracted from the representations
of constants. The problem reduction and model simplification
techniques for the exact CSE algorithms were presented in [9]
and [25]. Prominent CSE heuristics were proposed in [7], [8],
and [26].
The exact GB algorithms that search for a solution with the
minimum number of operations in breadth-first and depth-first
manners were introduced in [12]. Efficient GB algorithms that
includes two parts, i.e., optimal and heuristic, were introduced
in [10]–[12]. In their optimal parts, each target constant that
can be implemented with a single operation is synthesized.
If there exist unimplemented elements left in the target set,
then they switch to their heuristic parts where the required
intermediate constants are found. The RAG-n algorithm [10]
initially chooses a single unimplemented target constant with
the smallest single coefficient cost evaluated by the algorithm
of [27], and then synthesizes it with a single operation
including one(two) intermediate constant(s) that has(have) the
smallest value in its heuristic part. The Hcub algorithm [11]
selects a single intermediate constant that yields the best
cumulative benefit over all unimplemented target constants for
the implementation of each target constant. The approximate
algorithm [12] computes all possible intermediate constants
that can be synthesized with the current set of implemented
constants using a single operation and chooses the one that
leads to the largest number of synthesized target constants.
CONCLUSION
In this paper, we introduced the 0–1 ILP formalization
for designing digit-serial MCM operation with optimal area
at the gate level by considering the implementation costs of
digit-serial addition, subtraction, and shift operations. Since
there are still instances with which the exact CSE algorithm
cannot cope, we also proposed an approximate GB
algorithm that finds the best partial products in each iteration
which yield the optimal gate-level area in digit-serial
MCM design. This paper also introduced the design architectures
for the digit-serial MCM operation and a CAD tool
for the realization of digit-serial MCM operations and FIR
filters.