Главная > Разное > Цифровые устройства
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

1.12. Минимизация неполностью определенных функций, совместная минимизация нескольких функций

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

Совершенную ДНФ неполностью определенной функции можно представить в виде

где номера тех точек области определения, в которых функция имеет значение 1, т.е. номера тех точек, в которых функция имеет неопределенное значение, т.е.

Пусть задана СДНФ неполностью определенной функции четырех переменных

где Составим для этой функции диаграмму Вейча (рис. 1.4). Для этого в клетки с номерами и 8 следует занести значения функции, равные 1, а в клетки с номерами и 12 — неопределенные значения С помощью диаграммы Вейча легко найти все минимальные покрытия, полагая либо либо На рис. 1.4 представлены два варианта доопределения функции которые дают минимальные ДНФ:

если символ не вошел ни в один -куб, и если он вошел хотя бы в один -куб).

Рис. 1.4

Аналогично этому можно найти и МКНФ данной неполностью определенной функции, произведя оптимальным способом доопределение инверсной функции

Для данной функции имеется только один способ доопределения, дающий минимальную КНФ.

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

Комбинационные схемы. Логическая схема (рис. 1.5), выходные сигналы которой описываются системой переключательных функций

где входные сигналы логической схемы, называется комбинационной схемой (КС). Из (1.84) следует, что КС реализует однозначное соответствие между значениями входных и выходных сигналов.

При реализации функций описывающих выходные сигналы КС, используются логические элементы (ЛЭ), выпускаемые в виде интегральных схем. Условные графические обозначения таких ЛЭ, выполненные в соответствии с требованиями ЕСКД [12], представлены на рис. 1.6.

Рис. 1.5

Рис. 1.6

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

МДНФ функций заданных диаграммами Вейча (рис. 1.7), имеют вид

На рис. 1.8,а показана КС, реализующая эти функции. Из рис. 1.7 следует, что функции можно представить

(кликните для просмотра скана)

также в форме (не МДНФ)

Контерм входит в обе функции, а для его реализации требуется только один ЛЭ И. Для реализации функций в форме (1.86) требуется семь, а в форме (1.85) — восемь первичных термов. На рис. 1.8, б показана КС, реализованная в соответствии с (1.86). Сложность реализации КС можно оценивать также по суммарному числу входов используемых ЛЭ.

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

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

На рис. 1.10 представлены шесть способов реализации функции на ЛЭ различного типа. Последняя форма представления функции не может быть получена формальными методами, использованными при построении СНФ и МНФ, из-за линейной операции сумма по модулю два, достаточной для описания только линейных функций.

<< Предыдущий параграф Следующий параграф >>
Оглавление