Структурный синтез комбинационных устройств

Постановка задачи

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

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