QUINE-McCLUSKEY MINIMIZATION

		QUINE-McCLUSKEY MINIMIZATION
		Quine-McCluskey minimization method uses the same theorem to produce the solution as the K-map method, namely X(Y+Y')=X
		Minimization Technique
		The expression is represented in the canonical SOP form if not already in that form. The function is converted into numeric notation. The numbers are converted into binary form. The minterms are arranged in a column divided into groups. Begin with the minimization procedure. Each minterm of one group is compared with each minterm in the group immediately below. Each time a number is found in one group which is the same as a number in the group below except for one digit, the numbers pair is ticked and a new composite is created. This composite number has the same number of digits as the numbers in the pair except the digit different which is replaced by an "x". The above procedure is repeated on the second column to generate a third column. The next step is to identify the essential prime implicants, which can be done using a prime implicant chart. Where a prime implicant covers a minterm, the intersection of the corresponding row and column is marked with a cross. Those columns with only one cross identify the essential prime implicants. -> These prime implicants must be in the final answer. The single crosses on a column are circled and all the crosses on the same row are also circled, indicating that these crosses are covered by the prime implicants selected. Once one cross on a column is circled, all the crosses on that column can be circled since the minterm is now covered. If any non-essential prime implicant has all its crosses circled, the prime implicant is redundant and need not be considered further. Next, a selection must be made from the remaining nonessential prime implicants, by considering how the non-circled crosses can be covered best. One generally would take those prime implicants which cover the greatest number of crosses on their row. If all the crosses in one row also occur on another row which includes further crosses, then the latter is said to dominate the former and can be selected. The dominated prime implicant can then be deleted.
		Example
		Find the minimal sum of products for the Boolean expression, f=(1,2,3,7,8,9,10,11,14,15), using Quine-McCluskey method.
		Firstly these minterms are represented in the binary form as shown in the table below. The above binary representations are grouped into a number of sections in terms of the number of 1's as shown in the table below.
		Binary representation of minterms
		Minterms U V W X 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 14 1 1 1 0 15 1 1 1 1
		Group of minterms for different number of 1's
		No of 1's Minterms U V W X 1 1 0 0 0 1 1 2 0 0 1 0 1 8 1 0 0 0 2 3 0 0 1 1 2 9 1 0 0 1 2 10 1 0 1 0 3 7 0 1 1 1 3 11 1 0 1 1 3 14 1 1 1 0 4 15 1 1 1 1
		Any two numbers in these groups which differ from each other by only one variable can be chosen and combined, to get 2-cell combination, as shown in the table below.
		2-Cell combinations
		Combinations U V W X (1,3) 0 0 - 1 (1,9) - 0 0 1 (2,3) 0 0 1 - (2,10) - 0 1 0 (8,9) 1 0 0 - (8,10) 1 0 - 0 (3,7) 0 - 1 1 (3,11) - 0 1 1 (9,11) 1 0 - 1 (10,11) 1 0 1 - (10,14) 1 - 1 0 (7,15) - 1 1 1 (11,15) 1 - 1 1 (14,15) 1 1 1 -
		From the 2-cell combinations, one variable and dash in the same position can be combined to form 4-cell combinations as shown in the figure below.
		4-Cell combinations
		Combinations U V W X (1,3,9,11) - 0 - 1 (2,3,10,11) - 0 1 - (8,9,10,11) 1 0 - - (3,7,11,15) - - 1 1 (10,11,14,15) 1 - 1 -
		The cells (1,3) and (9,11) form the same 4-cell combination as the cells (1,9) and (3,11). The order in which the cells are placed in a combination does not have any effect. Thus the (1,3,9,11) combination could be written as (1,9,3,11).
		From above 4-cell combination table, the prime implicants table can be plotted as shown in table below.
		Prime Implicants Table
		Prime Implicants 1 2 3 7 8 9 10 11 14 15 (1,3,9,11) X - X - - X - X - - (2,3,10,11) - X X - - - X X - - (8,9,10,11) - - - - X X X X - - (3,7,11,15) - - - - - - X X X X - X X - X X - - - X -
		The columns having only one cross mark correspond to essential prime implicants. A yellow cross is used against every essential prime implicant. The prime implicants sum gives the function in its minimal SOP form.
		Y = V'X + V'W + UV' + WX + UW