计算机组成原理——进制与编码

BCD码

对于计算机来讲二进制方便计算机处理,而对于人类来讲十进制符合人类使用习惯。

二进制转换成十进制需要按以下方式:

$$ K_nr^n+K_{n-1}r^{n-1}+...+K_1r^1+K_0r^0 $$

由此可见转换相当麻烦。

8421码

为了快速变换就需要一种二进制编码的方式(Binary-Coded Decimal)实现二进制与十进制一一对应,其中一种方式为8421码,其映射方式如下。

0123456789
0000000100100011010001010110011110001001

对于十进制5+8这种操作,计算机会将01011000交给算术逻辑运算单元进行加法运算。但是运算结果为1101不在映射表里。

为了让运算结果符合映射规则,会对10101111这个区间的数,也就是10到15之间的数再加一个6,这样最高位必然向前进1,则剩下的部分就落在这个映射表中了。

例如对于13这个结果,二进制表示为1101,加6就成了00010011,而0011正好对应3,0001对应1。

当然对于人手算来讲,只需要写出十进制13,然后把每一位十进制对应的8421码的方式拼接即可。即1对应0001,而 3对应0011,拼接起来就是00010011,来表示13的8421编码方式。

余3码

余3码是在8421的基础上再加上3,于是存在以下映射关系:

0123456789
0011010001010110011110001001101010111100

8421码每个二进制位的权值都是固定不变的,都是8,4,2,1。而对于余3码每一位的权值不是固定的。因此8421这种也被称为有权码,而余3码这种类型的被称为无权码。

2421码

2421码是有权码,对应权值分别为2,4,2,1,其映射关系如下:

0123456789
0000000100100011010010111100110111101111

可以看到,对于5到9的数都是以1开头。这是因为如果按照2421编码方式5可以表示为0101也可以表示为1011,为了避免歧义就采用了这种规定。

无符号整数

无符号整数,即从零开始的整数,0,1,2,3,...

在C语言中,只需要用unsigned这个关键字即可生命一个无符号类型的数字。

unsigned short a=1;    //无符号短整型,2Byte
unsigned int b=2;    //无符号整型,4Byte

我们这里主要关心无符号整数在计算机内的运算以及硬件实现。

若一个机器字长为8位(现在的计算机通常是32位或64位),其寄存器只能存8位,也就是说无符号整数二进制位数是有上限的。

对于真值0,其二进制表示也是0,但是在8位寄存器中要扩展成8位00000000。、

对于8位寄存器存放的真值只能是0到255,总共256个数。如果真值256转换成二进制存放进去的话,会发生溢出现象,也就是说最高位会被忽略掉只能存放低8位,最终寄存器里的二进制为00000000

由此可见n bit无符号整数可以表示的范围为$0$到$2^{n}-1$​,最小的数每一二进制位全为0,最大的数全为1。

加法

接下来我们看下在计算机中,无符号整型的加法是如何实现的。我们以99+9为例,它们的8比特二进制分别为0110001100001001。它们相加只需要从最低位开始,并向着更高位进位即可,因此结果为01101100

当然两个无符号整型相加在8bit的限制下可能存在溢出的情况,例如255+1,只需要将结果保留低8位即可。

减法

在计算机中无符号整型减法需要遵循以下步骤:

  • 被减数不变,减数全部按位区反,末为全部加1,减法变加法
  • 从最低位开始,按位相加,并往更高位进位

加法电路造价更贵,而减法电路更昂贵,因此将减法转换成加法更节省成本。

我们以99-9为例,其二进制8比特表示分别为0110001100001001,按上述算法,需要对减数取反为11110110,并且末尾加1,变成了11110111

然后我们只需要将0110001111110111按照加法的方式进行相加即可得到90的二进制01011010

带符号整数

在数学里整数的概念即为带符号整数,如-1,-2,0,3,4等。

在C语言中我们可以用以下方式来表示带符号整数:

short a = 1; //带符号整数,短整型,2Byte
int b = -2;    //带符号整数,整型,4Byte

原码表示法

原码表示法最高位为符号为,最高位若为0,则为正数;若最高位为1,则为负数。剩下的较低的二进制位表示其数值。

也就是说,带符号的整数,若寄存器为n+1位,则可以表示的范围是$-(2^n-1)$到$2^n-1$。对于真值0有两种形式,一种是+0,另一种是-0,前者包括符号位在内的每一位都是0,后者除了符号位为1外,其他位都是0。

原码表示带符号整数,缺点是符号位不能参与运算,因此需要设计更复杂的硬件电路才能处理,成本比较高。

补码表示法

补码的转换

为了使符号位能够参与运算,于是就设计了补码表示法。

对于正整数来说,其补码与反码一致,不做改变。

而对于负整数来说,遵循以下原则:

  • 原码符号位不变,数值位按位取反,得到反码
  • 反码末位加1,得到补码

当然对于手算,则有更简单的方式。正数原码与补码之间的转换依然保持不变,而对于负数,只需要将原码从右往左找到第一个1,然后这个1与符号位之间的二进制位(不包括符号位与这个第一个1)全部取反即为补码。同理对于负数补码,我们也是从右往左找到第一个1,然后这个1与符号位之间的二进制位(不包括符号位与这个第一个1)全部取反即为原码。

我们以-100为例,其补码如下:

$$ 1\space0011100 $$

我们找到从右往左第一个1

$$ 1\space 0011\space100 $$

然后对中间的二进制位取反,即得到-100的原码

$$ 1 \space 1100 \space 100 $$

反之依然成立。

对于反码,真值0的表示方式同样分为+0和-0,前者所有位全为0,后者所有位全为1。

而对于补码,真值0的表示方式只有一种,那就是所有的二进制位都是0。

在计算机中有符号整数通常是以补码的形式存在的。

补码加法

我们以19+(-19)为例,19的补码为00010011,-19的补码为11101101,二者相加只需要从最低位开始,进行二进制加法,向更高位进位即可,结果为00000000

使用补码相加就使得符号位参与了运算,还能得到正确的结果。

补码减法

对于补码减法运算,我们仍旧按照之前的思想,将其转换为加法运算。对于A-B,实际上可以写成A+(-B),也就是说,我们只需要将减数的符号为取反,然后按照补码加法原则进行计算即可。

移码

移码只需要在补码的基础上取反符号为即可。但是移码只能表示整数,而补码和原码可以表示小数。

由于补码的真值0表示方式只有一种,那么移码的真值0表示方式也是只有一种,那就是符号位为1,其他二进制位为0。

总结

定点小数

定点小数的小数点位置是固定的。我们之前所说的带符号整数,其实也可以叫做定点整数,因为其小数点实际上是隐含的。

我们之前在带符号整数的移码部分提到过,带符号整数可以用原码、反码、补码、移码来表示,而定点小数的表示方式只有原码、反码、补码

原码表示

定点小数同样有一个符号位,若为1则代表负数,若为0则代表整数。

对于定点小数,其小数位之后的第i位(i>0)的权值为$2^{-i}$

我们假设定点小数的小数点位置在符号为之后,计算机字长为8位,则其每一位的权值如下图所示:

反码、补码

定点小数的反码、补码计算方式同带符号整数,这里不过多叙述。

定点小数加法、减法

定点小数采用补码加法,其算法同带符号整数。此外补码减法也同带符号整数。

定点小数与定点整数的对比

定点小数与定点整数的对比

定点小数与定点整数位数扩展是不一样的,对于定点小数来讲,位数扩展的位数是在最低位之后;而对于定点整数,位数扩展是在符号位与数值位之间。

我们分别对4bit的二进制定点小数1.110与定点整数1,110分别扩充4位。(注意这里的小数点和逗号只是用于分割表示,看起来更直观一点,实际上其二进制并没有小数点和逗号)

定点小数扩展后其二进制

$$ 1.1100000 $$

而对于定点整数扩充后其二进制为

$$ 1,0000110 $$

奇偶校验码

校验位

假设A、B两台计算机进行通信,其信息编码方式如下

ABCD
00011011

但是由于信道的电气特性引起信号幅度、频率、相位的畸变,信号反射、串扰、闪电、大功率电机的启停等,都有可能造成传输链路的数据信号产生差错,因此我们可以增加一个二进制位,来判断数据传输是否发生差错。

ABCD
100001010111

3bit映射到4个合法状态,有4个冗余的非法状态。

我们假设A传输数据001,但是到经过物理链路之后,B收到的信息为000的非法状态,B就可以判断出两者之间传输的数据发生错误。

奇偶校验

若存在有效信息位为n位,我们只需在头部或者尾部添加1个奇偶校验位来判断信息是否有误即可。

奇校验码:整个校验码中(有效信息和校验位)中1的个数为奇数。

偶校验码:整个校验码中(有效信息和校验位)中1的个数为偶数。

我们来看一个例子,给出两个编码1001101和1010111的奇校验码和偶校验码。假设最高位为校验位,其余7位为信息位,则对应的奇偶校验码如下:

  • 奇校验码分别是1 10011010 1010111。前者由于信息位中1的个数是4个即偶数个,所以最高位也就是校验位需要补一个1才能让整个校验码的1为奇数个;同样,后者信息位中1度个数为5个,为奇数个,所以最高的校验位不需要补1,填写0即可。
  • 偶检验码分别是0 10011011 1010111。由于是写偶校验码,前者信息位中1的个数为4个即偶数个,因此最高位即校验位不用补充1,填0即可;而后者信息位中的1的个数为5个即奇数个,因此最高位填1,使整个校验码中的1的个数达到偶数个。

奇偶校验码有一定局限性。假设我们采取偶校验码1 1010111,假如在信息传输过程中最低两位的1都变成了0,接收方收到校验码后是检查不出错误的,因为校验码中的1仍为偶数个。

硬件实现

偶校验的硬件实现

对信息位中的每一位进行异或运算(模2加运算)。异或运算的法则如下:

0异或00异或11异或01异或1
0110

即异或运算两个比特不同才为1,相同为0。

对于信息位1001101我们可以通过运算得到偶校验位为0

$$ 1 \oplus 0 \oplus 0 \oplus 1 \oplus 1 \oplus 0 \oplus 1 = 0 $$

奇校验的硬件实现

我们通过上面的知识可以知道,若信息位中有偶数个1,偶校验位为0,若有奇数个1则偶校验位是1。

那么对于奇校验位,只需要按照偶校验位那样进行异或运算,然后对最终结果取非即可。也就是说如果异或运算结果为0,我们就让奇校验位为1;若异或运算结果为1,则奇校验位就是0。

最后修改:2024 年 09 月 19 日
如果觉得我的文章对你有用,请随意赞赏