Class Note for ECE 380 at UA-Digital Logic(2)
Class Note for ECE 380 at UA-Digital Logic(2)
Popular in Course
Popular in Department
This 8 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Alabama - Tuscaloosa taught by a professor in Fall. Since its upload, it has received 13 views.
Reviews for Class Note for ECE 380 at UA-Digital Logic(2)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
ECE380 Digital Logic Optimized Implementation of Logic Functions Multilevel Synthesis and Analysis Electrical amp Computer Engineering Dr D J Jackson Lecture 141 Multilevel synthesis o For the previous minimization problems the goal was to always find a minimum SOP or POS realization of a given logic function 0 Circuits of this type have 2 levels stages of logic For SOP form the first level consists of only of AND gates that connect to a second level OR gate For POS form the first level consists of only of OR gates that connect to a second level AND gate 0 We assume that both true and complement forms of the input variables are available 0 A twolevel realization is usually efficient for functions of a few variables Electrical amp Computer Engineering Dr D J Jackson Lecture 142 Multilevel synthesis 0 As the number of inputs increases a two eve circuit may result in fanin problems depending on the technology used to implement the circuit 0 Fan in The number of inputs to a particular gate or circuit component 0 Consider the following minimum cost SOP expression fx1x7X1X3X6 X1X4X5X6 X2X3X7X2X4X5X7 Electrical amp Computer Engineering Dr D J Jackson Lecture 14quot Multilevel synthesis Consider implementing f in two types of PLDsa CPLD and an FPGA This CPLD implementation works because we have enough inputs at least 7 enough AND gates one per product term and enough OR gate inputs one for each AND gate output X1 X2 X3 X4 X5 X6 X7 unused E IHW i7 iz no 1 I quot J f x x i4 r7 i quot Electrical amp Computer Engineering Dr D J Jackson Lecture 144 Multilevel synthesis o If we have an FPGA that has only 2 input LUTS we cannot implement this function directly as written Since the minimum SOP form had terms with three and four literals requiring three and four input AND gates and There are four product terms needing to be ORed together requiring a fourinput OR gate 0 The fanin required to implement this function is too high for an FPGA with only 2 input LUTs Electrical amp Computer Engineering Dr D J Jackson Lecture 145 Multilevel synthesis 0 To solve this problem the function must be expressed in a form that has more than two levels of logic operations Such a form is called a multilevel logic expressnon 0 Two common techniques for synthesis of multilevel logic functions are Factoring Functional decomposition Electrical amp Computer Engineering Dr D J Jackson Lecture 146 Factoring o Factoring utilizes the distributive property to rewrite the expression in a form that generally has fewer literals per term fx1x7X1X3X6 X1X4X5X6 X2X3X7X2X4X5X7 fx1x7X1X6 X2X7X3X4X5 o In this form the function has no more than two literals comprising each term 0 It can be implemented using only 2 input LUTs Electrical amp Computer Engineering Dr D J Jackson Lecture 147 Factoring 0 I X1 0 X1X6 1 x5 0 C1 X1X6IX2X7 1 0 x2 0 1 0 0 XX 0 X7 1 2 7 0 0 f 1 x 0 x3 1 4 0 1 x o X4X5 1 X3X4X5 5 1 Electrical amp Computer Engineering Dr D J Jackson Lecture 148 Fanin problems o Fanin restrictions are not just a problem in PLDs as in the previous case 0 Fanin is also a problem for individual logic gates o In general as the number of inputs to a gate increases the propagation delay increases 0 Propagation delay is the total amount of time needed for a change at a gate input to cause a change at the gate output 0 Therefore we may wish to limit the number of inputs to a given gate 5 is a typical maximum Electrical amp Computer Engineering Dr D J Jackson Lecture 149 Fanin problems 0 Given the function fX1X2 X3X4 X5X6 X1X2X3 X4 X5 X6 o The direct solution for this would require 2 six input AND gates and 1 two input OR gate plus appropriate NOT gates o Factoring the function to the following form T f X1X4IX6X2X3X5 X2X339X5 o Gives a solution requiring 2 three input AND gates 1 two input OR gate and 1 four input AND gate Electrical amp Computer Engineering Dr D J Jackson Lecture 1410 Fanin problems 0 Factor the following expression so that the solution requires only 2 input AND and OR gates o Hint The solution will require 4 AND and 2 OR gates plus NOT gates fx1x7x1x2 x4 x5xlxz x6x7 x3 x4 x5x3 x6x7 Electrical amp Computer Engineering Dr D J Jackson Lecture 1411 Impact on wiring complexity Space on an integrated circuit is occupied by The circuitry that implements logic gates and Wires needed to make connections between gates o In a logic expression each literal corresponds to a wire in the circuit that carries the desired logic signal 0 Since factoring reduces the number of literals it also aides in reducing the wiring complexity in a logic circuit 0 During logic synthesis CAD tools consider parameters such as cost of the circuit number of gates fanin speed of the resulting logic and wiring complexity Electrical amp Computer Engineering Dr D J Jackson Lecture 1412 Functional decomposition 0 Complexity of a logic circuit in terms of wiring and logic gates can often be reduced by decomposing a two level circuit into subcircuits One or more subcircuits implement functions that may be used in several places to construct the final circuit 0 A single two level logic expression is replaced by two or more new expressions The new expressions are combined to define a multilevel circuit Electrical amp Computer Engineering Dr D J Jackson Lecture 1413 Decomposition example 0 Consider the following expression fwxyzxyw x zy z o In this form the function requires 1 three input AND gate 2 two input AND gates and 1 three input OR gate 0 COST4 gates 10 inputs 13 o COST19 if NOT gates and their inputs are included 0 Rewrite f into the following form fwxyzxyw x y z 0 Let gxyxy and note that g x y Electrical amp Computer Engineering Dr D J Jackson Lecture 1414 Decomposition example o The function f becomes fgwzgw39g39z o The circuit would be the following with a cost of 16 including NOT gates and their inputs 2 gtoJ 3 J D ID W Do D Eleunczl a Cnmrluler Enmnemnu m n 4 Jacksnn Lmure1dr15 Practical issues Functional decomposition is a powerful tool for reducing the complexity of logic functions It can also be used to implement general logic functions that have built in constraints For example in PLDs it is necessary to fit a desired logic circuit into logic blocks that are available on these devices Available logic blocks are a target for the decomposed subfunctions that are then used to form larger functions CAD tools make extensive use of the concept of functional decomposition Eleunczl a Cnmrluler Enmnemnu m n 4 Jacksnn Laclure 15716
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'