3.17 delta : Exclusive-OR operation

Format

$obj$.delta($zdd1$) $\rightarrow $ $zdd2$

Description

Find out the exclusive-OR (XOR) operation on $\alpha \oplus \beta $ on the itemset $\beta $ from the ZDD object $obj$ which contains $\alpha $ and $zdd1$, and return the result of ZDD object as $zdd2$.

For example, XOR operations on itemset abc and bcd are as follows.

abc.delta(bcd) = abc$\oplus $bcd = ad

Find out the XOR operation between multiple itemsets.

(abc + a).delta(bcd + b) = abc$\oplus $bcd + abc$\oplus $b + a$\oplus $bcd + a$\oplus $b

= ad + ac + abcd + ab

The weight is computed by expanding the same itemset to multiple instances.

(2abc).delta(bcd) = (abc+abc).delta(bcd) = ad + ad = 2ad

In addition, when $\alpha \oplus \beta $ is changed to $\alpha \cap \beta $ (intersection operation), it becomes delta function.

Example

Example 1: Basic Example

In the following, using items a,b,c, find out the exclusive OR on itemsets 2ab + a + 3b, abc + 2ab + bc + 1, ab+a.

> require 'zdd'
# First, define the itemsets
> a=ZDD::itemset("a")
> b=ZDD::itemset("b")
> c=ZDD::itemset("c")
> f=2*a*b+a+3*b
> f.show
 2 a b + a + 3 b

(2ab + a + 3b)$\oplus $a = 3ab + 2b + 1

> f.delta(a).show
 3 a b + 2 b + 1

(2ab + a + 3b)$\oplus $b = ab + 2a + 3

> f.delta(b).show
 a b + 2 a + 3

(2ab + a + 3b)$\oplus $ab = 3a + b + 2

> f.delta(a*b).show
 3 a + b + 2

(2ab + a + 3b)$\oplus $1 = 2ab+a+3b Since constant 1 is an empty itemset, it is remained in the original set for solving XOR operation.

> f.delta(1).show
 2 a b + a + 3 b

The operation result of the each term in (abc + 2ab + bc + 1)$\oplus $(2ab + a) are as follows:

The result is summarized as a b c + 2 a b + 2 a c + a + b c + 2 b + 2 c + 4.

> g=((a*b*c)+2*(a*b)+(b*c)+1)
> h=2*a*b + a
> g.show
 a b c + 2 a b + b c + 1
> h.show
 2 a b + a
> g.delta(h).show
 a b c + 2 a b + 2 a c + a + b c + 2 b + 2 c + 4

See Also