chap29.htm

介绍算法的书籍

To examine how the full adder operates, assume that each gate operates in unit time. Figure 29.2(a) shows a set of inputs that becomes stable at time 0. Gates <I>A-D</I>, and no other gates, have all their input values stable at that time and therefore produce the values shown in Figure 29.2(b) at time 1. Note that gates <I>A-D</I> operate in parallel. Gates <I>E</I> and <I>F</I>, but not gate <I>G</I>, have stable inputs at time 1 and produce the values shown in Figure 29.2(c) at time 2. The output of gate <I>E</I> is bit <I>s</I>, and so the <I>s</I> output from the full adder is ready at time 2. The <I>c</I> output is not yet ready, however. Gate <I>G</I> finally has stable inputs at time 2, and it produces the <I>c </I>output shown in Figure 29.2(d) at time 3.<P>
<img src="658_a.gif"><P>
<h4><a name="0930_1970">Figure 29.2 A full-adder circuit. (a) At time 0, the input bits shown appear on the three input wires. (b) At time 1, the values shown appear on the outputs of gates A-D, which are at depth 1. (c) At time 2, the values shown appear on the outputs of gates E and F, at depth 2. (d) At time 3, gate G produces its output, which is also the circuit output.<a name="0930_1970"></sub></sup></h4><P>
<P>







<h2>Circuit depth</h2><P>
<a name="0931_196e"><a name="0931_196f"><a name="0931_1970">As in the case of the comparison networks discussed in Chapter 28, we measure the propagation delay of a combinational circuit in terms of the largest number of combinational elements on any path from the inputs to the outputs. Specifically, we define the <I><B>depth</I></B> of a circuit, which corresponds to its worst-case &quot;running time,&quot; inductively in terms of the depths of its constituent wires. The depth of an input wire is 0. If a combinational element has inputs <I>x</I><SUB>1</SUB><I>, x</I><SUB>2</SUB><I>, . . . ,x<SUB>n</I></SUB> at depths <I>d</I><SUB>1</SUB>, <I>d</I><SUB>2</SUB>, . . . ,<I>d<SUB>n</I></SUB> respectively, then its outputs have depth max{<I>d</I><SUB>1</SUB><I>, d</I><SUB>2</SUB><I>, . . . ,d<SUB>n</I></SUB>} + 1. The depth of a combinational element is the depth of its outputs. The depth of a combinational circuit is the maximum depth of any combinational element. Since we prohibit combinational circuits from containing cycles, the various notions of depth are well defined.<P>
If each combinational element takes constant time to compute its output values, then the worst-case propagation delay through a combinational circuit is proportional to its depth. Figure 29.2 shows the depth of each gate in the full adder. Since the gate with the largest depth is gate <I>G</I>, the full adder itself has depth 3, which is proportional to the worst-case time it takes for the circuit to perform its function.<P>
A combinational circuit can sometimes compute faster than its depth. Suppose that a large subcircuit feeds into one input of a 2-input AND gate but that the other input of the AND gate has value 0. The output of the gate will then be 0, independent of the input from the large subcircuit. In general, however, we cannot count on specific inputs being applied to the circuit, and the abstraction of depth as the &quot;running time&quot; of the circuit is therefore quite reasonable.<P>
<P>







<h2>Circuit size</h2><P>
<a name="0932_1971">Besides circuit depth, there is another resource that we typically wish to minimize when designing circuits. The <I><B>size</I></B><I> </I>of a combinational circuit is the number of combinational elements it contains. Intuitively, circuit size corresponds to the memory space used by an algorithm. The full adder of Figure 29.2 has size 7, for example, since it uses 7 gates.<P>
This definition of circuit size is not particularly useful for small circuits. After all, since a full adder has a constant number of inputs and outputs and computes a well-defined function, it satisfies the definition of a combinational element. A full adder built from a single full-adder combinational element therefore has size 1. In fact, according to this definition, <I>any</I> combinational element has size 1.<P>
The definition of circuit size is intended to apply to families of circuits that compute similar functions. For example, we shall soon see an addition circuit that takes two <I>n</I>-bit inputs. We are really not talking about a single circuit here, but rather a family of circuits--one for each size of input. In this context, the definition of circuit size makes good sense. It allows us to define convenient circuit elements without affecting the size of any implementation of the circuit by more than a constant factor. Of course, in practice, measurements of size are much more complicated, involving not only the choice of combinational elements, but also concerns such as the area the circuit requires when integrated on a silicon chip.<P>
<P>







