数字逻辑 - Kaz的软件开发经验分享

进制与编码

进位计数制

基本要素

基数：计数制中所用到符号的个数
位权：用来表示不同数位上数值大小的一个的一个固定常数。
$R$ 进制数的的位权是 $R$ 的整数幂

表示方法

并列表示法
$(N)_R=K_{n-1}K_{n-2}K_{n-3}\cdots K_1K_0.K_{-1}K_{-2} \cdots K_{-m}$
多项式表示法
$(N)R=K{n-1} \times R^{n-1} + K*{n-2} \times R^{n-2} + K*{n-3} \times R^{n-3} + \cdots $

进制转换

graph TB

BIN(二进制)--位权乘法-->DEC(十进制)
BIN--三位一组-->OCT(八进制)
BIN--四位一组-->HEX(十六进制)


DEC--降幂法或除法-->BIN
DEC--降幂法或除法-->OCT
DEC--降幂法或除法-->HEX

OCT--按位拓展-->BIN
HEX--按位拓展-->BIN

十进制到任意进制：
- 降幂法：写出最高为二进制权值，作差，再将差减去二进制权值，以此类推。
- 除法：整数部分除权取余，小数部分乘权取整。
任意进制到十进制：按位权进行展开。
二进制到八进制和十六进制：以小数点为起点，三位（十六进制为四位）一组，用十六进制表示出来。缺位的补零。
八进制和十六进制到二进制：将每一位展开。

带符号数的表示

机器码和真值

真值：用 $+$ 和 $-$ 表示的二进制数。
机器码：将符号和数值一起编码表示的二进制数。

原码、反码、补码

类型	正数表示	负数表示	范围	例子(1 字节)
原码	符号为为 0，数值位转换成二进制	符号为 1，数值位转换成二进制	$-(2^N-1) \sim (2^N-1)$	$0$ = $0000$ $0000$ = $1000$ $0000$ $127$ = $0111$ $1111$ $-127$ = $1111$ $1111$
反码	同原码	符号为 1，数值位取反	$-(2^N-1) \sim (2^N-1)$	$0$ = $0000$ $0000$ = $1111$ $1111$ $127$ = $0111$ $1111$ $-127$ = $1000$ $0000$
补码	同原码	反码加 1	$-(2^N) \sim (2^N-1)$	$0$ = $0000$ $0000$ $127$ = $0111$ $1111$ $-127$ = $1000$ $0001$ $-128$ = $1000$ $0000$ $-1$ = $1111$ $1111$

原码、反码、补码的转换

正数： $原码=反码=补码$
负数：

graph TB

CC--减一-->IC
CC--数值位取反加一-->OC

IC--数值位取反-->OC
IC--加一-->CC(补码)

OC(原码)--数值位取反-->IC(反码)
OC--数值位取反加一-->CC

补码的加法和减法

加法 $ [X+Y]{补}=[X]{补} + [Y]_{补} $
减法 $[X-Y]_{补}=[X]_{补} + [-Y]_{补}$ ，其中 $[-Y]_{补}$ 只需对 $Y$ 求补即可。

进位和溢出

溢出：有符号数运算结果超过范围。
例如：
- 正数和正数相加得到负数
- 负数和负数相加得到正数

例子图形法判断溢出

假设数据的大小为 1 个字节，则补码的表示范围为 $ [-128,127] $。当溢出发生时，最高位由于长度限制被舍去，因此进入了下一个$ [-128,127] $轮回。

我们可以画一个圆，来表示 -128 到 127 直接的数，并标出 0：

对于含有正数的加法运算，结果会变大，即往逆时针方向旋转，当偏移到 127 左边时，发生溢出；
对于减数为正数的减法运算，结果会变小，即往顺时针方向旋转，当偏移到-128 右边时，发生溢出；

进位：无符号数运算结果超出范围。

求反和求补

求反：对每一个二进制位求反
求补：对每一个二进制位求反，再加一
关系：求补=求反+1

符号拓展

概念：位数少向位数多扩展，以表示更大或更小的数
方法：补码表示的正数扩展时前补 0，负数扩展时前补 1

例子

$[ + 46 ]_{补 }={0010},{1110} = {0000}, {0000} ,{0010} ,{1110}$

$[ - 46 ]_{补 }={1101},{0010} = {1111}, {1111} ,{1101} ,{0010}$

浮点数的表示

浮点数在内存中的存储方式

阶符

阶码

数符

尾数

浮点数的值 $V=数符 \times 尾数 \times 2^{阶码 \times 阶符}$
阶码是指数，尾数是纯小数
阶符和数符分别表示指数和数字的符号

例子

$(110.011)B=+0.110011 × 2^{+11}$

其中它在内存中的表示为：

110011

常用编码

BCD 码

使用 4 位二进制代码对十进制数字符号进行编码。

编码	8421(最常用)	2421	余 3 码
位权	8-4-2-1	2-4-2-1	无权
运算	直接十进制和二进制相互转换	按照位权运算	8421 码加 3
不足	容易出现加法问题	一个数可以有多种表示方法	无

格雷码

特点：任意两个相邻的数字仅有一位不同，表示方法不唯一。
转换：
- 二进制转换成格雷码：最高位不变，其余位和上位进行异或运算。

奇偶检验码

特点：
- 只有一位
- 只能检验出奇数个错误
- 编码简单、容易实现
检验方法

检验方法	错误时机
偶检验吗	奇数个 1
奇检验吗	偶数个 1

数 1 是奇数个还是偶数个：异或运算，结果为 1，则是奇数个 1。

逻辑代数

基本公式

规律	公式
交换律	$A+B=B+A,A \cdot B = B \cdot A$
结合律	$(A+B)+C=A+(B+C),(A \cdot B) \cdot C=A \cdot (B \cdot C)$
分配律	$A+(B \cdot C)=(A+B) \cdot (A+C),A\cdot(B + C)=A\cdot B + A\cdot C$
同一律	$A+0=A, A+0=A$
零律	$A+1=1, A \cdot 0=0$
矛盾律	$A \cdot \overline{A}=0$
排中律	$A+\overline{A}=1$
幂等律	$A+A=A, A \cdot A = A$
德摩根律	$\overline{A + B} = \overline{A} \cdot \overline{B},\overline{A \cdot B} = \overline{A} + \overline{B}$
吸收律	$A+A \cdot B=A, A \cdot (A+B) = A$
并项公式	$A \cdot \mathbf{B} + A \cdot \mathbf{\overline{B}} = A,(A + \mathbf{B}） \cdot (A + \mathbf{\overline{B}}) = A$
消因子公式	$A+\mathbf{\overline{A}} \cdot B=A + B, A \cdot (\mathbf{\overline{A}+B}) = A \cdot B$
消项公式	$A \cdot B + \overline{A} \cdot C + {\mathbf{B \cdot C}} = A \cdot B + \overline{A} \cdot C$

三大规则

代入规则

将出现变量的位置用逻辑函数替代，等式仍然成立。

反演规则

反函数的表示： $\overline{F}$
求反函数的方法：
1. 将 $\cdot$ 变成 $+$ ，将 $+$ 变成 $ \cdot$
2. 将 $0$ 变成 $1$ ，将 $1$ 变成 $0$
3. 将变量全部取反
4. 保持运算顺序不变

注意乘号的省略

例子
若 $F=\overline{A}B+C\overline{D}$ ，则 $\overline{F}=(A+\overline{B})(\overline{C}+D)$

对偶规则

对偶函数的表示： $F'$
求对偶函数的方法：
1. 将 $\cdot$ 变成 $+$ ，将 $+$ 变成 $ \cdot$
2. 将 $0$ 变成 $1$ ，将 $1$ 变成 $0$
3. 保持运算顺序不变

无需对变量取反，但 0 和 1 仍要变换。

例子
若 $F=\overline{A}B+C\overline{D}$ ，则 $F'=(\overline{A}+B)(C+\overline{D})$

自对偶函数： $F'=F$

常见复合逻辑

逻辑	函数表示	功能
与非逻辑	$F=\overline{ABC...}$	当 $A$ , $B$ , $C$ 全部为 1 时， $F$ 为 0，否则为 1
或非逻辑	$F=\overline{A+B+C+...}$	当 $A$ , $B$ , $C$ 全部为 0 时， $F$ 为 1，否则为 0
与或非逻辑	$F=\overline{AB+CD+...}$	与项均为 0 时，F 为 1，否则 F 为 0
异或逻辑	$F=A \oplus B=A\overline{B}+\overline{A}B$	$A$ 和 $B$ 不同时为 1，否则为 0
同或逻辑	$F=A \odot B=\overline{A}\cdot\overline{B}+A\cdot B$	$A$ 和 $B$ 不同时为 0，否则为 1

同或逻辑和异或逻辑互为相反，也互为对偶
当多个变量进行异或运算时，若有奇数个 1，则结果为 1，否则结果为 0。

逻辑函数表达式

基本形式

与或式：积之和
或与式：和之积

最小项和最大项

最小项

定义：与项包含全部变量，每个变量以原变量和反变量的形式出现，且只出现一次
表示： $m_i$ ，其中 $i$ 是与项中反变量替换成 0，原变量替换成 1 后转换成的 10 进制数。
个数： $2^{变量个数}$
性质：
- 任意两个最小项相与为 0
- 所有最小项相或为 1

最小项和最大项的关系

存在互补关系
- $\overline{m_i} = M_i$

标准表达式

最小项表达式： $\sum m(i_1,i_2,...)$
- 求法：逐项画真值表
最大项表达式： $\prod M(i_1,i_2,...)$
最小项表达式的性质
- $F_1$ 和 $F_2$ 相或， $\sum$ 括号内的数取并集
- $F_1$ 和 $F_2$ 相与， $\sum$ 括号内的数取交集
- $F_1$ 取反， $\sum$ 括号内的数相取补集

例子
若 $F_1(A,B,C)=\sum m(1,3,5)$ , $F_2(A,B,C)=\sum m(0,1,2,3)$ ，则

$\overline{F_1}=\sum m(0,2,4,6,7)$
$F_1+F_2=\sum m(0,1,2,3,5)$
$F_1F_2=\sum m(1,3)$

相互转化
- 最大项表达式中括号内的数，等于最小项表达式中的数的补集

例子
若 $F(A,B,C)=\sum m(1,3,5)$ ，则 $F=\prod M(0,1,2,4,6,7)$

标准表达式和真值表、函数值的关系
- 对于标准与或式，括号中的每个数对于的二进制数函数值为 1，其余为 0
- 对于标准或与式，括号中的每个数对于的二进制数函数值为 0，其余为 1

例子
若 $F(A,B,C)=\sum m(1,3,5)=\prod M(0,1,2,4,6,7)$ ，则其真值表如下：

A	B	C	F
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

任意项和无关条件

任意项：不会出现的逻辑变量取值对应的函数值，由 $d$ 和 $ \emptyset $ 表示。
无关条件：由不会出现的逻辑变量取值构成的逻辑函数表达式
约束条件：限制逻辑变量只能取某些值的表达式

例子

一个带有约束条件的逻辑函数表达式：
$F(A,B,C)=\sum m(1,3,5) + \sum d(0,1,2)$

逻辑函数的化简

代数化简法

常用公式：吸收律、并项公式、消因子公式、消项公式
与或式化简两个条件：与项个数最少、每个与项中变量个数最少
或与式化简方法
- 求对偶式
- 将对偶式化简成最简与或式
- 将最简与或式对偶

卡诺图化简法

行列排布：按照格雷码进行排布： $00$ 、 $01$ 、 $11$ 、 $10$
合并规则：相邻项可合并，需要注意边角位置。
方格填写：只填写 1 和任意项 d。
要求：
- 覆盖全部 1，但不要求全部覆盖 d
- 圈尽量小
- 圈尽量大
优先保证圈的个数，再保证圈的大小

例子

带任意项的化简：

组合逻辑电路

特点

由逻辑门电路构成，不含记忆元件
信号单向传输，不含任何回路

分析

步骤

根据电路图写出表达式
化简表达式
写出真值表
进行功能描述

案例

不一致电路：检测输入中各位是否不一致
半加器：输入两位二进制数，得到结果和进位
全加器：输入两位二进制数和进位，得到结果和进位
编码转换：8421 码转余 3 码

设计

步骤

画卡诺图
求最简与或式
根据给定门电路，调整表达式

竞争和险象

竞争：
- 概念：输入信号经过不同路径到达终点的时间不一样
- 判断：一个逻辑函数表达式中既出现了原变量，又出现了反变量
险象：
- 概念：输入信号的变化引起非预期的错误输出
- 判断：其他逻辑变量取某些值时，出现 $X+\overline{X}$ 或 $X\cdot\overline{X}$
- 消除：根据 消项公式 增加冗余项，使得其他逻辑变量取这些值时，出现 $X+\overline{X} + 1$ 或 $X\cdot\overline{X} \cdot 0$

例子

$F=AB+\overline{A}C$
- 既有 $A$ ，又有 $\overline{A}$ ，有竞争
- 当 $B=C=1$ 时， $F=A+\overline{A}$ ，有险象
- 根据 消项公式,为其加上冗余项 $BC$ ，即 $F=AB+\overline{A}C+BC$ ，使得当 $B=C=1$ 时，出现 $A+\overline{A}+1$
$F=A\overline{B}+\overline{A}B$
- 既有 $A$ ，又有 $\overline{A}$ ，有竞争
- 无论 $B=1$ 还是 $B=0$ ，都不会出现 $F=A+\overline{A}$ 的情况，没有险象

时序逻辑电路

时序电路

概念

构成：组合电路和存储电路
常用符号：
- 输入 $X$
- 存储电路输入 $Y$
- 次态 $y^{n+1}$
- 输出 $Z$
状态：
- 现态：某个时钟脉冲到来前电路所处的状态
- 次态：时钟脉冲后电路的状态
- 关系：次态不断成为现态，产生新的次态
工作方式：
- 同步：各触发器的时钟脉冲信号 CP 和统一的时钟信号相连接
- 异步：电路没有统一的时钟信号同步，输入信号的变化直接导致电路状态的变化
输入输出关系：
- Mealy 型：
  - 输出和输入、历史输入有关
  - 特点： $Z$ 和 $X$ 有关
- Moore 型：
  - 输出和输入、历史输入无关，或没有输出
  - 输入会转变成状态，再输出
  - 特点： $Z$ 和 $X$ 无关，或者没有 $Z$

描述

逻辑函数表达式：
- 输出函数 $Z=xxx$
- 激励函数 $Y=xxx$
- 次态函数 $y^{n+1}=xxx$
状态表分成两块，左边是输入和现态，右边是输出和次态
状态图
- 用一个点表示状态
- 用箭头表示状态变化，上面标注输入和输出

基本触发器

R-S 触发器

次态方程： $Q^{n+1}=S+R \cdot Q$
功能表：

R	S	功能
0	0	未知
0	1	置 0
1	0	置 1
1	1	状态不变

激励表：根据状态变化查询条件

$Q$	$Q^{n+1}$	R	S
0	0	d	1
0	1	1	0
1	0	0	1
1	1	1	d

默认触发方式：上跳触发

J-K 触发器

次态方程： $Q^{n+1}=J\overline{Q}+\overline{K}Q$
功能表：

J	K	功能
0	0	不变
0	1	置 0
1	0	置 1
1	1	翻转

激励表：根据状态变化查询条件

$Q$	$Q^{n+1}$	J	K
0	0	0	d
0	1	1	d
1	0	d	1
1	1	d	0

默认触发方式：上跳触发

D 触发器

次态方程： $Q^{n+1}=D$
功能表：

D	功能
0	置 0
1	置 1

激励表：根据状态变化查询条件

$Q$	$Q^{n+1}$	D
0	0	0
0	1	1
1	0	0
1	1	1

默认触发方式：上跳触发

T 触发器

次态方程： $Q^{n+1}=\overline{Q}$
功能表：

D	功能
0	不变
1	翻转

激励表：根据状态变化查询条件

$Q$	$Q^{n+1}$	D
0	0	0
0	1	1
1	0	1
1	1	0

默认触发方式：下跳触发（此时 CP 处有个圈）

分析

步骤

列方程：列出输出函数、次态方程和激励函数表达式
异步时序电路需要注意时钟脉冲的表达式
列状态表
画状态图
功能描述

案例

(可逆)计数器：加 1 计数，减 1 计数
序列检测器
串行加法器
- 优点：不限制位数
- 缺点：不能同时输入，不能并行计算

自校功能

自校：特殊的状态能够回到原来的状态
挂起：特殊的状态能够不能回到原来的状态

设计

步骤

画原始状态图和状态表
状态化简
- 等效状态：
  - 输出相同
  - 次态相同 $A \overset{1}{\rightarrow} B$ , $C \overset{1}{\rightarrow} B$
  - 次态交错 $A \overset{1}{\rightarrow} B$ , $B \overset{1}{\rightarrow} A$
  - 次态等于现态 $A \overset{1}{\rightarrow} A$
  - 次态循环 $A \overset{1}{\rightarrow} C$ $B \overset{1}{\rightarrow} D$ $C \overset{1}{\rightarrow} A$ $D \overset{1}{\rightarrow} B$
  - 等效对 $S_i$ 和 $S_j$ 的次态已为等效状态
- 等效类：等效状态构成的集合
状态编码
- 相同输入，相同次态的现态：相邻编码
- 相邻输入，同一现态的次态：相邻编码
- 输出相同的现态：相邻编码
求真值表：根据各触发器的激励表
求表达式：使用卡诺图进行化简