Digital and Logic System Design: Quine McCluskey Method PDF

DIGITAL AND LOGIC SYSTEM DESIGN Lecturer: Dwumfour Abdullai Aziz Email: [email protected] Mobile: 0260541219 UNIVERSITY OF GHANA CollegeofofEducation College Basic and Applied SchoolofofContinuing School Physical and Mathematical...

DIGITAL AND LOGIC SYSTEM DESIGN Lecturer: Dwumfour Abdullai Aziz Email: [email protected] Mobile: 0260541219 UNIVERSITY OF GHANA CollegeofofEducation College Basic and Applied SchoolofofContinuing School Physical and Mathematical and Distance Sciences Education 2022/2023 2014/2015 – 2016/2017 QUINE McCluskey MINIMIZATION TECHNIQUE Dwumfour Abdullai Aziz Slide 2 Prime Implicants and Essential Prime implicants Make the group of adjacent 1s(2,4,8…) Try to cover all the 1s using mininum number of groups Overlapping of groups is allowed Consider those minterms individually, which cannot be grouped with other minterms Dwumfour Abdullai Aziz Slide 3 Prime Implicants and Essential Prime implicants Implicant A group of 1s or single 1, which are adjacent and can be grouped in the k-map Dwumfour Abdullai Aziz Slide 4 Prime Implicants and Essential Prime implicants Prime Implicant The largest group of 1s which can be covered in the k-map Not fully covered by any other group Dwumfour Abdullai Aziz Slide 5 Prime Implicants and Essential Prime implicants Dwumfour Abdullai Aziz Slide 6 Prime Implicants and Essential Prime implicants Dwumfour Abdullai Aziz Slide 7 Prime Implicants and Essential Prime implicants Essential Prime Implicant (EPI) It is the prime implicant where at least one Minterm or 1 is not covered by any other prime implicant The essential prime implicants are always part of the minimal expression Dwumfour Abdullai Aziz Slide 8 Prime Implicants and Essential Prime implicants Dwumfour Abdullai Aziz Slide 9 Prime Implicants and Essential Prime implicants Finding the minimal solution / expression Find all the EPI and add them in the solution Determine the Minterms not covered by EPI Include the remaining Minterms using the non-EPI Dwumfour Abdullai Aziz Slide 10 QUINE McCLUSKEY MINIMIZATION TECHNIQUE Also known as the tabulation method is used to minimize the Boolean functions. It simplifies Boolean expression into the simplified form using prime implicants. This method is convenient to simplify Boolean expressions with more than 4 input variables Dwumfour Abdullai Aziz Slide 11  Steps for Quine McCluskey Method Step 1: Arrange the given Minterms according to the number of ones present in their binary representation in ascending order. Step 2: Take the Minterms from the continuous group if there is only a one-bit change to make match pair. Step 3: Place the ‘-‘ symbol where there is a bit change accordingly and keep the remaining bits the same. Step 4: Repeat steps 2 to 3 until we get all prime implicants (when all the bits present in the table are different). Dwumfour Abdullai Aziz Slide 12  Steps for Quine McCluskey Method Step 5: Make a prime implicant table that consists of the prime implicants (obtained Minterms) as rows and the given Minterms (given in problem) as columns. Step 6: Place ‘1’ in the Minterms (cell) which are covered by each prime implicant. Step 7: Observe the table, if the minterm is covered by only one prime implicant then it is an essential to prime implicant. Step 8: Add the essential prime implicants to the simplified Boolean function. Dwumfour Abdullai Aziz Slide 13  Steps for Quine McCluskey Method Example: Simplify the function below using the Tabular method F(X,Y Z,W) =∑!(0,1,3,7,8,9,11,15) Dwumfour Abdullai Aziz Slide 14  Steps for Quine McCluskey Method Obtain the binary representation of the minterms X Y Z W 0 0 0 0 0 1 0 0 0 1 3 0 0 1 1 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 11 1 0 1 1 15 1 1 1 1 Dwumfour Abdullai Aziz Slide 15 Step 1: Arrange the given Minterms according to the number of ones present in their binary representation in ascending order. Group Minterm X Y Z W 0 m0 0 0 0 0 1 m1 0 0 0 1 m8 1 0 0 0 2 m3 0 0 1 1 m9 1 0 0 1 1 0 0 1 3 m7 0 1 1 1 m11 1 0 1 1 4 m15 1 1 1 1 Step 2: Take the Minterms from the continuous group if there is only a one-bit change to make their pair. Step 3: Place the ‘-‘ symbol where there is a bit change accordingly and keep the remaining bits the same... STEP 2 AND 3 Group Matched pairs X Y Z W m0 –m1 0 0 0 - 0 m0 –m8 - 0 0 0 m1 –m3 0 0 - 1 1 m1 –m9 - 0 0 0 m8 –m9 1 0 0 - m3 –m7 0 - 1 1 2 m3 –m911 - 0 1 1 m9 –m11 1 0 - 1 3 m7 –m15 - 1 1 1 m11 –m15 1 - 1 1. STEP 4 Group Matched pairs X Y Z W m0 –m1 - m8 –m9 - 0 0 - 0 " 𝑌𝑍 m0 –m8 -m1 –m9 - 0 0 - m1 –m3-m9 –m11 - 0 - 1 1 " 𝑌𝑊 PI m1 –m9 -m3 –m11 - 0 - 1 m3 –m7 -m11 –m15 - - 1 1 2 Z𝑊 m3 –m11-m7 –m15 - - 1 1 Step 5: Make a prime implicant table that consists of the prime implicants (obtained Minterms) as rows and the given Minterms (given in problem) as columns. Step 6: Place ‘1’ in the Minterms (cell) which are covered by each prime implicant. Step 7: Observe the table, if the Minterms is covered by only one prime implicant then it is an essential to prime implicant. Dwumfour Abdullai Aziz Slide 20  PRIME IMPLICANTS PI Minterms Given Minterms Involved 0 1 3 7 8 9 11 15 !𝒁 𝒀 0, 1, 8, 9 X X X X !𝑾 𝒀 1, 3, 9, 11 X X X X ZW 3, 7, 11 , 15 X X X X Dwumfour Abdullai Aziz Slide 21 Step 8: Add the essential prime implicants to the simplified Boolean function. !𝑪 F= 𝑩 ! +CD Dwumfour Abdullai Aziz Slide 22  COMBINATIONAL CIRCUIT AND SEQUENTIAL DIGITAL LOGIC CIRCUIT Dwumfour Abdullai Aziz Slide 23