# Combinational Logic

• Summary: You will learn to use Logisim, a program that simulates digital logic circuits, and practice building larger combinational logic circuits from logic gates.

• Submitting: You do not need to turn in any work for this lab. If you are unable to finish all of the exercises during class time, you should complete this work on your own.

We often think of logic circuits in two distinct ways. The first is as a mechanism for computing logical formulas, which we used in the previous class. The second approach is to think of logical circuits as components performing some useful operation. This is often how we think of utility components like decoders and multiplexors, or the adders and memory elements we will see in the coming weeks. These views are not mutually exclusive. You will practice both approaches while learning to use Logisim in today’s in-class lab.

## Preparation

Logisim is a free graphical tool for designing and simulating logic diagrams. We are using an improved version of logisim, based on Logisim Evolution from GitHub. If you would like to set up Logisim on your personal machine, I can show you how to transfer the program from MathLAN to your own machine.

To start Logisim on a MathLAN machine, run the following command in a terminal window:

\$ java -jar /home/curtsinger/shared/logisim.jar &

You will need to keep the terminal window open as long as you are using Logisim.

## Exercises

### Exercise 0: Tutorial

1. To learn the basics of logisim, complete the Beginner’s Tutorial of the Guide to Being a Logisim User, up through step 4.
2. Read about the libraries and attributes of Logisim through its explorer pane, attribute table, and tool/component attributes.
3. Read about creating circuits in Logisim (but don’t go on to “Using subcircuits” yet).

### Exercise 1: Implementing Logical Formulas

Now that you can find your way around Logisim, we’ll practice using basic logic gates by reducing boolean formulas and implementing them as Logisim circuits. You will use Logisim’s “pin” element for both inputs and outputs. Inputs have a square outline, while outputs have a circular outline. You can switch a pin from input to output using the attributes menu, or you can use the two pin element buttons in the toolbar along the top of the window.

1. Reduce the following boolean expressions to simpler sum of products forms using Karnaugh Maps:

$\begin{eqnarray}F(a, b, c) & = & (b + \overline{a} \cdot \overline{c} + b \cdot \overline{c}) (\overline{a} + \overline{c}) \\ & = & \overline{a}\cdot b + \overline{a} \cdot \overline{c} + \overline{a} \cdot b \cdot \overline{c} + b \cdot \overline{c} + \overline{a} \cdot \overline{c} + b \cdot \overline{c}\end{eqnarray}$

$\begin{eqnarray}G(a, b, c, d) & = & (b + \overline{d}) (\overline{b} + \overline{c} + d) (\overline{a} + \overline{b} + d) \\ & = & (b \cdot \overline{b} + b \cdot \overline{c} + b \cdot d + \overline{b} \cdot \overline{d} + \overline{c} \cdot \overline{d} + d \cdot \overline{d} ) \cdot (\overline{a} + \overline{b} + d)\\ & = & \overline{a} \cdot b \cdot \overline{c} + \overline{a} \cdot b \cdot d + \overline{a} \cdot \overline{b} \cdot \overline{d} + \overline{a} \cdot \overline{c} \cdot \overline{d} +b \cdot \overline{b} \cdot \overline{c} + b \cdot \overline{b} \cdot d + \overline{b} \cdot \overline{b} \cdot \overline{d} + \overline{b} \cdot \overline{c} \cdot \overline{d} +b \cdot \overline{c} \cdot d + b \cdot d \cdot d+ \overline{b} \cdot d \cdot\overline{d} + \overline{c} \cdot d \cdot \overline{d} \\ & = & \overline{a} \cdot b \cdot \overline{c} + \overline{a} \cdot b \cdot d + \overline{a} \cdot \overline{b} \cdot \overline{d} + \overline{a} \cdot \overline{c} \cdot \overline{d} + \overline{b} \cdot \overline{d} + \overline{b} \cdot \overline{c} \cdot \overline{d} +b \cdot \overline{c} \cdot d + b \cdot d \end{eqnarray}$

Can’t see any formulas? Make sure you enable all scripts on this page if you are using the NoScript browser plugin.

