Минимизация булевых функций

47

Вступление

Одним из основных вопросов экономической политики на современном этапе является ускорение экономического и социального развития общества Решение этой задачи требует дальнейшего совершенствования системы управления экономикой, улучшения прогнозирования и планирования на базе более широкого применения математических методов и ЭВМ.

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

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

В широком смысле слова под, управлением понимают организационную деятельность, осуществляющую функции руководства чужой работой для достижения определенных целей. Процесс управления состоит в принятии решений о наиболее целесообразных действиях в той или иной сложившейся ситуации. Человек, осуществляющий управление, принимает решения, оценивая окружающую обстановку с помощью информации, получаемой от своих органов чувств, измерительных приборов, других лиц. Во многих случаях этой информации оказывается недостаточно для однозначной оценки обстановки - Тогда человек использует свой опыт, знания, память, интуицию. Однако в современных условиях даже у опытного руководителя знаний и интуиции оказывается недостаточно, чтобы осуществлять эффективное управление, принимать целесообразные решения. Здесь на помощь человеку приходит кибернетика, которая позволяет переложить на автоматические устройства сбор и обработку больших объемов информации, анализ сложившихся ситуаций и выработку рекомендаций относительно целесообразных управляющих действий.

Выдающийся математик академик Л.П. Колмогоров писал:»… кибернетика широко пользуется математическим методом и стремится к получению конкретных результатов, позволяющий как анализировать такого рода системы (исследовать их устройства на основании опыта обращения о ними), так и синтезировать их (создавать схемы систем, способных осуществлять заданные действия)».

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

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

1. Минимизация форм булевых функций. Методы минимизации

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

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

Существуют два направления минимизации:

1. Кратчайшая форма записи (цель - минимизировать ранг каждого терма). При этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ.

2. Получение минимальной формы записи (цель - получение минимального числа символов для записи всей функции сразу).

При этом следует учесть, что ни один из способов минимизации не универсален!

Существуют различные методы минимизации:

1. Метод непосредственных преобразований логических функций

При применении данного метода:

а) Записываются ДСНФ логических функций

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

По отношению к соседним min-термам применяется закон склейки, значит ранг min-терма понижается на единицу.

Определение: Min-термы, образованные при склеивании называются импликантами.

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

Определение: Несклеивающиеся импликанты называются прослойками.

Определение: Формула, состоящая из простых импликант - тупиковая.

Пример:

0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	0

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

Пример:

Мы получили минимальную СНФ.

Метод неопределенных коэффициентов. (1.2)

Суть метода состоит в преобразовании ДСНФ в МДНФ.

На основании теоремы Жигалкина любую ФАЛ можно представить в виде (рассмотрим на примере трех переменных):

Алгоритм определения коэффициентов:

1. Исходное уравнение разбить на систему уравнений, равных числу строк в таблице истинности.

2. Напротив каждого выражения поставить соответствующее значение функции.

3. Выбрать строку, в которой значение функции и приравнять все к нулю.

4. Просмотреть строки, где функция имеет единичное значение, и вычеркнуть все коэффициенты, встречающиеся в нулевых строках.

5. Проанализировать оставшиеся коэффициенты в единичных строках.

6. Используя правило, что дизъюнкция равна 1 если хотя бы один из , выбрать min-термы минимального ранга. Причем отдавать предпочтение коэффициентам, встречающимся в нескольких уравнениях одновременно.

7. Записать исходный вид функции.

Метод неопределенных коэффициентов применим для дизъюнктивной формы и непригоден для конъюнктивной.

Пример:



0	0	0	0	00	00	00	000	1
1	0	0	1	00	01	01	001	0
2	0	1	0	01	00	10	010	1
3	0	1	1	01	01	11	011	0
4	1	0	0	10	10	00	100	1
5	1	0	1	10	11	01	101	0
6	1	1	0	11	10	10	110	0
7	1	1	1	11	11	11	111	1

Итак, получим

Метод Квайна (1.3)

Суть метода сводится к тому, чтобы преобразовать ДСНФ в МДНФ. Задачи минимизации по методу Квайна состоит в попарном сравнении импликант, входящих в ДСНФ с целью выявления возможности склеивания по какой-то пременной так:

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

Определение: Непомеченные термы называются первичными импликантами.

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

Для этого:

1. Составляются таблицы, в строках которых пишутся найденные первичные импликанты, а в столбцах указываются термы первичной ФАЛ.

2. Клетки этой таблицы отмечаются в том случае, если первичная импликанта входит в состав какого-нибудь первичного терма.

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

Алгоритм метода Квайна (шаги):

1. Нахождение первичных импликант.

Исходные термы из ДНФ записывают в столбик и склеиваю сверху вниз. Непомеченные импликанты переходят в функции на этом шаге.

2. Расстановка меток избыточности.

Составляем таблицу, в которой строки - первичные импликанты, столбцы - исходные термы. Если некоторый min-терм содержит первичный импликант, то на пересечении строки и столбца ставим метку.

3. Нахождение существенных импликант.

Если в каком-либо столбце есть только одна метка, то первичный импликант соответствующей строки является существенным.

4. Строка, содержащая существенный импликант и соответствующие столбцы вычеркиваются.

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

5. Выбор минимального покрытия.

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

6. Далее результат записывается в виде функции.

Пример:

Шаг 1.

Термы 4 го ранга	Термы 3 го ранга	Термы 2 го ранга
* 1 * 3 * 4 * 1 * 2 * 2 * 3 * 4	* 1 * 2 * 2 * 1

Шаг 2.

Недостаток метода Квайна - необходимость полного по парного сравнения всех min-термов на этапе нахождения первичных импликант.

Идея модификации метода Квайна - метод Квайна-Мак-Класки. (1.4)

1. Каждая конъюнкция в ДСНФ представляется своим двоичным набором.

2. Вся совокупность номеров наборов разбивается на группы в зависимости от числа единиц, имеющихся в номерах наборов (0-группа, 1-группа, 2-группа и.т.д.).

3. Сравниваются две группы, отличающиеся на одну единицу.

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

5. В процессе преобразования возникают новые сочетания (n-группы).

6. Процесс преобразования длится до тех пор, пока возможна операция склеивания.

7. Элементы преобразованных групп являются первичными импликантами, которые вместе с номерами исходных наборов образуют таблицы разметок.

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

Определение: n-группа - это такой набор аргументов функции, что число всех аргументов равных единице равно n, причем значении функции равно 1.

Пример:

Составим таблицу истинности

0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	1
0	1	0	0	1
0	1	0	1	1
0	1	1	0	1
0	1	1	1	1
1	0	0	0	1
1	0	0	1	1
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	0
1	1	1	0	0
1	1	1	1	1

Запишем n-группы:

0-Группа: 0000

1-Группа: 0001, 0010, 0100, 1000

2-Группа: 0011, 0101, 0110, 1001

3-Группа: 0111,1011

4-Группа: 1111

Теперь сравним группы с номерами n и n+1:

0-Группа: 000-, 00-0, 0-00, -000

1-Группа: 00-1, 0-01, -001, 001-, 0-10, 010-, 01-0, 100-

2-Группа: 0-11, -011, 01-1, 011-, 10-1

3-Группа: -111, 1-11

Еще раз сравним (при этом прочерки должны быть на одинаковых позициях):

0-Группа: 00-, 0-0-, -00-

1-Группа: 0-1, -0-1, 0-1-, 01-

2-Группа: -11

И еще раз сравним:

0-Группа: 0-

Запишем таблицу исходных min-термов, где функция равна 1:



0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1011	1111
V	V	V	V	V	V	V	V					0-

Выделим минимальное число групп, покрывающих

Для проверки составим таблицу истинности

	1000	1001	1011	1111
-00-	V	V
-0-1		V	V
-111			V	V

Метод минимизирующих карт (для ДСНФ и КСНФ). (1.5)

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

Для ДСНФ единицы ставятся в клетке, соответствующей номеру набора, на котором значение функции равно единице, а ноль не ставится, а для КСНФ - наоборот.

Диаграмма для двух логических переменных (для ДСНФ):

Для трех переменных:



Карты Карно используются для ручной минимизации функций алгебры логики при небольшом количестве переменных. Правило минимизации: склеиванию подвергаются 2,4,8,16, клеток и клетки, лежащие на границе карты.

При числе переменных 5 и больше отобразить графически функцию в виде единой плоской карты невозможно. Тогда строят комбинированные карты, состоящие из совокупности более простых карт. Процедура минимизации заключается тогда в том, что сначала находится минимальная форма 4-х мерных кубов (карт), а затем, расширяя понятие соседних клеток, отыскивают min-термы для совокупности карт. Причем соседними клетками являются клетки, совпадающие при совмещении карт поворотом вокруг общего ребра.

Пример: Минимизировать ФАЛ от двух переменных:

	1	1
	1

Минимизировать функцию:

	1	1	1
		1

Минимизация логических функций, заданных в базисе .

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

1)

2)

3)

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

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

1) Подсчитывают, сколько раз в единичных строках встречаются термы первого ранга и оставляют из них те, которые встречаются максимальное число раз.

2) Находят нулевые строки, в которых встречаются оставленные в первом шаге термы и их не обнуляют.

3) Рассматривая нулевую строку, в которой остался одни единичные термы и находят в ней еще единичный терм, встречающийся максимальное число раз в единичных строках, в которых еще не было оставлено ни одного терма и.т.д.

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

Не полностью определенные ФАЛ (1.6)

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

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

Пример: доопределить функцию

Где символ * означает «может быть».

Доопределим *=0

1)

Доопределим *=1

2)

Если доопределять *=0 или *=1 то получим минимальный вариант:

3)

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

Пример: найти минимальную форму для

Составим таблицу истинности:

0	0	0	0	1
0	0	0	1	*
0	0	1	0	*
0	0	1	1	0
0	1	0	0	*
0	1	0	1	0
0	1	1	0	1
0	1	1	1	*
1	0	0	0	*
1	0	0	1	1
1	0	1	0	0
1	0	1	1	*
1	1	0	0	0
1	1	0	1	*
1	1	1	0	1
1	1	1	1	*

1) доопрделим *=1 и получим минимальный вид функции



Доопрделим *=0

Оптимальное доопрделение функций соответствующее минимальному покрытию может быть найдено по методу Квайна.

			V
	V		V
		V		V
			V

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

Временные булевы функции. (1.7)

Определение: Временная булева функция - логическая функция вида , принимающая значение единицы при , где s - дискретное целочисленное значение, называемое автоматическим временем.

Утверждение: число различных временных булевых функций равно .

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

Любая временная булева функция может быть представлена в виде

Где - конъюнктивный или дизъюнктивный терм, а равно 0 или 1 в зависимости от времени t. Форма представления временных булевых функций позволяет применить все методы минимизации.

Пример:

0	0	0	0
0	1	0	0
1	0	0	1
1	1	0	0
0	0	1	0
0	1	1	1
1	0	1	1
1	1	1	0
0	0	2	0
0	1	2	0
1	0	2	1
1	1	2	1

Временные булевы функции применяются для описания работы схем с памятью.

Определение: Производной первого порядка от булевой функции по переменной называется выражение:



Где первая - единичная остаточная функция, а вторая - нулевая остаточная функция.

Пример:

после минимизации получим:

производная первого порядка по переменной определяет условие, при котором эта функция изменяет свое значение при перемене значения с 0 на 1.

Для данной функции получим схему:

-

Смешанные производные k-го порядка.

Определение: смешанной производной k-го порядка называется выражение вида:

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

