Computer Architectures - Digital Circuits - Logic expressions

Examples:

## Correspondence between expressions and combinatorial circuits

Each expression has a trivial corresponding combinatorial circuit. For instance, the expressions in the example above, correspond to the following circuits:

## Power of logic expressions

A valid question is: can logic expressions describe all possible combinatorial circuits?. The answer is yes and here is why:

Take the following truth table for example:

```  x y z | f
---------
0 0 0 | 0
0 0 1 | 0
0 1 0 | 1
0 1 1 | 0
1 0 0 | 1
1 0 1 | 0
1 1 0 | 0
1 1 1 | 1
```

The corresponding expression is:

Since you can describe any combinatorial circuit with a truth table, and you can describe any truth table with an expression, you can describe any combinatorial circuit with an expression.

## Simplicity of logic expressions

There are many logic expressions (and therefore many circuits) that correspond to a certain truth table, and therefore to a certain function computed. For instance, the following two expressions compute the same function:

The left one requires two gates, one and-gate and one or-gate. The second expression requires two and-gates and one or-gate. It seems obvious that the first one is preferable to the second one. However, this is not always the case. It is not always true that the number of gates is the only way, nor even the best way, to determine simplicity.

We have, for instance, assumed that gates are ideal. In reality, the signal takes some time to propagate through a gate. We call this time the gate delay. We might be interested in circuits that minimize the total gate delay, in other words, circuits that make the signal traverse the fewest possible gates from input to output. Such circuits are not necessarily the same ones that require the smallest number of gates.