Summary:
The digital circuit’s output is a binary function in the following form y =
Σ(x, … ), which can be edited with various methods for achieving a simpler
form. The purpose of this process is the circuit’s minimization, and as a
result cheaper solutions and faster circuits.
Karnaugh mapping and Quine – McCluskey method are the basic and simpler
minimization methods. In the first method a table is created whose dimensions
depend from the multitude of the variables. Each cell is a combination of the
variables mentioned before. The final minimized result is formed by creating a
rectangular from neighboring midterms, which corresponds to a final term.
In the Quine – McCluskey method there are two stages: first finding the primary
terms and then using those, with the help of a table, who are traceable from
the first stage and are necessary to define the function.
In many cases, minimization isn’t a simple problem because the multitude of the
input and output variables is often very big. In this situation more advanced
methods are used such the BOOM which uses a combination of finding primary
terms with covering problem solutions. Then, it uses an algorithm with the
following steps: a) Finding the terms from the covering problem who are
necessary for covering the function, b) extending the terms to reach the
primary terms and c) solution of the covering problem.
Keywords:
Circuit Minimization, Digital circuits, Minimization methods, Heuristic algorithms, Prime implicants
