WIXLIB

Expression in POS form Apply DeMorgans and takecomplement, i.e., f is now in SOP form Fill in zeros in table, i.e., plot f Fill remaining cells with ones, i.e., plot f Simplify in usual way by grouping onesto simplify f

Don’t Care Conditions Sometimes we do not care about theoutput value of a combinational logiccircuit, i.e., if certain input combinationscan never occur, then these are knownas don’t care conditions. In any simplification they may be treatedas 0 or 1, depending upon which givesthe simplest result.– For example, in a K-map they are enteredas Xs

Don’t Care Conditions - Example Simplify the function f a .b .d a .c.d a.c.dWith don’t care conditions, a .b .c .d , a .b .c.d , a .b.c .dccd00 01 11 10ab00 X 1 1 XX 1011a 11110bSee only need to includeXs if they assist in makinga bigger group, otherwisecan ignore.c.da.bdf a .b c.d or,f a .d c.d

Some Definitions Cover – A term is said to cover a minterm if thatminterm is part of that term Prime Implicant – a term that cannot be furthercombined Essential Term – a prime implicant that covers aminterm that no other prime implicant covers Covering Set – a minimum set of primeimplicants which includes all essential terms plusany other prime implicants required to cover allminterms

Number Representation,Addition and Subtraction

Binary Numbers It is important to be able to representnumbers in digital logic circuits– for example, the output of a analogue to digitalconverter (ADC) is an n-bit number, where n istypically in the range from 8 to 16 Various representations are used, e.g.,– unsigned integers– 2’s complement to represent negative numbers

Binary Numbers Binary is base 2. Each digit (known as abit) is either 0 or 1. Consider these 6-bit unsigned numbers1 0 1 0 1 0 421032 16 8 4 2 1 Binary25 24 23 22 21 20 coefficientsMSBLSB 11100 0 1 0 1 132 16 8 4 2 1 Binary25 24 23 22 21 20 coefficientsMSBLSBMSB – mostsignificant bitLSB – leastsignificant bit

Unsigned Binary Numbers In general, an n-bit binary number, bn 1bn 2 b1b0has the decimal value,n 1 bi 2ii 0 So we can represent positive integers from0 to 2n 1 In computers, binary numbers are often 8bits long – known as a byte A byte can represent unsigned values from0 to 255

Unsigned Binary Numbers Decimal to binary conversion. Performsuccessive division by 2.– Convert 4210 into binary42 / 2 21 remainder 021 / 2 10 remainder 110 / 2 5 remainder 05 / 2 2 remainder 12 / 2 1 remainder 01 / 2 0 remainder 1 So the answer is 1010102 (reading upwards)

Octal: Base 8 We have seen base 2 uses 2 digits (0 & 1),not surprisingly base 8 uses 8 digits : 0, 1,2, 3, 4, 5, 6, 7.0 5 2 421064 8 1 Octal82 81 80 coefficientsMSBLSB To convert from decimal to base 8 eitheruse successive division, i.e.,42 / 8 5 remainder 25 / 8 0 remainder 5 So the answer is 528 (reading upwards)

Octal: Base 8 Or alternatively, convert to binary, dividethe binary number into 3-bit groups andwork out the octal digit to representeach group. We have shown that4210 1010102 So,1MSB051 01 028LSB 4210

Hexadecimal: Base 16 For base 16 we need 16 different digits.Consequently we need new symbols forthe digits to represent 10-1510102 1010 A1611012 1310 D1610112 1110 B1611102 1410 E1611002 1210 C1611112 1510 F160 2 A16 4210256 16 1 Hex162 161 160 coefficientsMSBLSB

Hex: Base 16 To convert from decimal to base 16 useeither use successive division by 16, i.e.,42 / 16 2 remainder A2 / 16 0 remainder 2 So the answer is 2A8 (reading upwards)

Hex: Base 16 Or alternatively, convert to binary, dividethe binary number into 4-bit groups andwork out the hex digit to represent eachgroup. We have shown that4210 1010102 So,0 0 12MSB010 1 0A16LSB 4210

Hex: Base 16 Hex is also used as a convenient way ofrepresenting the contents of a byte (an8 bit number), so for example 1110001021 1 1EMSB000 1 0216LSB E 216

Negative numbers So far we have only been able to representpositive numbers. For example, we haveseen an 8-bit byte can represent from 0 to255, i.e., 28 256 different combinations ofbits in a byte If we want to represent negative numbers,we have to give up some of the range ofpositive numbers we had before– A popular approach to do this is called 2’scomplement

