40163

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

Лекция

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

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

Русский

2013-10-15

518 KB

18 чел.

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


 

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

7213. Правовий режим майна субєктів господарювання 491 KB
  План 1. Майно у сфері господарювання. 2. Поняття і види правового режиму майна у сфері господарювання. 3. Право державної власності та правові форми її реалізації. 4. Право комунальної власності та правові форми її реалізації. 5. Право колективної в...
7214. Религия и культура 119.5 KB
  Религия и культура 1. Взаимоотношения религии и культуры в истории человечества. Сущность и основные функции религии. 2. Языческая культура. 3. Христианство и культура. 4. Исламская культура. Религия (лат. religio - благочестие...
7215. Распространение сигналов по оптическому кабелю 252.5 KB
  Распространение сигналов по оптическому кабелю. Передача сигналов по оптическому кабелю имеет свои особенности, которые связаны со способом передачи оптических сигналов, а также с тем, что распространение излучения по световоду является многомодовым...
7216. Сдвигающие Регистры 647 KB
  Сдвигающие Регистры Для выполнения операций умножения,деления, сложения необходим сдвиг числа влево или вправо. L1, L2 - сдвиг влево R1, R2 - сдвиг вправо (на 1 разряд, на 2)...
7217. Биохимия. Конспект лекций. Основные классы биомолекул 1.4 MB
  Основные классы биомолекул Практически все сухое вещество клеток составляют органические соединения, представленные четырьмя основными видами молекул: белками, нуклеиновыми кислотами, полисахаридами и липидами. Все они отличаются по свойствам, а зна...
7218. Проектирование систем электроснабжения 644.5 KB
  Проектирование систем электроснабжения Выбор оборудования Задание к расчётной работе Согласно приведённой на рис. 1 схеме от шин подстанции энергосистемы питается главная понизительная подстанция (ГПП), предназначенная для электроснабжения промышлен...
7219. Краткая характеристика ЗАО «МРК» 432 KB
  Цель руководства ЗАО «МРК» - техническое перевооружение литейного производства и создание единого литейного цеха с современным плавильным, формовочным оборудованием. ЗАО «МРК» - главный поставщик тюбингов для строящегося в областном центре метрополитена.
7220. Автоматизация междугородной связи с использованием ЦСК АХЕ - 10 303 KB
  Введение. Успешная деятельность современного человеческого общества невозможна без наличия специальных средств связи, обеспечивающих общение и взаимный обмен информацией между людьми независимо от расстояния. С каждым годом в мире возрастает объём и...
7221. Спроектировать двухступенчатый горизонтальный коническо-цилиндрический редуктор общего назначения привода ленточного конвейера 1.39 MB
  Задание проекта Спроектировать двухступенчатый горизонтальный коническо-цилиндрический редуктор общего назначения привода ленточного конвейера. Рис. 1. - Кинематическая схема привода ленточного конвейера: 1-двигатель 2- ременная передача...