multi-level gate circuit

Published on: **Mar 3, 2016**

Published in:
Education

- 1. KL 2164DIGITAL ELECTRONICSMulti Level Gate Circuit Pn. Wan Nurdiana Wan Ibrahim nurdiana@eng.ukm.my
- 2. Multi-Level Gate CircuitsTerminology:1. AND-OR circuit means a two-level circuit composed of a level of AND gates followed by an OR gate at the output.2. OR-AND circuit means a two-level circuit composed of a level of OR gates followed by an AND gate at the output.3. OR-AND-OR circuit means a three-level circuit composed of a level of OR gates followed by a level of AND gates followed by an OR gate at the output.4. Circuit of AND and OR gates implies no particular ordering of the gates; the output gate may be either AND or OR. 2
- 3. Four-Level Realization of ZEach node on a treediagram represents agate, and the numberof gate inputs iswritten beside eachnode. 3
- 4. 4
- 5. Z = (AB + C) (D+ E + FG) + HNumber of level?Number of gate?Number of gate input?Change to three levels by partially multiplying itout :Z = (AB + C) (D+ E + FG) + H 5
- 6. Three -Level Realization of Z 6
- 7. ExampleFind a circuit of AND and OR gates to realizef (a, b, c, d) = Ʃ m(1, 5, 6, 10, 13, 14) Consider solutions with two levels of gates and three levels of gates. Try to minimize the number of gates and the total number of gate inputs. Assume that all variables and their complements are available as inputs.First, simplify f by using a Karnaugh map. 7
- 8. 8
- 9. This leadsdirectly to atwo-levelAND-OR gatecircuit. 9
- 10. Factoring yields f=? 10
- 11. Both of these solutions have an OR gate at the output. Asolution with an AND gate at the output might have fewergates or gate inputs.A two-level OR-AND circuit corresponds to a product-of-sumsexpression for the function. This can be obtained from the 0′son the Karnaugh map as follows:f ′ = c′d + ab′c′ + cd + a′b′cleads directly to a two-level OR-AND circuit. 11
- 12. 12
- 13. To get a three-level circuit with an AND gate output, wepartially multiply out using (X + Y)(X + Z) = X + Y Z:It would require four levels of gates to realize; however, if we multiply out d′(a + b) and d(a′ + b), we getwhich leads directly to a three-level AND-OR-AND circuit. 13
- 14. 14
- 15. For this particular example,the best two-level solution had an AND gate at the outputthe best three-level solution had an OR gate at the output.In general, to be sure of obtaining a minimum solution, must find both thecircuit with the AND-gate output and the one with the OR-gate output. 15
- 16. NAND gatesThe small circle (or “bubble”) at the gate output indicatesinversion the NAND gate = AND gate followed by an inverter.The gate output is F = (ABC)′ = A′ + B′ + C′ 16
- 17. NOR gatesShows a three-input NOR gate.NOR gate = OR gate followed by an inverter.The gate output is F = (A + B + C)′ = A′B′C′ 17
- 18. Functionally Complete Set of GatesAND and NOT are a functionally complete setof gates because OR can also be realizedusing AND and NOT: 18
- 19. NAND GatesSimilarly, any function can be realized using onlyNAND gates: 19
- 20. Design of Two-Level NAND-Gate CircuitsA two-level circuit composed of AND and OR gates is easilyconverted to a circuit composed of NAND gates or NOR gatesStep 1: using F = (F′)′Step 2 : applying DeMorgan′s laws: (X1 + X2 + … + Xn)′ = X1′ X2′…Xn′ (X1 X2…Xn)′ = X1′ + X2′ + … + Xn′ 20
- 21. Design of Two-Level NAND-Gate Circuits –cont.Example illustrates conversion of a minimum sum-of-products formto several other two-level forms: F = A + BC′ + B′CD = [(A + BC′ + B′CD)′ ]′ AND-OR = [A′ • (BC′)′ • (B′CD)′]′ NAND-NAND = [A′ • (B′ + C) • (B + C′ + D′)]′ OR-NAND = A + (B′ + C)′ + (B + C′ + D′)′ NOR-OR 21
- 22. Design of Two-Level NOR-Gate CircuitsWant a two-level circuit containing only NOR gates; start with the minimum product-of-sums form for F.F can be written in the following two-level forms: F = (A + B + C)(A + B′ + C′)(A + C′ + D) OR-AND = {[(A + B + C)(A + B′ + C′)(A + C′ + D)]′ }′ = [(A + B + C)′ + (A + B′ + C′)′ + (A + C′ + D)′]′ NOR-NOR = (A′B′C′ + A′BC + A′CD′)′ AND-NOR = (A′B′C′)′ • (A′BC)′ • (A′CD′)′ NAND-AND 22
- 23. Eight Basic Forms for Two-Level Circuits 23
- 24. The other eight possible two-level forms:(AND-AND,OR-OR,OR-NOR,AND-NAND,NAND-NOR,NOR-NANDetc ) degenerate ;cannot realize all switching functions.Consider, for example, the following NAND-NOR circuit:From this example, it is clear that the NAND-NOR form can realizeonly a product of literals and not a sum of products. 24
- 25. Design of Minimum Two-Level NAND-NANDCircuitsProcedure for designing a minimum two-level NAND-NAND circuit:1. Find a minimum sum-of-products expression for F.2. Draw the corresponding two-level AND-OR circuit.3. Replace all gates with NAND gates leaving the gateinterconnection unchanged. If the output gate has any single literalsas inputs, complement these literals. 25
- 26. F = l1 + l2 + • • • + P1 + P2 + • • • F = (l1′l2′ • • • P1′P2′ • • •)′26
- 27. Design of Multi-Level NAND- and NOR-Gate Circuits The following procedure may be used to design multi-level NAND-gate circuits:1. Simplify the switching function to be realized.2. Design a multi-level circuit of AND and OR gates. The output gate must be OR. AND gate outputs cannot be used as AND- gate inputs; OR-gate outputs cannot be used as OR-gate inputs.3. Number the levels starting with the output gate as level 1. Replace all gates with NAND gates, leaving all interconnections between gates unchanged, leave the inputs to levels 2,4,6,… unchanged. Invert any literals which appear as inputs to levels 1,3,5,… 27
- 28. 28
- 29. Alternative Gate SymbolsLogic designers who design complex digital systems often find itconvenient to use more than one representation for a given type ofgate. For example, an inverter can be represented by 29
- 30. Alternative Gate SymbolsEquivalent gatesymbols based onDeMorgan′s Laws 30
- 31. NAND Gate Circuit Conversion 31
- 32. Conversion to NOR Gates 32
- 33. Conversion of AND-OR Circuit to NAND Gates 33
- 34. Design of Two-Level, Multiple-Output CircuitsSolution of digital design problems often requires the realizationof several functions of the same variables. Although eachfunction could be realized separately, the use of some gates incommon between two or more functions sometimes leads to amore economical realization.Example:Design a circuit with four inputs and three outputs which realizesthe functions 34
- 35. 35
- 36. Draw the Circuit Realization 36
- 37. Multiple-Output Realization of Equations Realization of functions with shared gates (lower overall cost) (7 Gates) 37
- 38. Another example of sharing gates among multiple outputs to reduce cost.f1 = Ʃ m(2, 3, 5, 7, 8, 9, 10, 11, 13, 15)f2 = Ʃ m(2, 3, 5, 6, 7, 10, 11, 14, 15)f3 = Ʃ m(6, 7, 8, 9, 13, 14, 15)Draw the Karnaugh Map: 38
- 39. Minimal Solution 39
- 40. In this example, thebest solution isobtained by notcombining the circled 1with adjacent 1’s. 40
- 41. The solution with themaximum number ofcommon terms is notnecessarily the bestsolution, as illustratedby this example. 41
- 42. Multi-Level Circuit Conversion to NOR Gates The procedure for design of single- output, multi-level NAND- and NOR- gate circuits also applies to multiple- output circuits 42