Программа минимизации логических функций

Номинация: Самая актуальная работа
Просмотреть картинки списком
Автор: Носков О. И., Смирнов Д. Э.
Город: г. Шуя, Ивановская область
Место учебы: Шуйский филиал Ивановского промышленно-экономического колледжа

1. Описание работы программы

Данная программа позволяет производить минимизацию логических функций с любым числом переменных методом Квайна, заданных в виде совершенной дизъюнктивной нормальной формы (СДНФ).

Функциональность программы включает следующие возможности:

1.  Задание логических функций с помощью определения номеров входных наборов значений переменных, на которых функция принимает значение «Истина»;

2.  Построение таблицы истинности и карт Карно по заданным входным наборам;

3.  Минимизация заданной функции методом Квайна;

4.  Проверка результатов минимизации методом подстановки значений переменных на основе таблицы истинности;

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

Программа «Минимизация логических функций» разработана в среде Visual Basic For Applications в MS Excel 2007.

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

1.1. Интерфейс программы

Окно программы содержит следующие области:

1.   Поле задания количества переменных функции;

2.   Поле ввода списка номеров входных наборов значений переменных,

на которых функция принимает значения «Истина»;

3.   Таблица истинности. Область содержит двоичные представления значений переменных для единичных значений функции. При числе переменных большем 17 таблица истинности не отображается. Она выводится на отдельном листе «Результаты минимизации»

4.   Карта Карно. Отображаются только для количества переменных от 2 до 5.

5.   Окно «Результат минимизации» содержит выражение функции в виде минимальной дизъюнктивной нормальной формы (МДНФ). В качестве обозначения инверсии используется символ «!», который ставится перед соответствующей переменной.

6.   Окно «Результат проверки» содержит выражение МДНФ, полученное в результате подстановки значений переменных из соответствующего входного набора, и значение функции на данном наборе.

7.   Окно «Состояние» отображает наименование текущей операции

8.   Окно «Выполнение» отображает процент выполнения текущей операции

Элементы управления:

1.   Кнопка «Таблица» формирует области таблицы истинности и карт Карно по заданным входным наборам.

2.  Кнопка «Минимизация» производит минимизацию заданной функции с выводом полученного результата в окно «Результат минимизации». Минимизация производится в два этапа: склеивание и исключение избыточных импликант.

3.  Кнопка «Тестирование» производит формирование списка номеров входных наборов, построение таблицы истинности и карты Карно, минимизацию и проверку результата для всевозможных комбинаций единичных значений функций с числом переменных от двух до четырех включительно. Результаты проверки при этом не отображаются.

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

5.   Опция «По шагам» задает пошаговый режим тестирования либо проверки. Для выполнения очередного шага необходимо каждый раз нажимать кнопки «Тестирование» и «Проверка» соответственно.

6.  Кнопка «Проверка» производит проверку результата минимизации на истинность методом подстановки значений переменных для всех комбинаций, в том числе для тех, на которых функция принимает значение «Ложь».

7.  Кнопка «Остановка» предназначена для прекращения операций тестирования или проверки.

8.  Кнопка «Пропуск» используется только для прерывания операции исключения избыточных импликант, если задана опция «С анализом».

1.2. Описание процедуры минимизации

Минимизация реализуется подпрограммой Minimize и производится в два этапа:

1.  Склеивание и поглощение;

2.  Исключение избыточных импликант.

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

Перед запуском процедуры склеивания производится формирование сочетаний из заданного количества переменных по длине равной Количество переменных - 1. Количество данных сочетаний равно:

(см. рис. 1), где n - количество переменных, k - длина сочетаний

Каждое сочетание представляет собой последовательность номеров переменных.

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

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

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

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

склеенной переменной, либо несколько из них. Кроме того возможен вариант, когда происходит полное склеивание. В этом случае результирующий список содержит единственный элемент, состоящий из всех дефисов, а результирующее выражение будет равно 1 («Истина»).

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

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

(см рис. 2), где n-количество простых импликаций

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

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

Алгоритм исключения избыточных импликант состоит в последовательном удалении импликант из списка на основе текущей перестановки и анализе на предмет появления исходных наборов значений переменных, не задействованных ни в одной операции склеивания. Если такие наборы образуются, данная простая импликанта не может быть исключена. В противном случае импликанта удаляется, что приводит к упрощению результата минимизации.

1.3. Дополнительные возможности

Файл программы содержит дополнительные xls-листы для сохранения текущих результатов.

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

Лист «Результаты минимизации» содержит таблицу истинности и выражение, полученное в результате процедуры минимизации. На данном листе дублируются те же данные, которые отображаются в главном окне программы. Однако в главном может отсутствовать таблица истинности, либо результирующее выражение может не умещаться в окне результата минимизации. В этом случае всю информацию можно просмотреть на листе «Результаты минимизации».

2. Общие сведения

Программа разработана в рамках студенческого научно-технического кружка по программированию Шуйского филиала Ивановского промышленно-экономического колледжа.

Руководитель кружка: Носков Олег Иванович, преподаватель.

Студент: Смирнов Дмитрий Эдуардович, 2 курс, специальность

«Специальность: 220703 "Автоматизация технологических процессов и производств" (по отраслям)».

Целью данной работы является:

1.  Создание электронного наглядного пособия и средства контроля знаний для лекционных занятий, выполнения практических и лабораторных работ и самостоятельной подготовки студентов по дисциплине ОП.08.«Вычислительная техника»;

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

3.  Закрепление знаний в области основ вычислительной техники;

4.  Приобретение навыков программирования.

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

1.  Преобразование функций к заданному базису;

2.  Построение принципиальных схем логических функций.

Программа была протестирована на всех наборах единичных значений функций с числом переменных от 2 до 4 включительно.