第三章

声明：Ayaka师傅yyds

数据的表示和转换

计算机为什么使用二进制？

十进制数和数字串之间的关系？

机器数表示

https://www.cnblogs.com/xfcao/p/10375645.html
正数的反码是他本身，
负数的补码＝反码+1
机器数表示方式小数原码：

整数原码：

小数补码：

整数补码：

补码相对于原码来说，可以多表示一个数，即区间下限。
补码运算规则：两个补码的和/差等于和/差的补码

定点补码加减法运算

原理框架

补码运算规则：两个补码的和/差等于和/差的补码
溢出的判断

例子：

红色的1被舍弃掉了采用双符号变形补码计算的
例子：

只有当两个符号位不相同的时候才发生溢出

浮点数的加减法

原理图

数据范围

关于ALU的讨论

1、ALU是组合电路，因为所见即所得
2、改变进位产生函数Gi，和进位传递函数Pi获得多重运算能力
3、根本区别：进位之间是否有关联，有关联的是算术运算，没有关联的是逻辑运算

74181逻辑图

IEEE754标准

https://blog.csdn.net/leader_song/article/details/121647097

浮点数规格化

阶码+尾数表示浮点数：
例子：
移动尾数，使尾数的有效数码尽可能地占满尾数的有位格对于基为2的浮点数，若满足1/2≤|m|<1则称为规格化数
规格化方法为调整阶码和尾数满足下列关系：
尾数为原码时，无论正负应满足1/2≤|m |<1，即小数点后的第一位数一定要为1
正数的尾数应为0.1xxxxx
负数的尾数应为1.1xxxxx
尾数为补码时，小数最高位应与符号位相反
正数应满足0.1xxxxx
负数应满足1.0xxxxx
采用变形补码时，
若两个符号位相同，则一直左移直到尾数第一位与符号位不同，
若两符号位不同，则右移一步即可。
例子：
M=11.110XX…X，左规2次，阶码-2，M=11.0XX…XM=01.XX…X，
右规（1次），阶码+1，M=00.1XX…X

对阶操作

原则：小阶向大阶对齐尾原：尾数右移符号位不动，尾数最高位补0尾补：尾数连同符号右移，最高位补符号位

例子

二进制乘法运算

定点数原码乘法

原码一位乘

符号位单独算，然后不停取乘数的尾数，是1则加|x|,是0则加0，然后右移，将刚才取的尾数顶掉

原码两位乘（不考）

移位原理和一位乘有几分类似
多了一个欠账触发器，每次取乘数的后两位

由于C是代表下一位是不是给当前位有进位的情况可以直接把C加到Yi-1Yi上
然后再根据

来判断进行哪种操作，

如果加完之后变成了100，则保持C为1，部分积右移两位即可。最后如果乘数已经处理完了，
C仍为1，则需要在部分积上加|X|用来还账，加完之后不移位
注意：移位的时候是右移采用补码规则

为什么加法器应该设置三个符号位？
按照原码一位乘的想法，其实两位符号位正好可以满足部分积相加，再配合逻辑移位。但是这中间有错误，当我们加上负x的补码，这时候就会出现小于0的情况，但是逻辑移位后的值是一个大于0的结果，很明显和结果不符合，所以才有三位符号位，加算术右移就很好的解决了这个问题

例题：

定点数补码乘法

定点数补码一位乘

校正法

将[X]补和[Y]补按原码乘法规则进行运算，根据具体情况对所得结果进行校正，从而得到[XY]补
具体方法为：将[Y]补去掉符号位，当做正数与[X]补按原码一位乘来做，相加的时候采用两位符号位，并且符号位参与运算，右移的时候遵循补码规则（左边补符号位）最后如果乘数为负，则对部分积进行校正（加[-X]补），但不移位
原理：

校正法缺点
乘数为正、为负运算规律不统一、控制复杂

比较法

优点：避免区分乘数的正负，而且让乘数的符号也参加运算，使运算规律统一起来
通过对校正法补码乘法公式进行变换实现

具体方法：部分积和被乘数采用双符号位，乘数采用单符号位，并且末尾添一个0
每次通过判断乘数后两位决定执行什么操作，
如下表：

右移的时候只移动一位最后一步不移位
（末尾还剩两个数的时候为最后一步）
例题：

定点数补码两位乘（不考）

运算规则：
- 方法一
  
  (1) 两数均用补码表示，符号位参加运算。
  
  (2) 部分积与被乘数均采用3位符号表示，乘数末位增加一位附加位y n+1 ，其初始值为0。
  
  (3) 按下表所示操作。
  
  (4) 若乘数的数值位n为偶数，乘数取双符号位，这种情况共做(n/2)+1步，最后一步不移位；若乘数的数值位n为奇数，乘数取单符号位这种情况共做(n+1)/2步，最后一步移一位。
- 方法二
  
  (1) 符号位和数值位不分开运算
  
  (2)被乘数以及部分积采用三位符号位，乘数y的符号位由以下规则判断：如果乘数y的尾数位数为奇数，则采用单符号位，并且运算的最后一步移一位；如果乘数y尾数的位数为偶数，则采用双符号位，并且运算的最后一步要不移位。
  
  (3)每次分别用乘数的两位以及外加一位yn+1（初始为0）来判断原部分积是否加和如何加被乘数，每进行一步操作yn+1随着右移顺延乘数的尾数。具体规则见下表（表格中均为算数右移）

即：附加位+末位-2倍倒数第二位
例题：

二进制除法运算

原码一位除

恢复余数法

类似于笔算除法，通过减法来判断当前位是否能除尽。如果不能就加上|Y|来恢复

恢复余数法的缺点
上商和左移必须分两步完成，除法时间较长，速度低
除法步数不固定，控制较复杂

加减交替法

左移、负加正减

原理图：

补码一位除

加减法交替法

符号位参与运算，除数和被除数都用双符号位补码表示
求余数的符号位：同号相减，异号相加
- 被除数与除数同号时，用被除数减去除数
- 被除数与除数异号时，用被除数加上除数
商的进位有关:
- 余数与除数同号时，商上1，余数左移一位减去除数。
- 余数与除数异号时，商上0，余数左移一位加上除数
商的校正规则:
- 刚好能除尽(运算结果中任何一-步余数为0),
  - 除数为正，则商不必校正。
  - 除数为负，则商需要校正，加2^-n（末位加1）
- 不能除尽
  - 商为正，则不必校正
  - 商为负，则商需要加上2^-n（末位加1）
余数的校正规则:
- 若商为正：余数与被除数异号时，余数+除数.
- 若商为负：余数与被除数异号时，余数-除数

Booth法（了解，不考）

无符号阵列乘法器

阵列乘法器基本思想：将大量的加法器单元电路按一定的阵列形式排列起来，直接实现乘法算式。（和笔算乘法的形式一样）
➢优点：避免重复的相加与移位操作

n×n位阵列乘法器需n×(n-1)个全加器和n^2个门
每个单元由一个全加器和一个与门构成，全加器

数据校验码

copy自Ayaka师傅

码距：一种码制中任意两个合法码字间距离的最小值（最少有几个数不同）
码字：由若干代码组成的一个字
距离：两个码字之间对应位代码不同的个数

来看例子：

如8421码，两个合法码字之间的最小距离为1，比如0001和0011，这两个码字只有一位不同，所以距离为1

码距越大，查错、纠错能力越强，码距越大，数据冗余越大

奇偶校验码

在每组数据信息上附加一个校验位

奇校验：加上校验码位后数据中’1’的个数应为奇数个
偶校验：加上校验码位后数据中’1’的个数应为偶数个

码距为2，可检出奇数个数位出错的情况

海明校验码

在数据中加入几个校验位，并把数据的每一个二进制位信息分配在几个奇偶校验组中码距为3（扩展海明码为4），不但可以发现错误，还可以指出是哪一位错了。其实就是把每一个2的幂次方位上都放校验位，其余位上放数据。
如果一个数据在第n位，则验证它的校验位为将n写成二进制后，为1的位置对应的校验位

举个例子：

并且对于D3来说，它在第七位，所以验证它的就是第4+2+1位，即P1、P2、P3偶校验时各校验位Pi的值为它参与校验的数据位的异或，奇校验时将上述值取反我们来看一个表加深一下理解：

注意：校验位参与校验的除数据位还有校验位自身
如果采用偶校验且仅有一位出错，出错位置由各个校验和依序排列后直接指明
例：若三个校验和 S3S2S1 依序排列后等于(101)2 =(5)10 ，海明码的第五位（D1）发生了错误，将其取反，即纠正了错误
**扩展海明码：**增加了全局校验位，放在最前端，全局校验和等于海明码所有位异或的结果

循环冗余校验码（CRC）

如何检错

假设被传送的k位二进制信息位用M(x)表示，系统选定的生成多项式用G(X)表示

第一步：将M(x)左移G(X)的最高次幂（即需要添加的校验位的位数r），写作M(x) • 2r
第二步：M(x) • 2r除以（使用模2除）生成多项式G(x)，所得商用Q(x)表示，余数用R(x)表示
第三步：将R（x）接在M(X)后面发出去，接收方用G(X)进行验证，余数为零则不出错

举个例子：

通俗易懂的说就是，

有个G(X)是发送方和接收方都知道的。发送方如果要发1010，而G(X)是1011的话，则将1010左移4-1=3位，变成1010000，然后做模2除法，其实就是不停异或，就拿这题为例：

1010000
1011

对应位异或后，1010000变成了1000 ，我们最后要的余数应该是3位，所以还要继续异或
1000
1011
结果为0011，由于我们只要三位，所以最后R(X)为011，把011接到1010后面，最后实际发送的数据位1010011。
然后接收方如何判断是否出错呢，其实就是对1010011做上面的异或操作，即
1010011
1011
对应位异或后结果为1011
再异或
1011
1011
结果为0，则校验成功，没有哪一位出错。如何纠错

先通过余数知道是哪个位错了，然后给余数不停补0接着模2除，一边循环左移数据，直到把出错的哪个位移动到最高位，然后取反，接着移动，直到循环移回来，纠错结束

校验码小结：

第三章