# TD - Combinatorial Logic

## Overview

## Setup

In order to do this exercise, you need to download the archive with the logisim circuits. Save it somewhere in your home directory. Open a terminal and change to the directory where you just saved the archive. Then type the following commands:

```
tar xzf td-logisim.tar.gz
cd td-logisim
```

If there are any error messages in the terminal, ask your teacher for help.

## The Multiplexer

**Exercise**: Build a multiplexer ciruit using basic logic gates (AND, OR, NOT,
etc).

First draft a circuit with paper and pencil. Remember the ciruit equation from the lecture:

\[S = \overline{Sel}\cdot E_0 + Sel\cdot E_1 \]

Now open a terminal and change into the root directory of the extracted archive (see the setup section above). Move into the subdirectory containing the multiplexer exercise and list the files it contains:

```
cd mux
ls
```

Here is a short explanation of the files :

**mux-impl.circ**: Contains your implementation of the multiplexer circuit. You will need to edit it using logisim.**mux-spec.circ**: Contains a correct multiplexer circuit (in other words, the*specification*for this exercise), using logisim's circuit library.**mux-tb.circ**: Contains a*test bench*, i.e. a circuit driving a multiplexer with different inputs in order to observe its behavior.**Makefile**: Contains rules that can be evoked from the command line in order to simulate your circuit and display the results.

The only file that you need to change is *mux-impl.circ*. But let's start a
simulation first. Switch back to the terminal and type

```
make
```

This command will read the first rule in the *Makefile* and try to execute it.
In this case, it will simulate the test bench with both the specification and
your implementation, generate a waveform file (a timing diagram) and start the
program *GTKWave* to show the waveform. This is what you should see:

All the subsequent exercices work in a quite similar way, so let's take a
minute to inspect the timing diagram. On the left hand side of the window, you
can explore all the signals of the two circuits, which are named *circ* (your
implementation) and *spec* (the correct circuit). In this case (and not
surprisingly) they have the same interface. If necessary, you can add signals
from the list on the left to the waveform on the right by right-clicking on
them.

On the right hand side, you see the waveform of the simulated test bench.
Time is progressing from left to right. There are two parts:
*Implementation* shows your circuit's behavior, and *Specifciation* shows the
expected behavior. Note that the *inputs* (*DIN0*, *DIN1*, and *Sel*) are
identical in both cases, this is how a testbench actually works. Here, the
testbench exhaustively simulates all (eight) possible input combinations. The
only difference between the specification and the implentation part is the
*outputs*. As you can see, there is just a red bar where the *DOUT* of your
implementation should be. This means that the value is *unknown*. The reason is
simply that the circuit does not have an implementation. Let's fix this.

Close the GTKWave window and switch back to the terminal. Type in the following command in order to open the implementation in logisim:

```
logisim mux-impl.circ &
```

Note that the little *ampersand* (&) at the end of the line will start logisim
*in the background*, such that you can still enter new commands in the
terminal. You should see something like this:

Let's have a quick look at logisim. On the left hand side, you see the current
*circuit library*. For this exercise, the only thing you need is the *Gates*
category. Above is the tool bar. Besides shortcuts for the most frequently used
logic gates, there are two important tools that you should understand:

- The
**hand**tool is used to change the values of the inputs in the circuit. - The
**pointer**tool is used to edit the circuit.

In the circuit view on the right hand side, you see the (empty) circuit. There is only the inputs (rectangular signals with connection points on the right) and the output (round signals with connection points on the left).

Let's build our first gate. Select the **pointer** in the tool bar. Choose an
*AND Gate* from the *Gates* library or click on the AND gate in the tool bar.
Then click somewhere in the circuit view to place the gate. You will see the
properties of the newly created gate on lower left of the window. Perform the
following actions:

- Change the
*Gate Size*to*Narrow* - Change the
*Number of Inputs*to 2 - Set
*Negate 2*to*Yes*, this will add a small circle to the lower input - Connect
*DIN0*to the upper gate input - Connect
*Sel*to the lower gate input

The result should look like this:

Congratulations, you just created your first gate! Now complete the exercise as follows:

- Create a second AND gate, without negation on the inputs
- Connect
*DIN1*and*Sel*to its inputs - Create an OR gate with 2 inputs
- Connect the outputs of the two AND gates to its inputs
- Connect its output to
*DOUT*

The result should look like this:

That's it.

**Note**: *Be careful not to delete input or output signals of the circuit! Unfortunately, there is a bug in logisim: Even if you undo (ctrl-Z) the deletion of an input or output, this might break the connections of the circuit within the test bench, and you will get errors or wrong results in the simulation. If this happens, ask a teacher to help you. It might be necessary to restore the original file from the archive to "fix" this problem.*

You can now do some basic simulations: Switch to the *hand* tool and
click on the inputs in order to toggle their value. You should be able to
observe the output value changing in turn. In order to check if this
implementation is correct for all possible input values, switch back to the
terminal and type

