Multiplier-less Multiplication by Constants - Digital Design of Signal Processing Systems: A Practical Approach - page 277

benefits and tradeoffs in HW mapping. The direct form requires only one set of registers and a
unified compression tree to optimize the implementation and provide area-efficient designs,
whereas the transposed form works on individual multiplications and keeps the results of these
multiplications in sum and carry forms that require two sets of registers for holding the
intermediate results. This form offers time-efficient designs. A mix of the two forms can
also be used for achieving the best time-area tradeoffs. These forms are shown in Figures 6.12
(c) and (d).

6.7 Complexity Reduction

The TDF structure of an FIR filter implements multiplication of all coefficients with x[n], as shown
in Figure 6.12(b). These multiplications can be implemented as one unit in a block. This
consideration of one unit helps in devising techniques to further simplify the hardware of the
block. All the multiplications in the block are searched to share common sub-expressions. This
simplification targets reducing either the number of adders or the number of adder levels. The two
approaches used for the HW reduction are sub-graph sharing and common sub-expression
elimination [9].

6.7.1 Sub-graph Sharing
The algorithms that can be represented as a dependency graph can be optimized by searching
constituent sub-graphs that are shared in the original graph. An algorithm that involves
multiplication by constants of the same variable has great potential of sub-graph sharing. The
sub-graphs, in these algorithms, are formed by generating all possible MSD (minimum signed
digit) factors of each multiplication. An optimization algorithm minimizes the number of adders
by selecting those options of the sub-graphs that are maximally shared among multiplications.
The problem of generating all possible graphs and finding the ones that minimize the number of
adders is a non-deterministic polynomial-time (NP)-complete problem. Many researchers have
presented heuristic solutions for finding near optimal solutions of this optimization problem. A
detailed description of these solutions is outside the scope of this topic, so interested readers
will find the references listed in this section very relevant. An n-dimension reduced adder graph
(n-RAG) can be sub-optimally computed using efficient heuristics. Such a heuristic is listed
in [10].
Example: This example is derived from [11]. An optimal algorithm in the graphical technique
first generates multiple options of adder graphs for each multiplication. The algorithm then selects
the graph out of all options for each multiplication that shares maximum nodes among all the graphs
implementing multiplications by coefficients.
Consider a 3-coefficient FIR filter with the following 12-bit fixed-point values:

12 0 b h 0 ¼ 0000 0000 0011 ¼ 3

12 0 b h 1 ¼ 0000 0011 0101 ¼ 53

12 0 b h 2 ¼ 0010 0010 1001 ¼ 583

These coefficients are decomposed in multiple options. The decomposition is not unique and
generates a search space. For the design in the example, some of theMSD decomposition options for
each coefficient are: