Up to this point, we have explored the concept of numbers and the process of converting between different bases. We then examined logic gates, learning how to transform logic diagrams into Boolean expressions and vice versa. This was followed by studying the truth table representation of functions using minterms and maxterms, and the methods for converting them to and from other forms. We also discussed schematic equivalence using only NAND and NOR gates.
How to Simplify a Logical Function?
In this section, we will focus on simplifying a given function using Boolean algebra and the Karnaugh map method. These techniques are valuable for reducing the number of gates and/or literals per gate, resulting in an updated schematic that generally occupies less area and can potentially offer higher speed performance.
What are the Metrics for Simplification?
Although Boolean Algebra and Karnaugh Maps are effective tools for simplifying logic functions, it’s not always obvious whether the resulting expression is truly minimal. To objectively compare different versions of a function, we use a standard metric known as Cost. This metric helps evaluate whether the transformation has led to a simpler, more efficient form.
Cost
Cost quantifies the resources consumed by a circuit implementation, primarily reflecting its physical area, component count, or design complexity.
However, this definition must be qualified with key limitations, as cost is never universal and depends on:
- Implementation Technology:
- ASIC/CMOS: Cost ≈ transistor count (e.g., NAND: 4 transistors, NOR: 4, inverter: 2).
- FPGA: Cost ≈ number of LUTs/CLBs (Look-Up Tables/Configurable Logic Blocks), not gates.
- Discrete Gates: Cost ≈ total gate inputs (e.g., 2-input AND = 2 units, inverter = 1 unit).
- Design Goals:
- Area minimization: Cost correlates with silicon area (transistors/gate inputs).
- Speed optimization: Cost may incorporate path delays (e.g., higher fan-in gates increase delay).
- Power constraints: Cost may include switching activity (rare in basic models).
- Level of Abstraction:
- Boolean algebra: Cost = literal count (e.g., \(\mathsf{F=AB+\overline{C}D\rightarrow{}4}\) literals).
- Logic gates: Cost = gate input count (dominant industry practice).
- Academic simplification: Cost = unit gate count (1 per gate, ignoring type/inputs).
To maintain academic simplicity, we define the cost function—unless stated otherwise—as follows: all primary input literals, whether complemented or uncomplemented, contribute zero cost. Each logic gate adds a cost of 1, and every input connected to that gate contributes an additional 1. This definition ensures that the total cost accurately reflects both the number of gates used and the total number of input connections in the implementation.
Example: Calculate the cost of \(\mathsf{Z=A\overline{B}}\)
\[
\begin{aligned}
\textsf{Number of gates }&\mathsf{=1}\textsf{ (AND)}\\
\textsf{Number of inputs to the gates }&\mathsf{=2}\\
\textsf{Total cost }&\mathsf{=1+2=3}
\end{aligned}
\]
Example: Calculate the cost of \(\mathsf{Z=\overline{A+\overline{B}}}\)
\[
\begin{aligned}
\textsf{Number of gates }&\mathsf{=2}\textsf{ (OR, NOT)}\\
\textsf{Number of inputs to the gates }&\mathsf{=3}\textsf{ (OR, 2) and (NOT, 1)}\\
\textsf{Total cost }&\mathsf{=2+3=5}
\end{aligned}
\]
Example: Calculate the cost of \(\mathsf{Z=\left(A\overline{B}+C\right)+\left(\left(\overline{A}+C\overline{D}\right)B\right)}\)
\[
\begin{aligned}
\textsf{Number of gates }&\mathsf{=6}\textsf{ (3 AND, 3 OR)}\\
\textsf{Number of inputs to the gates }&\mathsf{=12}\textsf{ (AND, 2 for each) and (OR, 2 for each)}\\
\textsf{Total cost }&\mathsf{=6+12=18}
\end{aligned}
\]