больше вес вектора, тем выше уровень, на котором он находится. Каждая пара
векторов, различающихся значением одного разряда, соединяется короткой
линией.
На рис. 4.2.3 показан пример сети для функции четырех переменных.
2. На шагах 2 и 3 каждому вектору V= (x
1
, ..., х
п
) сети присваивается
метка L(V), которая на рисунке указана без скобок.
Вначале определяется значение функции f, которое соответствует
вектору (11...1), имеющему вес п, в верхнем узле, и присваивается ему в
качестве метки L(ll...l). Если вектор верхнего узла является фиктивным, ему
присваивается значение метки, равное 0.
3. Закончив присваивание L(V) всем векторам с весом w, где 0<
n
,
присвоить L(V') каждому вектору V с весом w—1, равное минимальному
двоичному числу, удовлетворяющему следующим условиям.
1. Если значение f(V') не является фиктивным, то
а) значение младшего бита L(V') приравнивается значениюf(V);
б) остальные биты L{V) должны быть определены таким образом,
чтобы неравенство L(V') L(V) выполнялось для каждого вектора V с весом w,
отличающегося от вектора V значением только одного разряда.
≤
2. Если f(V) является фиктивным, должно выполняться только условие
б. (Следовательно, значение младшего разряда L(V) определяется таким
образом, чтобы удовлетворялось условие б.)
Например, L(1110) = 10 для вектора V= (1110), так как значение
младшего разряда должно быть равно нулю [f(1110) =0] по условию а, и это
число должно быть равно или больше 1 по условию б. Аналогично для вектора
V’=(1000) получаем L(1000) = 100,. потому что значение последнего разряда
должно быть равно нулю [f(1000)=0] по условию а, а число должно быть равно
или больше чисел 10, 11 и 11, присвоенных по условию б трем узлам: (1100),
(1010) и (1001) соответственно.
4. Повторять шаг 3 до тех пор, пока вектору нижнего уровня (00...0) не
будет присвоено значение L(00...0). Количество разрядов в метке L(00...0)
определяет минимальное количество МОП-ячеек, необходимых для реализации
функции f. Обозначим его через R. Преобразовать все ранее полученные
значения L(V) в двоичные числа той же длины, что и L(00...0), добавлением к
ним слева нулей. Например, L(ll...l)=l, полученное для верхнего узла,
преобразуется в 001 (рис. 4.2.3)
Этап 2
Определим теперь логику работы МОП-ячеек, исходя из значений L(V),
найденных на этапе 1.
1. Установить i=0 (смысл величины i будет пояснен ниже).
2. Обозначить каждое L(V), полученное на этапе 1, через L(V) = (u
1
,...,u
R
).
Для каждого L(V), имеющего u
1+i
= 0, сформировать новый вектор L(V)
= (u
1
,...,u
i
).
В качестве примера рассмотрим вначале случай, когда i=l {он несколько
проще, чем случай, когда i=0). Тогда для L(llll)=001, так как u
2
=0, формируется
99