Синтез автоматов без памяти

Комбинационная схема состоит из логических элементов и реализует булеву функцию или совокупность булевых функций.
Под логическим элементом понимают техническое устройство, реализующее одну элементарную булеву функцию.
Обычно логический элемент рассматривается как "черный ящик" и учитывается только реализуемая элементом булева функция.
Конструктивно логические элементы объединяются в единый корпус, называемый интегральной микросхемой (ИМС).
Под ИМС понимается микроминиатюрное электронное устройство, элементы которого нераздельно связаны конструктивно, технологически и электрически.
В одном корпусе ИМС могут быть один, два и более логических элементов. Число логических элементов, объединяемых в один корпус ИМС, характеризует степень интеграции логических элементов.

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

Обозначения логических элементов, реализующих основные булевы функции И, ИЛИ, НЕ
(булевый базис)

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

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

Задача синтеза КС состоит в построении оптимальной схемы проектируемого узла устройства, исходя из физического описания его работы (технического задания на проектирование).
Основные этапы синтеза:
1. Анализ технического задания и составление таблицы истинности.
2. Минимизация логических функций.
3. Преобразование минимальных логических функций для рациональной реализации логической схемы в заданном базисе.
4. Построение функциональной схемы.
5. Проверка работоспособности схемы и её корректировка.

Основные критерии качества технической реализации КС:
Сложность оборудования.
На практике оцениваются числом корпусов ИМС, используемых в схеме.
На теоретическом уровне используется оценка сложности КС по Квайну. Цена схемы по Квайну определяется суммарным числом входов ЛЭ в составе схемы.
Быстродействие. Оценивается максимальной задержкой сигнала при прохождении его от входа схемы к выходу. При этом считается, что каждый элемент задерживает сигнал на время, равное τ.
Минимум применяемых элементов.
Надёжность.

СИНТЕЗ ОДНОВЫХОДНЫХ КОМБИНАЦИОННЫХ СХЕМ
Задача синтеза схемы состоит в преобразовании логических функций в суперпозицию логических элементов заданного типа.
Исходная булева функция должна быть представлена в минимальной форме: МДНФ или МКНФ.
Найдем МДНФ и МКНФ исходной функции с помощью карты Карно.

а) Для построения схемы на элементах И, ИЛИ, НЕ можно использовать как МДНФ, так и МКНФ функции.
Построим схему по МДНФ.

Построим схему по МКНФ.

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

В этом случае функция представлена в виде суперпозиции только операторов И-НЕ.
Для реализации инверторов можно использовать двухвходовые элементы И-НЕ (2И-НЕ).

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

В этом случае функция представлена в виде суперпозиции только операторов ИЛИ-НЕ.
Для реализации инверторов можно использовать двухвходовые элементы ИЛИ-НЕ (2ИЛИ-НЕ).