ISSN 0236-235X (P)
ISSN 2311-2735 (E)

## Next issue

1
Publication date:
16 March 2021

2021
-->

## Data structures and the Quine–McCluskey method modification for minimizing normal forms

Date of submission article: 2020-03-05
UDC: 510.5
The article was published in issue no. № 3, 2020 [ pp. 396-403 ]
Abstract:Logical methods of analysis and synthesis of systems of various nature are usually based on the use of descriptions of their structures and processes in them in the form of Boolean functions, which are equivalently reduced to conjunctive normal forms to unify the representation. For initial systems and processes, as a rule, the main criterion for optimality is the minimum number of components that make up their components, which simplifies the structure, reduces cost and increases reliability, so for model conjunctive normal forms, the problem of minimizing them is of great practical importance. The algorithm’s efficiency that processes complex objects (including conjunctive normal forms) significantly depends on the main and auxiliary data structures used to represent these objects. There-fore, based on the analysis of existing structures, a new complex three-level data structure for repre-senting conjunctive normal forms has been developed. The lower level of the entire combined structure is the data structure for a single clause. Lists of clauses with the same number of letters form the middle level. An array of lists ordered by the lengths of their clauses sets the entire conjunctive normal form at the top level. The using lists, pointers to them and single elements, and the ordering of clauses by lengths make it possible to radically reduce operations for rewriting information and ordering it in the process of con-verting conjunctive normal forms. Based on the developed complex data structure, the authors developed a modification of the well–known Quine-McCluskey method used to reduce perfect normal forms. The combined use of the proposed data structure and the modified method makes it possible to sig-nificantly reduce the total number of operations while minimizing conjunctive normal forms compared to the basic version of the Quine–McCluskey method. This is achieved by reducing data re-processing, and by using special logical conditions, an addi-tional reduction is achieved in the total number of checks of letters in clauses when comparing them.
Аннотация:Логические методы анализа и синтеза систем самой различной природы обычно основаны на использовании описаний их структур и процессов в них в виде булевых функций, которые для унификации представления эквивалентно приводятся к конъюнктивным нормальным формам. Для исходных систем и процессов, как правило, основным критерием оптимальности является минимальное число составляющих их компонент, при котором упрощается структура, уменьшается стоимость и повышается надежность, поэтому для модельных конъюнктивных нормальных форм большое практическое значение имеет задача их минимизации. Эффективность алгоритмов, обрабатывающих сложные объекты (к которым относятся и конъюнктивные нормальные формы), существенно зависит от основных и вспомогательных структур данных, используемых для представления этих объектов, поэтому на основе анализа существующих структур разработана новая комплексная трехуровневая структура данных для представления конъюнктивных нормальных форм. Нижний уровень всей комбинированной структуры представляет собой структура данных для одиночного дизъюнкта. Средний уровень образуют списки дизъюнктов с одним и тем же числом литер. На верхнем уровне вся конъюнктивная нормальная форма задается массивом списков, упорядоченных по длинам входящих в них дизъюнктов. Использование списков, указателей на них и отдельные элементы, упорядоченность дизъюнктов по длинам дают возможность радикально сократить операции по перезаписи информации, ее упорядочению в процессе преобразования конъюнктивных нормальных форм. На основе разработанной комплексной структуры данных разработана модификация известно-го метода Квайна–МакКласки, применяемого для сокращения совершенных нормальных форм. Совместное применение предложенной структуры данных и модифицированного метода позволяет существенно уменьшить общее число операций при минимизации конъюнктивных нормальных форм по сравнению с базовой версией метода Квайна–МакКласки. Оно достигается за счет сокращения повторной обработки данных, а путем использования специальных логических условий достигается дополнительное сокращение общего числа проверок литер в дизъюнктах при их сравнении.
 Authors: Gdansky N.I. (al-kp@mail.ru) - Moscow Polytechnic University (Professor), Moscow, Russia, Ph.D, A.A. Denisov (aadenisov88@gmail.com) - K.G. Razumovsky Moscow State University of Technology and Management (First Cossack University) (Postgraduate Student), Moscow, Russia, Kulikova N.L. (kulikovanl@mpei.ru) - National Research University "Moscow Power Engineering Institute" (Associate Professor), Moscow, Russia, Ph.D Keywords: clause, conjunctive normal form, data structures, quine-mccluskey method Page views: 2478 PDF version article

Font size:       Font:

 Permanent link:http://www.swsys.ru/index.php?page=article&id=4723&lang=&lang=en Print version The article was published in issue no. № 3, 2020 [ pp. 396-403 ]

Back to the list of articles