AMAZON multi-meters discounts AMAZON oscilloscope discounts
1. Introduction
This section covers the basics of digital logic. The goal is straightforward -- provide a background that is sufficient for a reader to understand remaining sections.
Although many low-level details are irrelevant, programmers do need a basic knowledge of hardware to appreciate the consequences for software. Thus, we will not need to delve into electrical details, discuss the underlying physics, or learn the design rules that engineers follow to interconnect devices. Instead, we will learn a few basics that will allow us to understand how complex digital systems work.
2. Digital Computing Mechanisms
We use the term digital computer to refer to a device that performs a sequence of computational steps on data items that have discrete values. The alternative, called an analog computer, operates on values that vary continuously over time. Digital computation has the advantage of being precise. Because digital computers have become both inexpensive and highly reliable, analog computation has been relegated to a few special cases.
The need for reliability arises because a computation can entail billions of individual steps. If a computer misinterprets a value or a single set fails, correct computation will not be possible. Therefore, computers are designed for failure rates of much less than one in a billion.
How can high reliability and high speed be achieved? One of the earliest computational devices, known as an abacus, relied on humans to move beads to keep track of sums. By the early twentieth century, mechanical gears and levers were being used to produce cash registers and adding machines. By the 1940s, early electronic computers were being constructed from vacuum tubes. Although they were much faster than mechanical devices, vacuum tubes (which require a filament to become red hot) were unreliable -- a filament would burn out after a few hundred hours of use.
The invention of the transistor in 1947 changed computing dramatically. Unlike vacuum tubes, transistors did not require a filament, did not consume much power, did not produce much heat, and did not burn out. Furthermore, transistors could be produced at much lower cost than vacuum tubes. Consequently, modern digital computers are built from electronic circuits that use transistors.
3. Electrical Terminology: Voltage and Current
Electronic circuits rely on physical phenomena associated with the presence and flow of electrical charge. Physicists have discovered ways to detect the presence of electrical charge and control the flow; engineers have developed mechanisms that can perform such functions quickly. The mechanisms form the basis for modern digital computers.
Engineers use the terms voltage and current to refer to quantifiable properties of electricity: the voltage between two points (measured in volts) represents the potential energy difference, and the current (measured in amperes or amps) represents the flow of electrons along a path (e.g., along a wire). A good analogy can be made with water:
voltage corresponds to water pressure, and current corresponds to the amount of water flowing through a pipe at a given time. If a water tank develops a hole and water be gins to flow through the hole, water pressure will drop; if current starts flowing through a wire, voltage will drop.
The most important thing to know about electrical voltage is that voltage can only be measured as the difference between two points (i.e., the measurement is relative).
Thus, a voltmeter, which is used to measure voltage, always has two probes; the meter does not register a voltage until both probes have been connected. To simplify measurement, we assume one of the two points represents zero volts, and express the voltage of the second point relative to zero. Electrical engineers use the term ground to refer to the point that is assumed to be at zero volts. In all digital circuits shown in this text, we will assume that electrical power is supplied by two wires: one wire is a ground wire, which is assumed to be at zero volts, and a second wire is at five volts.
Fortunately, we can understand the essentials of digital logic without knowing more about voltage and current. We only need to understand how electrical flow can be controlled and how electricity can be used to represent digital values.
4. The Transistor
The mechanism used to control flow of electrical current is a semiconductor device known as a transistor. At the lowest level, all digital systems are composed of transistors. In particular, digital circuits use a form of transistor known as a Metal Oxide Semiconductor Field Effect Transistor (MOSFET), abbreviated FET. A MOSFET can be formed on a crystalline silicon foundation by composing layers of P-type and N-type silicon, a silicon oxide insulating layer (a type of glass), and metal for wires that connect the transistor to the rest of the circuit.
The transistors used in digital circuits function as an on/off switch that is operated electronically instead of mechanically. That is, in contrast to a mechanical switch that opens and closes based on the mechanical force applied, a transistor opens and closes based on whether voltage is applied. Each transistor has three terminals (i.e., wires) that provide connections to the rest of the circuit. Two terminals, a source and drain, have a channel between them on which the electrical resistance can be controlled. If the resistance is low, electric current flows from the source to the drain; if the resistance is high, no current flows. The third terminal, known as a gate, controls the resistance. In the next sections, we will see how switching transistors can be used to build more complex components that are used to build digital systems.
MOSFET transistors come in two types; both are used in digital logic circuits.
FIG. 1 shows the diagrams engineers use to denote the two types†.
Gate Source Drain Gate Source Drain (a) (b) current flows from S to D when G is positive current flows from S to D when G is negative
FIG. 1 The two types of transistors used in logic circuits. The type labeled
(a) turns on when the gate voltage is positive; transistor labeled (b) turns
on when the gate voltage is zero (or negative).
In the diagram, the transistor labeled (a) turns on whenever the voltage on the gate is positive (i.e., exceeds some minimum threshold). When the appropriate voltage appears on the gate, a large current can flow through the other two connections. When the voltage is removed from the gate, the large current stops flowing. The transistor labeled (b), which has a small circle on the gate, works the other way: a large current flows from the source to the drain whenever the voltage on the gate is below the threshold (e.g., close to zero), and stops flowing when the gate voltage is high. The two forms
†Technically, the diagram depicts the p-channel and n-channel forms of a MOSFET.
are known as complementary, and the overall chip technology is known as CMOS (Complementary Metal Oxide Semiconductor). The chief advantage of CMOS arises because circuits can be devised that use extremely low power.
5. Logic Gates
How are digital circuits built? A transistor has two possible states -- current is flowing or no current is flowing. Therefore, circuits are designed using a two-valued mathematical system known as Boolean algebra. Most programmers are familiar with the three basic Boolean functions: and, or, and not. FIG. 2 lists the possible input values and the result of each function.
FIG. 2 Boolean functions and the result for each possible set of inputs.
A logical value of zero represents false, and a logical value of one represents true.
Boolean functions provide a conceptual basis for digital hardware. More important, it is possible to use transistors to construct efficient circuits that implement each of the Boolean functions. For example, consider the Boolean not. Typical logic circuits use a positive voltage to represent a Boolean 1 and zero voltage to represent a Boolean 0. Using zero volts to represent 0 and a positive voltage to represent 1 means a circuit that computes Boolean not can be constructed from two transistors. That is, the circuit will take an input on one wire and produce an output on another wire, where the output is always the opposite of the input -- when positive voltage is placed on the input, the output will be zero, and when zero voltage is placed on the input, the output will be positive†. FIG. 3 illustrates a circuit that implements Boolean not.
The drawing in the figure is known as a schematic diagram. Each line on a schematic corresponds to a wire that connects one component to another. A solid dot indicates an electrical connection, and a small, open circle at the end of a line indicates an external connection. In addition to the two inputs and an output, the circuit has external connections to positive and zero voltages.
Electronic circuits that implement Boolean functions differ from a computer pro gram in a significant way: a circuit operates automatically and continuously. That is, once power is supplied (the + voltage in the figure), the transistors perform their function and continue to perform as long as power remains on -- if the input changes, the output changes. Thus, unlike a function in a program that only produces a result when called, the output of a circuit is always available and can be used at any time.
To understand how the circuit works, think of the transistors as capable of forming an electrical connection between the source and drain terminals. When the input is positive, the top transistor turns off and the bottom transistor turns on, which means the output is connected to zero volts. Conversely, when the input voltage is zero, the top transistor turns on and the bottom transistor turns off, which means the output is connected to positive voltage. Thus, the output voltage represents the logical opposite of the input voltage.
A detail adds a minor complication for Boolean functions: because of the way electronic circuits work, it takes fewer transistors to provide the inverse of each function.
Thus, most digital circuits implement the inverse of logical or and logical and: nor (which stands for not or) and nand (which stands for not and). In addition, some circuits use the exclusive or (xor) function. FIG. 4 lists the possible inputs and the results for each function†.
†Some digital circuits use 5 volts and some use 3.3 volts; rather than specify a voltage, hardware engineers write Vdd to denote a voltage appropriate for a given circuit.
FIG. 3 A pair of complementary transistors used to implement a Boolean
not.
FIG. 4 The nand, nor, and xor functions that logic gates provide.
†A later section explains that we use the term truth tables to describe the tables used in the figure.
6. Implementation Of A Nand Logic Gate Using Transistors
For the remainder of the text, the details of transistors and their interconnection are unimportant. All we need to understand is that transistors can be used to create each of the Boolean functions described above, and that the functions are used to create digital circuits that form computers. Before leaving the topic of transistors, we will examine an example: a circuit that uses four transistors to implement a nand function. FIG. 5 contains the circuit diagram. As described above, we use the term logic gate to describe the resulting circuit. In practice, a logic gate contains additional components, such as diodes and resistors, that are used to protect the transistors from electrostatic discharge and excessive electrical current; because they do not affect the logical operation of the gate, the extra components have been omitted from the diagram.
FIG. 5 Example of four transistors interconnected in a circuit that implements
a nand logic gate.
To understand how the circuit operates, observe that if both inputs represent logical one, the bottom two transistors will be turned on, which means the output will be connected to zero volts (logical zero). Otherwise, at least one of the top two transistors will be turned on, and the output will be connected to positive voltage (logical one). Of course, a circuit must be designed carefully to ensure that an output is never connected to positive voltage and zero volts simultaneously (or the transistors will be destroyed).
The diagram in FIG. 5 uses a common convention: two lines that cross do not indicate an electrical connection unless a solid dot appears. The idea is similar to the way vertices and edges are drawn in a graph: two edges that cross do not indicate a vertex is present unless a dot (or circle) is drawn. In a circuit diagram, two lines that cross without a dot correspond to a situation in which there is no physical connection; we can imagine that the wires are positioned so an air gap exists between them (i.e., the wires do not touch). To help indicate that there is no connection, the lines are drawn with a slight space around the crossing point.
Now that we have seen an example of how a gate can be created out of transistors, we do not need to consider individual transistors again. Throughout the rest of the section, we will discuss gates without referring to their internal mechanisms. Later sections discuss larger, more complex mechanisms that are composed of gates.
7. Symbols Used For Logic Gates
When they design circuits, engineers think about interconnecting logic gates rather than interconnecting transistors. Each gate is represented by a symbol, and engineers draw diagrams that show the interconnections among gates. FIG. 6 shows the symbols for nand, nor, inverter, and, or, and xor gates. The figure follows standard terminology by using the term inverter for a gate that performs the Boolean not operation.
FIG. 6 The symbols for commonly used gates. Inputs for each gate are shown
on the left, and the output of the gate is shown on the right.
†The technology limits the number of inputs that can be connected to a single output; we use the term fanout to specify the number of inputs that an output supplies.
8. Example Interconnection Of Gates
The electronic parts that implement gates are classified as Transistor-Transistor Logic (TTL) because the output transistors in each gate are designed to connect directly to input transistors in other gates. In fact, an output can connect to several inputs†. For example, suppose a circuit is needed in which the output is true if a disk is spinning and the user presses a power-down button. Logically, the output is a Boolean and of two inputs. We said, however, that some designs are limited to nand, nor, and inverter gates. In such cases, the and function can be created by directly connecting the output of a nand gate to the input of an inverter. FIG. 7 illustrates the connection.
FIG. 7 Illustration of gate interconnection. The output from one logic
gate can connect directly to the input of another gate.
As another example of gate interconnection, consider the circuit in FIG. 8 that shows three inputs.
FIG. 8 An example of a circuit with three inputs labeled X, Y, and Z.
Internal interconnections are also labeled to allow us to discuss intermediate values.
What function does the circuit in the figure implement? There are two ways to answer the question: we can determine the Boolean formula to which the circuit corresponds, or we can enumerate the value that appears on each output for all eight possible combinations of input values. To help us understand the two methods, we have labeled each input and each intermediate connection in the circuit as well as the output.
To derive a Boolean formula, observe that input Y is connected directly to an inverter. Thus, the value at A corresponds to the Boolean function not Y. The nor gate takes inputs not Y (from the inverter) and Z, so the value at B corresponds to the Boolean function:
Z nor (not Y)
Because the combination of a nand gate followed by an inverter produces the Boolean and of the two inputs, the output value corresponds to:
X and (Z nor (not Y))
The formula can also be expressed as:
X and not (Z or (not Y)) (eqn. 1)
Although we have described the use of Boolean expressions as a way of under standing circuits, Boolean expressions are also important in circuit design. An engineer can start a design by finding a Boolean expression that describes the desired behavior of a circuit. Writing such an expression can help a designer understand the problem and special cases. Once a correct expression has been found, the engineer can translate the expression into equivalent hardware gates.
The use of Boolean expressions to specify circuits has a significant advantage: a variety of tools are available that operate on Boolean expressions. Tools can be used to analyze an expression, minimize an expression†, and convert an expression into a diagram of interconnected gates. Automated minimization is especially useful because it can reduce the number of gates required. That is, tools exist that can take a Boolean expression as input, produce as output an equivalent expression that requires fewer gates, and then convert the output to a circuit diagram. We can summarize:
Tools exist that take a Boolean expression as input and produce an optimized circuit for the expression as output.
A second technique used to understand a logic circuit consists of enumerating all possible inputs, and then finding the corresponding values at each point in the circuit.
For example, because the circuit in FIG. 8 has three inputs, eight possible combinations of input exist. We use the term truth table to describe the enumeration. Truth tables are often used when debugging circuits. FIG. 9 contains the truth table for the circuit in FIG. 8. The table lists all possible combination of inputs on wires X, Y, and Z along with the resulting values on the wires labeled A, B, C, and output.
FIG. 9 A truth table for the circuit in FIG. 8.
†Google lists a set of rules used to minimize Boolean expressions.
The table in FIG. 9 is generated by starting with all possible inputs, and then filling in the remaining columns one at a time. In the example, there are three inputs (X, Y, and Z) that can each be set to zero or one. Consequently, there are eight possible combinations of values in columns X, Y, and Z of the table. Once they have been filled in, the input columns can be used to derive other columns. For example, point A in the circuit represents the output from the first inverter, which is the inverse of input Y.
Thus, column A can be filled in by reversing the values in column Y. Similarly, column B represents the nor of columns A and Z.
A truth table can be used to validate a Boolean expression -- the expression can be computed for all possible inputs and compared to the values in the truth table. For ex ample, the truth table in FIG. 9 can be used to validate the Boolean expression (2.1) above and the equivalent expression:
X and Y and (not Z))
To perform the validation, one computes the value of the Boolean expression for all possible combinations of X, Y, and Z. For each combination, the value of the expression is compared to the value in the output column of the truth table.
9. A Digital Circuit For Binary Addition
How can logic circuits implement integer arithmetic? As an example, consider using gates to add two binary numbers. One can apply the technique learned in elementary school: align the two numbers in a column. Then, start with the least-significant digits and add each column of digits. If the sum overflows a given column, carry the high-order digit of the sum to the next column. The only difference is that computers represent integers in binary rather than decimal. For example, FIG. 10 illustrates the addition of 20 and 29 carried out in binary.
FIG. 10 Example of binary addition using carry bits.
A circuit to perform the addition needs one module for each column (i.e., each bit in the operands). The module for the low-order bits takes two inputs and produces two outputs: a sum bit and a carry bit. The circuit, which is known as a half adder, contains an and gate and an exclusive or gate. FIG. 11 shows how the gates are connected.
FIG. 11 A half adder circuit that computes the sum and carry for two in
put bits.
Although a half adder circuit computes the low-order bit of the sum, a more complex circuit is needed for each of the other bits. In particular, each successive computation has three inputs: two input bits plus a carry bit from the column to the right. FIG. 12 illustrates the necessary circuit, which is known as a full adder. Note the symmetry between the two input bits -- either input can be connected to the sum of the circuit for the previous bit.
FIG. 12 A full adder circuit that accepts a carry input as well as two
in put bits.
As the figure shows, a full adder consists of two half adder circuits plus one extra gate (a logical or). The or connects the carry outputs from the two half adders, and provides a carry output if either of the two half adders reports a carry.
Although a full adder can have eight possible input combinations, we only need to consider six when verifying correctness. To see why, observe that the full adder treats bit 1 and bit 2 symmetrically. Thus, we only need to consider three cases: both input bits are zeros, both input bits are ones, and one of the input bits is one while the other is zero. The presence of a carry input doubles the number of possibilities to six. An exercise suggests using a truth table to verify that the full adder circuit does indeed give correct output for each input combination.
10. Multiple Gates Per Integrated Circuit
Because the logic gates described above do not require many transistors, multiple gates that use TTL can be manufactured on a single, inexpensive electronic component.
One popular set of TTL components that implement logic gates is known as the 7400 family†; each component in the family is assigned a part number that begins with 74.
Physically, many of the parts in the 7400 family consist of a rectangular package approximately one-half inch long with fourteen copper wires (called pins) that are used to connect the part to a circuit; the result is known as a 14-pin Dual In-line Package (14 pin DIP). More complex 7400-series chips require additional pins (e.g., some use a 16-pin DIP configuration).
To understand how multiple gates are arranged on a 7400-series chip, consider three examples. Part number 7400 contains four nand gates, part number 7402 contains four nor gates, and part number 7404 contains six inverters. FIG. 13 illustrates how the inputs and outputs of individual logic gates connect to pins in each case.
FIG. 13 Illustration of the pin connections on three commercially available
integrated circuits that implement logic gates.
Although the figure does not show gates connected to pins 14 and 7, the two pins are essential because they supply power needed to run the gates -- as the labels indicate, pin 14 connects to plus five volts and pin 7 connects to ground (zero volts).
†In addition to the logic gates described in this section, the 7400 family also includes more sophisticated mechanisms, such as flip-flops, counters, and demultiplexors, that are described later in the section.
11. The Need For More Than Combinatorial Circuits
An interconnection of Boolean logic gates, such as the circuits described above, is known as a combinatorial circuit because the output is simply a Boolean combination of input values. In a combinatorial circuit, the output only changes when an input value changes. Although combinatorial circuits are essential, they are not sufficient -- a computer requires circuits that can take action without waiting for inputs to change. For ex ample, when a user presses a button to power on a computer, hardware must perform a sequence of operations, and the sequence must proceed without further input from the user. In fact, a user does not need to hold the power button continuously -- the startup sequence continues even after the user releases the button. Furthermore, pressing the same button again causes the hardware to initiate a shutdown sequence.
How can a power button act to power down as well as power up a system? How can digital logic perform a sequence of operations without requiring the input values to change? How can a digital circuit continue to operate after an input reverts to its initial condition? The answers involve additional mechanisms. Sophisticated arrangements of logic gates can provide some of the needed functionality. The rest requires a hardware device known as a clock. The next sections present examples of sophisticated circuits, and later sections explain clocks.
12. Circuits That Maintain State
In addition to electronic parts that contain basic Boolean gates, parts are also avail able that contain gates interconnected to maintain state. That is, electronic circuits exist in which the outputs are a function of the sequence of previous inputs as well as the current input. Such logic circuits are known as sequential circuits.
A latch is one of the most basic of sequential circuits. The idea of a latch is straightforward: a latch has an input and an output. In addition, a latch has an extra in put called an enable line. As long as the enable line is set to logical one, the latch makes its output an exact copy of the input. That is, while the enable line is one, if the input changes, the output changes as well. Once the enable line changes to logical zero, however, the output freezes at its current value and does not change. Thus, the latch "remembers" the value the input had while the enable line was set, and keeps the output set to that value.
How can a latch be devised? Interestingly, a combination of Boolean logic gates is sufficient. FIG. 14 illustrates a circuit that uses four nand gates to create a latch.
The idea is that when the enable line is logical zero, the two nand gates on the right remember the current value of the output. Because the outputs of two nand gates feed back into each other's input, the output value will remain stable. When the enable line is logical one, the two gates on the left pass the data input (on the lower wire) and its inverse (on the higher wire) to the pair of gates on the right.
FIG. 14 Illustration of four nand gates used to implement a one-bit latch.
13. Propagation Delay
To understand the operation of a latch, one must know that each gate has a propagation delay. That is, a delay occurs between the time an input changes and the output changes. During the propagation delay, the output remains at the previous value. Of course, transistors are designed to minimize delay, and the delay can be less than a microsecond, but a finite delay exists. To see how propagation delay affects circuits, consider the circuit in FIG. 15.
FIG. 15 An inverter with the output connected back to the input.
As the figure shows, the output of an inverter is connected back to the input. It does not seem that such a connection makes sense because an inverter's output is al ways the opposite of its input. The Boolean expression for such a circuit is:
output = not(output)
which is a mathematical contradiction.
Propagation delay explains that the circuit works. At any time, if output is 0, the input to the inverter will be 0. After a propagation delay, the inverter will change the output to 1. Once the output becomes 1, another propagation delay occurs, and the out put will become 0 again. Because the cycle goes on forever, we say that the circuit oscillates by generating an output that changes back and forth between 0 and 1 (known as a square wave). The concept of propagation delay explains the operation of the latch in FIG. 14 -- outputs remain the same until a propagation delay occurs.
14. Using Latches To Create A Memory
We will see that processors include a set of registers that serve as short-term storage units. Typically, registers hold values that are used in computation (e.g., two values that will be added together). Each register holds multiple bits; most computers have 32-bit or 64-bit registers. The circuit for a register illustrates an important principle of digital hardware design:
A circuit to handle multiple bits is constructed by physically replicating a circuit that handles one bit.
FIG. 16 A 4-bit register formed from four 1-bit latches.
To understand the principle, consider FIG. 16 which shows how a 4-bit register circuit can be constructed from four 1-bit latches†. In the figure, the enable lines of all four latches are connected together to form an enable input for the register. Although the hardware consists of four independent circuits, connecting the enable lines means the four latches act in unison. When the enable line is set to logical one, the register accepts the four input bits and sets the four outputs accordingly. When the enable line be comes zero, the outputs remain fixed. That is, the register has stored whatever value was present on its inputs, and the output value will not change until the enable line be comes one again.
The point is:
A register, one of the key components in a processor, is a hardware mechanism that uses a set of latches to store a digital value.
15. Flip-Flops And Transition Diagrams
A flip-flop is another circuit in which the output depends on previous inputs as well as the current input. There are various forms. One form acts exactly like the power switch on a computer: the first time its input becomes 1, the flip-flop turns the output on, and the second time the input becomes 1, the flip-flop turns the output off.
Like a push-button switch used to control power, a flip-flop does not respond to a continuous input -- the input must return to 0 before a value of 1 will cause the flip-flop to change state. That is, whenever the input transitions from 0 to 1, the flip-flop changes its output from the current state to the opposite. FIG. 17 shows a sequence of inputs and the resulting output.
†Although the diagram only shows a 4-bit register, the registers used in typical processors store 32 bits or 64 bits.
FIG. 17 Illustration of how one type of flip-flop reacts to a sequence
of inputs. The flip-flop output changes when the input transitions from 0 to 1 (i.e., from zero volts to five volts).
Because it responds to a sequence of inputs, a flip-flop is not a simple combinatorial circuit. A flip-flop cannot be constructed from a single gate. However, a flip flop can be constructed from a pair of latches.
To understand how a flip-flop works, it is helpful to plot the input and output in graphical form as a function of time. Engineers use the term transition diagram for such a plot. In most digital circuits, transitions are coordinated by a clock, which means that transitions only occur at regular intervals. FIG. 18 illustrates a transition diagram for the flip-flop values from FIG. 17. The line labeled clock in FIG. 18 shows where clock pulses occur; each input transition is constrained to occur on one of the clock pulses. For now, it is sufficient to understand the general concept; later sections explain clocks.
FIG. 18 Illustration of a transition diagram that shows how a flip flop
reacts to the series of inputs in FIG. 17. Marks along the x axis indicate
times; each corresponds to one clock tick.
We said that a flip-flop changes output each time it encounters a one bit. In fact, the transition diagram shows the exact details and timing that are important to circuit designers. In the example, the transition diagram shows that the flip-flop is only triggered when the input rises. That is, the output does not change until the input transitions from zero to one. Engineers say that the output transition occurs on the rising edge of the input change; circuits that transition when the input changes from one to zero are said to occur on the falling edge.
In practice, additional details complicate flip-flops. For example, most flip-flops include an additional input named reset that places the output in a 0 state. In addition, several other variants of flip-flops exist. For example, some flip-flops provide a second output that is the inverse of the main output (in some circuits, having the inverse avail able results in fewer gates). NEXT>>
Related Articles -- Top of Page -- Home