РУБРИКИ

Лекция: Минимизация ФАЛ

 РЕКОМЕНДУЕМ

Главная

Правоохранительные органы

Предпринимательство

Психология

Радиоэлектроника

Режущий инструмент

Коммуникации и связь

Косметология

Криминалистика

Криминология

Криптология

Информатика

Искусство и культура

Масс-медиа и реклама

Математика

Медицина

Религия и мифология

ПОДПИСКА НА ОБНОВЛЕНИЕ

Рассылка рефератов

ПОИСК

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Минимизация ФАЛ Совершенно нормальные формы хотя и дают однозначные представления функции, но являются очень громоздкими. Реализация СНФ программно или схемотехнически является избыточной, что ведет к увеличению программного кода, поэтому существуют методы упрощения логической записи – минимизации. Определение: Преобразование логических функций с целью упрощения их аналитического представления называются минимизацией. Существуют два направления минимизации: 1. Кратчайшая форма записи (цель – минимизировать ранг каждого терма). При этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ. 2. Получение минимальной формы записи (цель – получение минимального числа символов для записи всей функции сразу). При этом следует учесть, что ни один из способов минимизации не универсален! Существуют различные методы минимизации: 1. Метод непосредственных преобразований логических функций. (1.1) При применении данного метода: а) Записываются ДСНФ логических функций б) Форма преобразуется и упрощается с использованием аксиом алгебры логики. При этом, в частности, выявляются в исходном ДСНФ так называемые соседние min-термы, в которых есть по одной не совпадающей переменной. Лекция: Минимизация ФАЛ По отношению к соседним min-термам применяется закон склейки, значит ранг min-терма понижается на единицу. Определение: Min-термы, образованные при склеивании называются импликантами. Полученные после склейки импликанты по возможности склеивают до тех пор, пока склеивание становится невозможным. Определение: Несклеивающиеся импликанты называются прослойками. Определение: Формула, состоящая из простых импликант – тупиковая. Пример:

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

0001
0011
0101
0111
1000
1010
1100
1110
Если в процессе склейки образуется форма R, содержащая члены вида Лекция: Минимизация ФАЛ и Лекция: Минимизация ФАЛ то для нее справедливо выражение Лекция: Минимизация ФАЛ , что позволяет добавить к исходной форме R несколько членов вида пар Лекция: Минимизация ФАЛ и Лекция: Минимизация ФАЛ и после этого продолжить минимизацию. Пример: Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Мы получили минимальную СНФ. Метод неопределенных коэффициентов. (1.2) Суть метода состоит в преобразовании ДСНФ в МДНФ. На основании теоремы Жигалкина любую ФАЛ можно представить в виде (рассмотрим на примере трех переменных): Лекция: Минимизация ФАЛ Алгоритм определения коэффициентов: 1. Исходное уравнение разбить на систему уравнений, равных числу строк в таблице истинности. 2. Напротив каждого выражения поставить соответствующее значение функции. 3. Выбрать строку, в которой значение функции Лекция: Минимизация ФАЛ и приравнять все Лекция: Минимизация ФАЛ к нулю. 4. Просмотреть строки, где функция имеет единичное значение, и вычеркнуть все коэффициенты, встречающиеся в нулевых строках. 5. Проанализировать оставшиеся коэффициенты в единичных строках. 6. Используя правило, что дизъюнкция равна 1 если хотя бы один из Лекция: Минимизация ФАЛ , выбрать min-термы минимального ранга. Причем отдавать предпочтение коэффициентам, встречающимся в нескольких уравнениях одновременно. 7. Записать исходный вид функции. Метод неопределенных коэффициентов применим для дизъюнктивной формы и непригоден для конъюнктивной. Пример: Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

