📄 ch02.16.htm
字号:
<HTML>
<HEAD>
<META NAME="GENERATOR" CONTENT="Adobe PageMill 2.0 Mac">
<TITLE> 2.6.4 Multipliers</TITLE>
</HEAD><!--#include file="top.html"--><!--#include file="header.html"-->
<P><A NAME="pgfId=167904"></A><HR ALIGN=LEFT></P>
<P><A HREF="CH02.12.htm">Chapter start</A> <A
HREF="CH02.15.htm">Previous page</A> <A HREF="CH02.17.htm">Next page</A></P>
<H2>2.6.4 Multipliers</H2>
<P><P CLASS="BodyAfterHead"><A NAME="pgfId=167910"></A>Figure 2.27
shows a symmetric 6-bit array <B>multiplier</B> (an <SPAN CLASS="EquationVariables">
n</SPAN> -bit multiplier multiplies two <SPAN CLASS="EquationVariables">
n</SPAN> -bit numbers; we shall use <SPAN CLASS="EquationVariables"> n</SPAN>
-bit by <SPAN CLASS="Emphasis"> m</SPAN> -bit multiplier if the lengths
are different). Adders a0f0 may be eliminated, which then eliminates adders
a1a6, leaving an asymmetric CSA array of 30 (5<SPAN CLASS="White"> </SPAN><SPAN CLASS="Symbol">
¥</SPAN> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>6)
adders (including one half adder). An <SPAN CLASS="EquationVariables"> n</SPAN>
-bit array multiplier has a delay proportional to <SPAN CLASS="EquationVariables">
n</SPAN> plus the delay of the CPA (adders b6f6 in Figure 2.27). There
are two items we can attack to improve the performance of a multiplier:
the number of partial products and the addition of the partial products.</P>
<P><TABLE BORDER="0" CELLSPACING="2" CELLPADDING="0">
<TR>
<TD><P CLASS="TableFigure"><A NAME="pgfId=169274"></A><IMG SRC="CH02-69.gif"
ALIGN="BASELINE" WIDTH="448" HEIGHT="470" NATURALSIZEFLAG="3"> </TD></TR>
<TR>
<TD><P CLASS="TableFigureTitle"><A NAME="pgfId=169277"></A>FIGURE 2.27 Multiplication.
A 6-bit array multiplier using a final carry-propagate adder (full-adder
cells a6f6, a ripple-carry adder). Apart from the generation of the summands
this multiplier uses the same structure as the carry-save adder of Figure 2.23(d).</TD></TR>
</TABLE>
<P CLASS="Body"><A NAME="pgfId=215738"></A>Suppose we wish to multiply 15
(the <B>multiplicand</B> ) by 19 (the <B>multiplier</B> ) mentally. It is
easier to calculate 15<SPAN CLASS="White"> </SPAN>¥<SPAN CLASS="White"> </SPAN>20
and subtract 15. In effect we complete the multiplication as 15<SPAN CLASS="White"> </SPAN>¥<SPAN CLASS="White"> </SPAN>(20<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>1)
and we could write this as 15<SPAN CLASS="White"> </SPAN>¥<SPAN CLASS="White"> </SPAN><IMG SRC=
"CH02-70.gif" ALIGN="BASELINE" WIDTH="15" HEIGHT="18" NATURALSIZEFLAG="3">
, with the overbar representing a minus sign. Now suppose we wish to multiply
an 8-bit binary number, A, by B<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>00010111
(decimal 16<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>4<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>2<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>1<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>23).
It is easier to multiply A by the canonical signed-digit vector<B> </B>(<B>
CSD vector</B> ) D<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN><IMG SRC=
"CH02-71.gif" ALIGN="BASELINE" WIDTH="47" HEIGHT="18" NATURALSIZEFLAG="3">
(decimal <SPAN CLASS="White"> </SPAN>32<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) since this requires only three add or subtract operations (and a subtraction
is as easy as an addition). We say B has a <B>weight</B> of 4 and D has
a weight of 3. By using D instead of B we have reduced the number of partial
products by 1 (=<SPAN CLASS="White"> </SPAN>4<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>3).</P>
<P><P CLASS="Body"><A NAME="pgfId=215750"></A>We can <B>recode</B> (or encode)
any binary number, B, as a CSD vector, D, as follows (canonical means there
is only one CSD vector for any number):</P>
<P><P CLASS="EqnNmbrdAlign"><A NAME="pgfId=168527"></A> D<SUB CLASS="SubscriptVariable">
i</SUB> <SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>B<SUB CLASS="SubscriptVariable">
i</SUB> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>C<SUB CLASS="SubscriptVariable">
i</SUB> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>2C<SUB CLASS="SubscriptVariable">
i</SUB> <SUB CLASS="Subscript"> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>1</SUB>
,(2.58)</P>
<P><P CLASS="BodyAfterHead"><A NAME="pgfId=168561"></A>where C<SUB CLASS="SubscriptVariable">
i</SUB> <SUB CLASS="Subscript"> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>1</SUB>
is the carry from the sum of 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> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>C<SUB CLASS="SubscriptVariable">
i</SUB> (we start with C<SUB CLASS="Subscript"> 0</SUB> <SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>0).</P>
<P><P CLASS="Body"><A NAME="pgfId=168566"></A>As another example, if B<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>011
(B<SUB CLASS="Subscript"> 2</SUB> <SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>0,
B<SUB CLASS="Subscript"> 1</SUB> <SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>1,
B<SUB CLASS="Subscript"> 0</SUB> <SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>1;
decimal 3), then, using Eq. 2.58,</P>
<P><P CLASS="EquationAlign"><A NAME="pgfId=168562"></A> D<SUB CLASS="Subscript">
0</SUB> <SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
0</SUB> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>C<SUB CLASS="Subscript">
0</SUB> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>2C<SUB CLASS="Subscript">
1</SUB> <SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>1<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>0<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>2<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN><IMG SRC=
"CH02-72.gif" ALIGN="BASELINE" WIDTH="9" HEIGHT="18" NATURALSIZEFLAG="3">
,</P>
<P><P CLASS="EquationAlign"><A NAME="pgfId=168576"></A> D<SUB CLASS="Subscript">
1</SUB> <SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
1</SUB> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>C<SUB CLASS="Subscript">
1</SUB> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>2C<SUB CLASS="Subscript">
2</SUB> <SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>1<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>1<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>2<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>0,</P>
<P><P CLASS="EqnNmbrdAlign"><A NAME="pgfId=168571"></A> D<SUB CLASS="Subscript">
2</SUB> <SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
2</SUB> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>C<SUB CLASS="Subscript">
2</SUB> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>2C<SUB CLASS="Subscript">
3</SUB> <SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>0<SPAN CLASS="White"> </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.59)</P>
<P><P CLASS="BodyAfterHead"><A NAME="pgfId=168605"></A>so that D<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN><IMG SRC=
"CH02-73.gif" ALIGN="BASELINE" WIDTH="21" HEIGHT="18" NATURALSIZEFLAG="3">
(decimal 4<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>1<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>3).
CSD vectors are useful to represent fixed coefficients in digital filters,
for example.</P>
<P><P CLASS="Body"><A NAME="pgfId=168645"></A>We can recode using a <B>radix</B>
other than 2. Suppose B is an (<SPAN CLASS="EquationVariables"> n<SPAN CLASS="White"> </SPAN></SPAN>
+<SPAN CLASS="White"> </SPAN>1)-digit two's
complement number,</P>
<P><P CLASS="EqnNmbrdAlign"><A NAME="pgfId=168646"></A> B<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
0</SUB> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
1</SUB> 2<SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
2</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><SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>B<SPAN CLASS="EquationVariables">
i</SPAN> 2<SUP CLASS="SuperscriptVariable"> i<SPAN CLASS="White"> </SPAN></SUP>
+<SPAN CLASS="EquationVariables"> <SPAN CLASS="White"> </SPAN></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">
n</SUB> <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> .(2.60)</P>
<P><P CLASS="Body"><A NAME="pgfId=168859"></A>We can rewrite the expression
for B using the following sleight-of-hand:</P>
<P><P CLASS="EquationAlign"><A NAME="pgfId=168648"></A> 2B<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>B<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>B<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
0</SUB> <SPAN CLASS="White"> </SPAN>+<SPAN CLASS="White"> </SPAN>(B<SUB CLASS="Subscript">
0</SUB> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>B<SUB CLASS="Subscript">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -