INVESTIGATION OF DECOMPOSABILITY OF A SYSTEM OF BOOLEAN FUNCTIONS
Abstract
A computer program is described which analyzes the decomposability of a system of Boolean functions and searches for an appropriate partition of the argument set. Three tasks linked with a system of Boolean functions are given: producing all solutions, searching for the best solution from the circuit complexity point of view, and finding a solution as quickly as possible, if the system is decomposable. The results of computer experiment for determining decomposability of systems of Boolean functions are given.
About the Authors
S. H. Taghavi Afshord
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
Yu. V. Pottosin
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
References
1. Hassoun, S. Logic Synthesis and Verification. The Springer International Series in Engineering and Computer Science / S. Hassoun, T. Sasao. – Kluwer Academic Publishers, 2001. – 472 p.
2. Perkowski, M.A. A Survey of Literature on Functional Decomposition, Version IV /M.A. Perkowski, S. Grygiel ; Portland State University, Department of Electrical Engineering. – Portland, USA, 1995. – 188 p.
3. Muthukumar, V. An efficient variable partitioning approach for functional decomposition of circuits / V. Muthukumar, R.J. Bignall, H. Selvaraj // Journal of Systems Architecture. – 2007. – Vol. 53, no. 1. – P. 53–67.
4. An improved functional decomposition method based on FAST and the method of removal and operation / F. Yu [et al.] // International Conference on System Science and Engineering (ICSSE), Dalian, China, Jun. 2012. – Dalian, 2012. – P. 487–492.
5. Закревский, А.Д. Логические основы проектирования дискретных устройств /А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.
6. Бибило, П.Н. Декомпозиция булевых функций на основе решения логических уравнений / П.Н. Бибило. – Минск : Беларус. навука, 2009. – 211 с.
7. Jóźwiak, L. An effective and efficient method for functional decomposition of boolean functions based on information relationship measures / L. Jóźwiak, A. Chojnacki // 3rd Design and Diagnostics of Electronic Circuits and Systems Workshop (DDECS), Bratislava, Slovakia, Apr. 2000. – Bratislava, 2000. – P. 242–249.
8. Закревский, А.Д. Декомпозиция частичных булевых функций – проверка на разделимость по заданному разбиению / А.Д. Закревский // Информатика. – № 1(13). – 2007. – С. 16–21.
9. Files, C.M. New mutivalued functional decomposition algorithms based on MDDs /C.M. Files, M.A. Perkowski // IEEE Transactions on Computer-Aided Design of Integrated Ciruits and Systems. – 2000. – Vol. 19, no. 9. – P. 1081–1086.
10. Rawski, M. Input variable partitioning method for decomposition-based logic synthesis targeted heterogeneous FPGAs / M. Rawski // International Journal of Electronics and Telecommunications. – 2012. – Vol. 58, no. 1. – P. 15–20.
11. Поттосин, Ю.В. Табличные методы декомпозиции систем полностью определе нных булевых функций / Ю.В. Поттосин, Е.А. Шестаков. – Минск : Белорус. наука, 2006. –327 с.
12. Поттосин, Ю.В. Применение аппарата покрытий троичных матриц для поиска разбиения множества аргументов при декомпозиции булевых функций / Ю.В. Поттосин, Е.А. Шестаков // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. – 2011. – № 3 (16). – С. 100–107.
13. Романов, В.И. Разработка инструментальных средств логического проектирования /В.И. Романов // Логическое проектирование. Вып. 6. – Минск : Ин-т техн. кибернетики НАН Беларуси, 2001. – С. 151–170.
14. Romanov, V.I. Tools for programming Boolean calculations / V.I. Romanov // Abstracts of ECCO XVIII Conf. «Combinatorics for Modern Manufacturing, Logistics and Supply Chains», Minsk, Belarus. – Minsk, 2005. – P. 57–58.
15. Кнут, Д.Э. Искусство программирования. Т. 4, А. Комбинаторные алгоритмы. Ч. 1 /Д.Э. Кнут. – М. : Вильямс, 2013. – 960 с.
Review
For citations:
Taghavi Afshord S.H., Pottosin Yu.V. INVESTIGATION OF DECOMPOSABILITY OF A SYSTEM OF BOOLEAN FUNCTIONS. Informatics. 2013;(4):94-103. (In Russ.)
Views: 776
Email this article 