Lesson 1:Lesson 1:
Elementary Boolean Functions
This lesson will introduce you to the elementary Boolean functions, and will familiarize you with the tools you will use throughout the course. The web page you are viewing is part of a self-contained course with a simulation-based laboratory. Using this web page and others like it, you will design circuits, simulate them, and print your results. It is not necessary to install any software on your system. All of the tools you will need are embedded in the pages themselves. No other software is required.
There are a few restrictions that are imposed by the way the tools have been implemented. All web pages for the course must be viewed in MS Internet Explorer Version 4.0 or greater. You must also use an IBM compatible PC to view the web pages. Your PC must run MS Windows 95, 98, or Windows NT.
The VDAL Logic Design Course is based on experimentation and simulation of circuits. Experiments will be done using both circuit schematics and text-based hardware design languages. Most experiments will be done using a simple hardware design language known as FHDL. This language is far simpler than commercial languages such as VHDL, but is extensive enough to permit the specification of a wide variety of circuits. Circuits can be automatically translated into VHDL for use with more advanced tools.
The editors you will need to create circuits will be embedded in the web pages where they are required. Furthermore, when we give a circuit as an illustration, we will display it in an editor window rather than using a static drawing. This will enable you to modify the illustration and observe the effect of changes in the circuit.
If you are like most people today, you already have extensive experience with computers. You have most likely seen the beautiful graphics and exciting animation of today's video games. You have probably used the computer to view photographs, write school reports, browse the web, look up information in a CD-ROM encyclopedia, and many other things. The computer is capable of being used in an almost unlimited number of ways, and is certainly one of the most useful and sophisticated tools ever invented. The computer is also one of the most complex devices ever invented. A modern computer contains several million transistors, all working in concert to perform the complex tasks demanded of it.
Designing a circuit with several million transistors is a monumental task, one that cannot be completed by a single person. Such a circuit must be broken down into smaller parts, each of which is assigned to a design team. Each part must be broken down further into smaller and smaller parts, until a point is reached where a single person can manage the design. Once all the components are designed, it is necessary to integrate them into larger and larger pieces, until the entire circuit is complete. The first step in learning to design computers is learning how to design elementary circuits. It is necessary for us to begin by examining the principles of the most elementary circuits used in computer design.
For the most part, the circuits used in computer design are digital circuits. Unlike analog circuits, which process complex wave forms, digital circuits process simple signals consisting of two different values. When we design a circuit we represent these two values as ONE and ZERO, or as TRUE and FALSE, depending on the type of digital circuit we are designing. Under normal circumstances, ONE and TRUE have the same representation, as do ZERO and FALSE. The method used to represent ONE and ZERO or TRUE and FALSE depends on the technology used to implement the circuit, but one common method is to represent ONE/TRUE as a high voltage, and ZERO/FALSE as a low voltage. These are generally known as active-high circuits, because in certain types of circuits, a TRUE value is assumed to cause some sort of activity. Active-low circuits, with TRUE represented as a low voltage, are also commonly used, especially in circuits designed to pass signals between different chips. In addition, there are mixed-logic circuits that have both active-high and active-low circuits. Unless otherwise specified, we will assume that all circuits are active-high, and that ONE and TRUE have the same representation. We will use the usual symbols 1 and 0 to represent ONE and ZERO, and TRUE and FALSE. Thus the symbol 1 will represent either ONE or TRUE, depending on the type of circuit we are currently designing.
Digital circuits have both electrical and logical properties. At the electrical level, the circuit must draw the proper amount of current, it must operate at the proper speed, and must not over-heat. At the logical level, digital circuits combine ones and zeros in specific ways to produce other ones and zeros. The simplest digital circuits are known as switching circuits. Switching circuits are used to compute elementary logical functions, and generally consist of no more than a couple dozen transistors.
To implement a large digital circuit, one starts with a collection of elementary switching circuits, and wires them together to produce the desired behavior. Once a basic set of circuits has been constructed, it is possible to ignore the electrical properties of the circuit, at least to some degree, and concentrate on the logical behavior. To simplify the process of logical design Boolean algebra is used to model the behavior of the elementary circuits. Algebraic operations can then be used to construct larger and larger circuits.
Boolean Algebra has two values 0 and 1, and three principal operators or functions, AND, OR, and NOT. We will assume that our underlying technology provides us with switching circuits that implement the AND, OR, and NOT functions, and some means of representing one and zero. Our design techniques will focus on the algebraic operations necessary to obtain a specific desired behavior. Once we have learned these techniques, we will be able to design circuits for any technology that is capable of implementing these three elementary functions. From time to time, we will introduce new elementary functions, but if necessary, these new functions can be constructed using the three elementary functions.
AND and OR are binary operations, meaning that they combine two Boolean values into one. The function of the operators AND, OR, and NOT is intuitive. AND produces a 1 only if both of its arguments are 1, while OR produces a 1 if either of its arguments is 1. NOT is a unary operation that reverses its input. The following tables give the values of each operator for each combination of argument values.
AND 0 1 OR 0 1 NOT 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 At the logical level, a digital circuit has one or more digital inputs and one or more digital outputs. (This is in contrast to the purely electrical connections such as power and ground .) Initially, a digital circuit is described using a set of Boolean equations, which show how to compute the digital outputs from the digital inputs. There must be one equation for each output. For complex circuits, it is typicall to have equations for intermediate values. For example, a circuit with four inputs and one output could be described with the following equation. In Boolean equations addition means OR, and multiplication means AND. In this circuit, the output q is equal to one if both a and b are equal to 1, or if both c and d are equal to 1.
q = ab + cd
In Boolean equations the NOT operator is indicated by a ' symbol following a variable or parenthesized expression. (In textbooks, it is more common to indicate the NOT function using an over-bar. However, this notation is difficult to manage on a web page.) The following circuit has one output q and two inputs a and b. The output is equal to 1 if a is zero and b is one.
q = a'b
In addition to the AND, OR and NOT functions there are a few other important Boolean functions that we should mention. These are the Exclusive-OR function, which is also called XOR, the NAND function and the NOR function. From time to time, we may also encounter the Exclusive-NOR function which is called XNOR or Equivalence. The XOR, NAND, and NOR functions are described in the following tables.
XOR 0 1 NAND 0 1 NOR 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 0 The XNOR function is the negation of the XOR function. Creation of the XNOR table is left as an exercise for the reader.
These new functions can be derived from the basic AND, OR, and NOT functions using the following equations.
NAND: q = (ab)'
NOR: q = (a+b)'
XOR: q = ab'+a'b
XNOR: q=ab+a'b'
Switching circuits that implement one of the elementary Boolean functions are called gates. Gates are named for the Boolean functions they implement, thus we speak of AND, OR, and NOT gates. When drawing the schematic of a digital circuit, each gate is represented by a characteristic shape. We will use the window below to illustrate these shapes. Click on the buttons to see the shape of each gate.
The signal flow through these symbols is assumed to be from left to right. Input wires are attached to the left side of the gate, and output wires are attached to the right. The gate can be reversed or rotated to show signal flow in a different direction. Note the difference between the OR gate and the XOR gate. The small circle on the outputs of the NAND and NOR gates indicates that the output is inverted. By the same token, the small circle on the output of the NOT gate indicates that its output is inverted. Without the small circle, the gate is known as a Buffer gate, or an Amplifier. The output of a Buffer gate is always equal to its input. At times we will use a small circle at the input of a gate to indicate that the input is inverted.
Before any digital circuit can be built, it must be simulated to verify its correctness. We will begin our simulation exercises with simple circuits consisting of a single gate. We will use the FHDL language to simulate our circuits. The following circuit is an FHDL description of a circuit containing a single AND gate. The first line indicates the beginning of the circuit and gives the circuit its name, MyCircuit . The next two lines show how the circuit is connected to the outside world. The fourth line describes a single AND gate, and shows how gate is connected to other gates (if any) and to the outside world. The last line is required.
MyCircuit: circuit inputs a,b outputs q gate1: and (a,b),q endcircuit
Type the circuit definition in the box below. Use tabs to separate the fields. Don't worry about lining things up.
Once the circuit description is complete, type your inputs in the box below. Inputs have the form 0,0 0,1 1,0 and 1,1. Type each on a line by itself and press enter. The simulator results will appear in red following the inputs.
The language used to describe this circuit is called FHDL (Florida Hardware Design Language). We will introduce more features of FHDL as we go along. Later in the course, we will demonstrate how to translate FHDL circuits into VHDL, a commercial hardware description language.
Each FHDL statement has a label field, an operation code, and an operand field. For some statements either the label field or the operand field will be blank, but the operation code is always required. The label field always starts in column 1 and ends with a colon. If a statement has no label, then it must start with a blank. Gates, such as and have two operands, an input list and an output list. The label field is optional, however a label field will allow gates to be more clearly identified in error messages. The input and output lists must be enclosed in parentheses. If either list contains only one element, the parentheses may be omitted. All circuits begin with a circuit statement and end with an endcircuit statement. The circuit statement should have a label giving the name of the circuit.
Now, you should experiment with the other six gates mentioned in this lesson. In the circuit given above, replace the line: gate1: and (a,b),q with one (and only one) of the following lines. Then simulate the new circuit with all four inputs. Repeat this exercise for all of the following lines. The not gate has only two inputs, 0 and 1.
gate2: or (a,b),q
gate3: xor (a,b),q
gate4: not a,q
gate5: nor (a,b),q
gate6: nand (a,b),q
gate7: xnor (a,b),q
You yave now finished Lesson 1. The course continues with Lesson 2.
Text Editor windows are implemented with BenetTec's AllText 4.5 control.
Drawings are from the Dover Old Fashioned Clip Art series.
Except as noted above, this page, its contents and ActiveX controls are Copyright (c) 1999, 2000 Peter M. Maurer
For comments and complaints send mail to peter_maurer@baylor.edu.
Home page http://cs.baylor.edu/~maurer