Розроблення та дослідження оптимальних алгоритмів мінімізації булових функцій у довільному логіковому базисі для проектування цифрових комбінаційних пристроїв

Abstract

У дисертації розв’язано актуальне науково-практичне завдання, яке полягає в удосконаленні та розробленні алгоритмів та методів мінімізації булових функцій для проектування цифрових комбінаційних схем радіотехнічних пристроїв та засобів телекомунікацій. Запропоновано числове подання кон'юнктермів довільного рангу у вигляді пари чисел: двійкового зображення та двійкової маски літералів. Двійкове зображення отримуємо шляхом заміни символів поглинання «−» на нулі в псевдотрійковому зображенні. Щоб отримати маску літералів, спочатку замінюємо в трійковому зображенні нулі одиницями, а потім символи поглинання нулями. Оскільки склеювання можливі лише між кон'юнктермами з однаковою маскою літералів, об'єднуємо такі кон'юнктерми у множини. Тепер можна позначати кожен кон'юнктерм лише одним числом, а маску літералів вказати єдину для всієї множини. Це дає змогу використати в алгоритмах мінімізації булових функцій двійкові операції замість операцій над символами. Такий підхід полегшує комп'ютерну реалізацію методів мінімізації. Розвинуто метод розчеплення кон'юнктермів. Запропоновано модифікацію процедури розчеплення кон'юнктермів на основі числового подання, що дозволяє зменшити витрати обчислювальних ресурсів, а використання додатково шістнадцяткової системи числення дає змогу розширити коло завдань, які можна розв’язати без застосування комп’ютера. The dissertation solves an actual scientific and practical task, which is to impreove and to develop algorithms and methods of minimizing Boolean functions for designing digital combinational circuits of radio engineering devices and telecommunications equipment. A numerical representation of conjuncterms of arbitrary rank is proposed in the form of a pair of numbers: a binary image and a binary mask of literals. The binary image is obtained by replacing the absorption symbols “–” with zeros in the pseudoternary image. To obtain a literal mask, we first replace zeros in the ternary image with ones, and then the absorption symbols “–” with zeros. Since gluing is possible only between conjuncterms with the same literal mask, we combine such conjuncterms into sets. Now you can denote each conjunction with only one number, and specify the literal mask with a single number for the entire set. This will allow the use of binary operations in algorithms for minimizing Boolean functions instead of operations on symbols. This approach simplifies the computer implementation of minimization methods. The splitting conjuncterms method has been developed. A modification of the procedure for splitting conjuncterms based on the proposed numerical representation, which makes it possible to reduce the amount of used computing resources, and the additional use of hexadecimal number system allows one to expand the range of problems that can be solved without the use of a computer. The method of bitwise cultivation of primes has been developed. The developed numeric representation was used instead of the pseudo-ternary one, which made it possible to operate with numbers instead of symbols in subsets of conjuncterms with the same literal mask. The concept of a code for marking a set of conjuncterms has been introduced to truncate the ternary tree of growing primes. A procedure has been introduced for detecting a subset, the elements of which are glued together into one conjuncterm by simply counting the number of elements immediately at the stage of sorting by a given bit. The scope of application of the method for not fully defined functions has been expanded. The proposed changes make it possible to expand the range of problems to be solved by reducing computational costs and expanding the scope of the method. The minimax coverage method in the set-theoretic form has been improved. It is proposed to arrange symbolic disjuncterms according to the increase in their powers, that is, starting from the minimum. This speeds up the procedure for simplifying the generated set by shortening the search path for simplifying disjuncterms. The procedure for chain coverage of the table of primes is proposed. This procedure takes into account the relative position of conjuncterms in binary space, which makes it possible to simplify the cyclic part of the table of simple conjuncterms. This leads to a reduction in the amount of used computing resources. To reduce the computational complexity of the problem, you can calculate the complexity coefficient in the vicinity of the chain branch and make a decision about breaking the chain at this place. The chain covering procedure for a set of simple conjuncterms makes it possible to split the covering problem into several computational threads. The proposed approach is heuristic. The method of bitwise sorting of integers for a set of numbers that does not contain tautologies has been improved. In the process of partitioning by a given bit with number n, the elements of the subset are counted, which makes it possible to identify the gluing of the resulting subset into a conjuncterm and replace the sorting procedure by the remaining bits by simply calculating from 0 to 2n-1. In addition, since certain minimization methods require preliminary sorting of a set of initial conjuncterms, the proposed modification makes it possible to obtain part of the The method of minimizing Boolean functions by bitwise partitioning of a set of conjuncterms has been developed. The method makes it possible to find low rank primes without intermediate gluings. For the applied problem, the synthesis of the code converter was performed using the methods proposed in the paper, among which the method of minimizing Boolean functions by bitwise partitioning with gluing showed the best result.