Согласно Бохману, производная k-го порядка вычисляется по формуле:

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

1)

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

Приложение алгебры логики. (1.8)

1) Для решения логических задач, - суть в том, что имея конкретные условия логической задачи стараются записать их в виде ФАЛ, которые затем минимизируют. Простейший вид формуды, как правило, приводят к ответу на задачу.

Задача:

По подозрению в преступлению задержаны: Браун, Джон и Смит. Один - старик, другой - чиновник, третий - мошенник). Все они дали показания, причем: старик всегда говорил правду, мошенник всегда лгал, а чиновник иногда лгал, а иногда говорил правду.

Показания: Браун - Я совершил это, Джон не виноват.

Джон - Браун не виноват, это сделал Смит.

Смит - я не виноват, виновен Браун.

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

Обозначим буквами: Б - виноват Браун

Д - виноват Джон

С - виноват Смит

Тогда показания запишутся в виде:

Тогда запишем функцию:

Запишем ее таблицу истинности и вычеркнем некоторые не подходящие наборы (2 преступника одновременно и.т.д.)

	Б	Д	С				L
1	0	0	0	0	0	0	0
2	0	0	1	0	1	0	1
3	0	1	0	0	0	0	0
4	0	1	1	0	1	0	1
5	1	0	0	1	0	1	1
6	1	0	1	1	0	0	1
7	1	1	0	0	0	1	1
8	1	1	1	0	0	0	0

Значит Браун - чиновник, Джон - старик, Смит - мошенник, он же преступник.

2) Среди технических средств автоматизации (релейно-контактные системы).

Значительное место занимают РКС, используемые в вычислительной технике. РКС - переключательные схемы. В 1910 г. физик Эрнфест указал на возможность применения алгебры логики при исследовании РКС. Его идея заключается в том, что каждой схеме можно сопоставить ФАЛ и наоборот. Это позволяет выявить возможности схемы, изучая соответствующую формулу, а упрощение схемы свести к упрощению ФАЛ - анализ переключательной схемы.

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

Рассмотрим связь между переключательными схемами и ФАЛ. (1.8.1)

Определение: переключательная схема - схемотехническое изображение устройства, состоящее из следующих элементов:

1) переключатель (может быть разомкнут или замкнут)

2) проводники

3) вход в схему и выход из нее

Примеры:

а) А В

б) Дизъюнкция: А В

в) Импликация: А В

г) Тождественно ложно: А В

д) Тождественно истинно: А В

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

А Б

После упрощения получим:

А B

Синтез логической схемы. (1.8.2)

В зависимости от выходного сигнала, все электрические схемы можно разбить на две группы:

1) 1-го рода - содержит комбинаторные схемы (выход зависит от входа)

2) 2-го рода - накапливающие схемы (элементы памяти, выход зависит от входа в данный момент времени и в предыдущий момент времени).

По количеству входов и выходов делятся на:

1) 1+1 - 1 вход и 1 выход

2) n+1 - n входов и 1 выход

3) 1+n - 1 вход и n выходов

4) n+m - n входов и m выходов

Любая ЭВМ состоит из комбинации схем 1-го и 2-го порядков.

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

Анализ схемы производят в два этапа:

1) Из вспомогательной схемы удаляются все вспомогательные элементы, не влияющие на логику работы системы.

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

Примеры:

Простейшие логические схемы:

После упрощения получим:

Синтез электронных схем (1.8.3)

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

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

2) анализ логических уравнений и получение минимальной формы для каждого из них в заданном базисе.

3) переход от логических уравнений к логической схеме, посредством применения логических операторов.

Электронные схемы с одним выходом.

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

Пример:

Типы логических элементов

Надо привести в базис импликации

Т.к. , то

Тогда получим схему:

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

Пример: синтезировать схему одноразрядного двоичного сумматора методом декомпозиции в базисе

Составим таблицу истинности:



