Hey Everyone,

Post your solutions to the May 10, In-Class Exercise to this thread.

Best,

Chris

Without MOD3 gates, we can calculate parity by tabulating all possible 2^n outputs and representing it as a CNF formula. As we allow unbounded fan-in, this circuit will be of depth 2. The first layer of fan-in AND will be of up to size 1.5n*2^n - every output is negated in half the inputs. Negation requires an additional circuit, leading to an average size of 1.5n for each AND. There are 2^n AND circuits OR'd together.

I don't use MOD3 gates so far.

• We can determine if there are an even or an odd number of inputs by hard- wiring a CNF or DNF formula. • For a K inputs, we can use a MOD-3 gate to reduce the number of gates by adding a MOD-3 gate for K inputs and a MOD-3 gate for K+1 inputs, with the +1 input being always on. Depending on our value for K, we can get our answer by applying a simple boolean function to the output of these gates.

XOR operation which uses AND, OR and NOT gates could be used here. This would require 2^n - 1 number of gates and the maximum depth would be 2^n. This circuit family does not require mod 3 gates