Conversion between different gates#

Functionally Complete#

Definition#

Info:

A set of logic operations is said to be functionally complete if any Boolean function can be expressed in terms of these operations.

Example 01 : $S_1=$ { AND, OR, NOT }#

The set AND, OR, and NOT is functionally complete as any Boolean function can be expressed in SOP and POS forms.

Hence, any set of logic gates which can realize AND, OR, and NOT is also functionally complete.

Example 02 : $S_2=$ { AND, NOT }#

Since we know { AND, OR, NOT } is a functionally complete set and OR can be rewrite as a combination of AND and NOT, hence the subset { AND, NOT } is also functionally complete.

$$a\lor b = a' \land b'$$

Similarly, the set { OR, NOT } is also functionally complete.

Example 03 : $S_3=$ { NAND }#

Lets look at each gate in $S_1$:

$$a' = \overline{a \land a}$$ $$a \land b = (\overline{a\land b})' = \overline{(\overline{a\land b})' \land (\overline{a\land b})'}$$ $$a \lor b = \overline{a'\land b'} = \overline{(\overline{a\land a}) \land (\overline{b\land b})}$$

Just as shown in the below circuit: We say this gate is a universal gate.

Similarly, we can also show that NOR is a univesal gate.

$$a' = \overline{a \lor a}$$ $$a \land b = (\overline{a' \lor b'}) = \overline{(\overline{a\lor a}) \lor (\overline{b\lor b})}$$ $$a \lor b = (\overline{a \lor b})' = \overline{(\overline{a\lor b}) \lor (\overline{a\lor b})}$$

Conversion - NAND#

We can convert OR and NOT gate into NAND gate, here is the illustration: We can imagine we put the bubble from right to left, and use DeMorgan’s rule, we can have the result.

Here are some examples:

Example 01#

We try to insert two bubble in both of the middle of AND and OR gate, then use DeMorgan’s law.

Example 02#

Same strategy, and we start from the gate that is near input, then converting step by step.

Example 03#

Sometimes, we can’t always use this strategy to get NAND gate, then we just need to use the coversion of those three standard gates to implement those unchangeable gates.

Example 04#

We want to implement this function with only NAND gate:

$$F=\Sigma m(1, 2, 3, 4, 5, 7)$$

First, we draw K-Map: Second, we draw the circuit with two bubbles between these two layers: Finally, just converts into NAND gate.

Conversion - NOR#

We can convert AND and NOT gate into Nor gate, here is the illustration:

We can imagine we put the bubble from right to left, and use DeMorgan’s rule, we can have the result.

Here are some examples:

Example 01#

We can easliy converts POS into NOR gates.

Example 02#

Similarly, for those gates that can not be readily converted, we can use its basic coversion to implement.

Exclusive Or Gate (XOR)#

Xor gate is defined by:

$$X\oplus Y = XY'+X'Y$$

It can be verified that it possess these two properties:

1. Associative

$$(A\oplus B)\oplus C = A\oplus (B\oplus C)$$

2. Commutative

$$A\oplus B=B\oplus A$$

By using XOR, we can create an odd function.

And here is its kmap :

Odd function#

The output of an odd function is 1 iff there is an odd numbers of input variables equal to 1. For example, the following logic function will give us a 4 input odd function.

$$F=A\oplus B\oplus C\oplus D$$

This function will be used in data transferring, which is called Parity generator, in order to check whether the data is completely transferred during this process.

tags: Logic Design EECS1010#