Материалы для подготовки к экзамену (2012-2013 учебный год), страница 6

В силу разделительности28Глава 1.КС Σ00 по входам указанная суперпозиция является корректной и поэтому КС Σfдействительно реализует ФАЛ f .Из (4.8) с учётом того, что число контактов в контактном дереве от r БП равно 2r+1 − 2, вытекает неравенствоL Σf 6 2n−q+1 + 2t+n−q+1 + t · 2t+n−q + 2s+1 + O t · 2m+s/2 .Оценка (4.6) получается из последнего неравенства при следующих значенияхпараметровn − 2 log nm = b2 log nc − 1,s=2,2при которых, начиная с достаточно большого n, выполнены все необходимые соотношения и, в частности, неравенства (4.7).Теорема доказана.Следствие. Из (4.6) с учётом нижней оценки (1.18) вытекает соотношение−→ 2n2 log n ± O(1)LКС n =1+.nn§5Асимптотически наилучший метод синтеза СФЭ в произвольном базисе. Асимптотические оценки высокой степени точности для сложности усилительных СФЭ в некоторых базисахИспользуем построенные в §3 ϕ–УМ для синтеза усилительных СФЭ в базисе Б,Б = {Ei }bi=1 .

В силу полноты базиса Б в UФБ существуют формулы F& , F∨ и F¬ ,реализующие ФАЛ x1 · x2 , x1 ∨ x2 и x1 соответственно, которыми мы будем заменять ФЭ базиса Б0 при синтезе схем на основе конъюнктивных и дизъюнктивныхпредставлений.Теорема 5.1 (ср. [3]).

Для любой ФАЛ f , f ∈ UУСБ , существует реализующая еёСФЭ Σf , Σf ∈ UУС,такая,чтоБ2n3 log n + O(1)L(Σf ) 6 ρБ1+.(5.1)nnДоказательство. Найдём среди ФЭ базиса Б, Б = {Ei }bi=1 , элемент Ej , на которомдостигается приведённый вес ρj = ρБ (см. §2), то естьρj =Lj= min ρi = ρБ .kj − 1 ki >2(5.2)Пусть, далее, m, s, t, p — натуральные числа такие, что s — чётное,p = t(kj − 1) + 1,2m2mkj 66p<+ (kj − 1),ss(5.3)(5.4)§5.29а Π = (π1 , . .

. , πp ) — такое разбиение куба B m на последовательные отрезки, что|πi | = si 6 s.(5.5)Построим из t ФЭ Ej бесповторную формулу Ft с p входами, которая имеет видквазиполного l–ярусного, l = dlogk pe, дерева и реализует ФАЛ ϕ(y1 , . . . , yp ). ПустьG, G ⊆ P2 (m), — стандартное ϕ–УМ порядка m, связанное с разбиением Π (см. §3),для которого в силу (5.3)–(5.5)|G| = λ 6 p · 2s .(5.6)Искомая СФЭ Σf строится, как обычно, на основе разложения ФАЛ f (x1 , . . . , xn )по переменным x00 = (xq+1 , . . .

, xn )_f (x0 , x00 ) =Kσ00 (x00 ) · fσ00 (x0 ),(5.7)σ 00 ∈B n−qгде q = m, x0 = (x1 , . . . , xq ), а fσ00 (x0 ) = f (x0 , σ 00 ). При этом для реализации каждойФАЛ fσ00 (x0 ), σ 00 ∈ B n−q , используется её представлениеfσ00 (x0 ) = ϕ(gσ00 ,1 , . . . , gσ00 ,p ),(5.8)где ФАЛ gσ00 ,1 , . . . , gσ00 ,p берутся из множества G.→−Из леммы 3.1 следует, что для системы ФАЛ G можно построить реализующуюm+s/2 , выходами которойеё СФЭ ΣG , ΣG ∈ UУСБ , сложности не более чем c · p · 2являются выходы усилительных ФЭ базиса Б.Пусть, далее, СФЭ Σ0 содержит СФЭ ΣG в качестве подсхемы и для каждого00σ , σ 00 ∈ B n−q , реализует ФАЛ fσ00 (x0 ) в соответствии с (5.8), используя для этогоформулу Fp .

Схема Σf представляет собой суперпозицию вида Σf = Σ0 (Σ00 ), гдеусилительная СФЭ Σ00 — мультиплексор порядка n − q от БП x00 , и реализует ФАЛf в соответствии с (5.7). Сложность построенной СФЭ Σf , Σf ∈ UУСБ , с учётом (5.2)–(5.6) будет удовлетворять неравенствуL(Σf ) 6 Lj · t · 2n−m + O(2n−m + p · 2s + p · 2s/2+m ),(5.9)из которого приm = q = d2 log ne ,n − 3 log ns=22(5.10)и при значениях остальных параметров, определённых из (5.3)–(5.4), следует (5.1).Теорема доказана.Следствие 1.УСLCБ (n) ∼ LБ (n) ∼ ρБ2n.n30Глава 1.Следствие 2.LУСБ00 (n)2n=n3 log n + O(1)1+.nБудем говорить, что разбиение ∆ является подразбиением разбиения D, D == (Y1 , .

. . , Yd ), множества Y , если оно получается из D в результате замены каждойего компоненты Yi , i = 1, . . . , d, её разбинием δi = (Yi,1 , . . . , Yi,di ). При этомH(∆) = −did XX|Yi,j |i=1 j=1|Y |· log|Yi,j |=|Y |did XX|Yi,j ||Yi ||Yi | |Yi,j |=−log=·+ log|Y | |Yi ||Y ||Yi |i=1 j=1didXX|Yi,j | |Yi,j ||Yi ||Yi | =log+log|Y ||Y ||Yi ||Yi |i=1j=1и, следовательно, справедливо равенствоH(∆) = H(D) +dX|Yi |i=1|Y |H(δi ),(5.11)из которого вытекает неравенствоH(∆) 6 log d + max H(δi ).16i6d(5.12)Для разбиения D = (Y1 , .

. . , Yd ) множества Y его спектром будем называтьмножество (сочетание), состоящее из чисел |Y1 |, . . . , |Yd |. Заметим, что два разбиения, спектры которых получаются друг из друга умножением на одно и то жечисло, имеет одинаковую энтропию.Разбиение, спектр которого имеет вид 1, 1, 2, 4, . . . , 2t−1 , где t > 1, будем называть двоично-геометрическим разбиением высоты t.При t > 2 указанное разбиение является, очевидно, подразбиением разбиениясо спектром 2t−1 , 2t−1 и получается из него заменой одной из компонент двоичногеометрическим разбиением высоты (t − 1). В силу (5.11) отсюда следует, что энтропия данного разбиения задаётся формулой 1111+1+...

1 +... ,222где число вложенных пар скобок равно (t−2), и, таким образом, энтропия двоичногеометрического разбиения высоты t, t > 1, равна1+111+ · · · + t−1 = 2 − t−1 .222§5.31e t и её связь с формулой FetРис. 5.1: Структура КС ΣТеорема 5.2. Для любой ФАЛ f , f ∈ P2 (n), существует реализующая её СФЭΣf , Σf ∈ UУС , такая, что2 log n + O(1)2n1+.(5.13)L(Σf ) 6nne = {E1 , E2 } — базис, где ϕ1 (x1 ) = x1 , ϕ2 (x1 , x2 , x3 , x4 ) =Доказательство. Пусть Бe Σe ∈ UУС ,= x1 x3 ∨ x2 x4 и L1 = 1, L2 = 3.

Заметим, что для любой СФЭ Σ,eБe Следосуществует эквивалентная ей СФЭ Σ, Σ ∈ UУС , такая, что L(Σ) = L(Σ).ef , Σe f ∈ UУС ,вательно, для доказательства теоремы достаточно построить СФЭ ΣeБкоторая реализует заданную ФАЛ f и сложность которой не превосходит правойчасти (5.13).e в соответствии с (5.2), где kj =Пусть параметры t и p выбраны для базиса Б= 4, то есть p = 3t + 1. Построим из t ФЭ E2 , соединённых между собой по двумe t с p входами, которая представляетпоследним входам, бесповторную формулу Fсобой l–ярустное, l = dlog(t + 1)e, квазиполное двоичное дерево и реализует ФАЛetϕ(ye 1 , .

. . , yp ). Будем считать, что все t̂, t̂ = t − 2l−1 + 1, ФЭ l-го яруса формулы Fb при ихприсоединены к первым t̂ листьям полного (l − 1)–ярусного поддерева Dестественной нумерации.e t как структурно, так и функционально моделируетсяЗаметим, что формула Feориентированной КС Σt , имеющей вид квазиполного двоичного l-ярусного дереваe t , с 2t контактас (p − 2t) листьями, которые являются «проводящими» входами Σми, которые помечены 2t «управляющими» входами этой КС, и корнем z, которыйявляется выходом КС (см.

рис. 5.1а). При указанном моделировании каждая верe t взаимно однозначно сопоставляется эквивалентной ей вершине v̌шина v КС Σe t так, как это показано на рис. 5.1б.дерева формулы FПусть для каждого i, i = 1, . . . , l, Yi0 и Yi00 — множество тех БП из Y == {y1 , . . . , yp }, которые связаны с двумя первыми и двумя последними входамиФЭ E2 относящихся к i-му ярусу, соответственно.

Заметим, что|Yl0 | = |Yl00 | = 2(t − 2l−1 + 1),00|Yl−1| = t + 1 − |Yl0 | и Yi00 = ∅,|Yv0 | = 2vпри всех i, i < (l − 1), v 6 l − 1.0 и Y 0 — равномощные подмножества, состоящие из тех БППусть, далее, Yi,0i,10множества Yi , i ∈ [1, l], которые связаны с первыми и вторыми входами ФЭ E200 ∪ Y 00 .соответственно, а Y 00 = Yl−1l32Глава 1.Из построения следует, что разбиение D множества Y , где0000D = (Y1,0, Y1,1, .

. . , Yl,0, Yl,1, Y 00 )является селекторным разбиением БП Y ФАЛ ϕ.e Действительно, для полученияe t БП y 00 из Y 00 достаточно для каждого i, i = 1, . . . , l, выбрать такиена выходе Σ0 и Y 0 соответственно, при которых в Σe t образуетсязначения σi и σ i для БП из Yi,0i,1только одна проводящая цепь, соединяющая листья дерева с его корнем, и эта цепьначинается в листовой вершине с пометкой y 00 . Заметим, что при любом i, i ∈ [1, l], и0 , для получениявыбранных значениях всех групп БП, за исключением группы Yi,σie t той БП yj из Y 0 , контакт которой лежит на построенной цепи,на выходе КС Σiдостаточно присвоить всем БП из Y 00 значение 1.b разбиения D, которое получается из него замеРассмотрим подразбиение D000 ,Y 0 ,Yb 00 ), где Y 0 =ной компоненты Y её произвольным разбиением вида (Y0,00,10,0 0 Y = 1.

Положим, далее,0,1Yb00 =l−1[i=00Yi,0,Yb10 =l−1[0Yi,1i=00 ,Y 0 ,Yb 00 ).и пусть Ď — разбиение множества Y на компоненты (Yb00 , Yb10 , Yl,0l,1Поскольку, как это следует из сказанного выше, 0 0 Yi,0 = Yi,1 = 2i−1b является подразбиением разбиения Ď и получаетсядля всех i, i = 1, . . . , l − 1, то Dзаменой двух первых компонент последнего двоично-геометрическими разбиениями высоты (l−1).

Следовательно, в силу (5.11), (5.12) и с учетом того, что энтропиядвоично-геометрических разбиений не более 2, получимb 6 log 5 + 2 6 5.H(D) 6 H(D)e f строится аналогично тому, как строилась СФЭ Σf , при докаИскомая СФЭ Σзательстве теоремы 5.1, с той лишь разницей, что вместо формулы Ft используетсяe t , а ϕ–УМформула FeG порядка m и схема ΣG находятся с использованием разбиения D по теореме 3.1 при значениях параметров p и s, удовлетворяющих еёe f справедливо неравенствоусловиям. При этом для сложности СФЭ Σe f ) 6 3t2n−m + O(2s + 2m+s/2 · log t)L(Σиз которого при следующих значениях параметров:2mm = d2 log ne , s = dn − 2 log ne , t =,3(s − 5)p = 3t + 1,обеспечивающих выполнение условий теоремы 3.1, вытекает (5.13)Теорема доказана.§6.33Следствие.УСL§62n(n) =n2 log n ± O(1)1+.nАсимптотически наилучший метод синтеза формул в произвольном базисе. Асимптотические оценки высокой степени точности для сложности формул в некоторых базисахПри синтезе СФЭ с базисе Б = {ϕi }bi=1 мы использовали (см.

§5) некоторые формулы F& , F∨ и F¬ из UФБ , реализующие ФАЛ x1 ·x2 , x1 ∨x2 и x1 соответственно, длямоделирования конъюнктивных и дизъюнктивных представлений ФАЛ. При этомвозможность такого моделирования и его сложность не налагали на данные формулы каких-либо структурных или параметрических ограничений. В то же времяпри использовании формул F& , F∨ , F¬ для аналогичного моделирования конъюнктивных и дизъюнктивных представлений ФАЛ в классе UФБ необходимо обеспечитьотсутствие «внутренних» ветвлений в получающихся схемах за счёт определенныхограничений на их структуру.Напомним, что БП, встречающаяся в записи формулы только один раз, считается бесповторной БП этой формулы и что формула, все БП (соответственно, всесущественные БП) которой бесповторны, называется бесповторной (соответсвенно, квазибеспоторной).Лемма 6.1.