chap29.htm

介绍算法的书籍

<a name="093a_1998">29.2-6<a name="093a_1998"><P>
Give a recursive block diagram of the circuit in Figure 29.12 for any number <I>n</I> of inputs that is an exact power of 2. Argue on the basis of your block diagram that the circuit indeed performs a prefix computation. Show that the depth of the circuit is <img src="../images/bound.gif">(lg <I>n</I>) and that it has <img src="../images/bound.gif">(<I>n </I>lg <I>n</I>) size.<P>
<a name="093a_1999">29.2-7<a name="093a_1999"><P>
What is the maximum fan-out of any wire in the carry-lookahead adder? Show that addition can still be performed in <I>O</I>(lg <I>n</I>) time by a <img src="../images/bound.gif">(<I>n</I>)-size circuit even if we restrict gates to have <I>O</I>(1) fan-out.<P>
<a name="093a_199a">29.2-8<a name="093a_199a"><P>
<a name="093a_198e"><a name="093a_198f">A <I><B>tally circuit</I> </B>has <I>n</I> binary inputs and <I>m</I> = <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrul14.gif"></FONT>lg(<I>n </I>+ 1)<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrur14.gif"> </FONT>outputs. Interpreted as a binary number, the outputs give the number of 1's in the inputs. For example, if the input is <img src="../images/lftwdchv.gif">10011110<img src="../images/wdrtchv.gif">, the output is <img src="../images/lftwdchv.gif">101<img src="../images/wdrtchv.gif">, indicating that there are five 1's in the input. Describe an <I>O</I>(lg <I>n</I>)-depth tally circuit having <img src="../images/bound.gif">(<I>n</I>) size.<P>
<a name="093a_199b">29.2-9<a name="093a_199b"><P>
Show that <I>n</I>-bit addition can be accomplished with a combinational circuit of depth 4 and size polynomial in <I>n</I> if AND and OR gates are allowed arbitrarily high fan-in. (<I>Optional:</I> Achieve depth 3.)<P>
<a name="093a_199c">29.2-10<a name="093a_199c"><P>
<a name="093a_1990">Suppose that two random <I>n</I>-bit numbers are added with a ripple-carry adder, where each bit is independently 0 or 1 with equal probability. Show that with probability at least 1 - 1/<I>n</I>, no carry propagates farther than <I>O</I>(1g <I>n</I>) consecutive stages. In other words, although the depth of the ripple-carry adder is <img src="../images/bound.gif">(<I>n</I>), for two random numbers, the outputs almost always settle within <I>O</I>(lg <I>n</I>) time.<P>
<P>


<P>