0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Где - переменные, - сумма в -ом разряде, - перенос из младшего разряда в старший, - перенос из старшего разряда.

Составим ДСНФ:

		1		1
	1		1

	1	1	1
		1

Тогда



Ci

Пi

Такой способ не очень хорош, так как не всегда оптимален.

Электронные схемы с несколькими выходами (1.8.4)

Пусть n входов и k выходов.

Классический пример таких схем - дешифратор

Входы Выходы

0	0	0	1	0	0	0	0	0	0	0
0	0	1	0	1	0	0	0	0	0	0
0	1	0	0	0	1	0	0	0	0	0
0	1	1	0	0	0	1	0	0	0	0
1	0	0	0	0	0	0	1	0	0	0
1	0	1	0	0	0	0	0	1	0	0
1	1	0	0	0	0	0	0	0	1	0
1	1	1	0	0	0	0	0	0	0	1

Причем, например , а и.т.д.

y0

y7

Несложно убедиться, что такой подход не является оптимальным, поэтому рассмотрим следующие моменты синтеза схем:

1) Классический основан на выделении простых импликант заданной системы функций, подобно тому, как это делается в методе минимизации Квайна-Мак-Класки, а затем ищется покрытие заданной функции этими импликантами.

При этом требуется:

1) найти простые импликанты заданной системы функций

2) выразить каждую функцию через простые импликанты

3) синтезировать схему, включающую только эти импликанты и связи между ними

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

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

y2

y1

Метод каскадов (1.8.5)

Этот метод основан на разложении ФАЛ на k переменных:

Где kn

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



и.т.д.

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

2. Определить понятия: микрооперация, микрокоманда, микропрограмма, МПА, критические состязания, гонки

Элементарное действие, выполняемое в одном из узлов ОБ в течение одного такта, называется микрооперацией, В некоторые такты в различных узлах ОБ (регистрах, мультиплексорах, счетчиках и др.) одновременно могут выполняться несколько микроопераций. Настройка ОБ на выполнение одной из возможных микроопераций осуществляется с помощью сигналов, поступающих на его управляющие входы. Набор этих сигналов (вектор сигналов управления) вырабатывается БФУС. Совокупность одновременно выполняемых микроопераций соответствует микрокоманде. Команда в общем случае состоит из нескольких простейших действий и обычно выполняется за несколько тактов, т.е. требует для своего выполнения нескольких микрокоманд. Последовательность микрокоманд, обеспечивающая выполнение команды, называется микропрограммой команды.

Так как выполнение любой команды по тактам на уровне регистровых передач реализуется микропрограммой команды, управляющий автомат, формирующий наборы управляющих сигналов, называют микропрограммным автоматом (МПА). В соответствии с реализуемой логикой управления МПА подразделяют на МПА с «жесткой» логикой управления и МПА с «мягкой» логикой управления. Термин «микропрограммный автомат», вначале использовавшийся только применительно к управляющим автоматам с «мягкой» логикой, с начала 80-х гг. XX в. используется и для автоматов с «жесткой» логикой.

При реализации МПА с «мягкой» логикой управления используется типовая структура автомата с блоком памяти микропрограмм, который, как и основная память, имеет линейно-адресную организацию. До появления технологии СБИС МПА с «мягкой» логикой управления имели преимущественное распространение. В основном это было связано с тем, что при ограниченных возможностях технологии производства ИС и средств автоматизации проектирования МПА с «мягкой» логикой управления позволяли эффективно использовать блоки памяти с регулярной структурой для хранения микропрограмм команд проектируемой системы. Явное представление микропрограмм команд в памяти облегчает внесение изменений в алгоритмы управления. В целом разработка УА МПА с «мягкой» логикой управления в значительной мере определяется разработкой микропрограмм команд. Следует отметить, что использование такого подхода внутри однокристального МП не является предпочтительным, так как приводит к снижению быстродействия. При необходимости изменения команд таких МП вносят изменения в схемные реализации алгоритмов команд, что при развитых средствах автоматизированного проектирования не представляет труда.

