内容课件教程教案lecture17combinational logic and k map

1、2/13/2022ELEC11001How a Robot Control Its MotionELEC1100 Fall 2011Lecture 17: Combinational Logic/K-MapIn todays lectureCombinational LogicK-Map2/13/20222Review from Last LectureBinary digit: 0 and 1 can be represented by logic (true or False) - 0 is equivalent to False - 1 is equivalent to TrueInpu

2、t AOutput AAND gateABOutputOR gateABOutputNAND gateNOR gateABOutputABOutputXOR gateXNOR gateABOutputABOutput2/13/202231. 0+X = X2. 1+X = 13. X+X= 14. 0.X = 05. 1.X = X6. X.X = X7. X.X = 08.(X) = X9. X+Y = Y+X10. X.Y = Y.X11. X+(Y+Z)= (X+Y)+Z12. X.(Y.Z) = (X.Y).Z13. X.(Y+Z) = X.Y+X.Z14. X+X.Z=X15. X.

3、(X+Y)=X16. (X+Y).(X+Z) = X+Y.Z17. X+XY = X+Y18. (XY)+(YZ)+(XZ)=(XY)+(XZ)19. (X+Y) = X.Y20. (XY) = X+Y(Associativity)(Associativity)(Distributivity)(DeMorgans Law)Law of Boolean Algebrahow do you verify this?2/13/2022ELEC11004Where Are We Now?Robot systeminputsactionsElectronic sub-systemMechanical s

4、ub-systemControl Logicsub-systemPowersub-systemSensorsub-systemAnalog sub-systemDigital sub-systemIn progressTo be doneDone 2/13/2022 ELEC11005What Are We Looking At Today?Robot systeminputsactionsElectronic sub-systemMechanical sub-systemControl Logicsub-systemPowersub-systemSensorsub-systemAnalog

5、sub-systemDigital sub-systemIn progressTo be doneDone Basic elements: - logic gate, flip-flop, etc.Basic principles: - DeMorgans law, etc.- K-mapBasic concepts: - input, output, etc.Digital sub-system2/13/2022 ELEC11006All Boolean equations can be written in standard formsSum of Products (SOP) ORing

6、 (sum) many AND (product) terms e.g. X = A.B+B.C.D + EFProduct of Sums (POS) ANDing (product) many OR (sum) terms e.g. X = (A+B).(B+C+D).(E+F)Combinational Logic: Standard FormHow do you change from one form to another?2/13/20227Build the truth table of the following circuit).)()(.()(.)(CADBABAADCBA

7、FABCDACABAABDFCombinational Logic and Truth TableExpand it out and minimize, we haveDCBABCDADCBACBBACBAABCDAACDAF.Before you build the truth table, can you simplify F?8Combinational Logic and Truth TableABCDABCD+ABCD000000001000100001100100001010011000111110001100101010010110110001101011100111102/13

8、/2022ELEC11009ABCF00000010010001111001101111011111Is there any systematic way to build a circuit from a truth table?We can implement using SOP formEach 1 at the output is a sum term,Add it up together means Oring all these termstogether We need 5 AND gates and 1 OR gate,Can we use fewer gates?Build

9、Circuit from Truth TableF = A.B.C+A.B.C+A.B.C+A.B.C+A.B.C2/13/2022ELEC110010Example: Half AdderINPUTINPUTOUTPUTOUTPUTABC=A+BC1C00000010110011110The half adder is a circuit that adds two 1-bit numbers and the result of the addition is a “2-bit number”. ABABABC1C02/13/2022ELEC110011ABF000011101111K-ma

10、p can help to convert any Boolean function or truth table into an equivalent SOP form with fewest possible product termsTwo variables K-map0111AABBK-mapABF0000111001110011AABBLogic Minimization using Karnaugh Map (K-Map)2/13/202212BABAF.A AB BF F0 00 00 00 01 10 01 10 01 11 11 11 10 01 11 10 0A AA A

11、B BB BAF 0 01 11 10 0A AA AB BB B0 01 10 01 1A AA AB BB BCan you do this?Logic Minimization using K-Map1.Begin with isolated cells. These must be used as they are and no simplification is possible.2.Find all cells that are adjacent to only one other cell, forming two-cell subcubes.3.Find cells that

12、form four-cell subcubes, eight-cell subcubes, etc.4.Collect the smallest number of maximal subcubes.2/13/2022ELEC11001310010110A.B A.B A.B A.BCCBefore circling: After circling : Before circling : CBACBA.After circling : BCOverall function before circlingAfter circling : (4 3-input AND gate + 1 4-inp

13、ut OR gate) (2 2-input AND gate + 1 2-input OR gate) Logic Minimization using K-MapK-map of 3 variables1.Begin with isolated cells. These must be used as they are and no simplification is possible.2.Find all cells that are adjacent to only one other cell, forming two-cell subcubes.3.Find cells that

14、form four-cell subcubes, eight-cell subcubes, etc.4.Collect the smallest number of maximal subcubes.2/13/2022ELEC110014Logic Minimization using K-MapK-map of 4 variables0000011001100000A.B A.B A.B A.BC.DC.DC.DC.DNote that the adjacent label only has 1 variable differenceThese two labels are adjacent

15、These two labels are adjacentDCBADCBADCBADCBAF.DBADBAF.First cyclingSecond cyclingDBF.Reduce from 4 4input-AND gates and 1 4input-OR gate to 1 2-input AND gateLogic Minimization using K-Map0000011001000000C.DC.DC.DC.DDCBADCBADCBAF.DCBDBAF.After cyclingCan not do 2nd cyclingA.B A.B A.B A.B10010001010

16、01001C.DC.DC.DC.DA.B A.B A.B A.BK-map of 4 variablesCBADCBADCBDCBF.DCBADCBADCBADCBADCBADCBAF.After 1st cyclingAfter 2nd cyclingCBADCBADBF.More ExamplesABCDF00001000110010100110010000101101100011101000110011101001011111000110111110011111Q: find and simplify FQ: whats the gate implementation?2/13/2022ELEC110017Lecture Summary1. Begin with isolated cells. These must be used as they are and no simplification is possible.2. Find all cells that are adjacent to only one