<h1><a name="093b_1997">29.3 Multiplication circuits<a name="093b_1997"></h1><P>
<a name="093b_1991"><a name="093b_1992"><a name="093b_1993"><a name="093b_1994">The &quot;grade-school&quot; multiplication algorithm in Figure 29.13 can compute the 2<I>n</I>-bit product <I>p</I> = <img src="../images/lftwdchv.gif"><I>p</I><SUB>2<I>n</I>-1</SUB>, <I>p</I><SUB>2<I>n</I>-2</SUB>, . . . . , <I>p</I><SUB>0</SUB><img src="../images/wdrtchv.gif"> of 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"><I>b<SUB>n</I>-1</SUB>, <I>b<SUB>n</I>-2</SUB>, . . . , <I>b</I><SUB>0</SUB><img src="../images/wdrtchv.gif">. We examine the bits of <I>b</I>, from <I>b</I><SUB>0 </SUB>up to <I>b<SUB>n</I>-1</SUB>. For each bit <I>b<SUB>i</I> </SUB>with a value of 1, we add <I>a</I> into the product, but shifted left by <I>i</I> positions. For each bit <I>b<SUB>i</I> </SUB>with a value of 0, we add in 0. Thus, letting <I>m</I><SUP>(<I>i</I>) </SUP>= <I>a</I> <SUP>.</SUP> <I>b<SUB>i</I></SUB> <SUP>.</SUP> 2<I><SUP>i</I></SUP>, we compute<P>
<img src="671_a.gif"><P>
<a name="093b_1995"><a name="093b_1996">Each term <I>m</I><SUP>(<I>i</I>) </SUP>is called a <I><B>partial product</I></B>. There are <I>n</I> partial products to sum, with bits in positions 0 to 2<I>n</I> - 2. The carry-out from the highest bit yields the final bit in position 2<I>n</I> - 1.<P>
In this section, we examine two circuits for multiplying two <I>n</I>-bit numbers. Array multipliers operate in <img src="../images/bound.gif">(<I>n</I>) time and have <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) size. Wallace-tree multipliers also have <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) size, but they operate in <img src="../images/bound.gif">(lg <I>n</I>) time. Both circuits are based on the grade-school algorithm.<P>
<pre>            1  1  1  0  =  <I>a</I></sub></sup></pre><P>
<pre>            1  1  0  1  =  <I>b</I></sub></sup></pre><P>
<pre>-------------------------------</sub></sup></pre><P>
<pre>            1  1  1  0  =  <I>m</I><SUP>(0)</sub></sup></pre><P>
<pre>         0  0  0  0     =  <I>m</I><SUP>(1)</sub></sup></pre><P>
<pre>      1  1  1  0        =  <I>m</I><SUP>(2)</sub></sup></pre><P>
<pre>   1  1  1  0           =  <I>m</I><SUP>(3)</sub></sup></pre><P>
<pre>-------------------------------</sub></sup></pre><P>
<pre>1  0  1  1  0  1  1  0  =  <I>p</I></sub></sup></pre><P>
<h4><a name="093b_1998">Figure 29.13 The &quot;grade-school&quot; multiplication method, shown here multiplying a = <img src="../images/lftwdchv.gif">1110<img src="../images/wdrtchv.gif"> by b = <img src="../images/lftwdchv.gif">1101<img src="../images/wdrtchv.gif"> to obtain the product p = <img src="../images/lftwdchv.gif">10110110<img src="../images/wdrtchv.gif">. We add <img src="672_a.gif">, where m<SUP>(i) </SUP><FONT FACE="Times New Roman" SIZE=2>= a <img src="../images/dot10.gif"> b<SUB>i </SUB><img src="../images/dot10.gif"><FONT FACE="Times New Roman" SIZE=2><SUB> </SUB><FONT FACE="Times New Roman" SIZE=2>2<SUP>i</SUP>. </FONT></FONT></FONT>Here, n = 8. Each term m<SUP>(i) </SUP>is formed by shifting either a (if b<SUB>i</SUB> = 1 ) or 0 (if b<SUB>i</SUB> = 0) i positions to the left. Bits that are not shown are 0 regardless of the values of a and b.<a name="093b_1998"></sub></sup></h4><P>





