4. Digital Logic and Operators
Part of
CS:2820 Object Oriented Software Development Notes, Fall 2017
|
We need a subject to use for the large-scale simulation exercise that will motivate the bulk of the machine problems assigned this semester. While, in the lectures, we will focus on the simulation of a road network, the machine problems will focus on something else.
This semester, we will focus on conventional Boolean digital logic, the kind that underlies the computers inside just about everything these days. In previous semesters, we have worked with ternary (3-valued) logic and neural networks. In the Fall of 2015, we worked with digital logic, but don't worry, the logic simulator we write this semester will be totally incompatable with the simulator that we wrote back then.
All solutions to programming assignments from my prior offerings of this course are available on line. Feel free to study them.
Boolean logic is called that because it was forulated by George Boole (1815-1864). In 1854, Boole published The Laws of Thought. In this work, he demonstrated that logic obeyed algebraic laws and was, therefore, properly considered to be a branch of mathematics. Previously, logic had been seen purely as a branch of philosophy. In medieval times, the seven libral arts were music, arithmetic, geometry and astronomy (the quadrivium or scientific arts), plus grammar, logic and rhetoric (the trivium or humanities). Boole's algebra moved logic from the humanities to the sciences!
Boolean logic was not considered to have any practical engineering uses until Claude Shannon showed, in 1937, how it could be used to analyze systems of electrical relays. Dial telephones based on relay technology had been around since the 1890s, but the design of relay-based systems was ad hoc until Shannon, using the work of Boole, demonstrated that relays implement logical operations and therefore are subject to mathematical analysis.
You all know a good amount of Boolean logic, since this is taught in Discrete Structures, a prerequisite for this course, and since Boolean variables and expressions are a common feature of programming languages. Nonetheless, a bit of review is appropriate. The basic Boolean values are:
Ternary logic adds a third value, unknown, and Quatrenary logic divides unknown into two values, overdefined meaning neither true nor false, and underfined meaning could be either true or false. These may be interesting, but we'll ignore them this semester.
George Boole represented false as 0 and true as 1; and he noticed that, with these two values, the logical and operator behaved like multiplication, and the logical or operator behaved sort of like addition if you take any nonzero results and replace it with 1. We continue to use essentially the same conventions in modern computer languages such as C, C++ and Java, but nothing requires us to do so.
If we limit ourselves to two-argument operators, where each argument has 2 possible values, any Boolean function f(a,b) can be described by a truth table with the following structure:
| ||||||||||||||||||||
In the above table, the outputs are given as unknowns, w, x, y and z. Since there are 4 values in the output column and each value may take exactly 2 values, there are 16 possible Boolean functions of 2 inputs. We can enumerate all 16 of these functions and give many of them names:
|
The above table only lists the Boolean functions that digital logic designers commonly name. Logicians like to name additional functions such as implication (1101).
The difference between the Boolean value true and the Boolean function true(a,b) may not be obvious. This function has the value true regardless of the values of its arguments. Similarly, the function a(a,b) has the value of its first argument, regardless of the value of the second argument.
A mathematician is happy with the concept of a logic function, but electrical engineers who design computers need to worry about the speed of light and about the speed of logic. Logicians think of logical functions as establishing equations where time is not an issue. Electrical engineers think in terms of building devices that evaluate logic functions.
We call a device that evaluates a logic function a gate. Each gate has inputs and an output, where the hardware of that gate sets the value of its output as a function of the values of its input. Unlike the mathematician's idealized functions, however, gates have time delays. If an input to the gate changes, the output will only change some time later. In the general case, the delay can depend on which input changed and how.
For most design of digital circuitry, we can use a more simplistic model that assigns a fixed delay to each gate. This delay does not depend on the values that change. Instead, if an input to a gate changes in a way that will cause the output of that gate to change, this change is only visible after the delay.
In slightly more sophisticated models, the delay from input to output of a gate has a slight random factor that simulates the effect of electrical noise, and the gate has a minimum response time so that, if the output would go from true to false to true or from false to true to false in a time shorter than the gate delay, the intermediate value is never seen and an outside observer looking at the output of the gate never sees any change. To start with, we'll ignore this, but note that this complexity begins to matter when there is feedback in a digital circuit.
Finally, in real digital logic, physical wires of some kind connect the outputs of gates to the inputs of other gates. These wires do not transmit signals instantly, but rather, signals injected into one end of a wire take a finite but small time to reach the other end of the wire. Modern computers are fast enough that the speed of light (about 1 foot per nanosecond) does not look infinite. When an electrical signal travels down a straight perfectly conducting wire surrounded by vacuum with no other conductors nearby, it travels at the speed of light.
None of the wires in a computer are infinitely far from other conductors, and none of them are perfect conductors. As a result, signals travel slower than the speed of light. In typical cables, signals travel at about 2/3 to 1/2 the speed of light. For signals traveling on traces on the surface of a printed circuit board, 1/2 the speed of light is a good guess. Signals traveling through buried layers are slower, and signals traveling on buried layers within a silicon integrated circuit chips can be much slower.
This is not a digital logic course. You will not be expected to be able to design digital logic circuits nor to understand how they are used to build computers! You will, however, be building a logic simulator. To do this, you will have to extract the relevant details from the description above and conver this to classes and objects in much the way we are describing road networks using classes and objects.
In earlier lectures, we came up with code looking something like this for describing road networks:
import java.util.LinkedList;
/** Roads are one-way streets linking intersections
* @see Intersection
*/
class Road {
float travelTime; //measured in seconds
Intersection destination; //where the road goes
Intersection source; //where the comes from
// name of road is source-destination
}
/** Intersections join roads
* @see Road
*/
class Intersection {
String name;
LinkedList <Road> outgoing = new LinkedList <Road> ();
LinkedList <Road> incoming = new LinkedList <Road> ();
// Bug: multiple types of intersections (uncontrolled, stoplight)
}
It's time to start working on initializing a road network. In theory we could build the road-network description in many ways. For example, we could build a graphical user interface where users could point and click to drag and drop intersections and roads into place.
GUIs are marvelously fun to use, interesting to design, and worthy of an entire course, but this is not that course, so we will pursue a simpler approach, reading the description of a road network from a text file. Consider, for example, a file structured as follows:
intersection ... intersection ... intersection ... road ... road ... road ... road ... road ...
Each line of the file begins with a keyword, either road or intersection, followed by the attributes of that road or intersection. We will expand on this description of the text file after we make some progress toward reading it.
Java provides a very useful class for reading text files, the scanner. To quote the official definition of this class: "A Scanner breaks its input into tokens using a delimiter pattern, which by default matches whitespace. The resulting tokens may then be converted into values of different types using the various next methods." The setup for calling a scanner is as follows:
import java.io.File;
import java.util.Scanner;
/** RoadNetwork, the main class to build a network of roads and intersections.
* @see Road
* @see Intersection
*/
public class RoadNetwork {
public static void main(String[] args) {
// Bug: Must add code to see if there is a file name
Scanner sc = new Scanner(new File(args[0]));
// Bug: What if the file doesn't exist?
}
}
The main class of the program must be declared as public class and the class name must match the file name. The main method must be declared as a public static void method with the name main, and it must take an un-dimensioned array of strings as an argument. By convention, this parameter is called args because it holds the arguments that were used to launch the program. The conventions for main are inherited from C++ which inherited them from C, a language that was developed in the late 1960s in the context of the Unix system and is strongly coupled to the Unix command line user interface.
Aside: This mix of required text and traditional text is called boilerplate. The concept of boilerplate text comes from legal documents, where boilerplate text is text that has been tested in court for generations and is therefore known to be resistant to challenge (like armor plate or the plate steel used to make steam boilers). Lawyers copy boilerplate from lawbooks instead of writing creatively in order to avoid the risk that they might overlook some detail that creates text that is vulnerable in court. Any text that you copy from a standard form instead of writing creatively has come to be knwn as boilerplate.
The above code creates a scanner called sc that reads from a file whose name is give by the first command line argument passed when launching the main program.
Consider running your program with this command:
[HawkID@serv15 ~/project]$ java RoadNetwork IowaCity.txt
This launches RoadNetwork.class, the file created by compiling RoadNetwork.java. Inside the main method of this class, you will find that args[0] has been set to the value "IowaCity.txt", so the call to the initializer
Scanner sc = new Scanner(new File(args[0]));
is equivalent to
Scanner sc = new Scanner(new File("IowaCity.txt"));
There are a number of different initializers for class Scanner, but the one we are calling here expects an open file as a parameter, and the initializer we are using for class File takes the file name, as a string, as a parameter.
Of course, the skeletal definition given above has some bugs. The code ought to check that there is a command line argument before using it, and it ought to output a sensible error message if the file does not exist or cannot be read. We need to fix the latter to make this file compile, and we will do this in the next class.