Misplaced Pages

#795204

72-602: The Quine–McCluskey algorithm ( QMC ), also known as the method of prime implicants , is a method used for minimization of Boolean functions that was developed by Willard V. Quine in 1952 and extended by Edward J. McCluskey in 1956. As a general principle this approach had already been demonstrated by the logician Hugh McColl in 1878, was proved by Archie Blake in 1937, and was rediscovered by Edward W. Samson and Burton E. Mills in 1954 and by Raymond J. Nelson in 1955. Also in 1955, Paul W. Abrahams and John G. Nordahl as well as Albert A. Mullin and Wayne G. Kellner proposed

144-406: A b c ′ {\displaystyle abc'} is numbered 110 2  = 6 10 and denoted m 6 {\displaystyle m_{6}} . Given the truth table of a logical function, it is possible to write the function as a "sum of products" or "sum of minterms". This is a special form of disjunctive normal form . For example, if given the truth table for

216-437: A Karnaugh map . The Quine–McCluskey algorithm can solve slightly larger problems. The field of logic optimization developed from the problem of finding optimal implementations of Boolean functions, such as minimal PoS and SoP forms. The sample truth tables for minterms and maxterms above are sufficient to establish the canonical form for a single bit position in the addition of binary numbers, but are not sufficient to design

288-489: A SAT solver . A heuristic method uses established rules that solve a practical useful subset of the much larger possible set of problems. The heuristic method may not produce the theoretically optimum solution, but if useful, will provide most of the optimization desired with a minimum of effort. An example of a computer system that uses heuristic methods for logic optimization is the Espresso heuristic logic minimizer . While

360-409: A minterm is a product term in which each of the n {\displaystyle n} variables appears exactly once (either in its complemented or uncomplemented form). Thus, a minterm is a logical expression of n variables that employs only the complement operator and the conjunction operator ( logical AND ). A minterm gives a true value for just one combination of the input variables,

432-406: A " * " in the previous step), and along the top go the minterms specified earlier. The don't care terms are not placed on top—they are omitted from this section because they are not necessary inputs. To find the essential prime implicants, we look for columns with only one "✓". If a column has only one "✓", this means that the minterm can only be covered by one prime implicant. This prime implicant

504-411: A 1-input NOR, is slower but for any word length the design only pays that penalty once (when the leftmost sum digit is developed). That's because those calculations overlap, each in what amounts to its own little pipeline without affecting when the next bit position's sum bit can be calculated. And, to be sure, the co ′ out of the leftmost bit position will probably have to be complemented as part of

576-421: A 4-input NOR gate we need to restate it as a product of sums (PoS), where the sums are the opposite maxterms. That is, In the maxterm example above, we wrote c o ( c i , x , y ) = M 0 M 1 M 2 M 4 {\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}} but to perform this with a 4-input NOR gate we need to notice

648-399: A clock signal to distinguish the previous inputs from the current inputs. They can be represented by finite state machines. Some examples are flip-flops and counters . While there are many ways to minimize a circuit, this is an example that minimizes (or simplifies) a Boolean function. The Boolean function carried out by the circuit is directly related to the algebraic expression from which

720-490: A decimal variant of the method. The Quine–McCluskey algorithm is functionally identical to Karnaugh mapping , but the tabular form makes it more efficient for use in computer algorithms, and it also gives a deterministic way to check that the minimal form of a Boolean F has been reached. It is sometimes referred to as the tabulation method. The Quine-McCluskey algorithm works as follows: Although more practical than Karnaugh mapping when dealing with more than four variables,

792-559: A drawback when trying to implement a function in canonical form, but there is a compensating bonus: such a gate with only one input implements the complementing function, which is required frequently in digital logic. This example assumes the Apollo parts inventory: 3-input NOR gates only, but the discussion is simplified by supposing that 4-input NOR gates are also available (in Apollo, those were compounded out of pairs of 3-input NORs). A set of 8 NOR gates, if their inputs are all combinations of

SECTION 10

#1733086123796

864-469: A formula in conjunctive normal form . Step two of the algorithm amounts to solving the set cover problem ; NP-hard instances of this problem may occur in this algorithm step. In this example, the input is a Boolean function in four variables, f : { 0 , 1 } 4 → { 0 , 1 } {\displaystyle f:\{0,1\}^{4}\to \{0,1\}} which evaluates to 1 {\displaystyle 1} on

