📄 chap29.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 29: ARITHMETIC CIRCUITS</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap30.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap28.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="092b_194a">CHAPTER 29: ARITHMETIC CIRCUITS<a name="092b_194a"></h1><P>
<a name="092b_1949">The model of computation provided by an ordinary computer assumes that the basic arithmetic operations--addition, subtraction, multiplication, and division--can be performed in constant time. This abstraction is reasonable, since most basic operations on a random-access machine have similar costs. When it comes to designing the circuitry that implements these operations, however, we soon discover that performance depends on the magnitudes of the numbers being operated on. For example, we all learned in grade school how to add two natural numbers, expressed as <I>n</I>-digit decimal numbers, in <img src="../images/bound.gif">(<I>n</I>) steps (although teachers usually do not emphasize the number of steps required).<P>
This chapter introduces circuits that perform arithmetic functions. With serial processes, <img src="../images/bound.gif">(<I>n</I>) is the best asymptotic time bound we can hope to achieve for adding two <I>n</I>-digit numbers. With circuits that operate in parallel, however, we can do better. In this chapter, we shall design circuits that can quickly perform addition and multiplication. (Subtraction is essentially the same as addition, and division is deferred to Problem 29-1.) We shall assume that all inputs are <I>n</I>-bit natural numbers, expressed in binary.<P>
We start in Section 29.1 by presenting combinational circuits. We shall see how the depth of a circuit corresponds to its "running time." The full adder, which is a building block of most of the circuits in this chapter, serves as our first example of a combinational circuit. Section 29.2 presents two combinational circuits for addition: the ripple-carry adder, which works in <img src="../images/bound.gif">(<I>n</I>) time, and the carry-lookahead adder, which takes only <I>O</I>(1g <I>n</I>) time. It also presents the carry-save adder, which can reduce the problem of summing three numbers to the problem of summing two numbers in <img src="../images/bound.gif">(1) time. Section 29.3 introduces two combinational multipliers: the array multiplier, which takes <img src="../images/bound.gif">(<I>n</I>) time, and the Wallace-tree multiplier, which requires only <img src="../images/bound.gif">(1g <I>n</I>) time. Finally, Section 29.4 presents circuits with clocked storage elements (registers) and shows how hardware can be saved by reusing combinational circuitry.<P>
<h1><a name="092d_194e">29.1 Combinational circuits<a name="092d_194e"></h1><P>
<a name="092d_194a"><a name="092d_194b"><a name="092d_194c"><a name="092d_194d">Like the comparison networks of Chapter 28, combinational circuits operate in <I><B>parallel</I>:</B> many elements can compute values simultaneously as a single step. In this section, we define combinational circuits and investigate how larger combinational circuits can be built up from elementary gates.<P>
<h2>Combinational elements</h2><P>
<a name="092e_194e"><a name="092e_194f">Arithmetic circuits in real computers are built from combinational elements that are interconnected by wires. A <I><B>combinational element</I></B> is any circuit element that has a constant number of inputs and outputs and that performs a well-defined function. Some of the elements we shall deal with in this chapter are <I><B>boolean combinational elements</I></B>--their inputs and outputs are all drawn from the set {0,1}, where 0 represents <FONT FACE="Courier New" SIZE=2>FALSE</FONT> and 1 represents <FONT FACE="Courier New" SIZE=2>TRUE</FONT>.<P>
<a name="092e_1950"><a name="092e_1951"><a name="092e_1952"><a name="092e_1953"><a name="092e_1954"><a name="092e_1955"><a name="092e_1956"><a name="092e_1957"><a name="092e_1958"><a name="092e_1959"><a name="092e_195a">A boolean combinational element that computes a simple boolean function is called a <I><B>logic gate</I></B>. Figure 29.1 shows the four basic logic gates that will serve as combinational elements in this chapter: the <I><B>NOT gate</I></B> (or <I><B>inverter</I></B>), the <I><B>AND gate</I></B>, the <I><B>OR gate</I></B>, and the <I><B>XOR gate</I></B>. (It also shows two other logic gates--the <I><B>NAND gate</I></B> and the <I><B>NOR gate</I></B>--that are required by some of the exercises.) The NOT gate takes a single binary <I><B>input</I></B> <I>x</I>, whose value is either 0 or 1, and produces a binary <I><B>output</I></B> <I>z</I> whose value is opposite that of the input value. Each of the other three gates takes two binary inputs <I>x</I> and <I>y</I> and produces a single binary output <I>z</I>.<P>
<a name="092e_195b"><a name="092e_195c"><a name="092e_195d"><a name="092e_195e"><a name="092e_195f"><a name="092e_1960"><a name="092e_1961"><a name="092e_1962">The operation of each gate, and of any boolean combinational element, can be described by a <I><B>truth table</I></B>, shown under each gate in Figure 29.1. A truth table gives the outputs of the combinational element for each possible setting of the inputs. For example, the truth table for the XOR gate tells us that when the inputs are <I>x</I> = 0 and <I>y</I> = 1, the output value is <I>z</I> = 1; it computes the "exclusive OR" of its two inputs. We use the symbols <img src="../images/rtdwnbrc.gif"> to denote the NOT function, <FONT FACE="Times New Roman" SIZE=4><img src="../images/angleup.gif"></FONT> to denote the AND function, <FONT FACE="Times New Roman" SIZE=4><img src="../images/angledwn.gif"></FONT> to denote the XOR function, and <img src="../images/xor14.gif"> to denote the XOR function. Thus, for example, 0 <img src="../images/xor14.gif"> 1 = 1.<P>
<a name="092e_1963"><a name="092e_1964"><a name="092e_1965">Combinational elements in real circuits do not operate instantaneously. Once the input values entering a combinational element <I><B>settle</I></B>, or become <I><B>stable</I></B>--that is, hold steady for a long enough time--the element's output value is guaranteed to become both stable and correct a fixed amount of time later. We call this time differential the <I><B>propagation delay</I></B> of the element. We assume in this chapter that all combinational elements have constant propagation delay.<P>
<img src="656_a.gif"><P>
<h4><a name="092e_1966">Figure 29.1 Six basic logic gates, with binary inputs and outputs. Under each gate is the truth table that describes the gate's operation. (a) The NOT gate. (b) The AND gate. (c) The OR gate. (d) The XOR (exclusive-OR) gate. (e) The NAND (NOT-AND) gate. (f) The NOR (NOT-OR) gate.<a name="092e_1966"></sub></sup></h4><P>
<P>
<h2>Combinational circuits</h2><P>
<a name="092f_1966"><a name="092f_1967"><a name="092f_1968"><a name="092f_1969">A <I><B>combinational circuit</I></B> consists of one or more combinational elements interconnected in an acyclic fashion. The interconnections are called <I><B>wires</I></B>. A wire can connect the output of one element to the input of another, thereby providing the output value of the first element as an input value of the second. Although a single wire may have no more than one combinational-element output connected to it, it can feed several element inputs. The number of element inputs fed by a wire is called the <I><B>fan-out</I></B> of the wire. If no element output is connected to a wire, the wire is a <I><B>circuit input</I></B>, accepting input values from an external source. If no element input is connected to a wire, the wire is a <I><B>circuit output</I></B>, providing the results of the circuit's computation to the outside world. (An internal wire can also fan out to a circuit output.) Combinational circuits contain no cycles and have no memory elements (such as the registers described in Section 29.4).<P>
<P>
<h2>Full adders</h2><P>
<a name="0930_196a">As an example, Figure 29.2 shows a combinational circuit, called a <I><B>full adder</I></B>, that takes as input three bits <I>x, y</I>, and <I>z</I>. It outputs two bits, <I>s </I>and <I>c</I>, according to the following truth table:<P>
<pre>x y z c s</sub></sup></pre><P>
<pre>-------------</sub></sup></pre><P>
<pre>0 0 0 0 0</sub></sup></pre><P>
<pre>0 0 1 0 1</sub></sup></pre><P>
<pre>0 1 0 0 1</sub></sup></pre><P>
<pre>0 1 1 1 0</sub></sup></pre><P>
<pre>1 0 0 0 1</sub></sup></pre><P>
<pre>1 0 1 1 0</sub></sup></pre><P>
<pre>1 1 0 1 0</sub></sup></pre><P>
<pre>1 1 1 1 1</sub></sup></pre><P>
<a name="0930_196b">Output <I>s</I> is the <I><B>parity</I></B> of the input bits,<P>
<pre>s = parity(x,y,z) = x <img src="../images/xor14.gif"> y <img src="../images/xor14.gif"> z,</sub></sup></pre><P>
<h4><a name="0930_196e">(29.1)<a name="0930_196e"></sub></sup></h4><P>
<a name="0930_196c">and output <I>c</I> is the <I><B>majority</I></B> of the input bits,<P>
<pre><I>c</I> = majority(<I>x,y,z</I>) = (<I>x</I> <img src="../images/angleup.gif"> <I>y</I>) <img src="../images/angledwn.gif"> (<I>y</I> <img src="../images/angleup.gif"> <I>z</I>) <img src="../images/angledwn.gif"> (<I>x</I> <img src="../images/angleup.gif"> <I>z</I>).</sub></sup></pre><P>
<h4><a name="0930_196f">(29.2)<a name="0930_196f"></sub></sup></h4><P>
(In general, the parity and majority functions can take any number of input bits. The parity is 1 if and only if an odd number of the inputs are 1's. The majority is 1 if and only if more than half the inputs are 1's.) Note that the <I>c</I> and <I>s</I> bits, taken together, give the sum of <I>x, y</I>, and <I>z</I>. For example, if <I>x</I> = 1, <I>y</I> = 0, and <I>z</I> = 1, then <img src="../images/lftwdchv.gif"><I>c, s</I><img src="../images/wdrtchv.gif"> = <img src="../images/lftwdchv.gif">10<img src="../images/wdrtchv.gif">,<SUP>1</SUP> which is the binary representation of 2, the sum of <I>x, y</I>, and <I>z</I>.<P>
<SUP><FONT FACE="Times" SIZE=1>1</SUP><FONT FACE="Times" SIZE=2>For clarity, we omit the commas between sequence elements when they are bits.</FONT></FONT><P>
<a name="0930_196d">Each of the inputs <I>x, y</I>, and <I>z</I> to the full adder has a fan-out of 3. When the operation performed by a combinational element is commutative and associative with respect to its inputs (such as the functions AND, OR, and XOR), we call the number of inputs the <I><B>fan-in</I></B> of the element. Although the fan-in of each gate in Figure 29.2 is 2, we could redraw the full adder to replace XOR gates <I>A</I> and <I>E</I> by a single 3-input XOR gate and OR gates <I>F</I> and <I>G</I> by a single 3-input OR gate.<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -