Lab 9: Combinatorial Circuits - https://artofcomputing.cecs.anu.edu.au/ Toggle Navigation The Art of Computing about schedule news labs contact student FAQ Lab 9: Combinatorial Circuits In this lab, you will use the Logisim tool, along with pen and paper, to analyse and create simple combinatorial circuits. Installing and Starting Logisim Unlike Snap!, Logisim does not run in a web browser but needs to be installed. It is not installed on the CSIT lab computers, so to use it, you will have to install it on your own computer or on your student account. Download the Logisim v. 2.7.1 JAR file and save it in a convenient location (e.g., your home directory). You will probably be able to start the program by simply (double-)clicking on the JAR file. If that doesn’t work, on a GNU/Linux system you can start a commandline (“terminal”) and type in java -jar logisim-generic-2.7.1.jar
(assuming you are in the directory where the file is). Note that Logisim requires Java version 5 or later. Exercise 9.1 (no marks) First, do the following simple exercise to familiarise yourself a bit with the Logisim environment. Download the file lab9ex1.circ (using “save link as”), then open the file in Logisim (select “Open…” under the “File” menu). If everything worked, you should now see a simple combinatorial circuit. What does this circuit do? It computes some function Output = F(A, B, C) where all three inputs and the output are binary (0 or 1). But what is the function F? To find out, you can: a. Figure it out by looking at the circuit. b. Select the “poke” tool (), click on the inputs A, B and C to change their value, and observe how the output changes. c. From the “Project” menu, select “Analyze Circuit”. This opens a window with information about the circuit. Under “Table” you can find the complete truth table for the circuit, and under “Expression” you can see the equivalent Boolean expression. (Note that Logisim does not have a symbol for logical AND in expressions: “x AND y” is written just “x y”. The symbol for logical OR is “+” and for NOT is “~“.) Make sure you try the first two methods before the last. Is there a simpler/smaller circuit that computes the same function? Using the truth table for the circuit, attempt to find a smaller expression that generates the same table. Build the corresponding circuit next to the one given (using the same inputs, but a new output) and test it to see that it gives the same result. (Again, Logisim offers you a way to cheat: The “Minimized” tab of the circuit analysis window will give you a minimal expression, and can even rebuild the circuit automatically for you. Use this to check what you came up with by hand.) Exercise 9.2 Sorting Numbers with Circuits In this exercise, you will construct a circuit that sorts four 4-bit binary numbers. This means the circuit has has 16 inputs and 16 outputs! If you tried build it directly, the result would probably be pretty gigantic. So, instead, we will introduce some intermediate abstractions, which will help keep the size of the result manageable. Download the file lab9ex2.circ and open it in Logisim. The project contains several defined components: a “1-bit swap”, a “4-bit swap” and a “4-bit compare & swap”. Task 1 1-bit swap (50%) The 1-bit swap element is not implemented. Your first task is to build it. The 1-bit swap has three inputs, called Input 1, Input 2 and swap?, and two outputs, called Output 1 and Output 2. The element is meant to implement a controllable swap of the two inputs into the two outputs. In other words, behaviour of the circuit should be as follows: When swap? is 0, the inputs are just copied to the outputs, that is Output 1 equals Input 1 and Output 2 equals Input 2. When swap? is 1, the outputs are the inputs swapped, that is Output 1 equals Input 2 and Output 2 equals Input 1. Hints To help you understand how to make this work, you can draw up the truth table (it has only 23 = 8 lines) and fill in the correct outputs for each case. If you are using more than 10 gates to build the circuit, you’re on the wrong track; there is an easier solution. Look at the truth table. All the inputs and output that your circuit should have are already in place, so you should not have to place any new “pins”. How to build circuits in Logisim To view and edit the circuit that implements one of the defined elements (1-bit swap, etc), double-click on it in the left-hand-side menu. You can also double-click “main” to get back to the main circuit. To add a gate to the circuit, select the gate you want from the menu on the left. Then just click on the circuit board to add the gate. When you have selected the edit tool () you can move components and add wires. Right-click and select “Delete” to remove a component or wire. To connect components, add or extend wires. Components have a small marker where they can connect (you will see a small green circle when the pointer is on the mark). You can also add a branch off an existing wire, at any point. Here is a short video showing how it is done. (Note: The circuit built in the video is not the solution to this exercise!) Test your circuit! After you have built a circuit, you can check that it does the right thing by either using the poke tool to vary the inputs, or using Logisim’s built-in circuit analyzer, which will show you the truth table for both outputs. The 4-bit swap element is implemented using several 1-bit swaps. Thus, after you have built the 1-bit swap (correctly), the 4-bit swap will also work. In the main circuit, off to the right, there is a small test circuit for the 4-bit swap: it has two 4-bit inputs and a (1-bit) swap input, and two displayed outputs. Using the poke tool, you can change the inputs; when you toggle the swap bit, you should see the outputs change place. (Note that when you use the poke tool to change multi-bit inputs, you must toggle each bit separately by clicking on it.) Task 2 The 4-number sorting circuit (50%) The 4-bit compare & swap element has two inputs and two outputs, which are all 4-bit binary numbers. It sorts the two input numbers: that is, the first (upper) output is the smaller of the two numbers, and the second (lower) output is the bigger one. Note that it does an unsigned comparison. This means the numbers are interpreted as positive (ranging from 0 to 15), not in 2’s complement. The 4-bit compare & swap element is implemented using the 4-bit swap and a “comparator” (a component from Logisim’s standard library). A test circuit is provided (also to the right in “main”): use the poke tool to change the inputs and observe what happens with the output. (This is also a chance to practice reading binary numbers: how do you set the inputs to, for example, 12 and 9?) Now, you should build the 4-number sorting circuit using only 4-bit compare and swap elements (and wires). The inputs (labelled A-D) are on the left and the outputs (labelled #1-#4) are on the right. The outputs should be the inputs sorted in increasing order, that is, #1 should be the smallest of A,B,C,D, #2 the second smallest, and so on. Hint If you have trouble working out how to sort the four numbers, think recursively. This circuit gives you part of one possible solution for sorting three numbers: After the two compare & swaps, the top wire has the smallest number, and the other two hold the two larger numbers (but not in sorted order). How would you complete this circuit to sort all three numbers? If you have a circuit that can sort three numbers, how could you use it to sort four numbers? Test and save your circuit! After you have built the circuit, check that works by varying the inputs. (The circuit analyzer tool does not work with multi-bit inputs and outputs.) Save your circuit in a new file (using “Save As…” from the File menu). This is the file that you will need to submit for this assignment. Submission: You must submit one Logisim circuit file, containing your solutions to Tasks 1 and 2. Submit the files through wattle. 14 May, 2017 1408 words Written by Patrik Haslum Pascal Van Hentenryck Lexing Xie Tags labs Quick links 2017 S1 lectures schedule: Monday 1200-1300 (PSYC G8) Tuesday 1000-1100 (PSYC G8) Wednesday 1200-1300 (PSYC G8) × Quick-access class pointers: TBC © The Art of Computing Team Built with Hugo
