WIXLIB

2.4Logic Minimization and Karnaugh MapsAs we found above, given a truth table, it is always possible to write down a correct logicexpression simply by forming an OR of the ANDs of all input variables for which the output istrue (Q 1). However, for an arbitrary truth table such a procedure could produce a verylengthy and cumbersome expression which might be needlessly inefficient to implement withgates.There are several methods for simplification of Boolean logic expressions. The process isusually called “logic minimization”, and the goal is to form a result which is efficient. Twomethods we will discuss are algebraic minimization and Karnaugh maps. For very complicated problems the former method can be done using special software analysis programs.Karnaugh maps are also limited to problems with up to 4 binary inputs.Let’s start with a simple example. The table below gives an arbitrary truth table involving2 logic inputs.Table 1: Example of simple arbitrary truth table.A B Q0 0 10 1 11 0 01 1 1There are two overall stategies:1. Write down an expression directly from the truth table. Use Boolean algebra, if desired,to simplify.2. Use Karnaugh mapping (“K-map”). This is only applicable if there are 4 inputs.In our example above, we can use two different ways of writin down a result directly fromthe truth table. We can write down all TRUE terms and OR the result. This givesQ ĀB̄ ĀB ABWhile correct, without further simplification this expression would involve 3 2-input ANDgates, 2 inverters, and 1 3-input OR gate.Alternatively, one can write down an expression for all of the FALSE states of the truthtable. This is simpler in this case:Q AB̄ Q AB̄ Ā Bwhere the last step results from Eqn. 3. Presumably, the two expressions can be found tobe equivalent with some algebra. Certainly, the 2nd is simpler, and involves only an inverterand one 2-input OR gate.8

Finally, one can try a K-map solution. The first step is to write out the truth table inthe form below, with the input states the headings of rows and columns of a table, and thecorresponding outputs within, as shown below.Table 2: K-map ofA\B 00110truth table.111The steps/rules are as follows:1. Form the 2-dimensional table as above. Combine 2 inputs in a “gray code” way – see2nd example below.2. Form groups of 1’s and circle them; the groups are rectangular and must have sides oflength 2n 2m , where n and m are integers 0, 1, 2, . . .3. The groups can overlap.4. Write down an expression of the inputs for each group.5. OR together these expressions. That’s it.6. Groups can wrap across table edges.7. As before, one can alternatively form groups of 0’s to give a solution for Q.8. The bigger the groups one can form, the better (simpler) the result.9. There are usually many alternative solutions, all equivalent, some better than othersdepending upon what one is trying to optimize.A\BHere is one way of doing it:01The two groups we have drawn010are111Ā and B. So the solution (as before) is:Q Ā B2.4.1K-map Example 2Let’s use this to determine which 3-bit numbers are prime. (This is a homework problem.)We assume that 0, 1, 2 are not prime. We will let our input number have digits a2 a1 a0 . Hereis the truth table:Here is the corresponding K-map and a solution.Note that where two inputs are combined in a row or column that their progressionfollows gray code, that is only one bit changes at a time. The solution shown above is:Q a1 a0 a2 a0 a0 (a1 a2 )9

Table 3: 3-digitDecimal a20001200341151671prime finder.a1 a0 Q0 000 101 001 110 000 111 001 11Table 4: K-mapa2 \a1 a0 000001of truth table.01 11 100 1 01 1 010

2.4.2K-map Example 3: Full AdderIn this example we will outline how to build a digital full adder. It is called “full” becauseit will include a “carry-in” bit and a “carry-out” bit. The carry bits will allow a successionof 1-bit full adders to be used to add binary numbers of arbitrary length. (A half adderincludes only one carry bit.)aiabibCinΣCoutCiniSiSCoutiFigure 7: Block schematic of full adder. (We name our adder the “Σ chip”).The scheme for the full adder is outlined in Fig. 7. Imagine that we are adding two n-bitbinary numbers. Let the inputs ai and bi be the i-th bits of the two numbers. The carry inbit Cini represents any carry from the sum of the neighboring less significant bits at positioni 1. That is, Cini 1 if ai 1 bi 1 1, and is 0 otherwise. The sum Si at position i istherefore the sum of ai , bi , and Cini . (Note that this is an arithmetic sum, not a BooleanOR.) A carry for this sum sets the carry out bit, Couti 1, which then can be applied to thesum of the i 1 bits. The truth table is given uti00010111With Cini 0, we see that the output sum Si is just given by the XOR operation, ai bi .And with Cini 1, then Si ai bi . Perhaps the simplest way to express this relationshipis the following:Si Cini (ai bi )To determine a relatively simple expression for Couti , we will use a K-map:Cini \ai bi0100 010 00 11111 101 01 1