00000000000001
10010001010010
20100100100101
30110101110110
41001010001001
51011011011010
61101110101100
71111111111111
Лекция: Минимизация ФАЛ Итак, получим Лекция: Минимизация ФАЛ Метод Квайна (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.

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

VV

Лекция: Минимизация ФАЛ

VV

Лекция: Минимизация ФАЛ

VV

Лекция: Минимизация ФАЛ

VV

Лекция: Минимизация ФАЛ

VV

Лекция: Минимизация ФАЛ

VVVV
Шаг 4 пропускаем. Шаг 5. Выбираем те min-термы, при записи которых, МДНФ функции минимальна. Шаг 6. Лекция: Минимизация ФАЛ Недостаток метода Квайна – необходимость полного по парного сравнения всех min-термов на этапе нахождения первичных импликант. Идея модификации метода Квайна – метод Квайна-Мак-Класки. (1.4) 1. Каждая конъюнкция в ДСНФ представляется своим двоичным набором. 2. Вся совокупность номеров наборов разбивается на группы в зависимости от числа единиц, имеющихся в номерах наборов (0-группа, 1-группа, 2-группа и.т.д.). 3. Сравниваются две группы, отличающиеся на одну единицу. 4. В результате сравнения в номере набора, имеющего большее число единиц на позиции, где обнаружится разница на одну единицу ставится прочерк. 5. В процессе преобразования возникают новые сочетания (n-группы). 6. Процесс преобразования длится до тех пор, пока возможна операция склеивания. 7. Элементы преобразованных групп являются первичными импликантами, которые вместе с номерами исходных наборов образуют таблицы разметок. 8. В остальном эти методы совпадают с единственным уточнением – если в результате таблицы разметок ни одна из строк не покрывает единицу столбца, то надо выбрать номер столбца набора из предыдущей группы преобразований. Определение: n-группа – это такой набор аргументов функции, что число всех аргументов равных единице равно n, причем значении функции равно 1. Пример: Лекция: Минимизация ФАЛ Составим таблицу истинности:

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

00001
00011
00101
00111
01001
01011
01101
01111
10001
10011
10100
10111
11000
11010
11100
11111
Запишем 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:
000000010010001101000101011001111000100110111111
VVVVVVVV0---
Выделим минимальное число групп, покрывающих Для проверки составим таблицу истинности
1000100110111111
-00-VV
-0-1VV
-111VV
Метод минимизирующих карт (для ДСНФ и КСНФ). (1.5) Одним из способов графического представления булевых функций от небольшого числа переменных являются карты Карно. Их разновидность – карты Вейча, которые строятся как развертки кубов на плоскости, при этом вершины куба представляются клетками карты, координаты которых совпадают с координатами соответствующих вершин куба. Для ДСНФ единицы ставятся в клетке, соответствующей номеру набора, на котором значение функции равно единице, а ноль не ставится, а для КСНФ – наоборот. Диаграмма для двух логических переменных (для ДСНФ): Лекция: Минимизация ФАЛ Для трех переменных: Лекция: Минимизация ФАЛ Карты Карно используются для ручной минимизации функций алгебры логики при небольшом количестве переменных. Правило минимизации: склеиванию подвергаются 2,4,8,16,Лекция: Минимизация ФАЛ клеток и клетки, лежащие на границе карты. При числе переменных 5 и больше отобразить графически функцию в виде единой плоской карты невозможно. Тогда строят комбинированные карты, состоящие из совокупности более простых карт. Процедура минимизации заключается тогда в том, что сначала находится минимальная форма 4-х мерных кубов (карт), а затем, расширяя понятие соседних клеток, отыскивают min-термы для совокупности карт. Причем соседними клетками являются клетки, совпадающие при совмещении карт поворотом вокруг общего ребра.

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

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

Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

11

Лекция: Минимизация ФАЛ

1
Лекция: Минимизация ФАЛ Минимизировать функцию: Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ

111

Лекция: Минимизация ФАЛ

1

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ Минимизация логических функций, заданных в базисе Лекция: Минимизация ФАЛ . Метод неопределенных коэфициентов применим для минимизации функций, заданных в различных базисах. Пусть функция Лекция: Минимизация ФАЛ является ПСНФ, операция Лекция: Минимизация ФАЛ имеет особенности, отличающие ее от операции дизъюнкции. 1)Лекция: Минимизация ФАЛ 2)Лекция: Минимизация ФАЛ 3) Лекция: Минимизация ФАЛ Минимизация при этом усложняется, так как ее основными критериями являются минимальные ранги каждого терма и их минимальное количество, при этом в ходе минимизации в базисе Лекция: Минимизация ФАЛ нецелесообразно приравнивать к нулю все коэффициенты на наборах где Лекция: Минимизация ФАЛ , т.к. в наборах, где функция Лекция: Минимизация ФАЛ могут остаться термы высокого ранга. Поэтому особой разницы между выбором нулевого или единичного значения функции нет. Количество коэффициентов, остающихся в нулевых строках должно быть четным, а в единичных – нечетным. Лучше всего рассматривать единичные строки и оставлять те коэффициенты минимального ранга, которые чаще всего повторяются в этих строках. В общем случае для получения минимальной формы выполняют следующие действия: 1) Подсчитывают, сколько раз в единичных строках встречаются термы первого ранга и оставляют из них те, которые встречаются максимальное число раз. 2) Находят нулевые строки, в которых встречаются оставленные в первом шаге термы и их не обнуляют. 3) Рассматривая нулевую строку, в которой остался одни единичные термы и находят в ней еще единичный терм, встречающийся максимальное число раз в единичных строках, в которых еще не было оставлено ни одного терма и.т.д. Метод Квайна-Мак-Класки может быть применим при минимизации этого базиса, при этом кроме эффективных значений функции, где Лекция: Минимизация ФАЛ включаются некоторые min-термы, где Лекция: Минимизация ФАЛ . Метод Квайна-Мак-Класки применим для минимизации базисов стрелки пирса и штриха Шеффера. Не полностью определенные ФАЛ (1.6) Определение: не полностью определенные ФАЛ от n переменных называется функции, заданные на множестве наборов меньше чем Лекция: Минимизация ФАЛ . Если количество неопределенных наборов равно m то путем различных доопределений можно получить Лекция: Минимизация ФАЛ различных функций. Пример: доопределить функцию Лекция: Минимизация ФАЛ Где символ * означает "может быть". Доопределим *=0 1)Лекция: Минимизация ФАЛ Доопределим *=1 2) Лекция: Минимизация ФАЛ Если доопределять *=0 или *=1 то получим минимальный вариант: 3)Лекция: Минимизация ФАЛ Пример показывает, что доопределение функции существенно влияет на конечный результат минимизации. При доопределении Лекция: Минимизация ФАЛ можно руководствоваться правилом: МДНФ не полностью определенных функций получается как дизъюнкция наиболее коротких по числу букв импликант функции Лекция: Минимизация ФАЛ на всех наборах и функциях, которые в совокупности покрывают все импликативные СНФ, и Лекция: Минимизация ФАЛ на всех наборах, где функция не определена. Пример: найти минимальную форму для Лекция: Минимизация ФАЛ Составим таблицу истинности:

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

00001
0001*
0010*
00110
0100*
01010
01101
0111*
1000*
10011
10100
1011*
11000
1101*
11101
1111*
1) доопрделим *=1 и получим минимальный вид функцииЛекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Доопрделим *=0 Лекция: Минимизация ФАЛ Оптимальное доопрделение функций соответствующее минимальному покрытию может быть найдено по методу Квайна.

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

V

Лекция: Минимизация ФАЛ

VV

Лекция: Минимизация ФАЛ

VV

Лекция: Минимизация ФАЛ

V
В результате получится минимальный вид функции вида: Лекция: Минимизация ФАЛ ее таблица единичных значений тогда будет: Лекция: Минимизация ФАЛ Временные булевы функции. (1.7) Определение: Временная булева функция – логическая функция вида Лекция: Минимизация ФАЛ , принимающая значение единицы при Лекция: Минимизация ФАЛ , где s – дискретное целочисленное значение, называемое автоматическим временем. Утверждение: число различных временных булевых функций равно Лекция: Минимизация ФАЛ . Доказательство: если функция времени принимает n значений Лекция: Минимизация ФАЛ и на каждом интервале времени t соответствует Лекция: Минимизация ФАЛ единичных наборов, то всего получится Лекция: Минимизация ФАЛ наборов, значит число временных булевых функций равно Лекция: Минимизация ФАЛ . Любая временная булева функция может быть представлена в виде Лекция: Минимизация ФАЛ Где Лекция: Минимизация ФАЛ - конъюнктивный или дизъюнктивный терм, а Лекция: Минимизация ФАЛ равно 0 или 1 в зависимости от времени t. Форма представления временных булевых функций позволяет применить все метды минимизации. Пример:

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

