COMP3222/9222 Digital Circuits & Systems
2. Optimized Implementation of Logic Functions
Lecture 2 Objectives
To learn more about:
• Synthesis & analysis of logic functions
• Graphical representation of logic functions in the form of
Karnaugh maps
– Techniques for deriving minimum-cost implementations of logic
functions
• Use of CAD tools and VHDL to implement logic functions
20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S2
• What is a minimum cost implementation?
• How is it obtained?
Consider simplifying f (x1, x2, x3) = S m(0, 2, 4, 5, 6)
20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S3
= x1x3 + x1x3 + x1x2
= x3 + x1x2
= x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3
f = m0 + m2 + m4 + m5 + m6
LIBRARY ieee ;
USE ieee.std_logic_1164.all ;
ENTITY func1 IS
PORT ( x1, x2, x3 : IN BIT ;
f : OUT BIT ) ;
END func1 ;
ARCHITECTURE LogicFunc OF func1 IS
BEGIN
f <= (NOT x1 AND NOT x2 AND NOT x3) OR (NOT x1 AND x2 AND NOT x3) OR ( x1 AND NOT x2 AND NOT x3) OR ( x1 AND NOT x2 AND x3) OR ( x1 AND x2 AND NOT x3) ; END LogicFunc ; The VHDL code for the function in L02/S3 Should synthesize to f = x3 + x1x2 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S4 Karnaugh map • The key to finding a minimum-cost expression for a given logic function is to reduce the number of product (or sum) terms needed in the expression by applying the combining/uniting property x∙y + x∙y’ = x and (x + y)∙(x + y’) = x as judiciously as possible. • The Karnaugh map approach provides a systematic way of performing this optimization 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S5 • Note that the addresses of horizontally and vertically adjacent cells in the Karnaugh map differ in a single bit. • This facilitates their combination. 00 10 01 11 Layout of two-variable minterms in a two- variable Karnaugh map x 2 (a) Truth table (b) Karnaugh map 0 1 0 1 m 0 m 2 m 3 m 1 x 1 x 2 0 0 0 1 1 0 1 1 m 0 m 1 m 3 m 2 x 1 (more significant variable) (less significant variable) 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S6 • Note that adjacent cells in a column or row of the Karnaugh map can be combined in order to eliminate the variable that is present in both uncomplemented and complemented form The function of L01/S26 x1 x1 x2 x2 x 2 0 1 0 1 x 1 1 1 0 1 f = x1 + x2 x1 x2 f(x1, x2) 0 0 1 0 1 1 1 0 0 1 1 1 20T3 COMP3222/9222 Optimized Implementation of Logic Functions x1x2 + x1x2 x1x2 + x1x2 m 0 m 2 m 3 m 1 L02/S7 Karnaugh map layout of three-variable minterms Note: columns (rows) of the table are labeled using a Gray encoding – successive entries differ in just one bit. 000 010 110 100 001 011 111 101 x3 x2 x1 x 1 x 2 x 3 00 01 11 10 0 1 (b) Karnaugh map x 2 x 3 0 0 0 1 1 0 1 1 m 0 m 1 m 3 m 2 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 m 4 m 5 m 7 m 6 x 1 (a) Truth table m 0 m 1 m 3 m 2 m 6 m 7 m 4 m 5 20T3 COMP3222/9222 Optimized Implementation of Logic Functions more significant variables least significant variable L02/S8 • Note that the map wraps around to form a torus – adjacency can span the leftmost and rightmost columns x1x2 x3 0 0 1 0 1 1 0 1 (a) The function of L01/S36 00 01 11 10 0 1 f x1x3 x2x3+= Examples of three-variable Karnaugh maps x 2 x 3 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 x 1 (a) 0 1 0 0 1 1 1 0 (b) 1 0 1 0 1 1 1 0 20T3 COMP3222/9222 x x1 2x3 1 1 0 0 1 1 0 1 (b) The function of L02/S3 00 01 11 10 0 1 f x3 x1x2+= L02/S9 • Note that both row and col addresses are Gray coded • Note that opposite edges of the map are considered adjacent A four-variable Karnaugh map x 1 x 2 x 3 x 4 00 01 11 10 00 01 11 10 x 2 x 4 x 1 x 3 m 0 m 1 m 5 m 4 m 12 m 13 m 8 m 9 m 3 m 2 m 6 m 7 m 15 m 14 m 11 m 10 0000 0100 1100 1000 0001 0101 1101 1001 0011 0111 1111 1011 0010 0110 1110 1010 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S10 Examples of four-variable Karnaugh maps x 1 x 2 x 3 x 4 0 00 01 11 10 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 00 01 11 10 f 2 x 3 x 1 x 4 + = x 1 x 2 x 3 x 4 0 00 01 11 10 0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 00 01 11 10 f 1 x 2 x 3 x 1 x 3 x 4 + = x x 1 2 x 3 x 4 1 00 01 11 10 0 0 1 0 0 0 0 1 1 1 0 1 1 0 1 00 01 11 10 f 3 x 2 x 4 x 1 x 3 x 2 x 3 x 4 + + = x 1 x 2 x 1 x 2 x 3 x 4 1 00 01 11 10 1 1 0 1 1 1 0 0 0 1 1 0 0 1 1 00 01 11 10 f 4 x 1 x 3 x 1 x 3 + + = 20T3 COMP3222/9222 Optimized Implementation of Logic Functions x 2 x 3 or L02/S11 A five-variable Karnaugh map x 1 x 2 x 3 x 4 00 01 11 10 1 1 1 1 1 1 00 01 11 10 x 1 x 2 x 3 x 4 00 01 11 10 1 1 1 1 1 1 1 00 01 11 10 f 1 x 1 x 3 x 1 x 3 x 4 x 1 x 2 x 3 x 5 + + = x 5 1 = x 5 0 = 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S12 • Cost – We use the number of gates plus the total number of inputs to gates, but we assume that the primary inputs are available in both true and complemented form at zero cost – we don’t count input inverters x 1 x 2 x 3 1 1 1 1 x 1 0 0 1 0 00 01 11 10 0 1 x 2 x 3 Minimization strategy Terminology • Literal – Each appearance of a variable in a product term • Implicant – A product term that indicates a set of valuations for which a given function is equal to 1 • Prime implicant – Cannot be combined into another implicant that has fewer literals • Cover – A collection of implicants that account for all valuations for which a given function is equal to 1 – A cover consisting only of prime implicants leads to a minimal cost implementation Implicants are expanded by square/ rectangular powers of 2 to form PIs 20T3 COMP3222/9222 Optimized Implementation of Logic Functions What is the minimum cost of this function? x 1 x 2 x 3 x 1 x 2 L02/S13 x 1 x 2 x 3 x 4 00 01 11 10 1 1 1 1 1 1 00 01 11 10 1 1 1 x 3 x 4 x 1 x 2 x 4 x2 x 3 x 2 x 3 x 4 Essential prime implicants • Where there is choice as to which prime implicants to use in a cover, how do we find the minimum cost subset of prime implicants? • If a prime implicant includes a minterm for which f = 1 that is not included in any other prime implicant, then it must be included in the cover and is referred to as an essential prime implicant • If the set of essential prime implicants covers all valuations for which f = 1, then this set is the desired cover of f. Otherwise, determine the nonessential prime implicants that should be included to form a minimum-cost cover • In this example, x1x3 is preferred over x1x2x4 for covering x1x2x3x4 since it has lower cost x1 x 3 What is the minimum cost of this function? L02/S14Optimized Implementation of Logic Functions When there is a choice of covers…. f ( x1,…, x4) = S m(0, 4, 8, 10, 11, 12, 13, 15) x 1 x 2 x 3 x 4 00 01 11 10 1 1 1 1 0 0 1 0 0 0 1 1 0 0 0 1 00 01 11 10 x3x4 x1x2x3 x1x2x4 x1x3x4 x1x2x3 x1x2x4 20T3 COMP3222/9222 Optimized Implementation of Logic Functions 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 L02/S15 Heuristic choice of nonessential prime implicants • The choice of nonessential prime implicants to be included in the cover is governed by cost considerations. • The choice is often not obvious and, for functions of a large number of variables, may involve assessing many possibilities. • A heuristic approach, which considers only a subset of possibilities but gives good results most of the time, is used: – Arbitrarily select one nonessential prime implicant and determine the cost of the resulting cover; – Then, determine the cost of a cover that does not include the chosen prime implicant; and – Select for implementation the cover which costs least. 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S16 x1 x 2 x 3 x 4 00 01 11 10 1 1 1 1 1 1 00 01 11 10 1 1 x 1 x 3 x 4 x 2 x 3 x 4 x 2 x 3 x 4 x 1 x 3 x 4 x 1 x 2 x 4 x 1 x 2 x 4 x 1 x 2 x 3 x 1 x 2 x 3 Sometimes alternative covers cost the same… f ( x1,…, x4) = S m(0, 2, 4, 5, 10, 11, 13, 15) 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S17 • Minimal SOP (sum of product) and POS (product of sum) implementations need to be compared to determine the least cost realization x 1 x 2 x 3 1 00 01 11 10 0 1 1 0 0 1 1 1 0 x 1 x 2 + ( ) x 1 x 3 + ( ) POS minimization of f (x1, x2, x3) = P M(4, 5, 6) 20T3 COMP3222/9222 Optimized Implementation of Logic Functions What is the cost of this function? Which costs less: SOP or POS? L02/S18 ( x1 + x2 + x3 )·( x1 + x2 + x3 ) ( x1 + x2 + x3 )·( x1 + x2 + x3 ) ⇒ POS minimization of f ( x1,…, x4) = P M(0, 1, 4, 8, 9, 12, 15) • Which implementation is cheaper: POS or SOP? x 1 x 2 x 3 x 4 0 00 01 11 10 0 0 0 0 1 1 0 1 1 0 1 1 1 1 1 00 01 11 10 x 2 x 3 + ( ) x 3 x 4 + ( ) x 1 x 2 x 3 x 4 + + + ( ) 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S19 • Often functions are not completely specified – The outputs under certain input conditions are not given ⇒ we can treat them as “don’t care” values • Don’t care conditions offer additional opportunities for simplification – A don’t care can be assigned the value 0 or 1, as desired – E.g., there are two possible implementations of the function f ( x1,…, x4) = S m(2, 4, 5, 6, 10) + D(12, 13, 14, 15) Practical Reality 1: Incompletely specified functions x 1 x 2 x 3 x 4 0 00 01 11 10 1 d 0 0 1 d 0 0 0 d 0 1 1 d 1 00 01 11 10 (a) SOP implementation x 2 x 3 x 3 x 4 x1 x 2 x 3 x 4 0 00 01 11 10 1 d 0 0 1 d 0 0 0 d 0 1 1 d 1 00 01 11 10 x 2 x 3 + ( ) x 3 x 4 + ( ) (b) POS implementation L02/S20 f 1 f 2 x 2 x 3 x 4 x 1 x 3 x 1 x 3 x 2 x 3 x 4 (c) Combined circuit for f 1 f 2 and Practical Reality 2: Multiple-output synthesis x 1 x 2 x 3 x 4 00 01 11 10 1 1 1 1 1 1 1 1 00 01 11 10 (a) Function 1 f 1 x 1 x 2 x 3 x 4 00 01 11 10 1 1 1 1 1 1 1 1 1 00 01 11 10 (b) Function f 2 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S21 Another example of multiple-output synthesis x 1 x 2 x 3 x 4 00 01 11 10 1 1 1 1 00 01 11 10 1 f 3 f 4 1 1 x 1 x 2 x 3 x 4 00 01 11 10 1 1 1 1 00 01 11 10 1 1 (a) Optimal realization of (b) Optimal realization of 1 (c) Optimal realization of f 3 x 1 x 2 x 3 x 4 00 01 11 10 1 1 1 1 00 01 11 10 1 1 1 x 1 x 2 x 3 x 4 00 01 11 10 1 1 1 1 00 01 11 10 1 1 1 and togetherf 4 f 3 f 4 x 1 x 4 x 3 x 4 x 1 x 1 x 2 x 2 x 4 x 4 (d) Combined circuit for f 3 f 4 and x 2 Note that the realizations of (c) are sub-optimal if considered individually 20T3 COMP3222/9222 Optimized Implementation of Logic Functions Combined cost = 2x2-in + 3x3-in + 1x4-in = 23 Cost = 2x2-in + 2x3-in = 14 Cost = 2x2-in + 1x4-in + 1x3-in = 15 Combined cost = 14 + 15 = 29 L02/S22 Practical Reality 3: Factoring for multilevel implementation f(x1,...,x7) = x1x3x6 + x1x4x5x6 + x2x3x7 + x2x4x5x7 = x1x6(x3 + x4x5) + x2x7(x3 + x4x5) = (x1x6 + x2x7)(x3 + x4x5) … by the distributive law • Electrical properties limit the number of inputs a logic gate can have before performance is compromised • Similarly, manufacturing constraints may impose an upper limit on the number of inputs to a logic resource – Factoring a circuit or function allows a function to be implemented from simpler sub-functions – Here, 4-input AND and OR gates are needed to implement f naively, but suppose the implementation technology we use is restricted to 2-input gates? – The result is a multilevel (more than two levels of gates) function/circuit implementation 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S23 MP3 encoder (eenewseurope.com) 7400 Quad 2-NAND (wikipedia.com) Implementation technologies: A quick introduction to FPGAs • Digital circuits are implemented in various solid state/silicon device technologies • Devices are classified as either fixed or programmable • Devices that are manufactured to perform fixed functions range from small-scale integrated devices (that contain a few specific logic gates) to custom VLSI circuits that comprise millions of gates • Programmable devices can be customized after fabrication to implement requisite circuits – Examples include: Programmable Logic Arrays, Complex Programmable Logic Devices and Field-Programmable Gate Arrays (FPGAs) Q: Is an ARM or Intel processor fixed or programmable? Q: How does the programmability of a processor differ from that of an FPGA? L02/S24 A Field-Programmable Gate Array (FPGA) • For cost and performance reasons, as few chips as possible are used to implement a design – 7400-series chips implement the equivalent of just a few two-input NAND gates (the prevalent metric for chip size) – An SPLD or CPLD macrocell represents about 20 equivalent gates; thus a PAL with 8 macrocells can accommodate a circuit that needs up to about 160 gates and a large CPLD with 500 macrocells can implement circuits of up to 10,000 equivalent gates – Modern FPGAs can be used to implement circuits of millions of equivalent gates in size B&V3, Figure 3.35 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S25 A two-input lookup table (LUT) as an FPGA logic cell/block B&V3, Figure 3.36 (a) Circuit for a two-input LUT x 1 x 2 f 0/1 0/1 0/1 0/1 An n-input LUT serves as a small 2n address memory to implement an arbitrary Boolean function of n variables f x 0 x 1 s A two-input multiplexer (MUX) f = s.x0 + s.x1 selects one of its two inputs to be routed to the output 0 1 x0 x1 s f 0 1 x 0 x 1 f s Two-input multiplexer circuit (2-MUX) 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S26 0 0 1 1 0 1 0 1 1 0 1 1 x 1 x 2 (b) f 1 x 1 x 2 + = (c) Storage cell contents in the LUT x 1 x 2 1 0 1 1 f 1 f 1 0 1 0 1 0 1 A section of a programmed FPGA B&V3, Figure 3.39 f1 = x1x2 f2 = x2x3 f = f1 + f2 f = x1x2 + x2x3 0 1 0 0 0 1 1 1 0 0 0 1 x 1 x 2 x 2 x 3 f 1 f 2 f 1 f 2 f x 1 x 2 x 3 f In an FPGA, the LUT contents, routing switches and connection boxes are most commonly configured via SRAM memory cells 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S27 f 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 x 2 x 3 x 1 A three-input LUT B&V3, Figure 3.37 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S28 7 inputs Realizing a seven-input product term • Implementing wide functions when gate fan-in is limited 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S29 • Factoring can be used to overcome fan-in constraints • For example, f = x1x2x3x4x5x6 + x1x2x3x4x5x6 = x1x4x6(x2x3x5 + x2x3x5) for FO4 (fan-in of 4) gates x 6 x 4 x 1 x 5 x 2 x 3 x 2 x 3 x 5 Still Practical Reality 3: A factored circuit 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S30 x 1 x 2 x 3 x 4 f g Practical Tradeoff: Functional decomposition • Multilevel realizations can reduce the cost of a circuit with increased propagation delay penalties • Consider the minimum-cost SOP expression f = x1x2x3 + x1x2x3 + x1x2x4 + x1x2x4 [7 gates + 18 inputs]* = (x1x2 + x1x2)x3 + (x1x2 + x1x2)x4 = gx3 + gx4 with g = x1x2 + x1x2 [9 FO2 gates+15 inputs]* 20T3 COMP3222/9222 Optimized Implementation of Logic Functions * inc. inverters L02/S31 1 x 2 x 3 x 4 f g h x x 1 x 2 x 3 x 4 f g The structure of decomposition in L02/S31 20T3 COMP3222/9222 Optimized Implementation of Logic Functions 3-LUT 3-LUT L02/S32 Q: How many 2-LUTs are needed to implement this function? NAND and NOR gates In custom VLSI implementations, NAND & NOR gate circuit realizations of SOP/POS networks are preferred over AND/OR/NOT gate realizations because they require less transistors to implement Optimized Implementation of Logic Functions20T3 COMP3222/9222 x 1 x 2 x n x 1 x 2 … x n + + + x 1 x 2 x 1 x 2 + x 1 x 2 x n x 1 x 2 x 1 x 2 ∙ x 1 x 2 … x n ∙ ∙ ∙ (a) NAND gates (b) NOR gates L02/S33 DeMorgan’s theorem in terms of logic gates Allows us to transform AND-OR networks into NAND-only or NOR-only equivalent networks Optimized Implementation of Logic Functions20T3 COMP3222/9222 x 1 x 2 x 1 x 2 x 1 x 2 x 1 x 2 x 1 x 2 x 1 x 2 x 1 x 2 x 1 x 2 + = (a) x 1 x 2 + x 1 x 2 = (b) L02/S34 Using NAND gates to implement a SOP network Optimized Implementation of Logic Functions20T3 COMP3222/9222 • To transform network into NAND-only type: 1. Replace AND & OR gates with equivalent NAND gates 2. Ensure the logical value of no wire is changed due to step 1. Insert additional bubbles into wires where only one bubble was added during step 1. x 1 x 2 x 3 x 4 x 5 x 1 x 2 x 3 x 4 x 5 x 1 x 2 x 3 x 4 x 5 L02/S35 x 1 x 2 x 3 x 4 x 5 x 1 x 2 x 3 x 4 x 5 x 1 x 2 x 3 x 4 x 5 Using NOR gates to implement a POS network Optimized Implementation of Logic Functions20T3 COMP3222/9222 • Follow a similar algorithm to transform network into NOR- only type L02/S36 Example 2.3 • Consider the function f(x1, x2, x3) = Σm(2, 3, 4, 6, 7) • The canonical SOP expression is derived using minterms f = m2 + m3 + m4 + m6 + m7 = x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 • The expression can be simplified using algebraic manipulation or a Karnaugh map: f = x1x2(x3 + x3) + x1(x2 + x2)x3 + x1x2(x3 + x3) = x1x2 + x1x3 + x1x2 = (x1 + x1)x2 + x1x3 = x2 + x1x3 Optimized Implementation of Logic Functions20T3 COMP3222/9222 L02/S37 f (a) SOP implementation x2 x3 x1 f (d) Resulting NAND implementation x3 x1 x2 NAND-gate realization of the function in Example 2.3 Optimized Implementation of Logic Functions20T3 COMP3222/9222 f (b) Partial NAND conversion x2 x3 x1 f (c) Balancing inserted inversions x2 x3 x1 L02/S38 Example 2.4 • Consider again the function of Example 2.3. Instead of using the minterms, we can specify this function as a product of maxterms for which f = 0, namely, f(x1, x2, x3) = ΠM(0, 1, 5) • Then the canonical POS expression is derived as f = M0∙M1∙M5 = (x1 + x2 + x3)(x1 + x2 + x3)(x1 + x2 + x3) • A simplifeied POS expression can be derived as f = ((x1 + x2) + x3)((x1 + x2) + x3)(x1 + (x2 + x3))(x1 + (x2 + x3)) = ((x1 + x2) + x3x3)(x1x1 + (x2 + x3)) = (x1 + x2)(x2 + x3) Optimized Implementation of Logic Functions20T3 COMP3222/9222 L02/S39 x1 f (a) POS implementation (b) NOR implementation f x3 x2 x1 x3 x2 NOR-gate realization of the function in Example 2.4 Optimized Implementation of Logic Functions20T3 COMP3222/9222 L02/S40 (a) Sum-of-products implementation x 2 x 1 x 1 x 2 Å Implementation of XOR (b) NAND gate implementation x 2 x 1 x 1 x 2 Å x 2 1 g x 1 x 2 Å (c) Optimal NAND gate implementation x Since (x1∙x2) = (0 + x1∙x2) = (x1∙x1 + x1∙x2) = (x1∙(x1 + x2)) = x1∙(x1∙x2) á 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S41 x 2 x 1 x 3 x 4 x 5 x 6 x 7 (a) Circuit with AND and OR gates x 2 x 1 x 3 x 4 x 5 x 6 x 7 f f (b) Inversions needed to convert to NANDs Multilevel NAND-gate circuit x 2 x 1 x 3 x 4 x 5 x 6 x 7 f (c) NAND-gate circuit 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S42 Equivalent multilevel NOR-gate circuit x 2 x 1 x 3 x 4 x 5 x 6 x 7 f (a) Inversions needed to convert to NORs x 2 x 1 x 3 x 4 x 5 x 6 x 7 f (b) NOR-gate circuit 20T3 COMP3222/9222 Optimized Implementation of Logic Functions Note that this circuit uses less gates and less levels of gates than the NAND-only circuit of L02/S42(c) L02/S43 Analysis of multilevel circuit P1 = x2x3 P2 = x5 + x6 P3 = x1 + P1 = x1 + x2x3 P4 = x4P2 = x4(x5 + x6) P5 = P4 + x7 = x4(x5 + x6) + x7 f = P3P5 = (x1 + x2x3)(x4(x5 + x6) + x7) = x1x4x5 + x1x4x6 + x1x7 + x2x3x4x5 + x2x3x4x6 + x2x3x7 x 2 x 1 x 3 x 4 x 5 x 6 x 7 f P 3 P 1 P 4 P 5 P 2 20T3 COMP3222/9222 Optimized Implementation of Logic Functions x7 f L02/S44 x1 x2 x3 x4 x5 P1 P 2 P3 (a) NAND-gate circuit f x1 x2 x3 x4 x5 f (b) Moving bubbles to convert to ANDs and ORs avoids multiple, tedious inversions Analyzing multilevel NOR/NAND-only circuits x1 x2 x4 fx5 (c) Circuit with AND and OR gates x3 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S45 x 2 x 3 x 1 x 4 x 5 f P 3 P 1 P 2 P 4 2 Exercise: What f does this circuit implement? 20T3 COMP3222/9222 Optimized Implementation of Logic Functions x5 f L02/S46 LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY func1 IS PORT ( x1, x2, x3 : IN BIT ; f : OUT BIT ) ; END func1 ; ARCHITECTURE LogicFunc OF func1 IS BEGIN f <= (NOT x1 AND NOT x2 AND NOT x3) OR (NOT x1 AND x2 AND NOT x3) OR (x1 AND NOT x2 AND NOT x3) OR (x1 AND NOT x2 AND x3) OR (x1 AND x2 AND NOT x3) ; END LogicFunc ; LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY func1 IS PORT ( x1, x2, x3 : IN STD_LOGIC ; f : OUT STD_ LOGIC ) ; END func1 ; ARCHITECTURE LogicFunc OF func1 IS BEGIN f <= (NOT x1 AND NOT x2 AND NOT x3) OR (NOT x1 AND x2 AND NOT x3) OR (x1 AND NOT x2 AND NOT x3) OR (x1 AND NOT x2 AND x3) OR (x1 AND x2 AND NOT x3) ; END LogicFunc ; The VHDL code for the function in L02/S3 Synthesizes to f = x1x2 + x3 Optimized Implementation of Logic Functions These two lines need to be included before every design module that uses data objects of type std_logic The std_logic package defines legal values and uses for data type; STD_LOGIC values: {0,1, Z, -, U, X, W, L, H} Z high impedance - don’t care U uninitialized X unknown W weak signal L weak tending to 0 H weak tending to 1 LIBRARY is needed to include package L02/S47 0 0 1 1 0 1 0 1 1 0 1 0 f 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 d d d d d d d d i 1 i 2 i 3 i 4 i 1 i 2 i 3 i 4 x 1 x 2 x 3 0 f LUT The VHDL code in L02/S47 implemented in a 4-LUT 20T3 COMP3222/9222 Optimized Implementation of Logic Functions f = x1x2 + x3 L02/S48 LIBRARY ieee; USE ieee.std_logic_1164.all; ENTITY func3 IS PORT ( x1, x2, x3, x4, x5, x6, x7 : IN STD_LOGIC; f : OUT STD_LOGIC); END func3; ARCHITECTURE LogicFunc OF func3 IS BEGIN f <= (x1 AND x3 AND NOT x6) OR (x1 AND x4 AND x5 AND NOT x6) OR (x2 AND x3 AND x7) OR (x2 AND x4 AND x5 AND x7); END LogicFunc; The VHDL code for the function of L02/S23 Synthesizes as f = (x1x6 + x2x7)(x3 + x4x5) 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S49 (a) Sum-of-products realization requires 5 4-LUTs x 6 x 4 f x 5 0 x 7 x 2 x 3 x 2 x 7 x 4 x 5 0 x 6 x 1 x 3 x 1 x 4 x 5 x 6 x 1 x 3 x 6 x 2 x 3 x 7 x 2 x 4 x 5 x 7 x 1 Implementation of the VHDL code in L02/S49 x 1 x 7 x 2 x 6 x 1 x 6 x 2 x 7 + x 5 x 3 x 4 f (b) Factored realization uses 2 4-LUTs 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S50 Exercise: • Determine the minimum-cost SOP and POS expressions for the function f(x1,x2,x3,x4) = Σm(4,6,8,10,11,12,15) + D(3,5,7,9) 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S51 Exercise: • Use Karnaugh maps to find the minimum-cost SOP and POS expressions for the function f(x1,..x4) = x1x3x4 + x3x4 + x1x2x4 + x1x2x3x4 assuming don’t cares are defined as D = Σ(9,12,14) 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S52 Circuit for problem 4.43 What is the cost of this circuit, assuming variables are available in complemented and un- complemented forms? Re-implement the circuit at the lowest possible cost. (Can you beat 33?) f g x 2 x 4 x 4 x 1 x 3 x 1 x 3 x 2 x 3 x 4 x 1 x 3 x 4 x 2 x 1 x 1 x 4 x 3 x 1 x 4 20T3 COMP3222/9222 Optimized Implementation of Logic Functions L02/S53