mem.academic
3 min read

II. Combinational Logic Circuits

memset0
memset0
Mar 14, 2024
Word Table
  • 集成电路(integreated circuit)
  • 逻辑门(logic gate)
  • 取反(complement)

Binary Logic and Gates

Logical Operators

三种基本的逻辑运算(logical operator)：

  • 和(and) is denoted by ⋅\cdot or ∧\land；
  • 或(or) is denoted by ++ or ∨\lor；
  • 非(not) is denoted by   ‾\overline{\,\,} or ∼\sim。
认识基本的逻辑门
认识基本的逻辑门
  • 在与门和或门与线连接处画小圆圈可以表达非的意思。
  • 逻辑门在从 01 直接跃迁时需要时间，在设计时序电路时可能需要考虑。
用电路表示的逻辑运算
用电路表示的逻辑运算

Logic Gates

逻辑门(logic gate) 是在硬件层面上实现布尔代数的逻辑单元。其操作对象为高低电平。但是由于是物理层面的实现，所以会有一些逻辑运算层面不会出现的问题，比如  延时(delay)。

CMOSTTL
功耗小效率高

Universal Gates

NAND 和 NOR 门是通用门(universal gate)。

Additional Gates and Circuits

NAND Gates

PROS:

  • 是实现起来最简单最快的电路门。The NAND gate is the natural implementation for the simplest and fastest electronic circuits
  • 是通用门——可以通过与非门的组合表示任意布尔运算。Universal gate - a gate type that can implement any Boolean function.

Buffers

缓冲器(buffer)：

PROS:

  • 可以抬高电路电压。A buffer is an electronic amplifier used to improve circuit voltage levels
  • 可以加速电路操作。To increase the speed of circuit operation.

Three-State Buffers

三向缓冲器(3-state buffer)：除了输入和输出，它还有一个使能端(enable) 来控制输出。

  • Hi-Z 高阻态（可以理解为悬空）

Boolean Algebra

Basic Laws

LawFormulas
0-1 LawX+0=XX⋅1=XX+1=1X⋅0=0\begin{aligned}&X+0=X\quad X\cdot 1=X\\ &X+1=1\quad X \cdot 0 = 0\end{aligned}
Overlapping LawX+X=XX⋅X=XX+X=X\quad X \cdot X = X
Complementary LawX+X‾=1X⋅X‾=0X+\overline{X}=1\quad X\cdot \overline{X} = 0
Involution LawX‾‾=X\overline{\overline{X}}=X
Commutative LawX+Y=Y+XXY=YXX+Y=Y+X \quad XY=YX
Associative LawX+(Y+Z)=(X+Y)+ZX(YZ)=(XY)ZX+(Y+Z)=(X+Y)+Z\quad X(YZ)=(XY)Z
Distributive LawX(Y+Z)=XY+XZX+YZ=(X+Y)(X+Z)X(Y+Z)=XY+XZ\quad X+YZ=(X+Y)(X+Z)
DeMorgan’s LawX+Y‾=X‾⋅Y‾X⋅Y‾=X‾⋅Y‾\overline{X+Y}=\overline{X}\cdot\overline{Y}\quad \overline{X \cdot Y}=\overline{X}\cdot \overline{Y}
Absorptive LawA(A+B)=AA+AB=AA(A‾+B)=ABA+A‾B=A+B\begin{aligned}&A(A+B)=A\quad A+AB=A\\ &A(\overline{A}+B)=AB\quad A+\overline{A}B=A+B\end{aligned}
Including Law(A+B)(A‾+C)(B+C)=(A+B)(A‾+C)AB+A‾C+BC=AB+A‾C\begin{aligned}&(A+B)(\overline{A}+C)(B+C)=(A+B)(\overline{A}+C)\\ &AB+\overline{A}C+BC=AB+\overline{A}C\end{aligned}

也可以考虑使用亦或(xor) 进行化简，因为亦或运算有很好的结合律。

Merging Terms

Applying formula: A+A‾=1\color{blue}A+\overline{A}=1.

F=ABC+ABC‾+ABC‾+ABC‾=AB(C+C‾)+AB‾(C+C‾)=AB+AB‾=A(B+B‾)=A\begin{aligned} F & =ABC+A\overline{BC}+AB\overline{C}+A\overline{BC}\\ & =AB(C+\overline{C})+A\overline{B}(C+\overline{C}) \\ & =AB+A\overline{B}=A(B+\overline{B})=A \end{aligned}

Absorbing Terms

Applying Absorptive law: A+AB=A\color{blue}A+AB=A.

L=AB‾+AB‾C+AB‾DE=AB‾(1+C+DE)=AB‾\begin{aligned} L & =A\overline{B}+A\overline{B}C+A\overline{B}DE \\ & =A\overline{B}(1+C+DE)=A\overline{B} \end{aligned}

Matching Terms

Applying formula: A+A‾=1\color{blue}A+\overline{A}=1, AA‾=0\color{blue}A\overline{A}=0, add new terms.

L=AB+A‾C+BCD=AB+A‾C+BCD(A+A‾)=AB+A‾C+ABCD+A‾BCD=AB+A‾C\begin{aligned} L &=AB+\overline{A}C+BCD=AB+\overline{A}C+BCD(A+\overline{A}) \\ & =AB+\overline{A}C+ABCD+\overline{A}BCD=AB+\overline{A}C \end{aligned}

Eliminating Terms

Applying Absorptive law: A+A‾B=A+B\color{blue}A+\overline{A}B=A+B.

L=A‾+AB+B‾E=A‾+B+B‾E=A‾+B+E\begin{aligned} L &=\overline{A}+AB+\overline{B}E=\overline{A}+B+\overline{B}E=\overline{A}+B+E \end{aligned}

Canonical Forms

对于一个逻辑变量 XiX_i，我们称 XiX_i 为它的 true form，Xi‾\overline{X_i} 为它的 complemented form。

最小项(minterm)：Minterms are AND terms with every variable present just once in either true or complemented form.

  • 所有 nn 个变量都需要出现在最小项中，一个最小项与真值表的一行相对应。
  • 用 mim_i 表示第 ii 个最小项，如 n=3n=3 时 m0=ABC‾m_0=\overline{ABC}，m4=ABC‾m_4=A\overline{BC}。
  • 对于一组变量的取值，只有一个最小项为 11。
  • 任意两个最小项的积一定是 00：mi⋅mj=0(i≠j)m_i \cdot m_j = 0 \quad(i\neq j)。
  • 所有最小项的和为 11：∑i=02n−1mi=1\displaystyle{\sum_{i=0}^{2^n-1} m_i} = 1。
  • 对于任意一个逻辑函数 FF，mim_i 要么在 FF 的 DNF 中要么在 F‾\overline{F} 的 DNF 中。

最大项(maxterm)：Maxterms are OR terms with every variable appearing just once in true or complemented form.

  • 用 MiM_i 表示第 ii 个最小项，如 n=3n=3 时 M4=A‾+B+CM_4 = \overline{A} + B + C（注意这里对应 literal 的方式和最小项是相反的）。
  • 对于一组变量的取值，只有一个最大项为 00。
  • 任意两个最大项的和一定是 11：Mi+Mj=1(i≠j)M_i+M_j = 1 \quad (i\neq j)。
  • 所有最大项的积为 00：∏i=02n−1Mi=0\displaystyle{\prod_{i=0}^{2^n-1} M_i= 0}。
  • 对于任意一个逻辑函数 FF，MiM_i 要么在 FF 的 CNF 中要么在 F‾\overline{F} 的 CNF 中。

最小项之和(sum of minterm, SOM) 也被称为 DNF，最大项之积(product of maxterm, POM) 也被称为 CNF。所有命题函数都可以被化简成这种形式，这两种形式被称为规范形式(canonical form)。

Comment

  • 要学会 DNF/CNF 的化简，前者可以直接从真值表中扣出来，后者先取反做然后用德摩根定律得到。具体参见离散数学笔记。

  • 要注意最小项和最大项的编号顺序，他们之中对应项的单个 literal 恰好是相反的。

Normal Forms

可以通过卡诺图化简得到积之和(sum-of-product, SOP) 或和之积(product-of-sum)。

基于 SOP/POS（或者退一步的 SOM/POM）的电路被称为二级电路。二级电路与多级电路相比，好处是时延少，代价是使用的逻辑门多。

更多简化方法：

  • “AND - OR” Simplification
  • “OR - AND” Simplification

Karnaugh Maps

Simplification Using Karnaugh Maps

以利用三变量卡诺图(karnaugh map, K-map) 求 SOP 为例：将 F 所有为 1 的最小项填入表中，可以得到对应的卡诺图。如果要求 POS，则可先求 SOP，再应用一次德摩根定律转为 POS。

画完卡诺图后，我们需要分析其主蕴含项，即就是画尽可能大的框。

  • 蕴含项(implicant)：对每一个最小项取值都为 1 的乘积项。对应卡诺图中全为 1 方格且大小为 2 的幂次的方框。
  • 主蕴含项(prime implicant)：如果从蕴含项中移去任意一个变量，所得的乘积项就不是蕴含项，则称为质蕴含项。对应卡诺图中一个不能再向任何方向拓展的方框。
  • 质主蕴含项(essential prime implicant)：如一个 1 方格仅存在于某个质蕴含项内，则称这样的主蕴含项是必要(essential) 的，称为质主蕴含项或必要主蕴含项。

在使用卡诺图找到布尔函数的主蕴含项后，可以利用主蕴含项进行化简。可以先选择所有的质主蕴含项，再使用一些主蕴含项来覆盖未被覆盖的方格 1。所以优化后的最优结果可能不是唯一的。有一些细节需要注意：

  • 找主蕴含项时，不要忘了考虑跨越边界而联通的情况。如果最后选到了一个非主蕴含项，那么这一优化结果一定不是最优的。
  • 选择多个主蕴含项时，相互之间可以重叠，注意电路优化的目标减少代价。
卡诺图的简略画法

标记出 XX 的两个位置，X‾\overline{X} 的记号可忽略。

Don’t-Care Conditions

不定项(don’t-care condition) 是指电路优化过程中，没有给出定义的项，他们可能是：

  • 输入组合不会出现；
  • 输入组合的输出不被使用；

对于这种项，在卡诺图中用 X 来表示，在最小项之和中用 ∑d(…)\sum d(\ldots) 表示。我们可以随意定义它们的输出，此时就可以利用这些项来方便我们的优化——当我们画出来的极大矩阵越大，成本就越低。

例：当 BCD 码数值大于等于 5 时返回 1

可以通过进行如下方法优化：

根据结果，写出优化后的表达式为：F(W,X,Y,Z)=W+XY+XZF(W,X,Y,Z) = W+XY+XZ。

Circuit Optimization

电路优化(circuit optimization) 的目标是在找到给定成本计算方式下的最优电路。

  • Literal Cost(L)：the number of literal appearances in a Boolean expression corresponding to the logic circuit diagram
  • 门输入代价(gate input cost)(G)：the number of inputs to the gates in the implementation corresponding exactly to the given equation or equations.
  • 带非门的门输入代价(gate input cost with NOTs, GN): G with inverters counted
F=BD+AB‾C+AC‾D‾⇒L=8, G=11, GN=14F = BD + A \overline{B}C + A\overline{C}\overline{D} \quad\Rightarrow\quad \text{L} = 8,\ \text{G} = 11,\ \text{GN} = 14

一般来说，成本函数是一个关于 L, G, GN\text{L, G, GN} 的函数。

Comments

门输入代价需要学会计算，重要！

Comments