同桥大学 TONGJI UNIVERSITY Optimization problem:state reduction Continued
Optimization problem: state reduction Continued
同源大学 TONGJI UNIVERSITY One question oIf a equals b,b equals c,so a equals c.Is it correct?
One question ⚫If a equals b, b equals c, so a equals c. Is it correct?
同©大学 TONGJI UNIVERSITY Correct of Not? This is correct when the output and the next state are definite. ●Proof: a-d-d-d2… b-e-e-d2… c-∫--f3
Correct of Not? ⚫ This is correct when the output and the next state are definite. ⚫ Proof: 1 2 1 2 1 2 a d d d b e e d c f f f − − − − − − − − −
同桥大学 TONGJI UNIVERSITY Proof (continued) It is a Finite state machine,there must exist number i and j,such that d =d; e;=ej
Proof (continued) ⚫ It is a Finite state machine, there must exist number i and j, such that i j i j i j d d e e f f = = =
同濟大学 TONGJI UNIVERSITY Proof(finished) (di,e)is implied by (di,e),since di and dj, e;and e;are the same,(di,e)are equivalent. ●So are(e,f)and(d,f) (a,c)are implied by (di,f) (a,c)are equivalent
Proof (finished) ⚫(di , ei ) is implied by (dj , ej ), since di and dj , ei and ej are the same, (di , ei ) are equivalent. ⚫So are (ei , fi ) and (di , fi ) ⚫(a,c) are implied by (di , fi ) ⚫(a,c) are equivalent
同桥大学 TONGJI UNIVERSITY Consequence Triangle has three edges. Polygons are all full polygons(every corner connected with each other.)
Consequence ⚫Triangle has three edges. ⚫Polygons are all full polygons (every corner connected with each other.)
同©大学 TONGJI UNIVERSITY oWhat about indefinite output?(D terms)
⚫What about indefinite output? (D terms)
同桥大学 TONGJI UNIVERSITY Example of indefinite output 00 01 11 10 a C,- @,0 b,- b 6 a,- ⑥，1 e,- d,ex ©.0 a,- d,- d d,ex d C,- b,- @,0 c,fx d,ex c,fx f,- b,- e,1 c,fx d,ex c,fx a,- e,- b (a)Primitive flow table (b)Implication table 2002 Prentice Hall.Inc. M.Morris Mano DIGITAL DESIGN,3e. Fig.9-23 Flow and Implication Tables
Example of indefinite output
同陈大学 TONGJI UNIVERSITY d (a)Maximal compatible: (b)Maximal compatible: (a,b.)(a,c,d)(b.e,f) (a,b.e,f)(b.c.h)(c,d)(g) Fig.9-24 Merger Diagrams 2002 Prentice Hall,Inc. M.Morris Mano DIGITAL DESIGN,3e
同桥大学 TONGJI UNIVERSITY For the indefinite output and state A equals B,B equals C,A may not equal C. why?
For the indefinite output and state ⚫A equals B, B equals C, A may not equal C. why?
