Combinational Logic Synthesis and Implementation Overview
Learn about the process of synthesizing logic from truth tables, drawing conventions, handling non-Boolean values, and implementing functions systematically using minterms and maxterms. Understand the standard forms, definition of literals, product terms, and sum terms to efficiently convert truth tables into logical equations. Discover the relationship between minterms and maxterms, the number of minterms for n variables, and how to implement functions using minterms in a structured manner.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
COMP541 Combinational Logic - 3 Montek Singh Jan 31, 2018 1
Todays Topics Synthesis: from truth table to logic implementation Schematic drawing conventions Non-Boolean values Don t Cares , or X values Floating values , or Z values 2
Mechanically Go From Truth Table to Function 3
From Truth Table to Logic Equation Consider a truth table Standard sum-of-products implementation OR of all product terms that are 1 For each row where output is 1 write the minterm called ON-set minterm OR all of these minterms F = X Y Z + X Y Z+XYZ+XYZ +XYZ 4
Standard Forms Not necessarily simplest F But it is a systematic way to go from truth table to function Definitions: Literal : a single variable, complemented or not Product terms : AND of literals BZ Sum terms : OR of product terms X + This is logical product and sum, not arithmetic 5
Definition: Minterm Product term in which all variables appear once (complemented or not) each minterm is 1 in exactly one row, 0 elsewhere 6
Number of Minterms For n variables, there will be 2n minterms Like binary numbers from 0 to 2n-1 Often numbered same way (often in decimal) 7
Maxterms Sum term in which all variables appear once (complemented or not) each maxterm is 0 in exactly one row, 1 elsewhere 8
Minterm related to Maxterm Minterm and maxterm with same subscripts are complements Example mj= Mj = = + + = m X YZ X Y Z M 3 3 9
Implementation: Sum of Minterms OR all of the minterms of truth table row with a 1 ON-set minterms F = m0 + m2 + m5 + m7 F = XYZ+ XYZ+XYZ+XYZ 10
More General: Sum of Products Simplifying sum-of-minterms can yield a sum of products difference is that each term need not be a minterm i.e., terms do not need to have all variables Ex: F = XYZ + XYZ ( F = XZ +XZ )+ XYZ +XYZ ( ) simplifies to: Implementation is still AND-OR but products may contain fewer literals 11
Two-Level Implementation Sum of products has 2 levels of gates ANDs followed by an OR equivalently: NANDs followed by a NAND 12
More Levels of Gates? What s best? Hard to answer More gate delays (more on this later) But maybe we only have 2-input gates So multi-input ANDs and ORs have to be decomposed 13
Complement of a Function Definition: 1s & 0s swapped in truth table Mechanical way to derive algebraic form Take the dual Recall: Interchange AND and OR, and 1s & 0s Complement each literal 14
Complement of F Not surprisingly, just sum of the other minterms sum of OFF-set minterms Example: F = m0 + m2 + m5 + m7 F = m1 + m3 + m4 + m6 F = XYZ + XYZ +XYZ +XYZ F = XZ +XZ simplifies to: 15
Product of Maxterms Recall that maxterm is true except for its own case So M1 is only false for 001 16
Product of Maxterms Can express F as AND of all rows that should evaluate to 0 i.e., product of OFF-set Maxterms! why? a row in which F=0 (OFF-set) has a Maxterm that is 0 which makes the product 0 F =M1 M3 M4 M6 or F =(X+Y +Z)(X+Y +Z)(X+Y +Z)(X+Y +Z) 17
Complement of F Can express F s complement similarly: product of ON-set Maxterms! why? a row in which F=1 (ON-set) has a Maxterm that is 0 which makes F zero F = M0 M2 M5 M7 or F =(X+Y +Z)(X+Y +Z)(X+Y +Z)(X+Y +Z) 18
More General: Product of Sums Simplifying product-of-Maxterms can yield a product of sums difference is that each term need not be a Maxterm i.e., terms do not need to have all variables Ex: F = (X+Y +Z)(X+Y +Z) (X+Y +Z)(X+Y +Z) F =(X+Z)(X+Z) simplifies to: HOW?? homework problem (hint: distributive property) Implementation is still OR-AND but each sum may contain fewer literals 19
From Equations to Gates Simply parse the Boolean equation and replace each operator with a gate AND, OR, NOT gates parentheses indicate hierarchy Example: Y = ABC+ABC+ABC 20
Recap Working (so far) with AND, OR, and NOT Algebraic identities Algebraic simplification Minterms and maxterms Can now synthesize gate-level implementation from truth table 21
Drawing Style Indicate inputs and outputs using arrows or: inputs at left/top, outputs at right/bottom If possible, gates should flow from left to right or: top to bottom Straight wires best or: keep bends at a minimum (preferably 90 deg) Connections: wires always connect at a T junction a dot at a wire crossing indicates connection wire crossing without a dot means no connection 22
Circuit Schematic Rules (cont.) Wire connections A dot where wires cross indicates a connection Wires crossing without a dot make no connection Wires always connect at a T junction wires crossing without a dot do not connect wires connect at a T junction wires connect at a dot 23
Multiple Output Circuits: Example A3 Y3 A2 Y2 Y3 Y2 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Y1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Y0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 A3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 A2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 A1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 A0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 Y1 A1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Y0 A0 PRIORITY CiIRCUIT Output asserted corresponding to most significant TRUE input Example: Priority Encoder Hardware 24
Example: Priority Encoder Hardware (contd.) Y3 Y2 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Y1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Y0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 A3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 A2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 A1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 A0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Y3 has 8 minterms, Y2 has 4 minterms, Y1 has 2 minterms and Y0 has 1 without simplification: 15 AND gates + 3 OR gates with simplification, a much smaller circuit (method discussed later) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 A3A2A1A0 Y3 Y2 Y1 Y0 25
Values that are not 0s and 1s Don t Cares (X) Floating values (Z) 26
X values X is neither 1 nor 0 typically used to represent unknown or illegal values Unknown e.g., an uninitialized value in a simulator in hardware most flipflops will wake up to a 1 or a 0 value but could be different each time it wakes up Don t Care an output specified as X means don t care i.e., left unspecified: whatever comes out is okay Illegal e.g., contention at output two gates fighting 27
Actually: Several Meanings of X When used to specify an input value Means: Don t Care : this particular input variable s value does not matter when determining the output Example: Output F is 1 when the inputs A, B, C are 1X1 Means F = AC // B is a Don t Care Unknown/uninitialized signal If a simulator cannot determine the value of a signal, it will display it as X Other values that depend on this signal may also become X Contention (illegal input value) Sometimes a simulator will use X to denote the value of a node that is being pulled both to 0 and to 1 Example: Outputs of two gates are shorted; or a gate has p- transistor and n-transistor network simultaneously on! 28
Dont Cares (X) Y3 Y2 0 0 0 0 0 0 1 1 0 0 Y1 0 0 0 0 1 1 0 0 0 0 Y0 0 0 1 1 0 0 0 0 0 0 A3 0 0 0 0 1 A2 0 0 0 1 X A1 0 0 1 X X A0 0 1 X X X Y3 Y2 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Y1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Y0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 A3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 A2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 A1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 A0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 More compact representation! A3A2A1A0 Y3 Y2 Example: Priority Encoder Hardware Y1 Y0 29
Z values Also neither 1 nor 0 but actually floating i.e., the output is neither connected to 0 (ground) nor to 1 (power supply) Could be undesirable: actual voltage is highly susceptible to noise e.g., neighboring wires/gates could easily influence value Could be by design: useful in buses, memories, multiplexers, etc. usually one gate drives a wire to a 1 or 0 all others float their outputs example: tristate buffers/inverters cover in next lecture tristate buffer 30
Next Detour overview of transistors Back to combinational logic common building blocks 31