936-454: A large number of variables have to be minimized with potentially non-optimal heuristic methods, of which the Espresso heuristic logic minimizer was the de facto standard in 1995. For one natural class of functions f {\displaystyle f} , the precise complexity of finding all prime implicants is better-understood: Milan Mossé, Harry Sha, and Li-Yang Tan discovered a near-optimal algorithm for finding all prime implicants of

1008-521: A minterm table. Don't-care terms are also added into this table (names in parentheses), so they can be combined with minterms: At this point, one can start combining minterms with other minterms in adjacent groups. If two terms differ by only a single digit, that digit can be replaced with a dash indicating that the digit doesn't matter. Terms that can't be combined any more are marked with an asterisk ( * ). For instance 1000 and 1001 can be combined to give 100- , indicating that both minterms imply

1080-482: A primary goal of minimizing the number of gates, and/or of minimizing the fanouts of signals to other gates since big fanouts reduce resilience to a degraded power supply or other environmental factors. In such a case, a designer may develop the canonical-form design as a baseline, then try a bottom-up development, and finally compare the results. The bottom-up development involves noticing that u = ci XOR ( x XOR y ), where XOR means eXclusive OR [true when either input

1152-407: A problem is the duality of minterms and maxterms, i.e. each maxterm is the complement of the like-indexed minterm, and vice versa. In the minterm example above, we wrote u ( c i , x , y ) = m 1 + m 2 + m 4 + m 7 {\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}} but to perform this with

