Logical functions in ESOP form minimisation algorithm and program
Students Name: Bielovolov Artem Oleksandrovych
Qualification Level: master (ESP)
Speciality: Telecommunications and Radio Engineering
Institute: Institute of Telecommunications, Radioelectronics and Electronic Engineering
Mode of Study: full
Academic Year: 2019-2020 н.р.
Language of Defence: ukrainian
Abstract: Even today the minimization problem remains relevant and the search for a universal accurate minimization method goes on. A properly done minimizational procedure allows to greatly reduce the number of logical elements and connections between them thus lowering the cost of digital circuit production significantly. As a result, not only the integrated circuit manufacturers benefit, but the end user can get a much cheaper product with the same computational power. This thesis is dedicated to a new method of logical function in ESOP-form (Exclusive Sum of Product) minimization. Most methods found in scientific and technical literature [1-4] on the subject operate with the SOP-form (Sum of Product) despite the ESOP potentially providing better minimization results and being more cost-effective to implement [5-6]. However, ESOP-form minimization is much more complicated and over the last few decades only heuristic methods found a relatively wide application. Furthermore, all of the ESOP-form minimization methods have several common disadvantages: they consider linking only the product terms of identical rank, they are not generalized regarding the Hamming distance between two product terms and they can be used only to logical functions of specific type and with a limited number of variables [7-8]. Therefore, a new minimization method without the aforementioned flaws is suggested. This method is based on three theorems described in [9] and the newly created product term decomposition rule (a generalization of the theorems for arbitrary product term ranks). To minimize the logical function method uses the so called “handshaking” procedure, which represents a mutual movement of two product terms from the initial pair towards each other to reduce the Hamming distance between them. As a result, a set of transformed ESOP product terms of lesser rank than that of the two initial product terms is formed. The transformed product terms can be used to simplify the logical function further. In the thesis various examples are given, demonstrating the method’s effectiveness and its ability to minimize functions that cannot be minimized in SOP-form. To implement the new “handshaking” based minimization method a program was written using the Python 3 programming language. The program operates in a cycle, during one cycle iteration it calculates the starting implementation cost, searches for the product term pair with the specified Hamming distance (first the lowest and to the highest), applies the “handshaking” procedure to the pair, does a basic minimization of the result and compares the implementation cost to the starting one. If there is improvement, the result becomes the input for the next cycle. The minimization is considered done when no cost improvement is found in the process of “handshaking” all the possible product term combinations. To demonstrate the effectiveness of the program, it was used to minimize a number of functions. The experimental results of minimization are provided in this thesis. The program successfully coped with functions which are used in [10] and other sources to illustrate the benefits of different minimization algorithms. Results show that the implementation cost of the minimized functions is identical to the original source or in some cases even better. Also the program minimized the so called “chain” functions which can have only two solutions in SOP-form each containing product terms of one less rank than that of the initial minterms. However, in ESOP-form the program managed to minimize such “chain” functions even further, the more minterms in the input function (or the longer the “chain”), the better is the result. The program proved itself capable of minimizing the benchmark-functions as well. Logical benchmarks are complicated functions with large number of variables used to test the completed minimization algorithms. Benchmark minimization results prove the hypothesis that there is no such concept as a fixed Hamming distance between two product terms for which the decomposition of such product terms is impractical and the function cannot be minimized further. Instead, the implementation cost tends to improve with the growth of the maximal checked Hamming distance and the presence / position of the optimal peak is individual to each function. Also the disadvantages of the program were analyzed and taken into consideration. The main drawbacks are: potentially imperfect look-ahead procedure, low algorithm speed and its novelty thus insufficient development. All in all, the experimental results proved that the “handshaking” based minimization algorithm is suitable for minimization of logical functions and if modified and developed it will become the universal accurate minimization method in ESOP form – a crucial and lacking solution to some minimizational problems in the realm of digital computing. Key words: product term, Exclusive-OR Sum-Of-Product form, ESOP, logical function, minimization method.