People like Logisim. It’s fun. Welcome… to fun.

You will make a circuit capable of adding or subtracting two 4-bit numbers. It will also be able to detect overflow for both the unsigned and signed interpretations of those two operations.

To make things interesting, you are only allowed to use a single adder component. It’s, uh, realistic!

0. Logisim

First, go download Logisim on the software page! Make sure it’s version 2241_1103. Those of you who took this class with me before, please download this new version, it has some nice quality-of-life additions and some bugfixes.

Install it just like you did with MARS, then run it just like you did before:

When you run Logisim, it looks like the image to the right.

The circuit diagram is where you do your work.

The parts library is just that - a collection of parts that you can add to the circuit diagram. (You can create your own, too!)

The properties panel is how you set the properties of parts in the circuit (changing their name, or appearance, or how many bits etc.).

And the toolbar contains the three main tools (hand, arrow, text) and shortcuts to some commonly-used parts: inputs, outputs, and the basic gates.

1. Getting started

Download this file, rename it to your username, and open it in Logisim (File > Open). You’ll see this:

Everything is probably really tiny and hard to see. You do not have to strain your eyes to use Logisim. In the bottom left corner, you’ll find the zoom control.

Zoom in by clicking the up arrow on the zoom control. The dots to the right of the arrows are a button that toggles the dot grid in the circuit diagram.

So what the heck did I give you? This is a bunch of inputs, outputs, and tunnels. The inputs and outputs will be used to hook your circuit up to an autograding circuit, so do not change any of them. (Well, you can change the inputs’ values, but don’t move them around, rename them, etc.)

Inputs and outputs

You can create inputs and outputs with these tools in the toolbar, but you won’t have to create any more for this lab:

The main toolbar tools

2. Tunnels

At the top left of the circuit, the inputs (rectangles) are connected to some tunnels (names in funny shaped boxes). Tunnels are a way of naming wires, and let you connect things over long distances without having to use really long wires.

Just like in Java, tunnels names are case-sensitive. Here, we have A and B. a and b would be different tunnels.

Right now the tunnels are gray, which means they have no “partners.” Let’s give them some partners:

  1. Select just the three tunnels and hit Ctrl+D/⌘D to Duplicate them.
    • You will now see “ghosts” of the tunnels that follow your mouse.
    • Move the “ghosts” to the right of the inputs, and click to place the duplicates there.
      • (Copying and pasting works the same way (Ctrl+C/⌘C to copy, Ctrl+V/⌘V to paste)).
    • Notice that the tunnels are no longer gray! They have partners.

  2. With the new copies still selected, hit the right arrow key on your keyboard.
    • This will make them face right.
      • (Try hitting the other arrow keys. Whee!)
    • If this doesn’t make them face right: let me know, it works for most people but occasionally it doesn’t and idk why, and maybe you can help me fix the bug
    • You should now have what’s in the picture on the right.

  3. With the arrow (edit) tool, click and drag on the little black dots on the right sides of the three new tunnels to create some wires like you see on the right.
  4. With the hand tool, poke some of the bits in the A and B inputs to change them. Then poke the wires coming out of the inputs, and the new wires that you just made.
    • Poking a wire lets you see what value is being carried by it.
    • By default, it shows the value as Binary / Signed Decimal but that can be changed with File > Preferences > Layout > First/Second radix when wire poked.

3. Probes

Poking wires to see their values is sometimes useful but often tedious. So instead, let’s use probes.

Now we’re gonna make this thing.

  1. Delete your duplicated sub tunnel and replace it with a duplicated O tunnel instead (from the outputs).
  2. In the parts library on the left, open the Wiring folder, click Probe, and click on your circuit to place it at the end of the wire as shown. Then make 2 more the same way.
    • If your probes look like this, they’re not hooked up right.
    • See the little dot on the right side of the probe? That is the pin that has to be connected for it to work.
    • Select the probe, then hit the left arrow key to make it face left, then connect it to the tunnel.
  3. Select all three probes that you just made and set their Radix property to Unsigned Decimal.
  4. Select the whole mess, duplicate it, and set the duplicated probes’ Radix to Signed Decimal.
  5. Use the text tool to label the left column “Unsigned” and the right column “Signed” to make it easier to read.

Now you can see what values are being added/subtracted, and what the result is, in both the unsigned and signed interpretations! Try changing the values of the A and B inputs and you’ll see the probes’ values change.

Probes are just a debugging tool. They do not have any effect on the circuit, and cannot be used in place of outputs.

Wire colors, blue wires, and x/???

You can already see several wire colors going on: black, two shades of green depending on what the sub input is, and blue. Also, the probes for O are displaying ???. What’s going on?

The O wire is not being given a value by any component, so it has the value of X. That’s why it’s blue, and that’s why the probe is showing ???. We’ll fix that soon.

4. The basic adder

Now to make some real circuitry. You’re going to be building the thing on the right.

  1. Place the following components into your circuit:
    • One adder from the “Arithmetic” folder
      • Set its Data Bits property to 4
    • One NOT gate
      • Set its Data Bits property to 4
    • One multiplexer from the “Plexers” folder
      • Set its Data Bits property to 4
      • Leave Select bits at 1
    • Duplicate the O tunnel again and make it face left as shown
  2. Connect things up like the image to the right by using the arrow tool to draw wires between things.
    • To make a wire junction (the thick black circle on the left), just click in the middle of a wire and drag away from it. It’ll create a new wire connected to it.
    • Watch out for “solder bridges.” This is when two or more pins of a component are joined together by “hidden” wires. You can see them as those “wire junction” circles on the pins. (This is a problem in real life, too.)

  3. Now test it!
    • Switch to the hand tool (Ctrl+1/⌘1) and poke the 0s and 1s in the inputs. Watch the inputs and output change on the probes.
    • Switch between addition and subtraction with the sub input.
      • See how it’s hooked up to the adder’s carry in, so that when sub is 1, it makes the adder add the extra 1 when subtracting?

A note on super-long wires and tunnels

New users of Logisim often make circuits like this.

Just like you can have spaghetti code, you can also have spaghetti circuits. This is extremely hard to read and understand.

To avoid spaghetti circuits, follow these two rules:

  1. When you need a value that comes from a tunnel, do not draw a long wire from an existing tunnel. Instead, duplicate (or copy and paste) the tunnel where you need it. That is the whole point of tunnels - so that you can use values wherever you need them!
  2. Keep your wires as short and straight as possible.

Logisim can also help you straighten out your wires. See the wire coming out of the adder going on a long journey to the O tunnel? To fix this, just move the O tunnel around a bit and Logisim will straighten the wire. As you move it closer to the adder, the wire gets cleaner and cleaner until it’s a nice short straight wire.

5. Detecting unsigned overflow

Unsigned overflow happens if we’re adding (sub == 0) and the carry out from the adder is 1; OR if we’re subtracting (sub == 1) and the carry out is 0. If we make a truth table:

sub c out UOV
0 0 0
0 1 1
1 0 1
1 1 0

This can be done with a single gate! (Go look at the “Gates and Wires” slides again at the truth tables for the basic kinds of gates. You can find this gate in the “Gates” folder on the left.)

Let’s see if you can do it on your own now. Your goal is the picture on the right. Duplicate tunnels as needed (UOV is connected to one of the outputs). The red circle is an LED from the “Input/Output” folder. Test that it properly detects overflow for both subtraction and addition.

Intermission: turning truth tables into Boolean functions

You do not need to turn in the circuit that you build in this section! Do it in another file! You do not need to redo the circuit you already built, either! It is just practice! It’s practice! That’s why it’s an intermission! Please read this pleaaaaase

A truth table describes a Boolean function, but doesn’t actually say how to build it. The problem is, for any truth table there is an infinite number of Boolean functions which could correspond to it. So, we need some kind of technique, or algorithm, which we can feed a truth table and it will produce a Boolean function.

One way of reading a truth table is like an “if-then” statement. Looking at the unsigned overflow table again:

sub c out UOV
0 0 0
0 1 1
1 0 1
1 1 0

For example, the second row can be read: “if sub is 0 and c out is 1, then output a 1.” A more “logical” reading is “if NOT sub AND c out, then output a 1.” Hey, that looks more like logic!

Every row in the truth table can be read this way, but for our purposes we only care about the rows where the output is a 1. This technique isn’t particularly smart, but it will work, every time. It goes like this:

  1. For each row where the output is a 1:
    • AND together all the input variables, but put NOTs on any inputs that are 0 in that row.
  2. OR together the outputs of all the ANDs.
  3. The output of the OR is the output of the truth table.
    • You can write the function like UOV = ... where the ... is the stuff you did in steps 1 and 2.

That’s it.

Now try doing that to the UOV table above on paper. You are going to get a Boolean function with:

Then, try turning it into a real logic circuit in a new file in Logisim. You shouldn’t replace the circuit you just built, you’re just doing this to practice. You can have multiple files open in Logisim, you just switch between them with the Window menu.

After building it, notice the shape of this circuit: NOTs, whose outputs go into ANDs, whose outputs go into an OR. Test it out by giving it each combination of inputs. Does it give you the right outputs?

This is also a real demonstration that there can be multiple different circuits that implement the same truth table… in fact there are an infinite number of circuits that implement it! But most of them are impractical and useless.

6. Detecting signed overflow

First, you need to get the sign bits of the operands and output. Your goal is to build the image on the right. Here’s how:

  1. Splitters can take multi-bit wires and split them into single bits.
    • Make a Wiring > Splitter and set its properties like so:
    • This will make something that looks like a little laser gun with a 3 on it.
      • The black side of the splitter accepts a 4-bit number.
      • The green side will output bit 3 (the MSB) from that 4-bit number.
  2. Now copy and paste that splitter a couple times for a total of three splitters.
  3. Make a new tunnel named MUX Out connected to the output of the MUX
    • that wire carries either B or ~B, depending on sub.
  4. To the input (black) side of the splitters, connect the A, MUX Out, and O tunnels.
    • Make copies. Don’t just make long wires from existing tunnels. That defeats the purpose of them!
  5. To the output (green) side of the splitters, make and connect some new tunnels named SA, SB, and SO for the sign of A, the sign of MUX Out, and the sign of O respectively.
SA SB SO SOV
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0

Now you have three tunnels, SA, SB, and SO which carry just the signs of the two addends and the output. You can then copy and paste those tunnels to use them as inputs to the circuit you are about to build.

Using the method from the “turning truth tables into Boolean functions” section above, turn this truth table on the right into a real circuit! The inputs are the tunnels you just made, and the output will be the SOV tunnel that is connected to the SOV LED.

Note: when you use that technique on this table, you may end up with situations where you have to AND three values together. You can either chain two 2-input AND gates, or you can set the “Number of Inputs” property on an AND gate to 3. The two possibilities are shown below.

Be sure to test all 8 possible combinations of signs (two inputs and one output) for addition! Then do it again for subtraction! For 4 bit signed numbers, the range is [-8, +7] and computing any number outside that range should turn on the SOV LED. For example below, I am computing -8 - 1, which would be -9, but we can’t represent that, so we get a signed overflow.

Submitting

There will be a proper autograder on Gradescope for this lab, one which tells you if your circuit behaves how it should.