<h2><a name="0933_0001">Exercises<a name="0933_0001"></h2><P>
<a name="0933_0002">29.1-1<a name="0933_0002"><P>
In Figure 29.2, change input <I>y</I> to a 1. Show the resulting value carried on each wire.<P>
<a name="0933_0003">29.1-2<a name="0933_0003"><P>
Show how to construct an <I>n</I>-input parity circuit with <I>n</I> - 1 XOR gates and depth <img src="../images/hfbrul14.gif">lg <I>n</I><img src="../images/hfbrur14.gif">.<P>
<a name="0933_0004">29.1-3<a name="0933_0004"><P>
Show that any boolean combinational element can be constructed from a constant number of AND, OR, and NOT gates. (<I>Hint:</I> Implement the truth table for the element.)<P>
<a name="0933_0005">29.1-4<a name="0933_0005"><P>
Show that any boolean function can be constructed entirely out of NAND gates.<P>
<a name="0933_0006">29.1-5<a name="0933_0006"><P>
Construct a combinational circuit that performs the exclusive-or function using only four 2-input NAND gates.<P>
<a name="0933_0007">29.1-6<a name="0933_0007"><P>
Let <I>C</I> be an <I>n</I>-input, <I>n</I>-output combinational circuit of depth <I>d</I>. If two copies of <I>C</I> are connected, with the outputs of one feeding directly into the inputs of the other, what is the maximum possible depth of this tandem circuit? What is the minimum possible depth?<P>
<P>


<P>







<h1><a name="0934_1974">29.2 Addition circuits<a name="0934_1974"></h1><P>
<a name="0934_1972"><a name="0934_1973">We now investigate the problem of adding numbers represented in binary. We present three combinational circuits for this problem. First, we look at ripple-carry addition, which can add two <I>n</I>-bit numbers in <img src="../images/bound.gif">(<I>n</I>) time using a circuit with <img src="../images/bound.gif">(<I>n</I>) size. This time bound can be improved to <I>O</I>(lg <I>n</I>) using a carry-lookahead adder, which also has <img src="../images/bound.gif">(<I>n</I>) size. Finally, we present carry-save addition, which in <I>O</I>(1) time can reduce the sum of 3 <I>n</I>-bit numbers to the sum of an <I>n</I>-bit number and an (<I>n</I> + 1)-bit number. The circuit has <img src="../images/bound.gif">(<I>n</I>) size.<P>
<pre>8  7  6  5  4  3  2  1  0     <I>i</I></sub></sup></pre><P>
<pre>1  1  0  1  1  1  0  0  0  =  <I>c</I></sub></sup></pre><P>
<pre>   0  1  0  1  1  1  1  0  =  <I>a</I></sub></sup></pre><P>
<pre>   1  1  0  1  0  1  0  1  =  <I>b</I></sub></sup></pre><P>
<pre>-------------------------------</sub></sup></pre><P>
<pre>1  0  0  1  1  0  0  1  1  =  <I>s</I></sub></sup></pre><P>
<h4><a name="0934_1975">Figure 29.3 Adding two 8-bit numbers a = <img src="../images/lftwdchv.gif">01011110<img src="../images/wdrtchv.gif"> and b = <img src="../images/lftwdchv.gif">11010101<img src="../images/wdrtchv.gif"> to produce a 9-bit sum s = <img src="../images/lftwdchv.gif">100110011<img src="../images/wdrtchv.gif">. Each bit c<SUB>i</SUB> is a carry bit. Each column of bits represents, from top to bottom, c<SUB>i</SUB>, a<SUB>i</SUB>, b<SUB>i</SUB>, and s<SUB>i</SUB> for some i. Carry-in c<SUB>0</SUB> is always 0.<a name="0934_1975"></sub></sup></h4><P>