Design Options for Basic Building Blocks - Digital Design of Signal Processing Systems: A Practical Approach - page 245

This technique of extracting multi-operand addition can be extended to dataflow graphs
where the graphs are observed to exhibit any potential use of CSA and compression trees.
The graphs are then first transformed to optimally use the compression trees and then are mapped
in HW. Such transformations are proven to significantly improve HW design of signal processing
applications [13].
Multiple addition operations are the easiest of all the transformations. The compression tree can
also be placed in the following add-compare-select operation:

sum 1 ¼ op 1 þop 2 ;
sum 2 ¼ op 3 þop 4 ;

if sim ð 1> sum 2 Þ

sel ¼ 0 ;

else

sel ¼ 1 ;

To transform the logic for optimal use of a compression tree, the algorithm is modified as:

sign op 1 þop 2 op 3 þop 4 ð ð Þ Þ¼ sign op 1 þop 2 op 3 op 4 ð Þ

sign op 1 þop 2 þop 3 0 þ 1 þop 4 0 þ 1 Þ¼ sign op 1 þop 2 þop 3 0 þop 4 0 þ 2 ð Þ

This compression tree transformation on the equivalent DFG is shown in Figure 5.52. Similarly
the following add and multiply operation is represented with the equivalent DFG:

ð

op 1 op ð 2 þop 3 Þ

The DFG can be transformed to effectively use a compression tree. A direct implementation
requires one CPA to perform op2 þ op3, and the result of this operation is then multiplied by op1. A
multiplier architecture comprises a compression tree and a CPA. Thus to implement the computation
two CPAs are required. A simple transformation uses the distributive property of the multiplication
operator:

op 1 op 2 þop 1 op 3 ð 5 15 Þ

:

Op 1 Op 2 Op 3 Op 4 Op 1 Op 2 Op 3 Op 4 2'b10

2

+ +

Compression Tree
(CT)

<

Sign

S S

Figure 5.52 Compression tree replacement for an add compare and select operation