40163

МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ УСТРОЙСТВ

Лекция

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

Минимизация с применением карт Вейча Карты Вейча – это прямоугольная таблица число клеток в которой для ФАЛ n – переменных равно 2n каждой из клеток поставлен в соответствие набор входных переменных причем рядом расположенным клеткам соответствуют соседние наборы входных переменных а в самих клетках записаны значения функции определенные для этих кодов. На карте Вейча ФАЛ n – переменных выделяют прямоугольные области объединяющие выбранные значения функции 0 или 1. Каждой из выделенных областей соответствует k – куб исходной ФАЛ...

Русский

2013-10-15

518 KB

17 чел.

9 МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ УСТРОЙСТВ

Цель минимизации – уменьшение стоимости ее технической реализации и повышения надежности.

Минимизация с применением карт Вейча

Карты Вейча – это прямоугольная таблица, число клеток в которой для ФАЛ n – переменных равно 2n , каждой из клеток поставлен в соответствие набор входных переменных, причем рядом расположенным клеткам соответствуют соседние наборы входных переменных, а в самих клетках записаны значения функции , определенные для этих кодов. Карты Вейча применяются для минимизации функций до 5 переменных (рис. 9.1).

    а)                                       б)                                                    в)

Рис.9.1 Карта Вейча для 2-х переменных (а);

Карта Вейча для 3-х переменных (б); Карта Вейча для 4-х переменных (в)

9.1 Правила минимизации

Осуществляют минимизацию по 0 или 1.

  1.  На карте Вейча ФАЛ n – переменных выделяют прямоугольные области, объединяющие выбранные значения функции (0 или 1). Каждая область должна содержать 2к клеток, где к – целое число.  Выделенные области могут пересекаться, т.е. одна или несколько клеток могут включаться в различные области.
  2.  Каждой из выделенных областей соответствует k – куб исходной ФАЛ, который представляется самостоятельным логическим произведением переменных, значения которых в рамках выделенной области остаются постоянными. Каждое произведение содержит nk переменных и носит название импликанты.
  3.  Из полученного множества выбирают минимальное число максимально больших областей, включающих все выбранные значения ФАЛ.
  4.  Логически суммируют импликанты, соответствующие выбранным областям. Полученная сумма образует МДНФ, т.е. является покрытием ФАЛ минимальной стоимости (покрытием квайна).

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

Пример: Минимизировать ФАЛ

1) По заданной ФАЛ составим карту Вейча (рис. 9.2).

        Запишем кубические комплексы К0=(111,101,110,100); К1=(1-1, 1-0,11-,10-); К2=(1--).

  1.  Выделим покрытия и запишем соответствующие им МДНФ:

П1=(1-1,1-0)  z(x)=x2x0+x2 ; П2=(11-,10-) ;

П3=(1--)  z(x)=x2

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

При объединении нулевых значений функции максимальная область соответствует 2 – куб (0--), для которого  или . В обоих случаях для минимальной ФАЛ получено одно и то же выражение.

9.1.1 Минимизация недоопределенной ФАЛ

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

9.2 Минимизация системы ФАЛ

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

Пример: Минимизировать структуру устройства, алгоритм которого задан таблицей истинности (табл. 9.2).

Минимизируем ФАЛ по каждому выходу отдельно, составляем карту Вейча (рис. 9.3).

Используя карты Вейча получаем систему минимальных ФАЛ. ;  ; .

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

9.3 Минимизация ФАЛ на ЭВМ методом Квайна и Мак – Класки

При увеличении числа переменных для минимизации ФАЛ используются методы, обладающие однозначностью алгоритма это необходимо для применения ЭВМ. Метод Квайна и Мак – Класки заключается следующим:

  1.  находят покрытие П(z) заданной функции. Для этого формируют кубический комплекс ФАЛ и в каждом i – м кубическом комплексе отмечают кубы (импликанты), не образовавшие i+1 – й кубический комплекс. Отмеченные импликанты, называемые простыми, образуют покрытие заданной ФАЛ;
  2.  строят таблицу покрытий матрицы Квайна. Строки указанной таблицы соответствуют простым импликантам, а столбцы 0 – кубам (конституентам единицы) ФАЛ. На пересечении i – ой строки и j – го столбца ставится метка, если импликанта  i покрывает конституенту j;
  3.  определяют покрытие минимальной стоимости:

а) выделяют ядро Квайна. Если 0 – куб заданной ФАЛ покрывается только одной простой импликантой, то последняя является существенной и входит в ядро Квайна и, следовательно, покрытие минимальной стоимости;

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

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

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

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

Пример: минимизировать ФАЛ z(x)=V(0,1,2,4,5,7,8,10,12,14,15).

Решение: цена покрытия исходной ФАЛ Цп=44Ф

               1 Сформируем кубический комплекс К(z).Фомирование кубическогокомплекса К(z) выполняется при помощи разбиения коституент ФАЛ на группы, содержащие одинаковое число единиц. В данном примере для ФАЛ четырех переменных можно выделить пять групп в виде таблиц (табл. 9.3).

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

