LCSD Lesson 1

Chapter I 数字系统与信息#

十进制及其特点#

• 0 - 9 十个符号
• Base: 10
• Power: 10^i

二进制及其特点#

• 0 - 1 两个符号
• Base: 2
• Power: 2^i

十进制和二进制转换#

二进制转十进制：直接乘 Power

十进制转二进制：整数部分整除 2，小数部分连乘 2

其它转换#

十六进制、八进制转十进制：直接乘 Power

十六进制、十进制、八进制和二进制互转：直接按 2 的次数为数字分组即可，转换的时候统一先转换到二进制。

Chapter II 逻辑代数#

逻辑代数的基本概念#

一个由逻辑变量集 K 、常量 0 和 1 以及 或与非 三种基本运算组成的一个封闭系统

$$L = \{K, +, \cdot, -, 0, 1\}$$

常量：0 和 1 表示的假和真

变量：变化的逻辑量

逻辑门介绍#

相关公理#

Axiom 1 交换律

对于任意逻辑变量 A、B，有

$$A + B = B + A \\ A \cdot B = B \cdot A$$

Axiom 2 结合率

对于任意的逻辑变量 A、B、C，有

$$(A + B) + C = A + (B + C) \\ (A \cdot B) \cdot C = A \cdot (B \cdot C)$$

Axiom 3 分配率

对于任意的逻辑变量 A、B、C，有

$$A \cdot (B + C) = A \cdot B + A \cdot C \\ A + (B \cdot C) = (A + B) \cdot (A + C)$$

Axiom 4 0-1 律

对于任意的逻辑变量 A，有

$$A + 0 = A,\ A \cdot 1 = A \\ A + 1 = 1,\ A \cdot 0 = 0$$

这条公理可以用来化简电路（关于逻辑门封锁与开放的控制）

Axiom 5 互补律

对于任意逻辑变量 A，存在唯一的 $\bar{A}$ ，使得

$$\bar{A} + A = 1 \\ \bar{A} \cdot A = 0$$

逻辑运算#

或运算：逻辑加

与运算：逻辑乘

非运算：取反

与非运算：通用逻辑门

$$F = \overline{A \cdot B \cdot C \cdots} \\ F = \overline{\overline{A \cdot B} \cdot 1} = \overline{\overline{A \cdot B}} = A \cdot B \\ F = \overline{\overline{A \cdot 1} \cdot \overline{B \cdot 1}} = \overline{\bar{A} \cdot \bar{B}} = A + B \\ F = \overline{A \cdot 1} = \bar{A}$$

或非运算：通用逻辑门

复合运算：

• 异或运算

$$F = A \oplus B = \bar{A}B + A\bar{B}$$

​ 异或运算是两变量运算，若需多变量进行异或运算可以如下进行：

$$F = A \oplus B \oplus C \oplus D = (A \oplus B) \oplus (C \oplus D) \\ \mathrm{or}\ F = [(A \oplus B) \oplus C] \oplus D$$

​ 两者不同则为 1，相同则为零。（工程应用：磁盘阵列 RAID）

• 同或运算

$$F = A\odot B = \bar{A} \cdot \bar{B} + A \cdot B$$

​ 两者相同则为 1，不同则为零

基本定理和规则#

Theorem 1

$$0+0=0\ 1+0=1\ \ \ \ 0·0=0\ 1·0=0 \\ 0+1=1\ 1+1=1\ \ \ \ 0·1=0\ 1·1=1$$

Theorem 2 等幂律

$$A + A = A;\ A \cdot A = A$$

Theorem 3 吸收律 (项、变量)

$$A + A \cdot B = A;\ A \cdot (A + B) = A$$

Theorem 4 消去律

$$A + \bar{A} \cdot B = A + B \\ A \cdot (\bar{A} + B) = A \cdot B$$

Theorem 5 还原律

$$\bar{\bar{A}} = A$$

Theorem 6 德摩根定理 (De Morgan’s Theorem)

$$\overline{A + B} = \bar{A} \cdot \bar{B} \\ \overline{A \cdot B} = \bar{A} + \bar{B}$$

Theorem 7 并项律

$$A \cdot B + A \cdot \bar{B} = A \\ (A + B) \cdot (A + \bar{B}) = A$$

Theorem 8

$$A \cdot B + \bar{A} \cdot C + B \cdot C = A \cdot B + \bar{A} \cdot C \\ (A + B) \cdot (\bar{A} + C) \cdot (B + C) = (A + B) \cdot (\bar{A} + C)$$

三大重要规则：

• 规则1：代入规则 任何一个含有变量 A 的逻辑等式，如果将所有出现 A 的位置都代之以同一个逻辑函数 F，则等式仍然成立。 （注：代入规则使用时必须注意同一变量的全代入）

• 规则2：反演规则 将逻辑函数表达式 F 中所有的 “$\cdot$” 变成 “$+$” ，“$+$” 变成 “$\cdot$” ；“0” 变成 “1” ，“1” 变成 “0” ；原变量变成反变量，反变量变成原变量。保持原函数中运算顺序不变，得到的新函数为原函数的补函数（$\bar{F}$），即值为 F 的非。

• 规则3：对偶规则 若将逻辑函数表达式 F 中所有的 “$\cdot$” 变成 “$+$” ，“$+$” 变成 “$\cdot$” ；“0” 变成 “1” ，“1” 变成 “0” ，并保持原函数中的运算顺序不变（注意：变量或反变量的文字 literal 不变！），则所得到的新的逻辑表达式称为函数 F 的对偶式，记作 F’。 （注：若两个逻辑函数表达式相等，则其对偶式也相等。利用该规则可使公式证明减少一半。原式不等于对偶式！）

逻辑函数及其表示方法#

1. 逻辑函数 (Boolean Function) 的定义

$$F = f(A_1, A_2, \dots, A_n)$$

• 逻辑函数和逻辑变量一样，取值只有 0 和 1 两种可能。
• 任何组合逻辑电路的功能都可由相应的逻辑函数完全描述，故可借助逻辑函数表达式分析组合逻辑电路。

2. 逻辑函数的表示方法

• 1) 逻辑表达式 逻辑表达式中的运算优先级排序： $( ) \rightarrow \overline{\ \ } \rightarrow \cdot \rightarrow \oplus \rightarrow +$ (括号 $\rightarrow$ 非 $\rightarrow$ 与 $\rightarrow$ 异或 $\rightarrow$ 或)

• 2) 真值表 (Truth Table) 包含所有可能的输入组合，一一列出对应的函数输出值。

• 3) 卡诺图 (Karnaugh map, K-map) 由逻辑变量所有取值组合的小方格所构成的拓扑结构（连接关系）。 K-map 的性质：

  1. 横坐标、纵坐标均是格雷码 (Gray code)。
  2. 每一行、每一列均是首尾相接。
  3. K-map 的几何拓扑结构是二维环面 (torus, “甜甜圈”)，每个瓦片都有 4 个邻居。
  4. 平面上绘制的 K-map 最多可表示 4 个自由变量 (x轴2个，y轴2个)。
  5. 三维欧几里得空间最多只能容纳 6 个自由变量的 K-map，用长方体来圈出主蕴含项。 注：表达式中各对应组合的项，小写的 $m$ 称为最小项 (minterm)。

• 4) 波形图 穷举出输入变量所有可能取值的组合，用高低电平表示 1 和 0。使用格雷码输入可减少波形边沿的切换次数。

逻辑函数的表达形式#

逻辑函数的表达式形式不唯一，需讨论基本形式、规范形式 (Canonical form) 及其相互转换。

1. 逻辑函数表达式的基本形式

• 1) “与-或” 表达式 (SOP form, Sum-of-Product) 由文字 (literal) 相与组成的蕴含项 (implicant) 进行“或”运算构成的表达式。 例如：$F = \bar{A}B + A\bar{B}C + \bar{C}$ 每个“与项”可以是单个变量的原变量或者反变量，也可由多个组成。“与项”也称“积项”，“与-或”表达式又称“积的和”表达式。

• 2) “或-与” 表达式 (POS form, Product-of-Sum) 由文字相或组成的蕴含项进行“与”运算构成的表达式。 例如：$F(A,B,C,D) = (\bar{A}+B)(B+\bar{C})(A+\bar{B}+C)D$ “或项”也称“和项”，“或-与”表达式也称“和的积”表达式。

(注：现实中的逻辑函数表达式可以被表示成任意的混合形式)

2. 逻辑函数表达式的规范形式 (Canonical form / 标准形式)

因为逻辑函数的基本形式不唯一，为了使逻辑功能与逻辑表达式唯一对应，引入了规范形式（引入最小项和最大项来表达）。

• 最小项 (minterm)

  • 定义：具有 $n$ 个变量的函数的“与项”包含全部 $n$ 个变量；每个变量都以原变量或反变量形式出现且仅出现一次。
  • 表示：用小写字母 $m_i$ 表示，如 3 变量中的 $m_5$ 对应 $A\bar{B}C$ （即原变量取 1，反变量取 0 时该项值为 1 的输入组合：101）。
  • 性质：
    1. 任意一个最小项，其相应变量有且仅有一种取值使这个最小项的值为 1。
    2. 相同输入值构成的两个不同最小项相“与”为 0，即 $m_i \cdot m_j = 0\ (i \neq j)$。
    3. $n$ 个变量的全部最小项“相或”为 1，即 $\sum_{i=0}^{2^n-1} m_i = 1$。
    4. $n$ 个变量构成的最小项有 $n$ 个相邻最小项（除一个变量互为相反外，其余部分均相同的两个最小项）。
  • 用途：相邻最小项可以直接合并进行化简，如 $A\bar{B}C + A\bar{B}\bar{C} = A\bar{B}$。

• 最大项 (maxterm)

  • 定义：具有 $n$ 个变量的函数的“或项”，包含全部 $n$ 个变量；每个变量都以原变量或反变量形式出现且仅出现一次。
  • 表示：用大写字母 $M_i$ 表示，如 $M_5$ 对应 $\bar{A}+B+\bar{C}$（即原变量取 0，反变量取 1 时该项值为 0 的输入组合：101）。
  • 性质：
    1. 任意一个最大项，其相应变量有且仅有一种取值使这个最大项的值为 0。
    2. 相同变量构成的两个不同最大项相“或”为 1，即 $M_i + M_j = 1$。
    3. $n$ 个变量的全部最大项相“与”为 0，即 $\prod_{i=0}^{2^n-1} M_i = 0$。
    4. $n$ 个变量构成的最大项有 $n$ 个相邻最大项。

• 最小项与最大项的关系 同一自变量问题中，下标相同的最小项和最大项的值互补，即： $\bar{m_i} = M_i \quad \mathrm{or} \quad m_i = \bar{M_i}$

• 规范形式的表达

  • “与-或”规范形式：由若干最小项相“或”构成，用累或操作符表示为 $F = \sum m(i, j, \dots)$。
  • “或-与”规范形式：由若干最大项相“与”构成，用累与操作符表示为 $F = \prod M(i, j, \dots)$。 (注：逻辑函数表达式的规范形式具有唯一性)

逻辑函数表达式的转换#

转换目的：将任意逻辑函数表达式转换成规范表达式。 转换方法：逻辑代数转化、真值表转换。

1. 求“与-或”规范式的一般步骤

• 代数转换法：
  1. 将函数表达式变换成一般“与-或”表达式。
  2. 反复使用 $X = X(Y+\bar{Y})$ 将表达式中所有非最小项的“与项”扩展成最小项。
• 真值表转换法： 列出 F 的真值表，找出所有输出为 1 的行，直接写出对应的最小项表达式。

2. 求“或-与”规范式的一般步骤

• 代数转换法：
  1. 将函数表达式转换成一般“或-与”表达式。
  2. 反复使用 $A = (A+B)(A+\bar{B})$ 把表达式中所有非最大项的“或项”扩展成最大项。
• 真值表转换法： 列出 F 的真值表，找出所有输出为 0 的行，将其对应的最大项相“与”即可。

逻辑函数化简#

化简目的：逻辑函数表达式越简单，相应逻辑电路也越简单，可降低延迟和硬件开销。 常用方法：代数化简法、卡诺图化简法。

1. 代数化简法#

(Trade-off：相比卡诺图法，在变量个数大于 4 的情况下，代数法可实现更小的运算量，求解更快，且不受变量个数限制。)

• 最简“与-或”表达式的判断条件：

  1. 表达式中的“与”蕴含项个数最少。
  2. 在满足上述条件前提下，每个“与”蕴含项中的文字个数最少。

• 代数化简常用方法：

  • 并项法 (Theorem 7)：利用 $AB + A\bar{B} = A$，合并一个“与”蕴含项后消去一个变量。
  • 吸收法 (Theorem 3)：利用 $A + AB = A$，吸收冗余的蕴含项。
  • 消去法 (Theorem 4)：利用 $A + \bar{A}B = A + B$ 消去多余变量。
  • 配项法：利用 $A \cdot 1 = A$ 及 $A + \bar{A} = 1$，为某些“与”项配上其所缺变量，再利用并项、吸收和消去等方法进行化简。

• 最简“或-与”表达式的化简： 条件同上（“或”项总数最少，项中文字最少）。除了直接运用定理配凑外，常用两次对偶法：

  1. 对函数 $F$ 求对偶，得到“与-或”表达式 $F'$。
  2. 求出 $F'$ 的最简“与-或”表达式。
  3. 对 $F'$ 再次求对偶，即可得到 $F$ 的最简“或-与”表达式。

2. 卡诺图化简法#

• 理论依据：利用 $AB + A\bar{B} = A$ 进行合并。相邻最小项在卡诺图中的位置必须相邻，才能实现无遗漏的合并（涉及卡诺图的连通度）。

• 基于卡诺图见格式如：Q1.15 (1位符号位+15位小数)、U8.8 (无符号，8位整数+8位小数)。的“与-或”表达式化简原则：

  1. 圈的边长必须是 $2$ 的正整数次幂。
  2. 在覆盖函数中所有最小项的前提下，卡诺圈的个数应尽可能少，卡诺圈要尽量大（每个最大圈对应一个主蕴含项 prime implicant）。
  3. 特别注意：所有的 1 都必须圈到；不能合并的 1 必须单独画圈。
  4. (注：虽然可以得到最简式，但形式不一定唯一。因为存在两个圈位置相切但切点没有被其他圈包围的情况，这对应的组合逻辑电路都可能会产生 glitch 干扰脉冲)

• 基于卡诺图的“或-与”表达式化简方法：

  • 方法 A (利用 0 构建)：对卡诺图中的 0 构建全覆盖最大卡诺圈，得到 $\bar{F}$ 的最简“与-或”表达式，然后利用德摩根定理，把“与”变成“或”、“或”变成“与”，得到 $F$ 的最简“或-与”式。
  • 方法 B (对偶卡诺图法)：作 $F$ 对偶式 $F'$ 的卡诺图 $\rightarrow$ 求出 $F'$ 的最简“与-或”表达式 $\rightarrow$ 对 $F'$ 的最简式取对偶，即得 $F$ 的最简“或-与”表达式。

• 卡诺图化简的不足： 变量个数受限。平面上最多容纳 4 个变量即可饱和（每个轴饱和度为 2）。大于 4 个变量时，由于无法在平面上直观展现足够的连通性（有分组边界阻隔），需要使用立体的三维卡诺图，或者借助代数化简。