<h2><a name="093c_1999">29.3.1 Array multipliers<a name="093c_1999"></h2><P>
<a name="093c_1997"><a name="093c_1998">An array multiplier consists conceptually of three parts. The first part forms the partial products. The second sums the partial products using carry-save adders. Finally, the third sums the two numbers resulting from the carry-save additions using either a ripple-carry or carry-lookahead adder.<P>
Figure 29.14 shows an <I><B>array multiplier </I></B>for two input 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"><I>b<SUB>n</I>-1</SUB>, <I>bn</I>-<SUB>2</SUB>, . . . , <I>b</I><SUB>0</SUB><img src="../images/wdrtchv.gif">. The <I>a<SUB>j</I> </SUB>values run vertically, and the <I>b<SUB>i</I></SUB> values run horizontally. Each input bit fans out to <I>n </I>AND gates to form partial products. Full adders, which are organized as carry-save adders, sum partial products. The lower-order bits of the final product are output on the right. The higher-order bits are formed by adding the two numbers output by the last carry-save adder.<P>
Let us examine the construction of the array multiplier more closely. Given the two input 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"><I>b<SUB><FONT FACE="Courier New" SIZE=2>n-</I>1</FONT></SUB>, <I>b<SUB><FONT FACE="Courier New" SIZE=2>n-</I>2</FONT></SUB>, . . . , <I>b</I><SUB><FONT FACE="Courier New" SIZE=2>0</SUB><img src="../images/wdrtchv.gif"></FONT>, the bits of the partial products are easy to compute. Specifically, for <I>i</I>, <I>j</I> = 0, 1, . . . , <I>n </I>- 1, we have<P>
<img src="672_b.gif"><P>
Since the product of 1-bit values can be computed directly with an AND gate, all the bits of the partial products (except those known to be 0, which need not be explicitly computed) can be produced in one step using <I>n</I><SUP>2<I> </I></SUP>AND gates.<P>
Figure 29.15 illustrates how the array multiplier performs the carry-save additions when summing the partial products in Figure 29.13. It starts by carry-save adding <I>m</I><SUP>(0)</SUP>, <I>m</I><SUP>(1)</SUP>, and 0, yielding an (<I>n</I> + 1)-bit number <I>u</I><SUP>(1) </SUP>and an (<I>n</I> + 1)-bit number <I>v</I><SUP>(1)</SUP>. (The number <I>v</I><SUP>(1)</SUP> has only <I>n</I> + 1 bits, not <I>n</I> + 2, because the (<I>n</I> + 1)st bits of both 0 and <I>m</I><SUP>(0)</SUP> are 0.) Thus, <I>m</I><SUP>(0)</SUP> + <I>m</I><SUP>(1)</SUP> = <I>u</I><SUP>(1)</SUP> + <I>v</I><SUP>(1)</SUP>. It then carry-save adds <I>u</I><SUP>(1),</SUP> <I>v</I><SUP>(1)</SUP>, and <I>m</I><SUP>(2)</SUP>, yielding an (<I>n</I> + 2)-bit number <I>u</I><SUP>(2)</SUP> and an (<I>n</I> + 2)-bit number <I>v</I><SUP>(2)</SUP>. (Again, <I>v</I><SUP>(2) </SUP>has only <I>n</I> + 2 bits because both <img src="674_c.gif"> and <img src="674_d.gif"> are 0.) We then have <I>m</I><SUP>(0)</SUP> + <I>m</I><SUP>(1)</SUP> + <I>m</I><SUP>(2)</SUP> = <I>u</I><SUP>(2)</SUP> + <I>v</I><SUP>(2)</SUP>. The multiplier continues on, carry-save adding <I>u</I><SUP>(<I>i</I>-1), </SUP><I>v</I><SUP>(i-1)</SUP>, and <I>m</I><SUP>(<I>i</I>) </SUP>for <I>i</I> = 2, 3, . . . , <I>n</I> - 1. The result is a (2<I>n</I> - 1)-bit number <I>u</I><SUP>(<I>n </I>- l)</SUP> and a (2<I>n </I>- 1)-bit number <I>v</I><SUP>(<I>n </I>- 1)</SUP>, where<P>
<img src="674_e.gif"><P>
<img src="673_a.gif"><P>
<h4><a name="093c_199a">Figure 29.14 An array multiplier that computes the product p = <img src="../images/lftwdchv.gif">p<SUB>2n-1,</SUB>p<SUB>2n-2, . . . , </SUB>p<SUB>0</SUB><img src="../images/wdrtchv.gif"> of two n-bit numbers a = <img src="../images/lftwdchv.gif">a<SUB>n-1</SUB>,a<SUB>n-2</SUB>, . . . ,a<SUB>0</SUB><img src="../images/wdrtchv.gif"> and b = <img src="../images/lftwdchv.gif">b<SUB><FONT FACE="Courier New" SIZE=2>n-1</SUB>,b<SUB><FONT FACE="Courier New" SIZE=2>n-2</SUB>, . . . , b<SUB><FONT FACE="Courier New" SIZE=2>0</SUB><img src="../images/wdrtchv.gif"></FONT><SUP></SUP><SUP></SUP><SUP></SUP><SUP></FONT></SUP>, shown here for n = 4. Each AND gate <img src="673_b.gif"><SUP> </SUP>computes partial-product bit <img src="673_c.gif">.<SUP> </SUP></FONT>Each row of full adders constitutes a carry-save adder. The lower n bits of the product are <img src="673_d.gif">and the u bits coming out from the rightmost column of full adders. The upper n product bits are formed by adding the u and v bits coming out from the bottom row of full adders. Shown are bit values for inputs a = <img src="../images/lftwdchv.gif">1110<img src="../images/wdrtchv.gif"> and b = <img src="../images/lftwdchv.gif">1101<img src="../images/wdrtchv.gif"> and product p = <img src="../images/lftwdchv.gif">10110110<img src="../images/wdrtchv.gif">, corresponding to Figures 29.13 and 29.15.<a name="093c_199a"></sub></sup></h4><P>
<pre>            0  0  0  0  =  0</sub></sup></pre><P>
<pre>            1  1  1  0  =  <I>m</I><SUP>(0)</sub></sup></pre><P>
<pre>         0  0  0  0     =  <I>m</I><SUP>(1)</sub></sup></pre><P>
<pre>-------------------------------</sub></sup></pre><P>
<pre>         0  1  1  1  0  =  <I>u</I><SUP>(1)</sub></sup></pre><P>
<pre>         0  0  0        =  <I>v</I><SUP>(1)</sub></sup></pre><P>
<pre>      1  1  1  0        =  <I>m</I><SUP>(2)</sub></sup></pre><P>
<pre>-------------------------------</sub></sup></pre><P>
<pre>      1  1  0  1  1  0  =  <I>u</I><SUP>(2)</sub></sup></pre><P>
<pre>      0  1  0           =  <I>v</I><SUP>(2)</sub></sup></pre><P>
<pre>   1  1  1  0           =  <I>m</I><SUP>(3)</sub></sup></pre><P>
<pre>-------------------------------</sub></sup></pre><P>
<pre>   1  0  1  0  1  1  0  =  <I>u</I><SUP>(3)</sub></sup></pre><P>
<pre>   1  1  0              =  <I>v</I><SUP>(3)</sub></sup></pre><P>
<pre>-------------------------------</sub></sup></pre><P>
<pre>1  0  1  1  0  1  1  0  =  <I>p</I></sub></sup></pre><P>
<h4><a name="093c_199b">Figure 29.15 Evaluating the sum of the partial products by repeated carry-save addition. For this example, a = <img src="../images/lftwdchv.gif">1110<img src="../images/wdrtchv.gif"> and b = <img src="../images/lftwdchv.gif">1101<img src="../images/wdrtchv.gif"> . Bits that are blank are 0 regardless of the values of a and b. We first evaluate m<SUP>(0)</SUP> + m<SUP>(1)</SUP> + 0 = u<SUP>(1)</SUP> + v<SUP>(1)</SUP> then u<SUP>(1)</SUP> + v<SUP>(1)</SUP>+ m<SUP>(2)</SUP> = u<SUP>(2)</SUP> + v<SUP>(2)</SUP>, then u<SUP>(2)</SUP> + v<SUP>(2)</SUP> + m<SUP>(3)</SUP> = u<SUP>(3)</SUP> + v<SUP>(3),</SUP> and finally p = m<SUP>(0)</SUP> + m<SUP>(1)</SUP> + m<SUP>(2)</SUP> + m<SUP>(3)</SUP> = u<SUP>(3)</SUP> + v<SUP>(3) </SUP>Note that <img src="674_a.gif"> and <img src="674_b.gif"> for i = 1, 2, . . . , n - 1.<a name="093c_199b"></sub></sup></h4><P>
In fact, the carry-save additions in Figure 29.15 operate on more bits than strictly necessary. Observe that for <I>i</I> = 1, 2, . . . , <I>n</I> - 1 and <I>j </I>= 0, 1, . . . , <I>i </I>- 1, we have <img src="674_f.gif"> because of how we shift the partial products. Observe also that <img src="674_g.gif"> for <I>i</I> = 1, 2, . . . , <I>n </I>- 1 and <I>j</I> = 0, 1, . . . , <I>i,</I> <I>i</I> + <I>n</I>, i + <I>n</I> + 1, . . . , 2<I>n</I> - 1. (See Exercise 29.3-1.) Each carry-save addition, therefore, needs to operate on only <I>n</I> - 1 bits.<P>
Let us now examine the correspondence between the array multiplier and the repeated carry-save addition scheme. Each AND gate is labeled by <img src="674_h.gif"> for some <I>i</I> and <I>j</I> in the ranges 0 <img src="../images/lteq12.gif"> <I>i</I> <img src="../images/lteq12.gif"> <I>n</I> - 1 and 0 <img src="../images/lteq12.gif"> <I>j</I> <img src="../images/lteq12.gif"> 2<I>n</I> - 2. Gate <img src="674_i.gif"><SUB> </SUB>produces <img src="674_j.gif">, the <I>j</I>th bit of the <I>i</I>th partial product. For <I>i</I> = 0, 1, . . . , <I>n</I