第二章 数据的表示和运算
2.1 数制和编码
2.1.1 进位计数制及其相互转换
1、进位计数法
基数，r进制的基数就是r，是指每个数位所用到的不同数码的个数称为基数；
位权
2、不同进制数之间的相互转换
二进制B结尾；十六进制H结尾或0x开头；十进制D结尾
（1）任意进制→十进制
（2）二进制与八进制数和十六进制数相互转换
（3）十进制→任意进制
把整数部分和小数部分分开处理，整数部分除基取余；小数部分乘基取整。整数部分先得到的是最低位，小数部分先得到的是最高位
2.1.2 真值和机器数
在计算机中，整数可以连续表示，但小数是离散的，并不是每个十进制小数都可以精确的用二进制表示。只有在乘基取整使出现了00的情况，才证明可以精确表示。但任何一个二进制小数都可以用十进制小数表示。
*2.1.3 BCD码
1、8421码（有权码
（1）有6种状态为冗余状态
（2）8421的加法：若相加之和小于1001，则不用修正；若结果超过了1001，则运算结果加6，并向高位进位
2、余3码（无权码）
8421码+（0011）2
3、2421码（有权码）
要规定 0~4第一位必须是0，5~9第一位要取1
2.1.4字符与字符串
1、字符编码ASCII码 7bit
32~126为可印刷字符，其余为控制、通信字符
注意ASCII中所有数字、大写字母、小写字母之间的ASCII码值都是连续的
2、汉字的表示和编码 2B
国标码=（区位码）16+2020H
汉字内码=（国标码）16+8080H
输入：输入编码
输出：汉字字形码
2.1.5 *校验码
由若干位代码组成的一个字叫做码字
将两个码字逐位进行对比，具有不同的位的个数称为两个码字间的距离。
一种编码方案可能有若干个合法码字，各合法码字间的最小距离称为码距d
1、奇偶校验码：一位检错能力
奇偶校验只能发现数据代码中奇数位的出错情况，而且没有纠错的能离；常用于存储器数据的检查或传输数据的审查。
偶校验的硬件实现：个信息进行异或（模2加）运算，得到的结果即为偶校验位。进行偶校验，所有位进行异或，结果为1表示出错，0表示没错
2、海明校验码：两位检错能力，一位纠错能力
（1）确定海明码的位数
信息位n位，校验位k位，应满足n+k+1<=2k；即k位校验位，n位信息位，一共n+k位
（2）确定校验位的分布 参考4.2.6！！
校验位在2i-1的位置上，其余各位为信息位
无法区分到底是一位错还是2位错，所以要加一个全校验位，对整体进行偶校验。此时
3、循环冗余校验码
（1）基本思想：数据发送、接收方约定一个除数
信息位k位，校验位R位
（2）生成多项式给出了除数的值，对移位后的信息码，用生成多项式进行模2除法，得到的余数就是R位校验位
在检验时，进行模二除的运算，余数为0，说明无错误，余数非0，说明出错
（3）理论上可以检测出所有奇数个错误、双比特错误、小于等于校验位长度的连续错误、若选择合适的生成多项式，且2R>=K+R+1。则可以纠正单比特错
2.2 定点数的表示和运算
2.2.1 定点数的表示
1、无符号数和有符号数的表示
2、机器数的定点表示
3、原码、补码、反码、移码
移码：只要把补码的符号位取反即可，因此和补码的数据表示范围完全一样；移码只能用于表示整数
移码表示的整数很方便对比大小，移码最小的值永远都是全零，最大的值永远都是全1
由[x]补求[-x]补
2.2.2 定点数的运算
1、定点数的移位运算
（1）算术移位
（2）逻辑移位
（3）循环移位
①带进位标志CF的循环移位（大循环）
②不带进位标志位的循环移位（小循环）
2、定点数的加减运算
（1）原码定点数的加减法运算
符号位单独计算，对绝对值进行运算
（2）补码定点数加减法运算
符号位参与运算
（3）溢出判断
①采用一位符号位
方法一：设A的符号位为As，B的符号位为Bs，运算结果的符号为Ss，则溢出表达式为
V=AsBs
+
Ss
若V=0，表示无溢出，V=1，表示有溢出
方法二：符号位的进位Cs&最高数值位的进位C1；
CsC1=01：上溢
CsC1=10：下溢
CsC1=11：正确的负数结果
CsC1=00：正确的正数结果
②采用双符号位
模4补码
但在实际存储时只存储一个符号位，运算时会复制一个符号位
具体看书
③采用一位符号位根据数据位的进位情况判断溢出
两次进位情况相同，表示没有溢出；两次进位情况不同，表示有溢出
（4）符号扩展 ①对于正数：所有空的位都用0填充
②对于负数：A.原码：多的位用0填充
B.补码：整数用1填充，小数用0填充
C.反码：用1填充
4、定点数的乘法运算
（1）原码一位乘法
符号位单独计算：异或
数值部份算绝对值相乘：先加法再移位，加法移位，加法移位，一直到0
n轮加法、移位，每次移位是原码的逻辑右移
（2）补码一位乘法（Booth算法）
符号位参与运算
n+1轮加法、n次移位，每次移位时补码的算术右移！
3、定点数的除法运算
（1）原码除法（符号位单独运算）
①恢复余数法
先减除数，如果得到是负数，就商0，并且恢复余数+[y]补，之后左移；如果得到的余数是整数，就商1，之后左移。
②不恢复余数法（加减交替法）
只是对恢复余数法中，余数的恢复做了一个简化；
若余数为负，则直接商0，让余数左移一位再加上|除数|，得到下一个余数；
若余数为正，则直接商1，让余数左移一位再减去|除数|，得到下一个余数。
在需要得到余数的情况下，若余数为负，需要商0，并且加[y]补，以得到正确的余数。
加减n+1次，每次加减确定一位商，左移n次（最后一次加减完不移位）
（2）补码除法（符号位一起参加运算）
2.2.3 C语言中的整数类型及类型转换
C语言中定点整数是用“补码”存储的。
int型占4个字节，short型占用2个字节，unsigned short 占2个字节；char型为8位ASCII码整数
相同长度的数据类型转换：位值不变，只改变解释反射光hi
不同长度的数据类型转换：大字长变量向小字长变量强制类型转换：高位截断，保留低位；
小字长变量向大字长变量转换：低位位置相等，高位扩展为原数字的符号位
2.2.4 数据的存储和排列
1、数据的大端方式和小端方式
（1）大端方式（便于人类阅读）：把存储字的更高字节存到最低的地址中
（2）小端方式：（便于机器数据处理）把存储字的最低字节存到最低的地址中
2、数据按边界对齐方式存储
空间换时间
2.3 浮点数的表示和运算
2.4 算术逻辑单元
第三章 存储器
3.3半导体随机存储器RAM
3.3.2 SRAM和DRAM
DRAM用了地址线复用技术，可以使地址线减半，引脚数量更小
1、SRAM原理
2、DRAM原理
（2）DRAM的刷新
把一个地址译码器编程行译码器和列译码器，提高了运算的速度，而且减少了选通线的数量。
以行为单位，每次刷新一行存储单元
2ms刷新一次，刷新通过硬件支持实现，每次刷新占用一个读/写周期，在什么时候刷新？
①分散刷新：每次读写玩都刷新一行，系统的存取周期变为原来的2倍，2ms内每一行都可以刷新很多很多次
②集中刷新：2ms内集中安排时间全部刷新，系统存取周期不变，但是专门用来刷新的时间无法访问存储器，存在死区
③异步刷新：每一段时间刷新一行；可以在译码阶段刷新
DRAM的刷新由存储器独立完成，不需要CPU的控制
现在一般都是用SDRAM
3.3.3只读存储器ROM
非易失，结构简单，位密度比较高
1、MROM：掩膜式只读存储器
2、PROM：可编程只读存储器，只能写一次
3、EPROM：可擦除的可编程只读存储器
UVEPROM：紫外线擦除
EEPROM：电可擦除
4、Flash Memory：闪存（U盘，SD卡）
写比读要慢，可读可写；手机辅存也是用Flash芯片的
5、Solid State Drives（SSD）
控制单元+Flash芯片，速度快功耗低。
计算机内的重要ROM：BIOS芯片，存储了自举装入程序，负责引导装入OS
RAM芯片时随机存取的，很多ROM芯片也具有随机存取的特性
3.4主存储器与CPU的连接
3.4.1连接原理
数据总线、地址总线、读/写控制线；
3.4.2主存容量的扩展
1、位扩展法（扩展数据的位数，即扩展存储字长）
2、字扩展法（扩展地址的范围，增加存储器中字的数量）可以用译码器，或者门电路实现
线选法：用多余的地址线，一根线选一个芯片；n个地址线只能选n个芯片
译码器片选法：n条多余的地址线可以产生2n个片选信号，控制2n个芯片
3、字位同时扩展法
CPU可以使用译码器的使能端来控制片选信号的生效时间；具体可以看书上的例题。
3.4.3存储芯片的地址分配和片选
1、线选法（产生片选信号，n根高位地址线可以选中n个存储芯片）
好处：不需要译码电路，比较简单；
缺点：地址空间不连续，选片的地址线必须分时为地带弄，不能充分利用系统的存储空间。
2、译码片选法
字选是指存储器内部的存储单元的地址选择（一般是由CPU给出的内存地址的低位地址与存储芯片的地址线直接相连），片选是用来选择存储芯片（由CPU地址线的高位给出）
自选的译码由芯片的片内逻辑完成，哦i按选的译码由外接译码器逻辑完成。
3.4.4存储器与CPU的连接
1、选择芯片
2、链接地址线
3、连接数据线
4、读/写命令线
5、片选线
3.5双端口RAM和多模块存储器
3.5.1双端口RAM
可以优化多核CPU访问一根内存条的速度
有两个独立的端口。
3.5.2多模块RAM
1、单体多字存储器
每次可以读取多个字
但是需要
2、多体并行存储器
（1）高位交叉编址
并没有提高存储器的吞吐率
（2）低位交叉编址
连续存取n个存储字→耗时T+(n-1)r；在宏观上看，每个字的平均存储时间只需要r，不需要恢复时间！
无缝衔接，提高了存储器的吞吐率
采用流水线方式的方式并行存取，m体交叉存储器可以提供的数据量为单个模块的m倍。当存取周期是T，存取时间为r（或描述成总线传输周期为r）时，为了使流水线不间断，应保证模块数m>=T/r
3.6高速缓冲存储器Cache
3.6.1程序访问的局部性原理
空间局部性、时间局部性
3.6.2Cache的基本工作原理
主存和Cache以块为单位进行交换
主存的块又叫“页/页面/页框”，Cache的块又叫“行”
3.6.3Cache和主存的映射方式
Cache和主存以块为单位进行信息的交换，Cache的块的大小应该与主存块的大小相同
1、全相联映射方式
通常用成本较高的按内容寻址的相联存储器进行地址的映射
2、直接映射
3、组相联映射
3.6.4Cache中主存块的替换算法
1、全相联映射
Cache完全满了才需要替换，需要在全局中选择替换哪一块
2、直接映射
3、组相联映射
3.6.5Cache写策略
1、写命中
（1）写回法：只修改Cache中的内容，只有当Cache块被换出时才写回主存。每个Cache行要加一个标记位（脏位），反应Cache块是否被修改过。
（2）全写法（写直通法）
为了增快速度，可以增加一个写缓冲，在CPU写的不频繁时，可以很好的提高CPU写的速度
2、写不命中
（1）写分配法：先把内存中的块调入Cache，在Cache中修改，然后再搭配写回法
（2）非写分配法：直接往内存里写，一般搭配全写法
注意：各级Cache之间一般使用全写法和非写分配法，Cache和主存之间用写回法和写分配法
3.7虚拟存储器
3.7.1页式存储器
逻辑地址（虚地址）
物理地址（实地址）
操作系统将程序分“页”，应用程序员只能看到逻辑地址，操作系统把逻辑地址映射为物理地址；把逻辑页号映射到主存块号，为此建立了页表
逻辑地址可以分为逻辑页号和页内地址
快表TLB
京公网安备 11010502036488号