组合逻辑电路
逻辑代数基本定理
1.重叠律：A+A=A A•A=A
2.吸收律：A+A•B=A A•(A+B)=A
3.还原律：~~A=A
4.反演律：(A+B)=A•B ~(A•B)=A+~B
5.包含律：A•B+A•C+B•C=A•B+A•C （A+B)•(A+C)•(B+C)=(A+B)•(A+C)
A•B+A•C+B•C•D•E•F…=A•B+A•C
逻辑代数的规则
带入规则：在任何一个包含某个变量的逻辑等式中，用另一个函数式代入式中所有这个变量的位置，等式依然成立
反演规则：将原函数中所有的•换成+，+换成•，0换成1，1换成0，原变量换成反变量，反变量换成原变量，就得到原函数的反函数**（不属于单个变量上的”非号”在变换中不变）**
对偶规则：将原函数中所有的•换成+，+换成•，0换成1，1换成0，就得到原函数的对偶式。对偶式与原式等价
逻辑函数
常用表达式
- 与或式 F=AB+CD
- 或与式 F=(A+B)(C+D)
- 与或非式 F=~（AB+CD)
标准表达式
- 最小项表达式：全部由最小项构成的与或式（积之和式）
写出真值表，把输出为1的输入组合写成乘积项的形式，取值为1的输入用原变量表示，取值为0的输入用反变量表示，然后将它们加起来
- 最大项表达式：全部由最大项构成的或与式（和之积式）
写出真值表，把输出为0的输入组合写成和项的形式，取值为0的输入用原变量表示，取值为1的输入用反变量表示，然后将它们乘起来
逻辑函数的简化法
利用对偶规则，将“或与”式转化为“与或”式来化简
代数法：利用公理、定理和规则进行化简，有合并乘积项法、吸收项法、配项法
卡诺图法
基本组合逻辑部件设计
数字电路分为组合逻辑电路和时序逻辑电路。
组合逻辑电路：将逻辑门以一定的方式组合在一起，使其具有一定逻辑功能的数字电路。
组合逻辑电路没有反馈电路和存储电路，当时的输出仅由当时的输入决定，是一种无记忆电路
加法运算电路
半加器：对两个1位二进制数进行相加求和，并向高位进位的逻辑电路，不考虑来自低位的进位
C0是进位，S0是和
全加器：对两个1位二进制数进行相加求和，考虑来自低位的进位，并向高位进位的逻辑电路
Ci是低位进位，C0是进位
并行加法器–串行进位
A,B是两个加数，每位分别相加，从低位串行进位，进位延时较长
并行加法器–并行进位
使用迭代的方法直接算出每一位的进位量
减法运算的实现
[A+B]补 = [A]补 + [B]补
[A-B]补 = [A]补 + [-B]补
-X的补码：对X的补码各位取反，然后加1
[A-B]补 = [A]补 + ~[B]补 + 1
所以，加减法可以共用同一套加法器电路
溢出
溢出指运算结果超出计数系统所能表示的范围
如果符号位相同的两数相加，所得结果的符号位与之相反，结果溢出
如果符号位相异的两数相减，所得结果的符号位与减数相同，结果溢出
溢出的判断：采用双符号位，“00”表示正，“11”表示负，如果 运算结果符号位出现“01”或“10”表示出现溢出。
数值比较器
用于比较两个二进制数的大小
运算单元电路
可执行1位与、或、或非、与非、加、减运算
编码器
编码：为区分一系列不同的事物，对其中的每个事物用一组二值（0或1）的二进制代码表示。从广义上讲，编码是信息从一种形式转换为另一种形式的过程。
编码器：实现编码功能的数字电路称为编码器
二进制编码器
用n位二进制代码，对2^n个信号进行编码。任一时刻只能对其中一个信号进行编码，即只允许其中一个输入信号有效，其余为无效电平。
高电平输入有效：在输入等于1时，对输入信号进行编码，输出等于对应有效输入信号的二进制编码
8线-3线编码器（高电平输入有效）
8个输入信号：Y0，Y1，…，Y7。任何时刻最多只有其中一个信号为1（高电平），其余均为0（低电平）
三位输出编码：C,B,A
C = Y4 + Y5 + Y6 + Y7
B = Y2 + Y3 + Y6 + Y7
A = Y1 + Y3 + Y5 + Y7
8421BCD码编码器（高电平输入有效）
输入：Y0，Y1，…，Y9，分别代表十进制数字0~9
输出 ：4位编码，DCBA
优先编码器
克服二进制编码器仅允许1个输入信号有限的局限，允许两个以上 输入信号同时有效；
对所有输入信号进行优先级别排序，任何时刻只对优先级最高的输入信号编码，对优先级别低的输入信号则不响应，以保证编码器可靠工作。
优点：当有两个或两个以上的输入有效时，输出不会发生混乱。 广泛应用于计算机的优先中断系统、键盘编码系统中。
74147优先编码器（低电平有效）
10线-4线优先编码器，10个输入信号，低电平有效。4个输出端，反码输出
译码器
将二进制代码所表示的信息翻译成对应高低电平信号输出的过程称为译码，译码是编码的反操作。实现译码功能的电路称为译码器
二进制译码器
将每个输入二进制代码，译成对应的一根输出线上的高电平（低电平）信号
任一时刻最多只允许一个输出有效
3线-8线译码器（74138）
3个输入：A2，A1，A0；共8种组合
8个输出：Y7~Y0，低电平输出有效，且任一时刻最多只有一个输出有效。如：输入000时Y0输出有效，输入001时Y1输出有效。
3个使能控制：S0,S1,S2为使能输入，当它们为1、0、0时译码器才正常译码，否则禁止工作
多路选择器
从一组输入数据选出其中一个作为数据输出的电路
8选1多路选择器（74151）
功能一：8选1数据选择器
D7~D0为数据输入端，A2 A1 A0为选择控制端
下图通过简单的“和逻辑”就能解释，无需画真值表，注意最小项之间都是互斥的
功能二 ：多功能运算电路
根据上图，我们可以发现，输出的内容是变量A2A1A0的最小项的组合，因此很容易想到我们可以用它来计算A2A1A0的组合逻辑
D7~D0为控制输入端
通过D7~D0取不同的值，从输入变量A2、A1、A0的各个最小项中选取某几个最小项的或输出，实现不同的运算电路
3个变量，共有8个最小项，有2^8=256种功能，包含3变量的所有最小项表达式，可实现任意组合逻辑电路的设计。m0~m7代表8个最小项
竞争与冒险
竞争：在组合电路逻辑中，某个输入变量通过两条或两条以上的途径传到输出端，由于每条途径延迟时间不同，到达输出门的时间就有先有后，这种现象称为竞争
冒险：门电路因输入端的竞争，而导致输出端产生不正常的尖峰干扰冒险信号（毛刺）的现象，称为冒险
竞争冒险的原因：门电路的延时
竞争冒险的判断
代数法
逻辑函数 F 中，若某个变量（假定为 A ）同时以原变量和反变量形式存在，逻辑函数在一定条件下（其它变量取特定的值1或0）可以简化为F= A+
A或F=AA的形式， 则该逻辑电路存在冒险。F= A+A存在“0”冒险， F=AA存在“1”冒险。
时序逻辑电路
由组合逻辑电路和存储电路构成
锁存器和触发器
触发器
一种有记忆功能的逻辑单元电路，是构成时序逻辑电路的基本器件
特点：
有两个互非的输出Q和~Q，Q称为状态变量
Q=0，称为0态
Q=1，称为1态
无外加信号时，触发器保持原有状态不变，n级触发器可以记忆n位二进制信息的2^n种状态
在外加信号作用（触发）时，可以改变原态：Q^n–>Q^n+1
双稳态电路
可以有两种稳定的状态，储存一位二进制信息
但是，初次加电，初值未知，Q未知。缺少输入，状态无法变换，没有价值
改进：
这是使用NOR门实现的RS锁存器，注意不允许Q和~Q同值
RS：
RReset置0
SSet置1
基本RS锁存器
这是使用NAND实现的RS锁存器
锁存器的逻辑功能可以用功能表、特性表（真值表）、 特性方程（函数表达式）、状态转换图、时序图等表示
钟控RS锁存器
基本RS锁存器中，是由输入信号直接控制锁存器的输出。在数字系统中，为了协调各部分电路的运行，常常要求某些锁存器在时钟信号的控制下同时动作，这就需要增加一个控制端（时钟），只有在控制端作用脉冲时，锁存器才能动作，这种有时钟控制端的锁存器叫做钟控锁存器。
由于这里时钟信号为高电位（或低电位）时锁存器的状态 随输入变化，因此，钟控锁存器是电位触发方式的锁存器。钟控锁存器在时钟控制下同步工作，因此也称同步锁存器。
工作原理
在高电平，锁存器才会被触发
特性与基本RS锁存器相同
钟控D锁存器
问题：如何消除RS锁存器的不定状态（RS同时为1）？
可以想办法让RS始终互非，将输入由R、S双端输入，改为单端输入（D）， 即：将其S输入端改为D输入端，然后经过非门接R端。
即：时钟为0时输出不变（无法写入），时钟为1时输出D的值（可以写入），为电平触发，只有在高（低）电平时，锁存器的状态才可能发生变化
D触发器
D触发器就是一位寄存器，有效沿触发
一个D触发器可由两个反相的D锁存器构成
当CP=0时，主锁存器可以写入，从锁存器无法写入，N1更新为D的值，输出不变
当CP=1时，主锁存器输出不变且无法写入，从锁存器可以写入，输出N1的值
不管CP为0还是1，在这个期间里，D触发器都无法写入，输出都是不会变化的
因此，它宏观上表现为：在时钟上升沿时写入，其它时候都无法写入，只有在有效沿，它的输出才可能发生变化
n个D触发器就能构成n位寄存器，它们共用时钟信号和复位信号
钟控JK触发器
在RS锁存器的基础上，增加两条反馈线：
- Q 反馈到 R 钟控门的输入端，并把 R 改名为 K
- ~Q反馈到 S 钟控门的输入端，并把 S 改名为 J
有限状态机
比较简单，不细讲
时序逻辑电路设计与分析
数据寄存器/数据锁存器
一位寄存器就是D触发器，多位寄存器是由D触发器组成的
数据寄存器
边沿敏感
数据锁存器
电平敏感
移位寄存器
具有移位功能的寄存器，每来一个时钟脉冲，寄存器中数据就依次向左或向右移动一位
不难想到，n位移位寄存器就是由n个寄存器组成的，首位相接即可
4位右移移位寄存器
4位右移移位寄存器的工作方式：
串入并出
串并转换需要n个周期
串行输入，4个周期后Q3Q2Q1Q0并行输出
串入串出
把最右边的触发器的输出作为电路的输出。经过4个CP后， Q3 输出的是 最先串行输入的数据。
4位串行输入、串/并行输出双向移位寄存器
4位双向移位寄存器
计数器
可以统计输入脉冲个数的器件
时序电路的时序
寄存器的时序
寄存器存在孔径时间，可以类比为相机的快门时间。在孔径时间内输入必须稳定，这样才能存储正确的结果。
Tctq：稳定时间
同步时序电路时钟周期
保持时间约束
tccq：从时钟有效沿到输出发生变化的时间
主存储器
半导体存储器
从访问形式上可分为
随机访问存储器：RAM
只读存储器：ROM
RAM从实现原理上可分为：
静态随机访问存储器SRAM
用作cache
动态随机访问存储器DRAM
用作主存
存储芯片内部结构
存储芯片容量的基本描述（字单元数×每个字单元的位数 2^n × m）
字单元：存储器中数据的基本访问单位
1K×2：1024个字单元，每个字单元2位（二进制位）
意味着任一时刻可以（也只能）访问1024个独立字单元中的任意一个，每次读写的数据位数是一个字单元的容量（2位）
对于1K×2的存储芯片：
有多少个存储位元？共1K个（1024个）字单元，每个字单元2位 2048
存储位元 = 字单元 × 位数
需多少条地址线？按字单元寻址，1K个（1024个 或 2^10个）字单元 10
地址线需要能表示1024种不同的组合，1024是2^10，因此需要10条地址线
地址线 = n
需要多少条数据线？一次访问一个字单元，每个字单元是2位 2
数据线的数量决定了每次读写操作能够传输的数据位数
数据线 = m
存储芯片结构（一维地址结构）
棕线是地址线，蓝线是字选择线，黄块是存储位元，红线是数据线
当容量大了以后，一维地址结构需要的地址线太多了，而且很难分块管理。于是我们需要二维地址结构
二维地址结构（SRAM）
128×128
容量：4096×4
存储矩阵：2^7×2^7（128行×128列）
行译码：X译码，行地址需要7位A0~A6
一行包括32个字单元共128位，任何时刻只能其中1个字单元被选中，每个字单元的位线分别接到数据线D0D1D2D3
列译码：Y译码，以字单元为单位，每行32个字单元，需要5位A7~A11
注意：128×128存储单元矩阵行地址与列地址数不等，而64×256存储矩阵行地址数与列地址数相等。后者往往要除以位数之后再比较
一些概念辨析
字单元：每个字单元能够存储一个独立的m位二进制数，每个字单元对应一个确定的地址，换言之，按照行列地址去寻址，找到的就是一个字单元
行地址和列地址：就是地址线的数量。地址能找到的最小单位就是字单元，所以它们只和字单元数量有关。
如果说行地址和列地址数量相同，指的就是行地址线和列地址线数量相同，换言之，一行与一列的字单元个数相同
行选择线和列选择线：行译码器和列译码器输出端的导线数量，它们是真正连接到每行每列的
若地址线有n条，则行/列选择线就有2^n条
存储器扩展
单个存储器芯片不能满足存储系统的容量需求
位空间不够：芯片32K×8 主存32K×16
字空间不够：芯片8K×16 主存32K×16
位空间和字空间都不够：芯片8K×8 主存32K×16
存储扩展：位扩展、字扩展、混合扩展
存储器芯片的扩展
位扩展
存储器芯片提供的字空间满足整个存储空间的字空间要求，但存储器芯片的位空间不能满足要求
方法：多个存储器芯片的数据位空间拼在一起，分别存储数据的高4位和低4位
字扩展
存储器芯片提供的字空间不能满足整个存储空间的字空间要求，但存储器芯片的位空间满足要求
方法：多个存储器芯片的字空间（地址空间）拼在一起，使用片选信号来判断应该启用哪块芯片
下面的例子，如果把AB11 AB10 AB9 …… AB0拼起来，那么和一块字空间4K的芯片是完全一样的
图示如下：
混合扩展
存储器芯片提供的字空间和位空间都不能满足整个存储空间的字空间要求
方法：字扩展 + 位扩展
图示如下：
关于片选信号
片选信号不能简单地理解成“选择某一芯片的信号”，在存在字扩展的时候，多个芯片拼接在一起才能得到完整的字单元，那么在考虑片选信号位数的时候，就需要把这几个芯片当成一个整体来看待。
DRAM的刷新
刷新的实质：先将原信息读出，再由刷新放大器形成原信息重新写入的再生成的过程，等于一次读写
刷新周期：对DRAM的所有存储单元恢复一次原状态的时间间隔
刷新间隔：两次刷新的起始时间差（某行从第一次刷新到第二次刷新的等待时间）
行刷新间隔/刷新信号周期：两行刷新的起始时间差（连续两次刷新两行的时间间隔）
刷新时间：规定的一个周期内刷新的总时间
特点：
按行刷新，每次刷新一行，故而要有刷新地址计数器，其位数即行地址位数
刷新与CPU访问内存分开进行
刷新一行的时间等于读/写周期，因为刷新的过程与一次读写相同
在主存储器中，所有芯片的刷新同时进行
刷新方式
集中式
将刷新周期分成两部分：在一个时间段内，刷新存储器所有行，此时CPU停止访问内存；而另一个时间段内，CPU可以访问内存，刷新电路不工作。
如图：
由于在一个周期里，集中刷新的时间是固定的，很容易知道：刷新间隔=刷新周期
优点：速度快
缺点：当集中刷新时，不能进行任何的读写操作，这部分时间称作死区时间
死区时间所占的比率称为“死时间率”
分散式
CPU与刷新电路交替访问内存，一个存储周期刷新一行，下一个存储周期刷新另一行，直至最后一行后，又开始刷新第一行。此时存储周期不仅包含一次读写的时间，还包含了刷新时间，所以一共是两次读写的时间。
如图：
刷新间隔=刷新行数 × 存储周期
优点：不存在死时间
缺点：系统速度降低
分布式/异步
保证在一个刷新周期内，将存储芯片内所有行刷新一遍，两次刷新操作之间，可能等时间间距，也可能不等。是前两者的结合，可减少死时间，同时保证性能。
刷新间隔=刷新周期
高速缓冲存储器
Cache的原理
Cache结构示意：S组，每组E行，每数据块包含B个字节
Cache的读操作过程：
Cache的映射机制
由于Cache的块比主存块少，所以多个主存块映射到一个Cache块中
全相联映射
主存分为若干Block，Cache按同样大小分成若干Block
Cache中的Block数目显然比主存的Block数少得多
主存中的某一Block可以映射到Cache中的任意一Blcok
全相联映射的地址
主存的地址格式：块地址 + 块内地址 块内地址位数保证按字节寻址
Cache的Tag内容：与该Cache块对应的主存块的块地址
Tag位数 = 主存块地址位数
直接映射
假设Cache中有M块，那么将主存以M块为一区进行分区，一个区中的块按顺序与Cache对应的块映射
主存中某一块J的映射就是J mod M
直接映射的地址
主存的地址格式：区地址Tag + 区内块地址 + 块内地址 块内地址位数保证按字节寻址
Cache的Tag内容：与该Cache块对应的主存块的区地址
访存逻辑
主存地址：区地址 + 区内块地址 + 块内地址
拿着区内块地址，找到Cache相应块。比较这两块的区地址，如果相同，则说明命中，否则缺失
如图：
组相连映射
组相联映射是直接映射和全相联映射的折中
与全相联映射相比，组相联映射的约束更严格，每个主存块映射有一定范围
与直接映射相比，组相联映射的约束更宽松，每个主存块可以映射到一定范围内的任意一块
Cache分成K组，每组L块。主存的块J以下列原则映射到Cache的组I中的任意一块，其中：
I = J mod K
这意味着，主存中的每一块都对应着Cache中的一组
实际上主存与Cache都分成K组，主存每一组组内的块数与Cache一组内的块数不一致，主存组M内的某一块只能映射到Cache组M内，但可以是组M内的任意一块
不难理解，主存的组地址在空间上是不连续的，是周期性变化的
组相连映射的地址
主存的地址格式：组内块地址Tag + 组地址 + 块内地址
Tag的内容：主存中与该Cache数据块对应的数据块的组内块地址
访存逻辑
主存地址：组内块地址 + 组地址 + 块内地址 块内地址保证按字节寻址
拿着组地址，找到Cache相应组。同时将这组中每一块的Tag，和组内块地址比较，如果有相同的则说明命中，否则缺失
如图：
Cache的替换策略
Cache的缺失处理
CPU访问Cache缺失时，CPU必须等待数据装入Cache后才能访问Cache，这期间的时间损失称为缺失损失。
取出块的时间： 第一个字的延迟时间（存储器访问）+ 块的剩余部分的传送时间。
总线宽度？单字宽？
单字宽：每次可以传输1字
访问并传输1个字所需时间（15+1）
每次读取1字，共有4/1=4个总线事务
1+4*（15+1）= 65T
4字宽：每次可以传输4字
访问并传输4个字所需时间（15+1）
每次读取4字，共有4/4=1个总线事务
1+1*（15+1）= 17T
Cache块的替换
因此，组相联和全相联在替换时要采用策略替换
最近最少使用法LRU：将最久没有使用的块替换出去
Cache的每一块都设置一个计数器，用来标记该块已经多久没有使用过，初始时计数值都为0
访问命中时，所有块的计数值与命中块相比：
若计数值小于命中块的计数值，则该块的计数值加一
若计数值大于命中块的计数值，则该块的计数值不变
最后将命中块的计数器清零
访问缺失时，选择计数值最大的块来替换，被替换的块的计数器清零
注意：每次更新计数器的规模是本组内
先进先出法FIFO：将最先调入Cache的块替换出去
类似于将块排成队列，队首的块是最先调入的，队尾的块是最近调入的，用计数器标记块的顺序
访问命中时，无事发生
访问缺失时，当某块被装入或替换时，该块的计数器清零，同组的其它各块的计数值加一
需要替换时选择计数值最大的块来替换
Cache的性能分析
Cache的容量
不作特殊申明时，Cache的容量指所有Cache数据块的总容量
Cache实际总的存储容量，实际上还包含tag和valid bit等的位数
Cache性能
虚拟存储系统
硬磁盘存储器
基本结构
每个盘有两个盘面，每盘面有若干磁道，每磁道有若干扇区，每扇区容量512byte
性能指标
存储容量：盘面数 × 每盘面的磁道数 × 每磁道的扇区数 × 扇区容量
访问时间/寻址时间：寻道时间 + 寻区时间
- 寻道时间：磁头从当前位置定位到目标磁道所需时间
- 寻区时间：磁头定位到目标磁道后，等待目标扇区旋转到磁头下所需的时间（盘面转半圈所需的时间）
数据传输率：单位时间内传输的数据位数（b/s）
计算公式：每秒旋转的圈数 × 每条磁道的容量
页式虚拟存储器
虚地址格式和实地址格式
虚地址格式：虚页号 + 页内地址
实地址格式：实页号 + 页内地址
注意：虚拟页和实际页的大小是相同的。即它们的页内地址（页内偏移量）相同
页表
每个程序被分为若干虚页，操作系统会为每道程序都建立一个页表
页表用虚页号作索引
- 类比Cache组相联中的组索引、直接映射中的区内块地址
页表项中仅仅包含有效位、修改位和对应的实页号，不包含虚页号
- 与TLB或Cache中的Tag做区分
由上图可知，在无TLB的情况下，既要先根据虚地址，访问主存中的页表以获得实地址；其次还要根据实地址，访问主存中的物理页，前后共需两次访问主存，时间成本较高。
虚实地址的转换
快表TLB
本质上是一种Cache，存储部分活跃的页表项，包含了最近使用的那些页表项，是页表的真子集
因此不可能出现页表未命中但TLB命中的情况
TLB本质上是一种Cache，它的块就是我们想要的信息，也就是实页号。与它做映射的是整张页表，其中页表项就等价于之前所说的块，这样就能确保任一虚页都能映射到某一实页
TLB内容：(页表项就相当于Cache中的块）
- 全相联：虚页号（Tag） + 页表项
- 组相联：组内块地址（Tag） + 页表项
当我们要求TLB的大小时，主要就是求Tag的位数。全相联的Tag位数就等于虚页号，组相联的Tag位数等于组内块地址位数：
组内块地址位数 = 虚页号位数 - 组地址位数
页表中有时并不能囊括所有的虚页号，页表发生缺页等价于该页表项的有效位为0，代表此页一定不在主存中，即实页的信息并不在内存中，故而也一定不在 cache 中
总线与I/O
总线的一般概念
总线：一组公共的信号通道
总线的分类
片内总线：CPU内部的总线。是CPU内部各寄存器之间、寄存器与ALU之间传递信息的公共通道
系统总线：CPU、主存、I/O部件（I/O接口）之间传递信息的公 共通道。一般分为数据总线、地址总线和控制总线三部分
- 数据总线：传输数据
- 地址总线：传输存储器地址和I/O地址
- 控制总线：数据传输控制信号、总线请求和响应信号、其它控制信号
通信总线：用于计算机系统间或计算机系统与其它系统间的通信
性能指标
总线宽度：数据总线的位数
标准传输率：每秒传输的最大字节量（B/s），与总线宽度和频率相关。宽度越大，频率越高，传输率越大
总线的通信过程
总线的一次信息传送过程，大致可以分为5个阶段：
- 请求总线：由需要使用总线的部件或设备，提出总线使用申请
- 总线仲裁：仲裁器决定下一传输周期的总线使用权是否授予该部件或设备
- 寻址：获得总线使用权的部件或设备，发出地址和有关命令
- 信息传送：进行数据传输
- 状态返回：该部件或设备有关信息从总线上撤除，让出总线使用权
整个过程涉及两个方面的控制：总线仲裁、通信控制