Logisim ALU

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.

Grading

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.

Additional consideration will be given to the clarity of organization within your circuits. Wires and gates should be laid out in a fashion that facilitates comprehension.

Getting Started

To begin this assignment, you will need the starter circuit file and access to an installation of Logisim. If you are working on MathLAN, you can start Logisism with the following shell command:

$ java -jar /home/curtsinger/shared/logisim.jar

You can also install Logisim on your personal computer. To do this, you will need to copy the Logisim file from MathLAN or download logisim.jar directly from this site. You can then start the program with Java on your own machine.

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

If your web browser tries to display these files, rather than save them, you can try to “right click” on each link and select the option to downoad the file.

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. Failure to name your circuit inputs and outputs correctly will cause failed test cases and produce a very poor grade.

Part 1: A 1-bit ALU

In the “1-bit ALU” subcircuit of 4-bit-alu.circ, 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=b‾+1-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 multiplexors. You should use Logisim’s built-in multiplexors, 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. For a description of this mechanism, refer to the ALU readings from appendix B in your textbook.

When using Logisim’s built-in multiplexor, set its option “Include Enable?” to “No”. (Such an input pin allows many such multiplexors to share the same output line, because when Enable is deasserted, the output will have no signal.)

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/shared/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

In the “4-bit ALU” subcircuit of 4-bit-alu.circ, chain four of your 1-bit ALUs together to build a 4-bit ALU. The inputs and outputs 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 (the LSB, or 202^0 place) 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/shared/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.

    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 multiplexor (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. To make the higher order bits zero:
    1. Add a one-bit “Constant” element from the “Wiring” category.
    2. Set this constant to zero.
    3. Connect the constant’s output pin to the less input of all your 1-bit ALUs except for the least-significant bit’s ALU. Alternatively, you may create a 0 constant within 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” subcircuit, 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 “MSB 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 B.5.10 from your textbook).
  8. Return to the “4-bit ALU” subcircuit, select the 1-bit ALU connected to the highest-order bits (i.e., the one connected to the pins labeled “3” on the splitters), and delete this ALU.

  9. Replace the ALU you deleted with an instance of 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 B.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. (You may also begin from a truth table.)
  2. Implement this logical expression in a new subcircuit 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.

    Your configuration need not necessarily match the book’s placement of an overflow detector. You may add new inputs or outputs to other subcircuits if you wish, but do not remove or rename any existing outputs that have been specified.

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:

The result of the subtraction performed for slt is 3, 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!

Acknowledgments

Part 5 is derived from exercise B.24 (p. B-83) in

Patterson, D.A. & Hennessy J.L. (2014). Computer organization and design: The hardware/software interface. Waltham, MA: Morgan Kaufmann.

Copyright © Janet Davis, Charlie Curtsinger, and Jerod Weinman

CC-BY-NC-SA This work is licensed under a Creative Commons Attribution NonCommercial ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/4.0/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.