Logic Minimization in FE Electrical Exam

Logic minimization is a crucial concept related to digital circuit design in the FE Electrical exam. It aims to reduce the complexity and optimize the performance of logic circuits. Understanding how to reduce complex equations with logic minimization using algebraic methods and K-Maps is a crucial topic per the NCEES® exam guidelines for the exam.

If you are gearing up for FE exam preparation, this is the topic you cannot afford to miss. Let’s explore this crucial exam topic in depth to learn about logic minimization techniques in the FE Electrical exam.

Understanding Logic Gates

Logic gates are fundamental building blocks of digital circuits that perform Boolean operations on one or more binary inputs to produce a single binary output based on a specific truth table. The basic logic gates include:

  • AND Gate: Outputs true (1) only if all inputs are true.
  • OR Gate: Outputs true (1) if at least one input is true.
  • NOT Gate: Inverts the input; outputs true (1) if the input is false (0), and vice versa.
  • NAND Gate: Combination of AND gate followed by NOT gate.
  • NOR Gate: Combination of OR gate followed by NOT gate.
  • XOR Gate: Outputs true (1) if the number of true inputs is odd.

Need for Minimization of Logical Circuits

Digital circuits can become complex quickly, especially in larger designs. Each additional logic gate introduces propagation delay, increases power consumption, and adds to the circuit’s physical size. Therefore, minimizing the number of logic gates required for a given logic function is essential to:

  • Reduce Cost: Fewer gates mean lower production costs.
  • Improve Performance: Minimized circuits operate faster due to reduced propagation delay.
  • Enhance Reliability: Simplified circuits are less prone to errors and easier to debug.

Logic Minimization Techniques

Logic minimization involves simplifying Boolean expressions or truth tables to achieve an equivalent but simpler logic circuit. Two primary methods are used for logic minimization:

Boolean Algebra

The approach Utilizes algebraic rules to simplify Boolean expressions.

The key rules include:

Commutative:

A+B = B+A

Associative:

(A+B) + C = A + (B+C)

Distributive:

A ⋅ (B+C) = (A⋅B) + (A⋅C)

Addition:

A + A = 1

A + 1 = 1

A + 0 = A

Multiplication:

A . 0 = 0

A . 1 = A

A . A = 0

Karnaugh Maps (K-Maps)

Graphical method to visualize and minimize Boolean functions for up to four variables. K-Maps exploit the adjacency of 1s in truth tables to identify prime implicants and minimize the number of terms in the simplified expression.

SOP and POS in Boolean Algebra

SOP (Sum of Products)

SOP, or Sum of Products, represents a Boolean expression combining multiple terms (products). Each product term consists of ANDed variables or their complements. SOP is useful for expressing a logic function where we list all combinations of inputs that result in an output of 1.

Example of SOP

For a Boolean function F (A, B, C) = A’B’C + AB’C + ABC’, the terms A’B’C, AB’C, and ABC’ are combined.

POS (Product of Sums)

POS, or Product of Sums, represents a Boolean expression where multiple sums (ORed terms) are multiplied. Each sum term consists of ORed variables or their complements. POS is useful for expressing a logic function where we list all combinations of inputs that result in an output of 0.

Example of POS

For a Boolean function F(A, B, C) = (A + B + C’)(A’ + B’ + C)(A’ + B + C), the terms (A + B + C’), (A’ + B’ + C), and (A’ + B + C) are multiplied together.

Simplification of SOP and POS with Boolean Algebra

Step by Step SOP (Sum of Products) Minimization

Consider the Boolean function F(A, B, C) given by the truth table:

ABCF(A,B,C)
0001
0010
0101
0111
1000
1011
1100
1111

Step 01: Identify minterms

Minterms are the terms where the function F(A, B, C) equals 1.

From the truth table: Minterms are 0, 2, 3, 5, 7.

Step 02: Write the SOP expression

Express F(A, B, C) as a sum of products (SOP) of minterms.

F(A,B,C) = Σ(0,2,3,5,7)

Convert minterms to their Boolean expressions:

𝑀(0) = 𝐴′𝐵′𝐶

𝑀(2) = 𝐴′𝐵𝐶

𝑀(3) = 𝐴𝐵′𝐶′

𝑀5 = 𝐴𝐵𝐶′

𝑀7 = 𝐴𝐵𝐶

