Построение близких к минимальным схем из функциональных элементов для булевых функций от четырех аргументов на основе разложений Шэннона

Изучение направлений при проектировании дискретных преобразователей. Исследование булевых функций от четырех аргументов, их минимизация и оценка сложности. Решение задач, построение библиотеки близких формул для булевых функций от четырех аргументов.

Рубрика Математика
Вид статья
Язык русский
Дата добавления 28.01.2019
Размер файла 252,9 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

ПОСТРОЕНИЕ БЛИЗКИХ К МИНИМАЛЬНЫМ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ ДЛЯ БУЛЕВЫХ ФУНКЦИЙ ОТ ЧЕТЫРЕХ АРГУМЕНТОВ НА ОСНОВЕ РАЗЛОЖЕНИЙ ШЭННОНА

В.А. Филиппов Филиппов Владислав Александрович, студент, e-mail: vlad4423@yandex.ru

Filippov Vladislav, student, e-mail: vlad4423@yandex.ru

Иркутский национальный

исследовательский технический

университет, 664074, г. Иркутск, ул. Лермонтова, 83.

В современной электронике многие элементы являются устройствами, преобразующими входные сигналы в выходные. Дискретный преобразователь, одна из разновидностей таких устройств, имеет подкласс устройств, в которых время преобразования существенно мало по сравнению с длительностью сигналов. Математической моделью данного подкласса устройств являются схемы из функциональных элементов (СФЭ). Одно из важных направлений при проектировании рассматриваемого подкласса дискретных преобразователей является минимизация схем, входящих в их состав. Цель данной работы - исследование булевых функций от четырех аргументов, их минимизация и оценка сложности. В результате решения ряда задач была построена библиотека близких к минимальным формул, по которым строится СФЭ, для булевых функций от четырех аргументов.

Ключевые слова: СФЭ; булевы функции; разложения Шэннона, схема из функциональных элементов.

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].

Одно из важных направлений при проектировании этих устройств - минимизация схем, входящих в их состав. Ее целью является уменьшение количества функциональных элементов, из которых состоит схема.

Схемы с меньшим числом функциональных элементов имеют ряд следующих преимуществ: меньшую себестоимость, размер, энергопотребление, время работы, упрощенную диагностику неисправностей. Так как большие схемы строятся на базе меньших, то актуальной становится задача поиска минимальных или близких к минимальным представлений булевых функций от небольшого числа аргументов.

Цель и задачи работы

Цель работы - исследование булевых функций от четырех аргументов, их минимизация и оценка сложности.

Для достижения указанной цели были выделены следующие задачи:

1) разработать программу, строящую всевозможные разложения Шеннона и их упрощения для заданной булевой функции от четырех аргументов;

2) написать программу, которая оценивает сложность схемы, построенной на основе формулы;

3) перебрать все булевы функции от четырех аргументов с построением и оценкой схем на основе данного метода;

4) для проверки написать программу, которая переводит формулу в вектор, программу, которая переводит формулу в формат tex, и программу для визуализации полученной схемы из функциональных элементов.

Реализация

Одной из поставленных задач было построение всевозможных разложений Шеннона по двум аргументам для булевой функции, заданной в виде вектора.

В процессе решения данной задачи были выделены следующие подзадачи:

1) разработка класса представления булевой функции;

2) разработка класса представления разложения Шеннона по одному аргументу;

3) реализация построения разложений Шеннона по одному аргументу;

4) реализация построения всевозможных разложений Шеннона по двум аргументам.

Для представления булевой функции был сформирован класс BooleanFunction. В этом классе есть три поля. Поле bytesList, которое содержит список битов, где i-ый бит является значением булевой функции на i-ом двоичном наборе, поле n, которое содержит количество аргументов булевой функции, и поле argumentsList, содержащее список аргументов.

Для представления разложения Шеннона по одному аргументу был разработан класс BooleanResidual. В данном классе есть три поля. Поля left и right содержат нулевую и единичную остаточную, а поле index - аргумент, по которому было произведено разложение. В этом классе нулевая и единичная остаточные рассматриваются как экземпляры класса BooleanFunction.

При реализации построения всевозможных разложений Шеннона по двум аргументам было необходимо написать функцию, которая строит разложение Шеннона по одному аргументу.

Принцип ее работы заключается в следующем. На вход ей поступает номер аргумента, по которому происходит разложение, и булева функция, для которой выполняется разложение. По заданной булевой функции и аргументу находятся нулевая и единичная остаточные. Результатом работы этой функции является экземпляр класса BooleanResidual, который создается по полученным ранее нулевой и единичной остаточным.

Последней задачей стало написание функции, строящей всевозможные разложения Шеннона по двум аргументам.

Работает она следующим образом. На вход поступает булева функция. Сначала перебираются все варианты одного аргумента, и по ним строятся разложения. Затем для этих разложений перебираются варианты уже двух аргументов, и по ним строятся разложения. Результатом работы данной функции является список всевозможных разложений Шеннона по двум аргументам.

Далее необходимо было реализовать упрощения формул, на основе которых строятся схемы.

Из эквивалентных преобразований при решении данной задачи использовались: дистрибутивность, работа с константами, законы де Моргана и приведение к базису B0.

В процессе решения поставленной задачи были выделены следующие подзадачи:

1) написание функции, строящей по формуле обратную польскую запись;

2) написание функции, строящей всевозможные упрощения для заданной формулы с использованием законов де Моргана;

3) написание функции, строящей всевозможные упрощения для заданной формулы с использованием дистрибутивности.

Для реализации упрощений было необходимо написать функцию, которая по формуле строит обратную польскую запись.

Также было необходимо создать функцию, которая разбивает формулу на три части: левая часть, правая часть и операция.

Принцип ее работы заключается в следующем. На вход поступает формула. Затем формула преобразуется в обратную польскую запись. Далее при помощи стека выполняется перевод из обратной польской записи в формулу, но производится он не до конца, а до тех пор, пока в стеке не окажутся три элемента (операция, левая часть и правая часть) и строка с обратной польской записью не будет уже полностью обработана. Результатом работы этой функции является стек с тремя элементами (левой частью, правой частью и операцией).

Далее была создана функция, которая строит всевозможные упрощения для заданной формулы с использованием закона де Моргана.

Общая идея этой функции заключается в следующем. Создается 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

преобразователь дискретный функция булевой

Таким образом, была построена библиотека близких к минимальным формул, по которым строится СФЭ, для булевых функций от четырех аргументов.

Библиографический список

1. Яблонский С.В. Введение в дискретную математику. Москва: Наука, 1986. 384 с.

Размещено на Allbest.ru

...

