Record Details

MINIMIZING THE MULTILEVEL REPRESENTATIONS OF SYSTEMS OF BOOLEAN FUNCTIONS BASED ON SHANNON DECOMPOSITION

Informatics

View Archive Info
 
 
Field Value
 
Title MINIMIZING THE MULTILEVEL REPRESENTATIONS OF SYSTEMS OF BOOLEAN FUNCTIONS BASED ON SHANNON DECOMPOSITION
МИНИМИЗАЦИЯ МНОГОУРОВНЕВЫХ ПРЕДСТАВЛЕНИЙ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ НА ОСНОВЕ РАЗЛОЖЕНИЯ ШЕННОНА
 
Creator P. Bibilo N.
Y. Lankevich Y.
П. Бибило Н.; Объединенный институт проблем информатики НАН Беларуси
Ю. Ланкевич Ю.; Объединенный институт проблем информатики НАН Беларуси
 
Subject —
—
 
Description A locally optimal algorithm is proposed to form a permutation of variables, which are used to obtain successive Shannon decompositions of a system of disjunctive normal forms of completely specified Boolean functions. The goal of it is a multilevel representation of functions which is called a reduced ordered Binary Decision Diagram. The results of experimental comparison of the program implementing the proposed algorithm and the program implementing the algorithm for enumeration of random permutations are given. The results show the advantage of the proposed algorithm when it is used for synthesis of logical circuits on the basis of library elements.
Предлагается приближенный алгоритм формирования перестановки переменных, по каждой из которых последовательно строятся разложения Шеннона системы дизъюнктивных нормальных форм полностью определенных булевых функций с целью получения многоуровневого представления функций, называемого в литературе сокращенной упорядоченной диаграммой двоичного выбора либо диаграммой двоичных решений. Приводятся результаты экспериментального сравнения программы, реализующей предложенный алгоритм, с программой, реализующей алгоритм перебора случайных перестановок.
 
Publisher UIIP NASB
 
Contributor —
—
 
Date 2017-06-15
 
Type info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
—
—
 
Format application/pdf
 
Identifier http://inf.grid.by/jour/article/view/211
 
Source Informatics; № 2(54) (2017); 45-57
Информатика; № 2(54) (2017); 45-57
1816-0301
 
Language rus
 
Relation http://inf.grid.by/jour/article/view/211/213
Шеннон, К. Синтез двухполюсных переключательных схем / К. Шеннон // Работы по теории информации и кибернетике. – М. : ИЛ, 1963. – С. 59–105.
Бибило, П.Н. Применение диаграмм двоичного выбора при синтезе логических схем / П.Н. Бибило. – Минск : Беларус. навука, 2014. – 231 с.
Akers, S.B. Binary Decision Diagrams / S.B. Akers // IEEE Trans. on Computers. – 1978. – Vol. C–27, no. 6. – P. 509–516.
Bryant, R.E. Graph-based algorithms for Boolean function manipulation / R.E. Bryant //IEEE Transactions on Computers. – 1986. – Vol. 35, no. 8. – P. 677–691.
Bryant, R.E. Ordered Binary Decision Diagrams / R.E. Bryant, C. Meinel // Logic synthesis and verification. – Boston, Dordrecht, London : Kluwer Academic Publishers, 2002. – P. 285–307.
Meinel, C. Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications / C. Meinel, T. Theobald. – Berlin, Heidelberg : Springer-Verlag, 1998. – 267 p.
Кнут, Д.Э. Искусство программирования / Д.Э. Кнут. – М. : Вильямс, 2013. – Т. 4, А : Комбинаторные алгоритмы, ч. 1. – 960 с.
Валидация на системном уровне. Высокоуровневое моделирование и управление тестированием / М. Чэнь [и др.]. – М. : Техносфера, 2014. – 296 с.
Карпов, Ю.Г. MODEL CHECKING. Верификация параллельных и распределенных программных систем / Ю.Г. Карпов. – СПб. : БХВ-Петербург, 2010. – 560 с.
Бибило, П.Н. Cистемы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum / П.Н. Бибило. – М. : СОЛОН-Пресс, 2005. – 384 с.
Бибило, П.Н. Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций / П.Н. Бибило, П.В. Леончик // Управляющие системыи машины. – 2009. – № 6. – С. 42–49.
Закревский, А.Д. Логические основы проектирования дискретных устройств / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – М. : Физматлит, 2007. – 589 c.
Закревский, А.Д. Вычисления в многомерном булевом пространстве / А.Д. Закревский. – Минск : ОИПИ НАН Беларуси, 2011. – 106 с.
Ishiura, N. Minimization of binary decision diagrams based on exchange of variables /N. Ishiura, H. Sawada, S. Yajima // Computer-Aided Design : proc. 29th IEEE Intern. conf., Santa Clara, 11–14 Nov. 1991 / IEEE Computer Society. – Washington, 1991. – P. 472–475.
Jeong, S.-W. An efficient method for optimal BDD ordering computation / S.-W. Jeong, T.-S. Kim, F. Somenzi // VLSI and CAD : proc. of Intern. conf. – Taejon, 1993. – P. 252–256.
Friedman, S.J. Finding the optimal variable ordering for binary decision diagrams /S.J. Friedman, K.J. Supowit // IEEE Trans. Computers. – 1990. – Vol. 39, no. 5. – P. 710–713.
Fujii, H. Interleaving based variable ordering methods for ordered binary decision diagrams / H. Fujii, G. Ootomo, C. Hori // Computer-aided design : proc. of the 1993 IEEE/ACM Intern. conf., Santa Clara, 7–11 Nov. 1993 / IEEE Computer Society Press. – Los Alamitos, 1993. – P. 38–41.
Dynamic variable reordering for BDD minimization / E. Felt [et al.] // Design Automation : proc. EURO-DAC, Hamburg, 20–24 Sep. 1993 / IEEE Computer Society Press. – Los Alamitos, 1993. – P. 130–135.
Jeong, C. Computer-Aided Design of Digital Systems / C. Jeong // Department of Computer Science [Electronic resource]. – Mode of access : http://www1.cs.columbia.edu/~cs6861/sis/espressoexamples/ex. – Date of access : 20.03.2017.
Бибило, П.Н. Логическое проектирование дискретных устройств с использованием продукционно-фреймовой модели представления знаний / П.Н. Бибило, В.И. Романов. – Минск :Беларус. навука, 2011. – 279 с.
Поляков, А.К. Языки VHDL и VERILOG в проектировании цифровой аппаратуры /А.К. Поляков. – М. : СОЛОН-Пресс, 2003. – 320 с.
Лохов, А. Функциональная верификация СБИС в свете решений Mentor Graphics /А. Лохов // Электроника: наука, технология, бизнес. – 2004. – № 1. – С. 58–62.
 
Rights Authors who publish with this journal agree to the following terms:Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Авторы, публикующие в данном журнале, соглашаются со следующим:Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.Авторы сохраняют право заключать отдельные контрактные договорённости, касающиеся не-эксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге), со ссылкой на ее оригинальную публикацию в этом журнале.Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).