type
status
slug
summary
tags
category
password
date
icon
Canonical Forms
Difficulties in Manipulating Boolean Functions
For Boolean function have function proof Problem:
- a Boolean function has multiple expressions.
For expression simplification
- Problem 1: too many identities and theorems of Boolean algebra to apply
- Problem 2: requires skills for simplification
举个例子:
Canonical Forms for Comparison of Equality
- 中每一项使用或来连接,3.中每一项使用and来进行连接
minterm
- Minterms are AND terms with every variable present in either trueor complemented form
maxterm
- 每一项使用or来连接
两个规则运用于minterm和maxterm:
- 包含所有的元素
- 各个字母元素出现的位置保持一致
采用这种表现的方式
最大项使用最小项取补号取得,maxterm是和的形式,minterm是乘积的形式
通过增添项数,使得满足minterm和maxterm的标准形态:
- 每个元素均会出现一次
- 写成maxterm和minterm的标准形式
- 最后化简成所需要的形式即可
已经知道SOM之后,如果想要得到POM
- 使用德摩根定律:
- 找到`F,然后使用德摩根定律进行求逆的操作就可以
采用的方法如下
- 两种格式的转换:
已经找到了最小项→根据最小项找出最大项:
最大项只需要对`F进行求逆的操作即可,保留剩下的那几项即可
- 举个例子:
- 像下面的算式:
- 关键是画出真值表,使用德摩根定律
Circuit Optimization
- 线路优化的目标:
- 减少线路的成本,成本最小化
- Optimization requires a cost criterion to measure the simplicity of a circuit
- 成本设计的方式:
- Literal Cost(L)
- Gate input Cost(G)
- Gate input Cost with NOTs(GN)
- 下面是以一个例子
- 卡诺图Karnaugh Maps (K-map)
- Step 1: Identify minterms or maxterms
- Step 2: Fill the K-map with minterms or maxterms
- For SOM, put 1's in squares respective to the minterms
- For POM, put 0's in squares respective to the maxterms
- 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
- 实现更大的矩形
- A Prime Implicant is a product term obtained by combining the maximum possible number of adjacent squares in the map into a rectangle with the number of squares a power of 2.
- 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.
Four Variable Maps
Example 1: Four Variable Map Simplification
𝐹(𝑊,𝑋,𝑌,𝑍)=Σ(0,2,4,5,6,7,8,10,13,15)
出现Don’t Cares:
SOM转换为POM:
主蕴含项和基本主蕴含项:
出现四个基本主蕴含项,需要包含所有基本主蕴含项
- 作者:fufu酱
- 链接:https://csfufu.life/article/649ab6fa-0743-44a6-8536-7dc65ca32a8b
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。