[情報] 關於 ite parameter 的 standardization

[ric2k1 (Ric)]

Many students are quite confused about "bar", "bubble", "negative cofactor",

etc. Let me try to explain it in the following example.

(Hope it won't confuse you more... orz)

============================================================================

Please note that we may apply the standardization rules in different orders.

For example, we have symmetrical rules:
                   _  _
ite(F, G, 1) = ite(G, F, 1)

ite(F, 1, G) = ite(G, 1, F)


We also have the complement parameter rule:
                              ____________
                   _                 _  _
ite(F, G, H) = ite(F, H, G) = ite(F, G, H)

=============================
We will now be given an ite(F, G, H), and would like to apply the
above standardization rules.

Consider the case:

F: ---o--(f), where f is a BddNode with NO bubble; that is, F has bubble
G: ------(g), where g is a BddNode without bubble; that is, G has no bubble
H: terminal 1

(in other words, ite(F, G, H) ==> ite(~f, g, 1))

and let F's level > G's level.

We try two different approaches:

*******************************************************
(1) Standardization approaches #1

>> We apply the symmetrical rule first.

Because "F's level > G's level" and "H == 1", we swap F and G and then
complement them.
                 _  _
Now we have: ite(G, F, 1) ==> ite(~g, f, 1)

>> Then we apply the complementary parameter rule.

Because the first parameter (~g) has bubble, we need to swap the second and
third parameters, and complement (~g).

At the end, we have: ite(~g, f, 1) ==> ite(g, 1, f)

*******************************************************
(2) Standardization approaches #2

>> We apply the complementary parameter rule first.

Because the first parameter in ite(F, G, H), F (= ~f), has bubble, we need
to swap G and H and complement F.
             _
We have: ite(F, H, G) ==> ite(f, 1, g)

Then we check the symmetrical rule.

We found that "the second parameter is 1", and "the level of first parameter
is greater than that of the third parameter". We then apply the second
symmetrical rule above:

ite(f, 1, g) ==> ite(g, 1, f)

********************************************************

Ends up both approaches get the same result!!

Hope this help.

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 59.121.130.124
推 phloke:如果先apply complement parameter rule那(F,!F,G)和
→ phloke:(F,0,G)的情況是不是不用考慮？
推 ric2k1:是有可能有重複的狀況  但是要小心不要 miss 掉一些情況
→ ric2k1:(不過 miss 掉一些情況只會影響 optimization.
→ ric2k1: BDD 應該還是長的一樣!!)