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

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

BCD码

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

二进制转换成十进制需要按以下方式：
$$K_n{r}^n+K_{n-1}{r}^{n-1}+...+K_1{r}^1+K_0{r}^0$$
由此可见转换相当麻烦。

8421码

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

0	1	2	3	4	5	6	7	8	9
0000	0001	0010	0011	0100	0101	0110	0111	1000	1001

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

为了让运算结果符合映射规则，会对1010到1111这个区间的数，也就是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，于是存在以下映射关系：

0	1	2	3	4	5	6	7	8	9
0011	0100	0101	0110	0111	1000	1001	1010	1011	1100

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

2421码

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

0	1	2	3	4	5	6	7	8	9
0000	0001	0010	0011	0100	1011	1100	1101	1110	1111

可以看到，对于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比特二进制分别为01100011与00001001。它们相加只需要从最低位开始，并向着更高位进位即可，因此结果为01101100。

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

减法

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

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

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

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

然后我们只需要将01100011和11110111按照加法的方式进行相加即可得到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为例，其补码如下：
$$10011100$$
我们找到从右往左第一个1
$$10011100$$
然后对中间的二进制位取反，即得到-100的原码
$$11100100$$
反之依然成立。

对于反码，真值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两台计算机进行通信，其信息编码方式如下

A	B	C	D
00	01	10	11

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

A	B	C	D
100	001	010	111

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

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

奇偶校验

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

奇校验码：整个校验码中（有效信息和校验位）中1的个数为奇数。

偶校验码：整个校验码中（有效信息和校验位）中1的个数为偶数。

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

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

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

硬件实现

偶校验的硬件实现

对信息位中的每一位进行异或运算（模2加运算）。异或运算的法则如下：

0异或0	0异或1	1异或0	1异或1
0	1	1	0

即异或运算两个比特不同才为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。