[CO]CO 理论概要(Updating)

序

这是计组理论复习概要。

概述

计算机基本组成与结构

计算机基本组成

• 硬件

  • 运算器
  • 存储器
  • I/O
  • 控制器

• 软件

  • 系统软件（操作系统）
  • 应用程序

计算机总线结构

总线Bus：符合一定标准的一组公用信息通道。

计算机层次结构

高级语言 -> 虚拟机 M3
  |           |
  |           |
汇编语言 -> 虚拟机 M2
  |           |
  |           |
机器语言 -> 实机 M1

• 指令集系统

计算机中数的表示

关于数制，参考这里。

• 无符号数

• 有符号数

• 浮点数

  • IEEE 754：符号Sign，阶码Exponent，尾数Mantissa。

• 布尔值

  • 真1，假0

• 西文字符

  • ASCII

• 汉字字符

  • GB2312
  • CJK
  • Unicode

计算机基本工作原理

• 机器指令

  • 操作码
  • 操作数地址

• 程序

  • 程序计数器Programme Counter

• 冯·诺伊曼计算机的特点

  • 由运算器，存储器，控制器和 I/O 组成
  • 指令和数据的储存没有区别，放在存储器中按地址访问
  • 指令由操作码和地址组成

• 摩尔定律

组合逻辑电路

逻辑代数

基本概念

• 逻辑代数 L = { K, ∨, ∧, ￢, 0, 1}，其中 K 为逻辑变量集。

  • 与 ·
  • 或 +
  • 非
  • 异或、同或等
  • 运算优先级：() -> ￢ -> ∧ -> ⊕ -> ∨

• 逻辑门符号表示

• 公理系统

  • A != 0 -> A = 1; A != 1 -> A = 0;
  • 0 · 0 = 0; 1 + 1 = 1;
  • 1 · 1 = 1; 0 + 0 = 0;
  • 0 · 1 = 0; 1 + 0 = 1; 1 · 0 = 0; 0 + 1 = 1
  • ￢0 = 1; ￢1 = 0;

定律、定理和规则

• 基本定律

  • 交换律
  • 结合律
  • 分配律
  • 0-1 律
  • 互补律

• 基本定理

  • 重叠律 A + A = A; A · A = A;
  • 吸收律：两个乘积项中，若有一个乘积项的部分因子，恰好是另一个乘积项的全部，则这个乘积项是多余的
  • 还原律：负负得正
  • 德摩根律
  • 更多……

• 规则

  • 代入规则
  • 反演规则：+ · 互换，0 1 互换，变量变为反变量，得到反函数
  • 对偶规则：+ · 互换，0 1 互换，变量保持不变，得到对偶式

逻辑函数

• 与或式 AB + CD

• 或与式 (A + B)(C + D)

• 与或非式 ￢(AB + CD)

• 最小项表达式：最小项构成的与或式（积之和式）（标准与或式）

  • 把输出为 1 的输入组合写成乘积项的形式，其中取值为 1 的输入用原变量表示，取值为 0 的输入用反变量表示，然后把这些乘积项加起来
  • 最小项：n 个变量构成的与式中，每个变量或其反变量有且仅有一次出现
  • n 个变量有 2ⁿ 个最小项

• 最大项表达式：最大项构成的或与式（和之积式）（标准或与式）

  • 把使输出为 0 的输入组合写成和项的形式，其中取值为 0 的输入用原变量表示，取值为 1 的输入用反变量表示，然后把这些和项乘起来
  • 最大项：n 个变量构成的或式中，每个变量或其反变量有且仅有一次出现
  • n 个变量有 2ⁿ 个最大项

• 逻辑函数化简

  • 最简与或表达式：乘积项最少，同时乘积项中的变量尽可能少
  • 最简或与表达式：和项最少，同时和项中的变量尽可能少
    • 利用对偶规则化为与或表达式，得到最简与或表达式，利用对偶规则化为最简或与表达式
  • 卡诺图

逻辑门电路

晶体管和 MOS 管

• P 型半导体：带正电的空穴导电

• N 型半导体：带负电的自由电子导电

• PN 结：P 型和 N 型制作在一起

  • 正向偏置：正极接 P 区，负极接 N 区，PN 结导通
  • 反向偏置：正极接 N 区，负极接 P 区，PN 结截止

• 晶体二极管

  • 正向导通：外加电压大于开启电压
  • 反向截止：外加反向电压或电压小于开启电压
  • 击穿：反向电压大于阈值（0.7V），二极管被击穿，失去单向导电性

• 晶体三极管

  • 导通：U_BC > 0, U_BE > 0.7V
  • 截止：U_BC < 0, U_BE < 0.7V

• MOS 管

  • 导通：V_GS > 开启电压
  • 截止：V_GS = 0

门电路

• 与或非门的实现方式

• CMOS 和 TTL 的对比

  • CMOS 功耗相对低，抗干扰能力相对强，带载能力强
  • TTL 功耗相对高，速度相对快，抗干扰能力相对弱

基本组合逻辑部件设计

• 半加器：两个 1 位二进制数相加求和，并向高位进位，不考虑低位进位

• 全加器：两个 1 位二进制数相加求和，并向高位进位，考虑低位进位

• 多位加法器

  • 并行加法器——串行进位
  • 并行加法器——并行进位

• 溢出判断

• 乘法器

• 数值比较器

• ALU（运算逻辑单元电路）

• 编码器

  • 2ⁿ 线 — n 线编码器（独热编码）
  • 优先编码器（输出优先级最高的输入信号对应编号的反码）

• 译码器

  • n 线 — 2ⁿ 线译码器
  • 显示译码器（七段码等）

• 多路选择器多路复用器，MUX

  • 8 选 1 MUX

• 竞争与冒险

  • 竞争：某个输入变量通过两条或两条以上的路径传输到输出端，由于每条路径的延迟不同，导致不同路径的数据到达输出端的时间又先后
  • 冒险：门电路由于输入端的竞争，在输出端出现尖峰干扰信号毛刺的现象
  • 核心原因：门电路的延迟
  • 代数法判断：逻辑函数 F 可以简化为 F = A + ~A 或 F = A · ~A
  • 卡诺图法
  • 消除竞争冒险

时序逻辑电路

锁存器和触发器

• 触发器Flip-Flop, FF是实现电路记忆功能的基本单元电路

  • 两个互非的输出 Q 和 ~Q，Q 称为状态变量
  • Q = 0 称为 0 态，Q = 1 称为 1 态
  • Qⁿ 称为原态，Qⁿ⁺¹ 称为次态

• RResetSSet 锁存器

  • 与非门 RS 锁存器
  • 或非门 RS 锁存器
  • 输入：~R，~S
  • 保持：~R = 1，~S = 1
  • 置 0：~R = 0， ~S = 1 （低电平有效）
  • 置 1：~R = 1，~S = 0 （低电平有效）
  • 非法：~R = ~S = 0 （产生竞争）
  • 约束条件：~R + ~S = 1
  • 特性方程：反映次态、原态和输入之间关系的函数表达式：
  $$Q^{n+1}=S_D\bar{R}_D+\bar{S}_D\bar{R}_DQ^{n}\\ = S_D+\bar{R}_DQ^n$$
  • 状态转移图
  • 时序图

• 钟控 RS 锁存器

  • 加入时钟信号CP，高电位（或低电位）时改变锁存器状态，因此为电位触发方式的锁存器
  • 亦称同步锁存器
  • CP = 0 时，~S 和 ~R 恒为 1，保持；clk = 1 时，由 ~S 和 ~R 决定
  • 仍有约束条件

• 钟控 D 锁存器

  • 将 R，S 两个输入端换为一个输入端 D，S = D，R = ~D，保证二者恒为互非
  • 特性方程：
  $$Q^{n+1} = D\quad(CP=1) \\ Q^{n+1} = Q^n\quad(CP=0)$$

• D 触发器

  • 由两个反相的 D 锁存器构成
  • 锁存器 L1 称为主Master锁存器，L2 称为从Slave锁存器
  • 触发器是时钟有效沿触发，锁存器是电位触发
  • 增加使能端
  • 在时钟信号上一般不要设置逻辑，否则可能因延迟导致时序错误
  • 增加复位端
    • 同步复位：复位信号有效和时钟沿有效才复位
    • 异步复位：复位信号有效则复位

• JK 触发器

  • 在钟控 RS 锁存器基础上，把 ~R = 1; ~S = 1 的情况变为翻转功能
  • 翻转：Qⁿ⁺¹ = ~Qⁿ
  • 特性方程
  $$Q^{n+1}=J\bar{Q}^n+\bar{K}Q^n$$
  • 状态转换图

有限状态机

关于有限状态机，参考这里。

• 同步时序电路

  • 每个电路元件都是组合逻辑或寄存器，且至少有一个寄存器
  • 每一个环路至少有一个寄存器
  • 所有寄存器接受同一个时钟信号
  • 可以描绘成有限状态机

• 有限状态机

  • 次态逻辑
  • 状态存储
  • 输出逻辑
  • Moore 机
    • 输出信号与当前状态有关
  • Mealy 机
    • 输出信号与当前状态及当前输入信号有关
  • 必须有时钟信号和复位信号
  • 状态编码方式
    • 二进制编码
    • 格雷编码
    • 独热编码

时序逻辑电路设计分析