1224-399: A similar manner, a canonical maxterm form can be reduced to various minimal PoS forms. While this example was simplified by applying normal algebraic methods [ f = ( a ′ + a ) b c {\displaystyle f=(a'+a)bc} ], in less obvious cases a convenient method for finding minimal PoS/SoP forms of a function with up to four variables is using

1296-427: A two-level circuit representation of circuits strictly refers to the flattened view of the circuit in terms of SOPs ( sum-of-products ) — which is more applicable to a PLA implementation of the design — a multi-level representation is a more generic view of the circuit in terms of arbitrarily connected SOPs, POSs ( product-of-sums ), factored form etc. Logic optimization algorithms generally work either on

1368-423: Is essential . For example: in the first column, with minterm 4, there is only one "✓". This means that m(4,12) is essential (hence marked by ). Minterm 15 also has only one "✓", so m(10,11,14,15) is also essential. Now all columns with one "✓" are covered. The rows with minterm m(4,12) and m(10,11,14,15) can now be removed, together with all the columns they cover. The second prime implicant can be 'covered' by

1440-414: Is a pair of gates cross-coupled to make a flip-flop: the output of each is wired as one of the inputs to the other.) There is also no need to create the complement form of the sum u . However, the carry out of one bit position must be passed as the carry into the next bit position in both direct and complement forms. The most straightforward way to do this is to pass co through a 1-input NOR gate and label

1512-588: Is a part of a logic synthesis applied in digital electronics and integrated circuit design . Generally, the circuit is constrained to a minimum chip area meeting a predefined response delay. The goal of logic optimization of a given circuit is to obtain the smallest logic circuit that evaluates to the same values as the original one. Usually, the smaller circuit with the same function is cheaper, takes less space, consumes less power , has shorter latency, and minimizes risks of unexpected cross-talk , hazard of delayed signal processing , and other issues present at

SECTION 20

#1733086123796

1584-416: Is divided into various categories: Graphical methods represent the required logical function by a diagram representing the logic variables and value of the function. By manipulating or inspecting a diagram, much tedious calculation may be eliminated. Graphical minimization methods for two-level logic include: The same methods of Boolean expression minimization (simplification) listed below may be applied to

1656-511: Is equivalent to a smaller SoP form. This smaller form would still consist of a sum of product terms, but have fewer product terms and/or product terms that contain fewer variables. For example, the following 3-variable function: has the canonical minterm representation f = a ′ b c + a b c {\displaystyle f=a'bc+abc} , but it has an equivalent SoP form f = b c {\displaystyle f=bc} . In this trivial example, it

1728-425: Is given a truth table of a logical function, it is possible to write the function as a "product of sums" or "product of maxterms". This is a special form of conjunctive normal form . For example, if given the truth table for the carry-out bit co of one bit position's logic of an adder circuit, as a function of x and y from the addends and the carry in, ci : Observing that the rows that have an output of 0 are

1800-455: Is made into an AND gate by passing each of its inputs through a 1-input NOR gate. However, this approach not only increases the number of gates used, but also doubles the number of gate delays processing the signals, cutting the processing speed in half. Consequently, whenever performance is vital, going beyond canonical forms and doing the Boolean algebra to make the unenhanced NOR gates do the job

1872-450: Is obvious that b c = a ′ b c + a b c {\displaystyle bc=a'bc+abc} , and the smaller form has both fewer product terms and fewer variables within each term. The minimal SoP representations of a function according to this notion of "smallest" are referred to as minimal SoP forms . In general, there may be multiple minimal SoP forms, none clearly smaller or larger than another. In

1944-521: Is tabulated as: The description of the bottom-up development mentions co ′ as an output but not co . Does that design simply never need the direct form of the carry out? Well, yes and no. At each stage, the calculation of co ′ depends only on ci ′, x ′ and y ′, which means that the carry propagation ripples along the bit positions just as fast as in the canonical design without ever developing co . The calculation of u , which does require ci to be made from ci ′ by

2016-419: Is the respective maxterm. That is, each maxterm is assigned an index based on the opposite conventional binary encoding used for minterms. The maxterm convention assigns the value 0 to the direct form ( x i ) {\displaystyle (x_{i})} and 1 to the complemented form ( x i ′ ) {\displaystyle (x'_{i})} . For example, we assign

2088-423: Is trial and error, but a more systematic way is Petrick's method . In the current example, the essential prime implicants do not handle all of the minterms, so, in this case, the essential implicants can be combined with one of the two non-essential ones to yield one equation: or Both of those final equations are functionally equivalent to the original, verbose equation: The pseudocode below recursively computes

2160-426: Is true but not when both are true], and that co = ci x + x y + y ci . One such development takes twelve NOR gates in all: six 2-input gates and two 1-input gates to produce u in 5 gate delays, plus three 2-input gates and one 3-input gate to produce co ′ in 2 gate delays. The canonical baseline took eight 3-input NOR gates plus three 4-input NOR gates to produce u, co and co ′ in 2 gate delays. If

2232-509: Is well worthwhile. We have now seen how the minterm/maxterm tools can be used to design an adder stage in canonical form with the addition of some Boolean algebra, costing just 2 gate delays for each of the outputs. That's the "top-down" way to design the digital circuit for this function, but is it the best way? The discussion has focused on identifying "fastest" as "best," and the augmented canonical form meets that criterion flawlessly, but sometimes other factors predominate. The designer may have

Quine–McCluskey algorithm - Misplaced Pages Continue

2304-409: The - 's must align and all but one of the other digits must be the same. For instance, -110 and -100 can be combined to give -1-0 , as can -110 and -010 to give --10 , but -110 and 011- cannot since the - 's do not align. -110 corresponds to BCD' while 011- corresponds to A'BC, and BCD' + A'BC is not equivalent to a product term. Note: In this example, none of

2376-545: The Quine–McCluskey algorithm that facilitate the process. Boolean function minimizing methods include: Methods that find optimal circuit representations of Boolean functions are often referred to as exact synthesis in the literature. Due to the computational complexity, exact synthesis is tractable only for small Boolean functions. Recent approaches map the optimization problem to a Boolean satisfiability problem. This allows finding optimal circuit representations using

2448-507: The 1 "true" value, a NOR gate is the simplest possible useful logical element. Specifically, a 3-input NOR gate may consist of 3 bipolar junction transistors with their emitters all grounded, their collectors tied together and linked to V cc through a load impedance. Each base is connected to an input signal, and the common collector point presents the output signal. Any input that is a 1 (high voltage) to its base shorts its transistor's emitter to its collector, causing current to flow through

2520-421: The 1st, 2nd, 3rd, and 5th, we can write co as a product of maxterms M 0 , M 1 , M 2 {\displaystyle M_{0},M_{1},M_{2}} and M 4 {\displaystyle M_{4}} . If we wish to verify this: evaluated for all 8 combinations of the three variables will match the table. It is often the case that the canonical minterm form

2592-534: The Quine–McCluskey algorithm also has a limited range of use since the problem it solves is NP-complete . The running time of the Quine–McCluskey algorithm grows exponentially with the number of variables. For a function of n variables the number of prime implicants can be as large as 3 n / n {\displaystyle 3^{n}/{\sqrt {n}}} , e.g. for 32 variables there may be over 534 × 10 prime implicants. Functions with

2664-428: The area of complex logic in integrated circuits . With the advent of logic synthesis , one of the biggest challenges faced by the electronic design automation (EDA) industry was to find the most simple circuit representation of the given design description. While two-level logic optimization had long existed in the form of the Quine–McCluskey algorithm , later followed by the Espresso heuristic logic minimizer ,

2736-1052: The arithmetic sum bit u of one bit position's logic of an adder circuit, as a function of x and y from the addends and the carry in, ci : Observing that the rows that have an output of 1 are the 2nd, 3rd, 5th, and 8th, we can write u as a sum of minterms m 1 , m 2 , m 4 , {\displaystyle m_{1},m_{2},m_{4},} and m 7 {\displaystyle m_{7}} . If we wish to verify this: u ( c i , x , y ) = m 1 + m 2 + m 4 + m 7 = ( c i ′ , x ′ , y ) + ( c i ′ , x , y ′ ) + ( c i , x ′ , y ′ ) + ( c i , x , y ) {\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}=(ci',x',y)+(ci',x,y')+(ci,x',y')+(ci,x,y)} evaluated for all 8 combinations of

2808-409: The binary string is used to represent the ticks within the prime implicant chart. The prime implicant chart can be created using the following steps: When written in pseudocode, the algorithm described above is: The utility function, ConvertToRegularExpression , is used to convert the prime implicant into the regular expression to check for matches between the implicant and the minterms. Using

2880-453: The circuit inventory actually includes 4-input NOR gates, the top-down canonical design looks like a winner in both gate count and speed. But if (contrary to our convenient supposition) the circuits are actually 3-input NOR gates, of which two are required for each 4-input NOR function, then the canonical design takes 14 gates compared to 12 for the bottom-up approach, but still produces the sum digit u considerably faster. The fanout comparison

2952-824: The circuit one would need two inverters , two AND gates , and an OR gate . The circuit can simplified (minimized) by applying laws of Boolean algebra or using intuition. Since the example states that A {\displaystyle A} is true when B {\displaystyle B} is false and the other way around, one can conclude that this simply means A ≠ B {\displaystyle A\neq B} . In terms of logical gates, inequality simply means an XOR gate (exclusive or). Therefore, ( A ∧ B ¯ ) ∨ ( A ¯ ∧ B ) ⟺ A ≠ B {\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B} . Then

Quine–McCluskey algorithm - Misplaced Pages Continue

3024-457: The circuit optimization. For the case when the Boolean function is specified by a circuit (that is, we want to find an equivalent circuit of minimum size possible), the unbounded circuit minimization problem was long-conjectured to be Σ 2 P {\displaystyle \Sigma _{2}^{P}} -complete in time complexity , a result finally proved in 2008, but there are effective heuristics such as Karnaugh maps and

3096-428: The complement operator and the disjunction operator ( logical OR ). Maxterms are a dual of the minterm idea, following the complementary symmetry of De Morgan's laws . Instead of using ANDs and complements, we use ORs and complements and proceed similarly. It is apparent that a maxterm gives a false value for just one combination of the input variables, i.e. it is true at the maximal number of possibilities. For example,

3168-622: The complementation pattern of the variables, where the variables are written in a standard order, usually alphabetical. This convention assigns the value 1 to the direct form ( x i {\displaystyle x_{i}} ) and 0 to the complemented form ( x i ′ {\displaystyle x'_{i}} ); the minterm is then ∑ i = 1 n 2 i − 1 value ⁡ ( x i ) {\displaystyle \sum \limits _{i=1}^{n}2^{i-1}\operatorname {value} (x_{i})} . For example, minterm

3240-521: The digital logic unless your inventory of gates includes AND and OR. Where performance is an issue (as in the Apollo Guidance Computer), the available parts are more likely to be NAND and NOR because of the complementing action inherent in transistor logic. The values are defined as voltage states, one near ground and one near the DC supply voltage V cc , e.g. +5 VDC. If the higher voltage is defined as

3312-446: The direct and complement forms of the 3 input variables ci, x, and y , always produce minterms, never maxterms—that is, of the 8 gates required to process all combinations of 3 input variables, only one has the output value 1. That's because a NOR gate, despite its name, could better be viewed (using De Morgan's law) as the AND of the complements of its input signals. The reason this is not

3384-571: The equality to the NOR of the same minterms. That is, One might suppose that the work of designing an adder stage is now complete, but we haven't addressed the fact that all 3 of the input variables have to appear in both their direct and complement forms. There's no difficulty about the addends x and y in this respect, because they are static throughout the addition and thus are normally held in latch circuits that routinely have both direct and complement outputs. (The simplest latch circuit made of NOR gates

3456-405: The first digit is 1 and the next two are 0 . When going from Size 2 to Size 4, treat - as a third bit value. Match up the - 's first. The terms represent products and to combine two product terms they must have the same variables. One of the variables should be complemented in one term and uncomplemented in the other. The remaining variables present should agree. So to match two terms

3528-406: The function is implemented. Consider the circuit used to represent ( A ∧ B ¯ ) ∨ ( A ¯ ∧ B ) {\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)} . It is evident that two negations, two conjunctions, and a disjunction are used in this statement. This means that to build

3600-466: The function, CreatePrimeImplicantChart , defined above, we can find the essential prime implicants by simply iterating column by column of the values in the dictionary, and where a single "1" is found then an essential prime implicant has been found. Minimization of Boolean functions Logic optimization is a process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. This process

3672-475: The index 6 to the maxterm a ′ + b ′ + c {\displaystyle a'+b'+c} (110) and denote that maxterm as M 6 . The complement ( a ′ + b ′ + c ) ′ {\displaystyle (a'+b'+c)'} is the minterm a b c ′ = m 6 {\displaystyle abc'=m_{6}} , using de Morgan's law . If one

SECTION 50

#1733086123796

3744-430: The interested reader, assisted by one more algebraic formula: u = ci ( x XOR y ) + ci ′( x XOR y )′]′. Decoupling the carry propagation from the sum formation in this way is what elevates the performance of a carry-lookahead adder over that of a ripple carry adder . One application of Boolean algebra is digital circuit design, with one goal to minimize the number of gates and another to minimize

3816-483: The load impedance, which brings the collector voltage (the output) very near to ground. That result is independent of the other inputs. Only when all 3 input signals are 0 (low voltage) do the emitter-collector impedances of all 3 transistors remain very high. Then very little current flows, and the voltage-divider effect with the load impedance imposes on the collector point a high voltage very near to V cc . The complementing property of these gate circuits may seem like

3888-411: The logic determining whether the addition overflowed. But using 3-input NOR gates, the bottom-up design is very nearly as fast for doing parallel addition on a non-trivial word length, cuts down on the gate count, and uses lower fanouts ... so it wins if gate count and/or fanout are paramount! We'll leave the exact circuitry of the bottom-up design of which all these statements are true as an exercise for

3960-436: The logical sum (logical OR, or disjunction) of all the terms being summed over. First, we write the function as a table (where 'x' stands for don't care): One can easily form the canonical sum of products expression from this table, simply by summing the minterms (leaving out don't-care terms ) where the function evaluates to one: which is not minimal. So to optimize, all minterms that evaluate to one are first placed in

4032-400: The maxterm a ′ + b + c ′ is false only when a and c both are true and b is false—the input arrangement where a = 1, b = 0, c = 1 results in 0. There are again 2 maxterms of n variables, since a variable in the maxterm expression can also be in either its direct or its complemented form—two choices per variable. The numbering is chosen so that the complement of a minterm

4104-402: The minimum nontrivial amount. For example, a b ' c , is true only when a and c both are true and b is false—the input arrangement where a = 1, b = 0, c = 1 results in 1. There are 2 minterms of n variables, since a variable in the minterm expression can be in either its direct or its complemented form—two choices per variable. Minterms are often numbered by a binary encoding of

4176-422: The minterm m 7 {\displaystyle m_{7}} , and the gate that generated it could have been eliminated. Nevertheless, it is still a good trade. Now we could have implemented those functions exactly according to their SoP and PoS canonical forms, by turning NOR gates into the functions specified. A NOR gate is made into an OR gate by passing its output through a 1-input NOR gate; and it

4248-414: The minterms and adds the dashes where necessary. The utility functions below assume that each minterm will be represented using strings. The pseudocode below can be split into two sections: The prime implicant chart can be represented by a dictionary where each key is a prime implicant and the corrresponding value is an empty string that will store a binary string once this step is complete. Each bit in

4320-538: The nano-scale level of metallic structures on an integrated circuit . In terms of Boolean algebra , the optimization of a complex Boolean expression is a process of finding a simpler one, which would upon evaluation ultimately produce the same results as the original one. The problem with having a complicated circuit (i.e. one with many elements, such as logic gates ) is that each element takes up physical space and costs time and money to produce. Circuit minimization may be one form of logic optimization used to reduce

4392-531: The number of levels here is 3, the total number of product terms and literals reduce because of the sharing of the term B + C. Similarly, we distinguish between combinational circuits and sequential circuits . Combinational circuits produce their outputs based only on the current inputs. They can be represented by Boolean relations . Some examples are priority encoders , binary decoders , multiplexers , demultiplexers . Sequential circuits produce their output based on both current and past inputs, depending on

SECTION 60

#1733086123796

4464-489: The output co ′, but that would add a gate delay in the worst possible place, slowing down the rippling of carries from right to left. An additional 4-input NOR gate building the canonical form of co ′ (out of the opposite minterms as co ) solves this problem. The trade-off to maintain full speed in this way includes an unexpected cost (in addition to having to use a bigger gate). If we'd just used that 1-input gate to complement co , there would have been no use for

4536-495: The output function f will be 1 for the minterms 4 , 8 , 10 , 11 , 12 {\displaystyle 4,8,10,11,12} and 15 {\displaystyle 15} (denoted by the 'm' term) and that we don't care about the output for 9 {\displaystyle 9} and 14 {\displaystyle 14} combinations (denoted by the 'd' term). The summation symbol ∑ {\displaystyle \sum } denotes

4608-553: The prime implicants given the list of minterms of a boolean function. It does this by trying to merge all possible minterms and filtering out minterms that have been merged until no more merges of the minterms can be performed and hence, the prime implicants of the function have been found. In this example the CheckDashesAlign and CheckMintermDifference functions perform the necessary checks for determining whether two minterms can be merged. The function MergeMinterms merges

4680-416: The rapidly improving chip densities, and the wide adoption of Hardware description languages for circuit description, formalized the logic optimization domain as it exists today, including Logic Friday (graphical interface), Minilog, and ESPRESSO-IISOJS (many-valued logic). The methods of logic circuit simplifications are equally applicable to Boolean expression minimization . Today, logic optimization

4752-402: The settling time. There are sixteen possible functions of two variables, but in digital logic hardware, the simplest gate circuits implement only four of them: conjunction (AND), disjunction (inclusive OR), and the respective complements of those (NAND and NOR). Most gate circuits accept more than 2 input variables; for example, the spaceborne Apollo Guidance Computer , which pioneered

4824-788: The structural (SOPs, factored form) or functional representation ( binary decision diagrams , algebraic decision diagrams ) of the circuit. In sum-of-products (SOP) form, AND gates form the smallest unit and are stitched together using ORs, whereas in product-of-sums (POS) form it is opposite. POS form requires parentheses to group the OR terms together under AND gates, because OR has lower precedence than AND. Both SOP and POS forms translate nicely into circuit logic. If we have two functions F 1 and F 2 : The above 2-level representation takes six product terms and 24 transistors in CMOS Rep. A functionally equivalent representation in multilevel can be: While

4896-412: The terms in the size 4 implicants table can be combined any further. In general this process should be continued (sizes 8, 16 etc.) until no more terms can be combined. None of the terms can be combined any further than this, so at this point we construct an essential prime implicant table. Along the side goes the prime implicants that have just been generated (these are the ones that have been marked with

4968-433: The third and fourth, and the third prime implicant can be 'covered' by the second and first, and neither is thus essential. If a prime implicant is essential then, as would be expected, it is necessary to include it in the minimized boolean equation. In some cases, the essential prime implicants do not cover all minterms, in which case additional procedures for chart reduction can be employed. The simplest "additional procedure"

5040-423: The three variables will match the table. For a boolean function of n variables x 1 , … , x n {\displaystyle {x_{1},\dots ,x_{n}}} , a maxterm is a sum term in which each of the n variables appears exactly once (either in its complemented or uncomplemented form). Thus, a maxterm is a logical expression of n variables that employs only

5112-506: The two circuits shown below are equivalent, as can be checked using a truth table : Sum of products Other canonical forms include the complete sum of prime implicants or Blake canonical form (and its dual), and the algebraic normal form (also called Zhegalkin or Reed–Muller). For a boolean function of n {\displaystyle n} variables x 1 , … , x n {\displaystyle {x_{1},\dots ,x_{n}}} ,

5184-683: The values 4 , 8 , 10 , 11 , 12 {\displaystyle 4,8,10,11,12} and 15 {\displaystyle 15} , evaluates to an unknown value on 9 {\displaystyle 9} and 14 {\displaystyle 14} , and to 0 {\displaystyle 0} everywhere else (where these integers are interpreted in their binary form for input to f {\displaystyle f} for succinctness of notation). The inputs that evaluate to 1 {\displaystyle 1} are called 'minterms'. We encode all of this information by writing This expression says that

#795204