Подобные документы

  • Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геометрическое представление логических функций. Геометрический метод минимизации булевых функций. Карты Карно.

    курсовая работа [278,1 K], добавлен 21.02.2009

  • Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.

    курсовая работа [701,9 K], добавлен 27.04.2011

  • Полнота и замкнутость системы булевых функций. Алгоритм построения таблицы истинности двойственной функции. Класс L линейных функций, сущность полинома Жегалкина. Распознавание монотонной функции по вектору ее значений. Доказательство теоремы Поста.

    учебное пособие [1,3 M], добавлен 20.08.2014

  • Основные этапы развития булевой алгебры и применение минимальных форм булевых многочленов к решению задач, в частности, с помощью метода Куайна - Мак-Класки. Применение минимизирования логических форм при проектировании устройств цифровой электроники.

    курсовая работа [58,6 K], добавлен 24.05.2009

  • Минимизация заданного выражения алгебры множеств на основании известных свойств. Анализ заданного бинарного отношения в общем виде. Вывод формул булевых функций для каждого элемента и схемы в целом. Преобразование формулы булевой функции логической схемы.

    контрольная работа [286,7 K], добавлен 28.02.2009

  • Логика - наука о законах и формах мышления, а основное понятие алгебры логики - высказывание. Основные понятия и тождества булевой алгебры. Изучение методов минимизации булевых функций. Метод Квайна, основанный на применении двух основных соотношений.

    контрольная работа [178,2 K], добавлен 20.01.2011

  • Понятие, основные свойства элементарных булевых функций и соотношения между ними. Формулировка принципа двойственности. Совершенные дизъюнктивная и конъюнктивная нормальные формы. Многочлен (полином) Жегалкина. Суперпозиция и замыкание класса функций.

    презентация [24,4 K], добавлен 05.02.2016

  • Построение графа и таблицы поведения автомата. Нахождение системы булевых функций для возбуждения JK-триггеров, реализующих функции y. Определение булевой функции для реализации функции j. Составление логической схемы автомата, кодирование данных.

    курсовая работа [200,4 K], добавлен 27.04.2011

  • Построение таблицы поведения автомата и соответствующего графа. Нахождение системы булевых функций для возбуждения T-триггеров, реализующих функции "пси". Определение булевой функции для реализации функции "фи". Составление логической схемы автомата.

    курсовая работа [96,7 K], добавлен 27.04.2011

  • Понятие алгебры логики, ее сущность и особенности, основные понятия и определения, предмет и методика изучения. Законы алгебры логики и следствия из них, методы построения формул по заданной таблице истинности. Формы представления булевых функций.

    учебное пособие [702,6 K], добавлен 29.04.2009

  • Булевы алгебры – решетки особого типа, применяемые при исследовании логики (как логики человеческого мышления, так и цифровой компьютерной логики), а также переключательных схем. Минимальные формы булевых многочленов. Теоремы абстрактной булевой алгебры.

    курсовая работа [64,7 K], добавлен 12.05.2009

  • График функции как множество всех точек координатной плоскости, абсциссы которых равны значениям аргументов, а ординаты – соответствующим значениям функции. Исследование графиков функций и графическое решение уравнений, их разновидности и особенности.

    контрольная работа [15,5 K], добавлен 10.11.2010

  • Характеристика булевой алгебры и способы представления булевых функций. Понятие и сущность бинарных диаграммах решений. Упорядоченные бинарные диаграммы решений, их построение и особенности применения для обработки запросов в реляционных базах данных.

    дипломная работа [391,7 K], добавлен 21.01.2010

  • Нахождение пределов функций. Определение значения производных данных функций в заданной точке. Проведение исследования функций с указанием области определения и точек разрыва, экстремумов и асимптот. Построение графиков функций по полученным данным.

    контрольная работа [157,0 K], добавлен 11.03.2015

  • Сущность и математическое обоснование булевой функции, ее назначение и пути решения. Порядок составления таблицы истинности для определенного количества переменных. Связь всех дизъюнкций в конъюнкцию. Разработка и листинг программы представления.

    курсовая работа [837,6 K], добавлен 27.04.2011

  • Использование эквивалентных преобразований. Понятие основных замкнутых классов. Метод минимизирующих карт и метод Петрика. Операция неполного попарного склеивания. Полином Жегалкина и коэффициенты второй степени. Таблицы значений булевых функций.

    контрольная работа [90,4 K], добавлен 06.06.2011

  • Вычисление пределов функций. Нахождение производные заданных функций, решение неопределенных интегралов. Исследование функции и построение ее графика. Особенности вычисления площади фигуры, ограниченной линиями с использованием определенного интеграла.

    контрольная работа [283,1 K], добавлен 01.03.2011

  • Свойства алгебры Жегалкина. Действия с логическими константами (нулём и единицей). Свойства элементарных булевых функций, задаваемых логическими операциями. Способы построения полиномов с помощью таблиц истинности (метод неопределенных коэффициентов).

    курсовая работа [467,2 K], добавлен 28.11.2014

  • Графическая интерпретация множеств и операций над ними. Математическая логика, булева алгебра. Совершенная конъюнктивная нормальная форма. Равносильные формулы и их доказательство. Полнота системы булевых функций. Логика предикатов, теория графов.

    лекция [253,7 K], добавлен 01.12.2009

  • Основные аксиомы и тождества алгебры логики. Аналитическая форма представления булевых функций. Элементарные функции алгебры логики. Функции алгебры логики одного аргумента и формы ее реализации. Свойства, особенности и виды логических операций.

    реферат [63,3 K], добавлен 06.12.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.