1. Due Dates

  • Checkpoint (Part 1) due 11:59pm Tuesday, February 11

  • Full Solution (Part 2) due 11:59pm Tuesday, February 18

You will work with your assigned partner on this lab: Lab 3 Partners

CS31 Partner Etiquette and Expectations.

2. Handy References

3. Lab 3 Goals

  • Build, test, and simulate digital circuits.

  • Observe how machine code instructions are executed by digital circuits.

  • Apply incremental implementation and testing to design.

4. Lab Overview

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.

5. Lab Starting Point Code

5.1. Getting Your Lab Repo

Both you and your partner should clone your Lab repo into your cs31/labs subdirectory:

  1. get your Lab ssh-URL from the CS31 git org. The repository to clone is named Lab03-user1-user2, where user1 and user2 are the user names of you and your Lab partner.

  2. cd into your cs31/labs subdirectory:

    $ cd ~/cs31/labs
$ pwd

  3. clone your repo

    $ git clone [your_Lab03_repo_url]

There are more detailed instructions about getting your lab repo from the "Getting Lab Starting Point Code" section of the Using Git for CS31 Labs page.

5.2. Starting Point Code

  • part1.circ is the file you should use for your solution to Part 1 (checkpoint):

  • alu.circ is the file you should use for your solution to Part 2 (full solution).

Logisim and git

Merge conflicts in logsim .circ files will be difficult or impossible to resolve by hand, so it is good to avoid situations that could result in merge conflicts—​work together on one of your repos, git add, commit, push and pull frequently. You can always recover a previously committed version with git, but it is better to just be a bit more careful and push often and avoid merge conflicts all together.

6. Part 1: Sign extender and adder.

Refer to some of the logisim beginners guide and other logisim references listed in Section 2. All the circuits for this part should be in a single file named part1.circ:

$ logisim part1.circ

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

You may only use Simple Gates in your solution to Part1. 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.

6.1. 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.

  1. 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.

  2. Name this circuit something like signext2to4. Be sure to label each of your input and output values.

6.2. 1-bit Full Adder

Create a 1-bit full adder as a new circuit (Project→Add Circuit). Name this circuit fulladder.

  1. Your full adder should take 3 inputs (X, Y, CarryIn) and yield two outputs (Sum, CarryOut).

  2. 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!

6.3. 4-bit Full Adder

Add a new circuit fulladder4 that takes two 4-bit input values, x and y, and one 1-bit input value, carry-in, and produces a 4-bit sum output value, and a 1-bit carry-out value.

  1. To build this circuit you should use four copies of your 1-bit adder to add each digit.

  2. 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.

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.

6.4. 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 three 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.

6.5. Circuit Layout

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

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

part1 Layout

7. Part 2 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 subtracter, 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!

8-bit adder:

  1. 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.

  2. 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.

  3. The carry-in and carry-out bits are only 1-bit each.

