Combinatorial circuits: Without Status

ion with the Karnaugh mapStep 2: Determine all prime implicants 1111111111wxyz11w’x’z’x’y’z’11w’yyz11111111wz1111wx’y’1111Rule:- Analyze each 1-minterm- Determine the largest sub-cube(s)that contain(s) the minterm andadd them to the list of primeimplicants (without adding analready listed sub-cube)19Minimization with the Karnaugh mapStep 3: Determine all essential prime implicants1111111111wxyzw’x’z’x’y’z’w’yyzwzwx’y’11wzw’yRule:- Search for 1-minterms that areonly contained in 1 prime implicant- Indicate this prime implicant asessential20Minimization with the Karnaugh mapStep 4: Search minimal coverage w’x’z’x’y’z’w’yyzwzwx’y’1111111111wxyz11111111120111x’y’z’Fmin=x’y’z’+w’y+wzRule:- Goal: search for the smallest set of (as big as possible)prime implicants that contain all 1-minterms- Take all essential prime implicants as initial list- Repeatedly add a prime implicant to the list that containsthe largest number of not yet covered 1-minterms. Whenthere are two that contain the same number of not yetcovered 1-minterms, make a random choice.	- Such a strategy is known as Greedy strategy: at each decision point,	take the best choice without looking to future implications	- This does not always lead to a global optimum21Minimization with the Karnaugh mapOriginal:F=x’y’z’+w’y+xyz+wzMinimalFmin=x’y’z’+w’y+wzwxyzwxyzCost=4*1+2*3+2*2+1*4=18Cost	=4*1+1*3+2*2+1*3=14	=22% cheaperDelay	=(1)+(.6+3*.4+1)	+(.6+4*.4+1)=7Delay	=(1)+(.6+3*.4+1)	+(.6+3*.4+1)=6.6	=6% faster22Minimization with the Karnaugh mapExample 2: F(v,w,x,y,z)23Minimization with the Karnaugh mapRealisation as sum of 1-minterms: F=(6,7,10,11,14,15,21,23,25,27,29,31)vwxyzCost=(5*1)+(12*(5+1))+(1*(12+1))=90Delay=(.6+1*.4)+(.6+5*.4+1)+(.6+12*.4+1)=1124Minimization with the Karnaugh mapMinimisationStep 1: Create Karnaugh map00000011001100110000011001100110wxyzzv25Minimization with the Karnaugh mapMinimisationStep 2: determine all prime implicants00000011001100110000011001100110wxyzzv2611111111Minimization with the Karnaugh mapMinimisationStep 3: Determine all essential prime implicants000000001100000000011000wxyzzv1111F1min2=v’xy+v’wy+vxz+vwzIs already the minimum coverage27Minimization with the Karnaugh mapRealisation of F1min2=v’xy+v’wy+vxz+vwz vwxyzCost=1+(4*(3+1))+(1*(4+1))=22 (76% cheaper)Delay=(.6+1*.4)+(.6+3*.4+1)+(.6+4*.4+1)=7 (34% faster)28Minimization with the Karnaugh mapRealisation in more than two layers F	=v’xy+v’wy+vxz+vwz	=v’y(x+w)+vz(x+w)	=(x+w)(v’y+vz)vwxyzCost	=(1*1)+(5*(2+1))=16	(82% cheaper)Delay	=(.6+1*.4)+(.6+2*.4+1)	+(.6+2*.4+1)+(.6+2*.4+1)	=8.2 (25% faster)29Minimization with the Karnaugh mapDual minimisationStep 1: Create the Karnaugh map00000011001100110000011001100110wxyzzv30Minimization with the Karnaugh mapDual minimisationStep 2: Determine all prime implicants00000011001100110000011001100110wxyzzv31Minimization with the Karnaugh mapDual minimisationStep 3: Determine all essential prime implicants00000011001100110000011001100110wxyzzv0000000000Is already the minimum coverageF0min2=(v+y)(w+x)(v’+z)32Minimization with the Karnaugh mapRealisation of F0min2=(v+y)(w+x)(v’+z)vwxyzCost=(1*1)+(3*(2+1))+(1*(3+1))=14 (84% cheaper)Delay=(.6+1*.4)+(.6+2*.4+1)+(.6+3*.4+1)=6.2 (44% faster)33Minimization with the Karnaugh mapSummaryArea/time trade-offWe’ll see that, depending on the technology mapping, we will eventually obtain for an ASIC realisation:	OR-AND-INV	Cost = 11 (Rel. cost=12%)	Delay = 4 (Rel. delay=36%)	NOR	Cost = 10 (Rel. cost=11%)	Delay = 4.2 (Rel. delay=38%)34Design of Combinatorial CircuitsMinimization of Boolean functionsKarnaugh mapMinimization with the Karnaugh mapDon’t care conditionsQuine-McCluskeyTechnology mappingCorrect timing behaviorBasic RTL building blocks (Adder, ALU, MUX, )35Don’t care conditionsIncompletely specified Boolean functionBCD7-segmentabcdefg36Don’t care conditionsStep 1: Create Karnaugh maps10110111xxxx11xx11111010xxxx11xx11101111xxxx11xx10110101xxxx11xx10010001xxxx10xx10001101xxxx11xx00111101xxxx11xxxxyyzzzzwwwwabcdefg37Don’t care conditionsStep 2: determine all prime implicants10110111xxxx11xx11111010xxxx11xx11101111xxxx11xx10110101xxxx11xx10010001xxxx10xx10001101xxxx11xx00111101xxxx11xxxxyyzzzzwwwwabcdefg38Don’t care conditionsStep 3: Determine all essential prime implicants10110111xxxx11xxxyzwaCompletecoverage11101111xxxx11xxzwcCompletecoverage10110101xxxx11xxzwdCompletecoverage10010001xxxx10xxxyeCompletecoverage10001101xxxx11xxfCompletecoverage00111101xxxx11xxgIncompletecoverage11111010xxxx11xxzwbCompletecoverage39Don’t care conditionsStep 4: Determine minimum coverage00111101xxxx11xxgSelection of the cube that realisesthe remaining minterm:	-	Select all cubes that realise	the minterm and are already	essential for another function;	in this case, both are already	essential	-	Select that cube that appears	in the smallest number of	other functions to keep the	fan-out as low as possible40Don’t care conditionsNote down the standard form10110111xxxx11xxxyzway’w’zywxa=y’w’+z+yw+x4111111010xxxx11xxzwbDon’t care conditionsNote down the standard formy’w’zywxa=y’w’+z+yw+xz’w’zwb=y’+z’w’+zwy’4211101111xxxx11xxzwcDon’t care conditionsNote down the standard formy’w’zywxa=y’w’+z+yw+xy’z’w’zwb=y’+z’w’+zwz’wyc=z’+w+y4310110101xxxx11xxzwdDon’t care conditionsNote down the standard formy’w’zywxa=y’w’+z+yw+xy’z’w’zwb=y’+z’w’+zwz’wyc=z’+w+yy’w’y’zyz’wzw’xd=y’w’+y’z+yz’w+zw’+x4410010001xxxx10xxxyeDon’t care conditionsNote down the standard formzywxa=y’w’+z+yw+xy’z’w’zwb=y’+z’w’+zwz’wyc=z’+w+yy’zyz’wzw’d=y’w’+y’z+yz’w+zw’+xy’w’y’w’zw’e=y’w’+zw’4510001101xxxx11xxfDon’t care conditionsNote down the standard formzywxa=y’w’+z+yw+xy’z’w’zwb=y’+z’w’+zwz’wyc=z’+w+yy’zyz’wzw’d=y’w’+y’z+yz’w+zw’+xe=y’w’+zw’z’w’yz’yw’xf=z’w’+yz’+yw’+xy’w’4600111101xxxx11xxgDon’t care conditionsNote down the standard formzywxa=y’w’+z+yw+xy’z’w’zwb=y’+z’w’+zwz’wyc=z’+w+yy’zyz’wzw’d=y’w’+y’z+yz’w+zw’+xe=y’w’+zw’yz’yw’f=z’w’+yz’+yw’+xyz’y’zyw’xg=y’z+yz’+yw’+xy’w’47Don’t care conditionsxyzwacbdefg48Don’t care conditionsCost when realising as (1-minterms):a: 4*1+8*(4+1)+1*(8+1)=53b: 4*1+8*(4+1)+1*(8+1)=53c: 4*1+9*(4+1)+1*(9+1)=59d: 4*1+7*(4+1)+1*(7+1)=47e: 4*1+4*(4+1)+1*(4+1)=29f: 4*1+6*(4+1)+1*(6+1)=41g: 4*1+7*(4+1)+1*(7+1)=47Cost for minimal 2-layer-implementationInvertors: 4*1=4AND-gates: 8*(2+1)+1*(3+1)=28OR-gates: 1*(2+1)+2*(3+1)+3*(4+1)	+1*(5+1)=32329 (100%)64 (19%)49Don’t care conditionsDelay when realising as (1-minterms):Critical path=c (9-input OR)c: (1)+(.6+4*.4+1)+(.6+9*.4+1)=9.4 (100%)Delay for minimal 2-layer-implementationCritical path=d (3-input AND & 5-input OR)d: (1)+(.6+3*.4+1)+(.6+5*.4+1)=7.4 (79%)50Design of Combinatorial CircuitsMinimization of Boolean functionsKarnaugh mapMinimization with the Karnaugh mapDon’t care conditionsQuine-McCluskeyTechnology mappingCorrect timing behaviorBasic RTL building blocks (Adder, ALU, MUX, )51Quine-McCluskeyMethod with Karnaugh mapOK for human minimisation : visually orientedno guarantee for optimum solutionComputer methodQuine-McCluskeytable orientedleads to optimum solutionis the basis of all CAD circuit design tools hardly doable by hand52Design of Combinatorial CircuitsMinimization of Boolean functionsTechnology mappingGate arrays: NAND, NORCustom library: AOI, OAI, PLAFPGACorrect timing behaviorBasic RTL building blocks (Adder, ALU, MUX, )53Design of Combinatorial CircuitsMinimization of Boolean functionsTechnology mappingGate arrays: NAND, NORCustom library: AOI, OAI, PLAFPGACorrect timing behaviorBasic RTL building blocks (Adder, ALU, MUX, )54Technology Mapping:Gate ArraysProperties of the methodology followed:When minimizing 1-minterms: INV-AND-ORWhen minimizing 0-maxterms: INV-OR-ANDAny function can be realized in two layers of logic with this methodologyThe fan-in of the gates can become arbitrary largeProperties of gate arrays:They only contain m-input NAND or m-input NOR gatesTechnology mapping is:Translating a circuit consisting of INV-AND-OR to one with only m-input NANDDual: INV-OR-AND  m-input NOR55Technology Mapping:Gate ArraysDesign flow:ConversionReplace each AND and ORby NAND or NOROptimisationEliminate double inversionsReplace each n-input AND(OR) by a few m-inputANDs (ORs), with m=64Xyy=1 when X<192x7x6yy=1 when X is evenx0yx7x6yX is8 bits126Design of Combinatorial CircuitsMinimization of Boolean functionsTechnology mappingCorrect timing behaviorBasic RTL building blocksRipple-carry addersCarry-look-ahead addersAdder/subtractorsMultipliersLogic unitsArithmetic-logic unitsDecodersSelectorsBusesPriority encodersMagnitude comparatorsShifters and rotators127Shifters and rotatorsShifter:An input word is shifted m positions to the left or to the rightm bits disappear at one sidem bits are created at the other sideFor an arithmetic shift (word = 2-complement)For a left shift m zeros are shifted in from the rightFor a right shift m times the MSB is shifted in from the left (for 2-complement)For a logic shiftIt is possible to indicate which value is shifted inm bit left shift is multiplication with 2mm bit right shift is division by 2m128Shifters and rotatorsRotator:An input word is shifted m positions to the left or to the rightThe bits that drop-off at one side, are shifted back in at the other side129Shifters and rotatorsd0d1d2d3S2S1S0L-inR-in4-to-1MUX4-to-1MUX4-to-1MUX4-to-1MUXMMy3y2y1y0S2: 0=no shift,1=shift S1: 0=left,1=right S0: 0=shift,1=rotate4-to-1MUX4-to-1MUX4-to-1MUX4-to-1MUXMMy3y2y1y0S2: 0=no shift,1=shift S1: 0=left,1=right S0: 0=shift,1=rotate4-to-1MUX4-to-1MUX4-to-1MUX4-to-1MUXMMy3y2y1y0S2: 0=no shift,1=shift S1: 0=left,1=right S0: 0=shift,1=rotate4-to-1MUX4-to-1MUX4-to-1MUX4-to-1MUXMMy3y2y1y0S2: 0=no shift,1=shift S1: 0=left,1=right S0: 0=shift,1=rotate4-to-1MUX4-to-1MUX4-to-1MUX4-to-1MUXMMy3y2y1y0S2: 0=no shift,1=shift S1: 0=left,1=right S0: 0=shift,1=rotate4-to-1MUX4-to-1MUX4-to-1MUX4-to-1MUXMMy3y2y1y0S2: 0=no shift,1=shift S1: 0=left,1=right S0: 0=shift,1=rotate130Shifters and rotatorsMMMMMMMMMMMMMMMMMMMMMMMMS0S1S28-bit barrel left rotator131