22C:122, Lecture Notes, Lecture 2, Fall 1999

Douglas W. Jones
University of Iowa Department of Computer Science

  1. A Breakneck Review of Digital Logic

    This review is organized in bottom-up fashion!

  2. Data Representations

    In a digital system, any physical condition may be used to represent the values zero and one, also referred to as true or false. We may use, for example, the opening and closing of relay contacts, the presence of or absence of some working fluid in a pipe, or the voltage on some point in a circuit.

    In digital electronics, we generally speak in terms of on wires within a circuit. At the electonic level, we must distinguish between several different values:

    The difference between the absolute minimum output and the threshold values for inputs is the noise margin of the logic family. For classic TTL, the minimum noise margin is 0.4 volts, but, note that the guaranteed input thresholds for zero and one are 1.2 volts apart. In fact, many gates have a short linear region where they act as analog components, but this region is rarely the full 1.2 volts wide! Instead, the typical gate has a linear region of around 0.5 volts, and the actual noise margin is closer to 1 volt.

    The point to remember is this: Logic circuits are not perfect digital devices with only 2 signal levels, but they are constructed so that, under normal operating conditions, they behave as if they were 2-level devices, and as a result, we can usually design digital systems without reference to the details of these thresholds and absolute minimum values.

    However, this is true only when we do not mix logic circuts from different logic families and it is only true when we do not overload circuits. Each logic family has different thresholds and minimum output values. Some families are fully compatable, while other logic families require special level conversion circuitry.

    Within a logic family, there is usually a concept of a unit load. The unit load of a standard input in that logic family is one, and the maximum fanout of a standard output in that logic family is the number of unit loads that may be connected to a single output. In the TTL logic families, most devices have a maximum fanout of at least 10.

    A logician may think in terms of infinite fanout -- that is, that a logic variable can be inspected by any number of users, but in real life, fanout is limited, each user of a variable draws current or otherwise loads the hardware that computes that variable, and therefore, there is a limit on the number of inputs that may be connected to one output.

    Special devices called bus drivers or buffers exist in many logic families. These are devices with a fanout limits significantly higher than other members of the family

  3. Combinational Devices

    The basic combinational functions of digital logic are the Boolean logic functions and, or and not.

    In addition to these, the functions nand and nor are commonly used. While we think of nand as being the same as a not operation composed with an and operation, in fact, the popularity of the nand function in digital design arises from the fact that nand is usually realized as a primitive function, and the and operation is frequently implemented in hardware as a not operation attached to the output of a nand gate.

    The standard 2-input functions are:

    	  A B | A and B | A nand B | A or B | A nor B | A xor B | A equ B
             -----+---------+----------+--------+---------+---------+---------
    	  0 0 |    0    |     1    |   0    |    1    |    0    |   1    
    	  0 1 |    0    |     1    |   1    |    0    |    1    |   0    
    	  1 0 |    0    |     1    |   1    |    0    |    1    |   0    
    	  1 1 |    1    |     0    |   1    |    0    |    0    |   1    
    	
    The xor operator is known as exclusive or, in English, and the equ operator is known as equals. When logic is written equationally, the following symbols are commonly used:
    	a and  b   ab   a*b  a×b  a&b
    
    	a or   b   a+b       a|b
                       __   ___  ___ 
    	a nand b   ab   a*b  a×b ~(a&b)
                       ___
    	a nor  b   a+b       ~(a|b)
    
    	a xor  b
                                 _______
    	a equ  b   a=b  a=b  a xor b
    	
    In the above, the overbar is used as a symbol for not, and it should be noted that a continuous overbar over all terms of an expression represents the negation of the entire expression and not the negation of its component terms. Thus
    	_____                    _   _
    	a + b is not the same as a + b
            _   _                _____
    	a + b is the same as a * b (DeMorgan's Law)
            _   _                _____
    	a * b is the same as a + b (DeMorgan's Law)
    	
    In addition, there are standard logic symbols for these operaitons. When square boxes are used, the name (or sometimes, an operator symbol) is shown inside the box:
            inputs           output
                     ______
            --------|      |
    	        | NAND |-------
    	--------|______|
    
    	
    By longstanding convention, inputs to logic circuits are drawn on the left and outputs on the right, unless the context makes it clear that some other convention is being used.

    The and, or, nand, nor and not logical operators all have conventional symbols that are distinguished by their shape and require no labels. These are crudely approximated below:

                     ____                 _____
            --------|    \        --------\    \
    	        | AND )-------         ) OR )-------
    	--------|____/        --------/____/
    
                     ____                 _____
            --------|    \        --------\    \
    	        |NAND )O------         )NOR )O------
    	--------|____/        --------/____/
    
                    |\ NOT                _____
                    | \           -------\\    \
    	--------|  >O---------        ))XOR )-------
    	        | /           -------//____/
    	        |/
    	
    In general, a "bubble" on any input or output of the symbol for a gate indicates a not operation, and a triangle by itself represents a buffer or amplifier. Thus, by DeMorgan's law, the following two symbols are equivalent:
                     ____                 _____
            --------|    \        -------O\    \
    	        |     )O------         )    )-------
    	--------|____/        -------O/____/
    
    	
    In practice, it is common to talk about positive logic, in which the "asserted" state is represented by a high signal (nominal +5 in TTL logic) and negative logic, in which the "asserted" state is represented by a low signal (nominal 0 in TTL). Many engineers will attempt to draw circuits so that the circuit symbol used is indicates the logical operation being performed, and the bubbles indicate which signals are positive and which are negative logic. Thus, for example, it is common to see this:
                     ____
            --------|    \
    	        |     )O--     
    	--------|____/    |    _____
    			   ---O\    \
    			        )    )-------
    		 ____      ---O/____/
            --------|    \    |
    	        |     )O-- 
    	--------|____/
    
    	
    Instead of this:
                     ____
            --------|    \
    	        |     )O--     
    	--------|____/    |     ____
    			   ----|    \
    			       |     )O------
    		 ____      ----|____/
            --------|    \    |
    	        |     )O-- 
    	--------|____/
    
    	
    The latter shows the parts actually used (3 nand gates), but the former is better at expressing the logical operation being performed, a logical sum of products.

  4. Common Combinational Functions

    There are some common higher-level logical functions that are worth describing. Given any truth-table, it is possible to automatically derive a logic circuit according to the following scheme:

    1. Start with the truth table for the function.
      	  inputs  |  outputs
      	   A  B   |   X  Y
      	----------+----------
      	   0  0   |   0  1   
      	   0  1   |   1  0   
      	   1  0   |   1  0   
      	   1  1   |   0  1   
      	
    2. Use one gate per row and one gate per column.
      Specifically, one not gate per input, one and gate per row, and one or gate per output. The and gates have as many inputs as there are inputs to the circuit, and the or gates have as many inputs as there are 1's in the corresponding column of the circuit. For example:
      	    input 
                A       B
                |       |
                o--     o--
                | _|_   | _|_
                | \ /   | \ /
                |  O    |  O
                |  |    |  |   ___
               -|--|----|--|--|   \   | |     | |
                |  |    |  |  |    )O-|-|-----|-|--
               -|--|----|--|--|___/   | |     | |
                |  |    |  |   ___    | |     | |
               -|--|----|--|--|   \   | |     | |
                |  |    |  |  |    )O-|-|-----|-|--
               -|--|----|--|--|___/   | |     | |
                |  |    |  |   ___    | |     | |
               -|--|----|--|--|   \   | |     | |
                |  |    |  |  |    )O-|-|-----|-|--
               -|--|----|--|--|___/   | |     | |
                |  |    |  |   ___    | |     | |
               -|--|----|--|--|   \   | |     | |
                |  |    |  |  |    )O-|-|-----|-|--
               -|--|----|--|--|___/   | |     | |
                |  |    |  |         _|_|_   _|_|_
      		              |     | |     |
      		              |     | |     |
      		               \___/   \___/
      		                 O       O
      		                 |       |
      		                 |       |
      		                 X       Y
      		                  outputs
      	
      Note that it is common to draw all gates as nand gates, and note that a 1-input nand gate is just an inverter.

    3. Interconnect following the truth table.
      Specifically, wherever there is a 1 in in input column of the truth table, connect the un-inverted input to the gate for the corresponding row, and wherever there is a zero, connect the inverted input to the gate. Then, in the output column, connect the output of the gate for the row to the gate for the column.
      	    input 
                A       B
                |       |
                o--     o--
                | _|_   | _|_
                | \ /   | \ /
                |  O    |  O
                |  |    |  |   ___
               -|--o----|--|--|   \   | |     | |
                |  |    |  |  |    )O-|-|-----o-|--
               -|--|----|--o--|___/   | |     | |
                |  |    |  |   ___    | |     | |
               -|--o----|--|--|   \   | |     | |
                |  |    |  |  |    )O-o-|-----|-|--
               -|--|----o--|--|___/   | |     | |
                |  |    |  |   ___    | |     | |
               -o--|----|--|--|   \   | |     | |
                |  |    |  |  |    )O-|-o-----|-|--
               -|--|----|--o--|___/   | |     | |
                |  |    |  |   ___    | |     | |
               -o--|----|--|--|   \   | |     | |
                |  |    |  |  |    )O-|-|-----|-o--
               -|--|----o--|--|___/   | |     | |
                |  |    |  |         _|_|_   _|_|_
      		              |     | |     |
      		              |     | |     |
      		               \___/   \___/
      		                 O       O
      		                 |       |
      		                 |       |
      		                 X       Y
      		                  outputs
      	
      The above is frequently abbreviated by drawing all gates as 1-input gates with multiple connections to their input lines.

    Optimization techniques can be used to simplify circuits by eliminating rows from the table, saving one gate per row, but this has no effect on the speed unless fanout considerations are examined! This proves that, in theory, all combinational logic functions can be realized in exactly 3 levels of logic, or 3 gate delays, if each gate has a constant delay.

    If no optimization is used, the above algorithm yields a ROM for the indicated function. If optimization is used, the algorithm yields a PLA or programmable logic array realization of the circuit.

  5. Tristate Logic

    Tristate logic is not logic that deals in, for example, 1, 0, and -1 as numeric values, or true, false and perhaps as logic values. When this is intended, we will use terms like three-valued logic.

    Tristate bus drivers are devices that, in addition to being able to drive their output to one or zero are also able to disconnect their output. Thus, if there are many tristate drivers connected to a bus line, any one of them may drive the line true or false, but if two of them attempt, simultaneously, to drive the line, a problem will arise when one drives the line up while the other drives the line down.

    Tristate devices are not essential! It is always possible to replace a bus line with many tristate drivers by an equivalent multiplexor, but such replacements are physically inconvenient. One way of thinking of tristate drivers and bus lines is to think of them as distributed implementations of multiplexors.

  6. Sequential Logic

    Logic circuits with feedback are sequential circuits. Consider the following:

                  _          ___
                  R --------|   \
                            |    )O---o--- Q
                          --|___/     |
                  _      |   ___      |
                  S -----|--|   \     |    _
                         |  |    )O-o-|--- Q
                       --|--|___/   | |
                      |  |          | |
                      |   ----------  |
                       ---------------
    
    	
    Here, treat Q and Qbar as distinct letters and, for the moment ignore the fact that the bar means negation.

    We can describe the above circuit by a system of boolean equations:

    	    _      _
    	Q = Q nand R
            _          _
    	Q = Q nand S
    
    	
    For some combinations of values of Rbar and Sbar, we can solve these equations. We get the following:
             _   _       _
    	 R   S | Q   Q
    	-------|-------
    	 0   0 | 1   1
    	 0   1 | 1   0
    	 1   0 | 0   1
    	 1   1 | ?   ?
    	
    	
    In the case of [Rbar Sbar] = [1 1], an attempt at solution merely simplifies our two equations to:
    	    _              _
    	Q = Q nand 1 = not Q
    	_                   
    	Q = Q nand 1 = not Q
    
    	
    There are two solutions to this set of 2 Boolean equations in 2 unknowns, [Q Qbar] = [1 0] is one, and [Q Qbar] = [0 1] is the other. In general, when there is feedback in a combinational circuit, it can be analyzed in this way, reducing the problem to a set of n equations in n unknowns for each of the possible combinations of external inputs, where there are n bits of feedback.

    For the above circuit, note that we can set a value of [Q Qbar] by setting the inputs [Rbar Sbar] to [0 1] or to [1 0] and then, if we shift [Rbar Sbar] to [1 1], the circuit will stay in that state indefinitely. We call this circuit an RS Flipflop, and we say that we can set the state of the flipflop by a negative pulse on one or the other inputs. So long as we avoide the state [Rbar Sbar] = [0 0], the circuit is an excellent memory circuit.

    RS flipflops are common enough that there is a standard schematic symbol for the circuit:

    		_______
    	       |_      |
    	 ------|R     Q|-----
    	       |       |
    	       |       |
    	       |_     _|
    	 ------|S     Q|-----
    	       |_______|
    
    	
    The R S flipflop circuit is not well matched to the needs of the user, because neither input is equal to the value we wish to store. This motivates the development of the type D latch.
                       ____        _______ 
            D--o------|    \      |_      |
              _|_     |     )O----|R     Q|-----
              \ /  ---|____/      |       |
               O  |    ____       |       |
                --|---|    \      |_     _|
                  |   |     )O----|S     Q|-----
            C-----o---|____/      |_______|
    
            
    With the addition of two nand gates and an inverter, we can store the value of the D input in the flipflop whenever the C input is high, and remember that value indefinitely when the C input is low. D latches are commonly used to construct registers in applications where the exact moment at which the D input is sampled is not critical. The D latch is frequently drawn using the following symbol:
    		_______
    	       |       |
    	 ------|D     Q|-----
    	       |   _   |
    	       | _| |_ |
    	       |      _|
    	 ------|>C    Q|-----
    	       |_______|
    
    	
    When a flipflop symbol contains a little graph of a pulse or other waveform, the graph indicates the nature of the input to the clock terminal C that will cause the flipflop to change state or remember its input. In this case, we have a positive pulse triggered D latch because the positive pulse causes the D input to appear on the Q output. The clock input to a flipflop symbol is frequently distinguished by the little triangle inside the symbol!

  7. Master Slave Flipflops

    The problem with the D latch is that, if the input changes while the clock pulse is in progress, it is hard to control the value that will be stored. This motivates the development of edge triggered and master slave flipflops. Consider the following:

    		_______              _______
    	 D     |       |      D'    |       |
    	 ------|D     Q|------------|D     Q|-----
    	       |   _   |            |   _   |
    	       | _| |_ |            | _| |_ |
    	       |      _|            |      _|
    	    ---|>C    Q|-        ---|>C    Q|-----
    	   |   |_______|        |   |_______|
    	   |                    O
    	   |                   /_\
    	   |                    |
    	 C |                    |
    	 --o--------------------
    
    	
    In the above circuit, because the 2 type D latches have clock inputs that are inverted relative to each other, changes in D never directly affect the output. However, when C is 0, the value of D appears at D', and as C changes from 0 to 1, D' is held constant and transferred to the Q output. Thus, we say that the externally observable state of this flipflop changes on the leading edge of a (positive) pulse on the C input. Because it has 2 stages, we call it a master-slave flipflop, and because its basic behavior is like a D latch, we call it a leading edge triggered master-slave D flipflop. In schematic diagrams, this is frequently abbreviated as:
    		_______
    	       |       |
    	 ------|D     Q|-----
    	       |    _  |
    	       |  _|   |
    	       |      _|
    	 ------|>C    Q|-----
    	       |_______|
    
    	
    Here, the little graph inside the box indicates that it is leading-edge triggered. Commercially produced D flipflops are always produced by optimization of the design outlined here. The behavior is the same, but the number of gate delays from input to output is significantly reduced, and the existance of distinct master and slave stages in the flipflop is greatly obscured.

    There are also JK flipflops, but their use is largely confined to optimal implementation of sequential circuits such as counters, and as a result, they are not important in this course, where optimizaiton is not a subject of discussion. Take a good digital logic course if you wish to optimize the function of digital circuits.