Синтез методом каскадов.

При синтезе комбинационных автоматов используется метод каскадов, основанный на разложении Шеннона:

f(x₁,..., x_i,..., x_n)=x_if(x₁,..., 1,..., x_n)Ú _if(x₁,..., 0,..., x_n)=x_if(1)Ú _if(0).

Такое разложение позволяет исключать переменные и понижать размерность по каскадам до тех пор, пока остаточные функции не будут иметь простой вид и их реализация не будет представлять трудности [9].

Реализуем вышерассмотренную функцию z(аbсdx₂x₁) методом каскадов с использованием блоков исключения переменной вида x_if(1)Ú _if(0), которые легко реализуются в базисе И, ИЛИ, НЕ.

Очевидно, что:

z(аbсdx₂x₁)= ,

т.е. , , которые реализуются на двухвходовых элементах И, ИЛИ. Проводить дальнейшее разложение нет необходимости. Соответствующая схема комбинационного автомата изображена на рис. 62.

Рис. 62. Схема, построенная по методу каскадов

Интересно, что схема на рис. 62, построенная по методу каскадов, проще в смысле числа элементов – для ее построения необходимо 11 элементов (9 двухвходовых и 2 инвертора). Сравните ее со схемой на рис. 61, для построения которой потребовалось 13 элементов (11 двухвходовых и 2 инвертора).

В общем случае сложность остаточных функций зависит от порядка исключения переменных и оптимальное их исключение ищут специальными методами, основанными на понятии булевой производной:

=f(x₁, x₂,..., x_i-1, 1, x_i+1,..., x_n)Å f(x₁, x₂,..., x_i-1, 0, x_i+1,..., x_n),

где Å – сумма по модулю 2 [9].

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

Например, в импликативном базисе {®, 0}:

=(а®(b®0))®0.