Circuits∗October 16, 2003AbstractIn this document, we build the TOY machine in hardware. Along the way we introduce Booleanfunctions, combinational circuits, and sequential circuits. Circuits are used to model the hardware ofdigital computers. They correspond directly with devices th at we can build. In this document, weaddress the following questions:• How can we build logical gates from wires and transistors?• How can we build arithmetic circuits from logical gates?• How can we build memory circuits?• How can we combine all of these components to build a computer?∗Copyrightc 2001, Kevin Wayne. Based on lecture notes by Robert Sedgewick.1CIRCUITS 2Contents1 Boolean Logic 31.1 Boolean Functions of Two Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Boolean Functions of 3 or More Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Controlled Switches 43 Gates 54 Combinational Circuits 64.1 Multiway AND and OR gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74.2 Sum-of-Products Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84.3 Better circuit design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94.4 Multiplexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104.5 Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114.6 Adder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114.7 Subtracter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 Arithmetic Logic Unit 146 Sequential Circuits (memory) 146.1 Timing Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156.2 Clock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156.3 Flip-flops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166.4 SR flip-flop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166.5 Clocked SR flip-flop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186.6 Clocked D flip-flop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196.7 Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206.8 Register file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216.9 1-bit counter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226.10 Counter (optional) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 Building a TOY Machine 24CIRCUITS 31 Boolean LogicBoolean logic is the foundation of digital computers. It is a rig orous mathematical system based on the twodistinct values true and false. Boolean logic is useful whenever there are two possible situations. A lightbulb is either on or off. In mathematics, a statement is either true or false. In digital circuits, a capacitoris either charged or uncharged. We universally a s sociate 1 with on or tr ue, and 0 with off or false, andrefer to the two binary digits as bits.A mathematical function is an object that takes an input a nd produces an output. For a given functionf, the same input always produces the same output. Some familiar functions that transform one real inputinto one real output include: f (x) = x2+ 5, f(θ) = sin θ, f(x) = 9x/5 + 32. Functions can also take severalinputs, e.g., f (x, y) = x + y, f (x, y) =px2+ y2, f(r, θ) = r s in θ. Boolean functions are functions whoseinputs and output consists of only zeros and ones. For example, the NOT function takes one input bit andreturns the complementary bit.NOT(x) =(1 if x = 00 if x = 1.We will consider several …