您所查看的帖子来源于考研论坛(bbs.kaoyan.com)
数字电路状 态 化 简
H1Y_ o!|Ctho'V
5u$|-v1Zc
什么叫状态化简？ 所谓状态化简，就是采用某种化简技术从原始状态表中消去多余状态，得到一个既能正确地描述给定的逻辑功能，又能使所包含的状态数目达到最少的状态表，通常称这种状态表为最小化状态表。
!x^fT%pE
A4p i ` u:`d"cxW
目的：简化电路结构。
F!mE n-Wd r
在设计具体电路时，状态数目的多少直接决定电路中所需触发器数目的多少。设状态数目为n,所需触发器数目为m,则应满足如下关系：
-TB.a:q.[,f
+@x X*e4M'bek
uJ [$m q#s+R t
2m ≥ n ＞ 2m-1
T%lU*g C"gEW&b
/]6X V
|;~ ~6g:cb1l
为了降低电路的复杂性和电路成本，应尽可能状态表中包含的状态数达到最少。
a#P)e(?TA[fW
方法：状态化简的方法很多，如观擦法、输出分类法、隐含表法等。
w B$l ^mw.E;Md#} x
下面讨论最常用的一种方法----隐含表法。在利用隐含表进行化简时，对于完全给定原始状态表和不完全给定原始状态表引用了不同的概念，并且处理过程有所不同。
CH1N4A4eU1w%F
e2b$gZ!C!j-|
一、完全确定状态表的化简
"EN F t2o}S}1@
If Y$h n+T
1．几个概念
q2Qw6N;k$Ks%D'a
(1) 等效状态
` g3Q9kM6Y
5a$k%l0X$Ue?
① 定义
@K
LsL l`g4nP5Z5u
假设状态Si和Sj是完全确定状态表中的两个状态，如果对于所有可能的输入序列，分别从状态Si和状态Sj出发，所得到的输出响应序列完全相同，则状态Si和Sj是等效的，记作(Si，Sj)，或者说，状态Si和Sj是等效对。
1Qv)F$U2M
A
B'b/^)N?D
② 判断法则
I z"e$ur1`Pd L
假定状态Si和Sj是完全确定的原始状态表中的两个现态，那么，Si和Sj等效的条件可归纳为在一位输入的各种取值组合下满足如下两条。
2fYx.g#|M#k o*r;Y
第一，它们的输出相同。
Ma`0v"w0Q[^m+P
第二，它们的次态属于下列情况之一：
P7e},NA&A A:K+]
a.次态相同；
[op^6\]pU
b.次态交错或为各自的现态；
m/~a ? Vs/h X
c.次态循环或为等效对。
[1z LSx#I)SU7Gf8HR
这里，所谓的次态交错，是指在某种输入取值下，Si的次态为Sj ，而Sj的次态为Si；所谓次态为各自的现态，即Si的次态仍为Si，Sj的次态仍为Sj ；所谓次态循环是指确定两个状态是否等效的关联状态对之间，其依赖关系构成闭环。而两个次态为状态对循环体中的一个状态对。例如，S1和S2在某种输入取值下的次态是S3和S4，而S3和S4在该种输入取值下的次态又是S1和S2，则称这种情况为次态循环。而次态为等效对是指Si和Sj的次态已被确认为等效状态。例如，S1的次态是S3，S2的次态是S4，尽管S3和S4既不相同，也不交错或循环，但若以S3和S4作为现态，在一位输入的各种取值下，其输出相同且次态相同或交错或循环，即S3和S4等效，那么，S1和S2是等效的。
|:l#Pt
ZXV
③ 性质
TuL T]3IC U1UpAb!F
等效状态具有传递性。即假若S1和S2等效，S2和S3等效，那么，一定有S1和S3等效。记作
C'z#Q~:cxmd-j
c
c&X$i]
(S1，S2)，(S2，S3) → (S1，S3)
E/{2]/O8XN J(PP
D!E5UM1O
`*Y;d
（2）等效类
9Nn*Axv
v? j
等效类：是指由若干彼此等效的状态构成的集合。在一个等效类中的任意两个状态都是等效的。
:]
jZ$|
{.b)O_
根据等效状态的传递性，可以从等效对中寻找出等效类。例如，由(S1，S2)和(S2，S3)可以推出(S1，S3)，进而可知S1、S2、S3属于同一等效类，记作{ S1，S2，S3}，即
&@+G;?\t;`
e&S U;{
(S1，S2)，(S2，S3) → { S1，S2，S3}
nTU"EH ] e
在等效关系中，等效对是狭义的概念，它是针对两个状态而言的，等效类却是广义的概念，两 个状态或多个状态均可以组成一个等效类，甚至一个状态也可以称为等效类，因为任何状态和它自身必然是等效的。
Mg8f2Qr
o Df
]8~z l
（3）最大等效类
B9KR+CA;c.}
所谓最大等效类，是指不被任何别的等效类所包含的等效类。
rl-w,p$g5In
注意： 这里所指的最大，并不是指包含的状态最多，而是指它的独立性，即使是一个状态，只要它不被包含在别的等效类中，也是最大等效类。换而言之，如果一个等效类不是任何其他等效类的子集，则该等效类称为最大等效类。
Y0Xy)F}3wA+UG e'z
原始状态表的化简过程，就是寻找出表中的所有最大等效类，然后将每个最大等效类的所有状态合并为一个新的状态，从而得到最小化状态表的过程。简化后的状态数等于最大等效类的个数。
lTqdWHy?e j
nM9W'd n0S
2．状态化简
:lly4R#S t3k
$e"k7f N+`!os[
（1）用隐含表法进行状态化简的一般步骤：
2O3aN} _ ?.E5m!R CL
SU!rfD.a {+U5k
①作隐含表
C;N1r5X3b)p0E4N!q+@8\}0i
隐含表是一个直角三角形阶梯网格，横向和纵向格数相同，即等于原始状态表中的状态数减1。隐含表中的方格是用状态名称来标注的，即横向从左到右按原始状态表中的状态顺序依次标上第一个状态至倒数第二个状态的状态名称，而纵向自上到下依次标上第二个状态至最后一个状态的名称。表中每个方格代表一个状态对。
9ND(}&_D:dRP
b ?|g,WZ%S:d
② 寻找等效对
cu)V
Yy7[Mi6V EF
利用隐含表寻找状态表中的全部"等效对"一般需要进行两轮比较，首先进行顺序比较，然后进行关联比较。
5a3z\M+R
※ 顺序比较：按照隐含表中从上至下、从左至右的顺序，对照原始状态表依次对所有"状态对"进行逐一检查和比较，并将检查结果标注在隐含表中的相应方格内。
K+_5kv8v X
比较结果只有3种情况:
-QiL V,z
等效-------在相应方格内填上"∨"；
l$c1FG oFA w xm4V N
不等效-----在相应方格内填上"×"；
No)C
t.u
与其他状态对相关 ----在相应方格内填上相关的状态对。
9]x ?J/qnql
※ 关联比较：指对那些在顺序比较时尚未确定是否等效的状态对作进一步检查。
F)A NK#I
关联比较时，首先要确定隐含表中待检查的那些次态对是否等效，并由此确定原状态对是否等效。如果隐含表中某方格内有一个次态对不等效，则该方格所对应的两个状态就不等效，并在相应方格中增加标志"/"。若方格内的次态对均为等效状态对，则与该方格对应的状态为等效状态，该方格不增加任何标志。这种判别有时要反复多次，直到判别出状态对等效或不等效为止。
mdy p/Eq l)f
$rz1M/S w&?,N
③ 求出最大等效类
#p FB;@@*C+b C
在找出原始状态表中的所有等效对之后，可利用等效状态的传递性，求出各最大等效类。确定各最大等效类时应注意两点：
@Q9E F9d.[
※ 各最大等效类之间不应出现相同状态，因为若两个等效类之间有相同状态，则根据等效的传递性可令其合为一个等效类；
6i X5h
e X B
※ 原始状态表中的每一个状态都必须属于某一个最大等效类，换句话说，各最大等效类所包含的状态之和必须覆盖原始状态表中的全部状态，否则，化简后的状态表不能描述原始状态表所描述的功能。
-B0K)Py!I+\
_
B_as2M)q&~
④ 作出最小化状态表
6{+F%]\ v{8\
将每个最大等效类中的全部状态合并为一个状态，即可得到和原始状态表等价的最小化状态表。
转载请注明出自bbs.kaoyan.com,本贴地址:
http://bbs.kaoyan.com/viewthread.php?tid=1682165