Sums of Weighted Bits

A large class of composite fixed-point computations can be expressed as a global sum of weighted bits. This point of view has many advantages, the main one being that the associativity of the sum can be exploited at the bit level to build efficient architectures, called compressor trees, that perform such computations. This chapter defines a data structure, the bit heap, that captures sums of weighted bits. It then discusses the construction of application-specific bit heaps. Finally, it studies the implementation of the corresponding compressor trees.