Home CPSC 305

Combinatorial Analysis

Overview

Complex circuits are not necessarily built from scratch by hardware designers. There are tools which can take truth tables or boolean expressions and construct circuits from them automatically. These tools are also generally able to simplify circuits so that they use fewer logic gates.

In this lab, we will learn how to do this with Logisim.


Combinatorial Analysis in Logisim

Logisim is capable of building circuits automatically from a truth table or an expression. To get started, click the "Window" menu, and then "Combinatorial Analysis". This will open a second window for creating a combinatorial circuit.

First you must enter the inputs and outputs of the circuit. These will create pins which are labeled with the name you give the input or output.

Here, I created three inputs for a simple multiplexer circuit:

And one output for the circuit:

Next, you have to specify the circuit behavior. There are two ways to do this:

In the "Minimized" tab, you can see a simplified version of the expression which governs your circuit. When you are read, click "Build Circuit" which will generate the gates for you.

In addition to giving the circuit a name, you can specify that the circuit should use only two-input gates, or that the circuit should be built out of NAND gates alone.

Then, Logisim will display the generated circuit for you. The multiplexer made of NAND gates looks like this:


Hierarchical Design

Large circuits are built out of smaller components in a hierarchical way, just like large programs are built out of smaller functions. This is done for the exact same reasons:

When we create a circuit using the combinatorial analysis tool in Logisim, it automatically makes it a component which can be added into something else. Notice on the left-hand side of the window, Logisim has something called "main". This is our "main" circuit which is similar to the main function in a C program - it is the top-level design which may reference other, smaller components.

When we created the multiplexer above, it creates a component which can be added into the main circuit. Adding it looks like this:

By default, the multiplexer has the three inputs on the left and the output on the right, and is drawn as a rectangle.

To build a complicated circuit, we should look to break it into manageable chunks, just like when writing a complicated program.


Exercise: Date Checker

For this lab, you will make a circuit which will test if a date is valid or not. For example, the dates "October 31", "February 20" and "April 30" are all valid, but the dates "November 31", "February 30" and "April 31" are not.

To do this, you should create two different circuits using the combinatorial circuit creator:

You should then build the "main" circuit which has 4 pins for the month, 5 pins for the day, and one pin for the leap year. Wire the month and leap year pins into the "Month to Max Days" circuit.

Wire the output of the "Month to Max Days" circuit, along with the lower two bits of the day into the "Two-Bit Less Than or Equal To" circuit. If that circuit outputs a 1 or if any of the three highest bits of the day counter are 0, then the day is valid. Otherwise, the day is not valid. You should wire this to an LED so that the light turns on whenever the inputs reflect a valid day, and off if the day is invalid.

This circuit is much easier to design hierarchically, and using the combinatorial analysis tool!


Submitting

When your circuit works, email the code to ifinlay@umw.edu. Be sure to test it thoroughly!

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.