Практическое занятие №7 Минимизация логического автомата

Краткие теоретические сведения

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

Карты Карно
Карта Карно́ — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба.
Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.
В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.
/22

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

На рисунке 1 изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов.
Возможность поглощения следует из очевидных равенств:
Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов.
Рисунок 1
/22

В случае функции трёх переменных приходится иметь дело с трёхмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке 2 в качестве примера показана таблица истинности для булевой функции трёх переменных и соответствующий ей куб.
Рисунок 2
Как видно из рисунка 2, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:
/22

В общем случае можно сказать, что 2K термов, принадлежащие одной K–мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются K переменных.
Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано на рисунке 3. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел, а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой
Рисунок 3
/22

Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для N=4 и N=5 приведены на рисунке 4. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х4 виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4 являются соседними, и соответствующие им термы можно склеивать.
Рисунок 4
/22

Описание
1. Объединяем смежные клетки содержащие единицы в область, так чтобы одна область содержала 2n (n целое число = 0… ) клеток(помним про то что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток содержащих нули;
2. Область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);
3. Не смежные области расположенные симметрично оси(ей) могут объединяться в одну;
4. Область должна быть как можно больше, а кол-во областей как можно меньше;
5. Области могут пересекаться;
6. Возможно несколько вариантов накрытия.
Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности, составленная в 2-х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т.о. вся Карта Карно сворачивается в фигуру тор (бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации.
Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки, которые содержат единицы, если нужна КНФ, то рассматриваем те клетки, которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ):
/22

Далее берём первую область и смотрим какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных, если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией. Например, для Карт на две переменные (рисунок 5 и 6):
Рисунок 5
Рисунок 6
/22

Примеры решения типовых задач

Пример 1
У мальчика Коли есть мама, папа, дедушка и бабушка. Коля пойдёт гулять на улицу, если ему разрешат хотя бы двое родственников.
Решение:
1) Для краткости обозначим родственников Коли через буквы (рисунок 7):
Рисунок 7
Условимся обозначать согласие родственников единицей, не согласие нулём. Возможность пойти погулять обозначим буквой f, Коля идёт гулять — f = 1, Коля гулять не идёт — f = 0.
2) Составим таблицу истинности (Рисунок 8):
Рисунок 8
/22

3) Перерисуем таблицу истинности в 2-х мерный вид (рисунок 9):
4) Переставим в ней строки и столбцы в соответствии с кодом Грея. Получили Карту Карно (рисунок 10):
5) Заполним её значениями из таблицы истинности (рисунок 11):
Рисунок 9
Рисунок 10
Рисунок 11
/22

1. Все области содержат 2^n клеток;
2. Так как Карта Карно на четыре переменные оси располагаются на границах Карты и их не видно;
3. Так как Карта Карно на четыре переменные все области симметрично осей — смежные между собой;
4. Области S3, S4, S5, S6 максимально большие;
5. Все области пересекаются (не обязательное условие);
6. В данном случае рациональный вариант только один
6) Минимизируем в соответствии с правилами (рисунок 12):
Рисунок 12
/22

7) Теперь по полученной минимальной ДНФ можно построить логическую схему (рисунок 13). Из за отсутствия в наличии шести-входового элемента ИЛИ, реализующего функцию дизъюнкции, пришлось каскадировать пяти- и двух-входовые элементы (D7, D8).
Рисунок 13
8) Составим мин. КНФ (рисунок 14):
Рисунок 14
9) Строим логическую схему по полученной минимальной КНФ (рисунок 15):
Рисунок 15
/22

Пример 2
По таблице истинности (рисунок 16) составить булево выражение в СДНФ, минимизировать это выражение с помощью карты Карно, нарисовать логическую схему, реализующую минимизированное булево выражение.
Рисунок 16
Решение:
1) Составим логическое выражение в СДНФ:
/22

2) Составим карту Карно для четырех переменных (рисунок 17):
Рисунок 17
Ячейки, в которых функция равна единице, объединены в три группы. В группе 1 результат не зависит от значения переменной А, во второй — тоже от переменной А, в третьей, объединяющей четыре ячейки, результат не зависит от переменных В и D.
3) Результат минимизации будет выглядеть следующим образом:
Данное логическое выражение является тупиковым.
4) Строим логическую схему (Рисунок 18):
Рисунок 18
/22

Пример 3
Требуется минимизировать функцию четырех переменных, карта Карно которой представлена на рисунке 19.
Рисунок 19
Решение:
1) Проводим два контура второго ранга и получаем:
2) Находим цену схемы:
3) Можно в карте Карно объединить нули, но при этом получаем инверсную функцию:
/22

4) Здесь проведены два куба — третьего и второго ранга. Цена схемы получается меньше:
5) Ее реализация на произвольных элементах имеет вид, показанный на рисунке 20:
Рисунок 20
6) Отрицание можно перенести в правую часть, что не отражается на цене:
Вывод: чем меньше цена, тем лучше. Поэтому минимизировать по карте Карно следует и по единицам, и по пулям. К реализации принимают формулу с наименьшей ценой.
/22

Задачи для самостоятельной работы
1-4. Записать минимальную форму в КНФ и в ДНФ:
5. По таблице истинности восстановите логическое выражение (рисунок 21).
Рисунок 21
6. Упростите следующее логическое выражение.
7. Составьте ДНФ по данной карте Карно (рисунок 22).
Рисунок 22
/22