рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Общие сведения о минимизации логических функций

Общие сведения о минимизации логических функций - Методические Указания, раздел Программирование, Логическое проектирование и минимизация Общие Сведения О Минимизации Логических Функций. Однозначность Соответствия Ф...

Общие сведения о минимизации логических функций. Однозначность соответствия формы логической функции и параметров реальной электронной схемы приводит к необходимости оптимизации функции, т.е. к необходимости получения наилучшего её вида по выбранному критерию.

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

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

Поэтому на практике обычно решается частная задача оптимизации по одному из критериев. Чаще всего это делается по минимуму потребного оборудования, так как при этом автоматически решаются задачи получения минимальных габаритов, веса, энергопотребления, стоимости.

Такая частная задача оптимизации логической функции носит название минимизации. Таким образом, возникает задача нахождения из всех возможных форм логической функции её так называемой минимальной формы, обеспечивающей минимум затрат оборудования при построении синтезируемого узла, если имеется заданный набор логических элементов НЕ, И, ИЛИ с определенными техническими характеристиками например, максимально возможное число входов у элементов И, ИЛИ и др Нетрудно заметить, что в рамках нормальных форм минимальной будет такая разновидность функции, которая состоит из наименьшего количества членов при наименьшем, по возможности, общем числе символов переменных.

Из большего числа различных приемов и методов минимизации рассмотрим три наиболее показательных, типовых расчетный метод метод непосредственных преобразований 2 расчётно-табличный метод метод Квайна-Мак-Класки табличный метод метод Вейча-Карно. Исходной формой для любого из этих методов является одна из совершенных форм-СДНФ или СКНФ. Это обстоятельство практически не накладывает особых ограничений, поскольку переход от произвольной формы функции к её совершенным формам, как это было показано выше, не представляет принципиальных трудностей.

В общем случае при любом из вышеупомянутых методов минимизация производится в три этапа. 1-й этап- переход от совершенной Д К НФ к сокращенной Д К НФ путем производства всех возможных склеиваний друг с другом конституент, а затем всех производны членов более низкого ранга.

Таким образом, под сокращенной формой будем понимать дизъюнктивную или конъюнктивную форму функции, членами которой служат только изолированные несклеивающиеся элементарные конъюнкции или дизъюнкции. Члены сокращенной Д К НФ в алгебре логики носят название простых импликант имплицент. Не исключен случай, когда СД К НФ тождественно равна сокращенной форме рассматриваемой функции. 2-й этап- переход от сокращенной нормальной к тупиковой нормальной форме.

Тупиковой будем называть такую нормальную дизъюнктивную конъюнктивную форму функции, членами которой являются простые импликанты имплиценты, среди которых нет ни одной лишней. Термин лишний здесь имеет прямое значение. Лишним будем называть такой член функции, удаление которого не влияет на значение истинности этой функции. Возможны случаи, когда в сокращенной форме не оказывается лишних членов.

Тогда сокращенная Д К НФ тождественно равна тупиковой форме. Не исключены случаи появления нескольких тупиковых форм из одной сокращенной. Название тупиковая форма показывает, что дальнейшая минимизация в рамках нормальных форм уже невозможна. 3-й этап - переход от тупиковой минимальной среди нормальных форм формы функции к её минимальной форме. Этот этап, называемый обычно факторизацией, уже не является регулярным, как два предыдущих, и требует определенной сноровки, интуиции и опыта.

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

Различные методы минимизации отличаются друг от друга путями и средствами практической реализации того или иного этапа. При минимизации сложных функций чаще всего ограничиваются двумя первыми этапами, т.е. получением самой простой среди тупиковых ДНФ КНФ . Рассмотрим каждый из вышеназванных методов. 1.3. Расчетный метод минимизации Пусть задана некоторая функция в СДНФ, которую требуется минимизировать fсднф x1 x2 x3 x1 x2 x3 x1 x2 x3 1.5 1-й этап - производим все возможные склеивания членов заданной функции.

В общем случае эта процедура осуществляется за несколько шагов, в результате каждого из которых происходит понижение ранга склеиваемых членов на единицу. На первом шаге склеиваются конституенты fпр x1 x3 x2 x3 x1x2 1.6 Затем производится второй шаг испытания на склеивание всех членов функции в промежуточной форме. Рассматривая соотношение 1.6 , убеждаемся, что все его члены изолированы. Следовательно, полученная промежуточная форма является сокращенной ДНФ исходной функции сДНФ . Отметим, что все конституенты функции 1.5 участвовали хотя бы в одном склеивании, поэтому ни в сокращенной, ни тем более в тупиковой форме членов максимального ранга не будет fсднф x1x3 x2x3 x1x2 1.7 2-й этап - осуществляется проверка каждой простой импликанты в сДНФ с целью выявления и удаления лишних членов.

