Метод каскадов

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

В основе метода лежит теорема Шеннона:

Теорема Шеннона: Любая, отличная от тождественного нуля логическая функция f(x₁,…,x_n) представима в виде

Функции f(x₁,…,x_i-1,1,x_i+1…,x_n) и f(x₁,…,x_i-1,1,x_i+1…,x_n) получаются подстановкой в f(x₁,…,x_n) вместо переменной x_i значений 1 и 0, соответственно. Размерность этих функций на 1 меньше исходной. Функции f(x₁,…,x_i-1,1,x_i+1…,x_n) и f(x₁,…,x_i-1,1,x_i+1…,x_n) называют остаточными функциями при разложении f(x₁,…,x_n) по переменной x_i единичной и нулевой, соответственно. В дальнейшем, эти функции для краткости будут обозначаться как и , соответственно.

В общем виде теорема Шеннона формулируется следующим образом:

Это означает, что при разложении функции по k-переменным получается 2^k остаточных функций, каждая из которых зависит от n-k переменных.

Следствие из теоремы Шеннона: Предельное разложение функции по n-переменным является совершенная дизъюнктивная нормальная форма (СовДНФ).

Действительно, разложение Шеннона будет представлено дизъюнкцией конституент, каждая из которых конъюнктивно связана с остаточной функцией-константой. Функция константа принимает имеет значение 1, если соответствующая ей конституента является единичной, и 0 – в противном случае.

Для краткости разложение Шеннона по одной переменной представляется как . Если предположить, что имеется конструктивный блок, реализующий это представление (блок исключения переменной - БИП), его внутренняю структура в классическом базисе должна иметь следующий вид:

Метод каскадов можно представить как процедуру последовательного исключения переменных:

- на первом шаге – из исходной функции исключается некоторая переменная, которая подается к левому входу БИПа, а к нижним соответствующим входам БИПа подключаются единичная и нулевая остаточные функции по этой переменной;

- далее к каждой остаточной функции применяется указанная в предыдущем шаге последовательность действий.

Указанная процедура применяется до тех пор, пока размерность остаточных функций не будет превышать 2. Такие простые функции целесообразно синтезировать не методом каскадов, а методом непосредственного моделирования в заданном логическом базисе.

Замечания:

1. Исходная функция для метода каскадов может быть задана в любом виде (ее минимизация или приведение к какому-либо стандартному виду не требуется)