оки3 (1155746), страница 7
Текст из файла (страница 7)
Действительно, для любой ФАЛ f , f ∈ P2 (n),e f может быть получена на осреализующая ее (1, 1)-КВС Σнове разложения (3.5) так же, как и СФЭ Σf из теоремы 5.1.Она является результатом корректной суперпозиции видаe f = Σ00 (Σ0 ), где Σ00 — (2n−q , 1)-КД от БП x00 , а (1, 2n−q )ΣКВС Σ0 реализует систему всех ФАЛ вида fσ00 (x0 ) , σ 00 ∈B n−q . При этом схема Σ0 по-прежнему содержит в каче→−стве подсхемы (1, λ)-КС ΣG , реализующую систему ФАЛ Gна основе леммы 1.2, и реализует каждую ФАЛ g (x0 ) типаfσ00 (x0 ) на основе ее представления (5.1) в виде дизъюнкцииg = g1 ∨ · · · ∨ gp с помощью присоединения входов вентильной звезды порядка p к соответствующим выходам КС ΣG(см.
рис. 8.1a), которое является корректной суперпозициe f при тех же значенияхей. Сложность построенной КВС Σпараметров, что и в теореме 5.1, будет удовлетворять неравенству (5.5).Напомним (см. §5), что в силу специфики стандартного ДУМ G вместо представления (5.1) для ФАЛ g можноиспользовать эквивалентное (5.1) представление (5.2) видаg = ψ1 · g1 ∨ · · · ∨ ψp · gp(8.1)и на его основе реализовать ФАЛ g с помощью корректной суперпозиции т.н. итеративно-контактных схем, показанной на рис. 8.1b, где ФАЛ ψ1 , . .
. , ψp управляют проводимостью соответствующих контактов. Асимптотически наилучший метод синтеза КС связан с «моделированием» этой52Глава 3. Синтез и сложность управляющих системg1•...ΣG1••&9 g...•gpa)g1•...ΣG1•ψ1...•gψp•gpb)Рис. 8.1: Корректная реализация дизъюнкции ФАЛg1 , . . . , gp в классах КВС и ИКСсуперпозиции и представления (8.1) на компонентах подходящего m-регулярного разбиения куба B m+p .Пусть δ̌ — m-регулярное множество наборов куба B m+p ,→−соответствующее системе ФАЛ ψ = (ψ1 , .
. . , ψp ) (см. рис. 8.2a),а ∆ = (δ1 , . . . , δ2p ) — построенное для нее по лемме 6.1 разбиение куба B m+p . Заметим, что любая ФАЛ g, g ∈ P2 (m + p),на любой компоненте этого разбиения вида δ̌ ⊕ α, гдеα = (0, . . . , 0, αm+1 , . .
. , αm+p ),| {z }mсовпадает с ФАЛααm+pm+1ǧ = xm+1· g1 ∨ . . . ∨ xm+p· gp ,(8.2)§8. Асимптотически наилучший метод синтеза КС. . . xm−1 xm ψ1 x1 0 ... 010... 0101.....π1....1...0...0.....π2....0.........0...0.....πp....1110ψ200...011...1.... .
. ψp00... ...000... ...0... ...00.. . . ..011...1δ̌a)g1•1αm+1xm+1...ΣG•gpǧαm+pxm+pb)Рис. 8.2: m-регулярное множество δ̌ и связанная с нимсуперпозиция КС5354Глава 3. Синтез и сложность управляющих системгде gi = gψi ∈ G(i) , i = 1, . . . , p. При этом ФАЛ ǧ может быть реализована в результате операции присоединенияαm+pαm+1к выходам (1, λ)звезды из контактов вида xm+1, . . .
, xm+p→−КС ΣG , реализующей систему ФАЛ G , так, как это показанона рис. 8.2b. Заметим также, что указанная операция суперпозиции является корректной на множестве наборов δ̌ ⊕ αв силу того, что из контактов присоединяемой (p, 1)-КС налюбом наборе этого множества проводит только один.Теорема 8.1 (ср. [14]). Для любой ФАЛ f , f ∈ P2 (n), существует реализующая ее КС Σf такая, что2n1L (Σf ) 61+O √(8.3)nnДоказательство. Пусть q = m + p, а ∆ = (δ1 , . . . , δ2p ) —описанное выше разбиение куба B q , с помощью которогоФАЛ f можно представить в видеp000f x ,x=2_i=1xx0i_σq+1xq+1· · · xσnn ǧσ00 ,i x0 ,σ 00 =(σq+1 ,...,σn )(8.4)где x — характеристическая ФАЛ δi , а в качестве ФАЛ fσ00 ,iiпри всех σ 00 ,σ 00 ∈ B n−q , и i, i ∈ [1, 2p ], берется ФАЛ ǧσ00 ,i вида(8.2), совпадающая с ФАЛ fσ00 (x0 ) на компоненте δi = δ̌ ⊕ α.Пусть ΣG — (1, λ)-КС, которая реализует систему ФАЛ→−G по их совершенным ДНФ на основе контактного дерева(см.
лемму 1.2 и оценку (1.2)). Для каждого i, i = 1, . . . , 2p ,построим (1, 2n−q )-КС Σ0i (см. рис. 8.3a), которая содержитКС ΣG в качестве подсхемы и реализует каждую ФАЛ ǧσ00 ,iвида (8.2) с помощью корректной на множестве наборовδi суперпозиции, показанной на рисунке 8.2b. Пусть, далее, (1, 2n−m )-КС Σ0 получается в результате отождествления входов у построенных выше КС Σ0i , i ∈ [1, 2p ], и реализует систему из всех ФАЛ вида ǧσ00 ,i , где σ 00 ∈ B n−q , i ∈ [1, 2p ].§8.
Асимптотически наилучший метод синтеза КС55Заметим, что при этом выполняются неравенстваL (ΣG ) 6 λ2m+1 ,L Σ0i 6 L (ΣG ) + p2n−q ,L Σ0 6 p2n−m + λ2q+1 .(8.5)Построим, наконец, каскадную (2n−m , 1)-КС Σ00 , котораяσq+1· · · xσnn , гдереализует столбец из всех ФАЛ вида x (x0 )·xq+1ii ∈ [1, 2p ] и σ 00 = (σq+1 , .
. . , σn ) ∈ B n−q . Эта КС получаетсяв результате объединения 2p схем типа (2n−q , 1)-КД от БПx00 , к выходам которых присоединены входы (2p , 1)-КС, реализующей столбец из ФАЛ x , i ∈ [1, 2p ], и получающейсяiиз (2q , 1)-КД от БП x0 в результате соответствующего отождествления входов (см. рис.
8.3b). Легко видеть, что приэтомL Σ00 6 2q+1 + 2n−m+1 .(8.6)Искомая КС Σf является результатом корректной стыковки вида Σf = Σ00 (Σ0 ), полученной в результате присоединения входов КС Σ00 к выходам КС Σ0 в соответствии спредставлением (8.4), сложность которой, в силу (8.5)–(8.6),удовлетворяет неравенствуL (Σf ) 6 (p + 2)2n−m + (λ + 1)2q+1 .Из этого неравенства при3m=log n2√ и s= n−2 n ,при которых выполнены условия2ms62 , p=smи q = m + p 6 n,56Глава 3. Синтез и сложность управляющих систем• ǧe0,i...1•• ǧσ 00 ,iΣG...• ǧe1,i|{zΣ0i.........xКД(x00 )1•...xКД(x00 )i•x00КД(x )КД(x0 )•...2p•}|a){zΣ00}b)Рис.
8.3: к доказательству теоремы 8.1вытекает неравенство (8.3) для сложности Σf , так как(p + 2)2n−m2n2n6+ 3 · 2n−m =sn(λ + 1)2q+111+O √,n22m+s+p+366 p2s · 2m+p+2 6s√322n√6 2n− n+3 log n = o.sn nТеорема доказана.Следствие. Из (8.3) с учетом нижней оценки (4.13) вытекает, что2n.LK (n) ∼nЗамечание. Построенную КС Σf можно разбить на не более,§9. Синтез схем для функций из специальных классовчем572n√λp · 2 + 2+ (λ + 1)2=On n«звезд», каждая из которых состоит из контактов одногои того же типа.
Для этого достаточно контакты всех звезд,показанных на рис. 8.2b, перераспределить в звезды из однотипных контактов, «центрами» которых являются выходыподсхем ΣG схем Σ0i , i = 1, . . . , 2q−m , а любой из остальныхконтактов КС Σf считать отдельной звездой.p§9n−m+1q+1Задача синтеза схем для функций из специальных классов. Асимптотически оптимальные методы синтеза схем из функциональных элементов и контактных схем для функций из некоторых классовМощностные соображения можно использовать при получении нижних оценок для функций Шеннона, связанных с реализацией ФАЛ из класса Q, Q = Q (1) , Q (2) , .
. .. . . , Q (n) , . . . , гдеQ ⊆ P2 и Q (n) = Q ∩ P2 (n) 6= ∅,n = 1, 2, . . . .Пусть U — один из рассмотренных в главе 2 классов схем,Ψ — введенный там функционал сложности, а Ψ (Q (n)) —функция Шеннона (для класса схем U относительно функционала сложности Ψ), связанная с классом ФАЛ Q, то естьΨ (Q (n)) = max Ψ (f ) .f ∈Q(n)Следующее «мощностное» неравенство обобщает равенство (4.1)и вытекает непосредственно из определений:kU (Ψ (Q (n)) , n)k > |Q (n)| .(9.1)58Глава 3. Синтез и сложность управляющих системОно позволяет получить нижнюю оценку функции Шеннона Ψ (Q (n)) на основе известной верхней оценки величиныkU (Ψ, n)k.Рассмотрим, в частности, нижние мощностные оценкидля функций LC (Q (n)) и LK (Q (n)), то есть функций Шеннона для сложности реализации ФАЛ из класса Q схемамииз классов UC и UK соответственно.
На основе мощностныхсоображений (см. (9.1)) аналогично тому, как это было сделано в теореме 4.1 для случая Q = P2 , доказывается следующее утверждение.Лемма9.1. Для класса ФАЛ Q такого, что n =log|Q(n)|= o log log|Q(n)| (log n = o (log log |Q(n)|)), выполняются следующие асимптотические неравенстваLC (Q (n)) &(соответственноlog |Q (n)|,log log |Q(n)|LK (Q (n)) &(9.2)log |Q (n)|).log log |Q(n)|(9.3)Пусть, например, класс Q состоит из всех ФАЛ, симметричных по первым двум БП.
Легко видеть, что при этом3 n|Q (n)| = 2 4 2 , так как f ∈ Q(n) тогда и только тогда, когдавторая и третья четверти столбца значений αef совпадают.Следовательно, в силу леммы 9.1, отсюда вытекает, чтоLC (Q(n)) &3 2n· ,4 nLK (Q (n)) &3 2n· .4 n(9.4)Описанные в §§5, 7, 8 асимптотически наилучшие методысинтеза схем ориентированы, вообще говоря, на произвольную или самую «сложную» ФАЛ.
Тем не менее, во многихслучаях они служат основой асимптотически наилучших методов синтеза СФЭ и КС для ФАЛ из заданного специально-§9. Синтез схем для функций из специальных классов59го класса Q и позволяют установить для этого класса «стандартные» (см. (9.2) и (9.3)) асимптотики видаLK (Q(n)) ∼ LC (Q(n)) ∼log log |Q(n)|.log |Q(n)|(9.5)Заметим, что асимптотики (9.5) устанавливаются, как правило, путем сведения задачи синтеза СФЭ или КС для любой ФАЛ из Q(n) к задаче синтеза соответствующей схемыдля системы из одной или нескольких произвольных ФАЛот меньшего числа БП.
При этом требуется, чтобы двоичный логарифм числа тех систем ФАЛ, к реализации которых сводится реализация ФАЛ из Q(n), был асимптотическиравен log |Q(n)|, а сложность вспомогательных ФАЛ, обеспечивающих данное сведение, была бы существенно меньшеправой части (9.2) или (9.3).Возьмем в качестве примера введенный выше класс ФАЛQ, состоящий из всех ФАЛ, симметричных по первым двумБП, и докажем, чтоLC (Q (n)) .3 2n· ,4 nто есть, с учетом (9.4), установим для него асимптотику (9.5)вида3 2nLC (Q (n)) ∼ · .4 nДействительно, разлагая ФАЛ f (x1 , .
. . , xn ) из Q (n) по БПx1 , x2 , получим_f x1 , x2 , x0 =xσ1 1 xσ2 2 fσ1 ,σ2 x0 ,(9.6)(σ1 ,σ2 )∈B 2где x0 = (x3 , . . . , xn ) и fσ1 ,σ2 (x0 ) = fσ1 ,σ2 (σ1 , σ2 , x0 ), причемf01 = f10 в силу симметричности ФАЛ f по БП x1 , x2 . Искомая СФЭ Σf реализует ФАЛ f в соответствии с (9.6) и имеет60Глава 3.
Синтез и сложность управляющих системвид Σf = Σ00 (Σ0 ), где Σ00 — мультиплексорная СФЭ порядка2 от адресных БП x1 , x2 , а СФЭ Σ0 от БП x0 реализует асимптотически наилучшим способом ФАЛ f00 , f01 = f10 и f11 отБП x0 . Легко видеть, что сложность построенной схемы Σfnасимптотически не больше, чем 43 2n . Аналогичным образомдоказывается, чтоLK (Q(n)) ∼3 2n.4 nДля класса ФАЛ Q введём «мощностную» последовательностьlog |Q(n)|σQ (n) =,2nгде n = 1, 2, .
. . . При этом из определения следует, что 0 6σQ (n) 6 1 для всех n, n = 1, 2, . . . . Класс ФАЛ Q называетсяненулевым классом ФАЛ, если limn→∞ σQ (n) > 0.В работах С. В. Яблонского (см., например, [31]) было предложено широкое семейство «естественных» классовФАЛ, названных им инвариантными классами. Рассмотримследующие операции над ФАЛ:1) добавление и изъятие фиктивных БП (переход к равной ФАЛ);2) переименование БП без отождествления (переход кконгруэнтной ФАЛ);3) подстановка констант 0, 1 вместо БП (переход к подфункции).Множество ФАЛ Q, Q ⊆ P2 , называется инвариантнымклассом ФАЛ, если оно замкнуто относительно трёх указанных операций. Множества {0}, {1}, {0, 1} называются тривиальными инвариантными классами.
Если инвариантный§9. Синтез схем для функций из специальных классов61класс Q не является тривиальным, то Q ⊇ {0, 1}, поскольку Q содержит неконстантую функцию, из которой при помощи операции 3 можно получить обе константы. Отметим,что если класс Q замкнут по суперпозиции и {0, 1} ⊆ Q,то класс Q является инвариантным. Примерами инвариантbных классов могут, следовательно, служить классы M и Lвсех монотонных и всех линейных ФАЛ соответственно. Приэтом класс самодвойственных функций, а также классы T0и T1 — классы сохранения констант 0 и 1 соответственно, —не являются инвариантными (они не замкнуты относительно операции 3). Класс всех симметрических ФАЛ также неявляется инвариантным, так как он не замкнут относительно операции 1. При этом инвариантным является класс Sb —класс квазисимметрических ФАЛ, то есть функций, симметрических по всем своим существенным переменным.Лемма 9.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
