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 Карта Вейча


 

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

19895. Провадження у справах про злочини неповнолітніх 41.7 KB
  ТЕМА 21: Провадження у справах про злочини неповнолітніх План 1. Особливості провадження у кримінальних справах про злочини неповнолітніх. 2. Предмет доказування у справах про злочини неповнолітніх. 3. Особливості провадження досудового і судового слідства у справах ...
19896. Поняття і система інвестиційного права 78 KB
  Лекція № 1. Тема : Поняття і система інвестиційного права. Мета: Ознайомлення студентів з поняттям функціями та системою інвестиційного права місцем інвестиційного права в системі права України. План 1. Місце інвестиційного права в системі права України. 2. По...
19897. Поняття інвестиційної діяльності 104.5 KB
  Лекція № 2. Тема 2: Поняття інвестиційної діяльності Мета: ознайомлення студентів з основами інвестиційної діяльності структурою інвестиційної діяльності поняттям інвестиційного клімату держави План 1. Поняття та класифікація інвестицій. Поняття інвестицій
19898. Правове регулювання фінансових інвестицій 97 KB
  Лекція № 3. Тема : Правове регулювання фінансових інвестицій. Мета: ознайомлення студентів з поняттям фінансові інвестиції основними цінними паперами основами управління інвестиційним портфелем План 1. Загальна характеристика фондового ринку в Україні. 2. Пра
19899. Субєкти інвестиційної діяльності 99 KB
  Лекція № 4. Тема 4: Суб'єкти інвестиційної діяльності. Мета: вивчення кола суб’єктів інвестиційної діяльності форми діяльності суб'єктів інвестиційної діяльності. План 1. Держава як суб'єкт інвестиційної діяльності. 2. Інвестиційний фонд компанія та довірчі то
19900. Інноваційна форма інвестицій 73 KB
  Лекція № 5. Тема 5: Інноваційна форма інвестицій. Мета: ознайомлення з поняттям інноваційної діяльності венчурного підприємства стадіями інноваційної діяльності. План 1. Поняття й зміст інновацій. Інноваційна діяльність. 2. Венчурне підприємство. Стадії іннов...
19901. Організаційно-правові форми регулювання взаємодії суб'єктів інвестиційної діяльності 61 KB
  Лекція № 6. Тема 6 : Організаційноправові форми регулювання взаємодії суб'єктів інвестиційної діяльності. Мета: ознайомлення студентів з поняттям та формами регулювання взаємодії суб’єктів інвестиційної діяльності визначити поняття фінансового лізингу та інвести...
19902. Іноземні інвестиції 92 KB
  Лекція № 7. Тема 7: Іноземні інвестиції. Мета: вивчення поняття іноземних інвестицій та правового статусу підприємства з іноземними інвестиціями ознайомлення з державною політикою в області іноземних інвестицій. План 1. Правовий режим іноземних інвестицій....
19903. Державне управління інвестиційною діяльністю в Україні 86.5 KB
  Лекція № 8. Тема 8: Державне управління інвестиційною діяльністю в Україні Мета: вивчення основ державного управління в галузі інвестиційної діяльності. визначення поняття зміст принципи і функції державного управління інвестиційною діяльністю План 1. Держав...