2’s Complement For 8-bit numbers:00Hpositive127 1287 FH 80Hnegative 1FFH Note all negative numbers have theMSB set The rule for changing a positive 2’scomplement number into a negative 2’scomplement number (or vice versa) is:Complement all the bits and add 1.

2’s Complement What happens when we do this to an 8 bitbinary number x ?– Invert all bits: x (255 x)– Add 1: x (256 x) Note: 256 ( 100H) will not fit into an 8 bitbyte. However if we ignore the ‘overflow’ bit,then 256 x behaves just like 0 x That is, we can use normal binary arithmeticto manipulate the 2’s complement of x and itwill behave just like -x

2’s Complement Addition0 0 0 0 0 1 1 170 0 0 0 0 1 0 0 4(0) 0 0 0 0 1 0 1 1 11 To subtract, negate the second number, then add:70 0 0 0 0 1 1 11 1 1 1 1 0 0 1 7(1) 0 0 0 0 0 0 0 000 0 0 0 1 0 0 191 1 1 1 1 0 0 1 7(1) 0 0 0 0 0 0 1 02

2’s Complement Addition0 0 0 0 0 1 0 041 1 1 1 1 0 0 1 7( 0) 1 1 1 1 1 1 0 1 31 1 1 1 1 0 0 1 71 1 1 1 1 0 0 1 7(1) 1 1 1 1 0 0 1 0 14

2’s Complement Note that for an n-bit number bn 1bn 2 b1b0 ,the decimal equivalent of a 2’s complementnumber is,n 2 bn 1 2n 1 ib 2 ii 0 For example, 1 1 1 1 0 0 1 06 b7 27 bi 2ii 0 1 27 1 26 1 25 1 24 1 21 128 64 32 16 2 14

2’s Complement Overflow For example, when working with 8-bitunsigned numbers, we can use the‘carry’ from the 8th bit (MSB) to indicatethat the number has got too big. With signed numbers we deliberatelyignore any carry from the MSB,consequently we need a new rule todetect when a result is out of range.

2’s Complement Overflow The rule for detecting 2’s complementoverflow is:– The carry into the MSB does not equal thecarry out from the MSB. We will now give some examples.

2’s Complement Overflow0 0 0 0 1 1 1 1150 0 0 0 1 1 1 1 15(0) 0 0 0 1 1 1 1 0 30OK0 1 1 1 1 1 1 1 1270 0 0 0 0 0 0 1 1(0) 1 0 0 0 0 0 0 0 128 overflow

2’s Complement Overflow1 1 1 1 0 0 0 1 151 1 1 1 0 0 0 1 15(1) 1 1 1 0 0 0 1 0 30 OK1 0 0 0 0 0 0 1 1271 1 1 1 1 1 1 0 2(1) 0 1 1 1 1 1 1 1 127 overflow

Binary Coded Decimal (BCD) Each decimal digit of a number is codedas a 4 bit binary quantity It is sometimes used since it is easy tocode and decode, however it is not anefficient way to store numbers.124810 0001 0010 0100 1000BCD123410 0001 0010 0011 0100BCD

Alphanumeric Character Codes ASCII: American Standard Code forInformation Exchange:– Standard version is a 7 bit code with theremaining bit usually set to zero– The first 32 are ‘control codes’ originally usedfor controlling modems– The rest are upper and lower case letters,numbers and punctuation.– An extended version uses all 8 bits toprovide additional graphics characters

Alphanumeric Character Codes EBCDIC – a legacy IBM scheme, now littleused Unicode – a 16 bit scheme, includesChinese characters etc.

Binary Adding Circuits We will now look at how binary additionmay be implemented using combinationallogic circuits. We will consider:– Half adder– Full adder– Ripple carry adder

Half Adder Adds together two, single bit binarynumbers a and b (note: no carry input) Has the following truth table:a bcout sum0011000101010110 By inspection:asumbcoutsum a .b a.b a bcout a.b

Full Adder Adds together two, single bit binarynumbers a and b (note: with a carry input)asumbcoutcin Has the following truth table:

Full Addercin a bcout sum000011110001011100110011So,0101010101101001sum cin .a .b cin .a.b cin .a .b cin .a.bsum cin .(a .b a.b ) cin .(a .b a.b)From DeMorgana .b a.b (a b).(a b ) (a.a a.b b.a b.b ) (a.b b.a )sum cin .(a .b a.b ) cin .(a .b a.b )sum cin .x cin .x cin x cin a b

Full Addercin a bcout sum0000111100010111001100110101010101101001cout cin .a.b cin .a .b cin .a.b cin .a.bcout a.b.(cin cin ) cin .a .b cin .a.bcout a.b cin .a .b cin .a.bcout a.(b cin .b ) cin .a .bcout a.(b cin ).(b b ) cin .a .bcout b.(a cin .a ) a.cin b.(a cin ).(a a ) a.cincout b.a b.cin a.cincout b.a cin .(b a )

