Skip to main content
Workforce LibreTexts

Part 2

  • Page ID
    3750
  • 1

    1

    0

    0

    1

    1

    1

    1

    1

    1

    0

    Figure 4-3 Truth table for AND and OR

    In this text, the AND operator will be shown by the * symbol (A*B) , and the OR operator by the + symbol (A+B) . The * is often dropped, as in algebra (e.g. A*B will be written AB).

    index-53_1.jpg

    index-53_2.jpg

    DIGITAL CIRCUIT PROJECTS

    49

    Unless it makes sense to do otherwise, this text will include the * include the operator in expressions.

    One last Boolean function which is important for many of the circuits in this text is the exclusive-or (XOR). An XOR function is important in that in can often reduce the size of many circuits. The symbol for the XOR is ⊕, so A⊕B means A XOR B. The XOR is often called an odd function, in that it is true (1) when there is an odd number of inputs to the function which are 1, and false when there is an even number of inputs to the function which are 1.

    Symbols for the AND, OR, and XOR gates are shown in Figure 4-5.

    Figure 4-4: AND, OR, and XOR gates

    A circuit implementing the AND, OR, and XOR gates in Logisim is shown in Figure 4-5.

    Figure 4-5: AND, OR, and XOR gate circuit

    4.5 Implementing the AND gate circuit

    This section will cover how to implement the AND gate circuit. This circuit will add a new component to the circuit, a 7408 (AND) chip to implement the AND gate. A brief overview of the 7408 chip will be given here.

    4.5.1 ICs and the 7408 chip

    Figures 4-5 and 4-6 are pictures of 7408 chips. There are a large number of manufactures of chips, and realtors will usually sell chips from several different manufactures. While the chips themselves are standard in their implementation and packaging, details such as the labeling are not. All chips are labeled on the top of the chip, though the labeling is not consistent. Some labels are easy to read, but often the labels require the user to move the chip around under a bright light to see the labeling. Other types of manufacturer specific information will be on the

    index-54_1.jpg

    index-54_2.jpg

    50

    DIGITAL CIRCUIT PROJECTS

    chip, and this will vary from manufacturer to manufacturer. But somewhere on the chip will be a designation of the chip type. This designation will follow the format of 74tttsss, as explained in section 1.2

    Every chip some number of sharp legs, called pins, which are designed to be inserted into the breadboard. Each pin has a specific use. For the 7408 chip these pins will be explained in the next section. Be careful when inserting and removing these chips, as these pins are delicate and easily bend and break.

    Figure 4-6: 7408 chip, circle indicates top of chip.

    Figure 4-7: 7408 chip, notch indicates top of chip.

    4.5.2 The datasheet

    Every IC chip comes with a datasheet which explains the setup of the chip. The datasheet contains a lot of useful information to engineers looking to use these chips, much of it beyond the scope of this text. One diagram that is always available in the datasheet is the pin configuration, and example for the 7408 chip shown in Figure 4-7 below.

    The pin configuration diagram contains several items. The first is the orientation of the chip. At the top of every chip is a circle or notch, shown in Figures 4-6 and 4-7 respectively. It is important to carefully note the top of the chip, as inserting the chip upside down is a common mistake. When this happens, generally the VCC and GND wires are reversed, and the chip

    index-55_1.jpg

    DIGITAL CIRCUIT PROJECTS

    51

    becomes hot very quickly. It is always a good idea to check the powering of the chip when it is place on the board to make sure it is not getting hot.

    Next the pin configuration diagram shows the input and output values for the pins on the chip.

    As shown in Figure 4-8, there are 4 AND gates on this chip. Pins 1 and 2 are inputs to an AND

    gate which has output on pin 3. Likewise pins 4 and 5 connect to pin 6, etc.

    Figure 4-8: 7408 pin configuration diagram

    There are two pins which are not connected to any gates, labeled VCC and GND. All chips must be powered to work. The VCC and GND are known as the power supply pins. These are the pins which are connected to the positive and negative rails to provide power to the circuit. As can be seen in Figure 4-9 the VCC (pin 14) is connected to the positive (red) rail using a red wire, and GND (pin 7) is connected to the ground (blue) rail using a black wire.

    We are now ready to implement the circuit to implement a single AND gate to turn on a LED.

    4.5.3 Creating the AND circuit

    This section covers how to implement a circuit using an AND chip. The steps correspond to the picture in Figure 4-7.

    1. Insert a second switch on the right hand side of the breadboard, and wire it just like the switch installed in Chapter 3. The right hand side of the breadboard should have been powered as part of the original circuit in Chapter 3.

    2. Carefully insert the 7408 (AND gate) chip onto the breadboard, being careful not to bend the pins on the chip. The chip is placed so that it crosses the middle of the board. Make sure that the circle or notch is at the top of the circuit, as in Figure 4-9.

    3. Provide power to the chip by connecting pin 14 to the positive rail.

    index-56_1.jpg

    52

    DIGITAL CIRCUIT PROJECTS

    4. Ground the chip by connecting pin 7 to the ground rail.

    5. Connect the input pins 1 and 2 to the inputs from the two switches.

    6. Connect the output pin 3 to the LED.

    If everything is connected correctly, the circuit will implement an AND gate with the input coming from the two switches.

    Figure 4-9: 7408 AND gate circuit

    4.6 Exercises

    1. Draw the symbols for the NAND, NOR, XOR, and XNOR gates. What is the difference between the Buffer, AND, OR, XOR and the NOT, NAND, NOR, and XNOR gates?

    2. Implement the AND chip circuit show in Figure 4-9. Show by various combinations of the switches that the circuit matches the AND gate truth-table.

    3. Modify the circuit from question 2 to use a second AND gate on the chip. You should use the same input switches on the circuit, so the resulting lighting of the LED should be the same.

    4. Remove the AND chip from the circuit in Exercise 3, and replace it with the OR chip.

    Show that the circuit matches the OR gate truth-table. Try other chips (NAND, XOR,

    DIGITAL CIRCUIT PROJECTS

    53

    etc) that you have from the lab kit.

    5. There are 16 possible combinations of output given 2 inputs. These 16 combinations are given in the following table. Use Logisim to identify the NAND, NOR, XOR and XNOR operators. See how many of the others you can name. The AND and OR are entered in the table for you.

    Input

    Output

    A

    B

    AND

    OR

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    1

    1

    1

    1

    1

    1

    1

    1

    0

    1

    0

    0

    0

    0

    1

    1

    1

    1

    0

    0

    0

    0

    1

    1

    1

    1

    1

    0

    0

    0

    1

    1

    0

    0

    1

    1

    0

    0

    1

    1

    0

    0

    1

    1

    1

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    54

    DIGITAL CIRCUIT PROJECTS

    index-59_1.jpg

    DIGITAL CIRCUIT PROJECTS

    55

    Chapter 5 Associative Boolean operators

    5.1 Introduction

    This chapter looks at which Boolean operators are associative. Associative operations allow arbitrary groupings of the operations. For example, addition is associative. We can show this with the following two equations, which are equal:

    x = (2 + (3 + (4+5))) = 14

    x = (2 + 3) + (4 + 5) = 14

    Subtraction is not associate, as can be seen in the equations below:

    x = (2 - (3 - (4 - 5))) = -2

    x = ((2 - 3) - (4 - 5)) = 0

    These examples show that subtraction is not associative, and while they do not prove that addition is associative, they are illustrative that addition is associative at least for this example.

    The proof that addition is associative is not really of interest in this text, and can easily be found in an online search.

    Like arithmetic operators, Boolean operators can also be associative, commutative, and distributive. This chapter will create circuits which will demonstrate the associative property for Boolean operators. The exercises at the end of the chapter allow the reader to further explore these properties.

    5.2 Modeling associative operations in Logisim

    To demonstrate which Boolean operators are associative, the first step is to write equations for each operator which implement two associative ways to implement an expression, and see if the results are equivalent or not. A first equation for the AND operation could be the following: (((A * B) * C)*D). In this equation, the results of the output from each AND gate serially feeds the inputs to the AND next gate, where it is matched with the next input. This is shown in Figure 5-1 below:

    Figure 5-1: Serial AND circuit

    A second equation, (A * B) * (C * D), does the first two AND operations in parallel, and then combines the results, as shown in Figure 5-2 below:

    index-60_1.jpg

    56

    DIGITAL CIRCUIT PROJECTS

    Figure 5-2: Parallel AND circuit

    These two circuits can be implemented in Logisim, and the results used to fill in the table for Exercise 1 in Section 5.5. This will show that for these two equations, the AND operator is associative. Changing the Boolean operator by inserting a different gate will give results for the rest of the table.

    5.3 Implementing the circuit

    The two expressions given above will now be implemented in a breadboard circuit to confirm that they are indeed associative. This exercise also serves to show how to implement circuits which require cascading of outputs from one gate to another in a circuit, and to better see how the circuit diagrams from Logisim can be translated into circuits implementations.

    5.3.1 Implementing the serial AND circuit

    The serial AND circuit from Figure 5-1 is implemented in Figure 5-4 below. Step by step instructions for implementing this circuit follow, and the numbers correspond to numbers in the picture of the circuit in Figure 5-4. You should start with a circuit with the powered 7408 chip on the breadboard from Chapter 3 (pins 7 and 14 connected to ground and positive respectfully).

    The pin layout schematic from Figure 4-6 is repeated here as Figure 5-3 for ease of reference in the steps below.

    0. This circuit requires 4 inputs, labeled A, B, C, and D. Install 4 switches just as in Chapter 3, and as shown in Figure 5-4.

    1. Install and power the 7408 chip (quad AND gate).

    2. The first two switches, A and B, form the inputs to the first AND gate (pins 1 and 2 ).

    The output is on pin 3 is the result of A*B.

    3. The output from the first AND gate (pin 3) is the input to the third AND gate (pins 13).

    This is done by connecting pin 3 to pin 13.

    4. Connect the switch C to the second input to the third AND gate (pin 12 ). The output from this AND gate, on pin 11, is ((A*B)*C).

    5. Connect the output from the third AND gate, pin 11, to the fourth AND gate by connecting pin 11 to pin 10. Note that in the picture this connection is a bare wire, and might be hard to see.

    6. Connect the second input to the fourth AND gate by connecting switch D to pin 9. The output of the third AND gate, pin 8, is (((A*B)*C)*D).

    7. The final output of the circuit is the output of the fourth AND gate on pin 8. Connect pin 8 to the led. When all 4 switches are turned on, the LED should light.

    index-61_1.jpg

    index-61_2.jpg

    DIGITAL CIRCUIT PROJECTS

    57

    Figure 5-3: 7408 pin configuration diagram

    When this is completed, your circuit should light the LED only when all 4 switches are in the on position.

    Figure 5-4: Serial AND implementation

    index-62_1.jpg

    58

    DIGITAL CIRCUIT PROJECTS

    5.3.2 Implementing the parallel AND circuit

    The parallel AND circuit shown in Figure 5-2 is implemented in Figure 5-5. This circuit is created from the serial circuit in Figure 5.4 by making the following modifications.

    1. Move switch D so that it is now input to the second AND gate, pin 13.

    2. Move the output from the first AND gate so that it is now input to third AND gate, pin 9.

    This circuit should produce the exact same output as the circuit in section 5.4.1, e.g. the LED

    should turn on when all of the switches are turned on.

    Figure 5-5: Parallel AND implementation

    5.4 Conclusion

    Like arithmetic operators, Boolean operators can be associative, commutative, and distributive.

    These properties affect the way that circuits are implemented, and the effects can be seen when building larger circuits.

    5.5 Exercises

    1. Implement the circuits in Figures 5-4 and 5-5.

    DIGITAL CIRCUIT PROJECTS

    59

    2. Completing the following table by implementing circuits in Logisim for the operations AND, OR, XOR, NAND, and NOR. Which operations appear to be associative?

    The output columns for the table below are defined as follows (the XOR operator is ^, and NOT is !, which is consistent with Java):

    As = (A*(B*(C*D)))

    Xs = (A^(B^(C^ D)))

    NOs = !(A+!(B+!(C+D))

    Ap = (A*B)*(C*D)

    Xp = (A^B)^(C^D)

    NOp = !(!(A+B)+!(C+D))

    Os = (A+(B+(C+D)))

    NAs = !(A*!(B*!(C*D))

    Op = (A+B)+(C+D)

    NAp = !(!(A*B)*!(C*D))

    Input

    Output

    A

    B

    C

    D

    As

    Ap

    Os

    Op

    Xs

    Xp

    NAs NAp NOs NOp

    0

    0

    0

    0

    0

    0

    0

    1

    0

    0

    1

    0

    0

    0

    1

    1

    0

    1

    0

    0

    0

    1

    0

    1

    0

    1

    1

    0

    0

    1

    1

    1

    1

    0

    0

    0

    1

    0

    0

    1

    1

    0

    1

    0

    1

    0

    1

    1

    1

    1

    0

    0

    1

    1

    0

    1

    1

    1

    1

    0

    1

    1

    1

    1

    3. Implement circuits in Logisim that show whether or not the operations AND, OR, XOR, NAND, NOR, and XNOR are commutative. This can be accomplished using circuits with only 3 inputs and 2 operations. Create a table similar to the one in problem 2.

    60

    DIGITAL CIRCUIT PROJECTS

    Which operations appear to be commutative?

    4. Implement two circuits showing the commutative property using your breadboard and chips.

    5. Implement circuits in Logisim that show whether or not the operations AND, OR, XOR, AND, NOR, and XNOR are distributive. This can be accomplished using circuits with only 3 inputs, but one version requires 2 operations and the other 3 operations. Create a table similar to the one in problem 1, except with only 3 inputs, and complete it. Which operations appear to be distributive? Implement the circuits using the breadboard.

    6. Implement two circuits showing the distributive property using your breadboard and chips.

    7. Show, by creating the circuit in Logisim, that a 32-way parallel AND operation can be implemented such that it only can be executed in 5*T time (where T is the time to do a single AND operation). What does this exercise imply about the runtime growth of associative operations when run in parallel? This question is for more advanced students, and assumes some background in data structures and algorithms, but illustrates an important point about parallelizing of associative operations.

    index-65_1.png

    DIGITAL CIRCUIT PROJECTS

    61

    Chapter 6 Adders

    6.1 Introduction

    The material covered up to this point was used to show how to implement circuits. This chapter will cover a circuit that will be used as an IC, and this circuit forms a basic building block of a CPU.

    Addition is the central to all arithmetic operations, and all other arithmetic operations (subtraction, multiplication, and division) can be built using addition. Therefore, addition is central to implementation of the Arithmetic Logic Unit (ALU) in a CPU shown in Figure 6-1.

    This chapter will show how addition of whole numbers using Boolean operations, and how it can be implemented in a circuit.

    Figure 6-1: ALU

    This chapter will first look at how two one-bit binary numbers can be added, which will be implemented using a circuit called the half adder. The need for a carry bit will become apparent when trying to add numbers larger then a single bit, and this will be done using a circuit called a full adder. Full adders will then be chained together to form an n-bit adder, which will be able to perform addition of whole numbers .

    6.2 Half adder

    The circuit presented in this section is called a half adder. A half adder is an adder which adds two binary digits together, resulting in a sum and a carry.

    Why is it called a half adder? Because this adder can only be used to add two binary digits, it cannot form a part of an adder circuit that can add two n-bit binary numbers. The adder circuit which will be used to add n-bit binary numbers is called a full adder. This adder is less than a full adder, and hence it is called a half adder.

    6.2.1 Adding binary numbers

    To understand binary addition, we must remember how we did addition when we first learned it.

    When executing decimal addition for any two digits, the result can have 2 digits. For example 7+6= 13. The first digit (in this case 1) is called the carry (C), and the second digit is called the

    index-66_1.jpg

    62

    DIGITAL CIRCUIT PROJECTS

    sum (C). The purpose of the carry is to be included in the addition of the next digit of the number. For example, to calculate 17 + 26, first the 7+6 operation is performed, and the digit 3

    is moved to the answer. The carry 1 is added to tens digits from 17 and 26 (1+1+2) to give the number 4, and the answer is combined to produce 43.

    Thus the carry digit is carried to the addition in the next digit. So when adding two digits the output from the operation is a sum and a carry. Remember that a carry always produced, even if it is 0. To calculate 14+22, the 4 and 2 are added, resulting in a 6 with a carry of 0. This is important to remember, every addition results in a sum and carry, though the carry can be 0.

    Binary addition for two binary numbers each containing one digit works the same way as decimal addition for two decimal one digit numbers, but is simpler because the two input values can only have 2 states (either 0 or 1). So give two binary inputs to an addition (X and Y) we can summarize the possible results of adding those bits in the following truth table. Note that the added values produce two results, a sum and a carry, both of which are either 0 or 1.

    Input

    Output

    X

    Y

    S

    C

    0

    0

    0

    0

    0

    1

    1

    0

    1

    0

    1

    0

    1

    1

    0

    1

    Figure 6-2: Half adder truth table

    6.2.2 Half adder circuit

    The truth table in Figure 6-2 shows that the outputs S and C are simply binary functions on X

    and Y. Specifically the S output is the result of an XOR operation X⊕Y. The C output is the result of an AND operation, X*Y. This circuit can be designed and implemented in Logisim, as shown in Figure 6-3.

    Figure 6-3: Half adder circuit

    This simple circuit adds two inputs, I0 and I1, and produces a sum and carry. This is the first circuit that we have implemented that has two outputs. This is not a problem. Any number of functions can be applied to a set of input data, and a single set of input data can result in any

    index-67_1.jpg

    DIGITAL CIRCUIT PROJECTS

    63

    number of outputs.

    6.2.3 Half adder implementation

    This section will show how to implement the half-added as a circuit on the breadboard. The circuit has 2 inputs (X and Y), so it will require two switches. The circuit has 2 outputs, thus it has 2 LEDs, one LED for the carry, and one LED for the sum.

    The circuit needs to use two chips since chips can contain multiple gates, but all of the gates on the chip are of the same type. This circuit needs one chip for the XOR gate and one chip for the AND gate. The 2 chips being used are the 7408 AND chip, and the 7486 XOR chip. Both of these chips are quad (4) gate chips, but this circuit will only use one gate on each chip.

    The implementation of the half adder is shown in Figure 6-5, and the following steps refer to that figure.

    0. Place two switches, which will be the X and Y input, on the breadboard, and connect them as in previous labs.

    1. Place the 7486 (XOR gate) chip on the breadboard and power the chip as in previous projects by connecting pin 7 to the ground rail, and pin 14 to the positive rail. The pin configuration for the 7486 chip is given in Figure 6-4.

    Figure 6-4: 7486 pin configuration diagram

    2. Place the 7408 (AND gate) chip on the breadboard and power the as in previous projects

    index-68_1.jpg

    64

    DIGITAL CIRCUIT PROJECTS

    by connecting pin 7 to the ground rail, and pin 14 the positive rail for both chips.

    3. Connect both switch X and Y to the input of the third XOR gate (pins 12 and 13) on the 7486 chip. Connect the output for the XOR gate (pin 11) to the input for the green, or sum, LED.

    Figure 6-5: Half adder implementation

    4. Connect both switch X and Y to the input of the first AND gate (pins 1 and 2) on the 7408 chip. Connect the output for the AND gate (pin 3) to the input for the red, or carry, LED.

    The circuit should now be dark if both switches are off, the green LED should light if only one switch is on, and the red LED should light if both switches are on.

    6.3 Full adder

    As was alluded to earlier, the problem with a half adder is that it does not consider the input carry bit, Cin. To understand Cin, consider the addition problem for two binary numbers in Figure 6-6. In this problem, the result of adding the first digit of the two inputs values is a sum of 1

    with a carry of 1. This carry of 1 must be considered when adding the next digit of the two input numbers. So the carry from each preceding digit must be included in the calculation of the result when adding binary numbers, and in effect the carry ripples through the digits of the addition

    index-69_1.jpg

    DIGITAL CIRCUIT PROJECTS

    65

    (hence this type of adder is called a ripple-carry adder).

    Figure 6-6: Addition problem showing a carry bit

    The inclusion of the carry bit means that an adder for a single digit in a binary addition requires 3

    inputs, the binary digit from the X and Y values being added, and the carry-out (Cout) from the addition of the preceding digit, which is the carry-in ( Cin)to this digit. The circuit that implements this addition is called a full adder circuit. The truth table which implements a full adder is given in the table below.

    Input

    Output

    X

    Y

    Cin

    S

    Cout

    0

    0

    0

    0

    0

    0

    0

    1

    1

    0

    0

    1

    0

    1

    0

    0

    1

    1

    0

    1

    1

    0

    0

    1

    0

    1

    0

    1

    0

    1

    1

    1

    0

    0

    1

    1

    1

    1

    1

    1

    Figure 6-7: Full adder truth table

    6.3.1 Full adder circuit

    The implementation details of the full adder are not as obvious as the half adder. There are still two output functions, S and Cout, but how to implement these functions is more complex. The first function, S, can be implemented by remembering that the XOR function is an odd function, that is the XOR result is 1 when an odd number of input bits is 1. Thus S=X⊕Y⊕Cin.

    is implemented with two cascading XOR gates.

    The Cout function can be implemented by realizing that it is true if both the X and Y values are true, or if either the X or Y value is true and the Cin is true, or

    index-70_1.jpg

    66

    DIGITAL CIRCUIT PROJECTS

    Cout = (X*Y) + ((X⊕Y)*Cin)

    Using these two functions for C and S, the circuit for the full adder can be represented in Logisim as the following diagram.

    Figure 6-8: Full adder circuit

    6.3.2 Full adder implementation

    The implementation of the full adder is by far the most complex circuit we have implemented up to this time. So while neatness when implementing a circuit always counts, it is now important to be very careful to consider not only how the circuit is implemented, but what gates on the chips to use and how to make the connections. A haphazard implementation of the circuit will become very messy and hard to understand, implement, and debug.

    1. Begin by installing and powering 3 switches. The first two switches will be the X and Y

    values for the circuit, and the third switch will be the Cin value to the circuit. Note the order of the switches is different than for the half adder. This circuit is somewhat complex, and so the placement of the switches is designed to keep the rest of the circuit as simple as possible.

    2. This circuit requires 3 types of gates, so 3 chips must be used. Install the 7486 (XOR) chip on the board, and power it as before.

    3. Install the 7408 (AND) chip on the board and power it.

    4. Install the 7432 (OR) chip on the board and power it. It is suggested that these chips be placed on the board in this order, as this is the order they will be accessed in the circuit.

    Any other placement of the chips will require wires to be run both forward and backward in this circuit, which will eventually be confusing.

    5. Once the chips have been installed on the board, wire the XOR gates. Wire the X and Y

    switches to pins 1 and 2 (first XOR gate) on the left side of the 7486 chip. The output of the XOR gate will be on pin 3.

    index-71_1.jpg

    DIGITAL CIRCUIT PROJECTS

    67

    Note a couple of things about this gate. First the X and Y input wires are connected to the input pins, but are also connected to wires which send their values on to the AND gate in step 7.

    Note also that the output on pin 3 is sent forward to two places: the input of the third XOR gate, and to the input of the second AND gate.

    Finally note that the circuit has been designed to attempt to keep the wires used in the S

    output on the right of the board, and the wires used in the C output on the left side of the board.

    Figure 6-9: Full adder implementation

    6. Wire the output from the first XOR gate (pin 3 on the 7486 chip) and the Cin switch to the third XOR gate on the right side of the board, using pins 12 and 13 on the 7486 chip. The output from this XOR gate, pin 11 on the 7486 chip, will be the S output from the circuit, so connect this to the S LED.

    Note that the Cin input on pin 12 will be forwarded to an input on the second AND gate, similar to what was done in step 5.

    index-72_1.jpg

    68

    DIGITAL CIRCUIT PROJECTS

    7. Wire the X and Y inputs, forwarded from pins 1 and 2 on the 7486 XOR chip, to the first AND gate, pins 1 and 2, on the left side of the 7408 chip. The output of this AND gate will be on pin 3, and sent to the input for the first OR gate.

    8. Wire the output of the first XOR gate, pin 3 on the 7486, to the input of the second AND

    gate, pin 4, on the left side of the 7408 chip. Wire the Cin , forwarded from pin 12 on the 7486 chip, to the second input for this AND gate, pin 5 on the 7408 chip. The output fro this AND gate will be on pin 6.

    9. Connect the output of the first AND gate, pin 3 on the 7408 chip, to the first input on the OR gate, pin 1, on the 7432 chip. Connect the output on the second AND gate, pin 6 on the 7408 chip, to the second input, pin 2, on the 7432 chip. The output from the OR gate, pin 3 on the 7432, is the Cout output for the circuit. Wire this output to the C LED.

    The circuit should implement the full adder behavior. If all switches are off, the circuit will be dark; if two or more switches are on, the C output will be on; finally if an odd number of switches are on the S output will be on. If all 3 switches are on, both the C and S LEDs will be on.

    6.4 2-bit adder circuit

    The full adder forms the basis for all arithmetic in a CPU. To illustrate this, a 2-bit adder is represented in Logisim in the Figure 6.6. This adder is implemented by using two instances of the 1-bit adder, and connecting the Cout from the first adder to the Cin of the second adder The adder shown below is adding X=112 (310) plus Y = 012(110), resulting in1002 (410), as expected.

    To create a n-bit adder (or example, a 32 bit adder used in many modern CPUs), 32 full adders can be wired together in a series, with the Cout of each bit being connected to the Cin of the next bit.

    Figure 6-10: 2 bit full adder circuit

    DIGITAL CIRCUIT PROJECTS

    69

    6.5 Conclusion

    The adder forms the basis for all of the arithmetic functions in the ALU. Subtraction, multiplication, and division all are implemented using algorithms which are based on the adder.

    The adder is therefore a stand in for all of the other types of functions performed by the ALU.

    Despite the appearance that addition is more complex, it can be implemented as a Boolean function consisting only of AND, OR, and XOR gates. These simple Boolean functions are implemented in circuits called half adders and full adders. It is when these functions are chained together so that the carry from each previous function is used in the next function that the adder can add larger numbers.

    The implementation of the full adder circuit is more complex than the other circuits which have been looked at so far. It required 3 different chips, 2 outputs, and 5 gates that had to be connected. This circuit required some degree of carefulness and forethought to implement and debug it.

    The adder was the first circuit implemented in this text that is a component, and it has been encapsulated as an IC. The 7482 (2-bit binary full adder) and 7483 (4-bit binary full adder) IC

    chips are implementations of this circuit.

    6.6 Exercises

    1. Implement the half adder circuit on the breadboard.

    2. Implement the full adder circuit on the breadboard.

    3. Using the 2-bit adder presented in the chapter as a model, implement a 4-bit adder in Logisim. Implement an 8 bit adder.

    70

    DIGITAL CIRCUIT PROJECTS

    index-75_1.jpg

    DIGITAL CIRCUIT PROJECTS

    71

    Chapter 7 Decoders

    7.1 Introduction

    Decoders are circuits which break an n-bit input into 2n individual output lines. For example, a decoder could break down 2 bit operations code into 4 separate operations. The operation code tells the CPU which operations to run. A 2 bit operation code is summarized in the following table. Here the code 00 corresponds to the operation ADD, 01 corresponds, to SUB, etc.

    Code

    Operation

    00

    ADD

    01

    SUB

    10

    MUL

    11

    DIV

    Figure 7-1: Control lines for ALU

    The Control Unit (CU) of the CPU would break the binary number down so that each operation would match exactly one control line. This is called a 2-to-4 decoder since 2 input bits are converted into 4 output lines. A schematic of the decoder to implement this CU is shown in the figure below.

    Figure 7-2: Decoder used to set ALU control lines

    Most CPUs support instruction sets that are much larger than simply ADD/SUB/MUL/DIV, and thus a 2-to-4 decoder is not that common, however the principals used to create a 2-to-4 decoder are the same even as the size of the decoder becomes larger. This chapter will only look at the 2-to-4 decoder. Larger decoders will be considered in the exercises at the end of the chapter.

    7.2 Decoder circuit

    The implementation of a decoder is based on the idea that all possible combinations of output from a given set of inputs can be generated by using AND operations on combinations of the input and inverted input bits. For example, for the two bits A and B all of the possible combinations of the bits are 00, 01, 10, and 11, or A'B', A'B, AB', and AB.

    index-76_1.jpg

    72

    DIGITAL CIRCUIT PROJECTS

    Consider the decoder in Figure 7-2, which has two inputs and 4 outputs. The implementation of this decoder is given in Figure 7-3. There are 2 inputs lines which are split into 4 lines, 2 normal and 2 inverted. These 4 lines are sent to 4 AND gates, each AND gate producing an output for one and only one value from the 2 input lines.

    Figure 7-3: Decoder circuit

    This shows a decoder is a circuit which enumerates all the values from the input bits by splitting them into separate output lines. A 3-to-8 decoder would have 3 input bits which would use AND

    and NOT gates to produce 8 output (000, 001, 010, 011, 100, 101, 110, and 111). The implementation of a 3-to-8 decoder is left as an exercise.

    7.3 2-to-4 decoder implementation

    The 2-to-4 decoder will need to use two switches, four LEDs, a 7404 (inverter) chip and a 7408

    (AND) chip. The input will come from two switches. The following steps refer to Figure 7-5.

    0. Install switches A and B, as well as the output LEDs AB, AB', A'B, and A'B'.

    1. Install and power the 7404 (NOT) chip. The pin configuration diagram for this chip is shown in Figure 7-4. Note that the gates on these chips have only a single input for each output, so there are 6 NOT gates on the chip.

    index-77_1.jpg

    DIGITAL CIRCUIT PROJECTS

    73

    Figure 7-4: 7404 pin configuration diagram

    2. Install and power the 7408 (AND) chip.

    3. Connect a wire from switch A to the first NOT gate, pin 1, on the 7404 chip. The output for this NOT gate is on pin 2

    4. Connect a wire from switch B to the third NOT gate, pin 5, on the 7404 chip. The output for this NOT gate is on pin 6. The third gate is used to make some separation for the wires. The second NOT gate (pin 3 input and 4 output), or indeed any two NOT gates on the chip can be used. Note that the input on pin 5 is also sent to step 8, and the output from pin 6 is sent to two separate gates in steps 6 and 7.

    5. Connect the two outputs from the NOT gates, pins 2 and 6 on the 7404 chip, to the third AND gate on the 7808 chip, pins 12 and 13. Connect the output from this AND gate, pin 11, to the A'B' LED. Note that the input on pin 13 is forwarded and to step 6.

    6. Connect switch B and the A’ output (forwarded from pin 13 in step 5), to the fourth AND

    gate on the 7808 chip, pins 9 and 10. Connect the output from this AND gate, pin 8, to the A'B LED.

    7. Connect switch A and the B' output, pin 6 on the 7404 chip, to the first AND gate on the 7408 chip, pins 1 and 2. Connect the output of this AND gate, pin 3, to the AB’ LED.

    Note that the A input is also connected forward to the next gate. Note that the input on pin1 from switch A is also sent on to step 8.

    8. Connect switch A (from pin 1 in step 7) and switch B (from pin 5 in step 4) to the second AND gate, pins 4 and 5, on the 7408 chip. Connect the output of this AND gate, pin 6, to the AB LED. Note that the A switch input to the second AND gate is connected from the first AND gate.

    index-78_1.jpg

    74

    DIGITAL CIRCUIT PROJECTS

    Figure 7-5: Decoder circuit

    The decoder should now work. One light should come on for each of the 4 combinations of switch positions. Keep this circuit intact as it will be used in the multiplexer IC in Chapter 8.

    7.4 Implementing a decoder using a single chip

    A decoder circuit is a commonly used IC, and so it has been implemented in an IC chip. This chip is easier to use than having to produce this entire circuit, so it will be used in chapter 9 to implement a multiplexor. This next section will cover implementing the 74139 decoder chip in a circuit.

    7.4.1 The 74139 chip

    The 74139 chip implements two complete decoders implemented in a single chip. The two decoders are basically on opposite sides of the chip. The difference is that on the left side of the chip the bottom pin, pin 8, is connected to ground rail, and on the right side of the chip the top pin, pin 16, is connected to the positive rail.

    The 74139 chip has an idiosyncrasy that its output is the inverse of the decoder implemented in section 8.2. This means that the selected output line is set to low, and the non-selected lines are

    index-79_1.jpg

    DIGITAL CIRCUIT PROJECTS

    75

    set to high7. So to adjust for this in the implemented circuit the output will be sent to an inverter on a 7404 chip before being sent to the LEDs. This will allow the output to be as it was in section 8.2.

    Figure 7-6 is the pin configuration diagram for the 74139 chip. The two decoders on the chip are numbered 1 and 2. The inputs to the first decoder are 1E', 1A0, and 1A1, and the inputs to the second decoder 2E', 2A0, and 2A1. The values of A0 and A1 are the select lines for each decoder.

    The E' is an enable input low bit. If E' is not enabled (E is positive or not connected), the circuit is basically disconnected, it is neither positive or ground and the results should not be used. If E'

    is enabled (or connected to ground), the circuit is connected. The use of enable bits is to allow power to be reduced in the circuit, and is an engineering concern, and not really of concern to the circuit.

    The outputs from the decoder are labeled 1Y[0-3] and 2Y[0-3]. They are also active low, and the output line which is low is the one which is selected. In the circuit in this section, only the first decoder will be used, and the outputs will be sent to a 7404 inverted to convert the output to the more common positive output expected.

    Figure 7-6: 74139 pin configuration diagram

    7 The reason the output is set low is that the output from a decoder is often ignored unless it is the selected output. This means that positive wires can be ignored and not used. Since the low state uses less electricity and produces less heat than the high state, using a low enable rather than a high enable is an engineering decision to save poser and heat.

    index-80_1.jpg

    76

    DIGITAL CIRCUIT PROJECTS

    7.4.2 Implementing one 2-to-4 decoder using the 74139 chip

    This section will outline how to implement a 2-to-4 decoder using the 74139 decoder chip. To start, remember that the output from the 74139 is enable low, or true when the output is 0. So the output from the chip will have to be sent to a 7404 (NOT), and the circuit will consist of 2 chips.

    To following list of steps implements the decoder circuit using the 74139 chip.

    Figure 7-7: 74139 decoder circuit

    0. Insert switches A and B, and the output LEDs A'B', A'B, AB', and AB.

    1. Insert and power the 74139 decoder chip.

    2. Insert and power the 7404 inverter chip.

    3. Enable output from the first decoder on the 74139 chip by connecting the enable low pin (pin 1) to ground.

    4. Connect the input switch A to pin 3 on the 74139 chip. Connect the input switch B to pin 2 on the 74139 chip.

    5. Connect each output 1I0 to 1I3 to an inverter input as follows:

    a. I0 (pin 3) on the 74139 chip is connected to the fifth inverter (pin 11) on the 7404

    inverter chip.

    b. I1 (pin4) on the 74139 chip is connected to the fourth inverter (pin 13) on the 7404

    inverter chip.

    c. I2 (pin 5) on the 74139 chip is connected to the first inverter (pin 1) on the 7404

    DIGITAL CIRCUIT PROJECTS

    77

    inverter chip.

    d. I3 (pin 6) on the 74139 chip is connected to the second inverter (pin 3) on the 7404

    inverter chip.

    6. Connect the inverter outputs to the correct LEDs:

    a. Connect pin 10 on the 7404 inverter chip to the A'B' LED.

    b. Connect pin 12 on the 7404 inverter chip to the A'B LED.

    c. Connect pin 2 on the 7404 inverter chip to the AB' LED.

    d. Connect pin 4 on the 7404 inverter chip to the AB LED.

    This circuit should now behave like the circuit in section 7.3.

    7.5 Conclusion

    A decoder is an IC which splits an n-bit input value into 2n output lines. A decoder has many uses, but the one presented here is translating a 2-bit input value into 4lines to allow the 4

    different operations of the CPU. The decoder will also be used in the next chapter as part of the multiplexer.

    The decoder works by doing AND operations on all combinations of the input and inverted input values, and then selecting the output using an OR operation on all of the inputs.

    The decoder is a common circuit, so it has been encapsulated in a 74139 chip. The 74139

    contains 2 decoders, and based on the binary input to each decoder, selects the correct output.

    The 74139 chip is different in the enable and all output values are enable low, or selected when the value is low. Therefore to get the behavior we want from the chip, the values must be sent to an inverted (7404) chip to be used.

    7.6 Exercises

    1. Implement the 2-to-4 decoder using 7404 (NOT) an 7808 (AND) chips on your breadboard.

    2. Implement the 2-to-4 decoder circuit with a 74139 chip on your breadboard.

    3. Implement a 1-to-2 decoder in Logisim. Implement this circuit on your breadboard.

    4. Implement a 3-to-8 decoder using NOT and AND gates in Logisim. Show that it is correct by showing it generates the same output as a 3-to-8 Decoder found in the Plexors menu of Logisim.

    5. In Logisim, implement a 3-to-8 decoder using two 2-to-4 decoders, and as many AND gates as you need. Compare the total number of AND gates in the circuit to the number of AND gates used to implement the 3-to-8 decoder with 2-input AND gates in question 4. Which circuit do you think is faster.

    6. Answer the fol owing questions.

    a. How many output lines would a 4 input decoder have?

    b. How many output lines would a 5 input decoder have?

    c. For an N-to-X decoder, specify X as a function of N (e.g. specify the number of output lines as a function of the number of input lines for a decoder).

    78

    DIGITAL CIRCUIT PROJECTS

    index-83_1.png

    DIGITAL CIRCUIT PROJECTS

    79

    Chapter 8 Multiplexers

    8.1 Introduction

    A multiplexer (or MUX) is a selector circuit, having log(N) select lines to choose an output from N input values. In a CPU, multiplexers are used to select the correct memory location values to send to the ALU, as shown below.

    Figure 8-1: Multiplexer as a memory selector

    MUXes have two types of inputs. The first type of input is the values to be selected from. In Figure 9-1 this input is the value contained in each memory location. Every memory location sends its value to both MUXes, the 4 values on the red line to Mux 1, and the 4 values on the green line to Mux 2. Thus both MUXes have all of the values from all memory to select from.

    The second type of input is a set of selection bits which tells the MUX which of the inputs to choose. In Figure 9-1 this input is the two select lines coming from the CU. The two bits on each select line tell each MUX which of the 4 input values to choose.

    The MUX in Figure 9-1 is selecting between n-bit values. The size, in bits, of the data value is called the data width. A data value which can contain the values 0..4 is represented by 2 bits, and so has a data width of 2; a data value which can contain the values 0..16 has a data width of 4; a data value which con contain the values 0..256 has a data width of 8; etc.

    If the memory in Figure 9-1 had a data width of 8, it would select 8 bits from each of 4 inputs, and be called an 8 bit 4-to-1 multiplexer. Thus a MUX has some number of inputs to choose from, and simply forwards one of these inputs to the output.

    The most basic type of MUX, the one on which all larger MUXes are built, is a 1 bit MUX. As will be shown later in this section 8 bit 4-to-1 MUX is made up of eight 1 bit 4-to-1 MUX. So to understand multiplexers a 1 bit 4-to-1 multiplexer will be examined.

    A 1 bit 4-to-1 multiplexer has four 1-bit data inputs values (I0-I3) to choose from. Each bit value I0-I3 can either be 0 or 1. For example, if I0 is selected, the output will be either the value in I0, and either 0 or 1, and the other values of I1, I2, and I3 are simply ignored. The following truth table characterizes this MUX based on the selection bits (S0-S1)

    index-84_1.jpg

    index-84_2.jpg

    80

    DIGITAL CIRCUIT PROJECTS

    :

    Input

    Output

    S1

    S0

    Y

    0

    0

    I0

    0

    1

    I1

    1

    0

    I2

    1

    1

    I3

    Figure 8-2: Truth table for a MUX

    Note that when a line is selected, either a 0 or a 1 will be passed through to Y. The value of input bit is placed on the output value Y. So in the figure below, if S1S0 are 00, Y is 0. If S0S1 are 01, Y is 1, etc..

    Figure 8-3: 1-bit 4-to-1 MUX

    To allow a MUX with a larger data width, multiple MUXes are used. Figure 8-4 shows two 4-to-1 MUXes linked together to choose one 2-bit output from four 2-bit inputs, thus creating a 2 bit 4-to-1 MUX.

    Figure 8-4: 4-to-2 MUX

    index-85_1.jpg

    DIGITAL CIRCUIT PROJECTS

    81

    The concept of linking MUXex in this manner can be expanded to produce a MUX that can have any size data width needed. If want to select an N bits of data (a data width of N), you need N

    MUXes.

    In a CPU the purpose of a MUX is to allow a circuit to select one input from a set of inputs. For example, consider the follow circuit, which implements an adder to add two 8 bit numbers. The first number to be added comes from Memory Set 1, and the second number from Memory Set 2.

    Each set contains four 8-bit values. The MUXes in this circuit choose which item from each Memory Set to use in the addition. For the first set the select bits are set to binary 01, and the second value, binary 00000010, is selected. For the second set the select bits are set to binary 10

    and the third value, binary 01000000, is selected. The two values are added together to produce the answer 01000010.

    Figure 8-5: Two 4-to-8 MUXes

    As this example shows, a MUX allows an input value of any fixed data width to be selected based on the value of select bits. The number of inputs which can be chosen from is 2s, where s is the number of select bits.

    8.2 Circuit Diagram for a MUX

    The truth table in Figure 8-2 characterizes a 4-to-1 MUX.

    Using this truth table, the 4-to-1 MUX can be built using by realizing I0 is only selected when S1S0 are 00, I1 is only selected with S1S0 are 01, etc. So the I0 bit can be sent to an AND gate with the result of the inverted value of S1 and S0. This AND gate will always be 0 except when S1S0

    are 00, when it will be I0. In this manner I1, I2, and I3 can be selected by an AND operation with 01, 10, and 11 respectively.

    Note that only one input value can ever be selected for any value of S0S1. The one input which is sent to an AND gate with 1 will be 0 or 1, based on its input. The result of all of the AND gates

    index-86_1.jpg

    82

    DIGITAL CIRCUIT PROJECTS

    are sent to a 4-way OR gate. Remembering 0 + X is always X, the result of the OR gate will represent the one input selected. It can be 0 or 1, but it will be 0 or 1 based on the value of the selected input.

    The schematic of a MUX is given in the Figure 8-7.

    Figure 8-6: Schematic of a MUX

    An interesting thing about this circuit is that it a decoder is implemented as part of the multiplexer circuit, as shown in the outlined part of Figure 8-6. This suggests another way to implement the MUX using a decoder to select which input line to select. This is shown in Figure 8-7. We will make use of this in designing our implementation of a MUX.

    index-87_1.jpg

    DIGITAL CIRCUIT PROJECTS

    83

    Figure 8-7: Decoder used to implement a MUX

    8.3 Implementing a MUX

    Figure 8-8 shows how to implement a multiplexer circuit on a breadboard using only 7808

    (AND), 7804 (OR) and 7832 (OR) chips. It begins by using the circuit which was implemented in Chapter 7.2.

    The input values to the MUX are "1 0 1 0", as shown in Figure 8-7. These are hard coded values, and implemented in the circuits as direct connections to the positive and ground rails on the breadboard.

    1. Start with the decoder circuit which was implemented in Chapter 7.2

    2. Install a 7408 (AND) chip to the board and power it.

    3. Install a 7432 (OR) chip to the board and power it.

    4. Wire the output from the A'B' gate in the decoder circuit (pin 11 on the 7408 chip labeled 1b) and wire it to the first input on the fourth AND gate (pin 13 on the7408 labeled 2).

    Connect the second input to the AND gate (pin 12 on chip labeled 2)) to a value of 1 by connecting it directly to the positive rail. The output of this AND gate (pin 11 on chip labeled 2) is forwarded to the 7432 (OR) chip.

    5. Wire the output from the A'B gate in the decoder circuit (pin 8 on the 7408 labeled 1b) and wire it to the third AND gate (pin 10 on the7408 chip labeled 2). Connect the second input to the AND gate (pin 9 on chip labeled 2) to a value of 0 by connecting it directly to the ground rail. The output of this AND gate (pin 8 on chip labeled 2) is forwarded to the 7432 (OR) chip.

    6. Wire the output from the AB' gate in the decoder circuit (pin 3 on the 7408 chip labeled 1b) and wire it to the first AND gate (pin 1 on the7408 labeled 2). Connect the second input to the AND gate (pin 2 on the chip labeled 2) to a value of 1 by connecting it

    index-88_1.jpg

    84

    DIGITAL CIRCUIT PROJECTS

    directly to the positive rail. The output of this AND gate (pin 3 on chip labeled 2) is forwarded to the 7432 (OR) chip.

    Figure 8-8: 4-to-1 MUX

    7. Wire the output from the AB gate in the decoder circuit (pin 6 on the 7408 chip labeled 1b) and wire it to the second AND gate (pin 4 on the7408 chip labeled 2). Connect the second input to the AND gate (pin 5 on chip labeled 2) to a value of 0 by connecting it directly to the ground rail. The output of this AND gate (pin 6 on chip labeled 2) is forwarded to the 7432 (OR) chip.

    8. Forward two of the input values from the AND gate (pins 11 and 8 on the 7408 chip) by sending them to the fourth OR gate (pins 12 and 13 on the 7482 chip).

    9. Forward two of the input values from the AND gate (pins 3 and 6 on the 7408 chip) by sending them to the first OR gate (pins 1 and 2 on the 7482 chip).

    index-89_1.jpg

    DIGITAL CIRCUIT PROJECTS

    85

    10. Forward the final output for the MUX by connecting the output of the first and fourth OR

    gate (pins 3 and 11 on the 7432 chip) to the input of the third OR gate (pins 9 and 10 on the 7432 chip). The output of the circuit is from the third OR gate (pin 8 of the 7432

    chip). It is sent to the LED as the output from the MUX.

    The MUX should now light when the switches A and B are in positions A'B' and AB'. The implementation of the MUX can be further tested by changing the input to the MUX by switching the inputs to the MUX, e.g. changing the rail to which pins 2, 5, 9, and 12 are connected.

    8.4 74153 MUX chip

    The MUX is a common circuit, and has been encapsulated into a single chip, the 74153 dual 4-to-1 data selector/multiplexer. This chip implements two multiplexers which share the two select lines. This section will use the 74153 chip to implement a circuit to mirror the input on/off switches. This circuit could easily be implemented by simply connecting the switches directly to the LED, as in Figure 3-11 for one switch and LED. The output is the same as in exercise 3-2.

    The reason this circuit is more interesting than the ones in Chapter 3 is that it shows how a MUX

    can be used to store and retrieve data values, and how those data values can represent a program.

    8.5 74153 circuit diagram

    The diagram for the 74153 input mirroring circuit is shown in Figure 8-10. In this circuit, the LED outputs will match the two input switches.

    Figure 8-9: 74153 circuit diagram

    In this circuit there are two 1 bit 4-to-1 MUXes used. Each MUX has 4 inputs which are addressed by the two select bits at the bottom of the diagram. The select bits retrieve one output bit from each MUX, which are sent to the LEDs. Note that the output from this circuit wil exactly fol ow the input switches, to show which input switch is on. In a real sense, the hard wired input to the two MUXes represent a

    index-90_1.png

    86

    DIGITAL CIRCUIT PROJECTS

    type of sequential logic which is applied to the input to produce the output. We wil use this method of implementing logic using a MUX in Chapter 10.

    8.6 Implementing the 74153 circuit

    Figure 8-12 shows the final implementation of the 74153 input mirroring circuit, as well as indicating the steps to be followed in implementing the circuit. These steps correspond to the numbers in the following list.

    0. Install 2 switches and 2 LEDs.

    1. Install and power the 74153 chip. Figure 8-10 is the 74153pin configuration diagram.

    Most of the pins will be hardwired to values, which will be explained in the following list. Pins which are wired to other components in the circuit are explained in subsequent steps.

    Figure 8-10: 74153 pin configuration diagram

    a. Pins 1 (1E') and 15 (2E') are enable low pins. Enable both multiplexers by connecting these pins to ground.

    b. Pins 3..6 and 10..14 are the input values to the MUX. These are to be programmed as in Figure 8-10. Pins 3..6 are values 0011, and pins 10..14 are 0101. 0 values are connected to the ground rail, 1 values are connected to the positive rail.

    2. Connect the switches to the input select values for the MUXes. Connect Switch 1 to S1

    (pin 2), and Switch 2 to S2 (pin 15).

    3. Connect the output Y values to the LEDs.

    index-91_1.jpg

    DIGITAL CIRCUIT PROJECTS

    87

    Figure 8-11: 74153 circuit

    The circuit should now mirror the input switches.

    8.7 Conclusion

    A multiplexer, or MUX, is a circuit that selects a single output from multiple inputs. It has multiple uses. The main use of a MUX is to select between input values, such as input values to the ALU in a CPU. But it can also be used to implement logic where the select lines are the inputs to a function, and the outputs to the function are hardwired to input values for the MUX.

    A MUX is an interesting circuit as it actually contains a decoder circuit as part of its implementation. This allows the MUX to be more easily built using a decoder, and shows a valid use for a decoder.

    8.8 Exercises

    1. Implement the 1 bit 4-to-1 MUX in Figure 8-9.

    2. Implement a 1 bit 4-to-1 MUX using the 74139 decoder chip introduced in section 7.4.

    This will require both the 74139 decoder and 7404 inverter chip.

    3. Implement the 1 bit 4-to-1 MUX using the 74139 decoder chip introduced in section7.4, but do not use an inverter on the 74139 output. Instead use the enable low outputs from the 74139 chip directly. This allows the circuit to be implemented using only 3 chips, a 74139, a 7402, and a 7432 chip.

    HINT: Remember deMorgan's Law, AB = (A'+B')'.

    88

    DIGITAL CIRCUIT PROJECTS

    4. Implement a 1 bit 4-to-1 MUX using the 74153 chip, as in section 8.3.

    5. Explain how a 1 bit 4-to-1 MUX can calculate any binary Boolean function. Because the MUX can calculate the result of any Boolean function, we call the MUX a univeral operation.

    6. In Logism implement an 8 bit 4-to-1 MUX using 8 4-to-1 MUXes.

    7. In Logisim implement an 8-to-1 MUX using 2 4-to-1 MUXes and a 2-to-1 MUX.

    8. In Logisim implement an 8-to-1 MUX using 4 2-to-1 MUXes and a 4-to-1 MUX.

    9. In Logisim implement a circuit similar to the one in figure 8-10, but which produces output which is the opposite of the input switch (e.g. the LEDs are 0 when the switch is 1, and 1 when the switch is 0). Change the program in the breadboard to match this new logic.

    index-93_1.png

    DIGITAL CIRCUIT PROJECTS

    89

    Chapter 9 Memory basics - flip-flops and latches

    9.1 Introduction

    This chapter introduces the last IC needed for a CPU, memory. For example 4 memory cells, or registers, on a CPU may be labeled R1..R4. In this chapter how these memory locations stored data will be explained.

    Figure 9-1: Memory in a CPU

    Up to this point this text all of the circuits are simple, or non-sequential, circuits. These circuits are called simple because the current is applied and the circuit takes on a set of values specified by the Boolean function for the circuit. The circuits have no state, or memory, of what previous values the circuit had. In order to do interesting things, like running programs, a computer must have state.

    The state of a circuit is the values of all memory which is stored. State is maintained in memory, and memory is just a place to store the values that make up the state. Circuits that contain state elements (memory) are called sequential circuits. This chapter will show how memory is implemented in hardware.

    9.2 Background material

    Memory is perhaps the hardest concept that is covered up to this time in the text. Therefore there is a lot basic material and background concepts which need to be covered before moving into how memory works directly. The concepts which will be covered in this section are:

    • State

    • Static and dynamic memory

    • Square wave oscillation

    9.2.1 State

    It is easy to confuse state and memory, and this is often a problem for programmers at all levels of experience. The two are very different, and it is important to understand this difference to understand how a computer works. Memory is a place to store values; state is the value of all memory.

    For example a 2-bit counter would have 2 bits of memory which would be used to store the current value in the counter (002..112) in the 2-bits. In a large computer state is the value of all

    index-94_1.jpg

    90

    DIGITAL CIRCUIT PROJECTS

    memory accessible in that computer. State is important because in hardware computers are most easily seen as simply machines that transition from one state to another using large black-boxes of circuits (called combinational logic) to determine the computer's next state.

    To apply this to a computer, consider two numbers are to be added together. These numbers would be stored in two memory locations. These two memory locations would be used as input to a combinational circuit (an adder), and stored back to (possibly the same) memory location.

    Hence the operation can be thought of as a state transition where the initial state of the computer (S0, the two memory values) are added in a black block (combination logic implementing an adder), and the result is a new state (S1, with the value of a memory location changed).

    9.2.2 Static and dynamic memory

    The second important memory concept is the difference between the static and dynamic memory8. Dynamic memory, called DRAM,is implemented using a capacitor and a transistor, and so is simple and cheap. However, the capacitor leaks current, so it is necessary to recharge it every other clock cycle, making dynamic memory slow. Static memory, called SRAM, does not have to be recharged, so it is faster, but requires at least 5 gates to implement. This makes static memory both faster and more expensive. Both types of memory exist in a computer, but for now we will discuss memory in the CPU, so speed is the most important requirement and only static memory will be used. Dynamic memory will not be covered.

    9.2.3 Square Wave

    Contained in every computer is a system clock, which regulates how fast the computer executes instructions. This is often cal ed the clock speed or clock rate of the computer. One of the functions of the system clock is to generate a signal called a square wave. A square wave is a pulse of current which alternates over time from a low voltage (0) to a high voltage (1). This is illustrated in Figure 9-2. In this figure the voltage is low from time t0 to t1, t2 to t3, t4 to t5, etc. The voltage is high from time t1 to t2, t3 to t4, etc. This oscillation of voltage can be used to send a 0 or 1 value into a circuit, and be used to control the changing of the state in the circuit. A square wave wil be used to implement state, and will be illustrated in the next section.

    Figure 9-2: Square Wave

    9.3 Latches

    A latch is a way to implement a circuit which maintains a data value of high(1) or low (0) so long as current is maintained in the circuit. Latches implement static memory that is used to maintain 8 Computer science often reuses terms with very different meanings in different contexts. This happens here where static and dynamic memory mean how memory is al ocated at a programming level, and how memory is implemented at a hardware level. Realize that there is no connection between the terms at the different levels of implementation (programming and hardware). Static and dynamic programming memory can exist in static or dynamic hardware memory.

    index-95_1.jpg

    index-95_2.jpg

    DIGITAL CIRCUIT PROJECTS

    91

    the state of the CPU.

    9.3.1 D latch

    There are many types of latches, including the R-S latch, T latch, and D latch. The only latch needed in this text is the D latch, shown in Figure 9-3, so it will be the only one covered. A D

    latch is a circuit that is set using an input value named D and a clock pulse. When the clock pulse is high (or 1), the value of the D latch changes to the input value of D. When the clock cycle is low ( or 0) the value of latch will maintain the last D value it received when a clock a cycle was high. The value which is saved in the D latch is named Q, and both Q and its complement Q' are output from the circuit.

    Figure 9-3: D latch

    The truth-table in Figure 9-4 gives the characteristics of the D latch. While the value of clock is 0, the D latch does not change value, and thus Qnew = Qcurrent. When the clock is 1, the D latch is set to the input value of D, and Qnew takes on the value of D.

    Input

    Output

    D

    Clock

    Qnew

    Comment

    x

    0

    Qcurrent State does not change

    0

    1

    0

    1

    1

    1

    Figure 9-4: Characteristic truth-table for a D latch

    To create multi-byte memory cells, multiple D latches are combined.

    While the version of the D latch described above is sufficient for storing data values, to be useful in a CPU the D latch needs to have an addition input called an enable bit. The enable bit allows the D latch to be set in only specific situations, not simply every time the clock is high. The D

    latch with an enable bit is shown in the Figure 9-5.

    index-96_1.jpg

    92

    DIGITAL CIRCUIT PROJECTS

    Figure 9-5: D latch with enable bit

    The truth-table which characterizes this D latch is shown in Figure 9-6. The implementation of this version D latch is left as an exercise at the end of the chapter. Note that an X in a column is a don't care condition, e.g. it does not matter what value is used as this input is not used.

    Input

    Output

    D

    Enable

    Clock

    Qnew

    Comment

    x

    X

    0

    Qcurrent

    State does not change

    x

    0

    X

    Qcurrent

    State does not change

    0

    1

    1

    0

    1

    1

    1

    1

    Figure 9-6: Truth-table for a D latch with enable bit

    9.3.2 Circuit diagram for a D latch

    The circuit diagram for a D latch is shown in Figure 9-7. This latch circuit will be explained in two steps. The first step will explain why the latch maintains its current state (Qnew = Qcurrent) if the clock is low. The second step will explain why the latch changes state (Qnew = D) if the clock is high.

    In the first step, note that the lines InputA and InputB must always be high (1) if the Clock input is low (0). Therefore the area which is circled in the diagram below can be analyzed without considering any other part of the circuit.

    Figure 9-7: Circuit diagram for a D latch

    Remember that a NAND of 1 with any value (e.g. Q) is simply its complement (e.g. Q'). So once the circuit is set, so that the outputs are Q and Q', it is easy to see that the output of the top

    index-97_1.jpg

    DIGITAL CIRCUIT PROJECTS

    93

    NAND gate is Q (e.g. (Q'*1)' = Q), and the output of the bottom NAND gate is Q' (e.g. (Q*1)' =

    Q'). Thus if Q and Q' are loaded into the circuit and the clock is 0, the circuit will maintain the values of Q and Q', and the latch keeps its current value.

    Next the question is if the Clock line becomes high (1), how does it force the value of D into the latch. To see this, note that if the Clock become 1, the InputA = D' and InputB = D must be true.

    Thus one of the lines must be 0. Again consider the part of the circuit which has been circled.

    The line which is 0 will force its output to be 1 (e.g. if Input-A = 1, Q = 1, or if Input-B = 0, Q' =

    1). This will eventually force the output of the other NAND gate to 0, though it might take some time to settle to this value. So long as the time needed for the circuit to settle is less than the clock speed (the length of the clock pulse), the circuit will become stable with Q = D and Q'=D'.

    So the result of the clock being high is that the latch will store in its state the value of Q = D and Q' = D'.

    Before the first clock pulse, the state of the latch is simply invalid, and the value of the latch cannot be used until after it is set with the first clock pulse.

    9.3.3 Implementing the D latch

    Implementing the D latch will require 2 switches, one NOT gate (7404 chip) and 4 NAND gates (7400 chip), and 2 LEDs for Q and Q'. In this lab a clock is not used, and instead is simulated by the second switch. Also in this diagram the two lines running from the output of the NAND

    gates backwards to the input of the other NAND gate use green wire.

    Figure 9-8: Implementation of a D latch

    index-98_1.png

    94

    DIGITAL CIRCUIT PROJECTS

    The following steps describe the implementation of the D latch, and correspond to the circuit in Figure 9-8.

    0. Install and power two switches (D and Clock), and the two output LEDs (Q and Q').

    1. Install and power the 7404 (NOT gate) chip.

    2. Install and power the 7400 (NAND gate) chip.

    3. Connect the D switch to the first NOT gate (pin 1 on the 7404 chip). The output from this NOT gate, D’, is on pin 2.

    4. Connect the CLK switch and the D' output (pin 2 and on the 7404 chip) to the first NAND gate, pins 1 and 2 on the 7400 chip. The output from this NAND gate will be on pin 3 of the 7400 chip, and used in step 5 (pin 3 on the 7400 chip).

    5. Connect the output from step 4 (pin 3 on the 7400 chip) to the second NAND gate (pin 4

    on the 7400 chip). Connect the output from step 7 (pin 8 on the 7400 chip) to the second input (pin 5 on the 7400 chip). The output from this NAND gate (pin 6 on the 7400 chip) will be sent to Q' and used in step 7 (pin 10 on the 7400 chip).

    6. Connect the D and Clock switches to the third input NAND gate (pins 12 and 13 on the 7400 chip). The output of this NAND gate will be on pin 11 of the 7400 chips, and used in step 7 (pin 9 on the 7400 chip).

    7. Connect the output from steps 5 and 6 (pins 6 and 11 on the 7400 chip) to the inputs of the fourth NAND gate (pins 9 and 10 of the 7400 chip). The output from this NAND

    gate (pin 8 on the 7400 chip) will be sent to the input of step 4 (pin 4 on the 7400 chip), and to Q'.

    When implemented correctly, the output Q and Q' lights will follow the D switch if the CLK

    switch is set to 1, or the on position. If the CLK is set to 0, or the off position, the lights will not change.

    Figure 9-9: 7475 pin configuration

    DIGITAL CIRCUIT PROJECTS

    95

    9.3.4 D latch as a single IC chip

    The D latch is a common IC, and it has been implemented as a single chip, the 7475 chip. The 7475 chip is called 4-bit bistable latch because each chip has four 1-bit D latches. A D latch is bistable because it has 2 stable states, 0 or 1.The circuit implemented here will use only one of the D latches available on the 7475 chip.

    The layout of the 7475 chip is somewhat complex. The pin configuration is given in Figure 9-9

    and a table for the meaning of each pin in Figure 9-10. The implementation of the circuit in this section will only use pins 1, 2, 5, 12, 13 and 16. The other pins will simply be left open, and not discussed further.

    Symbol Pin

    Description

    1Q'

    1

    complementary latch output 1

    1D

    2

    data input 1

    2D

    3

    data input 2

    LE34

    4

    latch enable input for latches 3 and 4 (active high)

    Vcc

    5

    positive supply voltage

    3D

    6

    data input 3

    4D

    7

    7 data input 4

    4Q'

    8

    complementary latch output 4

    4Q

    9

    latch output 4

    3Q

    10

    latch output 3

    3Q'

    11

    complementary latch output 3

    GND

    12

    Ground

    LE12

    13

    latch enable input for latches 1 and 2 (active high)

    2Q'

    14

    complementary latch output 2

    2Q

    15

    15 latch output 2

    1Q

    16

    15 latch output 1

    Figure 9-10: 7475 pin meanings

    index-100_1.jpg

    96

    DIGITAL CIRCUIT PROJECTS

    9.3.5 Implementation of a D latch using a 7475 chip

    Figure 9-11 implements the same circuit as in Figure 9-8, but now the 7475 chip is used. The fol owing steps outline how to implement this circuit, and the meaning of each connection.

    0. Insert the switches for the inputs CLK and D, and the LEDs for the outputs Q and Q'.

    1. Insert and power the 7475 chip. Note that the power is very different from any other chip that has been used up to this point. The positive and ground wires are on opposite sides of the chip, and they are on pins 5 and 12. Make sure you instal the power correctly, and check the chip after powering it to see if it is hot. If it is hot, you have wired it incorrectly.

    2. Connect the D input to pin 2 on the 7475 chip.

    3. Connect the CLK to pin 13 on the 7475 chip. This is labeled LE12, or latch enabled input for latches 1 and 2, enabled high. Enabled high means connected to the positive rail or set to the value of 1, and enabled low means connected to the ground rail or set to the value of 0. So this chip enables latch 1, the one we are using, when the CLK switch is set to high.

    4. Connect the Q output on pin 16 to the right LED.

    5. Connect the Q' output on pin 1 to the left LED.

    Figure 9-11: : D latch using a 7475 chip

    This circuit should behave exactly like the circuit in Figure 9-8.

    9.3.6 Limitations of the D latch

    The D latch does store state, but it is inefficient when implemented in a sequential circuit. To understand why it is inefficient, consider the Figure 9-12, which implements a circuit where the D latch provides some part of the state, and a black box containing some combinational logic to

    index-101_1.jpg

    index-101_2.jpg

    DIGITAL CIRCUIT PROJECTS

    97

    determine the next state. In this circuit, the result of that black box uses the current D input to determine the new state and set the D latch.

    Consider the case where the black box takes longer than a half of the clock pulse, as shown in Figure 9-12. The D latch retains its value until the combinational logic is completed, which occurs when the CLK is low. Thus the value of the D is not changed until the next clock pulse, and the circuit is fine.

    Figure 9-12: State transition with multiply operation

    However, it is unreasonable to expect all instances of combinational logic to take the same amount of time. For example, the time to do addition is very much smaller than the time it takes to do multiplication. This situation is shown in Figure 9-13. Here the black box can execute faster than the clock can pulse. In this case the latch is changed in the middle of a state transition, and the new value will cause the combinational logic to continue to process the new value while the clock pulse is low. Therefore, the value the D latch will be set to when the clock pulses high again will be incorrect.

    Figure 9-13: State transition with add operation

    One way to handle this situation is to put two D latches in the circuit, one which is set when the clock is high and the other when the clock is low, as shown in the Figure 9-14. This allows the circuit to obtain a value from the second D latch while updating the first.

    index-102_1.jpg

    index-102_2.jpg

    98

    DIGITAL CIRCUIT PROJECTS

    Figure 9-14: Two D latches to hold correct state

    While this solves the problem of maintaining the proper state of the latch, it should be obvious that it is a problem because it more than doubles the size of the circuit needed. This is twice as expensive, uses twice as much power, and produces twice as much heat. A better solution is needed, and one that was developed is called an edge triggered flip-flop.

    9.4 Edge triggered flip-flop

    An edge triggered flip-flop (or just flip-flop in this text) is a modification to the latch which al ows the state to only change during a smal period of time when the clock pulse is changing from 0 to 1. It is said to trigger on the edge of the clock pulse, and thus is called an edge-triggered flip-flop. The flip-flop can be triggered by a raising edge (0->1, or positive edge trigger) or falling edge (1->0, or negative edge trigger). All flip-flops in this text wil be positive edge trigger.

    The concept behind a flip-flop is that current flowing within a circuit is not instantaneous, but always has a short delay depending on the size of the circuit, the gates that it must traverse, etc. This is illustrated in Figure 9-15. In this diagram, it would appear that the Boolean equation (true^false) is always false, so this circuit should always produce a 0 output. However since there is a small but present lag in the current going over the NOT gate, there is a small but finite period of time when the two inputs to the AND gate would both be 1 (when the clock is transitioning from 0 to 1), and the output of the circuit would be 1.

    Figure 9-15: Small time delay rising edge

    This amount of time, Δt, is shown on the square wave diagram in Figure 9-16. This time is called a raising edge trigger, and it is during this time interval that the above circuit would be 1.

    index-103_1.jpg

    index-103_2.jpg

    index-103_3.jpg

    DIGITAL CIRCUIT PROJECTS

    99

    Figure 9-16: Edge trigger time in square wave

    This short delay can be used to change the circuit such that it wil only change during this brief edge trigger. Because Δt is smaller than any combinational logic, this removes the need to create a second latch to maintain a valid state. A circuit which implements this concept is shown in Figure 9-17.

    Figure 9-17: Illustrative example of D flip-flop

    The problem with the circuit in Figure 9-17 is that it cannot guarantee that the time delay caused by the edge trigger is sufficient to allow the latch logic to obtain the correct state. The circuit in Figure 9-18 is a true implementation of a flip-flop. While it appears much more complex than the implementation in the Figure 9-17, it is left as an exercise to show that it contains exactly the same number of gates as the example above.

    Figure 9-18: Actual implementation of a D flip-flop

    100

    DIGITAL CIRCUIT PROJECTS

    Due to a problem known as debouncing, it is hard to illustrate a flip-flop in isolation as a circuit.

    So this chapter will not implement a flip-flop. However, a flip-flop will be used as part of the circuits in chapter 10.

    9.5 Conclusion

    Circuits which have memory and can maintain a state are called sequential circuits. Simple, or non-sequential, circuits are circuits which do not maintain a state using memory. Simple circuits can calculate results based on inputs, but to compute a useful result a circuit must be able to maintain a state.

    This chapter introduced the concept of SRAM, and how it is implemented using only NAND and NOT gates. SRAM maintains its state so long as current is supplied to the circuit, and does not require a refresh cycle, making it faster than DRAM. But SRAM is also more complex than DRAM, so SRAM is more expensive than DRAM.

    SRAM was implemented using a D latch circuit. The problem with using a latch in a circuit, that it requires two latches to be effective, was illustrated. The D flip-flop was then introduced to solve the problem with a D latch.

    9.6 Exercises

    1. Implement the D latch from Figure 9-8 using a breadboard.

    2. Implement the D latch to include an enable line using Logisim. The enable line will be used to control when the D latch is set, so it is only set if the clock and enable line are high.

    3. Implement the circuit from problem 2 using a breadboard.

    4. Implement the D latch to include a synchronous clear line using Logisim. A clear line will set the value of the D latch to 0 on the next clock pulse.

    5. Implement the circuit from problem 4 using a breadboard.

    6. Implement a D flip-flop using the 7475 chip, as in figure 9-11.

    7. Show that the circuits in Figure 9-17 and 9-18 have exactly the same number of gates.

    DIGITAL CIRCUIT PROJECTS

    101

    Chapter 10 Sequential circuits

    10.1 Introduction

    Now that memory has been introduced it is possible to produce machines that change state. The ability to change the state of the computer forms the basis to do calculations.

    In this chapter a state machine will be presented. This machine will use memory, implemented as latches or flip-flops, to define states. Events will be generated, in this case the pushing of a button to simulate a clock pulse, which will allow the state machine to transition to a new state.

    The relationship between the previous and successor states will be represented in a state transition table, and the table used to encode a simple program into a multiplexer. The program to be implemented is a simple mod 4, or 2-bit, up counter, which will count from 0..3.

    10.2 Debouncing

    Before beginning the discussion of sequential circuits, there is a problem which occurs when trying to simulate the rising edge of a clock in the circuit. In all of the labs up to this point the toggle switches appear to turn on and off cleanly. This is because the switches are used to represent a constant input to the circuit. The only state of interest is if the switch is 0 or 1. How quickly or cleanly the switch changed from 0 to 1 or 1 to 0 did not matter.

    In reality no switch ever makes a clean transition between 0 and 1. Switches cannot turn on/off cleanly. All mechanical switches, when turned on or off, exhibit a period of time where the switch oscillates between on/off before it settles into a steady value. This oscillation is generally too fast for a human to notice, but the oscillations produce multiple square waves, and thus multiple edge triggers. These edge triggers are slow enough for a latch or flip-flop to see multiple phantom state changes instead of a single clean state change.

    The lab in this chapter will demonstrate how a circuit can transition between defined states. This requires that each time the switch is thrown only a single edge is ever seen as being produced.

    The multiple edges being generated by the switch cause the circuit to behave incorrectly. So something must be done to get only a single state change when a switch is thrown.

    To handle these multiple phantom state changes, the circuits need to be debounced. A simple way to think about debouncing is to realize that if multiple on/off signals are processed in a small amount of time, they are in reality just noise coming from the switch, and the edges should be combined into a single event.

    Every type of switch, including the keys on the keyboard you type on, must be debounced. This debouncing is generally handled in software which is designed to filter out the noise of the switch. However the circuits we are looking at in this text do not implement a processor, so a software solution is not possible.

    To debounce the circuits in this chapter a hardware approach is used. This hardware approach requires three parts be implemented in our circuit.

    1. A small push button switch is substituted for our toggle switch. The push button provides a much cleaner input than the toggle switch, and so it is easier to get a single clean edge from the pressing of the button. The button does introduce a problem, and that is that it has only one input. Unless the button is pushed, it is neither positive or

    index-106_1.png

    102

    DIGITAL CIRCUIT PROJECTS

    ground. This is called an open state. All of the chips that have been used in circuits up to the time have been of the HC or HCT variety, largely because of their lower cost. But HC and HCT chips do not handle open states, so this lab requires the chip used to be the ttl version of the 7414 chip.

    2. An extra capacitor be connected to the output of the push button switch. This capacitor helps to further clean up the edge.

    3. A Schmitt inverter, which is a 7414 chip, is inserted into the circuit. A Schmitt inverted is a circuit implemented with hysteresis. Hysteresis means the output of a circuit is dependant not only on the current state, but on the history of its past inputs. So the Schmitt inverter again is used to help clean up the edges from the switch.

    The implementation of the debouncing in the circuit will be presented with the circuits used in this chapter. How the debouncing circuit works is not a topic of this text, and so it is presented without further comment.

    10.3 Implementing a state machine

    10.3.1 Mod 4 counter

    A mod (or modulus) 4 counter is a circuit that counts from 0..3. It is also called a 2-bit counter because the numbers from 0..3 can be represented using 2-bits (e.g. 00, 01, 10, 11)9. The state of the counter is represented in 2-bits, and so is stored in 2 flip-flops (or latches). Because the two flip-flops combine to make a single value, they are often called a 2-bit register.

    The state transitions of this machine, as a counter, are 00->01->10->11->00. The machine just counts from 0 to 3 and starts over. This is represented in the following state diagram.

    Figure 10-1: State diagram for a mod 4 counter

    This state diagram can be written as a state transition table, as shown below.

    9 The name mod 4 counter is more accurate because the 2-bit counter could be used to implement a mod 3 or mod 4 counter. This is more a problem with a 4-bit counter because it is often used as a decade (mod 10) counter or a hex (mod 16) counter.

    index-107_1.jpg

    DIGITAL CIRCUIT PROJECTS

    103

    Input

    Output

    Q1old Q0old Clock Q1new Q0new

    X

    x

    0

    Q1old Q0old

    0

    0

    0

    1

    0

    1

    1

    0

    1

    0

    1

    1

    1

    1

    0

    0

    Figure 10-2: State transition table for a mod 4 counter

    This table says that if the clock does not pulse, Q1 and Q0 retain their old values. When the clock generates an rising edge (↑), the values of Q1 and Q0 transition to the next value in the counter, or their next state.

    10.3.2 Implementation of a state transition diagram

    The following is a generic implementation of a state machines. There are two components. The first is a n-bit register, which is a collection of n 1-bit D flip-flops or D latches. These n 1-bit data values store the current state of the machine, and can store up to 2n states. The register changes state when the clock generates a positive edge trigger, causing the flip-flops to take on a new value.

    The register will output some set of values, and at the same time recycle its state back into a set of gates which will determine how to change the register to the next state. This set of gates will be called the next state logic. The output of the next state logic will be connected to the input to the registers so that when the clock pulses (or ticks), the register is loaded with the new values.

    This logic is represented in the following figure.

    Figure 10-3: Circuit overview for a state machine

    index-108_1.jpg

    104

    DIGITAL CIRCUIT PROJECTS

    As this diagram shows that the input to the next state logic comes from the previous state. The next state logic uses the previous state to calculate the next state to store into the register. The clock tick then causes the register to store new state, which is feed back into the next state logic to calculate a new next state.

    This overview explains how a state machine works, but has left open the question of how to implement the next state logic? There are two basic ways to implement this logic, either through hardware or using a micro program. A hardware implementation uses gates to calculate the new state. A micro program is implemented in using Read Only Memory (or ROM), and the next state is retrieved from an address given by the current state. These will be explained in the next two sections.

    10.3.3 Hardware implementation of next state logic

    The next state logic must take as input the current state and convert it to the next state. The state transition diagram in Figure 10-2 is very similar to a truth table, where Q0old and Q1old are the inputs to the circuit, and Q0new and Q1new are the outputs. From the state transition diagram, it is simple to solve for the Boolean expressions, which are Q0new = (Q0old' * Q1old') + (Q0old' * Q1old)), and Q1new = (Q0old XOR Q1old). The circuit diagram for this next state logic is shown in the following figure.

    Figure 10-4: Hardware implementation for a mod 4 counter

    In this figure, the next state logic is implemented using NOT, AND, OR, and XOR gates. is actually a type of micro program which is implemented in hardware. This is called hard wired because the actual circuit to calculate the next state is wired into the circuit.

    index-109_1.jpg

    DIGITAL CIRCUIT PROJECTS

    105

    The problem with hard wired programs is that they cannot be easily changed. Modern computers generally do not implement the micro programs by hard wiring them, but use some type of read only memory.

    10.3.4 Read Only Memory

    Read Only Memory (ROM) is memory that is never written after it is first programmed10. It can be used to store programs that are used to initial y boot a computer, or to store static data tables or micro programs used to specify how the internal hardware of the CPU works. The fol owing is an example of the Mod 4 Counter shown using a ROM chip to implement the next state logic as a micro program.

    Figure 10-5: ROM implementation of a mod 4 counter

    The ROM chip contains the micro program which implements the Mod 4 Counter. The next state for the mod 4 counter (1, 2, 3, and 0, or 002, 012, 102, 112) is stored at an address corresponding to the current state of the mod 4 counter. Thus at address 0 the ROM program stores 1, to state that the next state from 0 is 1.

    The address is the current state of the counter, which is the value currently stored in the registers.

    At address 0, the value 1 is stored, which says that when Q0 and Q1 are 002, the ROM will read the value 012 from memory. Each time the clock ticks, the ROM chip sends the next value to the registers, which transitions to the next state in the counter.

    ROM chips are a very good way to implement state transition tables, but require special hardware to create and program the ROM chips. So a simple trick will be used to implement ROM for our circuits, as was done in the switch mirroring circuit in section 8-6. This trick is to use a multiplexer with hard wired input for the micro program, and the select bits used to specify the address. This design is shown in Figure 10-6.

    10 ROM and PROM chips are never changed once they are written. Some types of chips similar to ROM chips, such as EPROM or EEPROM, can be written in order to store a new program. But even these types of ROM chips are written to infrequently, and not meant to store transient data.

    index-110_1.jpg

    106

    DIGITAL CIRCUIT PROJECTS

    To understand this circuit, realize that each MUX chooses 1-bit for each of the 4 states. So when the state is 002, the bottom MUX will choose the 0 bit and the top MUX will select a 1 bit, which gives a new state of 012.

    This circuit using the two MUXes to implement the micro program will be shown in the next section.

    Figure 10-6: Mux implementation of next state logic for a mod 4 counter 10.3.5 Implementation of the Mod 4 counter

    Figure 10-9 implements the Mod 4 counter. Steps 1 and 2 are needed to implement the debouncing for the circuit, and are presented with no explanation of how they work. This circuit generally works well if the button is pressed sharply and cleanly, but multiple signals will at times stil be generated by the push button.

    1. Place the push button switch on the board. The switch does have direction, so it must be inserted properly to work. The easiest way to get the direction correct is to put the switch across the center cut out in the breadboard. Because the legs on the button are hooked, there is only one direction to insert the push button, and that is the correct direction.

    Connect the input of the chip to the negative rail. The output of the push button switch should be connected to the input of the 7414 Schmitt inverter in step 2. The output of the switch must also be connected to the negative rail by a 0.1µf capacitor. This capacitor is absolutely necessary for the circuit to work properly.

    2. Place the 7414 Schmitt inverter chip on the board, and power it. The output from the 7414 chip is the two clock inputs for the 7474 chip in step 7.

    3. Place the 74153 multiplexor chip on the board, and power it. The pin layout for the 74153 multiplexor is shown in Figure 10-7. Step 7 will discuss how to wire the chip to connect it to the circuit. The steps below discuss how to wire it.

    index-111_1.jpg

    index-111_2.png

    DIGITAL CIRCUIT PROJECTS

    107

    a. Power the chip with GND on pin 8 and Vcc on pin 16, as usual.

    b. Pins 1 and 15 are enable low. These enable the output from each MUX. We always want the output from the MUXes, so enable them by connecting these pins to low.

    Figure 10-7: 74153 pin layout diagram

    c. Pins 3...7 and pins 10...14 are the inputs to each MUX. These pins are set to implement the program. Note: the pins are set from I0...I3 in an upward direction, not a downward direction. Implement the program in Figure 10-6 using 1I values of 0110 and 2I values of 1010.

    Figure 10-8: 7474 pin layout

    index-112_1.jpg

    108

    DIGITAL CIRCUIT PROJECTS

    4. Place the 7474 2-bit D flip-flop chip on the board and power it. The pin layout of the 7474 chip is in Figure 10-8. Step 8 will discuss how to wire the chip to connect it to the circuit. The steps below discuss how to wire it.

    a. Power the chip with GND on pin 7 and Vcc on pin 8, as usual.

    b. Pins 1, 4, 10, and 13 are for asynchronous set and reset. They are enabled low, so connect these pins to the positive rail to disable them.

    5. Connect the push button switch to the input to a gate (pin 1) on the 7414 Schmitt inverter. The output of this gate (pin 2) wil be used to both clocks on the 7474 2-bit D

    flip-flop chip.

    6. Connect the 74153 chip (step 3) into the circuit. The inputs S1 and S0 (pins 2 and 14) are the outputs from the previous state, stored in the D flip-flops in step 4. These inputs use green wires to show that they are recycled from the output of a chip further down in the circuit. The outputs of the 74153 chip (pins 7 and 9) are the D input for the next state to the registers.

    7. Connect the D inputs for the 7474 2-bit D flip-flop to pins 2 and 12. The clock inputs from step 2 are connected to pins 3 and 11. The outputs are the current state on 1Q and 2Q, pins 6 and 9. These output are used as inputs to the next state logic implemented in the MUX (step 6, the green wire), and to show the current state represented in the output LEDs.

    Figure 10-9: Mod 4 counter

    DIGITAL CIRCUIT PROJECTS

    109

    When the push button switch is pressed, the LED lights should cycle through the states for 00-

    >01->10->11->00.

    10.4 Conclusion

    State machines are simple calculation machines which use a state and next state logic to implement simple algorithms such as counters. State machines are also a part of any larger calculation machine such as a computer.

    State machines can be implemented in hardware using some sort of memory to store a state, and next state logic which allows the machine to advance from one state to another. The memory used to store the state in this chapter was D flop-flops.

    The next state logic was implemented in two ways in this chapter. The first was by a circuit which implemented combinational logic to calculate the next state of the circuit. The second way next state logic was implemented was using a ROM chip where the current state was used as an address to the memory in the ROM chip which contained a value for the next state. Using a ROM chip in this way was called micro-programming.

    The chapter then continue by showing how a ROM chip could be simulated using a MUX with hard wired values as inputs, and the select lines as addresses to the values to choose.

    10.5 Exercises

    1. Implement a Mod 4 up counter using the 74153 chip to implement the next state logic as shown in section 10.3.

    2. Implement the Mod 4 up counter using combinational logic to implement the next state logic, as shown in Figure 10.4

    3. Implement a Mod 4 down counter, or a counter which counts 11->10->01->00->11.

    This counter will require that you modify the state diagram, state transition table, and your program. For this problem submit the state diagram, state transition table, Logisim diagram, and implemented circuit.

    4. Implement the following up counters in Logisim:

    a. Mod 6 counter

    b. Mod 8 counter

    c. Mod 10 (decade) counter.

    110

    DIGITAL CIRCUIT PROJECTS

    index-115_1.png

    DIGITAL CIRCUIT PROJECTS

    111

    Chapter 11 Use of these ICs in a CPU

    The IC’s presented in this text are not useful in themselves, but are quite powerful building blocks in implementing larger integrated circuits. This chapter will examine a useful IC, a Central Processing Unit (CPU), where these circuits provide the backbone of how the CPU is implemented. The CPU that is presented can be downloaded from the free text Implementing a

    One Address CPU in Logisim.

    This chapter will not attempt to describe the CPU in detail, nor will it attempt to explain how to implement or use programs on this CPU. These details are covered in the referenced text. This chapter will instead break down the CPU components to highlight how the ICs are used in the CPU, to show how important the ICs covered in this text are.

    11.1 An overview of the CPU.

    The following figure is of the entire CPU that will be covered in this text. There are 3 Logisim sub circuits that are part of this CPU, two of which will be broken down to show how the ICs from this book. They are the Arithmetic Logic Unit (ALU), and the Control Unit (CU). These two units will be explained in terms of the entire CPU, and then shown as sub circuits to expose the decoder and adder circuits.

    This CPU is an example of an accumulator or one-address architecture CPU. In all CPU designs, two operands are feed to the ALU, where the two operands are used to perform some operation and produce a result. In an Accumulator CPU, one of these operands is called the $pc, which is memory on the CPU chip (called a register), and the other comes from either the instruction itself or memory. So a simple program to add two numbers, the value of variable A and the number 2, would look as follows:

    clac # set the $ac (accumulator register) to 0

    add A # add the value of A to the accumulator

    addi 5 # add the number 5 to the value in the accumulator

    stor B # stor the accumulator value to memory variable B

    112

    DIGITAL CIRCUIT PROJECTS

    The CPU keeps track of the statement to process using the Program Counter ($pc) register. The $pc contains the address of the next instruction to execute. The CU takes the instruction, which is a 4-bit binary number, and breaks it down into control wires which specify how each component of the CPU (muxes, decoders, ALU, and memory) should behave for that instruction.

    The ALU does the actual operation that is requested (e.g. an add, subtract, etc.) So for example the add A instruction. The CU would specify:

    1. That the mux in front of the $pc select the input 0, which is the next instruction in the program (e.g. do not branch).

    2. That the mux in front of the $ac select input 0, which is the result of the ALU, to store in the $ac.

    3. That the mux in front of the ALU select a value from memory, not the instruction.

    4. That the ALU execution an addition operation.

    5. That the value of the $ac not be stored back to memory.

    The rest of this chapter will show how the IC’s from this text are used in this design.

    11.2 Flip Flops

    All memory cells located in the CPU are called registered, and are implemented as D flip flops.

    These flip flops are also called static ram, or SRAM. In this CPU, the values of the $ac and $pc, which store the current state of the CPU, are implemented as a group of 16 flip flops. These components are circled in red in Figure 11.1. Without flip flops, it would be impossible to maintain the state of the CPU, and the CPU could not do any useful work.

    The number of registers in a CPU varies widely between the types of CPU, and even within a CPU itself. A more normal Accumulator CPU would have several more registers, such as a Memory Access Register ($mar), and a temporary register ($temp).

    11.3 Muxes

    When designing a CPU, muxes seem to pop up everywhere. They are the most used building block in a CPU, and most larger ICs. In the CPU presented in Figure 11.1, each mux is circled in blue, the following muxes are used.

    1. There is a mux before the $pc register to select if the next sequential instruction in the memory is to be used, or if the program should branch to a non-adjacent instruction.

    2. There is a mux before the ALU to select if the ALU operand will be retrieved from memory, or if the operand should be taken from the instruction itself.

    3. There is a mux before the $ac register that determines if the instruction is to set the value of the $ac to 0, or if the value to be stored in the $ac comes from the ALU.

    11.4 Adder

    The ALU is the part of the CPU that implements operations, such as add, subtract, multiply, divide, OR, AND, shift, etc. The adder in this text was presented as an exemplar of an operation which would be done in the ALU. In this ALU, there is an ALUOpt control bus that consists of 4

    wires, which can specify up to 16 operations. Only 4 operations are implemented in this ALU,

    index-117_1.png

    index-117_2.jpg

    DIGITAL CIRCUIT PROJECTS

    113

    integer add, sub, multiply, and divide. All 4 operations are calculated all the time, but only one result is ever returned, and that result is selected by an ever ubiquitous mux.

    Figure 10-10: ALU Implementation

    11.5 Decoder

    Other than the fact that a decoder is present in a mux, the decoder is only present in this CPU in the CU. In the CU the decoder is used to break down the 4 bit input into the actual operations that the CPU is to perform. These operations are then combined to set the correct control wires for the CPU to perform this operation.

    Figure 10-11: Decoder used in the CU for a CPU

    11.6 Summary

    This text was written to help students and hobbyists to understand what an IC is, and to give them some of the most basic ICs and shown how they can be implemented using only AND, OR,

    114

    DIGITAL CIRCUIT PROJECTS

    NOT, NAD, and XOR gates. By actually implementing the ICs using a bread board and chips, the circuits were more concrete ideas rather than fuzzy concepts.

    However up until this last chapter, the usefulness of these gates in larger ICs was not covered.

    This chapter showed how to use these simple building blocks could create an IC which has potential to implement useful hardware.

    DIGITAL CIRCUIT PROJECTS

    115

    Index

    ' used as NOT operator, 20

    Chip Logic Type

    * as AND operator, 20, 48

    HC, 15

    + used as OR operator, 20, 48

    HCT, 15

    2 bit 4-to-1 mux, 80

    ttl, 15

    2-bit adder circuit, 68

    chip orientation, 50

    2-to-4 decoder implementation, 72

    chip pins, 50

    4-to-1 mux, 80

    chips getting hot, 51

    74153 circuit diagram, 85

    Chips used in text

    7805 voltage, 40

    7400 NAND gate, 15

    7805 voltage regulator, 41

    7400 NOT gate, 94

    7-segment display, 30, 34

    7402 NOR gate, 15

    accumulator architecture, 111

    7404 hex Inverter (NOT gate), 15

    adder, 69, 111, 112

    7404 NOT gate, 72, 76, 94

    ALU, 61, 79, 111

    7408 AND gate, 15, 49, 51, 63, 66, 73, 83

    analytical engine, 13

    74139 decode, 74

    AND gate circuit, 49

    74139 decoder, 16, 74, 76

    AND, OR, and NOT are universal, 21

    7414 Schmitt inverter (NOT gate), 106

    Arithmetic Logic Unit, 61, 111

    7414 Schmitt Invertor (NOT gate), 15

    associative boolean operators, 55

    74153 multiplexer, 16, 85, 86, 106

    associative operations in Logisim, 55

    7432 OR gate, 15, 66, 83

    binary addition, 61

    7474 D flip flop, 15, 108

    binary logic, 47

    7475 D latch, 96

    binary operators, 48

    7475 D-latch, 95

    binary variable value

    7486 XOR chip, 63

    0/1, 19, 47

    7486 XOR gate, 15, 66

    high/low, 47

    7805 voltage regulator, 15

    on/off, 47

    Cin, 65

    true/false, 19, 47

    Circuit diagram for a D latch, 92

    Boolean algebra, 19, 22

    clock rate, 90

    Boolean logic, 47

    clock speed, 90

    Boolean operation

    combinational logic, 90

    AND, 47

    Computers are machines, 17

    NOT, 47

    Control Unit, 71, 111

    OR, 47

    Cout, 65

    Boolean operator

    CPU, 13, 14, 71, 79, 89, 91, 111

    AND, 13, 48

    Creating the AND circuit, 51

    NAND, 13

    CU, 71, 79, 111

    NOT, 13, 48

    D flip flop, 112

    or, 48

    D flip-flop, 99, 100

    OR, 13, 48

    D latch, 91, 100

    breadboard, 37

    D latch enable bit, 91

    breadboard layout, 38

    datasheet, 50

    carry digit, 62

    Debouncing, 101

    Central Processing Unit, 13, 111

    Debugging the circuit, 45

    Charles Babbage, 13

    decoder, 77, 111

    chip datasheet, 50

    Decoder, 71, 113

    116

    DIGITAL CIRCUIT PROJECTS

    Decoder circuit, 71

    inverter, 48

    DeMorgan's Law, 22, 32

    Karnaugh map, 24

    Disjunctive Normal Form, 21

    Karnaugh Map, 23

    DNF, 21

    K-map

    don’t care conditions, 30

    3-variable, 25

    DRAM, 100

    K-map, 24

    dynamic memory, 90

    K-map

    Edge triggered flip-flop, 98

    4-variable, 27

    enable input low, 75

    labeling on chip, 49

    enable low, 77

    latch, 90

    falling edge, 98

    laws of magic, 13

    flip flop, 112

    LED installation direction, 45

    flip-flop, 98

    Limitations of the D latch, 96

    full adder, 64

    list of Boolean relationships, 22

    full adder circuit, 65

    Logisim, 14

    full adder implementation, 66

    Logisim circuit to turn on a light, 35

    gate

    memory, 89

    AND, 13, 49

    micro program, 104

    NAND, 13

    minimum Boolean expression, 31

    NOT, 13, 48

    minimum set of Boolean operations, 19

    OR, 13, 49

    minterm, 21

    XOR, 49

    Mod 4 counter, 102

    gates, 13

    multiplexer, 79

    GND, 50, 51

    mux, 112

    Gray Code, 23

    mux select bits, 79

    half adder, 61

    mux width (number of data bits), 79

    half adder circuit, 62

    negative edge trigger, 98

    half adder implementation, 63

    next state logic, 104

    Hardware implementation of next state logic,

    non-sequential circuit, 89

    104

    one-address architecture, 111

    hardware needed for circuits, 14

    operations code, 71

    high speed CMOS, 15

    Parts needed for labs

    high speed CMOS, ttl compatible, 15

    1k resistor, 16

    How a flip flop work, 98

    9V battery, 16

    How a latch works, 92

    9V battery snap, 16

    How to name logic chips, 14

    bladed screw driver, 16

    hysteresis, 102

    breadboard, 16

    IC, 13

    capacitors, 16

    Implementation of the Mod 4 counter, 106

    green led, 16

    Implementing a ROM chip with a mux, 106

    needle nose pliers, 16

    Implementing a state machine, 102

    push button switch, 16

    Implementing a state transition diagram, 103

    red led, 16

    Implementing one 2-to-4 decoder using the

    toggle switches, 16

    74139 chip, 76

    wire, 16

    Implementing the D latch, 93

    wire stripper, 16

    Implementing the switch circuit to turn on a

    pin configuration diagram, 51

    light, 36

    positive edge trigger, 98

    Integrated Circuit, 13

    rail on breadboard, 37

    DIGITAL CIRCUIT PROJECTS

    117

    raising edge, 98

    sum or products, 21

    Read Only Memory, 104, 105

    system clock, 90

    Real flip flop implementation, 99

    transitor-transitor logic, 15

    register, 89, 104, 111, 112

    truth table, 20, 23

    ripple-carry adder, 65

    truth-table, 47

    ROM, 104, 105

    unary operation, 47

    selector circuit, 79

    universal Boolean operations, 19

    sequential circuit, 89, 100

    universal Boolean operator, 32

    simple circuit, 89

    VCC, 50, 51

    square wave, 90

    Warnings for labs, 17

    SRAM, 100

    What is an edge trigger, 98

    state, 89, 90, 91, 100

    Why minimize number of gates, 22

    state diagram, 102

    Wire strippers, 38

    state transition tables, 105

    wiring convention, 16

    Stripping wires, 38

    XOR operator, 32