Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers

1.6k comments

529 users

0 votes

In the current exercise sheet 3, task 2 we have a given ZDD. For this I constructed the representation set and then tried to do the Reed-Muller Form. Going through the steps I thought I was right, but after checking it I wasn't.

Here my calculation step by step. Am I missing a point somewhere?

in * TF "Emb. Sys. and Rob." by (650 points)
edited by

2 Answers

0 votes
 
Best answer

The steps taken are correct, but in the distributive law step there is a missing part:

(a&b&c) ⊕ (a&b&c) ⊕ (a&c) ⊕ (a&b&c) ⊕ (a&b) ⊕ (a&c) ⊕ a ⊕ (a&b&c) ⊕ (a&b) ⊕ (a&c) ⊕ (b&c) ⊕ a ⊕ b ⊕ c ⊕ 1.

From the last bracket ((a ⊕ 1) & (b ⊕ 1) & (c ⊕ 1)) you get (a&b&c) ⊕ (a&b) ⊕ (a&c) ⊕ (b&c) ⊕ a ⊕ b ⊕ c ⊕ 1

On the next step of deleting doubles entries, I think there is misunderstanding. If you have double entries that term will be deleted based on:

a ⊕ a = 0

0 ⊕ a = a

Based on the syntactic sugar above and if we rearrange the term a bit,  we will have:

(a&b&c) ⊕ (a&b&c) ⊕ (a&b&c) ⊕ (a&b&c) ⊕ (a&c) ⊕ (a&c) ⊕ (a&c) ⊕ (a&b) ⊕ (a&b) ⊕ (b&c) ⊕ a ⊕ a ⊕ b ⊕ c ⊕ 1

= 0 ⊕ (a&c) ⊕ 0 ⊕ (b&c) ⊕ 0 ⊕ b ⊕ c ⊕ 1 = (a&c) ⊕ (b&c) ⊕ b ⊕ c ⊕ 1.

by (1.5k points)
selected by
0 votes

This is beautifully written, and well documented! Great work!

There are two slight typos that I spot.

  1. The line where you applied the distributive law, should end in xor 1, as the (a xor 1) & (b xor 1) & (c xor 1), also yields 1 & 1 & 1.
  2. You wrote deleting double entries but you actually just reduced all multiply occurring entries to a single entry. This isn't how the semantics of xor work. xor tells us whether and odd number of operands is satisfied. For example, a xor b xor a. Here, having both variables true satisfies the formula. This isn't the case for a xor b. The reason is that deleting an odd number of occurrences changes their parity. Deleting (or adding, haha) an even number of occurrences doesn't change the semantics of the formula: a xor b xor a = b = a xor b xor a xor a xor b xor b xor a xor c xor c (it's funny cuz it's true). In your example: (a & b & c) occurs four times → delete, a&c three times → keep once, (a & b) twice → delete, a twice → delete, b&c once → keep, b once → keep, c once → keep 
by (25.6k points)

Related questions

0 votes
1 answer
+6 votes
1 answer
0 votes
1 answer
asked Aug 14, 2020 in * TF "Emb. Sys. and Rob." by narayan (200 points)
0 votes
1 answer
asked Aug 14, 2020 in * TF "Emb. Sys. and Rob." by ssripa (550 points)
Imprint | Privacy Policy
...