Простейшие методы синтеза схем из функциональных элементов
Приведем несколько простейших алгоритмов синтеза схем, реализующих произвольную функцию от [math] n [/math] аргументов [math] f(x_, \ldots, x_) [/math] , в случае когда базис [math] B = \ [/math] .
Содержание
Метод синтеза, основанный на совершенной ДНФ [ править ]
Построим данную схему следующим образом: если [math] i [/math] -й множитель равен [math] \bar_ [/math] , то присоединяем к выходу [math] i [/math] элемент отрицания и последовательно присоединяем к элементу конъюнкции, иначе просто присоединяем к "свободному" входу элемента конъюнкции.
Очевидно, что сложность построенной схемы [math] size_(f)= n+n-1 = 2n-1 [/math] .
Поэтому [math] size_(f)\leqslant 2n-1 [/math] .
Пусть [math] f(x_, \ldots,x_) [/math] — произвольная булева функция.
Если [math] f = 0 [/math] , то схема строится в соответствии с представлением [math] 0=x_\wedge\overline_ [/math] , то есть [math] size_(0) \leqslant 2[/math] .
Если [math] f \ne 0 [/math] , то [math] f [/math] может быть задана дизъюнктивной нормальной формой
[math] f(x_, \ldots,x_) = K_ \vee K_ \vee \ldots \vee K_ [/math] ,
где [math] s \leqslant 2^ [/math] и каждая конъюнкция имеет вид
[math] K_=x_\wedge\overline_\wedge_\wedge \ldots \wedge_ [/math]
Схема [math] S [/math] для [math] f [/math] состоит из конъюнкций [math] K_ [/math] (каждая из них в соответствии с леммой 1 имеет сложность не более [math] 2n-1 [/math] ) и цепочки из [math] s-1 [/math] элемента дизъюнкции с [math] s [/math] свободными входами. Свободные входы этой цепочки присоединяются к выходам схем для конъюнкций [math] K_ [/math] .(рис. 2) Имеем
[math] size_(f)\leqslant s\cdot(2n-1)+s-1 \lt s\cdot(2n-1)+s = 2ns \leqslant n2^ [/math] .
Таким образом, для любой функции [math] f(x_, \ldots,x_) [/math] выполняется неравенство
Метод синтеза, основанный на более компактной реализации множества всех конъюнкций [ править ]
Определение: [math] f(n) \sim g(n) [/math] означает, что [math]f[/math] асимптотически эквивалентна [math]g[/math] , то есть [math]\lim\limits_\dfrac = 1[/math]Определение: [math] f(n) \lesssim g(n) [/math] означает, что [math]\varlimsup\limits_\dfrac \leqslant 1[/math]
Определение: Пусть есть булева функция от [math] n [/math] аргументов [math] f : \lbrace0, 1\rbrace^n \rightarrow \lbrace0, 1\rbrace [/math] и набор из [math] n [/math] булевых функций [math] g_1 \dotsc g_n [/math] , таких что [math] g_i :\lbrace0, 1\rbrace^ \rightarrow \lbrace0, 1\rbrace [/math] , где [math] i=1,\dotsc, n[/math] . Тогда системой булевых функций называется функция [math] S [/math] от всех аргументов функций [math] g_i[/math] , которая определяется как [math] S(x_,\dotsc,x_,x_,\dotsc,x_[/math] [math],\dotsc,x_,\dotsc,x_)[/math] [math]=f(g_1(x_,\dotsc,x_),g_2(x_,\dotsc,x_),\dotsc,g_n(x_,\dotsc,x_))[/math]
[math] x^ = \begin x, \sigma =1;\\ \overline, \sigma =0 \end[/math]
Конъюнкции [math] x_^\wedge\dotsc\wedge x_^[/math] соответствуют функциям [math] g [/math] из определения функции, [math] K_ [/math] соответствует функции [math] S [/math] , а конъюнкция функций [math] g [/math] соответствует функции [math] f [/math] .
Заметим, что на вход схемы подается определенный набор аргументов [math] x_^,\dotsc,x_^ [/math] , то есть на выходе схемы будет результат конъюнкции этих аргументов.
Разделим цепочки конъюнкций на две части. Каждая конъюнкция [math] x_^\wedge\dotsc\wedge x_^ [/math] может быть представлена в виде конъюнкции двух конъюнкций длины [math] k [/math] и [math] n-k [/math] ( [math] k [/math] мы выберем позже):
Поэтому схема для [math] K_ [/math] может быть образована из схем для [math] K_(x_^,\dotsc,x_^) [/math] и [math] K_(x_^,\dotsc,x_^) [/math] и системы из [math] 2^n [/math] элементов конъюнкции, осуществляющих вышеприведенную операцию, как показано в теореме 1 (рис. 3). Левая часть схемы считает конъюнкцию переменных [math] x_^,\dotsc,x_^ [/math] , а правая часть - переменных [math] x_^,\dotsc,x_^[/math] . Следовательно,
[math] size_(K_) \leqslant size_(K_) + size_(K_) + 2^n [/math] .
Так как по теореме 1 [math] size_(K_) \leqslant k2^ [/math] , [math] size_(K_) \leqslant (n-k)2^ [/math] ,то
[math] size_(K_) \leqslant k2^ + (n-k)2^ + 2^n [/math] .
Положим [math] k=[\dfrac][/math] . Тогда [math] k \leqslant \dfrac [/math] , [math] n-k \leqslant \dfrac+1 [/math] и
С другой стороны, при [math] n \geqslant 2 [/math] каждая конъюнкция реализуется на выходе некоторого элемента, то есть при [math] n \geqslant 2 [/math] выполняется неравенство [math] size_(K_) \geqslant 2^ [/math] . Таким образом,
Пусть [math] f(x_, \ldots,x_) [/math] — произвольная булева функция, [math] f \ne 0 [/math] . Заменим в схеме (рис. 2) верхнюю часть схемы, реализующую конъюнкции [math] K_ \vee K_ \vee \ldots \vee K_ [/math] , схемой, реализующей все конъюнкции из [math] K_ [/math] . Тогда для любой такой функции [math] f(x_, \ldots,x_) [/math] (не равной нулю) имеем
[math] size_(f) \leqslant size_(K_)+s-1 \leqslant size_(K_)+2^-1 \lesssim 2^ [/math]
Метод синтеза схем К.Э.Шеннона [1] [ править ]
Пусть [math] f(x_, \ldots,x_) [/math] — произвольная булева функция. Рассмотрим разложение [math] f [/math] по переменным [math] x_, \ldots,x_ [/math] , где [math] 1 \leqslant m \leqslant n [/math] :
Схема для функции [math] f [/math] строится из трех подсхем: [math] S_,S_,S_ [/math] . (рис. 4)
1. Система [math] K_ (x_^,\dotsc,x_^) [/math] содержит всевозможные конъюнкции [math]x_^\wedge\dotsc\wedge x_^[/math] . И схема [math] S_ [/math] реализует все эти конъюнкции. В силу леммы 2 выполняется неравенство [math] size_(S_) \leqslant size_(K_) \lesssim 2^ [/math] . 2. Схема [math] S_ [/math] реализует систему [math] F(x_^, \ldots,x_^) [/math] всех булевых функций от всевозможных наборов переменных [math] x_, \ldots,x_ [/math] . Другими словами, подсхема [math] S_ [/math] вычисляет все булевы функции, зависящие от последних [math] n - m [/math] переменных. В силу теоремы 1 [math] size_(S_) \leqslant (n-m)2^2^ [/math] . 3. Схема [math] S_ [/math] производит "сборку" в соответствии с разложением функции [math] f [/math] : для каждого набора [math] \widetilde=(\sigma_,\dotsc,\sigma_) [/math] реализуется конъюнкция [math] x_^\wedge\dotsc\wedge x_^\wedge f(\widetilde,x_,\dotsc, x_) [/math] ( [math] 2^ [/math] элементов конъюнкции) и образуется дизъюнкция таких конъюнкций ( [math] 2^-1 [/math] элементов дизъюнкции).
Поэтому выполняется неравенство [math] size_(S_) \leqslant 2^ +2^ -1 [/math] . Таким образом,
[math] size_(f) \leqslant size_(S_)+size_(S_)+size_(S_) \lesssim 3 \cdot 2^ +(n-m)2^2^ [/math] .
Положим [math] k=n-m [/math] . Тогда
[math] size_(f) \lesssim 3 \cdot 2^ +k2^2^ [/math] .
Заметим, что второе слагаемое "очень быстро" растет с ростом [math] k [/math] , а первое слагаемое убывает с ростом [math] k [/math] медленней. Поэтому следует взять такое значение [math] k [/math] , при котором первое и второе слагаемые приблизительно равны, и потом немного уменьшить [math] k [/math] . Тогда второе слагаемое "сильно" уменьшится, а первое "не очень сильно" возрастет. Возьмем, например, [math] k=\log_n [/math] . Тогда
[math] 3 \cdot 2^ = 3 \cdot \dfrac [/math] , [math] k \cdot 2^ \cdot 2^=\log_n\cdot (2n)\cdot 2^[/math] ,
то есть получили "слишком много". Возьмем [math] k [/math] на единицу меньше: [math] k=\log_n-1 [/math] . Тогда
[math] 3 \cdot 2^ = 3 \cdot \dfrac \cdot 2 [/math] , [math] k \cdot 2^ \cdot 2^=(\log_n-1)\cdot n\cdot 2^[/math] .
Вспомним теперь, что [math] k [/math] должно быть целым числом, и положим [math] k=[\log_n-1] [/math] . Тогда [math] n-k \lt n- \log_ + 2[/math] ,
[math] 3 \cdot 2^ \lt 12 \cdot \dfrac [/math] , [math] k\cdot 2^\cdot 2^ \leqslant (\log_-1)\cdot n\cdot 2^ [/math] .