```
make
```

If everything goes fine, this will once again open the waveform viewer with the new waveform:

Note that now the waveform of *DOUT* is identical for both the specification
and the implementation.

## Building a Subtractor

In the lecture, we have seen the *full adder* circuit:

In the same way, we would like to construct a *full subtractor*, i.e. a circuit
that performs one elementary subtraction with incoming carry (also called
*borrow* for subtraction).

**Question 1**: Show that for subtraction, the carry has *negative sign*.

In the following, we will use a Boolean value to encode the value of the carry, 0 corresponding to 0 and 1 corresponding to -1.

Our circuit will have the following interface:

- Operand inputs \(A\) and \(B\)
- Incoming carry \(C_{in}\)
- Outgoing carry \(C_{out}\)
- Difference output \(D\)

**Question 2**: Establish the arithmetic equation connecting the inputs to the
outputs.

**Question 3**: Fill in the truth table relating inputs and outputs:

\(A\) | \(B\) | \(C_{in}\) | \(C_{out}\) | \(D\) |
---|---|---|---|---|

0 | 0 | 0 | ||

0 | 0 | 1 | ||

0 | 1 | 0 | ||

0 | 1 | 1 | ||

1 | 0 | 0 | ||

1 | 0 | 1 | ||

1 | 1 | 0 | ||

1 | 1 | 1 |

**Question 4**: Establish the Boolean equations for te output signals.

**Question 5**: Draw a circuit implementing the full subtractor. Compare its
structure to the full adder circuit.

In order to test your circuit, there is a testbench in the source archive. Switch to the terminal, move to the root folder of the extracted archive and execute the following commands:

```
cd sub
logisim sub-impl.circ &
```

Complete the circuit and type `make`

to simulate it.

## The Adder/Subtractor

**Exercise**: Build an arithmetic operator that allows to compute either the
sum or the difference between two numbers *A* and *B*, given as signed 8 bit
integers.

Here are some additional constraints and assumptions:

- The circuit has an additional input
*sub*to indicate wether to perform addition (*sub*= 0) or subtraction (*sub*= 1). - The output of the operator is named
*Y*and has 8 bits - We will ignore any potential overflow

**Question 1**: Using pencil and paper, draft a first solution using an adder
and subtractor (on 8 bits) and any additional circuit element you consider
useful.

This solution is correct but not optimal regarding size (the number of logic gates used). We will build a second solution using the properties of the two's complement representation.

**Question 2**: Remember the equation used to obtain the (arithmetic) negation
of a given number in two's complement.

**Question 3**: Show that we can implement the adder/subtractor using only one
8 bit adder and an additional operator that computes the bit-wise complement of
a two's complement number.

**Question 4**: Which is the logic operation that allows to select a signal or
its complement, depending on a control signal? Extrapolate your solution to 8
bits.

**Question 5**: Using the above results, propose a new optimized circuit for
the adder/subtractor.

There is a testbench in the circuit archive for this exercise. Switch to the
subfolder *addsub* and open the circuits:

```
cd addsub
logisim addsub-spec.circ addsub-impl.circ &
```

The specification corresponds to the first solution: two operators and a
multiplexer. It is up to you to create the second implementation in the file
*addsub-impl.circ*. In order to check your solution, switch to the terminal and
type

```
make
```

## Finding the Maximum

**Exercise**: Build an operator that outputs the maximum *M* of two numbers *A*
and *B*, given as unsigned integers on 8 bits.

**Question 1**: Using pencil and paper, propose a first implementation using an
arithmetic operator and any additional logic you find useful.

**Question 2**: Show that we can obtain the maximum of *A* and *B* without the
arithmetic operator by comparing the two numbers bit by bit, starting with the
most significant bit.

**Question 3**: Show that in order to realise the above algorithm, we need to
propagate two bits of information from one bit to the next (from bit *i* to
*i-1*).

We will use the following symbol for the basic cell in order to implement the above algorithm:

Here, *a* and *b* are the respective *i*-th bits of *A* and *B*, *A>Bin* and
*B>Ain* represent the information coming from the next-upper (*i+1*) bit.
*A>Bout* and *B>Aout* represent the information propagated to the next-lower
(*i-1*) bit, and *m* is the *i*-th output bit for the maximum.

**Question 4**: Explain the purpose of the signals *A>Bin* / *A>Bout* and
*B>Ain* / *B>Aout* (cf Question 3). Give the Boolean equations to compute all
of the output signals of the basic cell.

We have provided circuit files for this exercise. From the root folder of the archive, switch to the subfolder and open the circuit designs:

```
cd max
logisim max-impl.circ &
```

The file contains two circuits: the (empty) basic cell, a full 8-bit implementation using the basic cell as building block.

**Question 5**: Complete the implementation of the basic cell and test it using
the 8-bit maximum operator.

The solution can be found in the file *max-solution.circ*.