Chap 2¶

约 472 个字 35 张图片预计阅读时间 2 分钟

Combinational Logic Circuits

逻辑门

Duality rules¶

变 \(AND\) 为 \(OR\) , 添加括号保证内容运算顺序不变
self-dual
- H=AB+AC+BC
- dual H=(A+B)\(\cdot\)(A+C) (B+C)
complementing functions
- use DeMorgan’s Laws(break the line,change the sign)

Theorem¶

MinimizationDistributiveAbsorptionConsensus

\(XY+\overline{X}Y=Y\) \((X+Y)(\overline {X}+Y)=Y\)

\(X+YZ=(X+Y)(X+Z)\)

\(A+A \cdot B=A\) \(A+\overline{A}B=A+B\)

\(AB+\overline{A} C+BC=AB+\overline{A}C\\=（A+C)(\overline A+B)=(A+C)(\overline A +B)(B+C)\)

Examples

想absorb \(\overline Y Z, XY\), 就主动填项来让剩余的去吸收

Canonical Forms¶

Boolean Expressions for a truth table

SOM:sum of minterms

POM:product of maxterms 索引反向读

Circuit Optimization¶

Gate Input Cost:
- L(literal cost)
- G(gate input count excluding single literal)
- GN(gate input count with NOTs)

Example

非门不要重复数

K-Maps¶

Gary-code, adjacent squares combining

三维卡诺图

Pitfalls

圈 \(2^n\) 个

四维注意number位置

Traps Example

不可圈中间4个，因为另4个小圈必会包含！！！

正确的圈法就是红色，而非红+蓝

Don’t Cares¶

"don't cares"可以在以下情况下使用：
1. 输入不可能出现：例如，如果我们有一个4位的二进制输入，但我们知道只有10种输入是有效的（0000到1001），那么其他6种输入（1010到1111）就可以被视为"don't cares"。
2. 输出对系统行为无影响：例如，如果我们正在设计一个系统，该系统在某些输入条件下的输出并不会影响系统的其他部分，那么这些输出就可以被视为"don't cares"。

example

one-hot encoding

更多的输入换取更多的优化机会和更少的门cost

Systematic Simplification¶

Info

Prime Implicant 包含 \(2^n\)个implicant的最大的
Essential Prime Implicant 含有其他prime implicant没有的项

Essential Prime Implicant 是必须优化的，剩余的有很多选择性

Quine–McCluskey Algorithm¶

Info

1.Find all prime implicants. 2.Include all essential prime implicants in the solution 3.Select a minimum cost set of non-essential prime implicants to cover all minterms not yet covered: