Опадчий Ю.Ф., Глудкин О.П., Гуров А.И. Аналоговая и цифровая электроника (2000) (1095415), страница 103
Текст из файла (страница 103)
Строки указанной таблицы соответствуют простым нмпликантам, а столбцы— 0-кубам (конституентам единицы) ФАЛ, На пересечении (-й строки н (-го столбца ставится метка, если импликанта ( покрывает конституеиту у. Отметим, что импликаита ~ нокры»ает конституенту ) в случае, если она отличается от исг независимыми аргументами. 3. Определяют покрытие минимальной стоимости, для этого; а) выделяют ядро Квайна. ( глн 0-куб заданной ФАЛ покрывается только одной простой пм»ликантой, то последняя является существенной и входит в ядро Квайна н, следовательно, в покрытие минимальной стоимости; б) из таблицы вычерки»ают столбцы и строки, покрытые импликантами ядра Квайиа.
Если в полученной ноглс»ычерчивания таблице содержатся простые имплнканты, они также включаются в ядро Квайна с последующим вычеркиванием соответствующих строк и столбцов. в) сжимают таблицу по столбцам, для чего из нее вычеркивают столбцы, в которые полностью входит любой из оставшихся столбцов; г) сжимают таблицу по строкам, для чего из нее вычеркивают строки, которые пол»огп,ю включаются в любую из оставшихся строк. Последователыю сжимая таблицу по строкам и столбцам, получают циклическую таблицу, импликанты которой должны входить в покрытие ФАЛ минимальной стоимости.
О.кубам (констнтуентам единицы) ФАЛ. На пересечении (-й строкам циклической таблицы и нмпликант, образующих ядро Квайна, получают МДНФ заданной Функции. Проиллюстрир>'ем применение описанного алгоритма иа примере. Пример 16.7. Миииыкзирокеть ФЯЛ л(я) ~I(0, 1, 2, 4, 5, 7, 8, 10, 12, И, 18). Решеике, Цене покрытия исяоккоа ФАЛ Ц„=44. 1. Сформируем кубический комплекс К(к).
Формнрованне кубнческого комплекса К(г) удобно выполнять прн помощн разбнення констнтуент ФАЛ на группы, солержзщне одинаковое чнюю елнннц. Прк гаком прехсгавлекнн кубы бочее высокого ранга могут образовать только кубы, находящкеся в расположенных рядом группах, В рассматрнваемом нрнмере для ФАЛ четырех переменных можно выделять пять групп, представка нх в анде табнцы, Для заполнення таблнцы каждый нз кубов левого столбца поочередно срз» ннвается с кубами правого столбца.
Еслн сравниваемая пара образовала к~ более высокого ранга, последний заппсмвастся в соответствующвд столб таблицы. 2. Кубы, не образовавшне куб более высокого ранга, являются простыми имплнкантамя н формярузтт покрмтке ФАЛ П(а) (01-1, -111; 111-', 0-Оч -00; -О-О: 1-0). 3. С использованием П1а) построим таблицу покрытий Квайяа 11, 1. 4. Согласно полученной таблнке простыми нмплнкзнтами являются 0.0. и -0-0, так как только первая покрывает 0-куб 0001 и только вторая покрмваиг 0- уб 0010. б.
В оставшейся после вычеркивания существенных имплнкапт и покрм. еаемых нми коистнтуеит единицы таблице больше иет существенных имплнкаит. Поэтому проезведем сжатие по столбцам п строкам. Первокечалыюе сжатие но столбцзи не выполняется, так как в таблице отсутствуют столбцы, полно. гтью входящие в любой нз оставшихся, Таблица сжимается по строкам, так кзк первая строка полностью входит во вторую, а четвертная в пятую. Поэтому нз таблицы вычеркиваются строки с номерами эдип н четыре.
Оставшаяся таблица может быть сжата по столбцам, так как первый столбец полностью зходнт в четвертый, а второй столбец — в третий. На основании этом из таблицы вычеркиваются третий и четвертый столбны. Полученная таблица больше не может быть сжата ии по строкам, нн по столбцам. Прн атом нмплнззита 111- является, лишней, так как она не покрывает ни одну нз оставшихся 533 коистнтуент единицы, Полученная после ее исключения таблица н является циклическая. 6. Просуммировав имилиианты циилнчесиоа таблицы н простые нмплнивн ты, получим ФАЛ минимальной стоимости г(к) =хФ~+хчхч+кчх,хе+хала, Алгоритм сжатия по строкам и столбцам можно пояснить следующим образом.
Из множества нмпликант, полученных после исключения существенных, необходимо найти такое нх минимальное подмножество, которое обеспечит покрытие всех оставшихся н таблице конституент единицы. Поэтому, если существует Т-я импликаита, которая покрывает множество О-кубов Уь которое вклю. чает множество кубов Уь покрываемое нмпликантой у, то импликанта у является лишней. Описанный алгоритм без каких-либо изменений позволяет минимизировать ФАЛ любого числа переменных, в том числе и с применением ЭВМ, Коитрвльиые вопросы 1.
В чем заключаются цель н принципы минимизации логических устройств. реализуемых на БИС н СБИС? 2, Чем характеризуется сложность ДНФ? 3. В чем заключается минимизация ФАЛ с помощью кар~ Вейча? 4. Представьте карты Вейча функции двух, трех, четырех и пяти переменных. $, К чему сводится алгоритм минимизации ФАЛ? Что такое импликанта и покрытие Кнайна? б.
В чем заключается минимизация недоопределенной ФАЛ? 7. В чем заключается минимизация системы ФАЛ? 8. К чему сводится алгоритм минимизвцик ФАЛ методом Квайна н Мак-Класки? ГЛАВА !б. КОМБИНАЦИОННЫЕ ЛОГИЧЕСКИЕ УСТРОЙСТВА 36З„СИИТЕЗ ЛОГИЧЕСКИХ УСТРОИств В зАЛАИИОйт ВАзисе лз При построении логических устройств обычно не пользуются функционально полной системой ЛЭ, реализующих все три основ. ные логические операции: И, ИЛИ и НЕ.
На практике, с целью сокращения номенклатуры элементов пользуются функционально бзе Таблнна )а! Ферма аакнсн есноанмх логических ооерачна Услоеиое оаозиаоеине оиерании Форне нраастаеления нызоаиого сигнала Эаанеит ! ~:~ХР; Х,+Хо; Зттгтлз, Хаааа 2И вЂ” НЕ (нзтрнх Шеффера) ! .Оз+хо; .с,хе, хзтнхе; х,атно 2ИЛИ вЂ” НЕ (стрелка Пирса) Хз(хо Х(Х) Хтхо+ХЗХЗХО(ХЗ+Хз) лето ХЗХЗХО(ХЗ+Хз) ХОХО ХзХз ХО ХЗХз = (хз)хе))((хз(хз(хз)!(Хз)хз)).
полной системой элементов, включаюшей только два элемента, аыполннюших операции И вЂ” НЕ н ИЛИ вЂ” НЕ, илн даже только один из этих элементов. Причем число входов этих элементов, как правило. задано. Поэтому вопросы синтеза логических устройств в заданном базисе ЛЭ имеют большое практнчсское значение. Прежде чем перейти непосредственно к вопросам синтеза логических устройств в заданном базисе ЛЭ, составим таблицу (табл. 16.(), в которую для удобства сведем возможные формй представления выходных сигналов элементов 2И вЂ” НЕ и 2ЙЛИ— НЕ при условии, что на их входы поданы логические переменные Х~ И ХО.
На основе данной таблицы любую ФАЛ можно записать н требуемом базисе ЛЭ. При этом используются два технических приема; двойное инвертирование исходного выражения или его части и применение теорем Де-Моргана. Если требуется привести ФАЛ к базису ЛЭ И вЂ” НЕ, то указанными приемамн функция преобразуется к виду, содержашему только операции логического умножения н инверсии. Далее она переписывается через условнйе обозначения операции И вЂ” НЕ. Аналогично поступают при преобразовании ФАЛ к базису ЛЭ ИЛИ вЂ” НЕ. В этом случае в выражении оставляют только операции логического сложения и инверсии, Проиллюстрируем сказанное примером. Прнмер )ад.
Задана ФАЛ х(з) хзто+(хтззхо)(х,+х,) Преобразовать к бззззкам ЛЭ И-НЕ и ИЛИ-НЕ. Р тря ение. Барнс ЛЗ И вЂ” НЕ: Базис ЛЭ ИЛИ вЂ” НЕ: х(х) хзсо+хзхесо(хо+из) хз+хо+хзхзхо+хз+х~ хо+хо+ хз+ хе+хе+ хз+хо (хз)хо) ) ((хз(хз)хо) ) (хз(х1) ). 1бз, ОСОБЕННОСТИ ПОСТРОЕНИЯ ЛОГИЧЕСКИХ УСТРОЙСТВ НА РЕАЛЬНОЙ ЭЛЕМЕНТНОЙ БАЗЕ Как уже отмечалось ранее, обычно задан не только тнп ЛЭ, но н число его входов.
Это значит, что задано число входных переменных, над которыми выполняется логическая операция. Прн этом, как правило, реальное число входов заданных логнческнх элементов не соответствует числу переменных в полученных после соответствующего преобразования выражениях. Возникает одна нз следующяя снтуацнй: а) число входов ЛЭ больше числа переменных, входящих в реализуемую с нх помощью ФАЛ; б) число входов ЛЭ меньше чнсла переменных, входящих в реализуемую с нх помощью ФАЛ. Рассмотрим некоторые приемы, используемые для разрещеннн указанных протнворечнй. Число входов ЛЭ больше требуемого. Для рассмотрения этогЮ случая введем понятне актнвного н пасснвногологпческнхуровнейз Ахтивзоым логическим уровнем называется такое значеняе входной переменной, которое однозначно определяет выходной сигнал ЛЭ.
Для уяснення того, какие логнческне снгналы для элементов И вЂ” НЕ н ИЛИ вЂ” НЕ являются актнвнымк, рассмотрнм таблнцу, нстннностн (табл. 16.2) для этих элементов прн условии действий, на нх входах двух логических сигналов. Из таблицы видно, что для элемента И вЂ” НЕ активным логнче. скнм уровнем является снгнал лог. О, так как наличие этого снг- Таблиаа !62 Обебмеииая саблина исеиинести есиеанмх лесиеесиих еиераииа хх с'.::„> с:~ ' %~ %х х хх хх к= хе хх'ко= * Гзх х «~хх " %'х4 х= ху~~а х=х, ло хв к, лх Рве. 1Вд.
умевьшевве фввтвееекого чвова входов вхвиевтов И вЂ” НЕ (а) в или — ие (а) 537 нала хотя бы на одном входе этого элемента однозначно определяет получение на выходе сигнала лог. !. Следовательно, сигнал лог. 1 для этого элемента является пассивным. По аналогии со сказанным, для элемента ИЛИ вЂ” НЕ активным является сигнал лог. 1, который однозначно определяет появление на выходе сигнала лог.
О: И вЂ” Е-)О '""'" ' ИЛИ вЂ” НЕ- )'1 '"'"'" " (16,1) 11 — пассивныи; 1Π— пассивный. Следует отметить, что ЛЭ с л-входами безразлично, сколько нассивных и активных уровней присутствует на его входах. Важен факт наличия нли отсутствия па входах хотя бы одного активного логического уровня. Из сказанного однозначно следует, что уменьшить фактическое число входов ЛЭ можно, подавая иа неиспользуемые входы сигналы пассивных логических констант: Π— для элементов ИЛИ вЂ” НЕ, 1 — для элементов И вЂ” НЕ; Другой прием уменьшения фактического числа входов ЛЭ базируется на использовании теоремы 3 нз $ 14.5.
Согласно этой теореме х+х- х и хх=х, поэтому иа несколько входов ЛЭ можно. подавать одну и ту же ло>ическую переменную (рнс. 16.1), Следствием сказанного являются два практических вывода: 1. Если на все входы л.входового элемента И вЂ” НЕ или ИЛИ— НЕ подать один и тот же логический сигнал, то относительно этого сигнала элемент пренращаетси в нивертор; 2. Если на а — 1 вход а-входового элемента И вЂ” НЕ илн ИЛИ— НЕ подать пассивпыс логические сигналы, то относительно л-го входа элемент препрашается и инвертор (рис. 16.2). 4 Рнс. 16.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
