Foundation of Combinational Circuit

    电路由节点和元件组成。元件本身又是一个带有输入、输出、功能规范和时序规范的电路，如上图E1，E2，E3所示。节点的本质就是一段导线，输入节点接收外部世界的值，如上图A，B，C所示；输出节点输出值到外部世界，如上图D所示；既不是输入节点也不是输出节点的节点是内部节点，如上图n1所示。

    组合电路的输出仅仅取决于输入值，是没有记忆的电路。只有当满足以下所有条件时，才能认为一个电路是组合电路：
    1. 每一个电路元件本身都是组合电路。
    2. 每一个电路节点，或者是一个电路的输入，或者是连接到外部电路的一个输出。因此注意上图所示的电路并不是组合逻辑电路，因为内部节点n1同时连接了I1和I2的输出。
    3. 电路不包含回路，经过电路的每条路径最多只能经过每个电路节点一次。

    组合电路的功能规范常用真值表或者布尔表达式来表示。以下将分别对其进行解释，然后会具体阐述以下几个问题：
    (1) 如何通过真值表得到布尔表达式？
    (2) 如何使用布尔代数和卡诺图来化简表达式？
    (3) 如何通过逻辑门来实现这些表达式并分析这些电路的速度？

3.1 布尔表达式

3.1.1 与布尔表达式相关的术语

    (1) 项(literal)：一个变量 `A` 以及它的非(complement) `\overline{A}` 都是项。
    (2) 乘积项(product) & 蕴含项(implicant)：一项或多项的AND，如`A\overline{B}C`等。
    (3) 最小项(minterm)：包含全部输入变量的乘积项，如有输入变量`A`，`B`，`C`， `A\overline{B}\overline{C}`就是一个最小项，而`A\overline{B}`不是。
    (4) 求和项(sum)：一项或多项的OR，如`A + \overline{B}`等。
    (5) 最大项(maxterm)：包含全部输入变量的求和项，如有输入变量`A`，`B`，`C`， `A + \overline{B} + \overline{C}`就是一个最大项。

3.1.2 与或式(sum-of-product，积之和)

    布尔代数的第一种表示方式是与或式。其原理是真值表中的每一行都可以与一个为TRUE的最小项关联，把真值表中所有输出为TURE的这些最小项相加，就可以满足使系统输出为TRUE的所有输入条件（只要系统输入满足其中任何一个这样的最小项，系统输出就为TRUE。一个为TURE就行，因此是最小项相OR的逻辑），所以可以使用与或式来描述真值表，具体例子如下所示：

    分析上面真值表，将所有输出为TRUE的最小项相加，可得所对应的布尔表达式为：`Y = \overline{A}B + AB`，
有时也将与或式记为 `F(A,B) = \sum(m_1, m_3)`。

3.1.3 或与式(product-of-sums，和之积)

    布尔表达式的另一种表达式是或与式。其原理是真值表中的每一行都可以与一个为FALSE的最大项关联，把真值表中所有输出为FALSE的这些最大项相乘，就可以满足使系统输出为FALSE的所有输入条件（只要系统输入满足其中任何一个这样的最大项，系统输出就为FALSE，一个为FALSE就行，因此是最大项相AND的逻辑），所以可以使用或与式来描述真值表，具体例子如下所示：

    分析上面真值表，将所有输出为FALSE的最大项相乘，可得所对应的布尔表达式为：`Y = (A + B)(\overline{A} + B)`，
有时也将与或式记为 `F(A,B) = \prod(M_1, M_3)`。

3.2 化简布尔表达式

    基于上面的阐述，我们可以从真值表中获取布尔表达式，但是这样得到的布尔表达式并不一定是最简单的形式。我们的目标是尽可能的用更少的逻辑门完成我们所要的电路功能，因此我们必须尝试化简布尔表达式。化简的工具之一是布尔代数。布尔代数以一组事先假定正确的公理为基础，这组公理无需证明，使用这组公理可以推出布尔代数的所有定理。本文不在公理和定理处花过多的解释文笔，仅罗列出所有的公理和定理，供随时参考，读者阅读时可以在心中把公理和定理都过一遍。

3.2.1 布尔代数的公理和定理

备注：对偶的含义是：如果符号0和1互换，操作符`\cdot`(AND)和`+`(OR)互换，表达式依然正确。

    使用布尔代数化简布尔表达式的精髓：`P\overline{A}+PA=P`，其中P可以是任何最小项。举个例子
    `\overline{A}\overline{B}\overline{C}+A\overline{B}\overline{C}+A\overline{B}C`
`=\underbrace{\overline{A}\overline{B}\overline{C}+A\overline{B}\overline{C}}_{合并}+\underbrace{A\overline{B}\overline{C}+A\overline{B}C}_{合并}`
`=\overline{B}\overline{C}+A\overline{B}`

3.2.2 德摩根定律和推气泡

    德摩根定律用文字概括即是：所有项的乘积的补等于每个项各自取补后相加，对偶形式亦然。该定律是数字设计中十分有用的定律，在CMOS电路中，工程师更偏爱使用NAND和NOR Gate而不是AND和OR Gate。但是从带有很多NAND和NOR Gate的电路中读出电路的布尔表达式是十分难受的，因此可以使用德摩根定律来化简电路，将NAND和NOR化简为带逆变器输入的AND和OR，俗称推气泡(bubble)。如上图所示，一个与非门等效于一个带逆变器输入的或门，一个或非门等效于一个带逆变器输入的与门。推气泡的原则如下：
    1. 从电路的输出端开始向输入方向推，从最后一级开始，根据德摩根定律，将NAND和NOR Gate替换为带逆变器的AND和OR Gate。
    2. 替换后，若输入端存在逆变器，则把该逆变器踢到前一级的输出端去，使前一级变为NAND或者NOR Gate（如果前一级输出已经有逆变器则直接抵消），然后继续化简。

3.2.3 卡诺图 (Karnaugh Map)

    上文说到，使用布尔代数化简布尔表达式的精髓是`P\overline{A}+PA=P`，其中P可以是任何最小项。除了使用布尔代数来化简布尔表达式，为了更加直观地进行化简，由贝尔实验室的电信工程师Maurice Karnaugh在1953年发明的卡诺图实现了对布尔表达式的可视化化简，保证化简后的布尔表达式会是最简的形式。下面简要阐述卡诺图的运作原理。

    如上图所示,卡诺图方格中的1和0代表了对应输入的输出值。其实每一个方格就对应了一个为TURE的最小项，注意到每一个方格与相邻方格只有一个输入变量的值不同，也即是说在绘制卡诺图时，输入变量的排布是以格雷码的顺序排布的，这种排序方式的用意就是当相邻的方格中的数字都为1时，这些方格所代表的最小项就可以被合并，合并方格的原则如下所示：
    1. 用最少的圈来圈住全部所有的1。
    2. 每个圈中的所有方格必须都包含1。
    3. 每个圈的边长都必须是2的整数次幂。
    4. 每个圈必须尽可能的大。
    5. 圈可以跨越卡诺图的边界，如上图中的大圈。
    6. 卡诺图中同一个方格可以被多个圈包含。

3.4 总结

综上所述，布尔代数，卡诺图是两种逻辑化简方法，其目的都是为了找出开销最低的特定逻辑函数的电路实现方法。在实践中，常借助数字逻辑设计软件(e.g. Vivado, Quartus等)的逻辑综合(logic systhesizer)功能来化简电路。

4.1 将布尔表达式映射至电路：二层逻辑和多层逻辑

    这本节我们将会把上文所描述的布尔表达式映射至真正的数字电路上。在上文的描述中，我们可以注意到与或式其实就是把最小项相加起来，因此我们称与或式为两级逻辑：第一级逻辑是在与门中连接相应的输入信号，第二级逻辑是在或门中连接与门的输出信号。而在实践中，常使用多级逻辑而非两级逻辑，因为多级组合电路使用的硬件比两级组合电路更少，下面是一个N输入异或门的例子（异或门原理：奇数个输入为TRUE时输出为TRUE），可以感受一下硬件的减少。

    如上左图所示，这是一个使用两级逻辑实现的三输入异或门(`Y=\overline{A}\overline{B}C+\overline{A}B\overline{C}+A\overline{B}\overline{C}+ABC`)，一共使用了3个非门，4个三输入与门和1个四输入或门。注意到其实异或运算是符合结合律的(i.e. `A\oplusB\oplusC=(A\oplusB)\oplusC`)，因此若采用多级逻辑来实现这个三输入异或门，可以使用2个二输入异或门来实现，如右上图所示。1个二输入异或门使用了2个非门，2个二输入与门和1个二输入或门，则使用2个二输入异或门总共消耗了4个非门，4个二输入与门和2个二输入或门，资源消耗相对二层逻辑实现减少。这种减少的程度随着异或门输入变量的增多而变得更加明显，比如1个八输入异或门，若采用两级逻辑实现，则需要`(2^8)\div2=128`个八输入与门，8个非门和一个一百二十八输入的或门，采用多层逻辑设计则可以节省很多硬件资源，如右下图所示。直观的硬件资源比较可以查看下表。

4.2 符号X和符号Z

4.2.1 符号X：非法值&未初始化值

    在真实电路中，若电路节点同时被0和1驱动，则称这种情况为竞争(contention)，使用符号X来表示该电路节点有未知或非法值。
    在电路仿真器中，符号X也被用于表示一个没有初始化的值。

4.2.2 符号Z：浮空值

    符号Z表示电路节点既没有被高电平驱动也没有被低电平驱动，即浮空(floating)或高阻态(high impedance)。如左图所示是一个三态缓冲器(tristate buffer)。使能端E为1时，则其为一个普通的缓冲器，将输入值输出到输出值。当使能端E为0时，则输出被设置为浮空。三态缓冲器经常在连接多个芯片的总线上使用。

5.1 传播延迟和最小延迟

    组合逻辑电路的时序特征包括传播延迟(propagation)和最小延迟(contamination delay)。传播延迟`t_(pd)`是从输入改变直到所有输出达到它们的最终值所经历的时间，最小延迟`t_(cd)`是从输入改变到任何一个输出发生改变的最短时间。在一个电路中，传播延迟是关键路径上每一个元件的传播延迟之和，最小延迟是最短路径上每个元件的最小延迟之和。

5.2 毛刺与冒险

    在上一节中，我们知道电路从输入到输出稳定是有时间延迟的，既然有延迟，那么电路输出在稳定之前就处于一个不确定的状态。以下面的例子`Y=\overline{A}\overline{B}+BC`为例，当A=0，C=1，B从1变成0时，我们可以看见由于n2和n1节点的变化存在先后顺序——n2先于n1发生变化，因此Y输出在n2变化后n1变化前会有一个短暂的低电平毛刺(glitch)出现，或称之为冒险(hazard)。其实从卡诺图中就可以看出来电路是否存在毛刺：如上图卡诺图红圈所示，上述的输入变化实际上在卡诺图中跨越了主蕴含项的两个圈。因此在一个主蕴含项关闭，另一个主蕴含项开启之前，电路就会出现毛刺。为了消除毛刺，可以增加一个新的主蕴含项来覆盖先前两个主蕴含项的边缘，如上图蓝圈所示。毛刺通常不会导致什么问题，但是了解它们和意识到它们的存在是重要的。

1. David Money Harris, Sarah L Harris, 机械工业出版社, 数字设计和计算机体系结构