Проверка состоит в следующим. На значение истинности функции влияет только та импликанта, которая сама равна 1. любая импликанта становится равной 1 лишь на одном, вполне определенном наборе значений истинности своих аргументов. Но если именно на этом наборе суммы остальных членов тоже обращается в 1, то рассматриваемая импликанта не влияет на значение истинности функции даже в этом единственном случае, т.е. является лишней.

Применим это правило к проверке членов функции в сДНФ 1.7 1 x1x3 1 при x1 0, x3 1 сумма остальных членов на этом же наборе равна x21 1x2 1 следовательно, проверяемый член - лишний 2 x2x3 1 при x2 0, x3 1 сумма остальных членов на этом же наборе равна x11 x10 x1 следовательно, проверяемый член не является лишним 3 x1x2 1 при x1 0, x2 1 сумма остальных членов на этом же наборе равна 1x3 0x3 x3 следовательно, проверяемый член не является лишним.

Таким образом, отбросив лишний член, получим тупиковую дизъюнктивную нормальную форму ТДНФ исходной функции fтднф x1x2 x2x3 1.8 Более подробно остановимся на случае, когда лишних членов оказывается больше, например два. Это не означает, что оба лишних члена можно отбросить, так как каждый из них проверялся при вхождении другого в оставшуюся сумму. Следовательно, отбросить наверняка можно только один из них, а затем нужно снова произвести проверку возможности отбросить и второй член. Следует также остановится подробнее и на случае, когда исходной формой является СКНФ. Методика проведения первого этапа при этом практически не изменяется, но реализация второго этапа имеет свою специфику.

На значение истинности функции в конъюнктивной нормальной форме влияет только та имплицента, которая сама равна 0. Но любая имплицента становится нулем только при одном наборе своих аргументов.

Следовательно, правило проверки сокращенной КНФ на лишние члены нужно сформулировать таким образом для каждого члена сокращенной КНФ находится такой набор значений истинности его переменных, который обращает данный член в 0. Далее определяется значение истинности произведения остальных членов на этом же наборе. Если произведение также равно 0, то проверяемый член - лишний. 3-й этап - упрощаем ТДНФ или ТКНФ функции.

Применив закон инверсии к первому члену функции в ТКНФ, получим минимальную форму МФ fмф x1x2 x2 x3 для аппаратурной реализации которой нужной всего семь условий транзисторов. Интересно, что преобразование в минимальную форму ТДНФ функции получается более сложным путем fтднф x1x2 x2x3 x1 x2 x2 x2 x1 x3 x2 x3 x1 x2 x1 x3 x2 x3 fскнф Переход от сКНФ к МФ нетрудно осуществить через ТКНФ, как это было сделано выше. 1.4.

– Конец работы –

Эта тема принадлежит разделу:

Логическое проектирование и минимизация

В связи с динамическим изменением элементной базы электроники, измерительной аппаратуры, электронный практикум должен своевременно обновляться и… Дело это трудоемкое и достаточно дорогое, особенно в нынешних условиях. При всех несомненных достоинствах существующего практикума имеется довольно много замечаний, которые в силу…

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Общие сведения о минимизации логических функций

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Обзор методов логического проектирования и минимизации
Обзор методов логического проектирования и минимизации. Термин логическое проектирование охватывает целый комплекс проблем, возникающих на одной из ранних стадий создания цифрового автомата.

Нормальные формы логических функций
Нормальные формы логических функций. Синтез комбинационных устройств обычно начинается с табулирования значений истинности всех входных и выходных величин. Табличное задание закона функциони

Расчётно-табличный метод минимизации
Расчётно-табличный метод минимизации. Минимизация этим способом отличается от расчётной минимизации только методикой выявления лишних членов в сокращённой Д К НФ. Данный метод предложен американски

Общие сведения об Electronics Workbench
Общие сведения об Electronics Workbench. Electronics Workbench канадской фирмы Interactive Image Technologies разработана достаточно давно и в Росси известны версии 3.0, 4.0, 4.1, 5.0, 5.12 Profess

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

Цифровой компаратор
Цифровой компаратор. х разрядного кода а б Рис.4.2 Схема цифрового компаратора ко 2-му варианту На рис.4.2 а, б изображена схема цифрового компаратора. Входными кодами являются 2-х разрядные

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги