Introduction
- The logic circuit is a combination of logic gates together as an integrated circuit to perform some incredibly complex calculations.
Definition
- A logic circuit is a type of electronic circuit that consists of one or more logic gates in a certain specific sequence, used/found in electronic devices to perform certain defined logical operations on its two or more input signals.
Features
- A logic circuit has one or more Boolean inputs and only one output.
Types of Logic Circuits
- There are two basic types of logic circuitry: (A) Combinational circuit and (B) Sequential/State circuit.
Minimization of Logic Circuits (Logic Gates)
- Minimization of logic circuits refers to the process of simplifying a digital logic circuit so that it uses the fewest possible gates or components while still performing the same logical function.
- The goal is to reduce the cost, size, and power consumption of the circuit, and to improve its speed and reliability.
- Why minimize the Logic circuits?
- To reduce hardware cost (fewer gates, ICs, or transistors)
- To save space on chips or circuit boards, i.e., smaller size.
- To lower power consumption
- To increase circuit processing speed and reliability
- Finally, to simplify and make an efficient logic circuit
- How is the minimization of a logic circuit done?
- The minimization of a Logic circuit is done by simplifying Boolean expressions that describe the circuit through the following ways:-
- Using Algebraic Simplification Methods (following Boolean algebra rules)
- Using Graphical Methods (Karnaugh Maps or K-Maps)
- Using Computer Algorithms (Quine-McCluskey method, software tools)
- The minimization of a Logic circuit is done by simplifying Boolean expressions that describe the circuit through the following ways:-
-
Algebraic Simplification Methods
-
Algebraic simplification is a method of minimizing Boolean expressions, hence logic circuits, using the rules and laws of Boolean algebra.
- Algebraic simplification uses Boolean algebra laws to reduce logic expressions, making digital circuits simpler, cheaper, and more efficient.
- The goal of this method is to reduce the number of terms and literals in a logic expression, which leads to simpler and more efficient digital circuits.
- Boolean Algebra Rules and Laws
-
-
-
- Identity Law (Used to remove redundant terms)
-
A + 0 = A
A · 1 = A
-
-
- Null Law (Used to eliminate terms)
-
A + 1 = 1
A · 0 = 0
-
-
- Idempotent Law (Used to remove duplicates)
-
A + A = A
A · A = A
-
-
- Inverse Law (Used to simplify complements)
-
A + A’ = 1
A · A’ = 0
-
-
- Commutative Law
-
A + B = B + A
A · B = B · A
-
-
- Associative Law
-
(A + B) + C = A + (B + C)
(A · B) · C = A · (B · C)
-
-
- Distributive Law (Used to expand or factor expressions)
-
A · (B + C) = (A · B) + (A · C)
A + (B · C) = (A + B) · (A + C)
-
-
- Absorption Law (Used to remove unnecessary terms)
-
A + (A · B) = A
A · (A + B) = A
-
-
- DeMorgan’s Theorems (Used to simplify complements)
-
(A · B)’ = A’ + B’
(A + B)’ = A’ · B’
-
- Working Mechanism of the Algebraic Simplification Method
Step1 : Write the Boolean expression of the given problem.
Step2 : Now we apply Boolean algebra rules and laws to the given problem expressions,
using combine, eliminate, or reduce terms.
Step3 : Repeat the process, combine, eliminate, or reduce terms until no further
Simplification is possible.
Step4 : Verify the simplified expression (optional, using truth tables or K-Map).
-
- For Example
Given problem :
F = A·B + A·B’
On using the Simplification method for the above problem:
By applying Distributive Law first:
F = A·(B + B’)
Now applying the Inverse Law:
F = A·1
Now apply Identity Law:
F = A
Finally, the Result is: The minimized equivalent expression/logic circuit is F = A, which is the minimized form of F = A·B + A·B’.
-
- Advantages of the Algebraic Simplification Method
- No need for graphical tools (like K-Map).
- Useful for small expressions/logic circuits or when only a few variables are involved.
- Helps in understanding the logic behind circuit minimization.
- Limitations
- Becomes complex and error-prone for expressions with many variables.
- Not systematic for large circuits (K-Map or computer algorithms are preferred).
- Advantages of the Algebraic Simplification Method
-
Karnaugh Maps or K-Maps
-
- A Karnaugh Map (K-Map) is a graphical tool used to simplify Boolean algebra expressions and minimize logic circuits.
- It helps in reducing complex logic functions into simpler forms, making circuit design more efficient and functional.
- Key Features
- Visual Representation: A K-Map is a grid-like diagram where each cell represents a possible combination of input variables.
- Grouping: Adjacent cells with value 1 (for SOP) or 0 (for POS) are grouped to simplify expressions.
- Reduces Human Error: Easier and less error-prone than algebraic simplification, especially for up to 4 or 5 variables.
- Conventions and Rules to Create a K-Map
K-Map conventions and rules ensure systematic simplification of Boolean expressions by grouping adjacent cells in powers of two, using Gray code arrangement, and covering all required 1s or 0s with the fewest groups.
The conventions and rules to create and use a Karnaugh Map (K-Map) are as follows:-
-
-
- The number of cells created for a grid/matrix in a K-Map is 2ⁿ, where n is the number of variables used.
- for 2 variables → 2ⁿ → 4 cells grid/matrix
- for 3 variables → 2ⁿ → 8 cells grid/matrix
- for 4 variables → 2ⁿ → 16 cells grid/matrix
- Cells are arranged so that adjacent cells differ by only one variable at a time (Gray code rule/order). This allows easy grouping of adjacent 1s (for SOP) or 0s (for POS).
- Each cell represents a minterm (for SOP) or maxterm (for POS).
- The K-Map is filled with 1s for minterms where the function is 1 (SOP), or 0s for maxterms where the function is 0 (POS).
- Now we group adjacent/edges of K-Map cells[vertical or horizontal, never diagonal] 1s (for SOP) or adjacent 0s (for POS) in rectangles in the order of … 64, 32,16, 8, 4, 2, 1, i.e., (powers of 2) cells.
-
Writing the Simplified Expression :
- For SOP (Sum of Products) Form:
- Each group gives a product (AND) term.
- The variable is included in the term if it is the same for all cells in the group; if it changes, it is omitted.
- For POS (Product of Sums):
- Each group gives a sum (OR) term.
- The variable is included in the term if it is the same for all cells in the group; if it changes, it is omitted (but in complemented form).
- For SOP (Sum of Products) Form:
-
Don’t Care Conditions:
- If the function has/applies “don’t care” conditions (X), they can be used as either 1 or 0 to help make larger groups and further simplify the expression.
-
No Overlapping or Repeating or Missing Groups:
-
We try to cover all 1s (for SOP) or all 0s (for POS) with the fewest and largest possible groups.
-
Do not leave any required 1 or 0 uncovered.
-
- The number of cells created for a grid/matrix in a K-Map is 2ⁿ, where n is the number of variables used.
-
-
- Structure
- 2-variable K-Map: 2×2 grid (4 cells)
- 3-variable K-Map: 2×4 grid (8 cells)
- 4-variable K-Map: 4×4 grid (16 cells)
- Each cell corresponds to a minterm (for SOP) or maxterm (for POS).
- How to Use/Create a K-Map
- Draw the K-Map: Create a grid-based matrix for the number of variables used in the logic circuit.
- Fill the K-Map: Enter 1s (for SOP method of K-Map) or 0s (for POS method of K-Map) in grid or matrix cells corresponding to the function’s truth table.
- Group Adjacent 1s/0s: Form groups of 1, 2, 4, 8, etc. (must be powers of 2). Groups can wrap around edges.
- Write Simplified Expression: Now, each group represents a simplified product (for SOP) or sum (for POS) term.
- Example:
- Structure
(i) A 3-Variable K-Map is represented in SOP form as –
Suppose the function is:
F(A, B, C) = Σ(1, 3, 5, 7)
(Here, Σ denotes the sum of minterms, i.e., SOP form)
(ii) A 3-Variable K-Map is represented in POS form as –
Suppose the function is:
F(A, B, C) = Π(1, 4, 6,7)
(Here, Π denotes the product of maxterms, i.e., POS form)
-
- Advantages of K-Map
- Simple and effective for up to 4 or 5 variables.
- Reduces Boolean expressions quickly.
- Helps in designing efficient digital circuits.
- Limitations
- Becomes complex for more than 5 variables.
- Not suitable for computer automation (for large functions, use Quine-McCluskey or software tools).
- Advantages of K-Map
-
Quine-McCluskey method/Tabulation method
-
- The Quine-McCluskey method (also called the tabulation method) is a systematic, algorithmic approach for minimizing Boolean functions.
- The Quine-McCluskey method is a tabular, algorithmic approach to minimizing Boolean functions, especially useful for functions with many variables, and is the basis for many logic minimization software tools.
- It is especially useful for functions with more than four variables, where Karnaugh Maps become difficult to use.
- Key Features
- Systematic and suitable for computer implementation
- Works for any number of variables
- Steps in the Quine-McCluskey Method:
- List All Minterms
- Write the Boolean function in terms of minterms (Σ notation).
- Convert each minterm to its binary equivalent.
- Group Minterms by Number of 1s
- Arrange minterms in groups based on the number of 1s in their binary representation.
- Pair and Combine Minterms
- Compare minterms in adjacent groups.
- If two minterms differ by only one bit, combine them by replacing the differing bit with a dash (–).
- Mark combined minterms.
- Repeat Pairing
- Repeat the process with the new groups until no further combinations are possible.
- The unpaired terms are prime implicants.
- Prime Implicant Chart
- Create a chart with all prime implicants and the original minterms.
- Mark which prime implicants cover which minterms.
- Select Essential Prime Implicants
- An essential prime implicant is the only one that covers a particular minterm.
- Select all essential prime implicants.
- If any minterms are still uncovered, select additional prime implicants to cover them (using Petrick’s method if needed).
- List All Minterms
- For Example
Suppose:
F(A, B, C, D) = Σ(0, 1, 2, 5, 6, 7, 8, 9, 10, 14)
Step 1: List minterms in binary.
Minterm – Binary Value
0 0000
1 0001
2 0010
5 0101
6 0110
7 0111
8 1000
9 1001
10 1010
14 1110
Step 2: Group by number of 1s.
0 ones: 0000 (0)
1 one: 0001 (1), 0010 (2), 1000 (8)
2 ones: 0101 (5), 0110 (6), 1001 (9), 1010 (10)
3 ones: 0111 (7), 1110 (14)
Step 3: Combine adjacent groups (and so on…)
Step 4: Continue until no further combinations.
Step 5: List all prime implicants.
Step 6: Use the prime implicant chart to select essential ones and cover all minterms.
Advantages
- Systematic and accurate for any number of variables.
- Suitable for computer implementation (used in logic synthesis software).
Disadvantages
- Tedious and time-consuming by hand for more than 5-6 variables.
- It can become complex for very large functions.
0 Comments