Assignment 4: ALU Practice

Assigned: Monday, September 12

Due: Tuesday, September 20 at the beginning of class

Submitting your work: Please submit this assignment electronically before the beginning of class.

Overview

For this assignment, you will build a 4-bit ALU in Logisim that implements standard arithmetic and logical operations: bitwise AND, OR, NAND, and NOR; addition and subtraction; and less-than comparison.

Collaboration

For this assignment, you will work with your assigned partner from the list below. This assignment should be a learning experience for everyone in the team, so do not approach this as a “divide and conquer” task. You should use a pair programming approach as you build your circuits.

You may discuss this assignment with other groups, but please do not share your answers or logisim files with any other groups.

Groups

• Hamza, Hattie, and Giang
• Ryan and Theo
• Ana and Charlie
• Fengyuan and Jacob
• Linda and Adam H.
• Blake and Sara
• Jerry and Devin
• Bea and Eli
• Sophie and Matt
• Maddie and Kamal
• Tanner and Adam W.

Submitting your work

Each team should submit a single solution set via email to curtsinger@grinnell.edu with the subject [CSC 211] ALU Practice. Please CC all other team members when you send this email. Your submission should include:

1. answers to all written questions in the body of the email or an attached PDF or Word document,
2. an attached 4-bit-alu.circ Logisim file containing your implementation for parts 1 and 2
3. an attached complete-4-bit-alu.circ Logisim file containing your implementation for parts 3–5.

Grading

Because this is a large assignment, we will discuss a potential change to the course grading scheme that better reflects the amount of effort required to complete this assignment.

Your grade for the Logisim portions of this assignment will be determined by how many tests your ALU implementation can pass. I have provided a limited set of tests for the 1-bit ALU that should help you with writing your own tests, which I highly recommend.

Getting Started

You do not need to work on the MathLAN machines, although these are always available for your use. You can install Logisim on any computer with a recent version of Java. The testing functionality I will use for grading (and you may use for your own testing) requires a modified version of Logisim available from Cornell University’s CS 3410 course (download here).

To start this modified version of Logisim, run the command:

java -jar /home/curtsinger/bin/logisim.jar &

To start your project, download the following files:

4-bit-alu.circ

The Logisim scaffold where you will build your ALU.

1-bit-alu-tests.txt

A limited set of tests for the 1-bit ALU

4-bit-alu-tests.txt

A limited set of tests for the 4-bit ALU

Be sure to save frequently as you work. The provided .circ file includes most of the inputs and outputs you will need, but you will be adding a few subcircuits and inputs later in the assignment. Be sure to give these the exact same name (including upper and lower case) as the name requested in the assignment.

Subcircuits

We will use subcircuits for the first time in this assignment. You can read about subcircuits in the Logisim guide. The starter circuit files include all the subcircuits you will need for this assignment, so you can skip this reading for now.

Part 1: A 1-bit ALU

In the “1-bit ALU” subcircuit, build a 1-bit ALU with the following inputs and outputs:

inputs a and b

The inputs that should be ANDed, ORed, added, etc.

input operation

The operation selector. The ALU should perform AND when operation is 00, OR when operation is 01, addition when operation is 10, and nothing (for now) when operation is 11.

inputs a_invert and b_invert

These inputs should invert a and b, respectively, before they are connected to any of the ALU’s operations. Setting both a_invert and b_invert allows you to compute NOR and NAND (using AND and OR operations) without any additional gates. Setting just b_invert (and c_in) negates the b input, which allows you to perform subtraction, and later a less-than comparison.

input c_in

This input is the carry input from a chained adder, or the c_in input you can set when negating a number. Recall that in two’s-complement $-b = \bar{b}+1$. Setting this input to 1 lets you easily add one to the inverted b value (selected with b_invert).

output result

The result of the selected operation after all inversions, carry logic, etc.

output c_out

The carry output of a and b. Note that this should be 1 if a plus b plus c_in is two or larger, even when operation is set to something other than addition or subtraction.

You do not need to build your own adder or multiplexers. You should use Logisim’s built-in multiplexers, adders, and any logic gates you may need. You should only use one adder in the ALU; with b_invert and c_in set you can perform subtraction without any additional logic. Refer to the ALU readings from appendix C for a description of this mechanism.

Testing

To test your 1-bit ALU, run the following command, assuming your 4-bit-alu.circ and 1-bit-alu-tests.txt files are in the current directory.

java -jar /home/curtsinger/bin/logisim.jar -test "1-bit ALU" 1-bit-alu-tests.txt 4-bit-alu.circ

This command will report how many test cases passed. For any failing tests, it will report the test number and the outputs that did not match the expected values.

The arguments after -test are the name of the subcircuit being tested, the text file listing test cases, and the circuit file that contains the subcircuit to test. Take a look at the test file and add any additional test cases you need to be confident that your circuit works. Your grade depends on how well your circuit works, so I highly recommend writing extensive tests!

Part 2: A basic 4-bit ALU

Chain four of your 1-bit ALUs together to build a 4-bit ALU in the “4-bit ALU” subcircuit. The inputs and ouputs provided in the subcircuit are the same, except a, b, and result are now four bits, and have been connected to splitters to break each bit off into a separate line. The pin numbered “0” is the rightmost digit of the binary number in the pin’s value.

Hint: You should leave at least six rows between your 1-bit ALUs to leave room for the additional connections you will make in parts 3–5.

Testing

To test your 4-bit ALU, run the following command:

java -jar /home/curtsinger/bin/logisim.jar -test "4-bit ALU" 4-bit-alu-tests.txt 4-bit-alu.circ

Be sure to add your own test cases. You don’t need to cover every possible input, but the provided tests do not use all of the ALU’s basic operations. Try to write a test for each special case (adding positive numbers, adding negative numbers, overflowing on addition, subtracting a negative number, etc).

Part 3: Adding the slt operation

The slt (set if less than) operation produces an output of 0001 if a is less than b, otherwise it produces the output 0000. To perform this operation, the ALU first subtracts b from a. If the result of the subtraction is negative, then a is less than b. Because we are using two’s-complement numbers, the most-sigificant bit (MSB) in the result of the subtraction tells us if the result is positive (MSB = 0) or negative (MSB = 1).

Follow these steps to add the slt operation to your 4-bit ALU:

1. Save a copy of your .circ file as complete-4-bit-alu.circ. You should make all changes for parts 3–5 in complete-4-bit-alu.circ, leaving the 4-bit-alu.circ file unmodified after part 2.
2. Add a one bit input pin called less (all lowercase) to your 1-bit ALU subcircuit.
3. Connect the less input directly to the fourth input of your main multiplexer (controlled by operation).
4. Return to the 4-bit ALU subcircuit. Adding the less pin may have moved pins on the small version of your 1-bit ALU subcircuit. You can just reconnect them, or right click on the 1-bit ALU and choose “Edit Circuit Appearance” to move each of the pins. Clicking a pin in this view will show you which part of the circuit this is connected to.
5. Most of your 1-bit ALUs should produce output 0 for slt, regardless of the result. Only the lowest order bit should ever be 1. Add a one bit “Constant” element from the “Wiring” category. Set this constant to zero and connect its output pin to the less input of all your 1-bit ALUs except for the least-significant bit’s ALU. You can create a 0 constant for each 1-bit ALU if this is easier to fit into your circuit.
6. Create a new subcircuit called “MSB ALU” (MSB is short for “Most Significant Bit”). Return to your 1-bit ALU, select all components (from the Edit menu), copy, then paste these into the MSB ALU subcircuit.
7. Create a new one bit output pin called set in the high-order bit ALU subcircuit. You will use this output to pass the most significant bit back to the least-significant bit ALU’s less input. Connect the output to the sum output from the MSB ALU’s adder (see figure C.5.10).
8. Return to the 4-bit ALU subcircuit, select the 1-bit ALU connected to the highest-order bits (connected to the pins labeled “3” on the splitters), and delete this ALU.
9. Replace the ALU you deleted with your new MSB ALU. Connect the set output of this ALU to the less input of the lowest order bit’s ALU (connected to “0” pins from the splitters). Be sure all the other inputs and outputs for this adder are connected. Your 4-bit ALU should now resemble figure C.5.11 in the book.

To run an slt operation, set b_invert and c_in to 1 to negate b’s input. Then set operation to 11 to choose the slt output. All of the ALUs produce a 0 except the lowest order bit, which echoes the output from the high order bit’s set pin.

Be sure to write additional test cases for your expanded 4-bit ALU. You may want to add additional test cases for the 1-bit ALU and the high-order bit ALU.

Part 4: Overflow detection

It is useful for hardware to report whether an arithmetic operation resulted in overflow of a signed two’s-complement number (adding to a number until it wraps around to a negative, or subtracting until it wraps around to a positive). Note that this overflow for signed numbers is not the same as unsigned overflow, which is indicated in the final ALU’s c_out.

1. Write down the logical expression that results in 1 if and only if an overflow has occurred, and explain why your approach works.
2. Implement this logical expression in a new subcricuit called “overflow detector”.
3. Add an overflow output to your 4-bit ALU subcircuit, add the overflow detector to your 4-bit ALU, and connect it so overflow will be 1 whenever an overflow has occurred.

Be sure to write test cases for your 4-bit ALU’s overflow detection.

Part 5: Correcting the slt operation for overflow

Our implementation of slt is not quite correct. To see where this implementation fails, use the following settings:

• a = 1001 (-7)
• b = 0110 (6)
• operation = 11 (for slt)
• b_invert = 1 (required to negate b for slt)
• c_in = 1 (required to negate b for slt)

The result of the subtraction performed for slt is 7, a positive number. This means that slt will produce a 0000 output for this input, even though -7 is certainly less than 6.

Modify your circuit to fix this error (you will need to come up with the fix). You can add the additional logic to your 4-bit ALU subcircuit, or to the high-order bit ALU subcircuit.

Don’t forget to write test cases for your improved circuit!

License

This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.

Part 5 is derived from exercise C.24 in Patterson & Hennessy.