Examples of Solved Problems for Chapter3,5,6,7,and8

1 Chapter3 ExamplesofSolvedProblemsforChapter3,5,6, 7,and8 This document presents some typical Problems that the student may encounter, and shows how suchproblems can be Solved . Note that the numbering of Examples below is taken from the 2nd editionof the bookFundamentals of Digital Logic with VHDL Design. Since not all of these examplesare relevant to ECE241, the numbering of Examples , and some figure numbers, are not alwayssequential in this :We introduced standard cell technology in section In this technology, circuits arebuilt by interconnecting building-block cells that implement simple functions, like basic logic commonly used type of standard cell are the and-or-invert (AOI) cells, which can be efficientlybuilt as CMOS complex gates.

2 Consider the AOI cell shown in Figure This cell implementsthe functionf=x1x2+x3x4+x5. Derive the CMOS complex gate that implements this The AOI cell for Example :Applying Demorgan s theorem in two steps givesf=x1x2 x3x4 x5=(x1+x2) (x3+x4) x51 Since all input variables are complemented in this expression, we can directly derive the pull-upnetwork as having parallel-connected PMOS transistors controlled byx1andx2, in series withparallel-connected transistors controlled byx3andx4, in series with a transistor controlled circuit, along with the corresponding pull-down network, is shown in Figure Circuit for Example :For the CMOS complex gate in Figure , determine the sizes of transistors thatshould be used such that the speed performance of this gate is similar to that of an.

3 Recall from section that a transistor with lengthLand widthWhas a drivestrength proportional to the ratioW/L. Also recall that when transistors are connected in par-allel their widths are effectively added, leading to an increase in drive strength. Similarly, whentransistors are connected in series, their lengths are added, leading to a decrease in drive us assume that all NMOS and PMOS transistors have the same length,Ln=Lp= pull-down network in Figure , the worst-case path involves just a single NMOS , we can make the length,Ln, of each NMOS transistor the same size as in the inverter. For thepull-up network, the worst-case path involves three transistors in series. Since, as we said in , PMOS transistors have about half the drive strength of NMOS transistors, we should makethe effective size of the three PMOS transistors in series about twice that of an NMOS ,Lp=Ln 3 2=6 LnExample : Convert the decimal number 14959 into a hexadecimal : An integer is converted into the hexadecimal representation by successive divisions by16, such that in each step the remainder is a hex digit.

4 To see why this is true, consider a four-digitnumberH= 163+h2 162+h1 16 +h0If we divide this by 16, we obtainV16=h3 162+h2 16 +h1+h016 Thus, the remainder givesh0. Figure shows the steps needed to perform the conversion(14959)10= (3A6F) Conversion from decimal to : In computer computations it is often necessary to compare numbers. Two four-bitsigned numbers,X=x3x2x1x0andY=y3y2y1y0, can be compared by using the subtractor circuitin Figure , which performs the operationX Y. The three outputs denote the following: Z= 1 if the result is 0; otherwiseZ=0 N= 1 if the result is negative; otherwiseN=0 V= 1 if arithmetic overflow occurs; otherwiseV=0 Show howZ,N,andVcan be used to determine the casesX=Y,X<Y,X Y,X>Y,andX : Consider first the caseX<Y, where the following possibilities may arise: IfXandYhave the same sign there will be no overflow, henceV= 0.

5 Then for both positiveand negativeXandYthe difference will be negative (N=1).3 IfXis negative andYis positive, the difference will be negative (N= 1) if there is nooverflow (V= 0); but the result will be positive (N= 0) if there is overflow (V=1).Therefore, ifX<YthenN V= caseX=Yis detected byZ= 1. Then,X Yis detected byZ+(N V) = 1. The lasttwo cases are just simple inverses:X>YifZ+(N V)=1andX YifN V= A comparator : Implement the functionf(w1,w2,w3)= m(0,1,3,4,6,7) by using a 3-to-8 binarydecoder and an OR : The decoder generates a separate output for each minterm of the required outputs are then combined in the OR gate, giving the circuit in Figure Circuit for Example : Derive a circuit that implements an 8-to-3 binary : The truth table for the encoder is shown in Figure Only those rows for which asingle input variable is equal to 1 are shown.

6 The other rows can be treated as don t care the truth table it is seen that the desired circuit is defined by the equationsy2=w4+w5+w6+w7y1=w2+w3+w6+w7y0= w1+w3+w5+w7 Figure Truth table for a 3-to-8 binary : Implement the functionf(w1,w2,w3,w4)=w1w2w4w5+w1w2+w1w 3+w1w4+w3w4w5by using a 4-to-1 multiplexer and as few other gates as possible. Assume that only the uncomple-mented inputsw1,w2,w3,andw4are : Since variablesw1andw4appear in more product terms in the expression forfthanthe other three variables, let us perform Shannon s expansion with respect to these two expansion givesf=w1w4fw1w4+w1w4fw1w4+w1w4fw1w4+w1w 4fw1w4=w1w4(w2w5)+w1w4(w3w5)+w1w4(w2+w3) +w1w2(1)WecanuseaNORgatetoimplementw2w5= w2+w5. We also need an AND gate and an ORgate.

7 The complete circuit is presented in Figure Circuit for Example : In Chapter 4 we pointed out that the rows and columns of a Karnaugh map are labeledusing Gray code. This is a code in which consecutive valuations differ in one variable only. depicts the conversion between three-bit binary and Gray codes. Design a circuit that canconvert a binary code into a Gray according the Binary to Gray code : From the figure it follows thatg2=b2g1=b1b2+b1b2=b1 b2g0=b0b1+b0b16=b0 b1 Example : In section we showed that any logic function can be decomposed using Shannon sexpansion theorem. For a four-variable function,f(w1,..,w4), the expansion with respect tow1isf(w1,..,w4)=w1fw1+w1fw1A circuit that implements this expression is given in Figure (a) If the decomposition yieldsfw1= 0, then the multiplexer in the figure can be replaced by asingle logic gate.

8 Show this circuit.(b) Repeat partafor the case wherefw1= : The desired circuits are shown in parts (b)and(c) of Figure Circuits for Example : In several commercial FPGAs the logic blocks are 4-LUTs. What is the minimum7number of 4-LUTs needed to construct a 4-to-1 multiplexer with select inputss1ands0and datainputsw3,w2,w1,andw0?Solution: A straightforward attempt is to use directly the expression that defines the 4-to-1multiplexerf=s1s0w0+s1s0w1+s1s0w2+ s1s0w3 Letg=s1s0w0+s1s0w1andh=s1s0w2+s1s0w3,sot hatf=g+h. This decomposition leads tothe circuit in Figure , which requires three Circuits for Example designing logic circuits, one can sometimes come up with a clever idea which leads to asuperior implementation.

9 Figure how it is possible to implement the multiplexer withjust two LUTs, based on the following observation. The truth table in Figure thatwhens1= 0 the output must be eitherw0orw1, as determined by the value generated by the first LUT. The second LUT must make the choice betweenw2andw3whens1= 1. But, the choice can be made only by knowing the value ofs0. Since it is impossible tohave five inputs in the LUT, more information has to be passed from the first to the second that whens1= 1 the outputfwill be equal to eitherw2orw3, in which case it is not8necessary to know the values ofw0andw1. Hence, in this case we can pass on the value ofs0through the first LUT, rather thanw0orw1. This can be done by making the function of this LUTk=s1s0w0+s1s0w1+s1s0 Then, the second LUT performs the functionf=s1k+s1kw3+s1kw4 Example : In digital systems it is often necessary to have circuits that can shift the bits of a vectorby one or more bit positions to the left or right.

10 Design a circuit that can shift a four-bit vectorW=w3w2w1w0one bit position to the right when a control signalShiftis equal to 1. Let theoutputs of the circuit be a four-bit vectorY=y3y2y1y0and a signalk, such that ifShift=1theny3=0,y2=w3,y1=w2,y0=w1,andk = : The required circuit can be implemented with five 2-to-1 multiplexers as shown in TheShiftsignal is used as the select input to each A shifter : The shifter circuit in Example shifts the bits of an input vector by one bit positionto the right. It fills the vacated bit on the left side with 0. A more versatile shifter circuit may beable to shift by more bit positions at a time. If the bits that are shifted out are placed into thevacated positions on the left, then the circuit effectively rotates the bits of the input vector by aspecified number of bit positions.