оки3 (1155746), страница 5
Текст из файла (страница 5)
Нижние мощностные оценки33получения нижних мощностных оценок соответствующих функций Шеннона и сложности почти всех ФАЛ. Напомним, что(см. леммы 4.3, 4.4, 6.2, 6.3 из главы 2) для любых натуральных n и L справедливы неравенства: CU (L, n) 6 (8 (L + n))L+1 ,(4.3) ΦU (L, n) 6 (8n)L+1 ,(4.4) KLU (L, n) 6 (8nL) ,(4.5)kUπ (L, n)k 6 (12n)L , ΦU [L, n] 6 (8n)2D .(4.6)(4.7)Лемма 4.1.
Для положительных действительных чиселa, y, q из неравенств(ay)y > q,a log q > 1,(4.8)следует неравенствоlog qy>log (a log q)log log (a log q)1+,log (ae log q)(4.9)где e — основание натуральных логарифмов, а из неравенствa > 1, ay > q — неравенствоy>log q.log a(4.10)Доказательство. Рассмотрим сначала случай, когда a = 1и log q > 1. В этом случае неравенство (4.9) следует из того,что левая часть (4.8) монотонно возрастает по y, и дляy 0 = (1 + ε)log q,log log qгдеε=log log log q,log (e log q)34Глава 3. Синтез и сложность управляющих системсправедливы соотношенияy 0 log y 0 =log q(log log q − log log log q + log e ln (1 + ε)) 6log log qε log elog log log q=+6 log q (1 + ε) 1 −log log qlog log q= log q (1 + ε) (1 − ε) = log q 1 − ε2 6 log q.= (1 + ε)Заметим, что в случае a > 0 неравенство (4.8) эквивалентнонеравенству(ay)ay > q a ,и поэтому неравенство (4.9) получается из неравенства y > y 0в результате замены y на ay и log q на a log q, если выполненоусловие a log q > 1.Неравенство (4.10) в случае a > 1 получается в результате логарифмирования неравенства ay > q и деления обеихчастей полученного неравенства на log a.Лемма доказана.Теорема 4.1.
Для некоторых последовательностей εi =εi (n),где i = 1, . . . , 5 и n = 1, 2, . . ., таких, что εi (n) > 0 приn > n0 и εi (n) стремится к 0 при n стремящемся к бесконечности, для почти всех ФАЛ f , f ∈ P2 (n), выполняются§4. Нижние мощностные оценки35неравенства2n,n2nLΦ (f ) > (1 − ε2 (n)),log n2nLK (f ) > (1 − ε3 (n)) ,n2nπL (f ) > (1 − ε4 (n)),log nD (f ) > n − log log n − ε5 (n).LC (f ) > (1 + ε1 (n))(4.11)(4.12)(4.13)(4.14)(4.15)Доказательство.
Неравенства (4.11)–(4.14) выводятся из соответствующего рассматриваемому классу схем U с функционалом сложности L неравенства (4.3)–(4.6) на основе мощностного неравенства (4.2), где δ = 1/n с использованиемnлеммы 4.1, где q = 22 /n, и1)2)3)4)a = 8,a = 8n,a = 8n,a = 12n,yyyy= LC (n) + n,= LΦ (n) + 1,= LK (n),= Lπ (n),еслиеслиеслиеслиU = UC ;U = UΦ ;U = UK ;U = Uπ .Действительно, подставляя указанные значения в (4.9) по-36Глава 3. Синтез и сложность управляющих системлучим, что доля тех ФАЛ f , f ∈ P2 (n), для которыхC1) L (f ) >>2) LΦ (f ) >3) LK (f ) >>log(n + 3) − o(1)2n1+−n>n+3n+5(4.16)2nlog n − 3 − o(1)1+;nn2n − log n2n3 + o(1)−1>1−;(4.17)log n + 3log nlog n2nlog(n + 3 + log n) − o(1)1+>n + 3 + log nn + 5 + log n2n3 + o(1)1−,nn(4.18)не меньше, чем (1 − 1/n).
Следовательно, неравенство (4.11)((4.12), (4.13)) будет справедливо для достаточно большихn при ε1 (n) = log nn−4 (соответственно ε2 (n) = log4 n , ε3 (n) =4n ).Аналогичным образом устанавливается справедливость(4.14) и (4.15) при ε4 (n) = log6 n = ε5 (n).Теорема доказана.Следствие 1.LC (n) &2n,n2n2n, LK (n) &,log nn2nLπ (n) &.log nLΦ (n) &§5. Метод Лупанова синтеза СФЭ§537Дизъюнктивно-универсальные множествафункций. Асимптотически наилучшийметод О. Б. Лупанова для синтезасхем из функциональных элементовв базисе {&, ∨, ¬}Рассмотрим метод синтеза схем из класса UC , который былпредложен О.Б.
Лупановым [14] и позволил впервые установить асимптотику функции Шеннона LC (n). Этот метод,как и метод Шеннона (см. §3), основан на представленииреализуемой ФАЛ f, f ∈ P2 (n), в виде (3.5) и построенииискомой СФЭ Σf , реализующей ФАЛ f , как суперпозициисхем вида Σf = Σ00 (Σ0 ). При этом схема Σ00 по-прежнему является мультиплексором порядка (n − q) от адресных БПx00 = (xq+1 , . . .
, xn ), а схема Σ0 реализует все ФАЛ видаfσ00 (x0 ), где x0 = (x1 , . . . , xq ) , σ 00 ∈ B n−q , и fσ00 (x0 ) = f (x0 , σ 00 ).Однако, в отличие от метода Шеннона, каждая ФАЛ fσ00 (x0 )берется не с выхода универсального многополюсника от БПx0 , а реализуется на выходе Σ0 как дизъюнкция некоторыхФАЛ, выбранных из специального множества G, G ⊆ P2 (q),реализованного на выходах соответствующей подсхемы схемыΣ0 .Множество ФАЛ G, G ⊆ P2 (m), называется дизъюнктивно-универсальным множеством (ДУМ) порядка m и ранга p, если любая ФАЛ g, g ∈ P2 (m), может быть представлена в видеg = g1 ∨ . . . ∨ gp ,где gi ∈ G при всех i, i = 1, .
. . , p. Стандартный способ построения таких множеств связан с разбиениями единичногокуба.Пусть Π = (π1 , . . . , πp ) — разбиение куба B m , и пусть длявсех i, i = 1, . . . , p, ФАЛ ψi (x1 , . . . , xm ) — характеристическая ФАЛ множества πi , а G(i) — множество всех тех ФАЛ38Глава 3. Синтез и сложность управляющих системg, g ∈ P2 (m), которые обращаются в 0 вне πi . Заметим, чтомножество ФАЛ G видаG = G(1) ∪ . . .
∪ G(p)является ДУМ порядка m и ранга p. Действительно, любаяФАЛ g, g ∈ P2 (m), может быть представлена в видеg = g1 ∨ . . . ∨ gp ,(5.1)где gi = ψi g и, следовательно, gi ∈ G(i) для всех i, i = 1, . . . , p.Заметим также, что мощность множества G(i) , i = 1, . . . , p,равна 2si , где si = |πi |, и что множество G(i) ∩ G(j) состоит из ФАЛ, тождественно равной 0, если 1 6 i < j 6 p.Следовательно,p pXX (i) λ = |G| =2si 6 p2s ,G − (p − 1) 6i=1i=1гдеs = max si .16i6pУказанное ДУМ G будем называть ДУМ, связанным сразбиением Π. Компоненты разбиения Π будем при этом называть полосами ДУМ G, а ФАЛ ψ1 = χδ1 , . . .
, ψp = χδp —его характеристическими ФАЛ. Заметим, что характеристические ФАЛ попарно ортогональны, то есть одновременно в 1 не обращаются, и принадлежат G. Заметим также,что представление (5.1) в случае рассматриваемого ДУМ Gравносильно представлению:g = ψ1 g1 ∨ ψ2 g2 ∨ · · · ∨ ψp gp(5.2)Будем считать стандартным ДУМ порядка m и высоты s, гдеs 62m ,(5.3)§5.
Метод Лупанова синтеза СФЭg1 g2 . . .g2s g2s +1. . .g2s+1 −1 . . . g(p−1)(2s −1)+2. . . gλx1 x2 . . . xm−1 xm... 00 0 01 0 0 ... 0...π1 ............π2 ...πp−1 πp 0 1 ... 10...0...0...00 0 .... . .. . ..
. .0 0 ...1...0...0.........0...00...0.........0...1.........0 0 ... 01...1...0...00 0 .... . .. . .. . .0 0 ...0...0...1.........0...01...0.........0...0...............39......0...0...0...0...0.........0...00...0.........0...0.........0......0 0 .... .
.. . .. . .0 0 ......0 0 ... 00...0...1...1...0 0 .... . .. . .. . .0 0 ...0...0...0.........0...00...0.........1...0.........o2s/o/O...2s −1s=s2...0...O00 0 ... 0...s=s10......Oos2 p −1s=sp−10Osp 6s0/Рис. 5.1: к определению дизъюнктивно-универсальногомножестваДУМ ранга p, p = d2m /se, связанное с разбиением Π =(π1 , . . . , πp ) куба B m на последовательные отрезки, для которого номер любого набора из множества πi меньше номералюбого набора из множества πj , если i < j, и выполнены соотношенияs1 = s2 = · · · = sp−1 = s,sp = 2m − (p − 1) s 6 s.(5.4)Таблица значений ФАЛ ДУМ G приведена на рис. 5.1.40Глава 3.
Синтез и сложность управляющих системИз проведенных построений и отмеченных выше свойствстандартного ДУМ вытекает справедливость следующего утверждения.5.1. Для любых натуральных p, m и s, где p =Лемма2m,существуетстандартное ДУМ G порядка m и высоsты s, которое является ДУМ ранга p и для которого:1) λ = |G| 6 p2s ;2) система из p характеристических ФАЛ ψ1 , .
. . , ψpДУМ G обладает тем свойством, что для любойФАЛ g, g ∈ P2 (m), и соответствующих ФАЛg1 , . . . , gp из G справедливо не только представление(5.1), но и представление (5.2).Теорема 5.1. Для любой ФАЛ f, f ∈ P2 (n), существуетреализующая ее СФЭ Σf , Σf ∈ UC , такая, что2n5 log n + O (1)L (Σf ) 61+.(5.5)nnДоказательство. Пусть x0 = (x1 , . . . , xq ), x00 = (xq+1 , . . . , xn )и fσ00 (x0 ) = f (x0 , σ 00 ) для всех σ 00 из B n−q .
Пусть, далее,Σ00 — мультиплексор порядка (n − q) от адресных БП x00 иинформационных БП y = (y0 , . . . , y2n−q −1 ), который построен в соответствии с леммой 2.3, представляет собой формулуFn−q и реализует мультиплексорную ФАЛ µn−q (x00 , y).Пусть s — некоторый параметр, удовлетворяющий (5.3),а G — стандартное ДУМ порядка m = q и высоты s, удовлетворяющее требованиям леммы 5.1.
Обозначим через ΣG→−СФЭ, которая реализует систему ФАЛ G и представляетсобой объединение схем, построенных для каждой из них всоответствии с леммой 1.2. Заметим, что, в силу леммы 2.3,(1.3) и леммы 5.1, выполнены неравенстваL Σ00 6 4 · 2n−q ,(5.6)L (ΣG ) 6 3p2s+q .§5. Метод Лупанова синтеза СФЭ41Схема Σ0 содержит СФЭ ΣG в качестве подсхемы и реализует каждую ФАЛ fσ00 (x0 ), где σ 00 ∈ B n−q , на одном из своих выходов как ФАЛ g (x0 ) вида (5.1) с помощью СФЭ из(p − 1) ФЭ ∨, входы которой присоединены к соответствующим выходам ΣG .
Искомая СФЭ Σf имеет вид Σf = Σ00 (Σ0 )и реализует ФАЛ f в соответствии с разложением (3.5). Длянее, в силу (5.6), будут выполняться неравенстваL (Σf ) 6 2n−q (p − 1) + L Σ00 + L (ΣG ) 66 2n−q (p − 1) + 4 · 2n−q + 3p2s+q ,из которых, выбрав значения параметровs = dn − 5 log ne ,m = q = d2 log ne ,удовлетворяющие (5.3), в соответствии с леммой 5.1 получим n2n2+O=L (Σf ) 6n − 5 log nn22n5 log n + O (1)=1+.nnТеорема доказана.Следствие. Из (5.5) с учётом следствия из теоремы 4.1вытекает, что2n.LC (n) ∼nОтметим, в заключение, что в соответствии с (5.5) и теоремой 4.1 сложность LC (f ) для почти всех ФАЛ f, f ∈P2 (n), асимптотически равна функции Шеннона LC (n), тоесть сложности самой сложной ФАЛ из P2 (n).
Тем самым,в отличие от класса ДНФ (см. §7 главы 1), в классе схем42Глава 3. Синтез и сложность управляющих системUC имеет место т. н. эффект Шеннона — асимптотическоеравенство сложности почти всех ФАЛ и сложности самойсложной ФАЛ от заданного числа БП, стремящегося к бесконечности.§6Регулярные разбиения единичного куба и моделирование функций переменными. Синтезсхем для некоторых дешифраторов и мультиплексоров.Множество δ, δ ⊆ B q , называется m-регулярным множеством наборов куба B q , если m < q, |δ| = 2m и все префиксы1 длины m наборов из δ различны. Заметим, что mрегулярному множеству δ, δ ⊆ B q , можно взаимнооднозначно сопоставить систему ФАЛ ψ = (ψ1 , . .
. , ψq−m ) из P2q−m (m)так, что набор α = (β, γ), где β ∈ B m и γ ∈ B q−m , принадлежит δ тогда и только тогда, когда ψ (β) = γ. Заметим также, что любая ФАЛ g, g ∈ P2 (q), совпадает наm-регулярном множестве наборов δ, δ ⊆ B q , с некоторойФАЛ из P2 (m), если рассматривать P2 (m) как множествовсех ФАЛ из P2 (q) с несущественными БП xm+1 , . . . , xq . Приэтом любая ФАЛ из связанной с δ системы функций совпадает на δ с соответствующей БП куба B q .Для наборов β = (β1 , . .
. , βq ) и α = (α1 , . . . , αq ) черезβ ⊕ α будем обозначать набор вида (β1 ⊕ α1 , . . . , βq ⊕ αq ).Для множества δ, δ ⊆ B q , и набора α, α ∈ B q , определиммножество δ ⊕ α как множество различных наборов видаβ ⊕ α, где β ∈ δ, то есть множество, получающееся из множества δ сдвигом (параллельным переносом) на набор α.Заметим, что для m-регулярного множества δ, δ ⊆ B q , илюбого набора α, α ∈ B q , множество δ ⊕ α также являетсяm-регулярным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
