CS 31 Lab 3

Building an ALU Circuit

Checkpoint due 11:59pm Tuesday, September 25

Full Solution due 11:59pm Tuesday, October 2


Handy References

Lab 3 Goals:

Lab Description

For this lab, you will use logic simulation software (Logisim) to construct your very own arithmetic logic unit (ALU). This lab is longer than the previous two, so you'll be given two weeks to complete it, with a checkpoint submission at the half-way point.

To get started, clone your Lab 3 git repository from Swarthmore's GitHub. You should see two .circ files (part1.circ and alu.circ). Use these files for your solution to Part 1 (checkpoint) and Part 2 (full solution).

Part 1 (Checkpoint): Sign extender and adder.

All the circuits for this part should be in a single file named part1.circ. There are built-in Logisim circuits that do sign-extension and addition. You should not use those for this part: you are building these circuits from simple gates (AND, OR, NOT, and XOR only), inputs, outputs and splitters. You are, however, welcome to test the behavior of your circuits against the built-in versions to convince yourself of correctness.

$ logisim part1.circ

Edit the text at the top of this file to list your names.

Sign Extension

Sign extension is an common operation performed inside a CPU. It is used when combining a value(s) of types smaller than the registers holding the values. Create a circuit (Project→Add Circuit) that takes a 2-bit 2's complement number and performs sign extension so that the output is an equivalent 4-bit 2's complement number. Name this circuit something like signext2to4. Be sure to label each of your input and output values.

1-bit Full Adder

Create a 1-bit full adder as a new circuit (Project→Add Circuit). Name this circuit fulladder. Your full adder should take 3 inputs (X, Y, CarryIn) and yield two outputs (Sum, CarryOut).

Start with the truth table for X + Y + C_in = Sum, C_out and then translate this into a circuit using basic gates only. (i.e. there is an adder circuit in Logisim, you cannot use that to solve this problem, you have to build your own).

Once built, be sure to test out your circuit for all possible input values to ensure that it's implemented correctly!

4-bit Full Adder

Add a new circuit fulladder4 that takes 2 4-bit input values, x and y, and 1 1-bit input value, carry-in, and produces a 4-bit sum output value, and a 1-bit carry-out value. To build this circuit you should use four copies of your 1-bit adder to add each digit. The two 4-bit input values can be represented as a single input of size 4 and then you can use a splitter to get the value of each bit.

NOTE: The 4-bit adder you are building adds two 4-bit numbers, whether they are unsigned or 2's complement. The only difference has to do with overflow -- which you aren't dealing with in this question -- the addition is the same either way.

Putting it all together

Finally, in part1.circ's main circuit, add a copy of your 4-bit adder and a copy of your sign extender. You are going to build a test circuit with 3 input values:
  1. one 4-bit value: x
  2. one 2-bit value: y
  3. one 1-bit value: carry_in
and two output values:
  1. one 4-bit value: the result of x + y
  2. one 1-bit value: carry_out
The input value, y, will need to be sign-extended before it is added to x.

Test out your resulting circuit for different input values. Use the poke tool to change the bits of an input value.

Part 2 (Full Solution): Building an ALU.

In this part of the lab, you will implement part of an arithmetic logic unit. Your answer will be stored in alu.circ. The ALU is the part of the processor that performs mathematical and logical operations. Unlike part 1 above, your ALU should use built-in components from Logisim whenever possible (with the exception of the subtractor, see the requirements below). For example, you do not need to build an 8-bit adder -- you may simply use the 8-bit adder that is part of Logisim. You know how to build an adder already, so let's take advantage of some abstraction!

To use an 8-bit adder, open the Arithmetic folder and select Adder. The default Adder has "Data Bits" set to 8. That is an 8-bit adder. The inputs to an 8-bit adder are also 8-bits, so you need to hook up an 8-bit input pin. The output is 8-bits, so you need to hook up an 8-bit output pin. The carry-in and carry-out bits are only 1-bit each.

Requirements

Your ALU will perform 8 arithmetic functions on two 8-bit inputs, producing one 8-bit output, and five 1-bit outputs (condition code flags). It will have one 3-bit input, the opcode, which will select which of the 8 arithmetic functions to perform. Implement this in your circuit using a multiplexor with 8 inputs, one for each function result, and 3 select lines. (In Logisim, be sure to change "Include Enable?" from "Yes" to "No".) The function you perform will depend on the value of the 3 select lines. Assuming the inputs are called X and Y, you will perform:

Your ALU should also have five 1-bit output flags. An output flag's value should be zero, unless it is specifically set as a side-effect of a arithmetic operation; think of it as clearing the flag bits "between" each arithmetic operation. Your processor will output the following flag bits: In all other cases the flag bits should be zero.

Remember that the ALU does not know, nor does it care, if the operands are signed or unsigned values. It will set the OF and the CF flags to 0 or 1 on every addition or subtraction.

Circuit Layout

This will make grading much easier. Please make the grader happy, everyone benefits from a happy grader!

Your final ALU circuit should look like this when you use it as part of a larger circuit:

If your circuit layout does not match this, then right-click on your ALU circuit in circuit menu and Choose Edit Circuit Appearance. Then move your input and output to the corresponding locations to match those above.

Tips

Submitting

To submit your circuit files, simply commit your changes locally using git add and git commit. Then run git push while in your lab directory. Only one partner needs to run the final push, but make sure both partners have pulled and merged each others changes. See the section on Using a shared repo on the git help page.

Note: When I clone your repositories, I will grab both the part1.circ and alu.circ when you submit for both your checkpoint and full solution. Don't worry about that. We will only look at your part1.circ for the checkpoint, and we will only look at alu.circ for the full solution even though part1.circ will be submitted again.