chap29.htm

介绍算法的书籍

<h2><a name="0935_197a">29.2.1 Ripple-carry addition<a name="0935_197a"></h2><P>
<a name="0935_1974"><a name="0935_1975">We start with the ordinary method of summing binary numbers. We assume that a nonnegative integer <I>a</I> is represented in binary by a sequence of <I>n</I> bits <img src="../images/lftwdchv.gif"><I>a<SUB>n-</I>1</SUB><I>, a<SUB>n-</I>2</SUB><I>, . . . , a</I><SUB>0</SUB><img src="../images/wdrtchv.gif">, where <I>n</I> <img src="../images/gteq.gif"> <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrul14.gif">l</FONT>g(<I>a</I> + 1)<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrur14.gif"> </FONT>and<P>
<img src="661_a.gif"><P>
<a name="0935_1976"><a name="0935_1977"><a name="0935_1978">Given two <I>n</I>-bit numbers <I>a</I> = <img src="../images/lftwdchv.gif"><I>a<SUB>n</I>-1</SUB><I>, a<SUB>n</I>-2</SUB><I>, . . . , a</I><SUB>0</SUB><img src="../images/wdrtchv.gif"> and <I>b = </I><img src="../images/lftwdchv.gif">b<SUB>n-<I>1</SUB></I>, b<SUB>n-<I>2</SUB></I>, . . . , b<I><SUB>0</SUB><img src="../images/wdrtchv.gif">, </I>we wish to produce an (<I>n</I> + 1)-bit sum <I>s = </I><img src="../images/lftwdchv.gif">s<SUB>n</SUB>, s<SUB>n-<I>1</SUB></I>, . . . , s<I><SUB>0</SUB><img src="../images/wdrtchv.gif"></I>. Figure 29.3 shows an example of adding two 8-bit numbers. We sum columns right to left, propagating any carry from column<I> i</I> to column <I>i</I> + 1, for <I>i</I> = 0, 1, . . . , <I>n</I> - 1. In the <I>i</I>th bit position, we take as inputs bits <I>a<SUB>i</I></SUB> and <I>b<SUB>i </I></SUB>and a <I><B>carry-in bit</I></B><I> c<SUB>i</I></SUB>, and we produce a <I><B>sum bit</I></B><I> s<SUB>i</I></SUB> and a <I><B>carry-out</I></B><I> </I>bit<I> c<SUB>i+</I>1</SUB>. The carry-out bit <I>c<SUB>i+</I>1</SUB><I> </I>from the<I> i</I>th position is the carry-in bit into the (<I>i</I> + 1)st position. Since there is no carry-in for position 0, we assume that <I>c</I><SUB>0</SUB> = 0. The carry-out <I>c<SUB>n</SUB> </I>is bit<I> s<SUB>n</SUB> </I>of the sum.<P>
Observe that each sum bit <I>s<SUB>i</I></SUB> is the parity of bits <I>a<SUB>i</I></SUB>, <I>b<SUB>i</I></SUB>, and <I>c<SUB>i</I></SUB> (see equation (29.1)). Moreover, the carry-out bit <I>c<SUB>i</I>+1</SUB> is the majority of <I>a<SUB>i</I></SUB>, <I>b<SUB>i</I></SUB>, and <I>c<SUB>i</I></SUB> (see equation (29.2)). Thus, each stage of the addition can be performed by a full adder.<P>
<a name="0935_1979">An <I>n</I>-bit <I><B>ripple-carry adder</I></B> is formed by cascading <I>n</I> full adders <I>FA</I><SUB>0</SUB>, <I>FA</I><SUB>1</SUB><I>, . . . , FA<SUB>n-</I>1</SUB>, feeding the carry-out <I>c<SUB>i+</I>1</SUB> of <I>FA<SUB>i</I></SUB> directly into the carry-in input of <I>FA<SUB>i+</I>1</SUB>. Figure 29.4 shows an 8-bit ripple-carry adder. The carry bits &quot;ripple&quot; from right to left. The carry-in <I>c</I><SUB>0</SUB> to full adder <I>FA</I><SUB>1</SUB> is <I><B>hardwired</I></B> to 0, that is, it is 0 no matter what values the other inputs take on. The output is the (<I>n+</I>1)-bit number <I>s = </I><img src="../images/lftwdchv.gif"><I>s<SUB>n</SUB>, s<SUB>n-</I>1</SUB><I>, . . . , s<SUB>0</I></SUB><img src="../images/wdrtchv.gif">, where <I>s<SUB>n </I></SUB>equals <I>c<SUB>n</I></SUB>, the carry-out bit from full adder <I>FA<SUB>n</I></SUB>.<P>
Because the carry bits ripple through all <I>n</I> full adders, the time required by an <I>n</I>-bit ripple-carry adder is <img src="../images/bound.gif">(<I>n</I>). More precisely, full adder <I>FA<SUB>i</I></SUB> is at depth <I>i</I> + 1 in the circuit. Because <I>FA<SUB>n-</I>1</SUB> is at the largest depth of any full adder in the circuit, the depth of the ripple-carry adder is <I>n</I>. The size of the circuit is <img src="../images/bound.gif">(<I>n</I>) because it contains <I>n</I> combinational elements.<P>
<img src="662_a.gif"><P>
<h4><a name="0935_197b">Figure 29.4 An 8-bit ripple-carry adder performing the addition of Figure 29.3. Carry bit c<SUB>0</SUB> is hardwired to 0, indicated by the diamond, and carry bits ripple from right to left.<a name="0935_197b"></sub></sup></h4><P>
<P>







<h2><a name="0936_1985">29.2.2 Carry-lookahead addition<a name="0936_1985"></h2><P>
<a name="0936_197a"><a name="0936_197b">Ripple-carry addition requires <img src="../images/bound.gif">(<I>n</I>) time because of the rippling of carry bits through the circuit. Carry-lookahead addition avoids this <img src="../images/bound.gif">(<I>n</I>)-time delay by accelerating the computation of carries using a treelike circuit. A carry-lookahead adder can sum two <I>n</I>-bit numbers in <I>O</I>(lg<I> n</I>) time.<P>
The key observation is that in ripple-carry addition, for <I>i </I><img src="../images/gteq.gif"> <I></I>1, full adder <I>FA<SUB>i</I></SUB> has two of its input values, namely <I>a<SUB>i</I></SUB> and <I>b<SUB>i</I></SUB>, ready long before the carry-in <I>c<SUB>i</I></SUB> is ready. The idea behind the carry-lookahead adder is to exploit this partial information.<P>
<a name="0936_197c"><a name="0936_197d"><a name="0936_197e"><a name="0936_197f">As an example, let <I>a<SUB>i-</I>1</SUB><I> = b<SUB>i-</I>1</SUB>. Since the carry-out <I>c<SUB>i</SUB> </I>is the majority function, we have <I>c<SUB>i</SUB> = a<SUB>i-</I>1</SUB><I> = b<SUB>i</I>-1</SUB> <I></I>regardless of the carry-in<I> c<SUB>i-</I>1</SUB>. If <I>a<SUB>i-</I>1</SUB><I> = b<SUB>i-</I>1</SUB><I> = </I>0, we can <I><B>kill</I></B> the carry-out<I> c<SUB>i</I></SUB> by forcing it to 0 without waiting for the value of <I>c<SUB>i</I>-1</SUB> to be computed. Likewise, if <I>a<SUB>i-</I>1</SUB><I> = b<SUB>i-</I>1</SUB><I> = </I>1, we can <I><B>generate</I></B> the carry-out<I> c<SUB>i</SUB> = </I>1, irrespective of the value of <I>c<SUB>i-</I>1</SUB>.<P>
<a name="0936_1980"><a name="0936_1981">If <I>a<SUB>i-</I>1 </SUB><img src="../images/noteq.gif"> <I>b<SUB>i-</I>1</SUB>, however, then <I>c<SUB>i</I></SUB> depends on <I>c<SUB>i-</I>1</SUB>. Specifically, <I>c<SUB>i</SUB> = c<SUB>i-</I>1</SUB>, because the carry-in <I>c<SUB>i</I>-1</SUB> casts the deciding &quot;vote&quot; in the majority election that determines <I>c<SUB>i</I></SUB>. In this case, we <I><B>propagate</I></B> the carry, since the carry-out is the carry-in.<P>
<a name="0936_1982">Figure 29.5 summarizes these relationships in terms of <I><B>carry statuses</I></B>, where <FONT FACE="Courier New" SIZE=2>k</FONT> is &quot;carry kill,&quot; g is &quot;carry generate,&quot; and <FONT FACE="Courier New" SIZE=2>p</FONT> is &quot;carry propagate.&quot;<P>
<a name="0936_1983">Consider two consecutive full adders <I>FA<SUB>i-</I>1</SUB> and <I>FA<SUB>i</I></SUB> together as a combined unit. The carry-in to the unit is <I>c<SUB>i</I>-1</SUB>, and the carry-out is <I>c<SUB>i+</I>1</SUB>. We can view the combined unit as killing, generating, or propagating carries, much as for a single full adder. The combined unit kills its carry if <I>FA<SUB>i </I></SUB>kills its carry or if <I>FA<SUB>i</I>-1</SUB> kills its carry and <I>FA<SUB>i</I></SUB> propagates it. Similarly, the combined unit generates a carry if <I>FA<SUB>i</I></SUB> generates a carry or if <I>FA<SUB>i-</I>1 </SUB>generates a carry and <I>FA<SUB>i</I></SUB> propagates it. The combined unit propagates the carry, setting <I>c<SUB>i+</I>1</SUB><I> = c<SUB>i</I>-1</SUB>, if both full adders propagate carries. The table in Figure 29.6 summarizes how carry statuses are combined when full adders are juxtaposed. We can view this table as the definition of the <I><B>carry-status operator</I></B> <img src="../images/circx.gif"> over the domain {<FONT FACE="Courier New" SIZE=2>k</FONT>, <FONT FACE="Courier New" SIZE=2>p</FONT>, g}. An important property of this operator is that it is associative, as Exercise 29.2-2 asks you to verify.<P>
<pre>a<B><SUB>i-1</SUB></B>  b<B><SUB>i-1   </SUB></B>c<B><SUB>i   </SUB></B>carry status</sub></sup></pre><P>
<pre>-----------------------------</sub></sup></pre><P>
<pre>  0    0     0        k</sub></sup></pre><P>
<pre>  0    1    c<SUB>i-1</SUB>      p</sub></sup></pre><P>
<pre>  1    0    c<SUB>i-1</SUB>      p</sub></sup></pre><P>
<pre>  1    1     1        g</sub></sup></pre><P>
<h4><a name="0936_1986">Figure 29.5 The carry-out bit c<SUB>i</SUB> and carry status corresponding to inputs a<SUB>i-1</SUB>, b<SUB>i-1, </SUB>and c<SUB>i-1</SUB> of full adder FA<SUB>i-1</SUB> in ripple-carry addition.<a name="0936_1986"></sub></sup></h4><P>
<pre>              FA<B><I><SUB>i</I></B></sub></sup></pre><P>
<pre>       <B><img src="../images/circx.gif">  k   p   g</B></sub></sup></pre><P>
<pre>--------------------</sub></sup></pre><P>
<pre>       k  k   k   g</sub></sup></pre><P>
<pre>FA<SUB>i-1  </SUB>p  k   p   g</sub></sup></pre><P>
<pre>       g  k   g   g</sub></sup></pre><P>
<h4><a name="0936_1987">Figure 29.6  The carry status of the combination of full adders FA<SUB>i-1</SUB> and FA<SUB>i</SUB> in terms of their individual carry statuses, given by the carry-status operator <img src="../images/circx.gif"> over the domain {k<FONT FACE="Times New Roman" SIZE=2>, p, g}.<a name="0936_1987"></FONT></sub></sup></h4><P>
We can use the carry-status operator to express each carry bit <I>c<SUB>i</I></SUB> in terms of the inputs. We start by defining <I>x</I><SUB>0</SUB> = <FONT FACE="Courier New" SIZE=2>k</FONT> and<P>
<img src="663_a.gif"><P>
<h4><a name="0936_1988">(29.3)<a name="0936_1988"></sub></sup></h4><P>
for <I>i = </I>1, 2, . . . , <I>n</I>. Thus, for <I>i = </I>1, 2, . . . <I>, n</I>, the value of <I>x<SUB>i</I></SUB> is the carry status given by Figure 29.5.<P>
<a name="0936_1984">The carry-out <I>c<SUB>i</I></SUB> of a given full adder <I>FA<SUB>i</I>-1</SUB> can depend on the carry status of every full adder <I>FA<SUB>j</SUB> </I>for<I> j =</I> 0, 1, . . . <I>, i </I>- 1. Let us define <I>y</I><SUB>0</SUB><I> = x</I><SUB>0</SUB><I> </I>=<I> </I><FONT FACE="Courier New" SIZE=2>k</FONT> and<P>
<pre><I>y<SUB>i </SUB> </I>=<I> y<SUB>i-</I>1 </SUB><img src="../images/circx.gif"><I> x<SUB>i</I></sub></sup></pre><P>
<pre>= x<SUB>0 </SUB><img src="../images/circx.gif"> x<SUB>1</SUB> <img src="../images/circx.gif"> <img src="../images/dot10.gif"><img src="../images/dot10.gif"><img src="../images/dot10.gif"> <img src="../images/circx.gif"> x<SUB>i</sub></sup></pre><P>
<h4><a name="0936_1989">(29.4)<a name="0936_1989"></sub></sup></h4><P>
for <I>i</I> = 1, 2, . . . , <I>n</I>. We can think of <I>y<SUB>i</I> </SUB>as a &quot;prefix&quot; of <I>x</I><SUB>0</SUB> <img src="../images/circx.gif"> <I>x</I><SUB>1</SUB> <img src="../images/circx.gif"><img src="../images/dot10.gif"><img src="../images/dot10.gif"><img src="../images/dot10.gif">  <img src="../images/circx.gif"> <I>x<SUB>n</I></SUB>; we call the process of computing the values <I>y</I><SUB>0</SUB>, <I>y</I><SUB>1</SUB>, . . . , <I>y<SUB>n</I></SUB> a <B>prefix computation.</B> (Chapter 30 discusses prefix computations in a more general parallel context.) Figure 29.7 shows the values of <I>x<SUB>i</I></SUB> and <I>y<SUB>i</I></SUB> corresponding to the binary addition shown in Figure 29.3. The following lemma gives the significance of the <I>y<SUB>i</I></SUB> values for carry-lookahead addition.<P>
<img src="664_a.gif"><P>
<h4><a name="0936_198a">Figure 29.7 The values of x<SUB>i</SUB> and y<SUB>i</SUB> for i = 0, 1, . . . , 8 that correspond to the values of a<SUB>i</SUB>, b<SUB>i</SUB>, and c<SUB>i</SUB> in the binary-addition problem of Figure 29.3. Each value of x<SUB>i</SUB> is shaded with the values of a<SUB>i-1</SUB> and b<SUB>i-1</SUB> that it depends on.<a name="0936_198a"></sub></sup></h4><P>
<a name="0936_198b">Lemma 29.1<a name="0936_198b"><P>
Define<I> x</I><SUB>0</SUB><I>, x</I><SUB>1</SUB><I>, . . . , x<SUB>n </I></SUB>and <I>y</I><SUB>0</SUB>,<I> y<SUB>1</SUB>, . . . , y<SUB>n</I></SUB> by equations (29.3) and (29.4). For <I>i = </I>0, 1, <I>. . . ,n</I>, the following conditions hold:<P>
1.     <I>y<SUB>i</SUB> =</I> <FONT FACE="Courier New" SIZE=2>k</FONT> implies <I>c<SUB>i</SUB> = </I>0,<P>
2.     <I>y<SUB>i</SUB> = </I>g implies <I>c<SUB>i</SUB> = </I>1, and<P>
3.     <I>y<SUB>i</SUB> =</I> <FONT FACE="Courier New" SIZE=2>p</FONT> does not occur.<P>
<I><B>Proof     </I></B>The proof is by induction on<I> i</I>. For the basis<I>, i</I> = 0. We have <I>y</I><SUB>0</SUB><I> = x</I><SUB>0</SUB> <I>= </I><FONT FACE="Courier New" SIZE=2>k</FONT> by definition, and also <I>c</I><SUB>0</SUB> = 0. For the inductive step, assume that the lemma holds for <I>i</I> - 1. There are three cases depending on the value of <I>y<SUB>i</I></SUB>.<P>
1.     If <I>y<SUB>i</SUB> = </I><FONT FACE="Courier New" SIZE=2>k</FONT>, then since <I>y<SUB>i</I></SUB> = <I>y<SUB>i-</I>1</SUB><I> </I><img src="../images/circx.gif"> x<SUB>i<I></SUB>, the definition of the carry-status operator <img src="../images/circx.gif"></I> from Figure 29.6 implies either that <I>x<SUB>i</SUB> = </I><FONT FACE="Courier New" SIZE=2>k</FONT> or that <I>x<SUB>i</SUB> =</I> p<I> </I>and <I>y<SUB>i-</I>1</SUB><I> = </I><FONT FACE="Courier New" SIZE=2>k</FONT>. If <I>x<SUB>i =</I> </SUB><FONT FACE="Courier New" SIZE=2>k</FONT>, then equation (29.3) implies that a<I><SUB>i-</I>1</SUB> = <I>b<SUB>i-</I>1</SUB><I> = </I>0, and thus<I> c<SUB>i</I></SUB> = majority (<I>a<SUB>i-</I>1</SUB><I>, b<SUB>i-</I>1</SUB><I>, c<SUB>i-</I>1</SUB>)<I> = </I>0<I>. </I>If<I> x<SUB>i</SUB> =</I> <FONT FACE="Courier New" SIZE=2>p<I> </I></FONT>and <I>y<SUB>i-</I>1</SUB><I> = </I><FONT FACE="Courier New" SIZE=1>k</FONT>, then <I>a<SUB>i-</I>1</SUB> <img src="../images/noteq.gif"><I> b<SUB>i-</I>1</SUB> and, by induction, <I>c<SUB>i-</I>1</SUB> = 0. Thus, majority (<I>a<SUB>i-</I>1</SUB>, <I>b<SUB>i-</I>1</SUB><I>, c<SUB>i-</I>1</SUB>) = 0, and thus <I>c<SUB>i</SUB> =</I> 0.<P>
2.     If <I>y<SUB>i</SUB> = </I>g, then either we have <I>x<SUB>i</SUB> = </I>g or we have <I>x<SUB>i</SUB> =</I> p and<I> y<SUB>i-</I>1</SUB><I> = </I>g. If <I>x<SUB>i</SUB> =</I> g, then <I>a<SUB>i-</I>1</SUB><I> = b<SUB>i-</I>1</SUB><I>=</I> 1, which implies <I>c<SUB>i</I></SUB> = 1. If <I>x<SUB>i</SUB> = </I>p and <I>y<SUB>i-</I>1</SUB> = g, then<I> a<SUB>i-</I>1</SUB> <img src="../images/noteq.gif"><I> b<SUB>i-</I>1</SUB> and, by induction, <I>c<SUB>i-</I>1</SUB> = 1, which implies <I>c<SUB>i=</I> 1</SUB>.<P>
3.     If <I>y<SUB>i</SUB> =</I> <FONT FACE="Courier New" SIZE=2>p</FONT>, then Figure 29.6 implies that <I>y<SUB>i-</I>1</SUB> = <FONT FACE="Courier New" SIZE=2>p</FONT>, which contradicts the inductive hypothesis.      <P>
Lemma 29.1 implies that we can compute each carry bit <I>c<SUB>i</I></SUB> by computing each carry status <I>y<SUB>i</I></SUB>. Once we have all the carry bits, we can compute the entire sum in <img src="../images/bound.gif">(1) time by computing in parallel the sum bits <I>s<SUB>i</SUB> = </I>parity (<I>a<SUB>i</SUB>, b<SUB>i</SUB>, c<SUB>i</I></SUB>) for <I>i =</I> 0, 1<I>, . . . , n</I> (taking <I>a<SUB>n</SUB> = b<SUB>n</SUB> </I>= 0). Thus, the problem of quickly adding two numbers reduces to the prefix computation of the carry statuses <I>y</I><SUB>0</SUB><I>, y</I><SUB>1</SUB><I>, . . . ,y<SUB>n</I></SUB>.<P>





<h3>Computing carry statuses with a parallel prefix circuit</h3><P>
<a name="0937_1985"><a name="0937_1986"><a name="0937_1987">By using a prefix circuit that operates in parallel, as opposed to a ripple-carry circuit that produces its outputs one by one, we can compute all <I>n </I>carry statuses <I>y</I><SUB>0</SUB><I>, y</I><SUB>1</SUB><I>, . . . , y<SUB>n</I></SUB> more quickly. Specifically, we shall design a parallel prefix circuit with <I>O(</I>lg<I> n)</I> depth. The circuit has <img src="../images/bound.gif">(<I>n</I>) size--asymptotically the same amount of hardware as a ripple-carry adder.<P>
Before constructing the parallel prefix circuit, we introduce a notation that will aid our understanding of how the circuit operates. For integers <I>i </I>and <I>j</I> in the range <I>0 </I><img src="../images/lteq12.gif"> i <I><img src="../images/lteq12.gif"> j </I><img src="../images/lteq12.gif"> n,<I> we define</I><P>