How To Draw Cmos Networks From Boolean Functions
Minimizing Boolean Functions
Introduction
This document describes graphical and algebraic ways to minimize boolean functions. Information technology includes a Java program that you tin can use to experiment with the algebraic algorithm outlined beneath. The field of study of minimization is also covered in many textbooks, articles, and other web sites. Here are a few references:
Why Minimize?
All the datapath and control structures of a digital device can be represented as boolean functions, which have the general form:
y = Σ(x, … )
where "(ten, … )" is a set of boolean variables (variables that may take on merely the values zero and ane). These boolean functions must exist converted into logic networks in the nigh economic way possible. What qualifies as the "most economical way possible" varies, depending on whether the network is built using discrete gates, a programmable logic device with a fixed complement of gates available, or a fully-customized integrated circuit. But in all cases, minimization yields a network with as pocket-size a number of gates every bit possible, and with each gate as simple every bit possible.
To appreciate the importance of minimization, consider the two networks in Figures ane and 2. Both behave exactly the same fashion! No affair what pattern of ones and zeros y'all put into a, b, and c in Fig. one, the value it produces at y will be exactly matched if you put the same pattern of values into the corresponding inputs in Fig. two. Nevertheless the network in Fig. 2 uses far fewer gates, and the gates it uses are simpler (have smaller fan-ins) than the gates in Fig. 1. Clearly, the minimized circuit should be less expensive to build than the unminimized version. Although information technology is not truthful for Fig. two, it is frequently the case that minimized networks will exist faster (accept fewer propagation delays) than unminimized networks.
Effigy ane
Figure ii
Background and Terminology
- The variables in the expression on the right side of a boolean equation are the input wires to a logic network. The left side of a boolean equation is the output wire of the network.
- Any boolean equation or combinational logic network can be completely and exactly characterized by a truth table. A truth table lists every possible combination of values of the input variables, and the respective output value of the function for each combination. There are two due north rows in the truth table for a function or network with due north input variables, so it isn't always applied to write out an entire truth table. Only for relatively small-scale values of n, a truth table provides a convenient way to describe the function or network's behavior exactly.
- Every row of a truth tabular array with a ane in the output column is called a minterm. A convenient mode to represent a truth table is to treat each combination of input variables as a binary number and to list the numbers of the rows that are minterms.
This document uses the part with the following truth table as a running case:
a b c Y 0 0 0 0 0 0 1 ane 0 i 0 ane 0 1 1 0 1 0 0 i 1 0 1 one 1 1 0 i 1 1 ane ane This truth table can too be represented every bit the list of minterms, [ 1, 2, 4, 5, 6, 7 ]. That is, the truth table has a i in the Y column for the rows where the binary number represented by the values of a, b, and c is one of the numbers listed inside the square brackets. The other two rows (0 and 3) have a 0 in the Y column, and thus are non minterms.
- One standard way to stand for any boolean function is called "sum of products" (SOP) or, more than formally, disjunctive normal form. In this form, the function is written as the logical OR (indicated by +) of a set of AND terms, one per minterm.
For case, the disjunctive normal class for our sample role would be:
Y = a'b'c + a'bc' + ab'c' + ab'c + abc' + abc
- There is too a conjunctive normal form, which represents an expression as a production of sums rather than equally a sum of products. The material presented below tin be extended to deal with conjunctive normal forms rather than disjunctive normal forms. We'll exit that as every bit ane of those classic "exercises left for the educatee," and deal with simply disjunctive normal forms.
- A literal is a variable that is either complemented or not in a production term. The minterms in our sample function have a total of vi literals: a, a', b, b', c, and c'. The network in Figure 2 uses only 5 literals because a' isn't used. In the disjunctive normal form of a part, each production term has ane literal for each variable. (vi literals for 3 variables in our example office.)
- Figure 1 implements our sample function, and demonstrates translating a disjunctive normal form role directly into a logic network. The translation procedure is as follows:
- Use inverters to generate all possible literals (the 6 vertical wires on the left in Fig. one).
- Describe an AND gate for each minterm. The fan-in (number of inputs) of each AND gate is equal to the number of input variables.
- Connect the outputs of all the AND gates to a single OR gate.
- Connect the inputs of each AND gate to a pattern of literals in such a way that it volition generate a ane when the pattern of input values matches the particular minterm assigned to it.
- A minimal form of a boolean expression is ane which implements the expression with equally few literals and production terms as possible. At that place may be more than 1 minimal form of an expression; if there is jut 1 minimal form, that form is the minimum.
- There are many rules for manipulating a boolean expression algebraically, but there is just ane rule that yous need in order to minimize a office in one case it is in disjunctive normal form: the dominion of complementation.
The rule of complementation says that (x + x') is always true (1), so any two terms that are in the grade (x + x')Y can be reduced to just Y without changing its meaning. Another way of saying this is that two production terms can be simplified if the only departure between them is the value of exactly one variable, in which case that variable can be eliminated from both terms to give an equivalent unmarried term. For example ab'c + a'b'c is equivalent to (a + a')b'c, which is the same as the single production term, b'c.
Karnaugh Maps
A Karnaugh Map is a graphical way of minimizing a boolean expression based on the rule of complementation. It works well if there are 2, 3, or 4 variables, but gets messy or impossible to utilise for expressions with more variables than that.
The idea behind a Karnaugh Map (Karnaugh, 1953) is to draw an expression's truth table equally a matrix in such a fashion that each row and each column of the matrix puts minterms that differ in the value of a single variable adjacent to each other. Then, by grouping adjacent cells of the matrix, you tin identify product terms that eliminate all complemented literals, resulting in a minimized version of the expression.
Figure 3 shows how the minterms in truth tables are placed in a Karnaugh Map grid for both 3 and 4 variable expressions.
Effigy 3
Looking at the 3 variable map on the left in Fig. three, annotation that minterm 0 (000two) is merely above minterm 4 (1002). This arrangement means that if both minterms 0 and 4 occur in a function, the first variable (the ane named a in Fig. three) appears in both its true and complemented grade, and can be eliminated. The acme row of the Karnaugh Map is labeled with a' and the lower row with a: Any minterms appearing in the top row have the literal a' in them, and any minterms in the lesser row have the literal a in them. At the same fourth dimension, note that each cavalcade has the aforementioned values for the variables b and c. Also, the columns are arranged in an lodge so that only i variable changes value equally you go from one column to the side by side. Thus, the first two columns differ in the value of c, the second and third columns differ in the value of b, and the 3rd and fourth columns differ in the value of c once again. Furthermore, the first and quaternary columns are "next to" each other as well, considering they differ from each other merely in the value of b.
The right side of Figure 3 shows that this same pattern (adjacent columns differ by the value of a single variable) applies to the rows of a Karnaugh map likewise: The first and second rows of that map differ in the value of b, the 2d and 3rd differ in the value of a, the third and fourth differ in the value of b, and the first and fourth differ in the value of a.
Effigy iv shows our sample part drawn as a Karnaugh Map. Minterms one and 2 are in the second and fourth columns of the pinnacle row, while minterms iv, five, vii, and 6 appear from left to correct in the 4 columns of the bottom row.
Figure iv
A Karnaugh Map is used to produce a minimal sum of products implementation of an expression past drawing rectangles effectually groups of adjacent minterms in the map; each rectangle will correspond to i production term, and the full expression will be constructed as the OR (sum) of all the product terms. The goal is to have as few product terms equally possible, which implies that each product term volition business relationship for as many minterms as possible.
Here are the rules for drawing the rectangles:
- Every minterm must be inside at least i rectangle, but there must non be whatever zeros inside any rectangles.
- Every rectangle has to exist as large as possible.
- Rectangles may wrap effectually to include cells in both the leftmost and rightmost columns. as well for the top and bottom rows.
- The number of minterms enclosed in a rectangle must be a power of two (1, 2, 4, 8, or xvi minterms for 4-variable maps).
- Some functions have "don't care" atmospheric condition, which are combinations of inputs that volition never occur, resulting in cases where it doesn't matter whether the output is a zero or a one. Where these don't care conditions appear in a Karnaugh Map (ordinarily indicated by Ten'due south instead of ones or zeros), they may be included inside rectangles or not depending on what volition make the rectangles equally few and every bit large as possible.
Figure 5 shows the rectangles for our sample function, post-obit the procedure outlined above:
Figure v
The largest rectangle (the lesser row) corresponds to the product term a. By enclosing four minterms, two variables take been eliminated resulting in a single product term with a unmarried variable. The rectangle in the 2nd column encloses two minterms, eliminating one variable (a) from that production term. Similarly, the rectangle in the fourth column eliminates a from that production term. The resulting sum of products function is:
y = a + b'c + bc'
If yous examine Fig. two, you lot volition see that that logic network implements exactly this role.
Every time you double the number of minterms within a rectangle, yous eliminate ane variable from the resulting product term. Every doubling corresponds to applying the rule of complementation once more. The adjacent section shows how to do the same thing algebraically.
The Interactive Karnaugh Map mentioned at the beginning of this page is a very nice way to see how to depict the rectangles. You can enter the role you want to process algebraically, by editing a truth table, or just by clicking on cells in the Karnaugh Map itself. Figure half dozen is a screen shot of the applet showing how it displays our sample office:
Figure 6
Algebraic Minimization
Minimizing an expression algebraically involves repeatedly applying the dominion of complementation, starting with the disjunctive normal course of the office, and ending with a prepare of production terms chosen prime implicants. A prime implicant is a product term that will generate ones only for combinations of inputs that are minterms of the disjunctive normal class of the function, and which cannot be further reduced past combining with whatever other term. They correspond to the rectangles in a Karnaugh Map.
We volition call each step in this process a "laissez passer." Information technology takes 2 passes to minimize our sample role. The following chart shows the original disjunctive normal course of the function every bit "Pass 0" and shows what reductions are performed for the other 2 passes.
--------------------------------------------------------------- | Pass 0: a'b'c + a'bc' + ab'c' + ab'c + abc' + abc | --------------------------------------------------------------- --------------------------------------------------------------- | Laissez passer one: a'b'c + ab'c reduces to b'c | | a'bc' + abc' reduces to bc' | | ab'c + ab'c' reduces to ab' | | abc' + abc reduces to ab | --------------------------------------------------------------- | b'c + bc' + ab' + ab | --------------------------------------------------------------- --------------------------------------------------------------- | Pass two: ab' + ab reduces to a | --------------------------------------------------------------- | a + b'c + bc' | ---------------------------------------------------------------
The rules to follow for each pass are:
- Each term present in one pass must exist combined with some other term if possible.
- Any terms that cannot be combined are carried frontwards unchanged to the adjacent pass.
- A term that has already been used in one case in a laissez passer should be used again if it will let another term to be reduced. For case, in Laissez passer 1 above, ab'c is used twice, then is abc'.
The dominion about reusing terms in a pass corresponds to circling some minterms more than one time in a Karnaugh Map. The 2 minterms that are reused in Pass 1 to a higher place are exactly the same two that are circled twice in the Karnaugh Map of Figure 5.
Once the prime implicants of an expression have been determined, a minimal subset of them has to be selected. Picking a minimal subset of prime implicants relies on the notion of minterms beingness "covered" by prime implicants. For our sample part, the prime implicant a covers minterms four, five, 6, and vii; the prime number implicant b'c covers minterms one and v, and and the prime implicant bc' covers minterms 2 and six. In this example, nosotros need all iii prime implicants in order to comprehend all the minterms at least once, and the expression shown at the end of Pass 2 is the minimized class for our sample function.
Simply whenever there is more than one minimal form for an expression, the different forms volition correspond to different subsets of the complete set of prime implicants. For any 1 of the minimal forms in that location volition be extra prime number implicants that have to be discarded.
The following procedure describes a way to determine one minimal form of an expression after all the prime implicants have been determined.
- For every minterm that is covered by just one prime number implicant, that prime implicant must be included in the minimal class. These minterms are called essential prime number implicants considering it is essential to include them in the minimization.
For our sample role, minterms 2, three, and 4 are each covered by exactly one prime implicant, then all three of the prime implicants are essential, there is but i minimized form, and there is nothing more to do.
- Make a listing of all minterms that are not covered by whatever of the essential prime implicants.
- Make a list of unused prime implicants. Gild this listing by the number of literals each prime implicant contains.
- If any remaining minterms are covered by just 1 of the remaining prime implicants, the corresponding prime number implicants must exist added to the minimization, and all the minterms they comprehend must exist removed from the list of uncovered minterms.
- If there are whatsoever uncovered minterms add the unused prime number implicant with the smallest number of literals to the minimization, and remove all minterms that are covered past this prime implicant from the list of uncovered minterms.
If ii or more prime implicants have every bit small-scale numbers of literals, in that location is more than than 1 minimal solution. Finding them all involves systematically substituting each of the tied prime implicants into the different minimal forms being generated.
- Remove all prime implicants that fail to encompass any of the remaining minterms from the list of unused prime implicants.
- Echo the previous three steps until all minterms have been covered.
Disclaimer! The algorithm given here is based on the Quine-McClusky "nautical chart" method described in (McClusky, 1965) and in (Kohavi, 1970). Merely information technology is not exactly the aforementioned as the procedure given in those references, and may non produce the same results. It should, all the same, produce a fully minimized function.
Minimization Plan
There are two version of the minimization plan available. The beginning was developed in 2000. It must be invoked from a command prompt such equally a Windows "DOS Window" or a Fifty/Unix shell prompt. The 2nd version was developed in 2005, and can yet be run from a control prompt, merely also tin can be run with a graphical user interface. Both versions require a Java runtime environment (JRE), bachelor from Sunday Microsystems' Java web site. The outset version of the program volition work with JRE version 1.3 or subsequently, and probably works with some older JRE's as well. The second version definitely needs JRE version 1.5 or afterward.
Download either version of the program:
- Minimize.jar: The current version of the program. Requires JRE 1.5 or subsequently. Includes source lawmaking.
- Minimize.zip: Previous version of the programme. Runs with JRE 1.3 or later. Does not include source lawmaking.
The program allows you to enter either a boolean expression or a list of minterm numbers, and displays a serial of messages that bear witness the steps it followed to perform the minimization. Some expressions can be minimized more than than one fashion, just the plan shows but i minimization even if others are possible.
Running the Programme
Electric current Version
If yous are running Windows and have the proper JRE installed, you tin run the program by double-clicking on it'south icon.
You may enter either a boolean expression or a listing of minterm numbers in the entry field in the upper left corner of the window, and the minimized version of the expression will announced immediately below it. Practise not use quotes for either blazon of input. Use single-letter variable names (case sensitive), * or nothing for AND, + for OR, ^ for XOR, and ' for postfix Non. You may also utilise the boolean constants 0 and 1, and you lot may employ parentheses to control evaluation order. When inbound minterm numbers instead of an expression, apply either spaces or commas to separate the numbers.
When yous enter an expression or minterm list, the minimized result of the algorithm appears immediately below the entry field. This string is automatically copied to the system clipboard and tin exist pasted into some other application if desired. (There is no visual indication that the result string has been selected, but it tin can be pasted.)
The Minterm Table immediately below the minimized result shows the minterms for the sum of products form of the expression you entered. The left column shows the production terms equally truth table row numbers, and the right cavalcade shows the product terms algebraically. The Prime Implicant Table below that shows each minimized production term in the first column, and a list of the full production terms that each minimized term "covers" (implies) in the second column.
The right side of the window shows the processing steps the program went through to practice the minimization. (Or an fault message if you entered an invalid expression.) This is the data that is written to the console when you run either version of the program from the command line.
Use the "New Window" button if y'all desire to have multiple minimizations visible at the same fourth dimension. The size, shape, and interior divisions of the last window you lot get out will be reused if you run the program again.
You tin can also launch the graphical interface from the command line using the command, coffee -jar Minimize.jar. If yous want to run the command line version, the command is:
coffee -cp Minimize.jar MinimizedTable <expression or minterm listing>
.
See the description of the older program version beneath for the syntax of <expression or minterm list>.
Previous Version
Open a command line window on your computer, and modify to the directory where y'all downloaded Minimize.zero. The command to run the program is:
java -cp Minimize.zip Minimize <expression or minterm list>
The boolean expression you lot enter on the control line must utilise the following syntax:
- Put quotes around the entire expression so that embedded spaces and other symbols such every bit asterisks will non be modified by the command interpreter.
- Employ unmarried letters for the variable names. Upper and lowercase letters are different variables. Don't utilize more than than 31 different variables. (Your reckoner volition undoubtedly run out of memory earlier you get close to this limit.)
- Use * for AND, + for inclusive OR, and ^ for exclusive OR. Y'all can leave out the *'southward. That is, ab is the same as a*b.
- Employ ' for complementation after the detail to be complemented.
- AND has precedence over OR and XOR. The latter two will be evaluated in right to left order. Apply parentheses to control the club of evaluation.
- Spaces have no effect.
- The constant literals 0 and 1 may be used.
Alternatively, you may write a list of minterm numbers on the command line. There must be spaces but no commas between numbers. The largest minterm number yous supply will determine the number of variables in the expression and the number of rows in the resulting truth table. For example:
java -cp Minimize.nada Minimize 4 6
At that place have to be three variables and eight rows in the truth tabular array to include these ii minterms. The variables will automatically be named a, b, and c.
Sample Output (First Version of the Program)
$ coffee -cp Minimize.naught Minimize "a+b^c" Finding One Minimization Minterm Numbers: [1,two,4,five,half-dozen,vii] Reduced ab'c and a'b'c to b'c in pass 1. Reduced abc' and a'bc' to bc' in pass 1. Reduced ab'c and ab'c' to ab' in pass 1. Reduced abc' and ab'c' to air conditioning' in laissez passer 1. Reduced abc and ab'c to air conditioning in laissez passer ane. Reduced abc and abc' to ab in pass 1. Unable to reduce b'c in laissez passer two Unable to reduce bc' in pass 2 Reduced ab and ab' to a in laissez passer two. Unable to reduce b'c in pass 3 Unable to reduce bc' in pass 3 Unable to reduce a in pass three Minterm 1 is covered by one prime implicant. Minterm two is covered by 1 prime implicant. Minterm 4 is covered by 1 prime implicant. Minterm 5 is covered by 2 prime implicants. Minterm 6 is covered by 2 prime implicants. Minterm 7 is covered past 1 prime number implicant. Expression: a+b^c Sum of products: a'b'c + a'bc' + ab'c' + ab'c + abc' + abc Prime implicants: [ a: ab'c', ab'c, abc', abc ], [ b'c: a'b'c, ab'c ], [ bc': a'bc', abc' ] Minimized: b'c + bc' + a $ coffee -cp Minimize.zip Minimize "aa'+b1" Finding 1 Minimization Minterm Numbers: [1,3] Reduced ab and a'b to b in pass 1. Unable to reduce b in pass 2 Minterm i is covered past i prime implicant. Minterm three is covered by i prime implicant. Expression: a*a'+b*one Sum of products: a'b + ab Prime number implicants: [ b: a'b, ab ] Minimized: b $
Source: https://babbage.cs.qc.cuny.edu/courses/Minimize/
Posted by: phillipsboild1989.blogspot.com
0 Response to "How To Draw Cmos Networks From Boolean Functions"
Post a Comment