This lab should be done with a partner of your choosing.

• Checkpoint: consists of submitting your solution to Part 1 by the checkpoint due date.
• Lab 3 full solution: consists of submitting your solutions to Part 1 and Part 2 prior to the due date (and yes, resubmit your Part 1 solution).

The setup procedure for this lab will work very similarly to Lab 2. First, both you and your partner should run setup31 to grab the starting point code for this assignment. Suppose users molly and tejas which to work together. Molly (mdanner1) can start by running

  [~]$ setup31 labs/03 tdanner1

Once the script finishes, Tejas (tdanner1) should run

  [~]$ setup31 labs/03 mdanner1

For the next step only one partner should copy over the starting code

  [~]$ cd ~/cs31/labs/03
  [03]$ cp -r ~adanner/public/cs31/labs/03/* ./
  [03]$ ls
  part1.circ alu.circ

Now push the changes to your partner

[03]$ git add *.circ
[03]$ git commit -m "lab 3 start"
[03]$ git push

Your partner can now pull the changes. In this case if Tejas wishes to get files Molly pushed, he would run

[~]$ cd ~/cs31/labs/03
[03]$ git pull

Using git, you should be able to submit only part1.circ for your checkpoint this week, and only alu.circ for your full solution next week. We will only look at your part1.circ for the checkpoint, and we will only look at alu.circ for the full solution, even if they are both submitted this week and next.

Lab 3 Goals:

• To build and test digital cicuits.
• To understand how machine code instrutions are executed by digital circuits.
• To apply incremental implementation and testing to design.

You do not need to submit anything for this part, but I suggest trying some things out in Logisim before jumping into the two required parts of the lab. You will use Logisim to create and test circuits. Take a look at some of the examples we did in lab for how to do different things in Logisim. Also, see the Beginners Guide and Library Documentation of the Logisim web page for more help. Remember that, to run Logisim, just type the following:

$ logisim               # start a new session
$ logisim alu.circ      # run on an existing circuit file

Here are a few other suggestions on where to begin. You don't have to do these all, but I suggest you do some of them:

1. In the main circuit that has a copy of your decoder, remove the two one-bit inputs, add a single two bit input and a splitter that splits each bit off and feeds one into input A and one into input B. Test it out with the poke tool.
2. Try adding a new circuit to the decoder file (Project->Add Circuit), that implements the version XOR we did in lab on Friday. Try changing the inputs to be 4 bits each instead of 1 bit each. In the main circuit add an instance of your 4-bit XOR circuit and test it out. (click on your XOR circuit from the menu and click on the canvas where you want ot place it)
3. Try out some other circuits and see if you can figure out what they do. The Logisim beginners guide and library reference are very helpful.

All the circuits for this part should be in a single file named part1.circ. There are 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 only), inputs, outputs and splitters.

$ logisim part1.circ

Edit the text at the top of this file to list your and your partner's 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. Your input should be labeled so that the least significant input bit is a0 and the most significant input bit is a1. Following the same pattern, label your output bits b0 through b3.

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_{\mathrm{in}} = \mathrm{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, test out your cicuit for all possible input values.

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.

You do not need to worry about overflow, but you should add a probe to the carry out bit wire to see when it is 0 or 1.

Test out your 4-bit adder for differnt input values.

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, add a circuit named tester. In to this 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 cirucit for different input values. Use the poke tool to change the bits of an input value. Do NOT hook up a clock and a counter to this circuit's input; the 3 input values x, y, and carry_in should come from the input. You can use a counter for testing, but the version you submit should not have this.

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. Your ALU should use components from Logisim whenever possible. For example, do not build a 8-bit adder -- simply use the 8-bit adder that is already part of Logisim.

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 ouputs (condition code flags). In addition 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:

• 000: X or Y
• 001: X and Y
• 010: X + Y
• 011: X - Y. Logisim contains a Subtractor circuit, however, I'd like you to not use it, and 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 curcuit.
• 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. Note: for the three shift operations, the input Y to the Shifter can only be 3 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 3 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 ouputs a 1-bit 0 or 1, so you'll need to figure out how to make that 8 bits.

Your ALU will also have 5 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 flags bits:

• bit 0: EQ: the EQ flag is set to 1 when x and y are equal
• bit 1: OF: the OF flag is set to 1 when either x + y or x - y results in SIGNED overflow.
• bit 2: CF: the carry flag is set to 1 when either x + y or x - y results in UNSIGNED overflow.
• 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 (as 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.

Circuit Layout

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

Implementation and Testing Hints

I suggest that you test your ALU curcuit 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 extesive 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.

Logisim hint: 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.

To submit your code, simply commit your changes locally using git add and git commit. Then run git push while in the labs/03 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.