📄 ch02.16.htm
字号:
1</SUB> )2<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>(B<SUB CLASS="SubscriptVariable">
i</SUB> <SUB CLASS="Subscript"> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>1</SUB>
<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>B<SUB CLASS="SubscriptVariable">
i</SUB> )2<SUP CLASS="SuperscriptVariable"> i<SPAN CLASS="White"> </SPAN></SUP>
+<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SPAN CLASS="EquationVariables">
n</SPAN> <SUB CLASS="Subscript"> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>1</SUB>
2<SUP CLASS="SuperscriptVariable"> n</SUP> <SUP CLASS="Superscript"> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>1</SUP>
<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>B<SUB CLASS="SubscriptVariable">
n</SUB> 2<SUP CLASS="SuperscriptVariable"> n</SUP></P>
<P><P CLASS="EquationAlign"><A NAME="pgfId=168904"></A> =<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>(2B<SUB CLASS="Subscript">
1</SUB> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
0</SUB> )2<SUP CLASS="Superscript"> 0</SUP> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>(2B<SUB CLASS="Subscript">
3</SUB> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
2</SUB> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
1</SUB> )2<SUP CLASS="Superscript"> 2</SUP> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN></P>
<P><P CLASS="EquationAlign"><A NAME="pgfId=168905"></A> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>(2B<SUB CLASS="SubscriptVariable">
i</SUB> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="SubscriptVariable">
i</SUB> <SUB CLASS="Subscript"> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>1</SUB>
<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
i<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>2</SUB>
)2<SUP CLASS="SuperscriptVariable"> i</SUP> <SUP CLASS="Superscript"> <SPAN CLASS="White"> </SPAN>1</SUP>
<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>(2B<SUB CLASS="SubscriptVariable">
i<SPAN CLASS="White"> </SPAN></SUB> <SUB CLASS="Subscript">
<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>2</SUB>
<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="SubscriptVariable">
i<SPAN CLASS="White"> </SPAN></SUB> <SUB CLASS="Subscript"> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>1</SUB>
<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="SubscriptVariable">
i</SUB> <SUB CLASS="Subscript"> <SPAN CLASS="White"> </SPAN></SUB>
)2<SUP CLASS="SuperscriptVariable"> i</SUP> <SUP CLASS="Superscript"> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>1</SUP>
<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN></P>
<P><P CLASS="EqnNmbrdAlign"><A NAME="pgfId=168799"></A> <SPAN CLASS="White"> </SPAN> +<SPAN CLASS="White"> </SPAN>(2B<SUB CLASS="SubscriptVariable">
n</SUB> +<SPAN CLASS="White"> </SPAN>B<SUB CLASS="SubscriptVariable">
i</SUB> <SUB CLASS="Subscript"> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>1</SUB>
<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="SubscriptVariable">
i</SUB> <SUB CLASS="Subscript"> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>2</SUB>
)2<SUP CLASS="SuperscriptVariable"> n</SUP> <SUP CLASS="Superscript"> 1</SUP>
.(2.61)</P>
<P><P CLASS="Body"><A NAME="pgfId=168862"></A>This is very useful. Consider
B<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>101001
(decimal 9<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>32<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>23,
<SPAN CLASS="EquationVariables"> n</SPAN> <SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>5),</P>
<P><P CLASS="EquationAlign"><A NAME="pgfId=168832"></A> B<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>101001<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>(2B<SUB CLASS="Subscript">
1</SUB> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
0</SUB> )2<SUP CLASS="Superscript"> 0</SUP> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>(2B<SUB CLASS="Subscript">
3</SUB> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
2</SUB> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
1</SUB> )2<SUP CLASS="Superscript"> 2</SUP> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>(2B<SUB CLASS="Subscript">
5</SUB> +<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
4</SUB> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
3</SUB> )2<SUP CLASS="Superscript"> 4</SUP></P>
<P><P CLASS="EqnNmbrdAlign"><A NAME="pgfId=168865"></A> = ((2<SPAN CLASS="White"> </SPAN><SPAN CLASS="Symbol">
¥</SPAN> <SPAN CLASS="White"> </SPAN>0)<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>1)2<SUP CLASS="Superscript">
0</SUP> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>((2<SPAN CLASS="White"> </SPAN><SPAN CLASS="Symbol">
¥</SPAN> <SPAN CLASS="White"> </SPAN>1)<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>0<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>0)2<SUP CLASS="Superscript">
2</SUP> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>((2<SPAN CLASS="White"> </SPAN><SPAN CLASS="Symbol">
¥</SPAN> <SPAN CLASS="White"> </SPAN>1)<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>0<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>1)2<SUP CLASS="Superscript">
4</SUP> <SPAN CLASS="White"> </SPAN>.(2.62)</P>
<P><P CLASS="BodyAfterHead"><A NAME="pgfId=169135"></A>Equation 2.61
tells us how to encode B as a radix-4 signed digit, E<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN><IMG SRC=
"CH02-74.gif" ALIGN="BASELINE" WIDTH="21" HEIGHT="18" NATURALSIZEFLAG="3">
(decimal 16<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>8<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>1<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>23).
To multiply by B encoded as E we only have to perform a multiplication by
2 (a shift) and three add/subtract operations.</P>
<P><P CLASS="Body"><A NAME="pgfId=205888"></A>Using Eq. 2.61 we can
encode any number by taking groups of three bits at a time and calculating</P>
<P><P CLASS="EqnNmbrdAlign"><A NAME="pgfId=169139"></A> E<SPAN CLASS="EquationVariables">
j</SPAN> <SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>2B<SUB CLASS="SubscriptVariable">
i</SUB> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="SubscriptVariable">
i</SUB> <SUB CLASS="Subscript"> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>1</SUB>
<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="SubscriptVariable">
i</SUB> <SUB CLASS="Subscript"> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>2</SUB>
, E<SUB CLASS="SubscriptVariable"> j</SUB> <SUB CLASS="Subscript"> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>1</SUB>
<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>2B<SUB CLASS="SubscriptVariable">
i</SUB> <SUB CLASS="Subscript"> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>2</SUB>
<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="SubscriptVariable">
i</SUB> <SUB CLASS="Subscript"> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>1</SUB>
<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="SubscriptVariable">
i</SUB> , .<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>,(2.63)</P>
<P><P CLASS="BodyAfterHead"><A NAME="pgfId=169140"></A>where each 3-bit
group overlaps by one bit. We pad B with a zero, B<SUB CLASS="SubscriptVariable">
n</SUB> <SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
1</SUB> B<SUB CLASS="Subscript"> 0</SUB> 0, to match the first term in Eq. 2.61.
If B has an odd number of bits, then we extend the sign: B<SUB CLASS="SubscriptVariable">
n</SUB> B<SUB CLASS="SubscriptVariable"> n</SUB> <SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>.<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
1</SUB> B<SUB CLASS="Subscript"> 0</SUB> 0. For example, B<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>01011
(eleven), encodes to E<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN><IMG SRC=
"CH02-75.gif" ALIGN="BASELINE" WIDTH="21" HEIGHT="18" NATURALSIZEFLAG="3">
(16<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>4<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>1);
and B<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>101
is E<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN><IMG SRC=
"CH02-76.gif" ALIGN="BASELINE" WIDTH="15" HEIGHT="18" NATURALSIZEFLAG="3">
. This is called <B>Booth encoding</B> and reduces the number of partial
products by a factor of two and thus considerably reduces the area as well
as increasing the speed of our multiplier [Booth, 1951].</P>
<P><P CLASS="Body"><A NAME="pgfId=180381"></A>Next we turn our attention
to improving the speed of addition in the CSA array. Figure 2.28(a)
shows a section of the 6-bit array multiplier from Figure 2.27. We
can collapse the chain of adders a0f5 (5 adder delays) to the <B>Wallace tree</B>
consisting of adders 5.15.4 (4 adder delays) shown in Figure 2.28(b).</P>
<P><TABLE BORDER="0" CELLSPACING="2" CELLPADDING="0">
<TR>
<TD><P CLASS="TableFigure"><A NAME="pgfId=192014"></A><IMG SRC="CH02-77.gif"
ALIGN="BASELINE" WIDTH="448" HEIGHT="388" NATURALSIZEFLAG="3"> </TD></TR>
<TR>
<TD><P CLASS="TableFigureTitle"><A NAME="pgfId=192020"></A>FIGURE 2.28 Tree-based
multiplication. (a) The portion of Figure 2.27 that calculates
the sum bit, P<SUB CLASS="Subscript"> 5</SUB> , using a chain of adders
(cells a0f5). (b) We can collapse this chain to a Wallace tree (cells
5.15.5). (c) The stages of multiplication.</TD></TR>
</TABLE>
<P CLASS="Body"><A NAME="pgfId=181496"></A>Figure 2.28(c) pictorially
represents multiplication as a sort of golf course. Each link corresponds
to an adder. The holes or dots are the outputs of one stage (and the inputs
of the next). At each stage we have the following three choices: (1) sum
three outputs using a full adder (denoted by a box enclosing three dots);
(2) sum two outputs using a half adder (a box with two dots); (3) pass
the outputs directly to the next stage. The two outputs of an adder are
joined by a diagonal line (full adders use black dots, half adders white
dots). The object of the game is to choose (1), (2), or (3) at each stage
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -