2.4.5. Синтез кс из элементов и-или-не.

–И-ИЛИ-НЕ обладает функциональной полнотой. Как и в предыдущих вариантах, КС строятся только из одного типа ЛЭ и, поэтому, нет проблемы выбора типа ЛЭ при синтезе схемы.

Важной остается задача поиска функций входов ЛЭ.

	qИ-pИЛИ-НЕ
2И-3ИЛИ-НЕ	3И-2ИЛИ-НЕ

Отсюда получаем дизъюнктивную модель элемента И-ИЛИ-НЕ.

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

1. Инвертировать F.

2. Получить ТДНФ Т = .

3. Разделить Т на р частей: Т₁, Т₂, … Т_р .

4. Инвертировать Т₁, Т₂, … Т_р .

5. Получить ТДНФ , , … .

6. Разделить каждую ТДНФ , , … на q частей:

Т₁₁,…Т_1q,Т₂₁,…Т_2q, … Т_р1,…Т_рq.

7. Инвертируя, получить функции входов:

, …, , …, ,…, , …

,…, .

При построении КС только из элементов И-ИЛИ-НЕ процедура эта применяется сначала к реализуемой функции, а затем к функциям входов ЛЭ, получаемым в процессе синтеза КС.

При этом после действий по п.7 процедуры выполняются действия по п.1, то есть выполняется двойное отрицание. Однако и значит можно не выполнять п.7 и п.1. Это позволяет ввести упрощенную дизъюнктивную модель ЛЭ И-ИЛИ-НЕ.

Таким образом, получаем упрощенную дизъюнктивную модель элемента.

Работать с такой моделью проще, но при этом нужно:

1. Заменить исходную функцию на ее инверсию.

2. Инвертировать значения функций для входов ЛЭ, не соединенных в КС с выходами других ЛЭ.

В результате получаем сокращенный алгоритм синтеза КС.

1. Инвертировать исходную функцию.

2. Получить ТДНФ рассматриваемой функции.

3. Разделить ТДНФ на р частей: Т₁, Т₂, … Т_р .

4. Инвертировать Т₁, Т₂, … Т_р .

5. Получить ТДНФ , , … .

6. Разделить каждую ТДНФ Т_j на q частей и получить

, …, , …, ,…, , …

,…, .

7. Для каждой функции входов повторять действия по п.п. 3-6, пока есть функции более одной переменной.

8. Инвертировать значения всех констант и отдельных переменных на входах ЛЭ.

Примечание.

Одинаковые части, получающиеся в КС, следует объединять. (В процессе построения КС или после завершения работ по п.8.)

Рассмотрим пример реализации БФ на элементах 2И-3ИЛИ-НЕ.

1 и 2 Находим по карте Карно инверсию функции и ТДНФ

3. Делим полученную ТДНФ на три части.

4;5.

6. Делим каждую из частей на две.

,

Если получились отдельные переменные, то мы их инвертируем и получаем функции входов, а другие Тij продолжим обрабатывать по сокращенному алгоритму.

3. Делим ТДНФ на три части.

4;5.

6. Делим каждую из частей на две.

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

7. Инвертируем Т для получения функций входа.

Теперь построим схему.

2.4.6. Синтез кс из набора элементов.

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

Пример набора элементов:

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

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

В приведенном выше примере, из элемента 3И-2ИЛИ-НЕ путем подстановки констант можно получить ЛЭ 2И-НЕ, 3И-НЕ, 2ИЛИ-НЕ. Фактически, схему можно строить только на элементах 3И-2ИЛИ-НЕ.

При построении КС сначала используются только те ЛЭ, которые не являются покрываемыми.

Затем в построенной КС заменяем везде, где это возможно использованные ЛЭ на наиболее простые покрываемые.

При синтезе КС из непокрываемых ЛЭ остается проблема нахождения наилучшего ЛЭ в данном месте.

Всякий раз для очередной рассматриваемой функции ищем ЛЭ с minW входа. Этот элемент и надо использовать.

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

При анализе ЛЭ И-ИЛИ-НЕ необходимо использовать полную дизъюнктивную модель.

Рассмотрим пример построения КС из набора элементов.

Задан набор ЛЭ.

Временно исключаем из рассмотрения поглощаемые ЛЭ, и получаем сокращенный набор ЛЭ.

Выясним теперь, какой ЛЭ должен быть на выходе всей КС.

Предположим, что на выходе стоит ЛЭ 3И-НЕ и найдем его функции входов.

,

maxW = 8

Tеперь предположим, что на выходе стоит ЛЭ 2И-2ИЛИ-НЕ и найдем его функции входов, используя неупрощенную дизъюнктивную модель.

По карте Карно находим инверсию функции и ТДНФ .

maxW = 8

Минимальный maxW у ЛЭ одинаковый. Будем выбирать по минимальному суммарному весу. Суммарный W для 3И-НЕ – 24, для 2И-2ИЛИ-НЕ – 20. Следовательно, выбираем 2И-2ИЛИ-НЕ (чем меньше вес, тем проще схема).

Осталось достроить функцию входа . Подбираем ЛЭ для реализации (a b).

Анализ показывает, что здесь по минимуму maxW можно выбрать любой из двух ЛЭ. ( Сумма W для обоих ЛЭ здесь одинакова.)

Выберем И-НЕ как более простой – 3 входа вместо 4.

В итоге получаем:

После анализа полученной схемы определяем, что ЛЭ 3И-НЕ можно заменить покрываемым элементом 2И-НЕ. Получаем окончательную схему реализации БФ.

ЛИТЕРАТУРА

1. Желенков Б.В. Дикин В.В. Курс интерактивных лабораторных работ по дисциплине «Дискретная математика». – М.: МИИТ, 2003г.

2. Першеев В.Г., Желенков Б.В. Мультимедийный конспект лекций «Дискретная математика». – М.: МИИТ, 2002г.

3. Поспелов Д.А. Логические методы анализа и синтеза схем. - М.: Энергия, 1979г.

4. Яблонский С.В. Введение в дискретную математику: Учеб. Пособие для вузов. 3-е изд.- М.: Высш. Шк., 2001 г.