- Build, test, and simulate digital circuits.
- Observe how machine code instructions are executed by digital circuits.
- Apply incremental implementation and testing to design.

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

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

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!

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.

- one 4-bit value: x
- one 2-bit value: y
- one 1-bit value: carry_in

- one 4-bit value: the result of x + y
- one 1-bit value: carry_out

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

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.

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:

- 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 circuit.
- 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~~01010~~**100**-- 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 8 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. You may want to review the course slides for a discussion of what does/doesn't constitute 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)

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.

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

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

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.