Principles of Computer Architecture Miles Murdocca and Vincent Heuring Appendix B: Reduction of Digital LogicChapter ContentsReduction (Simplification) of Boolean ExpressionsReduced Majority Function CircuitThe Algebraic MethodThe Algebraic MethodKarnaugh Maps: Venn Diagram Representation of Majority FunctionK-Map for Majority FunctionAdjacency Groupings for Majority FunctionMinimized AND-OR Majority CircuitK-Map GroupingsK-Map Corners are Logically AdjacentK-Maps and Don’t CaresFive-Variable K-MapSix-Variable K-Map3-Level Majority CircuitMap-Entered VariablesTwo Map-Entered VariablesTruth Table with Don’t CaresTabular (Quine-McCluskey) ReductionTable of ChoiceReduced Table of ChoiceMultiple Output Truth TableMultiple Output Table of ChoiceSpeed and PerformancePropagation Delay for a NOT Gate MUX DecompositionOR-Gate DecompositionState ReductionDistinguishing TreeReduced State TableThe State Assignment ProblemState Assignment SA0State Assignment SA1Sequence Detector State Transition DiagramSequence Detector State TableSequence Detector Reduced State TableSequence Detector State AssignmentExcitation TablesSequence Detector K-MapsClocked T Flip-FlopSequence Detector CircuitExcitation TablesSerial AdderSerial Adder Next-State FunctionsJ-K Flip-Flop Serial Adder CircuitD Flip-Flop Serial Adder CircuitMajority Finite State MachineMajority FSM State TableMajority FSM State AssignmentMajority FSM CircuitB-1Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationPrinciples of Computer ArchitectureMiles Murdocca and Vincent HeuringAppendix B: Reduction of Digital LogicB-2Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationChapter ContentsB.1 Reduction of Combinational Logic and Sequential LogicB.2 Reduction of Two-Level ExpressionsB.3 State ReductionB-3Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationReduction (Simplification) of Boolean Expressions• It is usually possible to simplify the canonical SOP (or POS) forms.• A smaller Boolean equation generally translates to a lower gate count in the target circuit.• We cover three methods: algebraic reduction, Karnaugh map reduction, and tabular (Quine-McCluskey) reduction.B-4Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationReduced Majority Function Circuit• Compared with the AND-OR circuit for the unreduced majority function, the inverter for C has been eliminated, one AND gate has been eliminated, and one AND gate has only two inputs instead ofthree inputs. Can the function by reduced further? How do we goabout it?B-5Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationThe Algebraic Method• Consider the majority function, F. We apply the algebraic method to reduce F to its minimal two-level form:B-6Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationThe Algebraic Method• This majority circuit is functionally equivalent to the previousmajority circuit, but this one is in its minimal two-level form:B-7Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationKarnaugh Maps: Venn Diagram Representation of Majority Function• Each distinct region in the “Universe” represents a minterm.• This diagram can be transformed into a Karnaugh Map.B-8Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationK-Map for Majority Function• Place a “1” in each cell that corresponds to that minterm.• Cells on the outer edge of the map “wrap around”B-9Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationAdjacency Groupings for Majority Function• F = BC + AC + ABB-10Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationMinimized AND-OR Majority Circuit• F = BC + AC + AB• The K-map approach yields the same minimal two-level form as the algebraic approach.B-11Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationK-Map Groupings• Minimal grouping is on the left, non-minimal (but logically equivalent) grouping is on the right.• To obtain minimal grouping, create smallest groups first.B-12Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationK-Map Corners are Logically AdjacentB-13Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationK-Maps and Don’t Cares• There can be more than one minimal grouping, as a result of don’t cares.B-14Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationFive-Variable K-Map• Visualize two 4-variable K-maps stacked one on top of the other; groupings are made in three dimensional cubes.B-15Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationSix-Variable K-Map• Visualize four 4-variable K-maps stacked one on top of the other; groupings are made in three dimensional cubes.B-16Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer Organization3-Level Majority Circuit• K-Kap Reduction results in a reduced two-level circuit (that is, AND followed by OR. Inverters are not included in the two-level count). Algebraic reduction can result in multi-level circuits with even fewer logic gates and fewer inputs to the logic gates.B-17Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University ITEC 352 Computer OrganizationMap-Entered Variables• An example of a K-map with a map-entered variable D.B-18Appendix B - Reduction of Digital LogicDepartment of Information Technology, Radford University