SEARCH OF A CUT IN A GRAPH USED IN LOGICAL DESIGN
Abstract
Two optimization problems in logical design are considered: decomposition of Boolean functions and state assignment of a finite automaton. A common approach to those problems is suggested. This approach is connected with the search of a maximal cut in a graph with weighted edges. Heuristic methods based on this approach to solve the problems are suggested.
About the Authors
Yu. V. POTTOSIN
United Institute of Informatics Problems of the National Academy of Sciences of Belarus
Belarus
Belarus
S. A. POTTOSINA
Belarusian State University of Informatics and Radioelectronics
Belarus
Belarus
References
1. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. – М.: Мир, 1978.
2. Поттосин, Ю. В. Табличные методы декомпозиции систем полностью определенных булевых функций / Ю. В. Поттосин, Е. А. Шестаков. – Минск: Белорус. наука, 2006.
3. Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. – М.: Физматлит, 2007.
4. Benini, L. State assignment for low power dissipation / L. Benini, G. de Micheli. // IEEE J. of Solid State Circuits. – 1995. – Vol. 30, no. 3. – P. 32–40.
5. Perkowski, M. A. A Survey of Literature on Functional Decomposition. Version IV (Technical report) / M. A. Perkowski, S. Grygiel. – Portland: Portland State University, Department of Electrical Engineering, 1995.
6. Taghavi Afshord, S. A new suboptimal decomposition algorithm based on the tabular method / S. Taghavi Afshord, Yu. V. Pottosin // Танаевские чтения: докл. Шестой междунар. науч. конф. (27–28 марта 2014 г., Минск). – Минск: ОИПИ НАН Беларуси, 2014. – С. 161–165.
7. Поттосин, Ю. В. Метод минимизации системы полностью определенных булевых функций / Ю. В. Поттосин, Н. Р. Торопов, Е. А. Шестаков // Информатика. – 2008. – № 2 (18). – С. 102–110.
8. Мурога, С. Системное проектирование сверхбольших интегральных схем: в 2 кн. / С. Мурога. – М.: Мир, 1985. – Кн. 1.
9. Pedram, M. Power minimization in IC design: Principles and applications / M. Pedram // ACM Trans. Design Automat. Electron. Syst. – 1996. – Vol. 1. – P. 3–56.
10. Macii, E. High-level power modeling, estimation and optimization / E. Macii, M. Pedram, F. Somenzi // IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems. – 1998. – Vol. 17, no. 11. – P. 1061–1079.
11. Закревский, А. Д. Алгоритмы энергосберегающего кодирования состояний автомата / А. Д. Закревский. – Информатика. – 2011. – № 1 (29). – С. 68–78.
12. Закревский, А. Д. Раскраска графов при декомпозиции булевых функций / А. Д. Закревский // Логич. проектирование. – Минск: ИТК НАН Беларуси, 2000. – Вып. 5. – С. 83–97.
Review
Views: 690
Email this article 