ПОИСК РАЗРЕЗА ГРАФА В РЕШЕНИИ НЕКОТОРЫХ ЗАДАЧ ЛОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ
Аннотация
Рассматриваются две задачи логического проектирования дискретных устройств: декомпозиция булевых функций и кодирование состояний конечного автомата. Предлагается общий подход к решению этих задач, который связан с поиском максимального разреза в графе со взвешенными ребрами. На основе указанного метода предложены эвристические методы решения рассматриваемых задач.
Об авторах
Ю. В. ПОТТОСИН
Объединенный институт проблем информатики Национальной академии наук Беларуси
Беларусь
Беларусь
С. А. ПОТТОСИНА
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
Беларусь
Список литературы
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.
Рецензия
Просмотров: 689
Послать статью по эл. почте 