0000
0100
1001
1100
0010
0111
1011
1110
0020
0120
1021
1121
Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Временные булевы функции применяются для описания работы схем с памятью. Определение: Производной первого порядка от булевой функции Лекция: Минимизация ФАЛ по переменной Лекция: Минимизация ФАЛ называется выражение: Лекция: Минимизация ФАЛ Где первая Лекция: Минимизация ФАЛ - единичная остаточная функция, а вторая- нулевая остаточная функция. Пример: Лекция: Минимизация ФАЛ после минимизации получим: Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ производная первого порядка по Лекция: Минимизация ФАЛ переменной определяет условие, при котором эта функция изменяет свое значение при перемене значения Лекция: Минимизация ФАЛ с 0 на 1. Для данной функции получим схему: Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ ---Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Смешанные производные k-го порядка. Определение: смешанной производной k-го порядка называется выражение вида: Лекция: Минимизация ФАЛ При этом порядок фиксированной переменной не имеет значения. Производная k-го порядка Лекция: Минимизация ФАЛ определяет условия, при которых эта функция изменяет свое значение при одновременном изменении значений Лекция: Минимизация ФАЛ . Согласно Бохману, производная k-го порядка вычисляется по формуле: Пример: определить условия переключения выходного канала функции Лекция: Минимизация ФАЛ при переключении каждого канала, первого и второго канала, всех каналов одновременно. 1)Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Понятие производной от булевых функций используется для синтеза логических схем, а также в теории надежности. Приложение алгебры логики. (1.8) 1) Для решения логических задач, - суть в том, что имея конкретные условия логической задачи стараются записать их в виде ФАЛ, которые затем минимизируют. Простейший вид формуды, как правило, приводят к ответу на задачу. Задача: По подозрению в преступлению задержаны: Браун, Джон и Смит. Один – старик, другой – чиновник, третий – мошенник). Все они дали показания, причем: старик всегда говорил правду, мошенник всегда лгал, а чиновник иногда лгал, а иногда говорил правду. Показания: Браун – Я совершил это, Джон не виноват. Джон – Браун не виноват, это сделал Смит. Смит – я не виноват, виновен Браун. На основании этого условия определить, кто из них совершил преступление, и кто старик, кто мошенник и кто чиновник. Обозначим буквами: Б- виноват Браун Д – виноват Джон С – виноват Смит Тогда показания запишутся в виде: Лекция: Минимизация ФАЛ Тогда запишем функцию: Лекция: Минимизация ФАЛ Запишем ее таблицу истинности и вычеркнем некоторые не подходящие наборы (2 преступника одновременно и.т.д.)
БДС

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

L
10000000

Лекция: Минимизация ФАЛ 2

0010101
30100000

4

0110101

5

1001011

6

1011001

7

1100011
81110000
Значит Браун – чиновник, Джон – старик, Смит – мошенник, он же преступник. 2) Среди технических средств автоматизации (релейно-контактные системы). Значительное место занимают РКС, используемые в вычислительной технике. РКС – переключательные схемы. В 1910 г. физик Эрнфест указал на возможность применения алгебры логики при исследовании РКС. Его идея заключается в том, что каждой схеме можно сопоставить ФАЛ и наоборот. Это позволяет выявить возможности схемы, изучая соответствующую формулу, а упрощение схемы свести к упрощению ФАЛ – анализ переключательной схемы. Синтез переключательной схемы (до построения схемы можно описать ее работу с помощью логической функции). Рассмотрим связь между переключательными схемами и ФАЛ. (1.8.1) Определение: переключательная схема – схемотехническое изображение устройства, состоящее из следующих элементов: 1) переключатель (может быть разомкнут или замкнут) 2) проводники 3) вход в схему и выход из нее
P
Примеры: а) А В
Лекция: Минимизация ФАЛ
Q
б) Дизъюнкция: А В
P
Q
в) Импликация: А В
P
P
г) Тождественно ложно: А В
Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

