Extra Credit Programming Assignment 5: Circuit Simulator in C Solution

    • Introduction

This assignment is designed to give you some experience in C programming while also increas-ing your understanding of circuits. You will be writing a C program to simulate the output of combinational circuits.


    • Circuit Description Directives

One of the inputs to your program will be a circuit description le that will describe a circuit using various directives. We will now describe the various directives.

The input variables used in the circuit are provided using the INPUTVAR directive. The IN-PUTVAR directive is followed by the number of input variables and the names of the input variables. All the input variables will be named with upper case alphabets (i.e., A,B,C, ...). An example speci cation of the inputs for a circuit with three input variables: A, B, C is as follows:

INPUTVAR 3 A B C

The outputs produced by the circuit is speci ed using the OUTPUTVAR directive. The OUT-PUTVAR directive is followed by the number of outputs and the names of the outputs.

An example speci cation of the circuit with output P is as follows:

OUTPUTVAR 1 P

The circuits used in this assignment will be built using the following building blocks: NOT, AND, OR, DECODER, and MULTIPLEXER.

The building blocks can produce temporary variables as outputs. Further, these building blocks can use either the input variables, temporary variables, a boolean ’1’ or a ’0’ as input.

Note: Output variables will never be used as inputs in a building block.

All the temporary variables will be named with lower case alphabets (i.e., a, b, c, ...).

The speci cation of each building block is as follows:



1

NOT: This directive represents the not gate in logic design. The directive is followed by the name of an input and the name of an output.

An example circuit for a NOT gate (B = A) is as follows.

NOTAB

AND: This directive represents the and gate in logic design. The directive is followed by the names of the two inputs and the name of the output.

An example circuit for an AND gate (C = A:B) is as follows:

ANDABC

OR: This directive represents the or gate in logic design. The directive is followed by the names of the two inputs and the name of the output.

An example circuit for an OR gate (C = A + B) is as follows:

ORABC

DECODER: This directive represents the decoder in logic design. The directive is followed by the number of inputs, names of the inputs, and the names of the outputs. The output are ordered in gray code sequence.

An example decoder with two inputs A and B is speci ed as follows:

DECODER2ABPQRS

P represents the AB output of the decoder, Q represents the AB output of the decoder, R

represents the AB output of the decoder, S represents the AB output of the decoder. Note that the outputs of the decoder (i.e., P, Q, R, and S) are in gray code sequence.

MULTIPLEXER: This directive represents the multiplexer in logic design. The directive is followed by the number of inputs, names of the inputs, names of the selectors, and the name of the output. The inputs are ordered in gray code sequence.

A multiplexer implementing a AND gate (P = A:B) using a 4:1 multiplexer is speci ed as follows:

MULTIPLEXER 4 0 0 1 0 A B P

The above description states that there are 4 inputs to the multiplexer. The four inputs to the multiplexer in gray code sequence are 0 0 1 0 respectively. The two selector input signals are A and B. The name of the output is P .







2
    • Describing Circuits using the Directives

It is possible to describe any combinational circuit using the above set of directives. For example, the circuit Q = AB + AC can be described as follows:

INPUTVAR 3 A B C

OUTPUTVAR 1 Q

AND A B w

AND A C x

OR w x Q

Note that Q is the output variable. A, B, and C are input variables. w and x are temporary variables.

Here is another example:

INPUTVAR 4 A B C D

OUTPUTVAR 1 P

OR C D v

AND A B w

MULTIPLEXER 4 0 1 0 1 w v P

As seen above, a circuit description is a sequence of directives. If every temporary variable occurs as a output variable in the sequence before occurring as an input variable, we say that the circuit description is sorted. You can assume that the circuit description les will be sorted.

Note: A temporary variable can occur as an output variable in at most one directive.


    • Format of the Input Files

As you will see in the problem statement below, your program will be given two les as input. One of the les will contain the description of a circuit using the directives described above. The other le will be an input values le. Each line of the input values le will be an assignment to variables in the INPUTVAR speci cation in the circuit description le.

For example, say that the circuit description    le contains the following:

INPUTVAR 3 A B C

OUTPUTVAR 1 Q

AND A B w

AND A C x

OR w x Q

Then an example of an input values    le is

1 0 1

1 1 1

Here the rst line corresponds to the assignment A = 1, B = 0, and C = 1, and the second line to the assignment A = 1, B = 1, and C = 1.

3
    • Instructions

You have to a write a C program that takes two  le names as command line arguments.

The rst le name will be that of the circuit description le, and the second le name will be that of the input values le.

For every line in the input values le, the program should interpret it as an assignment to the input variables, evaluate the circuit on that assignment, and output the values of the output variables.

The values of the output variables should be space separated and be in the same order as the output variables in the OUTPUTVAR directive, e.g., if the circuit description le has the directive OUTPUTVAR 3 P Q R, then the rst value should be that of the output variable P, followed by that of Q, and then that of R.

For every line in the input values  le, the output should be on a new line.


    • Circuit Simulation Program

You have to write a program called rst as described above. You are guaranteed that the circuit descriptions given as input to your program will be sorted. Let’s look at an example we have encountered before.


Example Execution 1

Suppose a circuit description  le named circuit.txt has the description for the circuit Q = AB +AC

INPUTVAR 3 A B C

OUTPUTVAR 1 Q

AND A B w

AND A C x

OR w x Q

and an input values    le named input.txt for the above circuit is as follows:

1 0 1

0 0 1

Then, on executing the program with the above circuit description le and input values le, your program should produce the following output (one line for each input in the input le).

./first circuit.txt input.txt

1

0




4


C D


1
00
A





0
01


1
11
0
Y
0
10







1
1





Figure 1: Circuit with Multiplexers from Homework 1


The output of the circuit Q = AB + AC when A is 1, B is 0 and C is 1 is 1. Hence the rst line is 1 in the output. Similarly, the output of the circuit is 0 when A is 0, B is 0, and C is 1.

Note the use of the temporary variables in the circuit description le to represent intermediate outputs.


Example Execution 2

The circuit description    le (circuit.txt) for the circuit in Figure 1 is as follows:

INPUTVAR 3 A C D

OUTPUTVAR 1 Y

MULTIPLEXER 4 1 0 1 0 C D w

MULTIPLEXER 2 w 1 A Y

The input value    le (input.txt) for the circuit is as follow:

1 1 1

1 0 0

0 1 0

When we execute the program the output should be as follows:

./first circuit.txt input.txt

1

1

0






5
    • Submission

You have to e-submit the assignment using Sakai. Your submission should be a tar le named pa5.tar. To create this le, put everything that you are submitting into a directory (folder) named pa5. Then, cd into the directory containing pa5 (that is, pa5’s parent directory) and run the following command:

tar cvf pa5.tar pa5

To check that you have correctly created the tar le, you should copy it (pa5.tar) into an empty directory and run the following command:

tar xvf pa5.tar

This should create a directory named pa5 in the (previously) empty directory.

The pa5 directory in your tar le must contain one subdirectory. The subdirectory should be named rst (in lower case). It should contain your source les, header les, and a make le.

Use the autograder to test your submission during development and before submission as you had done with your other assignments.


    • Grading Guidelines

Your program should work with the provide autograder

You should make sure that we can build your program by just running make. You should test your code as thoroughly as you can.

Your program should produce the output following the example format shown in previous sections. Any variation in the output format can result up to 100% penalty. There should be no additional information or newline. That means you will probably not get any grade is you forgot to comment out some debugging message.

Be careful to follow all instructions. If something doesn’t seem right, ask.


















6