CS31 Lab 3: Circuits

Part 1: Due before 11:59pm Tuesday, Sept. 26
Part 2: Due before 11:59pm Tuesday, Oct. 3

This lab should be done with a new assigned partner. You and your Lab 3 partner will work together for two weeks on both part 1 and part 2 of lab 3.

Here are the partner lists for Lab A, Lab B, and Lab C

Expectations for Working with Partners

NOTE: merge conflicts in logsim .circ files will be difficult or impossible to resolve by hand, so it is good to avoid situtations 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.

Lab 3 Goals:

Contents:

Lab 3 Starting Point Code

Both you and your partner should do:

  1. Get your Lab03 ssh-URL from the GitHub server for our class: CS31-F17
  2. On the CS system, cd into your cs31/labs subdirectory 
    cd ~/cs31/labs
  3. Clone a local copy of your shared repo in your private cs31/labs subdirectory: 
    git clone [your_Lab03_URL]
    Then cd into your Lab03-you-partner subdirectory.
If all was successful, you should see the following files when you run ls: 
README.md  alu.circ part1.circ
If this didn't work, or for more detailed instructions see the the Using git guide.

As you and your partner work on your joint solution, you will want to push and pull changes from the master into your local repos frequently.

Logisim

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 Beginner's Guide and Library Documentation of the Logisim web page (version 2.7.x) for more help. To run: 
$ logisim               # start a new session
$ logisim alu.circ      # run on an existing circuit file


Part 0. Getting Started in Logisim

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. Here are a few suggestions (you don't have to do them all, but I sugest you do some of them):

  1. Do the Beginner's Tutorial on the logisim web page (Logisim web page (version 2.7.x)).
  2. Try adding a new circuit to the file (Project->Add Circuit) that implements the 4-bit version of XOR we did on the board in class on Tuesday. 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 to place it.)
  3. Before starting Part 2, try out some of the logisim circuits in a test.circ file and see if you can figure out what they do and how to configure them. The Logisim beginners guide and library reference are very helpful.
Part 1. Warm-up Circuits

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. It's okay to use AND and OR gates with more than two inputs. 

$ logisim part1.circ
Edit the text at the top of this file to list your name and your partner's name.

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 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, carry-in) and yield two outputs (sum, carry-out).

Start with the truth table for x + y + carry-in = sum, carry-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 circuit for all possible input values.

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. To build this circuit you should use four copies of your 1-bit adder to add each digit. x and y can each be represented as a single input pin with the "Data Bits" option set to 4. You can then use a splitter to get the value of each bit. You can also use a splitter facing in the opposite direction to collect the four 1-bit output wires into the 4-bit output value, sum.

Test out your 4-bit adder for different 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. Into 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: sum, 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. It may be convenient to use a clock and counter for testing. Just make sure the version you submit does NOT have a clock or a counter. The three inputs (and two outputs) should all be represented as pins in the circuit design you submit. You can figure out whether one of your components is a pin by selecting it and looking at the attribute table that appears in the lower left portion of the logisim window.

When you're working with 1-bit wires logisim uses color to indicate whether current is flowing through the wire or not. Your tester circuit will have wires carrying more than a single bit. To examine the value flowing through a multi-bit wire you can attach a "Probe" to it. This will be a useful debugging aid here and especially in part 2.

One last thing before you submit: We will be able to grade your assignments much more efficiently if everyone submits a circuit that appears the same when used as a subcircuit in a larger circuit. Right-click on the name of your tester circuit where it appears in logisim's explorer pane. From here you can alternate between editing the circuit's appearance and editing its layout. Edit your circuit's appearance so that it is identical to ours:

Now make sure that your inputs and outputs appear in the following order: going down the left side of the circuit, x, y, and carry-in; going down the right side, sum and carry-out. You can verify this by using your tester circuit as a subcircuit in the main circuit and hovering over the connection points until the corresponding labels appear.

Part 2. Build 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 in the circuit labeled main. The ALU is the part of the processor that performs mathematical and logical operations. Unlike in part 1, now you can and should use components from Logisim to simplify your circuit whenever possible. For example, do not build a 8-bit adder--instead 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 should also be 8 bits wide, 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 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 3 "Select Bits" and 8 "Data Bits". (Also change "Include Enable?" from "Yes" to "No".) The function you perform will depend on the value of the 3-bit input or opcode as follows:

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 an arithmetic operation. Think of your ALU as clearing the flag bits "between" each operation. It should output the following flags bits:

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.

Implementation and Testing Hints

I suggest that you test your ALU curcuit as you go; add a little functionality, then stop and test that functionality by trying out different input values using the poke tool. Once you're conviced that the new functionality works, add a little more functionality and repeat the cycle.

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.

The logic of the flags 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. For instance:

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.

Circuit Layout

Right click on the name of your circuit, main, and choose "Edit Circuit Appearance". If your circuit doesn't look like the image below--a 3 by 6 rectangle with inputs and outputs in the same locations--please edit its appearance so that it does. Again, this will make our grading process much more efficient.

Verify that the inputs and outputs are in the correct places by using your ALU circuit as part of a larger circuit. (You might want to do this when you test the circuit anyway.)

The opcode input is on top, x and y are on the left side with x on top of y, the result is on the top-half of the right side, and the flags are along the bottom. Going left to right the order of the flags should be SF, ZF, CF, OF, and EQ. Remember that if you hover the mouse over a connection point the corresponding pin's label will appear.

Lab Questionnaire
With every lab assignment is a file named QUESTIONNAIRE for you to fill out and submit with your lab solution. In this file you will answer some questions about the lab assignment. You should fill this out and submit it with your Part 2 lab solution.

Submit

Before the Due Date

Only one of you or your partner needs to push your solution from one of your local repos to the GitHub remote repo. It doesn't hurt if you both push, but the last pushed version before the due date is the one we will grade, so be careful that you are pushing the version you want to submit for grading.

From one of your local repos (in your ~you/cs31/labs/Lab03-partner1-partner2 subdirectory): 

git push

For both Part 1 and Part 2 you will be pushing files in the same Lab03 repo. Make sure for Part 1 you have committed and pushed part1.circ and for Part 2 you have committed and pushed alu.circ. The QUESTIONNAIRE is due with Part 2.

Troubleshooting

If git push fails, then there are likely local changes you haven't committed. Commit those first, then try pushing again: 
git add part1.circ   # add this for part 1 solution and alu.circ for part2
git add alu.circ
git add QUESTIONNAIRE
git commit
git push
Another likely source of a failed push is that your partner pushed, and you have not pulled their changes. Do a git pull. Compile and test that your code still works. Then you can add, commit, and push.

If that doesn't work, take a look at the "Troubleshooting" section of the Using git page. You may need to pull and merge some changes from master into your local. If so, this indicates that your partner pushed changes that you have not yet merged into your local. Anytime you pull into your local, you need to check that the result is that your solution is still correct (run in logisim) before submitting.