Full Adder Alternatively,cin a bcout sum0000111100010111001100110101010101101001cout cin .a.b cin .a .b cin .a.b cin .a.bcout cin .(a .b a.b ) a.b.(cin cin )cout cin .(a b) a.b Which is similar to previous expressionexcept with the OR replaced by XOR

Ripple Carry Adder We have seen how we can implement alogic to add two, one bit binary numbers(inc. carry-in). However, in general we need to addtogether two, n bit binary numbers. One possible solution is known as theRipple Carry Adder– This is simply n, full adders cascadedtogether

Ripple Carry Adder Example, 4 bit adderc0a0 b0a1 b1a2 b2a3 b3a bcin coutsuma bcin coutsuma bcin coutsuma bcin coutsums0s1s2s3c4 Note: If we complement a and set co toone we have implemented s b a

Combinational Logic DesignFurther Considerations

Multilevel Logic We have seen previously how we canminimise Boolean expressions to yieldso called ‘2-level’ logic implementations,i.e., SOP (ANDed terms ORed together)or POS (ORed terms ANDed together) Note also we have also seen anexample of ‘multilevel’ logic, i.e., fulladders cascaded to form a ripple carryadder – see we have more than 2 gatesin cascade in the carry chain

Multilevel Logic Why use multilevel logic?– Commercially available logic gates usuallyonly available with a restricted number ofinputs, typically, 2 or 3.– System composition from sub-systemsreduces design complexity, e.g., a rippleadder made from full adders– Allows Boolean optimisation across multipleoutputs, e.g., common sub-expressionelimination

Building Larger Gates Building a 6-input OR gate

Common Expression Elimination Consider the following minimised SOPexpression:z a.d . f a.e. f b.d . f b.e. f c.d . f c.e. f g Requires: Six, 3 input AND gates, one 7-inputOR gate – total 7 gates, 2-levels 19 literals (the total number of timesall variables appear)

Common Expression Elimination We can recursively factor out common literalsz a.d . f a.e. f b.d . f b.e. f c.d . f c.e. f gz (a.d a.e b.d b.e c.d c.e). f gz ((a b c).d (a b c).e). f gz (a b c).(d e). f g Now express z as a number of equations in 2level form:x a b cx d e 4 gates, 9 literals, 3-levelsz x. y. f g

Gate Propagation Delay So, multilevel logic can produce reductionsin implementation complexity. What is thedownside? We need to remember that the logic gatesare implemented using electroniccomponents (essentially transistors) whichhave a finite switching speed. Consequently, there will be a finite delaybefore the output of a gate responds to achange in its inputs – propagation delay

Gate Propagation Delay The cumulative delay owing to a number ofgates in cascade can increase the timebefore the output of a combinational logiccircuit becomes valid For example, in the Ripple Carry Adder, thesum at its output will not be valid until anycarry has ‘rippled’ through possibly every fulladder in the chain – clearly the MSB willexperience the greatest potential delay

Gate Propagation Delay As well as slowing down the operation ofcombinational logic circuits, gate delay canalso give rise to so called ‘Hazards’ at theoutput These Hazards manifest themselves asunwanted brief logic level changes (orglitches) at the output in response tochanging inputs We will now describe how we can addressthese problems

Hazards Hazards are classified into two types,namely, static and dynamic Static Hazard – The output undergoes amomentary transition when it issupposed to remain unchanged Dynamic Hazard – The output changesmore than once when it is supposed tochange just once

Timing Diagrams To visually represent Hazards we will use theso called ‘timing diagram’ This shows the logical value of a signal as afunction of time, for example the followingtiming diagram shows a transition from 0 to 1and then back againLogic ‘1’Logic ‘0’Time

Timing Diagrams Note that the timing diagram makes a numbersimplifying assumptions (to aid clarity)compared with a diagram which accuratelyshows the actual voltage against time– The signal only has 2 levels. In reality the signalmay well look more ‘wobbly’ owing to electricalnoise pick-up etc.– The transitions between logic levels takes placeinstantaneously, in reality this will take a finitetime.

Static HazardLogic ‘1’Static 1 hazardLogic ‘0’TimeLogic ‘1’Static 0 hazardLogic ‘0’Time

Dynamic HazardLogic ‘1’Dynamic hazardLogic ‘0’TimeLogic ‘1’Dynamic hazardLogic ‘0’Time

Static 1 HazardxyyuwttvzuvThis circuit implements,w x. y z. yConsider the output when zand y changes from 1 to 0 x 1w

