УДК 004
ПОСТРОЕНИЕ БЛИЗКИХ К МИНИМАЛЬНЫМ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ ДЛЯ БУЛЕВЫХ ФУНКЦИЙ ОТ ЧЕТЫРЕХ АРГУМЕНТОВ НА ОСНОВЕ РАЗЛОЖЕНИЙ ШЭННОНА
1
Иркутский национальный исследовательский технический университет,
664074, 3.
В современной электронике многие элементы являются устройствами, преобразующими входные сигналы в выходные. Дискретный преобразователь, одна из разновидностей таких устройств, имеет подкласс устройств, в которых время преобразования существенно мало по сравнению с длительностью сигналов. Математической моделью данного подкласса устройств являются схемы из функциональных элементов (СФЭ). Одно из важных направлений при проектировании рассматриваемого подкласса дискретных преобразователей является минимизация схем, входящих в их состав. Цель данной работы – исследование булевых функций от четырех аргументов, их минимизация и оценка сложности. В результате решения ряда задач была построена библиотека близких к минимальным формул, по которым строится СФЭ, для булевых функций от четырех аргументов.
Ключевые слова: СФЭ; булевы функции; разложения Шэннона, схема из функциональных элементов.
BUILDING CLOSE TO MINIMAL SFE FOR BOOLEAN FUNCTIONS OF FOUR ARGUMENTS BASED ON SHANNON'S DECOMPOSITION
V. Filippov
Irkutsk National Research Technical University,
83 Lermontov Str., Irkutsk, 664074, Russia.
In modern electronics, many elements are devices that convert input signals into output. One form of such devices is a discrete converter. One of the subclasses of discrete converters is a class of devices in which the conversion considerably little compared with the duration of signals. The mathematical model of such devices is a scheme of functional elements. One important aspect in the design of these devices is minimization schemes within them. Schemes with fewer functional elements have the following advantages: lower cost, size, power consumption, time, simplified fault diagnosis. The author builds a library of close to the minimum formulas, which are used to SFE, for Boolean functions of four arguments.
Keywords: SFE; Boolean function; Shannon's Decomposition, scheme of functional elements.
Введение
Многие элементы в современной электронике являются устройствами, преобразующими входные сигналы в выходные. Одной из разновидностей таких устройств является дискретный преобразователь. Одним из подклассов дискретных преобразователей является класс устройств, в которых время преобразования существенно мало по сравнению с длительностью сигналов. Математической моделью таких устройств являются схемы из функциональных элементов (СФЭ) [1].
Одно из важных направлений при проектировании этих устройств – минимизация схем, входящих в их состав. Ее целью является уменьшение количества функциональных элементов, из которых состоит схема.
Схемы с меньшим числом функциональных элементов имеют ряд следующих преимуществ: меньшую себестоимость, размер, энергопотребление, время работы, упрощенную диагностику неисправностей. Так как большие схемы строятся на базе меньших, то актуальной становится задача поиска минимальных или близких к минимальным представлений булевых функций от небольшого числа аргументов.
Цель и задачи работы
Цель работы – исследование булевых функций от четырех аргументов, их минимизация и оценка сложности.
Для достижения указанной цели были выделены следующие задачи:
разработать программу, строящую всевозможные разложения Шеннона и их упрощения для заданной булевой функции от четырех аргументов; написать программу, которая оценивает сложность схемы, построенной на основе формулы; перебрать все булевы функции от четырех аргументов с построением и оценкой схем на основе данного метода; для проверки написать программу, которая переводит формулу в вектор, программу, которая переводит формулу в формат tex, и программу для визуализации полученной схемы из функциональных элементов.Реализация
Одной из поставленных задач было построение всевозможных разложений Шеннона по двум аргументам для булевой функции, заданной в виде вектора.
В процессе решения данной задачи были выделены следующие подзадачи:
разработка класса представления булевой функции; разработка класса представления разложения Шеннона по одному аргументу; реализация построения разложений Шеннона по одному аргументу; реализация построения всевозможных разложений Шеннона по двум аргументам.Для представления булевой функции был сформирован класс BooleanFunction. В этом
классе есть три поля. Поле bytesList, которое содержит список битов, где i-ый бит является значением булевой функции на i-ом двоичном наборе, поле n, которое содержит количество аргументов булевой функции, и поле argumentsList, содержащее список аргументов.
Для представления разложения Шеннона по одному аргументу был разработан класс BooleanResidual. В данном классе есть три поля. Поля left и right содержат нулевую и единичную остаточную, а поле index – аргумент, по которому было произведено разложение. В этом классе нулевая и единичная остаточные рассматриваются как экземпляры класса BooleanFunction.
При реализации построения всевозможных разложений Шеннона по двум аргументам было необходимо написать функцию, которая строит разложение Шеннона по одному аргументу.
Принцип ее работы заключается в следующем. На вход ей поступает номер аргумента, по которому происходит разложение, и булева функция, для которой выполняется разложение. По заданной булевой функции и аргументу находятся нулевая и единичная остаточные. Результатом работы этой функции является экземпляр класса BooleanResidual, который создается по полученным ранее нулевой и единичной остаточным.
Последней задачей стало написание функции, строящей всевозможные разложения Шеннона по двум аргументам.
Работает она следующим образом. На вход поступает булева функция. Сначала перебираются все варианты одного аргумента, и по ним строятся разложения. Затем для этих разложений перебираются варианты уже двух аргументов, и по ним строятся разложения. Результатом работы данной функции является список всевозможных разложений Шеннона по двум аргументам.
Далее необходимо было реализовать упрощения формул, на основе которых строятся схемы.
Из эквивалентных преобразований при решении данной задачи использовались: дистрибутивность, работа с константами, законы де Моргана и приведение к базису B0.
В процессе решения поставленной задачи были выделены следующие подзадачи:
написание функции, строящей по формуле обратную польскую запись; написание функции, строящей всевозможные упрощения для заданной формулы с использованием законов де Моргана; написание функции, строящей всевозможные упрощения для заданной формулы с использованием дистрибутивности.Для реализации упрощений было необходимо написать функцию, которая по формуле строит обратную польскую запись.
Также было необходимо создать функцию, которая разбивает формулу на три части: левая часть, правая часть и операция.
Принцип ее работы заключается в следующем. На вход поступает формула. Затем формула преобразуется в обратную польскую запись. Далее при помощи стека выполняется перевод из обратной польской записи в формулу, но производится он не до конца, а до тех пор, пока в стеке не окажутся три элемента (операция, левая часть и правая часть) и строка с обратной польской записью не будет уже полностью обработана. Результатом работы этой функции является стек с тремя элементами (левой частью, правой частью и операцией).
Далее была создана функция, которая строит всевозможные упрощения для заданной формулы с использованием закона де Моргана.
Общая идея этой функции заключается в следующем. Создается HashMap для хранения формулы и ее вариаций с применением законов де Моргана. Далее для формулы строится бинарное дерево. Для каждого корня (подкорня) этого дерева используются его потомки, которые соединяются через операцию, указанную в корне (подкорне). В результате получаются формулы. К каждой из них применяются законы де Моргана, и полученные формулы записываются в HashMap. Затем каждая формула разбивается на две части, и каждая часть заменяется на свои вариации, содержащиеся в HashMap. В результате получается список формул.
Следующей задачей было построение всевозможных упрощений для заданной формулы с использованием дистрибутивности. Из дистрибутивности был реализован только случай с вынесением общего множителя. Заметим, что применяется она только к разложениям Шеннона по двум аргументам.
Суть ее работы заключается в следующем. На вход поступает разложение Шеннона по двум аргументам, оно разбивается на четыре части по дизъюнкции. Затем каждая часть разбивается на три подчасти по конъюнкции. Для каждой части запускается цикл прохода по подчастям, в котором подчасть каждой части проверяется на ее наличие в других частях. Если она присутствует, то подчасть выносится за скобки, а из тех частей, в которых она есть, она удаляется, и то, что получилось, объединяется через конъюнкцию. В результате образуются все варианты вынесения общего множителя.
Далее необходимо было решить задачу оценки сложности схемы, для чего использовался алгоритм перевода из формулы в обратную польскую запись и алгоритм перевода из обратной польской записи в формулу.
Принцип их работы заключается в следующем. На вход подается формула, которая переводится в обратную польскую запись. Затем создается HashSet, и после при помощи стека происходит обратный перевод в формулу с добавлением всех элементов, которые попадают в стек, кроме переменных, в HashSet. Так как HashSet состоит из функциональных элементов, то его размер является сложностью схемы, построенной на основе формулы.
Для проверки результатов дополнительно необходимо было создать программы для перевода формулы в вектор и в формат tex.
При реализации перевода формулы в вектор был использован алгоритм перевода из формулы в обратную польскую запись и алгоритм перевода из обратной польской записи в формулу. Только вместо добавления в стек переменных и формул добавляются результаты формул и значения переменных для каждого двоичного набора.
Суть реализации перевода формулы в формат tex заключается в замене символов на соответствующие команды LaTeXa и формировании файла формата tex.
Еще одной задачей для проверки результатов была визуализация схем из функциональных элементов, построенных по заданным формулам.
Для ее реализации был применен алгоритм перевода из формулы в обратную польскую запись и алгоритм перевода из обратной польской записи в формулу. Также использовался стек и класс HashSet.
Суть реализации заключается в следующем. На вход поступает формула, для которой строится обратная польская запись. Создается HashSet, и затем при помощи стека происходит обратный перевод в формулу с добавлением всех элементов, которые попадают в стек, кроме переменных, в HashSet. В результате в HashSet содержатся функциональные элементы, по которым строится схема и представляется ее визуализация.
Подводя итоги, укажем последовательность преобразований для получения оценок СФЭ. На вход поступает булева функция, заданная в виде вектора. Для нее строятся всевозможные разложения Шеннона по двум аргументам. Далее к разложениям применяется вынесение общего множителя. Затем для каждой получившейся формулы строятся варианты ее упрощения. И после среди них находится формула, сложность схемы которой является наименьшей, – она и является ответом.
Был произведен перебор для всех 65536 булевых функций от четырех аргументов, и для каждой их них получена формула, сложность схемы которой близка к минимальной. Результаты перебора представлены таблице.
Результаты перебора 65536 булевых функций от четырех аргументов
Операции | Кол-во булевых функций, сложность которых больше 15 |
Разложение Шеннона + вынесение общего множителя | 3810 |
Разложение Шеннона + вынесение общего множителя + упрощение по де Моргану | 849 |
Также был получен список достаточно сложных булевых функций (рис. 1) и их представлений в базисе B0 (рис. 2).
Рис. 1. Часть списка достаточно сложных булевых функций
Рис. 2. Представления части списка булевых функций в базисе B0
Таким образом, была построена библиотека близких к минимальным формул, по которым строится СФЭ, для булевых функций от четырех аргументов.
Библиографический список
Яблонский в дискретную математику. Москва: Наука, 1986. 384 с.
1 , студент, e-mail: *****@***ru
Filippov Vladislav, student, e-mail: *****@***ru
