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

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

Есть только проблема поиска функций входов ЛЭ.

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

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

T₁ T₁ = ₁

F = T

ТДНФ T_k T_k = _k

Алгоритм синтеза КС.

1. Получить ТДНФ рассматриваемой БФ.

2. Разделить полученную ТДНФ на К частей.

3. Получить инверсию отдельных ТДНФ.

4. Для каждой полученной функции входа повторять действия по п.п. 1-3.

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

5. В полученной КС отыскиваются одинаковые части (подсхемы) и заменяются одной общей частью, для построения более экономной схемы.

Рассмотрим пример синтеза схемы минимальной глубины на элементах 2И-НЕ.

1. Получаем ТДНФ Т для F, например, по карте Карно.

2. Разделяем ТДНФ на 2 части с min(maxW).

3. Ищем инверсии отделенных частей (можно аналитически, но здесь удобнее по карте Карно).

Таким образом, получаем первый элемент схемы.

Далее продолжаем аналогично. В результате получаем схему.

В КС есть одинаковые части, допускающие слияние. Объединив одинаковые части, получим:

Рассмотрим пример синтеза схемы минимальной глубины на элементах 3И-НЕ.

F = abcde

1. Получаем ТДНФ Т для F.

Т = abcde.

2. Т = abcde

Т₁ = abcde; Т₂ = 0;Т₃ = 0.

3. ; ;

Далее имеем:

1.

2. ; ;

3. ; ;

Далее действуем аналогично.

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

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

Есть только проблема поиска функций входов ЛЭ.

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

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

T₁ = ₁

F F T

ТДНФ T_к = _к

Алгоритм синтеза КС.

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

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

3. Разделить ТДНФ на К частей.

П.п. 4 и 5 аналогичны процедуре синтеза КС из элементов И-НЕ.

Рассмотрим пример синтеза схемы минимальной глубины на элементах 3ИЛИ-НЕ.

F_~(a,b,c,d) задана М₁* =(0,7,13,14,15), М₀* = (1-6,8-10)

1. Получаем инверсию F_~ .

_~(a,b,c,d) М₁* = (1-6,8-10), М₀* (0,7,13,14,15)

2. По карте Карно получаем ТДНФ :

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

, ,

Далее обрабатываем ₁ , ₂ ,₃ .

1. Если рассматривать ₁ , ₂ ,₃ не как недоопределенные БФ, а как функции, заданные T₁ , T₃, T₂ , то их можно инвертировать по правилам де-Моргана:

, ,

Полученные ДНФ приводим к ТДНФ. (В нашем примере они останутся такими же.)

3. Разделяя ТДНФ получим:

Завершая, реализуем последнюю функцию входа .

Функции ₁ , ₂ ,₃ нашего примера можно рассматривать как недоопределенные БФ и задать М₁ и М₀. При этом, например, для ₁ М₁ получается как часть М₁ (F_~), которая покрывается Т₁, а М₀ - как М₀ (F_~).

М₁^* 

₁:

М₀^* 

Работа с как с недоопределенной БФ сложнее, но в принципе, может давать более хорошие результаты.

Рассмотрим пример синтеза схемы минимальной глубины на элементах 2ИЛИ-НЕ.

1. Выполняем инверсию. Удобно делать это по карте Карно. При этом сразу можно найти ТДНФ.

2. 

3.  ,

Далее обрабатываем ₁:

1.

2.

3. ,

Достраиваем схему.

Теперь обрабатываем ₁₁ и ₁₂:

1. ,

2. ,

3. ,

Осталось реализовать _2.