Hazard Removal To remove a 1 hazard, draw the K-mapof the output concerned. Add anotherterm which overlaps the essential terms To remove a 0 hazard, draw the K-mapof the complement of the outputconcerned. Add another term whichoverlaps the essential terms(representing the complement) To remove dynamic hazards – notcovered in this course!

Removing the static 1 hazardw x. y z. yyzzx00 01 11 10011 1 1x 1xyyExtra term added to removehazard, consequently,w x. y z. y x.zzw

To Speed up Ripple Carry Adder Abandon compositional approach to the adderdesign, i.e., do not build the design up fromfull-adders, but instead design the adder as ablock of 2-level combinational logic with 2ninputs ( 1 for carry in) and n outputs ( 1 forcarry out). Features– Low delay (2 gate delays)– Need some gates with large numbers of inputs(which are not available)– Very complex to design and implement (imaginethe truth table!

To Speed up Ripple Carry Adder Clearly the 2-level approach is notfeasible One possible approach is to make useof the full-adder blocks, but to generatethe carry signals independently, usingfast carry generation logic Now we do not have to wait for the carrysignals to ripple from full-adder to fulladder before output becomes valid

Fast Carry Generationc0c0a0 b0a1 b1a2 b2a3 b3a bcin coutsums0a bcin coutsums1a bcin coutsums2a bcin coutsums3a0 b0a1 b1a2 b2a3 b3Fast Carry Generationa ba ba ba bc0 cin cout c1 cin cout c2 cin cout c3 cin coutsumsumsumsums0s1s2s3ConventionalRCAc4Fast CarryAdderc4

Fast Carry Generation We will now determine the Booleanequations required to generate the fastcarry signals To do this we will consider the carry outsignal, cout, generated by a full-adderstage (say i), which conventionally givesrise to the carry in (cin) to the next stage,i.e., ci 1.

Fast Carry GenerationCarry out always zero.ci a bsi ci 10000111101101001001100110101010100010111ki ai .biCall this carry killCarry out same as carry in.Call this carry propagateCarry out generatedindependently of carry in.pi ai bigi ai .biCall this carry generateAlso (from before), si ai bi ci

Fast Carry Generation Also from before we have,ci 1 ai .bi ci .(ai bi ) or alternatively,ci 1 ai .bi ci .(ai bi )Using previous expressions gives,ci 1 gi ci . piSo,ci 2 g i 1 ci 1. pi 1ci 2 g i 1 pi 1.( g i ci . pi )ci 2 g i 1 pi 1.g i pi 1. pi .ci

Fast Carry GenerationSimilarly,ci 3 g i 2 ci 2 . pi 2ci 3 g i 2 pi 2 .( g i 1 pi 1.( g i ci . pi ))ci 3 g i 2 pi 2 .( g i 1 pi 1.g i ) pi 2 . pi 1. pi .ciandci 4 g i 3 ci 3 . pi 3ci 4 g i 3 pi 3 .( gi 2 pi 2 .( gi 1 pi 1.g i ) pi 2 . pi 1. pi .ci )ci 4 g i 3 pi 3 .( g i 2 pi 2 .( g i 1 pi 1.g i )) pi 3 . pi 2 . pi 1. pi .ci

Fast Carry Generation So for example to generate c4, i.e., i 0,c4 g3 p3.( g 2 p2 .( g1 p1.g 0 )) p3. p2 . p1. p0 .c0c4 G Pc0where,G g3 p3.( g 2 p2 .( g1 p1.g 0 ))P p3. p2 . p1. p0 See it is quick to evaluate this function

Fast Carry Generation We could generate all the carrys within anadder block using the previous equations However, in order to reduce complexity, asuitable approach is to implement say 4-bitadder blocks with only c4 generated usingfast generation.– This is used as the carry-in to the next 4-bitadder block– Within each 4-bit adder block, conventional RCAis used

Fast Carry Generationc0a0 b0a1 b1a2 b2a3 b3Fast Carry Generationa bc0 cin coutsums0a bcin coutsums1a bcin coutsums2a bcin coutsums3c4

Other Ways to ImplementCombinational Logic We have seen how combinational logiccan be implemented using logic gates,e.g., AND, OR etc. However, it is also possible to generatecombinational logic functions usingmemory devices, e.g., Read OnlyMemories (ROMs)

ROM Overview A ROM is a data storage device:– Usually written into once (either at manufacture orusing a programmer)– Read at will– Essentially is a look-up table, where a group ofinp

design combinational logic circuits Combinational logic circuits do not have an internal stored state, i.e., they have no memory. Consequently the output is solely a function of the current inputs. Later, we will study circuits having a stored internal