数据与文字的表示方法
数据格式
在计算机中对数据进行表示实际上使用计算机中的高低电平对现实中的数据进行表示,例如如果想表示现实中的自然数,我们知道计算机中的数据是用二进制来表示的,每一个位表示一个二进制位,计算机能够表示的最大数字取决于计算机的容量,但无论如何计算机的容量是有限的,用有限模拟无限这是不可能的,如果要表示的数据是整数,这些存储空间表示的数字一定在一个有限的范围中,在表示实数时也是同理,因为有限不能表示无限所以在表示实数的时候存在精度问题。
所以在计算机表示数的时候要考虑下面几个因素:
- 要表示数的类型
- 可能的数值范围
- 数值精确度
- 数据存储和处理所需要的硬件代价
计算机中常用的数据表示有两种,一种是定点格式(小数点的位置固定),另一种是浮点格式(小数点的位置可以浮动)
定点格式
因为小数点的位置固定不变,所以就不需要在对小数点有额外的关注,小数点的位置固定在哪一位都可以。
例如
… | … | … | … | 整数第一位 | 小数点后第一位 | … | … |
---|
假设将小数点固定在第三位上,那么小数点之后的位数就固定了,在表示数字的时候小数部分按照小数部分的转化规则来,整数部分按照整数部分的转化规则来就行
例如
1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
---|
此数表示的是
1
∗
2
4
+
1
∗
2
3
+
1
∗
2
−
1
+
1
∗
2
−
3
=
16
+
8
+
0.5
+
0.125
=
24.625
1*2^4+1*2^3+1*2^{-1}+1*2^{-3} = 16+8+0.5+0.125=24.625
1∗24+1∗23+1∗2−1+1∗2−3=16+8+0.5+0.125=24.625
可以看出整个数字的能够表示的最小精度为
2
−
3
2^{-3}
2−3因为你可以在任何位置进行数字的增加,但是最小的增加一定是
2
−
3
2^{-3}
2−3的整数倍,所以可以看出来定点数的精度是固定的。
通过将小数点固定在最右侧可以表示纯整数,通过将小数点固定在最左侧可以表示纯小数。
浮点格式
在我们常用的科学计数法中,我们会将下面的数进行转换成更简单的表示方法,如
1652000000
301200000000000000
1652000000\\ 301200000000000000
1652000000301200000000000000
我们在科学计数法中是可以表示为
1.652
∗
1
0
9
3.012
∗
1
0
17
1.652*10^9\\ 3.012*10^{17}
1.652∗1093.012∗1017
我们可以看到在上面的例子中可以看到尽管两个数的大小相差甚远,但是通过化成科学计数法的形式,变成了一个数乘于一个指数的形式,而且表示起来更加的简单,在计算机中浮点形式的数字就是基于这种表示的方法进行表示的。
将一个数字的有效数字和数的范围在计算机的一个存储单元中分别进行表示,这种把数的范围和精度分别表示的方法,相当于数的小数点位置随比例因子的不同而在一定范围内可以自由浮动,所以称之为浮点表示法。
在计算机中都按照二进制进行表示,所以数字要化成
y
∗
2
x
y * 2^{x}
y∗2x这种形式其中y是一个二进制数称为尾数,x也是一个二进制数称为阶码。
所以一个浮点数组成部分如下:
阶符(阶码的符号) | 阶码 | 数符(数的符号) | 尾数 |
---|
十进制数串的表示方法
字符串形式
每一个字节存放一个十进制的数位或符号位,在主存中,这样的一个十进制数占用连续的多字节,故为了指明这样一个数,需要给出该数在主存中的起始地址和串的长度。
压缩的十进制数串形式
因为1个字节表示八个二进制位,而一个十进制位需要四个二进制位就能进行表示,因此可以在一个字节中存放两个十进制的数位,这种形式比字符串形式的存储方式节省存储空间,又便于直接完成十进制数的算术运算,是较为理想的方法。
与字符串表示形式类似,要知名一个压缩的十进制数串,也得给出它在主存中的首地址和数字位个数。
数的机器码表示
在计算机中要对数据进行运算,对数据运算如何综合考虑数据的表示形式与各种运算的关系,就产生了各种数的表示方法,如原码、补码、反码、移码。为了区别一般书写表示的数和机器中这些编码表示的数将前者称为真值,后者称为机器码。
原码表示法
若定点整数的原码形式为
x
n
x
n
−
1
x
n
−
2
.
.
.
x
1
x
0
x_nx_{n-1}x_{n-2}...x_{1}x_{0}
xnxn−1xn−2...x1x0(注
x
n
x_n
xn为符号位)则原码表示的定义为
[
x
]
原
=
{
x
0
≤
x
<
2
n
2
n
−
x
=
2
n
+
∣
x
∣
−
2
n
<
x
≤
0
[x]_{原}=\begin{cases}x&&0\leq x<2^n\\ 2^n-x = 2^n + |x| && -2^n<x\leq 0 \end{cases}
[x]原={x2n−x=2n+∣x∣0≤x<2n−2n<x≤0
上面定义的意思就是如果一个数的真值大于等于0则在机器码中的表示直接用真值表示即可,如果一个数的真值小于等于0需要用
2
n
+
∣
x
∣
2^n + |x|
2n+∣x∣表示,即在将真值转化为绝对值之后表示,然后在最高位取1进行表示。
例如:
真值:+1001,则
[
x
]
原
=
01001
[x]_{原}=01001
[x]原=01001
真值:-1001,则
[
x
]
原
=
11001
[x]_{原}=11001
[x]原=11001
在原码表示法中我们易于发现对于0这个数的表示似乎有+0和-0之分,因为0按照定义两个表示都可以。
在原码表示法中加法运算复杂,所以人们提出了补码表示方法
补码表示方法
在补码表示法中人们利用了循环的性质,利用取余操作,人们可以实现数的循环,比如下式在取余运算中是成立的
−
3
=
+
9
(
m
o
d
12
)
-3 = +9(mod 12)
−3=+9(mod12)
也就是说在取模的概念下-3和9是等价的,如果我们用8加上-3,理应得到一个5,但是如果我们使用8+9然后对12进行取模我们也会得到9,也就是说在取模的概念下可以将减法转换为加法。
在取模的概念下一旦超出模的范围就会被自动丢掉,这与计算机中的数据表示天然契合,在计算机中一旦超出最高位,超出的部分就会被丢掉。
若定点整数的原码形式为
x
n
x
n
−
1
x
n
−
2
.
.
.
x
1
x
0
x_nx_{n-1}x_{n-2}...x_{1}x_{0}
xnxn−1xn−2...x1x0(注
x
n
x_n
xn为符号位),则补码表示的定义为:
[
x
]
补
=
{
x
0
≤
x
<
2
n
2
n
+
1
+
x
=
2
n
+
1
−
∣
x
∣
−
2
n
≤
x
≤
0
[x]_{补}=\begin{cases} x && 0\leq x<2^n\\ 2^{n+1} + x = 2 ^{n+1} -|x|&&-2^n\leq x\leq 0 \end{cases}
[x]补={x2n+1+x=2n+1−∣x∣0≤x<2n−2n≤x≤0
这个定义的意思是,一个数的真值大于等于0,在补码表示中可以直接使用真进行表示,对高位补0即可。对于一个数的真值小于等于0则可以使用
2
n
+
1
+
x
2^{n+1}+x
2n+1+x进行表示,这是因为对于n+1位二进制数,最大可以表示的数为
2
n
+
1
2^{n+1}
2n+1(这是模数)所以负数按照规则要转换为对应的补码形式需要加上一个模数。这是同余式的性质
利用补码进行表示的好处是在计算机中进行运算时,减法转换成为加法进行,在计算机中进行实现比较方便。
但是按照定义来说将负数转换为补码仍然需要做减法,为此可以通过反码来解决。
通过原码表示法编程补码表示法的方法
在定点数的反码表示法中,正数的机器码仍然等于其真值,而负数的符号位为1,将原码的每一位求反得到反码,反码的符号位不变,数值位最低位加1,得到反码。
移码表示法
移码通常用于浮点数的阶码的表示,由于,移码的传统定义是
[
e
]
移
=
2
k
+
e
≤
e
≤
[e]_{移} = 2^k + e \ \ \ \leq e\leq
[e]移=2k+e ≤e≤
也就是说对于整个数的表示增加了
2
k
2^k
2k这相当于在数轴上进行了移动(增加了一个固定的偏移量),因此称为移码
浮点数的机器表示
上面我们已经讨论过了浮点表示,现在我们来讨论浮点数在计算机内部如何表示,现在计算机都采用统一的IEEE754标准中的格式表示浮点数,上文中我说
阶符(阶码的符号) | 阶码 | 数符(数的符号) | 尾数 |
---|
在IEEE754标准中使用移码来表示阶码,因此32位短浮点数可以看作下面的格式进行保存
s(符号,1位) | 阶码(移码表示,8位) | 尾数(23位) |
---|
在IEEE754标准中,一个规格化的32位浮点数x的真值表示为
x
=
(
−
1
)
s
∗
(
1.
M
)
∗
2
E
−
127
x = (-1)^s*(1.M)*2^{E-127}
x=(−1)s∗(1.M)∗2E−127
因为你在存储的时候增加127进行存储的,在进行解码的时候应该减去127进行解码。在尾数部分,由于规格化的浮点数的尾数域最左位总为1,因此这一位无需存储。
对于32位浮点数N,IEEE754定义:
- 若E=255且M<>0,则N=NaN。符号NaN表示无定义数据
- 若E=255且M=0,则N= ( − 1 ) s ∞ (-1)^s\infty (−1)s∞,当阶码全为1时且尾数M为全0时,表示的真值N为无穷大,结合符号位S为0或1,有 + ∞ +\infty +∞ − ∞ -\infty −∞之分
- 若E=0且M=0,则N=
(
−
1
)
s
0
(-1)^s0
(−1)s0当阶码全为0且尾数全为0时表示的真值N为零(称为机器0),结合符号位S为0或1,有正零和负零之分。
因为阶码-127被表示正负0,阶码128被表示正负 ∞ \infty ∞因阶码的范围为[-126,127] - 若 0 < E < 255 0<E<255 0<E<255则 N = ( − 1 ) s ∗ ( 1. M ) ∗ 2 E − 127 N=(-1)^s*(1.M)*2^{E-127} N=(−1)s∗(1.M)∗2E−127(规格化数)
- 若E=0且M<>0,则 N = ( − 1 ) s ∗ ( 0. M ) ∗ 2 − 126 N=(-1)^s*(0.M)*2^{-126} N=(−1)s∗(0.M)∗2−126(非规格化数)
上面是一些规定记住就行了。
字符与字符串的表示方法
对于文字、字母、符号等在计算机中都需要转换为二进制格式代码,也就是字符信息用数据表示,称为符号数据。
目前国际上普遍采用的一种字符系统是七单位的IRA码。其美国版称为ASCII码,包含10个10进制数码,26个英文字母和一定数量的专用符号,总共128个元素,因此二进制编码需要7位,加上一个偶校验位,共八位,刚好一字节。
汉字的表示方法
汉字的输入编码
数字编码
常用的国标区位码,用数字串代表一个汉字输入。区位码是将国家标准局公布的6763个两极汉字分为94个区,每个区分为94位,把汉字表示成为二维数组,a[区码][位码]给出区码和位码可以唯一表示一个汉字。
优点:无重码、且输入码与内部码的转换比较方便
缺点:代码难以记忆
拼音码
以汉语拼音为基础的输入方法。
优点:易于掌握
缺点:汉字同音字过多,输入重码率很高,输入速度易受同音字的影响
字形码
把汉字的笔画部件用字母或数字进行编码,按笔画的顺序依次输入就能表示一个汉字。
汉字内码
汉字内码是用于汉字信息的存储、交换、检索等操作的机内代码,一般采用2字节进行表示,有些系统中字节的最高位用于奇偶校验位,这种情况下用3字节表示汉字内码
汉字字模码
字模码是用点阵表示的汉字字形代码,他是汉字的输出形式。
三种编码的总结
汉字的输入编码、汉字内码、字模码是计算机中用于输入、内部处理、输出三种不同用途的编码。
校验码
为了防止数据在传送过程中受到干扰而造成破坏,需要检测错误甚至纠正错误。通常使用的方法是,在每个字上添加一些校验位,用来确定字中出现错误的位置。
检错码
最常用的检错码是采用一位校验位的奇校验或偶校验,设X=(
x
0
x
1
.
.
.
x
n
−
1
x_0x_1...x_{n-1}
x0x1...xn−1)是一个n位字,则奇校验位C’定义为C’=(
x
0
⊕
x
1
⊕
.
.
.
⊕
x
n
−
1
x_0\oplus x_1\oplus ... \oplus x_{n-1}
x0⊕x1⊕...⊕xn−1)
只有当X中包含奇数个1的时候才能和四C’=1即C=0。
同理偶校验位的定义为
C=(
x
0
⊕
x
1
⊕
.
.
.
⊕
x
n
−
1
x_0\oplus x_1\oplus ... \oplus x_{n-1}
x0⊕x1⊕...⊕xn−1)
当X中包含有偶数个1的时候就会C=0
检错码是如何发挥作用的
首先假设一个字要进行传送,这个字为X=(
x
0
x
1
.
.
.
x
n
−
1
x_0x_1...x_{n-1}
x0x1...xn−1),在传输之前首先计算校验码C计算出之后将(
x
0
x
1
.
.
.
x
n
−
1
C
x_0x_1...x_{n-1}C
x0x1...xn−1C)进行传送,然后接受端收到(
x
0
′
x
1
′
.
.
.
x
n
−
1
′
C
′
x'_0x'_1...x'_{n-1}C'
x0′x1′...xn−1′C′)之后进行验证,F=
x
0
′
⊕
x
1
′
⊕
.
.
.
⊕
x
n
−
1
′
⊕
C
′
x'_0\oplus x'_1\oplus ... \oplus x'_{n-1} \oplus C'
x0′⊕x1′⊕...⊕xn−1′⊕C′
假设(
x
0
x
1
.
.
.
x
n
−
1
x_0x_1...x_{n-1}
x0x1...xn−1)要是存在一位(注意是一位)错误且C传送无误那么在F公式中
x
0
′
⊕
x
1
′
⊕
.
.
.
⊕
x
n
−
1
′
x'_0\oplus x'_1\oplus ... \oplus x'_{n-1}
x0′⊕x1′⊕...⊕xn−1′计算出来的就与C’恰好相反,这会导致计算出来的结果为1,即F=1,表示传送出错,F=0表示传送正确
定点加法、减法运算
补码加法
补码加法的公式是:
[
x
]
补
+
[
y
]
补
=
[
x
+
y
]
补
[x]_补+[y]_补=[x+y]_补
[x]补+[y]补=[x+y]补
即两个数的补码相加等于目标数的补码。
证明过程如下:
- 假设两个正数进行相加,则有
[ x ] 补 = x , [ y ] 补 = y [x]_补=x,[y]_补=y [x]补=x,[y]补=y
[ x ] 补 + [ y ] 补 = x + y ( m o d 2 n + 1 ) [x]_补 + [y]_补 = x+y\ \ \ (mod \ \ 2^{n+1}) [x]补+[y]补=x+y (mod 2n+1)
因为正数加正数得到的一定是正数,正数的补码等于它本身,所以得到的结果 x + y x+y x+y是 [ x + y ] 补 [x+y]_补 [x+y]补 - 假设一个正数和一个负数进行相加,则有
[ x ] 补 = x , [ y ] 补 = y + 2 n + 1 [x]_补=x,[y]_补=y+2^{n+1} [x]补=x,[y]补=y+2n+1
[ x ] 补 + [ y ] 补 = 2 n + 1 + x + y = 2 n + 1 + ( x + y ) ( m o d 2 n + 1 ) [x]_补 + [y]_补 = 2^{n+1}+x+y = 2^{n+1} + (x+y) \ \ \ \ (mod \ \ 2^{n+1}) [x]补+[y]补=2n+1+x+y=2n+1+(x+y) (mod 2n+1)
正数和负数相加有三种可能0,正数,负数
假设结果为0按照补码的定义因为在取模的情况下 2 n + 1 2^{n+1} 2n+1不影响结果可以去掉,上式得到的 2 n + 1 + ( x + y ) ( m o d 2 n + 1 ) 2^{n+1} + (x+y) \ \ \ \ (mod \ \ 2^{n+1}) 2n+1+(x+y) (mod 2n+1)等于 x + y x+y x+y而0的补码等于其本身,
如果结果为正数分析同0的情况。
如果结果为负数得到的 2 n + 1 + ( x + y ) ( m o d 2 n + 1 ) 2^{n+1} + (x+y) \ \ \ \ (mod \ \ 2^{n+1}) 2n+1+(x+y) (mod 2n+1)就是负数 x + y x+y x+y的补码,所以在一正一负的情况下相加仍然成立 - 假设两个负数进行相加,则有
[ x ] 补 = x + 2 n + 1 , [ y ] 补 = y + 2 n + 1 [x]_补=x+2^{n+1},[y]_补=y+2^{n+1} [x]补=x+2n+1,[y]补=y+2n+1
[ x ] 补 + [ y ] 补 = 2 n + 1 + x + 2 n + 1 + y = 2 n + 1 + ( 2 n + 1 + ( x + y ) ) ( m o d 2 n + 1 ) [x]_补 + [y]_补 = 2^{n+1}+x+2^{n+1}+y = 2^{n+1}+(2^{n+1} + (x+y) )\ \ \ \ (mod \ \ 2^{n+1}) [x]补+[y]补=2n+1+x+2n+1+y=2n+1+(2n+1+(x+y)) (mod 2n+1)
可以对结果式进一步化简,因为对 2 n + 1 2^{n+1} 2n+1进行取模,所以结果可以变为 2 n + 1 + ( x + y ) ( m o d 2 n + 1 ) 2^{n+1} + (x+y) \ \ \ \ (mod \ \ 2^{n+1}) 2n+1+(x+y) (mod 2n+1)
又因为负数加负数一定是负数,所以 2 n + 1 + ( x + y ) ( m o d 2 n + 1 ) 2^{n+1} + (x+y) \ \ \ \ (mod \ \ 2^{n+1}) 2n+1+(x+y) (mod 2n+1)按照补码的定义就是负数 x + y x+y x+y的补码
证毕。
补码减法
对于补码的减法如果两个数补码相减等于目标数的补码那么就能很方便的进行运算,即
[
x
−
y
]
补
=
[
x
]
补
−
[
y
]
补
[x-y]_补=[x]_补-[y]_补
[x−y]补=[x]补−[y]补
同时按照补码加法的性质有
[
x
−
y
]
补
=
[
x
]
补
+
[
−
y
]
补
[x-y]_补=[x]_补+[-y]_补
[x−y]补=[x]补+[−y]补,所以如果补码减法成立的话应该符合下面的补码减法的公式:
[
x
−
y
]
补
=
[
x
]
补
−
[
y
]
补
=
[
x
]
补
+
[
−
y
]
补
[x-y]_补=[x]_补-[y]_补 = [x]_补+[-y]_补
[x−y]补=[x]补−[y]补=[x]补+[−y]补
证明过程如下:
上式要想成立只需证明
[
−
y
]
补
=
−
[
y
]
补
[-y]_补=-[y]_补
[−y]补=−[y]补即可
首先利用前面证明过的补码加法运算我们知道存在下式成立
[
x
−
y
]
补
=
[
x
+
(
−
y
)
]
补
=
[
x
]
补
+
[
−
y
]
补
[x-y]_补 = [x+(-y)]_补 = [x]_补 + [-y]_补
[x−y]补=[x+(−y)]补=[x]补+[−y]补
[
x
+
y
]
补
=
[
x
]
补
+
[
y
]
补
[x+y]_补 = [x]_补 + [y]_补
[x+y]补=[x]补+[y]补
两式相加可得
[
x
−
y
]
补
+
[
x
+
y
]
补
=
[
x
]
补
+
[
−
y
]
补
+
[
x
]
补
+
[
y
]
补
=
2
[
x
]
补
+
[
−
y
]
补
+
[
y
]
补
[x-y]_补 + [x+y]_补 = [x]_补 + [-y]_补 + [x]_补 + [y]_补 = 2[x]_补 + [-y]_补+ [y]_补
[x−y]补+[x+y]补=[x]补+[−y]补+[x]补+[y]补=2[x]补+[−y]补+[y]补
前面的
[
x
−
y
]
补
+
[
x
+
y
]
补
=
[
x
−
y
+
x
+
y
]
补
=
[
2
x
]
补
=
2
[
x
]
补
[x-y]_补 + [x+y]_补=[x-y+x+y]_补=[2x]_补 = 2[x]_补
[x−y]补+[x+y]补=[x−y+x+y]补=[2x]补=2[x]补
因此上式
[
x
−
y
]
补
+
[
x
+
y
]
补
=
2
[
x
]
补
+
[
−
y
]
补
+
[
y
]
补
[x-y]_补 + [x+y]_补 = 2[x]_补 + [-y]_补+ [y]_补
[x−y]补+[x+y]补=2[x]补+[−y]补+[y]补将$2[x]_补
移项之后得
移项之后得
移项之后得[-y]_补+ [y]_补=0
即
即
即[-y]_补=- [y]_补$
证毕。
溢出的概念与检测方法
为什么要检测溢出呢?在机器中执行两个数的运算的时候,假设都是32位二进制数进行运算得到的结果可能超过了最大的值32位,这种现象显然是错误的,所以出现溢出时代表结果不正确,所以运算其必须要能够检测溢出。
正溢和负溢
两个正数相加,解诂大于机器字长所能表示的最大正数,称为正溢。
两个负数相加,结果小于机器所能表示的最小负数,称为负溢。
检测方法
双符号位法
采用双符号位办法进行检测,这是因为在采用双符号位的时候相当于将整个数的范围加大了一倍,如果产生溢出的话只可能有一位的溢出,这样就会造成双符号位中两个符号不同,即出现01,或者10这种情况,这就是发生了一处,换句话说双符号位中两个符号其中一个是原始符号备份,另一个是运算结果的符号,如果这两个不同就说明符号位被改变,这就会造成溢出。
01表示正溢
10表示负溢
单符号位法
当最高有效位产生进位而符号位无进位时产生正溢,当最高有效位无进位而符号位有进位时,产生负溢
基本的二进制加法/减法器逻辑结构图
减法可以按照补码化成加法操作,所以只需要加法就行了,对于加法运算其可以参考这一篇文章加法运算器
定点乘法运算
在运算中我们知道同号相乘肯定得到正号,异号相乘肯定得到符号,将符号位和结果符号位画出表来:
数1符号位 | 数2符号位 | 结果符号位 |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
使用逻辑表达式进行表达的话
C
=
A
′
B
+
A
B
′
C = A'B + AB'
C=A′B+AB′
这是
C
=
A
⊕
B
C = A\oplus B
C=A⊕B
也就是说结果的符号由两个数的符号位进行异或操作来决定。
结果的数值部分则是两个数相乘之积。
乘法则可以按照如下规则进行
1101
∗
1011
_
_
_
_
_
_
_
_
_
_
_
_
1101
1101
0000
1101
_
_
_
_
_
_
_
_
_
_
_
_
10001111
\ \ \ \ \ \ \ \ 1101 \\ *\ \ \ \ \ \ 1011 \\ \_\_\_\_\_\_\_\_\_\_\_\_ \\ \ \ \ \ \ \ \ \ 1101 \\ \ \ \ \ \ \ 1101\\ \ \ \ \ 0000\\ \ \ 1101\\ \_\_\_\_\_\_\_\_\_\_\_\_ \\10001111
1101∗ 1011____________ 1101 1101 0000 1101____________10001111
在预算的过程中我们可以将第一行1101看作y中最右侧的1乘上x得到的结果,第二行的1101看作y中右侧第二个1成上x的右移一位的结果,第三行的0000可以看作y中的0乘上x的右移两位得到的结果,最后一个1101可以看作y中最左侧的1乘上x的右移三位得到的结果。其实补充完整应为:
1101
∗
1011
_
_
_
_
_
_
_
_
_
_
_
_
1101
11010
000000
1101000
_
_
_
_
_
_
_
_
_
_
_
_
10001111
\ \ \ \ \ \ \ \ 1101 \\ *\ \ \ \ \ \ 1011 \\ \_\_\_\_\_\_\_\_\_\_\_\_ \\ \ \ \ \ \ \ \ \ 1101 \\ \ \ \ \ \ \ 11010\\ \ \ \ \ 000000\\ \ \ 1101000\\ \_\_\_\_\_\_\_\_\_\_\_\_ \\10001111
1101∗ 1011____________ 1101 11010 000000 1101000____________10001111
串行乘法器
串行乘法器分为下面几部分组成,被乘数寄存器、乘数寄存器、累加寄存器、移位寄存器
过程:
首先检测乘数的最低位,如果乘数最低位为1将被乘数的与累加寄存器中的数据进行加和,然后进行移位操作,重复上述流程,直到的得出结果。
但是这种方法时间效率太慢,目前串行乘法器已经被淘汰,现在随着技术的发展,出现了各种形式的高速流水式阵列乘法器。
流水式阵列乘法器
对于流水式阵列乘法器它的工作原理如表所示:
首先对于两个数相乘可以得到下面的一张表
a 3 a_3 a3 | a 2 a_2 a2 | a 1 a_1 a1 | a 0 a_0 a0 | ||||
---|---|---|---|---|---|---|---|
b 3 b_3 b3 | b 2 b_2 b2 | b 1 b_1 b1 | b 0 b_0 b0 | ||||
a 3 b 0 a_3b_0 a3b0 | a 2 b 0 a_2b_0 a2b0 | a 1 b 0 a_1b_0 a1b0 | a 0 b 0 a_0b_0 a0b0 | ||||
a 3 b 1 a_3b_1 a3b1 | a 2 b 1 a_2b_1 a2b1 | a 1 b 1 a_1b_1 a1b1 | a 0 b 1 a_0b_1 a0b1 | ||||
a 3 b 2 a_3b_2 a3b2 | a 2 b 2 a_2b_2 a2b2 | a 1 b 2 a_1b_2 a1b2 | a 0 b 2 a_0b_2 a0b2 | ||||
a 3 b 3 a_3b_3 a3b3 | a 2 b 3 a_2b_3 a2b3 | a 1 b 3 a_1b_3 a1b3 | a 0 b 3 a_0b_3 a0b3 | ||||
R 7 R_7 R7 | R 6 R_6 R6 | R 5 R_5 R5 | R 4 R_4 R4 | R 3 R_3 R3 | R 2 R_2 R2 | R 1 R_1 R1 | R 0 R_0 R0 |
在这样的一张表中我们会发现
a
x
b
y
a_xb_y
axby这样的数一共有
m
∗
n
m*n
m∗n个,而结果序列
R
7
R
6
.
.
.
R
1
R
0
R_7R_6...R_1R_0
R7R6...R1R0可以通过这
m
∗
n
m*n
m∗n个进行得到,这
m
∗
n
m*n
m∗n个数可以并行得到,因此时间花销主要在执行加和得到
R
7
R
6
.
.
.
R
1
R
0
R_7R_6...R_1R_0
R7R6...R1R0这个数,在这一部分中得到
R
7
R
6
.
.
.
R
1
R
0
R_7R_6...R_1R_0
R7R6...R1R0的逻辑表达式为:
R
7
=
C
R
6
R_7 = C_{R_6}
R7=CR6
⋅
⋅
⋅
⋅
⋅
⋅
······
⋅⋅⋅⋅⋅⋅
R
2
=
a
2
b
0
⊕
a
1
b
1
⊕
a
0
b
2
⊕
C
R
1
R_2=a_2b_0\oplus a_1b_1 \oplus a_0b_2 \oplus C_{R1}
R2=a2b0⊕a1b1⊕a0b2⊕CR1
R
1
=
a
1
b
0
⊕
a
0
b
1
⊕
C
R
0
R_1 = a_1b_0 \oplus a_0b_1 \oplus C_{R_0}
R1=a1b0⊕a0b1⊕CR0
R
0
=
a
0
b
0
R_0 = a_0b_0
R0=a0b0
其中
C
R
x
C_{R_x}
CRx表示
R
x
R_x
Rx产生的进位
上面的时间开销主要在于进位产生的延时