МПА с «жесткой» логикой управления представляется в виде конечного автомата (в сложных случаях используется сеть конечных автоматов). Алгоритм команды в МП с подобным МПА задан жестко соединениями схемы, поэтому список операций (система команд) МП является неизменным, и это не позволяет вносить какие-либо изменения в систему команд МП после его изготовления. Основным достоинством МПА с «жесткой» логикой управления является его высокое быстродействие. Такие устройства управления используются в большинстве однокристальных МП, отличительной характеристикой которых является то, что все элементы структуры МП выполнены на одном кристалле.

Число, назначение и разрядность регистров блока РОН в различных МП могут существенно отличаться. В использовании РОН имеются два крайних подхода. При первом подходе, реализуемом в МП компании Motorola, почти все регистры МП выполняют абсолютно одинаковые функции, т.е. являются универсальными и взаимозаменяемыми. При втором подходе, характерном для МП компании Intel, многие регистры наряду с возможностью использования в качестве универсальных в некоторых командах могут выполнять специфические функции, закрепленные за этими регистрами. Специализация регистров при выполнении наиболее часто используемых операций позволяет в соответствующих командах не указывать их адреса, что обеспечивает уменьшение необходимой для управления информации и более компактное кодирование команд. В частности, конкретные регистры МП Pentium используются в командах умножения и деления, управления циклами, ввода-вывода, при табличных преобразованиях, в стековых и сдвиговых операциях. В МП фирмы Zilog используется промежуточный вариант организации блока РОН, в котором часть РОН являются универсальными, а другая часть - многофункциональными.

Микропрограмма (англ. firmware, «прошивка») - программное обеспечение, встроенное («зашитое») в аппаратное устройство. Часто представляется в виде микросхем флеш-ПЗУ или в виде файлов образов микропрограммы, которые могут быть загружены в аппаратное обеспечение.

Под микропрограммой понимается следующее:

· Компьютерная программа, записанная на интегральной микросхеме ПЗУ и управляющая работой аппаратного обеспечения.

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

· Программа по тактам, управляющая ресурсами вычислительного устройства (ALU, сдвигатели, мультиплексоры и др.). Обычно, в командном слове, выделяются отдельные биты для управления необходимым устройством.

· Программа конфигурирования различных ПЛИС (FPGA, CPLD, PAL и т.п.).

Зачастую различные по возможностям и цене приборы отличаются лишь версиями микропрограммы. Для обозначения версии микропрограммы используется номер партии аппаратного обеспечения или другие специализированные идентификаторы, часто смена «прошивки» производится изготовителем без уведомления потребителя.

Микропрограммы («прошивки») применяются везде, где применяются микропроцессоры: в мобильных телефонах, фотоаппаратах, измерительных приборах, телевизорах, платёжных картах и т.д. и т.п.

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

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

Так, для небольших устройств иногда используется FreeRTOS. В последнее время, в связи с удешевлением памяти, достаточно часто применяется GNU/Linux.

Для написания исходных текстов программ используются ассемблеры, язык Си, языки типа Verilog'а для микросхем с программируемой логикой (ПЛИС).

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

В связи с этим фирмы-производители, как правило, очень ревностно следят за сохранностью «прошивок»: лицензионное соглашение с потребителем запрещает извлекать и изучать «прошивки» тем или иным способом:

· самовольная замена «прошивки» на другую («перепрошивка») обычно прекращает действие гарантийных обязательств фирмы;

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

Некоторые фирмы (Microchip, Atmel и др.) производят микропроцессоры со встроенной программируемой памятью такой, что записанная на них программа уже не может быть считана штатными средствами. С другой стороны, фирмы-конкуренты иногда используют для считывания, например, электронные микроскопы