7.1. Requirements

  1. Your ALU will perform eight arithmetic functions on two 8-bit inputs, producing one 8-bit output, and five 1-bit outputs (condition code flags).

  2. It will have one 3-bit input, the opcode, which will select which of the eight arithmetic functions to perform.

  3. Implement selecting ALU output using a multiplexor with eight data inputs, one for each function result, and one three-bit select input. (In Logisim, be sure to change "Include Enable?" from "Yes" to "No").

    The function the ALU outputs depends on the value of the three select lines. Assuming the inputs are called X and Y, the ALU operation selected for output for each select value is:

    • 000: X or Y

    • 001: X and Y

    • 010: X + Y

    • 011: X - Y

    • 100: X <<Y Shift left, e.g. 10111000 becomes 01110000. Note that Logisim has a Shifter gate that can be customized to perform this and the next three operations. Shifts X to the left Y times. For the three shift operations, the input Y to the Shifter can only be three bits. Use a splitter to extract the last three bits of Y, then use another splitter (in reverse) to build up a 3-bit wire from the three least significant digits. If Y=01010100, you would shift 01010100 — 4 places to the left.

    • 101: X >>Y (Shift right) without sign extension (also known as logical shift), e.g. 10111001 becomes 01011100, not 11011100. Shifts X to the right Y times; the input Y is still only 3 bits.

    • 110: X >>Y (Shift right) with sign extension (also known as arithmetic shift), e.g. 10111001 becomes 11011100 and 01000001 becomes 00100000; the input Y is still only 3 bits.

    • 111: X < Y? The output should be 00000001 if X < Y, 00000000 otherwise. X and Y should be treated as 2’s complement values. Logisim has a comparator gate that can be customized to perform almost exactly what you need, but it only outputs a 1-bit 0 or 1, so you’ll need to figure out how to make that eight bits.

  4. You must implement subtraction (X - Y) as X + ~Y + 1.

    Do Not Use Logisim’s Subtractor and Negator Circuits

    Logisim contains a Subtractor and a Negator circuit, however, you are not allowed to use these in your alu. Instead use an Adder circuit to perform subtraction as X + ~Y + 1.

    It is probably easier to not use the same Adder circuit for both the addition and subtraction operations (i.e. just have two Adder circuits in your solution, one for X+Y and the other for X-Y).

    You are welcome to try using a single Adder circuit for the two operations if you’d like. There is a constant that you can use for the c_in input to the Adder circuit.

7.2. Output Flags (Condition Codes)

Your ALU should also have five 1-bit output flags. Each output flag’s value should be zero unless it is specifically set as a side-effect of the selected arithmetic operation; think of it as clearing the flag bits "between" each arithmetic operation.

Your ALU will output the following flag bits:

  • bit 0: EQ: The EQ flag is set to 1 when x and y are equal.

  • bit 1: OF: For addition and subtraction, the OF flag is set to 1 when the requested operation results in SIGNED overflow. In other words:

    • If the opcode says to add (010), this flag should only be set to 1 if the addition represents signed overflow, and

    • If the opcode says to subtract (011), this flag should only be set to 1 if the subtraction represents signed overflow.

    • For all other operations, you can set this flag to zero.

  • bit 2: CF: For addition and subtraction, the carry flag is set to 1 when the requested operation results in UNSIGNED overflow. Its behavior is similar to that of the OF flag (above), only here we’re considering UNSIGNED overflow. For all other operations, you can set this flag to zero.

  • bit 3: ZF: The zero flag is set to 1 if the result is equal to zero

  • bit 4: SF: The sign flag is set to 1 if the result is negative (when interpreted as an 8 bit 2’s complement value)

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. It is up to you as the circuit designer to only set the flags when the appropriate opcode is selected.

7.3. Setting the Overflow Flag for Subtraction

The overflow flag for subtraction is slightly more complex to reason about. Rather than using the rules we discussed in class, you should use the following rules to design the overflow flag circuitry.

Overflow Flag Rules for Subtraction

Positive operand - Negative operand = Positive Result: No Overflow
Positive operand - Negative operand = Negative Result: Overflow

Negative operand - Positive operand = Negative Result: No Overflow
Negative operand - Positive operand = Positive Result: Overflow

  • As an example consider the following cases for four bit subtraction for Rule 1:

    Positive - Negative = Positive (no overflow)
    Positive - Negative = Negative (overflow)

    E.g. No Overflow
   X: 3 = 0011 (positive) Y: -4 1100 (negative)  Operation: X-Y = 7
   Representing the operands as two's complement values:
   R: X-Y = X + (~Y) + 1
          = 0011 (positive) - 1100 (negative)
	  = 0011 + 0100
	  = 0111 = 7 (positive)
	  = no overflow

E.g. Overflow
   X: 3 = 0011 (positive) Y: -6 1010 (negative)  Operation: X-Y = 9
   Representing the operands as two's complement values:
   R: X-Y = X + (~Y) + 1
          = 0011 (positive) - 1010 (negative)
	  = 0011 + 0110
	  = 1101 = -3 (negative)
	  = overflow

  • and for Rule 2:

    Negative operand - Positive operand = Negative Result: No Overflow
    Negative operand - Positive operand = Positive Result: Overflow

    E.g. No Overflow
   X: -3 = 1101 (negative) Y: 4 0100 (positive)  Operation: X-Y = -7
   Representing the operands as two's complement values:
   R: X-Y = X + (~Y) + 1
          = 1101 (negative) - 0100 (positive)
	  = 1101 + 1100
	  = 1 1001 = -7 (negative)
	  = no overflow

E.g. Overflow
   X: -3 = 1101 (negative) Y: 6 0110 (positive)  Operation: X-Y = -9
   Representing the operands as two's complement values:
   R: X-Y = X + (~Y) + 1
          = 1101 (positive) - 0110 (negative)
	  = 1101 + 1010
	  = 1 0111 = 7 (positive)
	  = overflow

7.4. 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:

ALU Layout

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 inputs and outputs to the corresponding locations to match those above.

7.5. Grading Rubric

  • Checkpoint

    • Sign-extender functionality: 1

    • One-bit adder functionality: 1

  • ALU

    • Arithmetic results computed correctly (0.5 for each opcode): 4

    • SF, ZF, and EQ flags computed correctly (0.5 for each flag): 1.5

    • OF flag: 1

    • CF flag: 1

    • Circuit matches correct layout: 0.5

8. Tips

  • I suggest that you test your ALU circuit often as you go; add a little functionality, stop and test that functionality by trying out different input values using the poke tool, once that part works, then add a little more functionality …​

  • You may also want to add a tester circuit into which you can plop a copy of your alu, and from which you can do more extensive testing on your entire circuit. You could use counters and clocks here to cycle through a set of values if you’d like. You can also use input values stored in 3 ROMs: one for op; one for x; and one for y. Then use a counter and clock to feed addresses into the three ROMS to get the next set of x, y, and opcode input to test. If you do this make sure the tester circuitry is in a separate subcircuit from your main ALU circuit

  • If you have an 8-bit number and you want to access just the bits individually, you can use the Splitter located under Wiring. If you set "Fan Out" to 8 and "Bit Width In" to 8, you’ll be able to turn any 8-bit input into 8 1-bit outputs. You can also do the reverse by simply connecting 8 1-bit inputs to one side of the splitter and getting 1 8-bit output back out.

  • Occasionally Logisim will, for lack of a better description, "freak out" on you for no apparent reason and decide that none of your components are connected to each other, even when they clearly are. If you all of a sudden see tons of wires turn blue or red and connections stop making sense, save your work, exit Logisim, and reopen your saved file. Also, save changes frequently as you go.

  • The logic of the flags (condition codes) will require some thought. I recommend implementing one flag at a time, and working out the logic on paper with a truth table before trying to implement the circuitry. Make sure you test the behavior of the flags in a variety of different situations.

    The OF and CF flags will require the most thought and testing to get right. I suggest starting with SF, ZF, and EQ first, and testing them before trying OF and CF.

    Step through some examples of operations applied to different values, and consider what the flag values should be. For instance:

    • If the opcode is 011 (subtraction), x is 00000000 and y is 00000001 then the result should be 11111111 and the flags should be set as follows: SF: 1, ZF: 0, CF: 1, OF: 0, EQ: 0 (subtracting 1 from zero results in unsigned overflow (CF) but not signed overflow (OF)).

    • If the opcode is 010 (addition) and x and y are both 01000001 then the result should be 10000010 and the flags should be set as follows: SF: 1, ZF: 0, CF: 0, OF: 1, EQ: 1.

      There are also cases where both OF and CF should be set as well as cases where neither should be set. Test out your circuit for as many different kinds of inputs as you can think of.

9. 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.

For example, here are the commands to submit your part 1 solution (use similar commands to submit alu.circ for part2):

$ git add part1.circ
$ git commit -m "part1 completed"
$ git push

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.

If you have difficulty pushing your changes, see the "Troubleshooting" section and "can’t push" sections at the end of the Using Git for CS31 Labs page. And for more information and help with using git, see the git help page.