Расчетно-табличный метод минимизации

Расчетный метод минимизации.

Расчетно-табличный метод минимизации - student2.ru

Этап

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

1 шаг) Расчетно-табличный метод минимизации - student2.ru и Расчетно-табличный метод минимизации - student2.ru

Результат склеивания Расчетно-табличный метод минимизации - student2.ru

2 шаг) Расчетно-табличный метод минимизации - student2.ru и Расчетно-табличный метод минимизации - student2.ru

Результат склеивания Расчетно-табличный метод минимизации - student2.ru

3 шаг) Расчетно-табличный метод минимизации - student2.ru и Расчетно-табличный метод минимизации - student2.ru

Результат склеивания Расчетно-табличный метод минимизации - student2.ru

Расчетно-табличный метод минимизации - student2.ru

Затем выполняется испытания на склеивание всех членов функции в промежуточной форме Расчетно-табличный метод минимизации - student2.ru .

Из соотношения Расчетно-табличный метод минимизации - student2.ru видно, что все его члены изолированы друг от друга. Следовательно, полученная промежуточная форма является сокращенной ДНФ исходной СДНФ.

Необходимо убедиться, что все конституенты исходной СДНФ участвовали хотя бы в одном склеивании и в сокращенной форме максимального ранга не будет.

Расчетно-табличный метод минимизации - student2.ru

Этап

Выполним проверку каждой простой импликанты в СДНФ, чтобы выявить и удалить лишние члены.

На значение истинности функция влияет только импликанта, которая сама равна 1.

Любая импликанта становится равной 1лишь на одном определенном наборе значений истинности своих аргументов.

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

1) Расчетно-табличный метод минимизации - student2.ru =1

При Расчетно-табличный метод минимизации - student2.ru

Сумма остальных членов на этом же наборе:

Расчетно-табличный метод минимизации - student2.ru

Следовательно проверяемый член лишний.

2) Расчетно-табличный метод минимизации - student2.ru

При Расчетно-табличный метод минимизации - student2.ru

Сумма остальных членов на этом же наборе:

Расчетно-табличный метод минимизации - student2.ru

Следовательно проверяемый член не лишний.

3) Расчетно-табличный метод минимизации - student2.ru

При Расчетно-табличный метод минимизации - student2.ru

Расчетно-табличный метод минимизации - student2.ru

Следовательно проверяемый член не является лишним.

Таким образом, отбросив лишний член, получим тупиковую ДНФ исходной функции

Расчетно-табличный метод минимизации - student2.ru

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

Этап

Попытаемся упростить ТДНФ.

*Для аппаратурной реализации ТДНФ потребуется восемь условных транзисторов.

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

Следовательно, любую логическую схему можно оценить по количеству потребного для её реализации оборудования, подсчитав количество входов всех элементов, составляющих эту схему (суммарное число входов всех элементов). Это оценка по Квайну является приближенной, т.к. логические элементы могут строиться на различных принципах и по различным схемам (на многоэмиттерных транзисторах, по схеме токовых переключателей и т.д.). Такая оценка является очень удобной, т.к. объективна, доступна на самых ранних стадиях логического проектирования, главное, все – таки достаточна точна при сравнительных ( а не абсолютных) оценках различных вариантов одного и того же устройства.*

Применим к Расчетно-табличный метод минимизации - student2.ru распределительный закон второго рода

Расчетно-табличный метод минимизации - student2.ru

*Распределительный закон второго рода: сумма некоторой логической переменной и произведения нескольких аргументов равно произведению сумм каждого сомножителя и этой переменной.

Расчетно-табличный метод минимизации - student2.ru

Расчетно-табличный метод минимизации - student2.ru

Применим распределительный закон первого рода

*Произведение суммы нескольких аргументов на какую либо (логическую) переменную равно сумме произведений каждого слагаемого на эту переменную

Расчетно-табличный метод минимизации - student2.ru *

Расчетно-табличный метод минимизации - student2.ru

=>

Расчетно-табличный метод минимизации - student2.ru
Расчетно-табличный метод минимизации - student2.ru

Введём в состав функции нулевой член Расчетно-табличный метод минимизации - student2.ru и выполним преобразования.

Расчетно-табличный метод минимизации - student2.ru

Применим ко второму конъюнктивному члену правило Де Моргана и получим минимальную форму исходной функции.

Расчетно-табличный метод минимизации - student2.ru

Для аппаратурной реализации потребуется всего семь условных транзисторов.

Расчетно-табличный метод минимизации

Отличается от расчетного только методикой выявления лишних членов в сокращенной ДНФ(КНФ). Этот метод был предложен американским ученым У. Квайном.

Первый и третий этапы будут идентичны соответствующим этапам при расчетном методе.

Расчетно-табличный метод минимизации - student2.ru

Расчетно-табличный метод минимизации - student2.ru

2 Этап

Для выявления возможных лишних членов в сДНФ строится таблица, входными величинами в которой будут конституенты – члены СДНФ и простые импликанты – члены сДНФ.

Поэтому такую таблицу называют конституентно-импликантной матрицей; либо таблицей Квайна, либо таблицей покрытий.

Число строк = числу простых импликалет в сДНФ. Строки делятся на столбцы, число столбцов = числу конституент в СДНФ.

Простые импликанты Конституенты
Расчетно-табличный метод минимизации - student2.ru Расчетно-табличный метод минимизации - student2.ru Расчетно-табличный метод минимизации - student2.ru Расчетно-табличный метод минимизации - student2.ru
Расчетно-табличный метод минимизации - student2.ru }лишняя X   X  
Расчетно-табличный метод минимизации - student2.ru }ядро X     X
Расчетно-табличный метод минимизации - student2.ru   X X  

Процесс минимизации начинается с последовательного сопоставления каждой простой импликанты со всеми конституентами.

Если какая-либо импликанта является собственной частью некоторой конституенты, то в табличной клетке, соответствующей обоим членам, проставляется любой условный значок.

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

В идеальном случае каждая импликанта покрывает только свою конституенту и в каждом столбце находится только один условный значок.

Практически этого не происходит.

Часто одна и та же конституента покрывается в таблице несколькими импликантами.

Необходимо вычеркиванием некоторых (лишних) импликант попытаться оставить в каждой колонке только один значок или минимальное их число.

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

В ядро входят импликанты Расчетно-табличный метод минимизации - student2.ru и Расчетно-табличный метод минимизации - student2.ru . Вычеркивание Расчетно-табличный метод минимизации - student2.ru не нарушает условия о наличии хотя бы одного покрытия каждой конституенты.

Наши рекомендации