Состояние гонки (англ. race condition) - ошибка программирования многозадачной системы, при которой работа системы зависит от того, в каком порядке выполняются части кода. Название ошибка получила от похожей ошибки проектирования электронных схем (см. Гонки (электроника)).

Состояние гонки - гейзенбаг, проявляющийся в случайные моменты времени и «затихающий» при попытке его локализовать.

Рассмотрим пример кода (на Java)

volatile int x;

 // Поток 1:

while (! stop)

{

x++;

…

}

 // Поток 2:

while (! stop)

{

if (x % 2 == 0)

System.out.println («x=» + x);

…

}

Пусть x=0. Предположим, что выполнение программы происходит в таком порядке:

1. if в потоке 2 проверяет x на чётность.

2. Оператор «x++» в потоке 1 увеличивает x на единицу.

3. Оператор вывода в потоке 2 выводит «x=1», хотя, казалось бы, переменная проверена на чётность.

Самый простой способ решения - копирование переменной x в локальную переменную. Вот исправленный код:

 // Поток 2:

while (! stop)

{

int cached_x = x;

if (cached_x % 2 == 0)

System.out.println («x=» + cached_x);

…

}

Естественно, этот способ работает только тогда, когда переменная одна и копирование производится за одну машинную команду.

Более сложный, но и более универсальный метод решения - синхронизация потоков, а именно:

volatile int x;

 // Поток 1:

while (! stop)

{

synchronized(SomeObject)

{

x++;

}

…

}

 // Поток 2:

while (! stop)

{

synchronized(SomeObject)

{

if (x % 2 == 0)

System.out.println («x=» + x);

}

…

}

Предположим, что переменная x имеет тип не int, а long (на 32-битных ЭВМ её копирование выполняется за две машинных команды), а во втором потоке вместо System.out.println стоит более сложная обработка. В этом случае оба метода неудовлетворительны: первый - потому что x может измениться, пока идет копирование; второй - потому что засинхронизирован слишком большой объём кода.

Эти способы можно скомбинировать, копируя «опасные» переменные в синхронизированном блоке. С одной стороны, это снимет ограничение на одну машинную команду, с другой - позволит избавиться от слишком больших синхроблоков.

volatile long x;

 // Поток 1:

while (! stop)

{

synchronized(SomeObject)

{

x++;

}

…

}

 // Поток 2:

while (! stop)

{

long cached_x;

synchronized (SomeObject)

{

cached_x = x;

}

if (cached_x % 2 == 0)

 //System.out.println («x=» + cached_x);

DoSomethingComplicated (cached_x);

…

}

Очевидных способов выявления и исправления состояний гонки не существует. Лучший способ избавиться от гонок - правильное проектирование многозадачной системы.

Аппарат лучевой терапии Therac-25 был первым в США медицинским аппаратом, в котором вопросы безопасности были возложены исключительно на программное обеспечение. Этот аппарат работал в трёх режимах:

1. Электронная терапия: электронная пушка напрямую облучает пациента; компьютер задаёт энергию электронов от 5 до 25 МэВ.

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

3. В третьем режиме никакого излучения не было. На пути электронов (на случай аварии) располагается стальной отражатель, а излучение имитируется светом. Этот режим применяется для того, чтобы точно навести пучок на больное место.

Эти три режима задавались вращающимся диском, в котором было отверстие с отклоняющими магнитами для электронной терапии, и мишень с рассеивателем для рентгеновской. Из-за состояния гонки между управляющей программой и обработчиком клавиатуры иногда случалось, что в режиме рентгеновской терапии диск оказывался в положении «Электронная терапия», и пациент напрямую облучался пучком электронов в 25 МэВ, что вело к переоблучению. При этом датчики выводили «Нулевая доза», поэтому оператор мог повторить процедуру, усугубляя ситуацию. В результате погибли четыре пациента.

Часть кода была взята из Therac-6 и Therac-20. При этом в Therac-6 не было электронной терапии, а в Therac-20 были аппаратные меры безопасности, которые не давали включить излучение, когда диск в неправильном положении.

Существует класс ошибок (и эксплуатирующих их типов атак), позволяющих непривилегированной программе влиять на работу других программ через возможность изменения общедоступных ресурсов (обычно - времменных файлов; англ. /tmp race - состояние гонки во времменном каталоге), в определённое временноме окно, в которое файл по ошибке программиста доступен для записи всем или части пользователей системы.

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

3. Практическое задание

Для заданной логической функции

где А и В выбраны из таблицы 1, выполнить:

а) Составить таблицу истинности значений заданной функции F (x, y, z, v) = A&B.

б) Выбрать метод минимизации, минимизировать функцию F (привести к МДФ).

в) По МДФ построить комбинационную схему из логических элементов И, ИЛИ, НЕ на ПЭВМ.

г) Из комбинационной схемы определить значения F для всех наборов аргументов, сравнить с результатами, полученными в п. 3, а.

Значения А и В:

Решение

а) Составим таблицу истинности значений заданной функции
F (x, y, z, v) = A&B решение представлено в таблице 1.

б) Выбор метода минимизации, минимизирование функции F (МДФ).

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

Таблица 1 - Таблица истинности значений заданной функции

№	x	y	z	v	A	B	F
1	0	0	0	0	1	1	1
2	0	0	0	1	1	1	1
3	0	0	1	0	1	0	0
4	0	0	1	1	1	0	0
5	0	1	0	0	1	1	1
6	0	1	0	1	1	1	1
7	0	1	1	0	0	0	0
8	0	1	1	1	0	0	0
9	1	0	0	0	1	1	1
10	1	0	0	1	1	1	1
11	1	0	1	0	1	1	1
12	1	0	1	1	1	1	1
13	1	1	0	0	1	1	1
14	1	1	0	1	1	1	1
15	1	1	1	0	1	1	1
16	1	1	1	1	1	1	1

в) По МДФ построим комбинационную схему из логических элементов И, ИЛИ, НЕ на ПЭВМ (при помощи MATLAB R2008a).

Модель представлена на рис. 1



Рис. 1 - Модель функции МДФ

Из результатов работы модели (рис. 2) видно что функция истинна при следующих значениях табл. 2

Рис. 2 - Результаты работы модели

Таблица 1 - Таблица результатов

№	x	z	F
1	0	0	1
2	0	0	1
3	0	1	0
4	0	1	0
5	0	0	1
6	0	0	1
7	0	1	0
8	0	1	0
9	1	0	1
10	1	0	1
11	1	1	1
12	1	1	1
13	1	0	1
14	1	0	1
15	1	1	1
16	1	1	1

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

Рис. 3 - Модель не минимизированной функции



Рис. 4 - Модель Х значений

Рис. 5 - Модель У значений

Рис. 6 - Модель Z значений



Рис. 7 - Модель V значений

Рис. 7 - Модель A значений

Рис. 8 - Модель B значений



Рис. 9 - Модель результатов работы функции

Литература

1. Гультясв А.К. MATLAB 5.2. Имитационное моделирование в среде Windows: Практич. пособ. - Спб.: КОРОНА принт, 1999. - 288 с.

2. Потемкин В.Г. Система инженерных и научных расчетов MATLAB 5.: - В 2-х т. Т. 1. - М.: ДИАЛОГ МИФИ, 1999. - 366 с.

3. Потемкин В.Г. Система MATLAB 5 для студентов. - М: ДИАЛОГ-МИФИ, 1998. - 256 с.

4. Советов Б.Я. Моделирование систем. - М.: Высшая школа, 1985. -379 с.

5. Савельев А.Я. Прикладная теория цифровых автоматов: Учеб. для вузов по спец. ЭВМ. - М.: Высш. шк., 1987. - 272 с: ил.

6. Основы математического моделирования: Учеб. Пособие / А. II. Зелинский. - К.: УМК ВО, 1991.-236 с.