Assignment: Logisim Combinational Logic

Assigned
Wednesday, Sep 12, 2018
Due
Tuesday, Sep 18, 2018 by 10:30pm
Collaboration
Complete this assignment individually. You may not discuss the specific implementation of any of this assignment’s parts with your classmates, but you are welcome to review course material together in preparation for this assignment. If you use any resources other than our class discussions you must include a citations.txt file with your submission that clearly acknowledges those resources. You should cite help from the textbook, mentors, CS tutors, instructor, websites, or any other source.
Submitting
Please submit your circuit file, combinational-logic.circ, using gradescope. To do this, go to http://gradescope.com, log in, select this course, click on the Combinational Logic assignment, and drag your circuit file to the submission window that pops up. You may omit any test files, but do not forget to include your citations.txt file if you used any outside help for this assignment. Gradescope should show you your grade within a few minutes of submitting your work. You may resubmit this assignment as many times as you like up until the deadline.

Overview

In this assignment you will build two small circuits to add one-bit binary numbers, then chain these together to produce a larger adder that can add 8-bit numbers. This assignment will give you additional practice working with Logisim, where you will continue to use subcircuits, splitters, inputs, outputs, and basic gates. You will also see Logisim’s support for test files, which make it possible to validate your circuits without manually setting inputs and checking outputs.

Grading

Your grade on this assignment will depend on the correctness of your circuits. I will use a large test suite to validate your circuits’ outputs. To receive an A on this assignment, your circuits must pass every test case. Circuits that fail fewer than 5% of the test cases will receive a B, and circuits that produce a significant number of incorrect outputs will receive a C or lower.

You may not use any Logisim components except those under the Wiring and Gates categories. Submissions that use disallowed components (such as Logisim’s built-in adder) will receive a zero.

Testing circuits requires that I specify the names of inputs and outputs exactly in the test files. Please pay close attention to the instructions when setting up your circuits; any submission that requires me to manually change your circuit to conform to the assignment requirements will receive a 1/3 letter grade reduction. For example, an implementation with incorrect input names that is otherwise correct will receive an A- instead of an A.

Finally, some 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.

Once you have Logisim available, download the combinational-logic.circ starter circuit file. The file is set up with three subcircuits; please pay close attention to which part of the assignment should be completed in each subcircuit. You are free to move input and output pins around, but please do not rename any inputs or outputs. You should not create any additional subcircuits for this assignment.

Part A: Half Adder

Please complete this part of the assignment in the half-adder subcircuit.

Consider the problem of adding two bits $x_{1}$ and $x_{2}$:

Here $s$ represents the “sum” or the rightmost bit, while $c_{o}$ represents the carry (for reasons we’ll understand in the next day’s class, this is the carry out, hence the subscript).

  1. Complete the truth table for this problem, which is called a “half adder.”

    $x_{1}$ $x_{2}$ $c_{o}$ $s$
    0 0    
    0 1    
    1 0    
    1 1    
  2. Identify the sole two gates necessary to represent the $c_{o}$ and $s$ outputs of a half-adder circuit.

  3. Build a half-adder circuit in Logisim. (Note that additional gates are available in the Logisim explorer pane.)

    • The starter circuit file already has inputs named x1 and x2, and outputs co and s. These correspond to the terms $x_{0}$, $x_{1}$, $c_{o}$, and $s$, respectively.

    • You may find it visually helpful to arrange your two outputs such that the carry-out bit is to the left of the sum bit. This way, the two output bits can be read as a normal two-digit binary number, making it easy to test your circuit.

    • Test your circuit. It should display the sum of the two input bits, which will always be 0, 1, or 2 (displayed in binary).

While this circuit is fairly easy to test manually (there are only four cases to try), we can instead test it automatically using Logisim’s test vectors. First, download the half-adder-tests.txt test file. To run the tests in this file, select Test Vector from the Simulate menu item in Logisim while you are in the half-adder subcircuit. Click the Load Vector button and open the test file you just downloaded. The test vector window will then show you which tests you pass or fail.

I recommend adding test cases to this file before moving on to the next part of the assignment. You can find some basic information about the test vector format in the test file itself; you can edit this file with the programming text editor of your choice.

Part B: Full Adder

Please complete this part of the assignment in the full-adder subcircuit.

Half adders work when we want to add two one-bit numbers, but we often ask computers to add much larger numbers. The processor performs multi-bit addition by chaining together a series of adders. However, a half adder basically stands in isolation because it can’t take the carry from a previous column as input in a multi-bit addition. The full adder therefore incorporates not only the two bits of a number to sum, but also the carry-out bit from the previous column as a carry-in input bit, called $c_{i}$.

The truth table for a full adder would look like the following:

$c_{i}$ $x_{1}$ $x_{2}$ $c_{o}$ $s$
0 0 0    
0 0 1    
0 1 0    
0 1 1    
1 0 0    
1 0 1    
1 1 0    
1 1 1    
  1. Complete the truth table for a full adder.

  2. Use a Karnaugh Map and/or boolean algebra to identify reduced functions for both $c_{o}$ and $s$.

  3. Implement the full-adder circuit using the resulting simplified functions. The starter circuit file already has inputs named x1, x2, and ci, and outputs co and s. These correspond to the terms $x_{0}$, $x_{1}$, $c_{i}$, $c_{o}$, and $s$, respectively.

You should test your circuit to make sure it works correctly. I recommend testing with the Test Vector tool. You can download the starter test file for this subcircuit, full-adder-tests.txt. You should add additional tests to increase your confidence that your circuit is indeed correct.

Part C: 8-bit Adder

Please complete this part of the assignment in the main subcircuit.

Now that we have both full and half adders, you should chain these subcircuits together to add a pair of 8-bit numbers. The main subcircuit has two 8-bit inputs that should be added, an 8-bit output that should contain the sum, and a carry-out output that tells us wether the most significant bit addition produced a carry that does not fit in an 8-bit result. Note that there is no carry-in input for this adder; you should not add any additional inputs or outputs to this subcircuit.

The starter circuit provides inputs and outputs with the same names as the half-adder circuit. Note that these are different inputs and outputs, all but the co output carry eight bits rather than a single bit.

Once you have an implementation of your subcircuit, you should test it. There are far too many possible inputs to test every case, but you can cover many of them using a Test Vector. The test file 8-bit-adder-tests.txt shows how you can specify multi-bit test inputs.

Once you have completed this part, please follow the instructions at the top of the assignment to submit your work.

Other Notes

  • If you have red error signals on any wires coming out of your subcircuits that otherwise tested successfully, try saving your file, closing Logisim, and re-opening your circuit file. This clears the state in your elements.