This yieldsCouti ai bi Cini ai Cini bi ai bi Cini (ai bi )which in hardware would be 2 2-input OR gates and 2 2-input AND gates.As stated above, the carry bits allow our adder to be expanded to add any number ofbits. As an example, a 4-bit adder circuit is depicted in Fig. 8. The sum can be 5 bits, wherethe MSB is formed by the final carry out. (Sometimes this is referred to as an abΣCoutCinSabΣCoutCinSabΣCoutCinSSSS3210Figure 8: Expansion of 1-bit full adder to make a 4-bit adder.2.4.3Making a Multiplier from an AdderIn class we will discuss how to use our full adder (the “Σ chip”) to make a multiplier.2.5MultiplexingA multiplexer (MUX) is a device which selects one of many inputs to a single output. Theselection is done by using an input address. Hence, a MUX can take many data bits andput them, one at a time, on a single output data line in a particular sequence. This is anexample of transforming parallel data to serial data. A demultiplexer (DEMUX) performsthe inverse operation, taking one input and sending it to one of many possible outputs.Again the output line is selected using an address.A MUX-DEMUX pair can be used to convert data to serial form for transmission, thusreducing the number of required transmission lines. The address bits are shared by the MUXand DEMUX at each end. If n data bits are to be transmitted, then after multiplexing, thenumber of separate lines required is log2 n 1, compared to n without the conversion toserial. Hence for large n the saving can be substantial. In Lab 2, you will build such asystem.Multiplexers consist of two functionally separate components, a decoder and some switchesor gates. The decoder interprets the input address to select a single data bit. We use theexample of a 4-bit MUX in the following section to illustrate how this works.2.5.1A 4-bit MUX DesignWe wish to design a 4-bit multiplexer. The block diagram is given in Fig. 9. There are 4input data bits D0 –D3 , 2 input address bits A0 and A1 , one serial output data bit Q, and12

an (optional) enable bit E which is used for expansion (discussed later). First we will designthe decoder.ED3D2D1D0MUXGATES/SWITCHESQC3 C2 C1 C0A1A0DECODERFigure 9: Block diagram of 4-bit MUX.We need m address bits to specify 2m data bits. So in our example, we have 2 addressbits. The truth table for our decoder is 01The implementation of the truth table with standard gates is also straightforward, asgiven in Fig. 10.C3C2C1C0A1A0Figure 10: Decoder for the 4-bit MUX.For the “gates/switches” part of the MUX, the design depends upon whether the inputdata lines carry digital or analog signals. We will discuss the analog possibility later. Thedigital case is the usual and simplest case. Here, the data routing can be accomplished13

simply by forming 2-input ANDs of the decoder outputs with the corresponding data input,and then forming an OR of these terms. Explicitly,Q C 0 D0 C 1 D1 C 2 D2 C 3 D3Finally, if an ENABLE line E is included, it is simply ANDed with the righthand side of thisexpression. This can be used to switch the entire MUX IC off/on, and is useful for expansionto more bits. as we shall see.14

3Flip-Flops and Introductory Sequential LogicWe now turn to digital circuits which have states which change in time, usually accordingto an external clock. The flip-flop is an important element of such circuits. It has theinteresting property of memory: It can be set to a state which is retained until explicitlyreset.3.1Simple LatchesThe following 3 figures are equivalent representations of a simple circuit. In general theseare called flip-flops. Specifically, these examples are called SR (“set-reset”) flip-flops, or SRlatches.SSQQRQQRFigure 11: Two equivalent versions of an SR flip-flop (or “SR latch”).SQQRFigure 12: Yet another equivalent SR flip-flop, as used in Lab 3.The truth table for the SR latch is given below.S1001S0110R0101R QQ1 100 011 retains previous0 00The state described by the last row is clearly problematic, since Q and Q should not bethe same value. Thus, the S R 1 inputs should be avoided.From the truth table, we can develop a sequence such as the following:15

1. R 0, S 1 Q 1 (set)2. R 0, S 0 Q 1 (Q 1 state retained: “memory”)3. R 1, S 0 Q 0 (reset)4. R 0, S 0 Q 0 (Q 0 state retained)In alternative language, the first operation “writes” a true state into one bit of memory.It can subsequently be “read” until it is erased by the reset operation of the third line.3.1.1Latch Example: Debounced SwitchA useful example of the simple SR flip-flop is the debounced switch, like the ones on the labprototyping boards. The point is that any simple mechanical switch will bounce as it makescontact. Hence, an attempt to provide a simple transition from digital HIGH to LOW with amechanical switch may result in an unintended series of transitions between the two statesas the switch damps to its final position. So, for example, a digital counter connected to Qwould count every bounce, rather than the single push of the button which was intended.The debounced configuration and corresponding truth table are given below. When theswitch is moved from A to B, for example, the output Q goes LOW. A bounce would resultin A B 1, which is the “retain previous” state of the flip-flop. Hence, the bounces donot appear at the output Q. 5 V1kQAB1k 5 VFigure 13: A debounced switch.A1010B0110Q01retains previousnot allowed16

3.2Clocked Flip-flopsWe will soon get used to the idea of a clock as an essential element of digital circuitry.When we speak of a clock signal, we mean a sequence of evenly spaced digital high and lowsignals proceeding at a fixed frequency. That is, the clock is a continuous sequence of squarewave pulses. There are a number of reasons for the importance of the clock. Clearly it isessential for doing any kind of counting or timing operation. But, its most important roleis in providing synchronization to the digital circuit. Each clock pulse may represent thetransition to a new digital state of a so-called “state machine” (simple processor) we willsoon encounter. Or a clock pulse may correspond to the movement of a bit of data from onelocation in memory to another. A digital circuit coordinates these various functions by thesynchronization provided by a single clock signal which is shared throughout the circuit. Amore sophisticated example of this concept is the clock of a computer, which we have cometo associate with processing speed (e.g. 330 MHz for typical current generation commercialprocessors.)We can include a clock signal to our simple SR flip-flop, as shown in Fig. 14. The truthtable, given below, follows directly from our previous SR flip-flop, except now we include alabel for the nth clock pulse for the inputs and the output. This is because the inputs have noeffect unless they coincide with a clock pulse. (Note that a specified clock pulse conventionallyrefers to a HIGH level.) As indicated in the truth table, the inputs Sn Rn 0 represent theflip-flop memory state. Significantly, one notes that the interval between clock pulses alsocorresponds to the “retain previous state” of the flip-flop. Hence the information encodedby the one bit of flip-flop memory can only be modified in synchronization with the clock.SQRQCLKFigure 14: A clocked SR flip-flop.Sn1001Rn0101Qn10Qn 1avoidWe are now set to make a subtle transition for our next version of the clocked flip-flop.The flip-flop memory is being used to retain the state between clock pulses. In fact, thestate set up by the S and R inputs can be represented by a single input we call “data”, or17

D. This is shown in Fig. 15. Note that we have explicitly eliminated the bad S R 1state with this configuration.We can override this data input and clock sychronization scheme by including the “jamset” (S) and “jam reset” (R) inputs shown in Fig. 15. These function just as before withthe unclocked SR flip-flop. Note that these “jam” inputs go by various names. So sometimesthe set is called “preset” and reset is called “clear”, for example.SDQQRCLKFigure 15: A “D-type transparent” flip-flop with jam set and reset.A typical timing diagram for this flip-flop is given in Fig. 16. Note that the jam resetsignal R overrides any action of the data or clock inputs.CLKDRQFigure 16: Example of timing diagram for the transparent D flip-flop. (It is assumed that Sis held HIGH throughout.)3.2.1Edge Triggered Flip-FlopsWe need to make one final modification to our clocked flip-flop. Note that in the timingdiagram of Fig. 16 that there is quite a bit of apparent ambiguity regarding exactly whenthe D input gets latched into Q. If a transition in D occurs sometime during a clock HIGH, forexample, what will occur? The answer will depend upon the characteristics of the particularelectronics being used. This lack of clarity is often unacceptable. As a point of terminology,18

the clocked flip-flop of Fig. 15 is called a transparent D-type flip-flop or latch. (An examplein TTL is the 7475 IC.)The solution to this is the edge-triggered flip-flop. We will discuss how this works for oneexample in class. It is also discussed some in the text. Triggering on a clock rising or fallingedge is similar in all respects to what we have discussed, except that it requires 2–3 coupledSR-type flip-flops, rather than just one clocked SR flip-flop. The most common type is thepositive-edge triggered D-type flip-flop. This latches the D input upon the clock transitionfrom LOW to HIGH. An example of this in TTL is the 7474 IC. It is also common to employ anegative-edge triggered D-type flip-flop, which latches the D input upon the clock transitionfrom HIGH to LOW.The symbols used for these three D-type flip-flops are depicted in Fig. 17. Note thatthe small triangle at the clock input depicts positive-edge triggering, and with an inversionsymbol represents negative-edge triggered. The JK type of flip-flop is a slightlier fancierversion of the D-type which we will discuss briefly later. Not shown in the figure are thejam set and reset inputs, which are typically included in the flip-flop IC packages. In timingdiagrams, the clocks for edge-triggered devices are indicated by arrows, as shown in Fig. 18.DQDCLKQDCLKQCLKJCLKQKFigure 17: Symbols for D-type and JK flip-flops. Left to right: transparent D-type, positiveedge triggered D-type, negative-edge triggered D-type, and positive-edge triggered JK-type.CLKCLKFigure 18: Clocks in timing diagrams for positive-edge triggered (left) and negative-edgetriggered (right) devices.For edge-triggered devices, the ambiguity regarding latch timing is reduced significantly.But at high clock frequency it will become an issue again. Typically, the requirements areas follows: The data input must be held for a time tsetup before the clock edge. Typically, tsetup 20 ns or less. For some ICs, the data must be held for a short time thold after the clock edge. Typicallythold 3 ns, but is zero for most newer ICs. The output Q appears after a short propagation delay tprop of the signal through thegates of the IC. Typically, tprop 10 ns.19

From these considerations we see that for clocks of frequency much less than 1/(10ns) 100 MHz, these issues will be unimportant, and we can effectively consider the transitionsto occur instantaneously in our timing diagrams.20

4Counters, Registers, and State MachinesWe can now apply what we know about basic flip-flops circuit elements to develop newfunctions: counters and registers. In doing so, we will introduce the “state machine”, aclocked sequential “processor”. We will examine this latter topic in more detail in a fewweeks.4.1Divide by Two CounterThe edge-triggered D-type flip-flops which we introduced in the previous Section are quiteuseful and versatile building blocks of sequential logic. A simple application is the divide-by-2counter shown in Fig. 19, along with the corresponding timing diagram.INDINQOUTQ OUTCLKQD QFigure 19: Positive edge-triggered D-type flip-flop connected as divide-by-2 counter.4.1.1Using the JK Flip-flopIn Lab 4 you will build an asynchronous (ripple) counter using a sequence of cascaded JKflip-flops, rather than the D-type which is used in our discussion below. For reference, theJK truth table is given in Fig. 20. Note that there is no fundamental advantage to usingthe JK instead of the D-type, only that the JK, with the additional J K 1 state, makesthe divide-by-2 function slightly simpler to implement.JCLKQKJn100Kn010Qn10Qn 111Qn 1Figure 20: The JK Flip-flop.21

4.2Asynchronous CounterFlip-flops can be connected in series, as shown in Fig. 21. The resulting outputs are givenin Fig. 22. (Note that labels in these two figures correspond when A 20 , B 21 , C 22 ,and D 23 . Hence, this is a 4-bit counter, with maximum count 24 1 15. It is clearlypossible to expand such a counter to an indefinite number of bits.While asynchronous counters are easy to assemble, they have serious drawbacks for someapplications. In particular, the input must propogate through the entire chain of flip-flopsbefore the correct result is achieved. Eventually, at high input rate, the two ends of the chain,representing the LSB and MSB, can be processing different input pulses entirely. (Perhapsin lab you can see this effect on the oscilloscope with a very high input frequency.) Thesolution to this is the synchronous counter, which we will discuss below as an example of astate machine.2DIN02DQ12DQ2DQ3QCLKQCLKQCLKQCLKQ2Figure 21: Asynchronous (“ripple”) counter made from cascaded D-type flip-flops.01234567891011121314INABCDFigure 22: Waveforms generated by the ripple counter.2215

4.3Registers4.3.1Basic RegisterThe figure below represents a 4-bit memory. We can think of it as 4 individual D-typeflip-flops. The important point about a data register of this type is that all of th

The basic logic gates are AND, OR, NAND, NOR, XOR, INV, and BUF. The last two are not standard terms; they stand for \inverter" and \bu er", respectively. The symbols for these gates and their corresponding Boolean expressions are given in Table 8.2 of the text which, for convenience, is rep