1. Draw a completed PLA for these formulas, as shown in the diagram below.
1. Implement the reduced formula for $$F$$ as a Logisim circuit.

### Exercise 2: Building Subcircuits

Much like procedures in code, computer architects tend to reuse common structures in their digital logic designs. Logisim supports reusable components with subcircuits. Read the Logisim Tutorial on Using Subcircuits.

Once you’ve read about creating subcircuits, move on to the two sub-parts of this exercise.

#### Build a Decoder

Recall that a decoder takes some number of bits of input, interprets these bits as a binary number, and then turns on the corresponding output pin; a decoder is effectively a binary to unary converter. The three-bit decoder you are building will have three input pins and eight output pins. When the three inputs are all zero, the zeroth output pin is on. If all three inputs are on (encoding the number seven in binary), the seventh output is on. Likewise for all the numbers in-between. You are free to establish the order of bits however you like.

Create a subcircuit named 3-bit decoder in your Logisim project. Select the subcircuit and begin building the decoder using only inputs, outputs, and simple logic gates. You should have one input and eight outputs in your decoder subcircuit:

selector (input, 3 bits)
This single input carries all three bits of the input to the decoder. You can use a splitter to break a multi-bit input into separate one-bit wires.
out0out7 (outputs, 1 bit each)
Each output should be a single bit. While we could bundle these into a single 8-bit output, decoders are often most useful with their outputs separated. This matches the behavior of Logisim’s built-in decoder component.

Hint: You can think of a three-bit decoder as a series of eight logical formulas, each mapping the three bits of input to one of the output pins. You can also approach this problem from the component viewpoint. Rather than thinking of an AND gate as the logical conjunction, you can think of it as a device that determines whether one input is mirrored to the output. For a two-input AND gate, if one input is on, the output will mirror the second input to the AND gate. If one of the AND gate inputs is turned off, the output of the AND gate will always be off. It’s okay if one of these approaches doesn’t make sense; we will practice both in the future.

#### Build a Multiplexer

Next, create a 4-input multiplexer subcircuit. Build a multiplexer in this subcircuit using only inputs, outputs, and simple logic gates.

Recall that a four-input multiplexer will have four one-bit data inputs, a two-bit selector input, and a one-bit output. If the selector encodes the number zero, the zeroth data input should be passed on to the output. If the selector encodes the number three, the third data input is passed on to the output.

### Exercise 3: Using Subcircuits

While you can certainly build a multiplexer from simple logic gates, a decoder is actually a useful building block in a multiplexer. Create an 8-input multiplexer subcircuit and use your 3-bit decoder subcircuit to build a larger multiplexer.

An 8-input multiplexer will have eight one-bit data inputs, a three-bit selector, and a one-bit output. When using a decoder to build a multiplexer, the selector bits go directly to the decoder subcircuit. Each output of the decoder is combined with one of the inputs; when both the input and its corresponding decoder output turn on, the multiplexer output should be on.

#### Debugging

Odds are you will run into issues when building your circuits in Logisim; if you don’t, count yourself lucky (so far). Before moving on, read about Debugging Subcircuits in the Logisim manual.

### Challenge: Encoder

If you have additional time you should build an encoder, another useful combinational logic building-block. An encoder is essentially an inverted decoder; an 8-input encoder has eight one-bit inputs, only one of which should be on at a time, and outputs a single 3-bit value. If input four is on, then the output should be the binary encoding of the number 4 (i.e. 100). If no inputs are on, your encoder can still produce the value 000.

Create an 8-input encoder subcircuit, select it, and build an encoder using basic logic gates, inputs, outputs, and any subcircuits you built as part of this mini-lab.

Extra Challenge: You may assume that your encoder will only be used with valid inputs (one input pin on at a time). However, a useful extension of this component is a priority encoder, which outputs the binary value of the highest active input. As an example, if both inputs four and six are on, the output should be 110 (six in binary). You should be able to build a priority encoder in a separate subcircuit using your encoder subcircuit as a component. This work is licensed under a Creative Commons Attribution NonCommercial ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/4.0/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.