2 Кубы не образовавшие куб более высокого ранга, являются простыми импликантами и формируют покрытие ФАЛ П(z)=(01-1,-111,111-,0-0-,--00,-0-0,1--0).

3 С использованием П(z) построим таблицу покрытий Квайна.

4 Согласно полученной таблицы простыми импликантами являются 0-0- и –0-0, т.к. только первая покрывает 0- куб 0001 и только вторая покрывает 0- куб 0010.

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

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

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

6 Просуммировав импликанты циклической таблицы и простые импликанты, получим ФАЛ минимальной стоимости .

Алгоритм сжатия по строкам и столбцам можно пояснить следующим образом. Из множества импликант, полученных после исключения существенных, необходимо найти такое их минимальное подмножество, которое обеспечит покрытие всех оставшихся в таблицы конституент единицы. Поэтому, если существует i-я импликанта, которая покрывает множество 0- кубов Vi, которая включает множество кубов Vj, покрываемое импликанты j, то импликанта j является лишней. По этим правилам можно минимизировать ФАЛ любого числа переменных, особенно эффективно с применением ЭВМ.

9.4 Минимизация ФАЛ с помощью карт Карно

Это графический метод для минимизации логических функций с числом переменных << 6.

СДНФ: .

С помощью преобразования алгебры логики, получено минимизированное выражение МДНФ:

.   Первый член МДНФ соответствует объединению клеток 1 (рис. 9.4).

Все клетки объединения 2 соответствуют минтермам, которые имеют одну общую переменную. Дизъюнкция этих минтермов, как показано выше, также равна, т.е. второй член МДНФ соответствует объединению 2 на рисунке.

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

PAGE  81

Рис.9.4  Карты Карно

Рис. 9.3 Минимизация по выходу Z0 (а); Минимизация по выходу Z1 (б);

Минимизация по выходу Z2 (в)

в)

б)

  а)

EMBED Рисунок AutoCAD 14  

EMBED Рисунок AutoCAD 14  

EMBED Рисунок AutoCAD 14  

EMBED Рисунок AutoCAD 14  

EMBED Рисунок AutoCAD 14  

EMBED Рисунок AutoCAD 14  

EMBED Рисунок AutoCAD 14  

EMBED Рисунок AutoCAD 14  

EMBED Рисунок AutoCAD 14  

Таблица 9.3 Таблица формирования кубического комплекса К(z)

EMBED Рисунок AutoCAD 14  

EMBED Рисунок AutoCAD 14  

EMBED Рисунок AutoCAD 14  

Таблица 9.5 Таблица покрытий Квайна

Таблица 9.4 Таблица покрытий Квайна

EMBED Рисунок AutoCAD 14  

Таблица  9.2  Таблица истинности

Таблица 9.1 Таблица

истинности

Рис. 9.2 Карта Вейча


 

А также другие работы, которые могут Вас заинтересовать

9898. Вторая вариация и достаточные условия экстремума 178 KB
  Вторая вариация и достаточные условия экстремума Вспоминая о глубокой аналогии между дифференциальным и вариационным исчислениями, естественно ожидать, что при переходе к достаточным условиям экстремума функционалов будет введено понятие, иг...
9899. Классификация задач оптимизации 70 KB
  Классификация задач оптимизации оптимизируемая функция (целевая функция, целевой функционал, критерий качества и т.п.), численно выражает степень достижения целей функционирования оптимизиру...
9900. Динамическая оптимизация 97 KB
  Динамическая оптимизация Статическая задача распределения ограниченных ресурсов для достижения комплекса конкурирующих целей в некоторый определенный момент времени математически формализуется в виде математической задачи выбора из заданного до...
9901. Динамическое программирование 224 KB
  Динамическое программирование Динамическое программирование является еще одним из двух современных направлений в теории задач управления. Метод динамического управления может применяться непосредственно при решении общей задачи управления...
9902. Линейное программирование 383.5 KB
  Линейное программирование Линейное программирование (ЛП) - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения 1930 г., А.Н. Толстой - составление оптим...
9903. Симплекс-метод решения задач ЛП 86.5 KB
  Симплекс-метод решения задач ЛП Симплекс-метод предложен Дж. Данцигом в 1947 г. непосредственно применяется к общей задаче ЛП в канонической форме: Z = CTX min, при ограничениях X0, AX = B, B > 0, Любое неотрицательное решение...
9904. Двойственность в линейном программировании 47 KB
  Двойственность в линейном программировании Для любой задачи ЛП можно сформулировать двойственную задачу, являющуюся зеркальным отражением исходной задачи, т.к. она использует те же параметры, а ее решение может быть получено одновременно с решение...
9905. Нелинейное программирование 80.5 KB
  Нелинейное программирование § 1. Общая задача нелинейного программирования Как известно, общая задача математического программирования формулируется следующим образом: найти вектор Х=(х1, х2, ..., хn) удовлетворяющий системе ограничений gi (х1, х2, ...
9906. Принцип максимума. Классификация задач оптимального управления динамическими системами 106.5 KB
  Принцип максимума Вторым направлением в теории решения задач управления является принцип максимума. Это метод в отличие от классического вариационного исчисления позволяет решать задачи управления, в которых на управляющие параметры наложены весьма ...