Минимизация переключательных функций с помощью карт Карно

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

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

Введем понятие подкуба, которое используется в теории ПФ и их минимизации. Подкуб – это совокупность 2i соседних клеток карты Карно, заполненных единицами (нулями), для которых по крайней мере одна переменная в координатах всех этих 2i клеток имеет неодинаковые значения (0 и 1). Из определения следует, что подкуб могут образовать 2, 4, 8, 16 и т.д. соседних клетки карты.

Каждый 2i-клеточный подкуб позволяет при минимизации исключить i переменных – 1,2,3,4 и т.д. Действительно, подкуб, состоящий из двух клеток, соседних по горизонтали или вертикали (рис.2,а,б,в,г) характеризуется тем, что координаты его клеток различаются значением одной переменной, а остальные переменные имеют одинаковое значение.

Переменная, значения которой для этих клеток различны (0 и 1), в соответствии с законом склеивания исчезает. Четырехклеточный подкуб содержит клетки, координаты которых различаются значениями двух переменных (рис.3,а,б,в), следовательно, четырехклеточный подкуб позволяет исключить две переменные. Восьмиклеточный подкуб позволяет исключить три переменные (рис.3,г,д).

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

Контерм (конъюнктивный терм) – результат склеивания соседних минтермов, входящих в подкуб (соседних единичных клеток). В алгебраическом представлении контерм - есть конъюнкция переменных, имеющих неизменное значение в координатах строк и столбцов всех объединяемых клеток; если неизменное значение переменной в координатах равно 1, то в конъюнкции она записывается без инверсии, если равна 0 – то с инверсией.

На рис.2,а,б,в приведены примеры записи контермов для двухклеточных подкубов, а на рис.3,а,б,в,г,д – четырехклеточных () и восьмиклеточных ().

МДНФ – есть дизъюнкция контермов.

Пример: МДНФ для ПФ y9 (рис.3,е) как результат минимизации по единичным значениям функции имеет вид:

. (5)

Перейти на страницу: 1 2 3

Советуем почитать:

Разработка цифрового измерителя кровяного давления на микроконтроллере MC68HC908JL3
С развитием микроэлектронной индустрии, а в частности с развитием микроконтроллеров, появилась возможность делать малогабаритные и сравнительно дешёвые электронные изделия. На сегодня ...

Разработка конструкции и технологического процесса изготовления печатной платы
Основной особенностью производства ЭВМ является использование большого количества стандартных и нормализованных элементов, интегральных схем, радиодеталей и др. Важным вопросом, решаемы ...

Проект внедрения волоконно-оптической линии связи между УТС Югорскгазтелеком и 5 городскими АТС
Последние десятилетия двадцатого века характеризовались бурным ростом спроса на услуги связи и передачи информации. Согласно статистике объем передаваемой в мире информации и оказываемых ...

Меню



© 2015 TechExternal