Combinational Logic Design

TODO:
Full Adder
Comparator
Arithmetc Logic Unit

Logical completeness
(读 Slides)

本章重点:
(深蓝色部分为本章介绍的重点，浅蓝色部分为次重点)

# 2.1-Introduction

数字电路

one or more discrete-valued input terminals
one or more discrete-valued output terminals
a functional specification describing the relationship between inputs and outputs
a timing specification describing the delay between inputs changing and outputs responding.
(terminal 有接线端子的意思)

组合逻辑电路和时序逻辑电路 (Sequential Logic Circuits) 的区别

A combinational circuit’s outputs depend only on the current values of the inputs.
A sequential circuit’s outputs depend on both current and previous values of the inputs.
(换句话说，A combinational circuit is memoryless, but a sequential circuit has memory.)

组合逻辑电路的画图方法

为了简化输出输出，即 bus (bundle of mutiple signals)，可以使用 line+slash 表示输入输出:

Rule of Combinational Composition

Every circuit element is itself combinational.
Every node of the circuit is either designated as an input to the circuit or connects to exactly one output terminal of a circuit element. (这句话说明一个电路的输入只能来自一个电路的输出；一个电路的输出只能给一个电路作为输入？？这句话暂时存疑)
The circuit contains no cyclic paths: every path through the circuit visits each circuit node at most once.

# 2.2-Boolean Equations

本节内容:

定义一些 Boolean Equation 中的术语
学习如何根据真值表写出 Boolean Equation 的两种方法:
- Sum-of-Products Form
- Product-of-Sums Form

# 2.2.1-Terminology

complement of A:

A is true form(true form does not mean that A is TRUE)

is complementary form

literal: Literals are the true or complementary forms of the input variables.

The OR of one or more literals is called a sum

A minterm is a product involving all of the inputs to the function.

A maxterm is a sum involving all of the inputs to the function.

Precednece: NOT > AND > OR

Implicants are the product (AND) of literals.

# 2.2.2-Sum-of-Products Form

列出带 minterm 的真值表 (保证每个 minterm 都为 true)
将所有输出 Y 为 True 的 minterm 组合起来即为该真值表的 Boolean equation:

(为了统一，要按照 minterm 在真值表中的出现顺序写 Boolean equation)
or

or

Sum-of-Products Form 的缺点：产生的 Boolean equation 并不是最简的。(下一节将解释如何进行化简)

# 2.2.3-Products-of-Sums Form

列出带 maxterm 的真值表 (保证每个 maxterm 都为 false)
将所有输出 Y 为 False 的 minterm 组合起来即为该真值表的 Boolean equation:

or

or

什么时候使用 Sum-of-Products? 什么时候使用 Product-of-Sums?
Sum-of-products produces a shorter equation when the output is TRUE on only a few rows of a truth table; product-of-sums is simpler when the output is FALSE on only a few rows of a truth table.

# 2.3-Boolean Algebra

Boolean Algebra 用来简化 Boolean equation.
本节讲介绍:

theorems of Boolean algebra
- One Variable
- Several Variables

提示

Theorems of Boolean algebra obey the principle of duality (二元性). If the symbols 0 and 1 and the operators・(AND) and + (OR) are interchanged, the statement will still be correct. We use the prime symbol (′) to denote the dual of a statement.

# 2.3.2-One Variables

Null Element: 表示在这两种情况下可以用一根导线表示，不需要 AND/OR Gate。
idempotent: idem(same) potent(power)

# 2.3.3-Several Variables

其中这里要重点强调一下 De Morgan's theorem 的图像化解释:

The inversion circle is called a bubble. Intuitively, you can imagine that “pushing” a bubble through the gate causes it to come out at the other side and flips the body of the gate from AND to OR or vice versa.
(2.5 章节中将使用 bubble pushing 来帮助分析电路。)

# 2.3.5-Simplifying Equations

简化 Boolean Equation 的基本原则:
The basic principle of simplifying sum-of-products equations is to combine terms using the relationship , where P may be any implicant.

什么样的 Boolean Equation 是最简的？
An equation in sum-of-products form to be minimized if it uses the fewest possible implicants. If there are several equations with the same number of implicants, the minimal one is the one with the fewest literals.

为什么需要 Karnaugh map？
Karnaugh maps are a visual tool for minimizing functions of up to four variables. 虽然可以使用布尔代数对 Boolean equation 进行化简，但是可能会出现错误或者是难以化到最简的情况。而用 Karnaugh map 得到的 Boolean equation 就是最简的。(但是卡诺图最多只能用于四个输入变量的化简)

为什么需要化简？
Simplifying reduces the number of gates used to physically implement the function, thus making it smaller, cheaper, and possibly faster.

什么是 prime implicant?
It cannot be combined with any other implicants in the equation to form a new implicant with fewer literals.

# 2.4-From Logic to Gates

这一节主要给出了一些画 Gates 的 Discipline，有助于规范化画图，详情看书上。

什么是 programmable logic array(PLA)?

(A PLA enables the two-level SOP implementation of any N-input M-output function)

Program the connections from AND gate outputs to OR gate inputs to implement a desired logic function.

PLA 的组成部分:

An array of AND gates
The number of AND gates is the number of possible minterms.(For an n-input logic function, we need a PLA with n-input AND gates)
Followed by an array of OR gates
The number of OR gates corresponds to the number of output columns in the truth table.(常见的真值表都是单输出，所以需要一个 OR Gate)

如何使用 PLA 实现任意 N 输入的 logic function?

Connect the output of an AND gate to the input of an OR gate if the corresponding minterm is included in the SOP

参考:
H&H section:2.4
Y&S section 3.3.4
ETH sildes-2023-lecture3-combinational-logic-ii (示例看 Slides)

# 2.5-Multilevel Combinational Logic

什么是 two-level logic?

Logic in sum-of-products form is called two-level logic, because it consists of literals(true form or complementary form) connected to a level of AND gates connected to a level of OR gates.

什么是 Multilevel logic?
Multilevel logic implementations with various types of gates may be more efficient. For example, CMOS circuits favor NAND and NOR gates because these gates can be built directly from CMOS transistors without requiring extra NOT gates.
(When using NAND and NOR gates, bubble pushing is helpful to keep track of the inversions. Section 2.5.2)

# 2.5.1-Hardware Reduction

Selecting the best multilevel implementation of a specific logic function is not a simple process. Moreover, “best” has many meanings: fewest gates, fastest, shortest design time, least cost, least power consumption. It is a trade-off that you should made.

# 2.5.2-Bubble Pushing

Rules of Bubble Pushing:
见 Section 2.3

Guidelines of Bubble Pushing:

Begin at the output of the circuit and work toward the inputs.
Push any bubbles on the final output back toward the inputs so that you can read an equation in terms of the output (for example, Y) instead of the complement of the output . 因为在 hat 下面有一长串 blooean eqution 是非常难看的。
Working backward, draw each gate in a form so that bubbles cancel. If the current gate has an input bubble, draw the preceding gate with an output bubble. If the current gate does not have an input bubble, draw the preceding gate without an output bubble.

# X's and Z's, Oh My

X: Illegal value
用符号 X 来表示电路中出现的未知 / 不合法的值。

Section2.4 中我们还使用 X 来表示 "Dot's care":

When X appears in a truth table, it indicates that the value of the variable in the truth table is unimportant (can be either 0 or 1).
When X appears in a circuit, it means that the circuit node has an unknown or illegal value.

Z: floating value
The symbol Z indicates that a node is being driven neither HIGH nor LOW.
比如 tristate buffer 在没有 enable 时。

# Karnaugh Maps

(卡诺图)
卡诺图的使用方法:

使用最少的圈来圈出卡诺图中所有的 1
圈中的所有数都必须是 1
每个圈中的元素数量都必须是 (i.e., 1, 2, or 4)
(为什么不能圈三个？对化简没有作用，圈三个化简后还是有两项；两个圈就能化简为两项)
每个圈都应该尽可能的大
边沿上的圈可以收尾相连
每一个 1 都能够被圈多次

使用卡诺图化简的思想是什么？
如果不画圈，将每一项用 sum of products 的形式写出来就是 blooean equation. 相邻格子中只有一个变量的取值不同，其余变量的取值相同，所以通过画圈就可以消除相同的变量。
具体看书上 2.7.1 节。

什么是 Don't care？
如果输入不影响输出，那么我们就说这个输入为 don't care。

"Don't cares" in K-Maps:
什么时候可以使用 Don't cares 在 K-Maps 中:
Don’t cares also appear in truth table outputs where the output value is unimportant or the corresponding input combination can never happen.
使用方法:
In a K-map, X’s allow for even more logic minimization. They can be circled if they help cover the 1’s with fewer or larger circles, but they do not have to be circled if they are not helpful.

# Combinational Building Blocks

# 2.8.1 Multiplexers

什么是 Multiplexer (MUX, 多路选择器)? 为什么要叫 MUX?
因为可以根据 S 端信号来控制输出来自于哪个输入端。
比如一个 2:1 的 Multiplexers:

2:1 的 Multiplexer: 可以根据真值表使用 Sum-of-Products (SOP) 的方法进行构建；或者使用 tristate buffers (三态缓存) 进行构建。

对于一个 wider Multiplexer 可以有多种构建方法:
(a) 使用 two-level logic (即使用 SOP 的方法进行构建)
(b) 使用 trisates buffer
(c) hierachical (比如 4:1 的 MUX 可以使用 2:1 的 MUX 进行构建，其中用来控制使用, 还是, )

MUX 的应用场景:
使用 MUX 作为 Lookup tables 构建任意 logic function (类似于 programmable logic array):

Lookup tables 和 Truth Table 的关系:
A Look-Up Table is a discrete block of functionality that can be programmed by the Digital Designer. LUTs use the same truth table concept to relate outputs to inputs. (LUT 是 FPGA 中的常见 Block)

使用方法:
The inputs (下面例子中的 A 和 B) serve as select lines.
The MUX data inputs are connected to 0 or 1 according to the corresponding row of the truth table.
举例:

4:1 multiplexer implementation AND gates

通常来说，要构成 N 个输入的 logic function (输入类型有种) 需要有个输入的 MUX.

但是可以通过修改数据输入，使得 N 个输入的 logic function (输入类型有种) 只需要有个输入的 MUX.
修改策略：Provide one of the literals to the multiplexer data inputs.
修改方法:
Combine pairs of rows to eliminate the rightmost input variable (即保证其他的变量的值相同) by expressing the output in terms of this variable
举例:

# 2.8.2 Decoder

A decoder has N inputs and outputs.

Decoder 可以由 two level logic 构成，比如 2:4 的 Decoder 如下图所示::

使用 Decoder + OR 实现电路逻辑:

提示

因为每个输出输入的函数都是一个 minterm，比如在 2:4 的 decoder 中，输出和输出的关系可以使用 SOP 求出:
= , = , = , =

从而就可以使用 Decoder + OR 实现任意的电路逻辑:
举例：使用 decoder 实现 XNOR

一个的 decoder 和 M 位输入的 OR 门，可以组成一个拥有 M 个 minterm 项的组合逻辑表达式。比如上面的例子中 M 为 2，那么说明可以有两个 minterm 项作为输入。

这个概念将在 Section 5.5.6 ROM 中用到。

# 2.8.3 Full Adder

(课本上 5.2.1 节的内容)

# Half Adder

首先从 1bit 的半加器开始介绍。半加器有两个输入和两个输出:

代表两个 1bit 的输入
表示输出
表示进位 (Carry out)

真值表和电路符号以及使用 SOP 得到的布尔等式如下图所示:

# Full Adder

全加器和半加器相比，多了一个输入端口，真值表和电路符号以及使用 SOP 得到的布尔等式如下图所示:

# Carry Propagate Adder

Carry Propagate Adder (CPA，进位传递加法器): 每个 bit 位的进位输出都会传递到下一位的作为输入。电路图如下图所示:

常见的 CPA 有三种类型:

Ripple-Carry Adder
Carry-Lookahead Adder
Prefix Adder (暂时不介绍)

# Ripple-Carry Adder

(脉冲进位加法器)

一种最简单的构建 CPA 的方法是将 N 个全加器串联起来即可形成一个 CPA，即脉冲进位加法器。

优点：使用了模块化的思想，成功管理了加法器的复杂度。

缺点：当 N 很大时，加法器很慢。因为每一个全加器都要等待上一个全加器运行得到进位后，它才能运行。

假设 Ripple-carry 加法器每个全加器的延迟为，那么该加法器的延迟为:

verilog 描述见 USTC OJ25 (opens new window)

# Carry-Lookahead adder

(超前进位加法器)

Ripple-Carry adder 很慢的原因是因为下一个全加器都要等待上一个全加器运行完成得到进位后，下一个才能运行。但是真的需要等待上一个全加器运行结束后才能运行下一个全加器吗？

答案当然是否定的，如果能够知道上一个全加器的进位输出，就不需要等待上一个全加器运行结束就可以运行下一个全加器了。

那问题是如何在不运行上一个全加器的情况下，知道上一个全加器的进位呢？

对于 1bit 的全加器，不需要全加器运行，通过一些布尔运算就能知道该全加器是否有进位输出:

情况一: one bit generate carry for:
如果输入 A 和 B 都为 1 那么不需要运行该加法器，那么该加法器一定会产生 one bit generate carry。，其中表示是否存在 one bit generate carry。
情况二: one bit propagate carry:
如果输入 A 和 B 其中一个为 1 另一个为 0，并且该加法器的进位输入 Cin 为 1 (即上一个全加器的进位输出为 1)，那么该加法器会产生 one bit propagate carry。，其中表示是否存在 one bit propagate carry.

只有上面两种情况会产生进位，所以可以也出布尔等式:
(可以看出来这是一个递推公式)

同理可以将 generate 和 propate 的定义扩展到多个 bit 加法运算的 module (模块) 上，并且不需要运行全加器就能得到进位输出:

a module generate carry: 一个模块在不需要知道进位输入的情况下就能产生进位输出 1 ，定义符号为，其中 i 表示最高位，j 表示最低位
产生 a module genearte carry 的两种情况:
- 当两个输入的最高位都为 1 时 (即 one bit generate carry)
- 当两个输入的最高位一个为 1 一个为 0，且前面的全加器组成的模块产生了 module generate carry (用到了递归的思想)
为什么这里第二条中前面的全加器模块只能是module generate carry，不可以是module prapagate carry?
- 首先先解释一下 module propagate carry: 一个模块有进位输入时，一定能产生进位输出；如果该模块没有进位输入，就没有进位输出。这种情况只有每列全加器都产生进位输出的情况下才能产生。
- 回答提出的问题：因为我们 module generate carry 的定义中就有在不知道进位输入的情况下就能产生进位输出 1 ，而 module propagate carry 必须要有进位输入才能产生进位输出，如果我们要产生出一个 module generate carry 在前面的全加器模块中也不能有 module propagte carry。

所以有:

比如一个 4bit 的加法模块可以通过上式得到:

表示 4bit 加法模块在没有进位输入的情况下产生的进位输出
表示 3bit 加法模块在没有进位输入的情况下产生的进位输出
表示 2bit 加法模块在没有进位输入的情况下产生的进位输出
表示第 3 位全加器的 one bit genearte carry
表示第 2 位全加器的 one bit genearte carry
表示第 1 位全加器的 one bit genearte carry
表示第 0 位全加器的 one bit genearte carry
表示第 3 位全加器的 one bit prapagate carry
表示第 2 位全加器的 one bit prapagate carry
表示第 1 位全加器的 one bit prapagate carry
a module propagate carry: 一个模块有进位输入时，产生进位输出；进位输入时，没有进位输出。这种情况只有所有的全加器都产生进位输出的情况下才能产生。
如果知道了进位输入，那么
- 表示第 0 位的 prapagate carry
- 表示 2bit 模块的 prapagate carry
- 表示 4bit 模块的 prapagate carry
- 表示 4bit 模块的 prapagate carry

综上，如果有一个 Ripple-Carry Adder，通过组合 Module propagate carrry 和 Module generate carry 就能预测一个模块 (RCA 的 i:j 位组成的模块) 是否会产生进位输出 C_i:

G_{i:j}: 第 i~j 位的 generate carry
P_{i:j}: 第 i~j 位的 propagate carry
C_i: 第 i 位的进位输出 (i:j 位 Ripple-Carry Adder 组成的模块的进位输出)
C_j: 第 j 位的进位输入 (i:j 位 Ripple-Carry Adder 组成的模块的进位输入)

如果每 4 位的全加器组成一个 ripple-carry adder 模块，每个模块的进位输出在上面的布尔等式中已经计算出来，8 个模块就可以构成一个 32-bit 的加法器，得到的电路图和获取第一个模块进位输出的电路图如下图所示:

# 进位选择加法器

进位选择加法器将电路分为两段，每段实现 16bit 的加法，为了使高 16 位与低 16 位同时进行运算，这里我们采用两个 add16 对高位进行计算，区别在于进位位分别为 0 和 1，最终通过低 16 位加法器的输出进位作为选择控制信号，选择高 16 位的运算结果。这样，32bit 加法器的延时就变为：16t+tmux2 ≈16t, 延时降低了接近一倍，这是一种以空间（增加电路）换时间（提高速度）的做法。

verilog 描述见 USTC OJ26 (opens new window)

# 2.8.4 Prority circuit

(4bit 优先级电路，来自于课本上的 2.4 节)

当为 1 时，无论其他输入为什么，输出都为，我们就称此时为 don't care

# 2.9 Timing

# 2.9.1 Delay

一个 Gate 的 Propagaton delay (最大延迟) 和 Contamination Delay (最小延迟):
Propagaton delay: The propagation delay is the maximum time from when an input changes until the output or outputs reach their final value.

Contamination Delay: The contamination delay is the minimum time from when an input changes until any output starts to change its value.
(designers 通常都使用 Propagaton delay 来代表 delay，笔记中也是一样，如果不特别说明都指的是 Propagaton delay)

一个电路的 Propagaton delay 和 Contamination Delay:
critical path is the longest, and the slowest path.
short path is the shortest fastest path.

The propagation delay of a combinational circuit is the sum of the propagation delays through each element on the critical path.

The contamination delay is the sum of the contamination delays through each element on the short path.

# 2.9.2 Glitches

在数字电路中，Glitches 是指短暂的、不期望的电压或电流突变。这种突变通常由于信号传输延迟或信号反射等原因引起，导致信号的瞬时变化。这种瞬时变化可能会导致电路输出的错误结果，因为它们可能被错误地识别为有效的逻辑状态。(如何避免具体看书上)

上次更新: 12/27/2023, 8:55:47 AM

← From Zero To One Sequential Logic Design→