1. Due Dates:

Checkpoint (Part 1) Due by 11:59 pm, Monday, Mar. 01, 2021

Full Solution (Part 2) Due by 11:59 pm, Monday, Mar. 08, 2021
You will work with your assigned partner on this Lab 3 Partners
2. 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.
3. 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 halfway point.
4. Lab Starting Point Code
4.1. Getting Your Lab Repo
The setup for this week’s lab will be a little different since there is nothing to compile on the CS machines. You will modifying two circ files locally on your personal computer, so you can bypass the CS machines entirely for this lab assignment only.
If you have not done so already, install Logisim using the install instructions.
You will still need to retrieve your starting code and partner changes from GitHub and upload your changes to GitHub, but the way you do that will be a different for the Logisim assignment.
To retrieve your files, start by logging into GitHub and clicking on your Lab3 repo. Click on the file you want to download, e.g., part1.circ
, then click the Raw button on the next page. Once you have a view in you browser of just the file content and no GitHub buttons, use your browser to save the file to your computer using, e.g., right click and Save As.. or CtrlS. Remember to save the file as part1.circ
. Some browsers may want to rename the file part1.txt
by default.
You can repeat this process of clicking on a file, clicking on the Raw button, and using save as to download a copy of files on GitHub to get other files, or get updates from your partner.
4.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).
5. Part 0: Getting Started in Logisim
You do not need to submit anything for this part, but you should trying some things out in logisim before jumping into the two required parts of the lab.
Start by going through the Logisim Beginner’s Tutorial and try out building the XOR circuit. Run logisim with the name of the file you want to use for your new circuit, for example:
$ logisim
and choose File→SaveAs to choose a file name (and location) for the tutorial circuit. Then follow along the tutorial to build an XOR circuit and test it.
You can also try changing the inputs and outputs to be 4 bits each instead of 1 bit each. And you could try creating a new circuit for this (Project→Add Circuit) and adding some circuitry for testing the circuit, like we did in Wednesday lab.
Before starting Part 2, you may want try out some of the logisim
circuits (you can just do this in your test.circ
file).
See if you can figure out what some of the circuits do and how to
configure them. Refer to some of the logisim beginners guide and other
logisim references listed in Section 10.
6. Part 1: Sign extender and adder.
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 builtin Logisim circuits that do signextension 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 builtin 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.

Create a circuit (Project→Add Circuit) that takes a 2bit
2’s
complement number and performs sign extension so that the output is an equivalent 4bit 2’s complement number. 
Name this circuit something like signext2to4. Be sure to label each of your input and output values.
6.2. 1bit Full Adder
Create a 1bit 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!
6.3. 4bit Full Adder
Add a new circuit fulladder4
that takes two 4bit
input values, x
and
y
, and one 1bit
input value, carryin, and produces a 4bit
sum output
value, and a 1bit
carryout value.

To build this circuit you should use four copies of your
1bit
adder to add each digit. 
The two 4bit 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 4bit adder you are building adds two 4bit 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 4bit adder and a
copy of your sign extender. You are going to build a test circuit with three
input values:

one 4bit value:
x

one 2bit value:
y

one 1bit value:
carry_in
and two output values:

one 4bit value: the result of
x + y

one 1bit value:
carry_out
The input value y
, will need to be signextended 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:
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 part1 above, your ALU should use builtin components from Logisim whenever possible (with the exception of the subtracter, see the requirements below).
For example, you do not need to build an 8bit adder
— you may simply use
the 8bit adder
that is part of Logisim. You know how to build an adder
already, so let’s take advantage of some abstraction!
8bit adder:

To use an
8bit adder
, open theArithmetic
folder and selectAdder
. The defaultAdder
has "Data Bits" set to 8. That is an8bit adder
. 
The inputs to an
8bit adder
are also8bits
, so you need to hook up an8bit input pin
. The output is 8bits, so you need to hook up an8bit output pin
. 
The carryin and carryout bits are only
1bit
each.
7.1. Requirements

Your ALU will perform eight arithmetic functions on two
8bit
inputs, producing one8bit
output, and five1bit
outputs (condition code flags). 
It will have one
3bit input, the opcode
, which will select which of the eight arithmetic functions to perform. 
Implement selecting ALU output using a
multiplexor
with eight data inputs, one for each function result, and one threebit 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
becomes01110000
. Note that Logisim has aShifter
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 theShifter
can only be three bits. Use asplitter
to extract the last three bits of Y, then use anothersplitter
(in reverse) to build up a3bit
wire from the three least significant digits. IfY=01010100
, you would shift01010100
— 4 places to the left. 
101: X >>Y
(Shift right) without sign extension (also known as logical shift), e.g.10111001
becomes01011100
, not11011100
. 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
becomes11011100
and01000001
becomes00100000
; the input Y is still only 3 bits. 
111: X < Y?
The output should be00000001
if X < Y,00000000
otherwise. X and Y should be treated as 2’s complement values. Logisim has acomparator
gate that can be customized to perform almost exactly what you need, but it only outputs a1bit
0
or1
, so you’ll need to figure out how to make that eight bits.


You must implement subtraction
(X  Y)
asX + ~Y + 1
.Do Not Use Logisim’s Subtractor and Negator CircuitsLogisim 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 XY).
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 1bit
output flags. Each output flag’s value
should be zero unless it is specifically set as a sideeffect 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.
you may want to review the course slides for a discussion of what does/doesn’t constitute overflow.


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 theOF 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.
7.3. 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 rightclick 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.
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 8bit 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 8bit input into 8 1bit outputs. You can also do the reverse by simply connecting 8 1bit inputs to one side of the splitter and getting 1 8bit 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
For the Logisim assignment, you will not use the add, commit, and push process to submit your files to GitHub. Instead, log into GitHub, and go to your Lab3 repo. Next to the green Code button where you usually find the clone URL, you should see an Add File button. Click this button and select Upload Files.
On the next screen, you will be able to drag files or choose them from your computer’s file browser. You can add a descriptive commit message, and then click the green Commit changes button at the bottom. You do not need to change the default setting of commit directly to the master branch.
Once you have uploaded your files, notify your partner to download the update using the process outlined in Section 4.1.
At this point, you should submit the required Lab 3 Questionnaire (each lab partner must do this)