32. Метод синтеза сфэ, основанный на компактной реализации всех конъюнкций с помощью универсального многополюсника, сложность получаемых схем.

Определение. Функцияотnаргументовназывается булевой функцией (или функцией алгебры логики), если каждому наборуона ставит в соответствие число.

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

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

Метод синтеза СФЭ, основанный на компактной реализации всех конъюнкций с помощью универсального многополюсника. Данный метод также основывается на представлении функции в виде СДНФ, но позволяет строить менее сложные схемы за счет более компактной реализации конъюнкций. Разложение функции в СДНФ может содержать конъюнкции, имеющие общие множители. Если две таких конъюнкции реализовать одной подсхемой в блоке, то для этого потребуется конъюнкторов хотя бы на единицу меньше, чем их требовалось прежде, при независимой реализации всех конъюнкций первым методом синтеза. Компактной реализации всех возможных конъюнкций длиныnможно добиться с помощью индуктивно построенного универсального многополюсника, имеющегоnвходов и 2ⁿ выходов, гдеn = 1,2,3,… Преимущества метода особенно заметны, когда одной схемой требуется реализовать систему из нескольких булевых функций. В этом случае можно было бы расщепить и далее пропустить через дизъюнкторы те выходы универсального многополюсника, которые соответствуют конъюнкциям, входящим в СДНФ функций заданной системы. Это позволило бы обойтись меньшим количеством конъюнкторов, чем если бы каждую функцию заданной системы независимо реализовали своей собственной подсхемой.

Сложность такого многополюсника равна L() =.

Если схема из функциональных элементов Σ содержит ровно r функциональных элементов, то говорят, что она имеет сложность r и записывают это в виде равенства L(Σ) = r.