Lab 3: Modelling Digital Circuits

Digital circuits can be modelled as boolean functions, and in this lab you will do so to implement a toolkit that may help you in your course on digital electronics. You can think of this toolkit as something like the toolkit for pictures described in the book, except that in this case, the objects we manipulate are circuits.

Environments

We shall model circuits with a number of named inputs and outputs. We can represent their values by a list with the following type,

type Env = [(String,Bool)]

containing names and their values. For example, the inputs to the following AND gate

might be

[("x",True), ("y",False)]

representing a True input on x and a False input on y. The corresponding output would be

[("z",False)]

Such a list of names and values is called an environment (in the sense of omgivning, not miljö); it contains the values of all the variables we are interested in, and provides a context in which any expression involving variables can be evaluated.

We will need to look up the values of variables stored in the environment.

Define a function

value :: String -> Env -> Bool

such that value x env returns the value associated with x in the environment env.

Examples

value "x" [("x",True),("y",False)] = True
value "y" [("x",True),("y",False)] = False

Circuits

Circuits produce outputs from inputs. We will model a circuit by

the names of its inputs,
the names of its outputs,
and a function which computes the circuits outputs from its inputs.

The circuit type will therefore be

type Circuit = ([String], [String], Env -> Env)

For example, the AND gate above would be modelled as

andGate :: Circuit
andGate = (["x", "y"], ["z"], andGateFn)
  where andGateFn env = [("z",value "x" env && value "y" env)]

Notice how andGateFn uses value to extract the values of its inputs from the environment it is given, and constructs an environment containing a value for its output, "z", as its result. (We could also have written this definition like this:

andGate = (["x", "y"], ["z"], \env -> [("z",value "x" env && value "y" env)])

using a λ-expression to write the definition of andGateFn "in place" where it is used.)

Notice also that andGate is not itself a function; it is a tuple containing a function, which is not at all the same thing. If we want to simulate a circuit on a given input, we need to extract the function from it -- for example, using

simulate :: Circuit -> Env -> Env
simulate (inputs,outputs,action) env = action env

Calling simulate andGate [("x",True),("y",False)] produces the output [("z",False)].

Define

inverter :: Circuit
orGate :: Circuit
xorGate :: Circuit

to model an inverter, an OR gate, and an exclusive OR gate, in a similar way. Choose suitable names for the inputs and outputs yourself. (The exclusive-OR of two booleans is True if exactly one of the inputs is True, and False otherwise.)

Truth Tables

We can illustrate the behaviour of a circuit using a truth table giving the values of the outputs, for each combination of input values. For example, the truth table for the AND gate above would be

x       y       |       z
--------------------------------
True    True    |       True
True    False   |       False
False   True    |       False
False   False   |       False

All the information needed to produce such a table is given in the type Circuit: the first component of a circuit, the names of the inputs, tell us what to call the columns to the left of the "|"; the second component, the names of the outputs, tell us what to call the columns after the "|", and the third component, the function, tells us how to compute a row of the output from a row of the input.

Define a function

tabulate :: Circuit -> String

which generates a truth table from a circuit, in a format like the example above.

Example

putStr (tabulate andGate)

should print the table above.

I suggest writing a separate function to compute the left part of the table first, that is, to decide which rows should be present. Then you can compute the values of the outputs for each row. Don't forget that a circuit can have several outputs (thus, several columns after the "|"), even though the examples we have constructed so far have only one.

Composing Circuits in Series

Larger circuits can be built up by composing smaller ones. We will consider two ways of doing so, connection in series, and connection in parallel.

When two circuits are connected in series, the outputs of the first become the inputs of the second. For example, we might connect the AND gate above to an inverter

to create a NAND gate

(where z is now an internal wire, neither an input nor an output).

Obviously, the first circuit should produce as outputs all of the inputs that the second circuit requires, but it does not matter if it produces other outputs also -- they are simply discarded.

Define an operator

 (>.>) :: Circuit -> Circuit -> Circuit

which constructs the circuit consisting of its two arguments connected in series.

Example

We should be able to define a NAND gate by

nandGate :: Circuit
nandGate = andGate >.> inverter

and then

putStr (tabulate nandGate)

should print

x       y       |       w
--------------------------------
True    True    |       False
True    False   |       True
False   True    |       True
False   False   |       True

Tips

