## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

 CHAPTER 12 Trees

Consider the problem of designing a circuit that computes the OR of n bits. A natural approach for solving this problem is to partition the bits into pairs, compute the OR of each pair, and continue recursively until we are left with one bit—the result. The underlying graph, or topology, of the combinational circuit we obtain is a rooted tree. Is this the best design? In this chapter, we prove that indeed, this is the case.

We consider this question in a more general setting. First, we define a class of functions for which the preceding problem can be easily formulated. This is the class of associative Boolean functions. Second, we define a combinational circuit with a topology of a rooted tree, all gates of which are ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required