Quine-McCluskey Method Part -1

 Quine-McCluskey Method

Quine-McCluskey (Tabulation) Method is an alternative method to replace Karnaugh-Map(K-maps). When there are more than 6 variables, K-maps are not efficient to minimized standard from Boolean function. However, for functions with more than six variables, it becomes very difficult to visualize how the minterms should be combined into subcubes. In addition, the K-map algorithm is not as straight forward to program the computer with. There exist a tabulation method called the Quine-McClusky method that are better suited for programming the computer, and thus can solve any function having any number of variables.

Example: f(w,x,y,z) = Σ(0,2,5,7,10,13,14,15)

The minterms is group according to the numbers of 1's in the minterms binary representation. For Example the Group0 does not have any 1's binary(0000), the group1 has only one 1's(0010), the group2 got 2 subcube minterms that have two 1's.

The next step, we construct another tables by combining the minterms in adjacent groups from the first table that differ in only one-bit position. For example, m0 and m2 differ in only the y bit. Thus, this table lists all the1-subcubes. A hyphen (-) is used in the bit position that is different in the two minterms. Since this 1-subcube covers the two individual minterms, we make a note of it by checking the two minterms in the "Subcube Covered" column in the previous table. The 1-subcube table is shown next
1-subcube table

We repeat the second step as long as there are adjacent subcubes that differ in only one-bit position including the hyphen. These subcubes are combined to give the next subcube table. From the above 1-subcube table, we get the following 2-subcube table.
2-subcube table

We stop when there are no more subcubes that can be combined. The prime implicants are those subcubes that are not covered, i.e. those without a checkmark in the Subcube Covered column. For example, from the last table (2-subcube table) the only subcube in this table has the value x = 1 and z = 1, thus we get the prime implicant xz.

From the 1-subcube table, we have the four prime implicants w'x'z', x'yz', wyz', and wxy. Note that these prime implicants may not necessary be all in the last table.

F = w'x'z' + xz + wyz'

Comments

Post a Comment

Popular posts from this blog

BCA Syllabus Topics

SEMESTER-2 nd Course: BCA SUBJECT: DIGITAL COMPUTER ORGANIZATION Syllabus : Unit-I : Digital computer and digital system; Binary number system: number base conversion. Compliments: one's, two's, 9's and 10's complements code: Gray BCD, ASCII, and error detection code. Logic Gates: AND, OR, NOT, EX-OR, Universal gate. Logic Circuit. Boolean function: Rules and simplification, simplification of Boolean function using map method, don't care condition. Unit-II: Combinational Circuits: Adders, Subtractors, Multiplexer, Demultiplexer Decoder, Encoder) Sequential Circuit: Flip-Flop: RS, Clocked RS, JK, D flip-flop, and Master board, Case studies to understand organization of laptop like Dell, Lenovo etc. slave flip-flop. Register- Introduction, Shift register, serial Transfer & parlor Load. Counters- Ripple Counter (Asynchronous), Synchronous Counters. Unit-III: 8086 internal architecture, register organization of 8086, addressing modes, instruction set and assembler ...
Read more

Quine-Mccluskey Method

Image
 Quine-Mccluskey Method It also known as Tabular method. It is more systematic method of minimizing expressions of even larger number of variables. It is suitable for hand computation as well as computation by machines i.e., programmable. . The procedure is based on repeated application of the combining theorem.  PA+P =P (P is set of literals) on all adjacent pairs of terms, yields the set of all PI‘s from which a minimal sum may be selected.  Consider expression ∑m(0,1,4,5)= + C+A +A C First,  second terms & third, fourth terms can be combined ( + ) + (C+ )= + A Reduced to (      +    ) = The same result can be obtained by combining m 0 & m 4 & m 1 &m 5 in first step & resulting terms in the second step. Procedure: Decimal Representation Don‘t cares PI chart EPI Dominating Rows & Columns Determination of Minimal expressions in c...
Read more

Alternate Logic-Gate Representations

Image
Alternate Logic-Gate Representations We have discussed the five basic logic gates (AND, OR, INVERTER, NAND, and NOR) and the standard symbols used to represent them in a logic circuit diagram. Most of the logic networks use standard symbols. But in some networks an alternative set of symbols is used in addition to the standard symbols. The table shows the alternate set of symbols for the five basic gates. Table: Alternate Logic Gate Representations To convert any normal symbol to its corresponding alternate symbol, the following steps are used: METHODOLOGY: TO CONVERT STANDARD SYMBOL TO ALTERNATE SYMBOL Step 1: Add bubbles (indication of inversion) at those input or output points where it is not present. Step 2: Remove all pre-existing bubbles of the normal symbol, if there is any at the point (only NOT, NAND and NOR gates) Step 3: If the existing normal logic symbol is AND, change it to OR, Similarly, if it is OR, then change it to AND. There is no change for the triangular symbol of ...
Read more