Optimal Gate-Level Minimization Techniques for Digital Circuits
"Explore gate-level minimization techniques for designing optimal Boolean function implementations in digital circuits. Learn about the importance of minimizing variables using K-map and step-by-step solving methods."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Gate Gate- -level minimization refers to the design task of finding an optimal gate-level implementation of Boolean functions describing a digital circuit. level minimization 5
In many digital circuits and practical problems we need to find expression with minimum variables. We can minimize Boolean expressions of 3, 4 variables very easily using K-map without using any Boolean algebra theorems. 6
K K- -map and Product of Sum (POS) of problem. map can take two forms Sum of Product (SOP) Product of Sum (POS) according to the need Sum of Product (SOP) K-map is table like representation but it gives more information than TRUTH TABLE. We fill grid of K-map with 0 s and 1 s then solve it by making groups. 7 March 18, 2025
Steps to solve expression using Select K-map according to the number of variables. Identify minterms or maxterms as given in problem. For SOP put 1 s in blocks of K-map respective to the minterms (0 s elsewhere). For POS put 0 s in blocks of K-map respective to the maxterms(1 s elsewhere). Make rectangular groups containing total terms in power of two like 2,4,8 ..(except 1) and try to cover as many elements as you can in one group. From the groups made in step 5 find the product terms and sum them up for SOP form. Steps to solve expression using K K- -map map 1. 2. 3. 4. 5. 6. 8
A two-variable map Four minterms x' = row 0; x = row 1 y' =column 0; y =column 1 A truth table in square diagram Fig. 3.2(a): xy = m3 Fig. 3.2(b): x+y = x'y+xy' +xy = m1+m2+m3 Figure 3.1 Two-variable Map Figure 3.2 Representation of functions in the map 9
A three-variable map Eight minterms The Gray code sequence Any two adjacent squares in the map differ by only on variable Primed in one square and unprimed in the other e.g., m5 and m7can be simplified m5+ m7 = xy'z + xyz = xz (y'+y) = xz Figure 3.3 Three-variable Map 10
m0and m2(m4 and m6) are adjacent m0+ m2= x'y'z' + x'yz' = x'z' (y'+y) = x'z' m4+ m6= xy'z' + xyz' = xz' (y'+y) = xz' 11
simplify the Boolean function F(x, y, z) = (2, 3, 4, 5) F(x, y, z) = (2, 3, 4, 5) = x'y + xy' Figure 3.4 Map for Example , F(x, y, z) = (2, 3, 4, 5) = x'y + xy' 12
simplify F(x, y, z) = (3, 4, 6, 7) F(x, y, z) = (3, 4, 6, 7) = yz+ xz' Figure 3.5 Map for Example ; F(x, y, z) = (3, 4, 6, 7) = yz + xz' 13
Consider four adjacent squares 2, 4, and 8 squares m0+m2+m4+m6= x'y'z'+x'yz'+xy'z'+xyz' = x'z'(y'+y) +xz'(y'+y) = x'z' + xz = z' m1+m3+m5+m7= x'y'z+x'yz+xy'z+xyz =x'z(y'+y) + xz(y'+y) =x'z + xz = z Three-variable Map 14
Simplify F(x, y, z) = (0, 2, 4, 5, 6) F (x, y, z) = (0, 2, 4, 5, 6) = z'+ xy' Figure 3.6 Map for Example , F(x, y, z) = (0, 2, 4, 5, 6) = z' +xy' 15
let F = A'C + A'B + AB'C + BC a) Express it in sum of minterms. b) Find the minimal sum of products expression. Ans: F (A, B, C) = (1, 2, 3, 5, 7) = C + A'B Figure 3.7 Map for Example , A'C + A'B + AB'C + BC = C + A'B 16
The map 16 minterms Combinations of 2, 4, 8, and 16 adjacent squares Figure 3.8 Four-variable Map 17
Simplify F (w, x, y, z) = (0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14) F = y'+w'z'+xz' Figure 3.9 Map F(w, x, y, z) = (0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14) = y' + w' z' +xz' 18
simplify F = ABC + BCD + ABCD + ABC Map for Example A B C + B CD + A B C D + AB C = B D + B C +A CD 19
Consider F(A, B, C, D) = (0, 2, 3, 5, 7, 8, 9, 10, 11, 13, 15) The simplified expression may not be unique F = BD+B'D'+CD+AD = BD+B'D'+CD+AB' = BD+B'D'+B'C+AD = BD+B'D'+B'C+AB' 20
Approach #1 Simplified F' in the form of sum of products Apply DeMorgan's theorem F = (F )' F : sum of products F: product of sums Approach #2: duality Combinations of maxterms (it was minterms) M0M1= (A+B+C+D)(A+B+C+D') = (A+B+C)+(DD ) = A+B+C 00 AB CD 01 11 10 M0 M4 M12 M8 M1 M5 M13 M9 M3 M7 M15 M11 M2 M6 M14 M10 00 01 11 10 21
simplify F = (0, 1, 2, 5, 8, 9, 10) into (a) sum-of-products form, and (b) product-of-sums form: F(A, B, C, D)= (0, 1, 2, 5, 8, 9, 10) = B'D'+B'C'+A'C'D a) b) F' = AB+CD+BD' Apply DeMorgan's theorem; F=(A'+B')(C'+D')(B'+D) Or think in terms of maxterms Figure Map for Example F(A, B, C, D)= (0, 1, 2, 5, 8, 9, 10) = B'D'+B'C'+A'C'D 22
Gate implementation of the function of Example F(A, B, C, D)= (0, 1, 2, 5, 8, 9, 10) = B'D'+B'C'+A'C'D Product-of sums form Sum-of products form Figure Gate Implementation of the Function 23
Consider the function defined in Table In sum-of-minterm: ( , , ) F x y z = (1,3,4,6) In sum-of-maxterm ( , , ) F x y z (0,2,5,7) = Taking the complement of F )( = + + ( , , ) F x y z ( ) x z x z 24
Consider the function defined in Table 3.2. Combine the 1 s: xz = + ( , , ) F x y z xz Combine the 0 s : Map for the function of Table 3.2 25
