6 research outputs found
The Use of Zhegalkin Polynomials for Minimization of Multilevel Representations of Boolean Functions Based on Shannon Expansion
No full textLogical optimization of Boolean nets using Shannon expansion
Get PDFA synthesis of logical circuits, comprising functional combination blocks of very large scale integration circuits, is one of the most important tasks of computer-aided design. As the data size of design tasks increases, the execution time of synthesis of logic circuits also increases. The global technological independent optimization as the first stage of synthesis of logical circuit is especially labor-consuming. The second stage is technological mapping of optimized logical representations of functions to the logical elements of technological library. The main features of logical circuit, such as area, performance, power consumption, depend on the efficiency of the first stage – global logical optimization. The evolution of methods of global logical optimization has revealed the efficiency of Shannon expansion in case of optimization of multi-level representations of the systems of fully defined Boolean function. A number of methods and programs were developed using graphical representations of Shannon expansions – BDD representations. Most of the developed methods of optimization of BDD-representations use the initial representations of functions systems in the form of disjunctive normal form (DNF).In the article an algorithm of minimization of nodes number of Boolean net, which is a multi-level representation of the system of fully defined Boolean function, is proposed. Minimization is based on Shannon expansion and a search of equal (with accuracy up to inversion) nodes in Boolean net. Such algorithm of logical optimization was implemented as application. The experiments have shown that this algorithm and the application is reasonable to use in cases when the initial multi-level representation of functions is impossible to define as DNF system, or when DNF system contains a large number of elementary conjunctions
Logical minimization for combinatorial structure in FPGA
Get PDFThe paper describes the research results of application efficiency of minimization programs of functional descriptions of combinatorial logic blocks, which are included in digital devices projects that are implemented in FPGA. Programs are designed for shared and separated function minimization in a disjunctive normal form (DNF) class and minimization of multilevel representations of fully defined Boolean functions based on Shannon expansion with finding equal and inverse cofactors. The graphical form of such representations is widely known as binary decision diagrams (BDD). For technological mapping the program of "enlargement" of obtained Shannon expansion formulas was applied in a way that each of them depends on a limited number of k input variables and can be implemented on one LUT-k – a programmable unit of FPGA with k input variables. It is shown that a preliminary logic minimization, which is performed on the domestic programs, allows improving design results of foreign CAD systems such as Leonardo Spectrum (Mentor Graphics), ISE (Integrated System Environment) Design Suite and Vivado (Xilinx). The experiments were performed for FPGA families’ Virtex-II PRO, Virtex-5 and Artix-7 (Xilinx) on standard threads of industrial examples, which define both DNF systems of Boolean functions and systems represented as interconnected logical equations
Логическая минимизация при синтезе комбинационных структур в FPGA
Get PDFThe paper describes the research results of application efficiency of minimization programs of functional descriptions of combinatorial logic blocks, which are included in digital devices projects that are implemented in FPGA. Programs are designed for shared and separated function minimization in a disjunctive normal form (DNF) class and minimization of multilevel representations of fully defined Boolean functions based on Shannon expansion with finding equal and inverse cofactors. The graphical form of such representations is widely known as binary decision diagrams (BDD). For technological mapping the program of "enlargement" of obtained Shannon expansion formulas was applied in a way that each of them depends on a limited number of k input variables and can be implemented on one LUT-k – a programmable unit of FPGA with k input variables. It is shown that a preliminary logic minimization, which is performed on the domestic programs, allows improving design results of foreign CAD systems such as Leonardo Spectrum (Mentor Graphics), ISE (Integrated System Environment) Design Suite and Vivado (Xilinx). The experiments were performed for FPGA families’ Virtex-II PRO, Virtex-5 and Artix-7 (Xilinx) on standard threads of industrial examples, which define both DNF systems of Boolean functions and systems represented as interconnected logical equations.Описываются результаты исследования эффективности применения программ минимизации функциональных описаний блоков комбинационной логики, входящих в проекты цифровых устройств, реализуемых в FPGA (Field-Programmable Gate Array). Программы предназначены для раздельной и совместной минимизации функций в классе ДНФ (дизъюнктивных нормальных форм) и минимизации многоуровневых представлений систем полностью определенных булевых функций на основе разложения Шеннона с нахождением как равных, так инверсных коэффициентов (кофакторов) разложения. Графические формы таких представлений широко известны в литературе как BDD (Binary Decision Diagrams). Для технологического отображения применялась программа «укрупнения» полученных формул разложения Шеннона (логических уравнений), так, чтобы каждое из них зависело от ограниченного числа k входных переменных и могло быть реализовано на одном LUT-k ‑ программируемом элементе FPGA, имеющем k входных переменных (LUT ‑ Look-Up Table) . Показано, что предварительная логическая минимизация , выполняемая с помощью отечественных программ, позволяет улучшать результаты проектирования в зарубежных САПР (системах автоматизированного проектирования), таких как LeonardoSpectrum (ф. Mentor Graphics) и ISE (ф. Xilinx). Эксперименты проводились для семейств FPGA Virtex-II PRO и Virtex-5 (ф. Xilinx) на потоках стандартных промышленных примеров, задающих как системы дизъюнктивных нормальных форм булевых функций, так системы булевых функций в виде взаимосвязанных логических уравнений
Логическая минимизация булевых сетей с использованием разложения Шеннона
Get PDFA synthesis of logical circuits, comprising functional combination blocks of very large scale integration circuits, is one of the most important tasks of computer-aided design. As the data size of design tasks increases, the execution time of synthesis of logic circuits also increases. The global technological independent optimization as the first stage of synthesis of logical circuit is especially labor-consuming. The second stage is technological mapping of optimized logical representations of functions to the logical elements of technological library. The main features of logical circuit, such as area, performance, power consumption, depend on the efficiency of the first stage – global logical optimization. The evolution of methods of global logical optimization has revealed the efficiency of Shannon expansion in case of optimization of multi-level representations of the systems of fully defined Boolean function. A number of methods and programs were developed using graphical representations of Shannon expansions – BDD representations. Most of the developed methods of optimization of BDD-representations use the initial representations of functions systems in the form of disjunctive normal form (DNF).In the article an algorithm of minimization of nodes number of Boolean net, which is a multi-level representation of the system of fully defined Boolean function, is proposed. Minimization is based on Shannon expansion and a search of equal (with accuracy up to inversion) nodes in Boolean net. Such algorithm of logical optimization was implemented as application. The experiments have shown that this algorithm and the application is reasonable to use in cases when the initial multi-level representation of functions is impossible to define as DNF system, or when DNF system contains a large number of elementary conjunctions.Синтез логических схем, реализующих комбинационные блоки сверхбольших интегральных схем, – одна из важнейших задач компьютерного проектирования, так как размерность задач проектирования увеличивается, возрастает также время выполнения этапов синтеза логических схем. Особенно трудоемкой является глобальная технологическая независимая оптимизация – первый этап синтеза логической схемы. Суть второго этапа заключается в технологическом отображении оптимизированных логических представлений функций на логические элементы технологической библиотеки. Основные характеристики логической схемы, такие как площадь, быстродействие, энергопотребление, зависят от эффективности первого этапа. Эволюция методов глобальной логической оптимизации показала эффективность разложения Шеннона при оптимизации многоуровневых представлений систем полностью определенных булевых функций. Разработано множество методов и программ, использующих графические представления разложений Шеннона – BDD-представления. Большинство разработанных методов оптимизации BDD-представлений используют задания исходных систем булевых функций в виде дизъюнктивных нормальных форм (ДНФ).Предлагается алгоритм минимизации числа вершин булевой сети, являющейся многоуровневым представлением системы полностью определенных булевых функций. Минимизация осуществляется на основе разложения Шеннона и поиска вершин сети, реализующих одинаковые и взаимно инверсные функции. Предложенный алгоритм логической оптимизации реализован в виде программы. Эксперименты показали, что данный алгоритм и полученную программу целесообразно использовать в случае, когда исходное многоуровневое представление функций невозможно представить (за приемлемое время работы компьютерной программы) в виде системы ДНФ либо когда система ДНФ, полученная из многоуровневого представления, содержит большое число (десятки и сотни тысяч) элементарных конъюнкций
