ITM omputer and ommunication Technologies Lecture #4 Part I: Introduction to omputer Technologies Logic ircuit Design & Simplification
ITM 計算機與通訊技術 2 23 香港中文大學電子工程學系 Logic function implementation Logic function implementation - SOP SOP This is usually called a sum-of-products (SOP) configuration. F F F =
ITM 計算機與通訊技術 3 23 香港中文大學電子工程學系 Product Product-Of Of-Sum (POS) onfiguration Sum (POS) onfiguration Product Of Sum obtained from truth table by making use of DeMorgan: OR (sum) the complemented inputs needed to get a low output in the truth table and ND (multiply) all such sums together F ( )( )( )( )( )( ) F =
Product-Of Of-Sum (POS) onfiguration In the POS extraction, each variable in a set of input variables that produces a low output is ORed together with other variables in that set. fterward, each set of ORed variables that produce a low output is NDed with other sets that produce low outputs. Extraction of the variables that produce low outputs is done in complementary form. F ( )( )( )( )( )( ) F = 23 香港中文大學電子工程學系 ITM 計算機與通訊技術 4
SOP Extraction vs. POS Extraction! When an SOP expression is extracted from a truth table, the expression is written to represent each high output condition. This is because the OR gate will output high when any of the sets of input variables produces a high output from the ND gates.! When a POS expression is extracted from a truth table, the expression is written to represent every low output condition on the truth table. This is because the ND gate will output low when any of the sets of input variables produce a low output from the OR gates.! Using DeMorgan s theorem, expressions for SOP and POS are proved to be equal. 23 香港中文大學電子工程學系 ITM 計算機與通訊技術 5
Some Definitions! Minterm: product term containing all input variables of a function in either true or complementary form e.g. F=! Maxterm: sum term containing all input variables of a function in either true or complementary form e.g. F=! anonical Form: a function expressed in either fully minterms or fully maxterms! Literal: each occurrence of a variable of a function in either true or complementary form 23 香港中文大學電子工程學系 ITM 計算機與通訊技術 6
Design Minimization! Reduce Hardware! Reduce Number of Inputs May be realized in oolean expression by having minimum number of terms minimum number of literals 23 香港中文大學電子工程學系 ITM 計算機與通訊技術 7
Design Minimization using oolean lgebra Example ( )( )( )( )( )( ) F = no. of terms = 6 no. of literals = 8 The above expression may be simplified using oolean algebra to: F = 23 香港中文大學電子工程學系 ITM 計算機與通訊技術 8
Karnaugh Map (K-Map)! Karnaugh map (K-map) is a pictorial method used to minimize oolean expressions without having to use oolean algebra theorems and equation manipulations. K-map can be thought of as a special version of a truth table.! Using a K-map, expressions with two to four variables are easily minimized. Expressions with five to six variables are more difficult but achievable, and expressions with seven or more variables are extremely difficult (if not impossible) to minimize using a K-map. 23 香港中文大學電子工程學系 ITM 計算機與通訊技術 9
Simplification using K-MapK Truth Table F F = 2-input K-map K-map simplification = ( ) = () = 23 香港中文大學電子工程學系 ITM 計算機與通訊技術
Simplification using K-MapK ny expression plotted on a K-map may be simplified by looping horizontally and/or vertically adjacent s. s shown on the right, once the looping has been completed, all complementary variables can be eliminated from the original expression. This will result in a simplified, yet equivalent expression. The that is horizontally adjacent to the loop stays in the output expression. Since and appear vertically adjacent to the horizontal loop, they may be eliminated. 23 香港中文大學電子工程學系 ITM 計算機與通訊技術
3-input K-mapK Layout of a 3-input K-map based on Gray ode () () ()() ()() 23 香港中文大學電子工程學系 ITM 計算機與通訊技術 2
4-input K-map K example D D D D D D 23 香港中文大學電子工程學系 ITM 計算機與通訊技術 3
K-Map Minimization Guideline! Loop all isolated s;! onsider each remaining separately. If it can be looped in more than one way, try include it in the largest possible loop;! minimal solution is derived as soon as all s are covered. In the process of making the largest loop, it is permissible to use previously covered s. 23 香港中文大學電子工程學系 ITM 計算機與通訊技術 4
Don t are ondition in K-MapK ertain combinations of inputs may be immaterial to a given function. For such don t care states the output is irrelevant and may be or. X X X don t care input condition If we use X=, F = This can be simplified (with X=) to F = With K-map, can be assigned to any don t care position to - form largest possible loop - ombine isolated to form a loop - In the example we can further simplify the expression by taking the bottom X as : F = 23 香港中文大學電子工程學系 ITM 計算機與通訊技術 5
Design Example: Majority Detector Design a 4-input circuit that will function as a majority detector. The circuit should output high when a majority of the inputs are high. The first step is to complete a truth table and mark high outputs for every set of input conditions that contains three or four (majority) s. This is shown in the truth table on the right. 23 香港中文大學電子工程學系 D X ITM 計算機與通訊技術 6
Design Example: Majority Detector D X Next, plot the oolean expression from the truth table on a K-map as shown and simplify the expression. D D D D X = D D D 23 香港中文大學電子工程學系 ITM 計算機與通訊技術 7
Design Example: Majority Detector The simplified expression is shown on the right, which has four terms since four pairs of s can be looped on the K-map. Implementation is straightforward as shown on the right because this is an SOP expression. The circuit requires four 3-input ND gates and one 4-input OR gate. 23 香港中文大學電子工程學系 X = D D D D D D ITM 計算機與通訊技術 8