F(A,B,C) = 𝐴′𝐵’𝐶 + 𝐴’𝐵𝐶 + 𝐴𝐵′𝐶′ + 𝐴𝐵𝐶’ + ABC

Step 03: Simplify using Boolean algebra

Apply Boolean algebraic rules to simplify the expression.

F(A,B,C) = 𝐴′𝐵’𝐶 + 𝐴’𝐵𝐶 + 𝐴𝐵′𝐶′ + 𝐴𝐵𝐶’ + ABC

Using Boolean algebra simplification techniques (associative, distributive, etc.), we can combine terms:

  • Combine 𝐴BC and A′BC to factor BC
  • Combine AB’C’ and ABC’ to factor AC’
  • Isolate A’B’C

F(A,B,C) = [ABC+𝐴’𝐵𝐶] + [𝐴𝐵′𝐶′+𝐴𝐵𝐶’] + 𝐴′𝐵’𝐶

F(A,B,C) = [BC(A+𝐴’)] + [𝐴C'(𝐵′+B)] +𝐴′𝐵’𝐶

F(A,B,C) = [BC(A+𝐴’)] + [𝐴C'(𝐵′+B)] + 𝐴′𝐵’𝐶

By A+A’=1 and B+B’=1

F(A,B,C) = BC+𝐴C’ + 𝐴′𝐵’𝐶

Which is a simplified expression.

Step-by-Step POS (Product of Sums) Minimization

Consider the following truth table and extract its POS equation:

ABCF(A,B,C)
0001
0010
0101
0110
1001
1011
1101
1111

Step 01: Identify max terms

Maxterms are the terms where the function F(A, B, C) equals 0.

From the truth table: Maxterms are 1, 3.

Step 02: Write the POS expression

Express F(A, B, C) as a product of sums (POS) of max terms.

F(A,B,C) = Π(1,3)

Convert max terms to their Boolean expressions:

𝑀1 = (𝐴+𝐵+𝐶′)

𝑀4 = (A’+B+C)

Step 03: Simplify using Boolean algebra

Apply Boolean algebraic rules to simplify the expression.

𝐹(A,B,C) = (𝐴+𝐵+𝐶′)(A’+B+C)

Using distributive law and combining terms:

F(A,B,C) = A(A′+B+C)+B(A′ +B+C)+C′(A′+B+C)

Apply distributive property again:

F(A,B,C)=AA′ + AB + AC + BA′ + BB + BC + C′A′ + C′B + C′C

Simplify using the complement property

𝐴𝐴′ = 0

𝐵𝐵 = 𝐵

and 𝐶𝐶′ = 0

F(A,B,C) = AB + AC + BA′ + B+BC + C′A′ + C′B

Rearrange the terms

F(A,B,C) = AB + BA′ + AC + B + BC + C′B + C′A′

F(A,B,C) = B(A+A′) + AC+B+B(C+C′) + C′A′

Using A+A’ = 1 and C+C’ = 1

F(A,B,C) = B + AC + B + B + C′A′

F(A,B,C) = B + B + B + AC + C′A′

Using B + B + B = B

F(A,B,C) = B + AC + C′A′

Which is a simplified expression.

Verification for Simplified POS or SOP Expressions

To verify the minimization results for SOP and POS:

  • Substitute A, B, and C values from the truth table into the simplified SOP and POS expressions.
  • Ensure that F(A, B, C) evaluates to 1 for the minterms (0, 2, 3, 5, 7) and evaluates to 0 for the maxterms (1, 4).

K-MAP – Everything You Need to Know

Karnaugh Maps (K Maps) are graphical tools that simplify Boolean expressions. They are particularly useful for reducing Boolean functions to their simplest form, especially when dealing with 3 or 4 variables.

Here’s a general step-by-step explanation for using K Maps for Sum of Products (SOP) with 3 and 4 variables:

Step-by-Step Working for Karnaugh Maps (SOP) with 3 Variables

Step 1: Construct the Karnaugh Map

Dimensions: Create a K Map with 2 rows and 4 columns for 3 variables (A, B, C).

Cell Arrangement: Arrange cells so that adjacent cells differ by only one variable (Gray code ordering).

Step 2: Mark Minterms

Identify Minterms: Mark cells corresponding to minterms where the Boolean function equals 1. Each cell corresponds to a unique combination of A, B, and C.

Step 3: Group Adjacent 1s

Grouping: Group adjacent 1s in powers of 2 (1, 2, 4… cells) to cover as many 1s as possible with the fewest groups.

Rules for Grouping: Groups must be rectangular in shape and should ideally cover 1, 2, or 4 cells.

Step 4: Derive Simplified Expression

Read Grouped Terms: Each group represents a product term in the simplified Boolean expression.

Combine Terms: Combine terms within each group using the variables that do not change across the group.

Step 5: Verify and Complete

Verify: Substitute the simplified expression into the K Map to ensure it covers all marked 1s.

Check: Ensure the simplified expression matches the original Boolean function across all input combinations.

For 3 Variables

A/AB00011110
00110
10011

The terms involve:

Group 01: A’B’C+A’BC = A’C(B+B’)=A’C

Group 02: ABC+ABC’=AB(C+C’)=AB

Final Expression: A’C+AB

Step-by-Step Working for Karnaugh Maps (SOP) with 4 Variables

Step 1: Construct the Karnaugh Map

Dimensions: Create a K Map with 4 rows and 8 columns for 4 variables (A, B, C, D).

Cell Arrangement: Arrange cells so that adjacent cells differ by only one variable (Gray code ordering).

Step 2: Mark Minterms

Identify Minterms: Mark cells corresponding to minterms where the Boolean function equals 1. Each cell corresponds to a unique combination of A, B, C, and D.

Step 3: Group Adjacent 1s

Grouping: Group adjacent 1s in powers of 2 (1, 2, 4, 8… cells) to cover as many 1s as possible with the fewest groups.

Rules for Grouping: Groups must be rectangular in shape and should ideally cover 1, 2, 4, or 8 cells.

Step 4: Derive Simplified Expression

Read Grouped Terms: Each group represents a product term in the simplified Boolean expression.

Combine Terms: Combine terms within each group using the variables that do not change across the group.

Step 5: Verify and Complete

Verify: Substitute the simplified expression into the K Map to ensure it covers all marked 1s.

Check: Ensure the simplified expression matches the original Boolean function across all input combinations.

For 4 Variables

AB/CD00011110
000110
010110
110011
100001

Group 01: A’B’C’D + A’B’CD + A’BC’D + A’BCD

D(A’B’C’ + A’B’C + A’BC’ + A’BC)

D(A’B’(C’ + C) + A’B(C’ + C))

D(A’B’ + A’B)

D(A’(B’ + B))

D(A’)

A’D (Which are repeating variables in all 4 cells)

Group 02: ABCD + ABCD’

ABC(D + D’)

ABC(1)

ABC (Which are repeating variables in all 2 cells)

Group 03: AB’CD’ (We cannot deduct any variable as all exist for the single cell).

(There is no need to solve with algebraic simplification; you just have to take the terms of their conjugate that repeats in all cells. For instance, you can directly count A’ and D and combine them in a single term as A’ and D repeats in all 4 cells of tetra selection where 1s occur).

Guidelines for Working with Karnaugh Maps:

  • Cell Ordering: Use Gray code ordering to arrange cells for variables to ensure adjacent cells differ by only one variable.
  • Grouping: Groups should be rectangular and cover 1, 2, 4, or 8 cells (make the biggest selection possible for efficient simplification).
  • Simplification: Combine terms within groups to form the minimized Boolean expression using common variables.
  • Verification: Always verify the simplified expression against the original Boolean function to ensure correctness.

By following these general steps and guidelines, you can effectively use Karnaugh Maps to simplify Boolean expressions with 3 or 4 variables using the Sum of Products (SOP) method.

Conclusion

Logic minimization in the FE Electrical exam is crucial from an exam standpoint. It also greatly helps in digital circuit design optimize performance, reduce complexity, and enhance reliability. Electrical and computer engineers can efficiently minimize logic circuits while maintaining functionality by employing Boolean algebra and Karnaugh maps. This approach ensures digital systems operate effectively with minimal resources.

For more FE-related guides and exam preparation resources, explore Study for FE, your go-to place for exam preparation.

wasim-smal

Licensed Professional Engineer in Texas (PE), Florida (PE) and Ontario (P. Eng) with consulting experience in design, commissioning and plant engineering for clients in Energy, Mining and Infrastructure.