📄 ch02.17.htm
字号:
"CH02-103.gif" ALIGN="BASELINE" WIDTH="10" HEIGHT="16" NATURALSIZEFLAG=
"3"> or B[i<SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>1]=<IMG SRC=
"CH02-104.gif" ALIGN="BASELINE" WIDTH="10" HEIGHT="16" NATURALSIZEFLAG=
"3"> </CODE></TD>
<TD><P CLASS="Table"><A NAME="pgfId=199060"></A><CODE>1</CODE></TD>
<TD><P CLASS="Table"><A NAME="pgfId=199062"></A><CODE>0</CODE></TD></TR>
<TR>
<TD><P CLASS="Table"><A NAME="pgfId=199064"></A>1</TD>
<TD><P CLASS="Table"><A NAME="pgfId=199066"></A>1</TD>
<TD><P CLASS="Table"><A NAME="pgfId=199068"></A>x</TD>
<TD><P CLASS="Table"><A NAME="pgfId=199070"></A>x</TD>
<TD><P CLASS="Table"><A NAME="pgfId=199072"></A>0</TD>
<TD><P CLASS="Table"><A NAME="pgfId=199074"></A>1</TD></TR>
</TABLE>
<P CLASS="Body"><A NAME="pgfId=197466"></A>The redundant binary representation
is not unique. We can represent 101 (decimal), for example, by <IMG SRC=
"CH02-105.gif" ALIGN="BASELINE" WIDTH="39" HEIGHT="14" NATURALSIZEFLAG=
"3"> (binary and CSD vector) or <IMG SRC="CH02-106.gif" ALIGN="BASELINE"
WIDTH="49" HEIGHT="18" NATURALSIZEFLAG="3"> . As another example, 188 (decimal)
can be represented by <IMG SRC="CH02-107.gif" ALIGN="BASELINE" WIDTH="44"
HEIGHT="14" NATURALSIZEFLAG="3"> (binary), <IMG SRC="CH02-108.gif" ALIGN=
"BASELINE" WIDTH="54" HEIGHT="18" NATURALSIZEFLAG="3"> , <IMG SRC="CH02-109.gif"
ALIGN="BASELINE" WIDTH="54" HEIGHT="18" NATURALSIZEFLAG="3"> , or <IMG SRC=
"CH02-110.gif" ALIGN="BASELINE" WIDTH="54" HEIGHT="18" NATURALSIZEFLAG=
"3"> (CSD vector). Redundant binary addition of binary, redundant binary,
or CSD vectors does not result in a unique sum, and addition of two CSD
vectors does not result in a CSD vector. Each <SPAN CLASS="EquationVariables">
n</SPAN> -bit redundant binary number requires a rather wasteful 2<SPAN CLASS="EquationVariables">
n</SPAN> -bit binary number for storage. Thus <IMG SRC="CH02-111.gif" ALIGN=
"BASELINE" WIDTH="21" HEIGHT="18" NATURALSIZEFLAG="3"> is represented as
010010, for example (using sign magnitude). The other disadvantage of redundant
binary arithmetic is the need to convert to and from binary representation.</P>
<P><P CLASS="Body"><A NAME="pgfId=198881"></A>Table 2.14 shows the
(5, 3) <B>residue number system</B> . As an example, 11 (decimal) is represented
as [1, 2] residue (5, 3) since 11R<SUB CLASS="Subscript"> 5</SUB>
<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>11
mod 5<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>1
and 11R<SUB CLASS="Subscript"> 3</SUB> <SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>11
mod 3<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>2.
The size of this system is thus 3<SPAN CLASS="White"> </SPAN><SPAN CLASS="Symbol">
¥</SPAN> <SPAN CLASS="White"> </SPAN>5<SPAN CLASS="White"> </SPAN>=<SPAN CLASS="White"> </SPAN>15.
We add, subtract, or multiply residue numbers using the modulus of each
bit positionwithout any carry. Thus:</P>
<P><SPAN CLASS="ComputerFirst"> <A NAME="pgfId=197386"></A>
4 [4, 1]
12 [2, 0]
3 [3, 0]</SPAN>
<SPAN CLASS="Computer"> <A NAME="pgfId=197387"></A> + 7 + [2,
1]
4 [4, 1] <SPAN CLASS="Symbol">
¥</SPAN> 4 <SPAN CLASS="Symbol">
¥</SPAN> [4, 1]</SPAN> <SPAN CLASS="Computer"> <A NAME="pgfId=197388"></A> = 11 = [1,
2] = 8 = [3,
2] = 12 = [2,
0]</SPAN> <TABLE BORDER="0" CELLSPACING="2" CELLPADDING="0">
<TR>
<TD COLSPAN="9"><P CLASS="TableTitle"><A NAME="pgfId=196788"></A>TABLE 2.14 The
5, 3 residue number system.</TD></TR>
<TR>
<TD><P CLASS="Table"><A NAME="pgfId=196813"></A>n</TD>
<TD><P CLASS="Table"><A NAME="pgfId=196848"></A>residue 5</TD>
<TD><P CLASS="Table"><A NAME="pgfId=196850"></A>residue 3</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197102"></A>n</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197104"></A>residue 5</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197106"></A>residue 3</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197204"></A>n</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197206"></A>residue 5</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197208"></A>residue 3</TD></TR>
<TR>
<TD><P CLASS="Table"><A NAME="pgfId=196936"></A>0</TD>
<TD><P CLASS="Table"><A NAME="pgfId=196938"></A>0</TD>
<TD><P CLASS="Table"><A NAME="pgfId=196940"></A>0</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197300"></A>5</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197302"></A>0</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197304"></A>2</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197330"></A>10</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197332"></A>0</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197334"></A>1</TD></TR>
<TR>
<TD><P CLASS="Table"><A NAME="pgfId=196930"></A>1</TD>
<TD><P CLASS="Table"><A NAME="pgfId=196932"></A>1</TD>
<TD><P CLASS="Table"><A NAME="pgfId=196934"></A>1</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197306"></A>6</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197308"></A>1</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197310"></A>0</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197336"></A>11</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197338"></A>1</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197340"></A>2</TD></TR>
<TR>
<TD><P CLASS="Table"><A NAME="pgfId=196924"></A>2</TD>
<TD><P CLASS="Table"><A NAME="pgfId=196926"></A>2</TD>
<TD><P CLASS="Table"><A NAME="pgfId=196928"></A>2</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197312"></A>7</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197314"></A>2</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197316"></A>1</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197342"></A>12</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197344"></A>2</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197346"></A>0</TD></TR>
<TR>
<TD><P CLASS="Table"><A NAME="pgfId=196918"></A>3</TD>
<TD><P CLASS="Table"><A NAME="pgfId=196920"></A>3</TD>
<TD><P CLASS="Table"><A NAME="pgfId=196922"></A>0</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197318"></A>8</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197320"></A>3</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197322"></A>2</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197348"></A>13</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197350"></A>3</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197352"></A>1</TD></TR>
<TR>
<TD><P CLASS="Table"><A NAME="pgfId=196912"></A>4</TD>
<TD><P CLASS="Table"><A NAME="pgfId=196914"></A>4</TD>
<TD><P CLASS="Table"><A NAME="pgfId=196916"></A>1</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197324"></A>9</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197326"></A>4</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197328"></A>0</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197354"></A>14</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197356"></A>4</TD>
<TD><P CLASS="Table"><A NAME="pgfId=197358"></A>2</TD></TR>
</TABLE>
<P CLASS="BodyAfterHead"><A NAME="pgfId=197407"></A>The choice of moduli
determines the system size and the computing complexity. The most useful
choices are relative primes (such as 3 and 5). With <SPAN CLASS="EquationVariables">
p</SPAN> prime, numbers of the form 2<SPAN CLASS="EquationVariables"> p</SPAN>
and 2<SUP CLASS="Superscript"> p</SUP> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>1
are particularly useful (2<SUP CLASS="Superscript"> p</SUP> <SPAN CLASS="White"> </SPAN><SPAN CLASS="White"> </SPAN>1
are <B>Mersenne's numbers</B> ) [Waser and Flynn, 1982].</P>
<P><HR ALIGN=LEFT></P>
<P><A HREF="CH02.12.htm">Chapter start</A> <A
HREF="CH02.16.htm">Previous page</A> <A HREF="CH02.18.htm">Next page</A>
</BODY>
<!--#include file="Copyright.html"--><!--#include file="footer.html"-->
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -