跳转至

2 Circuit Optimization

文本统计：约 1798 个字

2.1 Cost Criteria

Literal Cost (L)：出现变量的个数（重复的也计算在内）它的缺点是只评价了第一层的电路数量。

Literal Cost

\[ F=BD+A\overline BC + A\overline C\overline D \]

这里的 Literal cost 就是 8

Gate Input Cost (G)（门输入代价）：输入给逻辑门的总和

Example

\(F = A + BC + \overline{BC}\), 这个时候 G 为 7，而不是 8

Gate input cost with NOTs (GN)：加上了非门（重复的算一个）

Example

计算 G 和 GN 只需要一层一层数就可以了，非常简单

2.2 Boolean Function Optimization

2.2.1 K-Maps

直观的方法：对规范形式使用 Minimization Theorem(最小化定理)，更进一步引入工具：K-Map.

K-Maps 具有的特点

  • 表格每个方块代表最小项与最大项
  • 将真值表转换成二维表
  • 相邻的格子中仅有一个变量是不同的（按照格雷码排布）

也就是 K-Maps 是真值表的一种组织方式，以更加方便地完成项的合并。

使用 K-Maps 完成布尔代数式的优化，步骤可以总结为下面四步

Step 1: Identify min-terms or max-terms 判断是最小项还是最大项

Step 2: Fill the K-map with min-terms or max-terms 将这些最大项与最小项填入 K-Maps

  • For SOM, put 1's in squares respective to the min-terms 最小项填1
  • For POM, put 0's in squares respective to the max-terms 最大项填0

Step 3: Form the rectangular groups containing maximum number of terms in power of two

Step 4: Obtain the simplified expression for groups

  • For SOM, find the product terms and sum them up
  • For POM, find the sum terms and take product of them

Two Variable Maps

找相邻想项，应用 Minimization Theorem 即可。

如果出现了重复项，也就是某一项可以与好几项合并，只需要将其复制即可。

三维的 K-Maps 的排布如下图

然后合并的规则就是

  • One square represents a min-term with three variables.
  • Two adjacent squares represent a product term with two variables.
  • Four “adjacent” terms represent a product term with one variable.
  • Eight “adjacent” terms is the function of all ones (no variables) = 1.

Three Variable Maps

注意项的合并不只是图上所看到的，还可以头尾连接

再举个例子

Pitfalls of Combining Squares

  • Only \(2^n\) number of squares in each group.

  • Groups should be as large as possible.

而对于四维K-Maps，相应的排列如下所示

无关项：有些输入不可能出现，比如BCD码中只有0~9被使用，其他的就是无关项，这些项可0可1，所以就可以获得更多的优化机会。

BCD "5 or More"

这里 BCD 码中10-15都是无关项，所以可以随意赋值

独热码 (one-hot) 与一般二进制编码的比较

独热码读取最小项时可以直接读特征项，比如说F1直接读Z，F2直接读Y+X，但这样就少了最小项之间可能存在的优化机会。

编码稀疏，优化机会可能更多，减少门输入代价

K-Maps 的优势与劣势：优势在于这个方法比较简单，同时相比于其他简化方式，步骤更少，然后得到的结果必然是最简的。但是随着变量的增多，K-Maps 的过程会变得越来越复杂，难以程序化，并且 K-Maps 得到的结果不一定是唯一的。

2.2.2 Quine-McCluskey Algorithm

在计算机中使用的简化算法为 Quine-McCluskey algorithm

蕴含项（implicant)：就是SOP中的每项积以及POS中的每项和，比如说 \(F = AB+ABC+BC\)，蕴含项就是 \(AB,ABC,BC\)，在 K-Maps 中， the implicant is a group containing \(2^n\) squares.

蕴含项可分为两类：Prime Implicant and Essential Prime Implicant

A Prime Implicant is a product term obtained by combining the maximum possible number of adjacent squares in the map with \(2^n\) number of squares. 包含尽可能多的相邻项，且是 \(2^n\) 个

An Essential Prime Implicant is a prime implicant that covers one or more minterms that no combination of other prime implicants are able to include.

Example of Prime Implicants

Cyclic Boolean Function

However a cyclic Boolean function doesn’t have Essential Prime Implicant. Every minterm is covered by at least two prime implicants and every prime implicant is of same size.

Quien McCluskey 算法

（1）找到所有主蕴含项

（2）包含进所有基本主蕴含项

（3）挑选尽可能少的非基本主蕴含项去包含所有最小项

Example

2.2.3 Multiple-Level Optimization

提取公因式，不一定会减少，比如说下面这个例子

Example

2.2.4 Summary

2.3 Additional Gates and Circuits

为什么要有其他类型的门？

  • Implementation feasibility and low cost 实现更灵活并且花费更少

  • Power in implementing Boolean functions 表达布尔表达式更强大

  • Convenient conceptual representation

门的分类

  • Primitive gate - a gate that can be described using a single primitive operation type (AND or OR) plus an optional inversion(s).

  • Complex gate - a gate that requires more than one primitive operation type for its description

2.3.1 NAND Gates

(1) The NAND gate is the natural implementation for CMOS technology in terms of chip area and speed.

(2) The NAND gate is an Univerisal Gate

(3) BUT NAND usually does not have an operation symbol defined since the NAND operation is not associative

(4) NAND represents NOT AND or Applying DeMorgan's Law gives Invert-OR

NOR Gate is almost as same as NAND Gates. 略……

2.3.2 Exclusive OR/Exclusive NOR

The Exclusive OR (XOR) function is an important boolean function used extensively in logic circuits, The Exclusive NOR function is the complement of the XOR function

XOR 函数可以被直接实现或者通过别的门连接实现，XOR 与 XNOR 都是复杂门

XOR Implementation

XOR 的代数性质

\[ \begin{aligned} X \bigoplus Y = X \overline Y + \overline XY\\ \overline{X \bigoplus Y} = XY + \overline {XY} \end{aligned} \]
\[ \begin{align*} &X \oplus 0 = X \quad X \oplus 1 = \overline{X} \\ &X \oplus X = 0 \quad X \oplus \overline{X} = 1 \\ &X \oplus Y = Y \oplus X \\ &(X \oplus Y) \oplus Z = X \oplus (Y \oplus Z) = X \oplus Y \oplus Z \end{align*} \]

怎么找出数组中唯一的一个出现一次的数，其他的数均出现两次

Function Singular(int a[], int Count) 
 value = 0 
 for i = 0, Count-1 
 value = value ⊕ a[i] 
 return value

注意异或的性质：\(X \bigoplus 0 =X\) \(X \bigoplus X =0\)

XOR 与 XNOR 的扩展：若变量数大于2个，名字被替换为奇函数与偶函数（对输入的1的奇偶进行判断）【西洋棋盘形式】

The 1s of an odd function correspond to minterms having an index with an odd number of 1s.

The 1s of an even function correspond to minterms having an index with an even number of 1s.

Implementation of odd and even functions for greater than four variables as a two-level circuit is difficult, so we use “trees” made up of : 得益于异或的良好代数性质

  • 2-input XOR or XNORs

  • 3- or 4-input odd or even functions

应用：产生校验位

偶校验位，1的数量为奇数的时候校验位就为1

Even Parity bit: count of 1s in (n+1)-bit code is even

  • So use an odd function to generate the even parity bit

To check for even parity

  • Use an odd function to check the (n+1)-bit code

2.3.3 Buffer

A buffer is an electronic amplifier used to improve circuit voltage levels and increase the speed of circuit operation.

缓冲器是一种电子放大器，用于提高电路电压水平和提高电路运行速度。

The buffer is a gate with the function \(F = X\)

2.3.4 The 3-State Buffer

IN = data input, EN = Enable control input, OUT = data output

(1) If EN = 0, then OUT = Hi-Z

  • Regardless of the value on IN

  • Output disconnected from input

(2) If EN = 1, then OUT =IN

  • Output follows the input value

引入三态门的主要原因是为了解决多个信号源同时驱动同一信号线时可能产生的电气冲突问题。

Data Selection Circut

2.3.5 More Complex Gates

The remaining complex gates are SOP or POS structures with and without an output inverter.

The names are derived using:

  • A - AND
  • O - OR
  • I - Inverter
  • Numbers of inputs on first-level “gates” or directly to second-level “gates”

Example

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！