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


 

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

32794. Исторические этапы развития мировой филосовской мысли. Основные филосовские принципы и исторические типы филосовствования 14.95 KB
  В истории философской мысли также выделяются основные типы философствования философского анализа. В античности созерцательный тип философствования проявился в натурфилософии философии природы а в Древнем Китае – в принципе недеяния т. 2Умозрительный тип философствования – это способ теоретического постижения действительности основанный на отвлеченных логических построениях не связанных с опытными данными. Ярким примером умозрительного типа философствования являются доказательства существования Бога в учении Ф.
32795. Особенности Древнеиндийской философии. Её основные направления 17.32 KB
  В развитии культуры Древней Индии можно выделить два основных периода: 1ведический – предфилософский сер. связанный с переселением на территорию Древней Индии арийских племен. Культура Древней Индии в целом и философия в частности возникла и развивалась в условиях кастовой организации общественной жизни патриархальных традиций и власти деспотического государства. Основным культурным источником философии Древней Индии стала ведическая литература.
32796. Особенности Древнекитайской философии и её основные направления 17.69 KB
  В этот период создавались важнейшие философские школы оказавшие огромное влияние на общественную мысль китайского общества: конфуцианство даосизм моизм легизм и др. б даосизм как онтологическое учение его наивнодиалектический характер. Основателем даосизма является мудрец Лаоцзы VI – V вв. Его главный труд – Даодэцзын – Книга о Дао и Дэ.
32797. Античная философия: этапы развития и характерные черты. Первые греческие мыслители 22.71 KB
  Античная философия: этапы развития и характерные черты. Античная философия возникла в Древней Греции в середине I тысячелетия до н. В центре внимания философии данного периода проблемы природы космоса в целом; 2классическая греческая философия учения Сократа Платона Аристотеля – V – IV вв. Главное внимание здесь уделяется проблеме человека его познавательных возможностей; 3философия эпохи эллинизма – III в.
32798. Философия Платона, Теория познания Платона 14.35 KB
  Наиболее известные диалоги Платона: Государство Пир диалоги Софист и Федр посвящены проблеме души Тимей – вопросу возникновения Космоса Протагор – проблеме добродетели. Человек по Платону единство души и тела которые в то же время противоположны. Смертное тело – только тюрьма для души оно источник страданий причина всех зол; душа гибнет если она слишком срослась с телом в процессе удовлетворения своих страстей. Стимулом к совершенствованию души является любовь к прекрасному.
32799. Философия эпохи эллинизма, ее основные направления 14.57 KB
  На развитие античной философии значительное влияние оказал распад империи А. Неоплатонизм получил распространение в период когда античный способ философствования уступал место философии основанной на христианской догматике. Это последняя попытка решить задачу создания целостного философского учения в рамках дохристианской философии. Главное отличие от философии Платона заключается в том что мир идей Платона – это неподвижный безличный образец мира а в неоплатонизме появляется активное мыслящее начало – Ум.
32800. Вклад Аристотеля в развитие мировой философской культуры (учение о материи и форме). Учение о душе 13.19 KB
  Аристотель 384 – 322 гг. Аристотель считается величайшим энциклопедистом древности и систематизатором всех философских и научных знаний накопленных до него в области логики физики биологии психологии этики экономии искусствознания и др. Высоко оценивая Платона Аристотель подверг его идеалистическое учение серьезной критике Платон мне друг но истина дороже. Аристотель формулирует свое представление о бытии.
32801. Условия формирования западноевропейской философии в Средние века. Роль христианства в развитии культуры 15.27 KB
  Условия формирования западноевропейской философии в Средние века. Этапы развития и характерные черты средневековой философии. В развитии философии Средних веков можно выделить несколько основных этапов: 1 апологетика II – IV вв. В этот период не было создано философских систем но был намечен круг вопросов ставших центральными в средневековой философии: о Боге и соотношении Бога и мира о сотворении мира и структуре мироздания о сущности человека и его месте в мире; 2 патристика V – IX вв.
32802. Философия Августина Аврелия (Блаженного). И Фомы Аквинского 14.95 KB
  Учение о Боге и мире. Бог рассматривается им как начало всего сущего как единственная причина возникновения вещей. Бог вечен и неизменен. Мир созданных богом вещей изменчив и пребывает во времени.