• 寄存器

  • 触发器和控制门电路组成
    • 一个触发器存储一位
    • 控制门电路保证各触发器同时接收数据
  • 写/读/复位清零
  • 边沿或电位触发
  • 数据寄存器
    • 边沿触发器组成
  • 数据锁存器
    • 电位触发器组成
  • 移位寄存器
    • 具有移位功能的寄存器。每来一个时钟脉冲，寄存器中数据就依次向左或向右移一位

• 计数器

  • 统计输入的脉冲个数
  • 同步计数
    • 各触发器同时翻转，工作频率高
  • 异步计数
    • 脉冲信号只作用于最低位触发器，高位触发器待低位触发器翻转后才能翻转，工作频率低
  • 进制
  • 加法/减法

• 时序电路的时序

  • 建立Setup时间：触发时钟沿之前，输入必须稳定的时间
  • 保持Hold时间：触发时钟沿之后，输入必须稳定的时间
  • 孔径时间：T_Setup + T_Hold
  • Clock-to-Q 时间：从触发时钟边沿开始到输入稳定的时间
  • 时钟周期 >= T_CTQ + T_CDL最长路径延迟 + T_Setup + 时钟偏移（一般忽略）
  • T_CTQ + T_CDS最短路径延迟 >= T_Hold，否则无法锁存输入，因为在上一个输入的保持时间内，输入发生了变化

主存储器

概述

分类

• 按介质

  • 半导体（易失）
  • 磁介质（非易失）
  • 光盘（非易失）

• 按访问方式

  • 随机访问存储器RAM
    • 静态随机访问存储Static RAM：用作 Cache
    • 动态随机访问存储Dynamic RAM：用作主存
  • 只读存储器ROM
  • 顺序访问存储器Tape
  • 直接访问存储器Disk

• 按功能

  • 高速缓冲存储器Cache
  • 主存储器
  • 辅助存储器
  • 控制存储器

性能指标

• 访问时间 T_A

  • RAM：访问时间指读或写操作所用时间，即从给定地址到存储器完成读或写操作所需时间
  • 其它：指将读写机构定位到目标位置所需的时间

• 存储周期 T_C

  • 仅对 RAM 而言：指两次访问存储单元间的最小时间间隔
  • T_C > T_A

• 带宽/数据传输率

• 存储器的性能特征：成本低的容量大，速度慢；成本高的容量小，速度快

存储单元电路

• 基本要求

  • 具有两种稳定状态，表示 0 和 1
  • 可以实现状态写入
  • 可以实现状态感知

• SRAM 存储单元电路

• DRAM 存储单元电路

• ROM 存储单元电路

非易失存储器

• 相变存储器PCM

  • 非易失
  • 空闲时功率低
  • 延迟高
  • 活跃时功率高
  • 寿命短

• 自旋转矩磁随机存取存储器STT-MRAM

• 忆阻器Memristor

存储器芯片结构

• 基本描述

  • 字单元数 * 每个字单元的位数例如 1K * 2：1024 个字单元，每个字单元 2 位。
  • 存储位元数：字单元数 * 每个字单元的位数，如 1024 * 2 = 2048
  • 地址线数：按字单元寻址，1024（2¹⁰）个字单元，需要 10 条地址线
  • 数据线数：一次访问一个字单元，每个字单元 2 位，需要 2 条数据线
  • 2ⁿ * m 个存储位元，需要 n 条地址线和 m 条数据线

• 二维地址结构

  • SRAM 的情况：例如 4096 * 4：2¹⁴ 个存储位元，划为 2⁷ * 2⁷ 的存储矩阵。一行 2⁷ = 128 个存储位元，每 4 个为 1 字单元，共 32（2⁵） 个字单元。
    • 行地址线数：2⁷ 个存储位元，使用 7 条地址线（X 译码）
    • 列地址线数：2⁵ 个字单元，使用 5 条地址线（Y 译码）
    • 数据线数：4
  • DRAM 的情况：例如 4096 * 4：2¹² 个字单元，划为 2⁶ * 2⁶ 的存储矩阵。
    • 行地址线数 = 列地址线数 = 6
    • 数据线数：4

存储器扩展

• 位扩展：多个存储器芯片的数据位空间拼在一起例如 2 个 1024 * 4 的 SRAM 芯片构造 1024 * 8 的存储器

• 字扩展：多个存储器芯片的字空间拼在一起例如 4 个 1024 * 8 的 SRAM 芯片构造 4096 * 8 的存储器。地址线需要增加 2 条以选择是哪一片 SRAM 芯片中的数据

• 混合扩展：综合运用位扩展和字扩展例如 8 个 4096 * 4 的 SRAM 芯片构造 16384 * 8 的存储器（两个一组进行位扩展，四组进行字扩展）

• 同一字空间的存储芯片选择信号连在一起

• 同一位空间的数据线连在一起