Декомпозиция логических схем

Поскольку на этапе декомпозиции требуется уменьшение сложности схемы, необходимо ввести критерий сложности. Абстрактной оценкой сложности схемы будем считать величину.

(бит),.

где — количество входов, а — количество выходов КЛС.

Рис. 1. Логическая схема с входами и выходами.

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

Параллельная декомпозиция

Исходная сложность схемы равна.

(бит).

После разделения сложность схемы составляет.

(бит).

Рис. 2. Параллельная декомпозиция логических блоков.

Разделение будем считать целесообразным, если в результате сложность схемы уменьшается:

(1).

Из выражения (1) следует, что. В этом случае целесообразно выделить параллельный блок. Это означает, что выходов зависят фиктивно от некоторых входов .

Фиктивной называется зависимость выходных сигналов от входных, если при изменении состояния на каком-либо входе логической схемы не происходит изменение состояния на определенном выходе этой схемы.

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

Два числа каждого столбца поразрядно суммируются по модулю два в двоичном коде. После выполнения этой операции над всеми столбцами мы получим двоичных чисел, над которыми затем выполняется поразрядная операция «ИЛИ». В результате получается одно двоичное число, единицы которого отмечают те входы, которые существенно зависят от рассматриваемого входа (по которому проводилось разложение).

Описанная процедура повторяется для каждой из входных переменных и результаты заносятся в специальную таблицу.