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


 

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

16821. Технологии добычи золота 52 KB
  Технологии добычи золота. В настоящее время золото добывают главным образом из руд причем не только золотых но и таких в которых основными полезными ископаемыми являются другие цветные металлы в частности медь цинк серебро свинец. В этом случае золото рассматривает...
16822. Технологические исследования для обоснования кондиций и подсчета запасов рудных месторождений 46 KB
  Технологические исследования для обоснования кондиций и подсчета запасов рудных месторождений В.Е.Дементьев Г.И.Войлошников ОАО Иргиредмет Золотодобыча №121 Декабрь 2008 Успешность проекта горнодобывающего предприятия во многом определяется правильным обосно...
16823. Технология попутного извлечения золота из полиметаллических руд 30 KB
  Технология попутного извлечения золота из полиметаллических руд Гравитационное обогащение Гравитационное обогащение руд коренных и рассыпных месторождений является одним из наиболее распространенных способов переработки широкого спектра полезных ископаемых.
16824. Физические и химические свойства золота 139 KB
  Физические и химические свойства золота проба золота РМО ОАО Иргиредмет Нет человека который не видел бы золота в ювелирных изделиях. Яркожелтый металл известен людям несколько тысяч лет. Однако в природе золото многолико. Размер его частиц колеблется от микрон до д
16825. Частота съема шлихов 53.5 KB
  Частота съема шлихов От редакции. Больше золота можно получить за счет объемов промывки песков но для этого нужны солярка и запчасти. Можно также получить больше золота за счет качественной промывки песков. Наша редакция не может помочь золотодобытчикам соляркой и з...
16826. ЭНЕРГОЕМКОСТЬ ТРАНСПОРТНЫХ СИСТЕМ КАРЬЕРОВ: ОЦЕНКА И ПЕРСПЕКТИВЫ 328 KB
  ЭНЕРГОЕМКОСТЬ ТРАНСПОРТНЫХ СИСТЕМ КАРЬЕРОВ: ОЦЕНКА И ПЕРСПЕКТИВЫ Авторы: Ворошилов Г. А. главный инженер ОАО Институт Уралгипроруда.; Лель Ю. И. д.т.н. проф. зав. кафедрой разработки месторождений открытым способом Уральского государственного горного университета. ...
16827. Геологические особенности техногенных золотосодержащих минеральных образований хвостов обогащения золотоизвлекательной фабрики AGRC и геотехнология их рациональной переработки 605.45 KB
  Нарсесян Сурен Саакович Геологические особенности техногенных золотосодержащих минеральных образований хвостов обогащения золотоизвлекательной фабрики AGRC и геотехнология их рациональной переработки Автореферат диссертации на соискание ученой степе
16828. Золотопромышленность, добыча полезных ископаемых 77.24 KB
  Золотопромышленность добыча полезных ископаемых М.В. Шиловский История открытия и формирования основных центров по добыче золота в Сибири целиком укладывается в рамки ХIХ в. В 1812 г. русским подданным было разрешено разрабатывать серебряные и золотые руды на Ура
16829. Организация защиты населения в военное время. Медицинское обеспечение мероприятий гражданской обороны 246 KB
  Рассмотреть вопросы организации защиты населения в период подготовки к возможным боевым действия и в военное время. Изучить коллективные средства защиты (убежища, противорадиационные укрытия, простейшие), их классификацию, тактико-технические характеристики, санитарно-гигиенические характеристики