Parallel decomposition by reducing the value of the basic coefficient K as an alternative method minimization of Boolean functions
DOI:
https://doi.org/10.31498/2225-6733.30.2015.52801Keywords:
basic factor K, parallel decomposition of Boolean functions, the base part Φi, the informing part Qi, Boolean functionsAbstract
Steady improvement of microelectronics necessitates deeper understanding of existing methods for discrete structures synthesis, as well as development of new ones. Сombinational circuits of digital blocks are an important class of discrete structures, and Boolean functions are the mathematical models of their functioning. The purpose of this paper is to describe an alternative method of Boolean functions with a large number of arguments minimization. The method is implemented basing on the decomposition of Boolean functions through reducing the value of the basic factor K. Shannon’s decomposition of Boolean functions means Boolean functions decomposition into two summands with respect to some i-argument. The ratio between the number of arguments in informing and in the basic parts of each series member is determined by coefficient K. K is the number of arguments, which is part of the series member basis. The value of K is the criterion of minimizing of the logic equations of Boolean functions y=f(x1,x2,x3,…,xn). The basic factor K is optimal if its informing part value is equal to Qi=1 or Qi=0. Decomposition of Boolean functions does not always result in the minimal form of Boolean functions. It provides a consistent decomposition of Boolean functions, and arguments are essentially equal. Therefore a method of parallel decomposition is proposed in this article. This method is based on decomposition of Boolean functions by simultaneous changes in all the arguments of the basic factor K. Parallel decomposition process consists of two stages. In the first stage, the full list of all the basic parts -Φi with the optimal value of the basic factor K are determined. In the second stage on the basis of Φi complete list of answers is formed. The paper provides a detailed description of the parallel decomposition algorithm for the minimization. Parallelization of the minimization process accelerates the whole process. The software for the minimization of Boolean functions with a large number of arguments on the basis of the described algorithm has been developed. Parallelization process, which is offered for the longest stages of the minimization process makes it possible to obtain minimal forms of Boolean functions by utilizing multiprocessor systems in a relatively short period of time. This has a positive effect on the speed of the digital blocks logical designReferences
Бибило П.Н. Синтез комбинационных схем методами функциональной декомпозиции / П.Н. Бибило, С.В. Енин ; ред. А.Д. Закревский ; АН БССР. Ин-т техн. кибернетики. – Мн. : Наука и техника, 1987. – 189 c.
Панаско О.М. Пошук однакових фрагментів при мінімізації логічних функцій в ортогональній реалізації / О.М. Панаско // Радіоелектронні і комп’ютерні системи. − 2014. − № 1. − С. 92-97.
Кочкарев Ю.А. Минимизация булевых функций по частям / Ю.А. Кочкарев, С.В. Бурмистров, С.Ф. Аксенов // Радіоелектронні і комп’ютерні системи. − 2012. − № 4. − С. 110-115.
Кочкарев Ю.А. Минимизация частично определенных булевых функций в ортогональ-ной форме представления / Ю.А. Кочкарев, С.В. Бурмистров, С.Ф. Аксенов // Прикладная радиоэлектроника. – 2013. – Т. 12, № 3. – С. 423-430.
Кочкарев Ю.А. Минимизация систем полностью определенных булевых функций в ортогональной форме представления / Ю.А. Кочкарев, В.Н.Рудницкий, С.В.Бурмистров // Эвристические алгоритмы и распределенные вычисления в прикладных задачах. (Выпуск 2). Коллективная монография под редакцией профессора Мельникова. – Ульяновск. – 2013. – С. 87-100.
Рудницкий В.Н. Распараллеливание процесса минимизации систем частично или полностью определенных булевых функций с большим числом переменных / В.Н. Рудницкий, С.В. Бурмистров // Вектор науки Тольяттинского государственного университета. – 2014. − № 1. − С. 27-30.
Бурмістров С.В. Паралельна декомпозиція як основний метод мінімізації булевих функцій в ортогональній формі представлення / С.В. Бурмістров // Вісник Черкаського державного технологічного університету. – 2014. – № 2. – С. 67-73.
Downloads
How to Cite
Issue
Section
License
The journal «Reporter of the Priazovskyi State Technical University. Section: Technical sciences» is published under the CC BY license (Attribution License).
This license allows for the distribution, editing, modification, and use of the work as a basis for derivative works, even for commercial purposes, provided that proper attribution is given. It is the most flexible of all available licenses and is recommended for maximum dissemination and use of non-restricted materials.
Authors who publish in this journal agree to the following terms:
1. Authors retain the copyright of their work and grant the journal the right of first publication under the terms of the Creative Commons Attribution License (CC BY). This license allows others to freely distribute the published work, provided that proper attribution is given to the original authors and the first publication of the work in this journal is acknowledged.
2. Authors are allowed to enter into separate, additional agreements for non-exclusive distribution of the work in the same form as published in this journal (e.g., depositing it in an institutional repository or including it in a monograph), provided that a reference to the first publication in this journal is maintained.