We can define an operator in Haskell in just the same way we define a function, but we write an operator application on the left hand side of the definition. For example, in this case we might write the definition of >.> as

(inputs,outputs,fn) >.> (inputs',outputs',fn') = ...

(where you are supposed to fill in the ...), using pattern matching to give names to the components of the two circuits. When we declare the type of an operator, as I did above, we enclose its name in brackets.

If you add a line

infixr 9 >.>

(which specifies how tightly the operator >.> binds), then Haskell will allow you to write, for example,

 f >.> g >.> h

without brackets.

Wiring

When we connect circuits in series, the outputs of the first circuit must have the same names as the inputs of the second. But suppose we had called the input of the inverter w instead of z? Then we would not have been able to connect it to the AND gate we modelled earlier. (You may well have encountered this problem!)

The solution is to model a wire, connecting an input with one name to an output with another:

Define

wire :: String -> String -> Circuit

so that wire x y constructs a circuit with one input, x, and one output, y, whose value is equal to the input.

Example

If your inverter's input is called w, you should be able to construct the circuit above as

 andGate >.> wire "z" "w" >.> inverter

Composing Circuits in Parallel

When we connect two circuits in parallel, the inputs are shared between them, so that either circuit can read any input, and the outputs are combined. For example, here is a half-adder, produced by composing an XOR gate and an AND gate in parallel. (A half-adder adds together two bits, producing a sum bit and a carry bit).

Notice that both gates receive both inputs, and the outputs of the half-adder consist of the combined outputs of the two gates.

Define an operator

(|||) :: Circuit -> Circuit -> Circuit

which constructs the circuit consisting of its two arguments connected in parallel. The inputs will be the combined inputs of the two argument circuits, and the outputs will be the combined outputs.

Example

If you have an AND gate and an XOR gate available, both with inputs x and y, and both with outputs called z, then you can construct a half-adder as

halfAdder :: Circuit
halfAdder = (andGate >.> wire "z" "carry") ||| (xorGate >.> wire "z" "sum")

Notice that you have to rename the outputs using wires, so that the outputs of the entire half-adder have the names we want.

Printing the truth table of the half-adder using

putStr (tabulate halfAdder)

should produce

x       y       |       carry   sum
----------------------------------------
True    True    |       True    False
True    False   |       False   True
False   True    |       False   True
False   False   |       False   False

Tips

You may find the standard function union useful to compute the inputs of the combined circuit. It is defined in the standard List library, which means you must add a line

import List

at the top of your program to use it.

Add a line

infixr 8 |||

so you can use the new operator without brackets. The number 8 is its binding strength: since this is less than 9 (the strength we gave >.>), then ||| will bind less tightly than >.>. In other words, we can omit the brackets in the definition of halfAdder above.

Making a Full Adder

A full adder performs "one bit worth" of addition: it adds together two input bits to produce a sum bit and a carry bit, but in contrast to a half adder it can also handle a carry-in. An adder for n-bit numbers can be constructed by connecting n full adders in a row. The full adder itself can be built from two half adders, as shown below:

Here the carry-in is called cin, and the carry out is called cout.

Construct a model of the full adder

fullAdder :: Circuit

using halfAdder, orGate, wires, and the operators ||| and >.>, and print its truth table using tabulate.

Remark

In this lab, we have modelled combinational circuits, that is, circuits with no state, or "memory". You will shortly meet sequential circuits, which do have a memory, and therefore can produce different outputs at different times, even given the same inputs. The general approach we've taken works for sequential circuits also: the only difference is that the inputs and outputs are no longer single booleans, but rather lists of booleans, representing the value of the signal at each time step. Unfortunately, we don't have time to explore this idea now.

There is a nice recursive algorithm to construct the disjunctive normal form of a boolean function -- i.e. the job you do using Karnaugh maps -- but this lab is too short to contain it!

Deadline

Solve this problem in pairs as before. You should hand in the code of your solution to your group tutor at the group meetings in the week beginning October 14th, and also submit it electronically. You should include instructions to enable your tutor to run your code.

If you want to work with a different partner (because your original partner wants to choose the alternative lab, for example), you may. Just make sure that

Only one lab group uses each account. If you need an extra account, just ask at the help desk in the basement of the Matematiska Centrum.
The "försättsblad" you hand to your tutor carries the names of the people who actually worked on the solution.

Last modified: Sun Sep 29 23:34:12 MET DST 2002