д) Тождественно истинно: А В
Из схем а,б,в можно получить функцию алгебры логики.
Лекция: Минимизация ФАЛ
Z
X
А Б
Лекция: Минимизация ФАЛ
Лекция: Минимизация ФАЛ
Лекция: Минимизация ФАЛ
X
После упрощения получим:
Лекция: Минимизация ФАЛ
Y
X
А 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
Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ
Лекция: Минимизация ФАЛ
Лекция: Минимизация ФАЛ
Лекция: Минимизация ФАЛ
1
Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ После упрощения получим:
&
Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ
1
Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Синтез электронных схем (1.8.3) Задачу синтеза электронных схем можно сформулировать следующим образом: при заданных входных переменных и известной выходной функции, спроектировать логическое устройство, которое реализует эту функцию. При этом могут быть наложены дополнительные ограничения либо в виде системы логических элементов, либо по количеству логических операторов и.т.д. Обычно, решая задачи анализа и синтеза, используют полные базисы функций. При этом, любую логическую функцию, входящую в базис, сопоставляют с некоторым физическим элементом, в результате логическую схему можно заменить принципиальной схемой, состоящей из физических элементов. Таким образом удается соединить математическую задачу синтеза логической схемы с инженерной задачей проектирования электронной схемы. При разработке электронной схемы за основные критерии принимают минимум аппаратуры, минимум типов применяемых элементов и максимум надежности. С точки зрения математической логики, задачи синтеза решаются при обеспечении минимального числа логических операторов, минимального количества типов логических операторов. В общем случае при синтезе электронной схемы соблюдается следующая последовательность: 1) сопоставление математического описания, адекватно отображающего процессы, происходящие в схеме (система логических уравнений). 2) анализ логических уравнений и получение минимальной формы для каждого из них в заданном базисе. 3) переход от логических уравнений к логической схеме, посредством применения логических операторов. Электронные схемы с одним выходом. Это наиболее простые схемы, основная сложность при синтезе этих схем – найти выражение для выходной функции в заданном базисе. Пример: Лекция: Минимизация ФАЛ Типы логических элементов Лекция: Минимизация ФАЛ Надо привести в базис импликации Лекция: Минимизация ФАЛ Т.к. Лекция: Минимизация ФАЛ , то Лекция: Минимизация ФАЛ Тогда получим схему:
Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

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

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

00000
00110
01010
01101
10010
10101
11001
11111
Где Лекция: Минимизация ФАЛ - переменные, Лекция: Минимизация ФАЛ - сумма в Лекция: Минимизация ФАЛ -ом разряде, Лекция: Минимизация ФАЛ - перенос из младшего разряда в старший, Лекция: Минимизация ФАЛ - перенос из старшего разряда. Составим ДСНФ: Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

11

Лекция: Минимизация ФАЛ

11

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ

111

Лекция: Минимизация ФАЛ

1

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Тогда Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ
1
&
1
1
1
1
&
Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ
1
&
Ci

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ Пi Такой способ не очень хорош, так как не всегда оптимален. Электронные схемы с несколькими выходами (1.8.4) Пусть n входов и k выходов. Классический пример таких схем – дешифратор Входы Выходы

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

Лекция: Минимизация ФАЛ

00010000000
00101000000
01000100000
01100010000
10000001000
10100000100
11000000010
11100000001
Причем, например Лекция: Минимизация ФАЛ , а Лекция: Минимизация ФАЛ и.т.д. Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ
&
&
1
y0
Лекция: Минимизация ФАЛ
Лекция: Минимизация ФАЛ
Лекция: Минимизация ФАЛ
&
&
y7 Лекция: Минимизация ФАЛ Несложно убедиться, что такой подход не является оптимальным, поэтому рассмотрим следующие моменты синтеза схем: 1) Классический основан на выделении простых импликант заданной системы функций, подобно тому, как это делается в методе минимизации Квайна-Мак- Класки, а затем ищется покрытие заданной функции этими импликантами. При этом требуется: 1) найти простые импликанты заданной системы функций 2) выразить каждую функцию через простые импликанты 3) синтезировать схему, включающую только эти импликанты и связи между ними Пример: синтезировать схему в базисе Лекция: Минимизация ФАЛ , функции которой на выходе имеют следующий вид: Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Решение: разобьем Лекция: Минимизация ФАЛ на группы, соответствующие по количеству единиц: Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ
1
&
1
Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ y2
Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ
Лекция: Минимизация ФАЛ
1
&
1
Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ y1
Лекция: Минимизация ФАЛ
Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Метод каскадов (1.8.5) Этот метод основан на разложении ФАЛ на k переменных: Лекция: Минимизация ФАЛ Где kЛекция: Минимизация ФАЛ n Эта формула попеременно применяется к заданной функции столько раз, чтобы получить простое логическое выражение, которое легко синтезировать. Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ Лекция: Минимизация ФАЛ . . . и.т.д. Построенная на основе этих выражений логическая схема на каждом этапе образует последний каскад искомой комбинационной схемы.


© 2010
Частичное или полное использование материалов
запрещено.