оки3 (1155746), страница 6
Текст из файла (страница 6)
Если при этом ν (α) < 2q−m , то есть1Для слова (набора) α вида α = βγ слово β (γ) считается его префиксом (соответственно суффиксом).§6. Регулярные разбиения единичного куба43α = (0, . . . , 0, γ),| {z }mгде γ = (γ1 , . . . , γq−m ) и ν (γ) = ν (α), а множество наборовδ соответствует системе ФАЛ g = (g1 , . . . , gq−m ), то множество наборов δ ⊕ α будет соответствовать системе ФАЛ(g1 ⊕ γ1 , . .
. , gq−m ⊕ γq−m ), получающейся из системы g инвертированием некоторых ФАЛ.Лемма 6.1. Для любых натуральных m, λ и q = m + λ идля любой системы ФАЛ g = (g1 , . . . , gλ ) из P2λ (m) существует m-регулярное разбиение ∆ = (δ1 , . . . , δ2q−m ) куба B qтакое, что любая ФАЛ gi на любой компоненте δj совпадает либо с одной из БП xm+1 , . . .
, xq , либо с её отрицанием.Доказательство. Пусть δ = δ1 — m-регулярное множество,соответствующее системе ФАЛ g = (g1 , . . . , gλ ), и пусть δi =δ1 ⊕ α, где ν(α) = i − 1, для всех i, i = 1, . . . , 2q−m . Из построения системы множеств ∆ = (δ1 , . .
. , δ2q−m ) следует, чтокаждое из них обладает требуемым свойствами, связаннымис можелированием ФАЛ из g с помощью БП.Покажем теперь, что ∆ — покрытие куба B q . Для этоговозьмем произвольный набор из B q вида (β, γ), где β ∈ B mи γ ∈ B q−m , а по нему найдем в множестве δ набор вида(β, γb), который имеется в δ в силу m-регулярности этогомножества.
Следовательно,(β, γ) = (β, γb) ⊕ (0, . . . , 0, γb ⊕ γ) = (β, γb) ⊕ α,| {z }m2q−m .где ν (α) <Таким образом, система ∆ образует поmкрытие куба B .С другой стороны, из m-регулярности δ следует m-регулярность любого из множеств δi , i = 1, . . . , 2q−m , и поэтомуq−m2X|δi | = 2m 2q−m = 2q .i=144Глава 3. Синтез и сложность управляющих системСледовательно, система ∆ образует разбиение куба B q .Лемма доказана.Применим технику моделирования ФАЛ переменнымидля синтеза некоторых дешифраторов и мультиплексоров.Лемма 6.2 (ср.
[14]). Для n = 1, 2, 3, . . . выполняются неравенства n− 2К →nLQn 6 2 + O,(6.1)n n− 2n+1К →Jn 62+O.(6.2)LnДоказательство. Выберем параметры m, q и λ так, чтоλ = 2m ,q = m + λ и q 6 n,а затем рассмотрим m-регулярное множество наборов δ1 куба B q от БП x0 = (x1 , . . . , xq ), связанное с системой ФАЛ→−Q m (x1 , . . . , xm ), которая состоит из всех ЭК вида xσ1 1 · · · xσmm ,где ν(σ1 , . . . , σm ) = j − 1, j ∈ [1, λ].Построим для этой системы по лемме 6.1 разбиение ∆ =(δ1 , . .
. , δ2q−m ) куба B q и заметим, что любая ЭК K(x0 ) =σxσ1 1 · · · xq q , где σ 0 = (σ1 , . . . , σq ) ∈ δi , совпадает на множестве→−δi с одной из ЭК системы Q m , то есть совпадет на нем сα 0буквой xj σ0 , где m + 1 6 jσ0 6 q, ασ0 ∈ B.
Заметим, что вσсилу указанных выше свойств разбиения ∆ любая ЭК K =xσ1 1 · · · xσnn , где σ 0 = (σ1 , . . . , σq ) ∈ δi , 1 6 i 6 2λ , может бытьпредставлена в видеαK = χi (x0 ) · xj σ0 · Kσ00 (x00 ),σ0(6.3)где x00 = (xq + 1, . . . , xn ), σ 00 = (σq+1 , . . . , σn ).Пусть, далее, (1, 2λ )-КС Σ0 = Σ0 (a; b1 , . . . , b2λ ) реализует−0строку из ФАЛ →χ = (χ1 , . . . , χ2λ ), где χλi(x ) — характеристическая ФАЛ множества δi , i ∈ 1, 2 , и получается в§6. Регулярные разбиения единичного куба45результате отождествления входов у схем Σ01 , .
. . , Σ02λ , гдеπ-схема Σ0i , i ∈ [1, 2λ ], построена по лемме 1.2 для ФАЛ χi ,и является ККС сложности не больше, чем q · 2m , с входом ai = a и выходом bi — корнем соответствующего КД(см. рис. 6.1).→−(&)Искомая (1, 2n )-КС Σn реализует каждую ЭК из Q n всоответствии с (6.3), имеет вид, показанный на рис. 6.1, иявляется ККС.Полагаяm = dlog ne − 2,получим, чтоλ = 2m 6n,2q = m + λ 6 n.(&)При этом сложность построенной (1, 2n )-КС Σn , являющейся контактным дешифратором порядка n, удовлетворяет неравенствам: n2(&)n−mn−m+1qnL Σn6 λ2+2+ q2 6 2 + O,nиз которых вытекает неравенство (6.1).(∨)Искомая (1, 2n )-КС Σn , являющаяся дизъюнктивнымконтактным дешифратором порядка n, сложность которогоудовлетворяет оценке (6.2), получается в результате перехо(&)да от ККС Σn к инверсной ККС.Лемма доказана.Следствие.
Оценки леммы 6.2, следствия из леммы 2.2 иследствия из леммы 2.4 дают асимптотические равенства→− →−LК Q n ∼ 2n ,LK ( J n ) ∼ 2n+1 .46Глава 3. Синтез и сложность управляющих системsРис. 6.1: к доказательству леммы 6.2Лемма 6.3. Для n = 1, 2, . . . выполняются неравенства n n22πnCn, L (µn ) 6 2 · 2 + O,L (µn ) 6 2 · 2 + OnnD(µn ) 6 n + 6,причем существует такая реализующая ФАЛ µn и бесповторная по информационным БП формула Mn с поднятыми отрицаниями, глубина которой удовлетворяет последнему из них, альтернирование не больше 3, а сложностьне превосходит 7 · 2n .Доказательство. Искомая π-схема Σn получается в резуль(&)тате присоединения к каждому из выходов (1, 2n )-КС Σn ,§6. Регулярные разбиения единичного куба47построенной при доказательстве леммы 6.2, контакта соответствующей ему информационной БП и отождествленияконцевых вершин всех таких контактов в выходную вершину Σn .
Искомая СФЭ Sn получается из формулы с поднятыми отрицаниями Fn , которая моделирует π-схему Σn(см. §4 гл. 2), в результате применения операций приведения (см. §1) для вершин, соответствующих ФЭ ¬.Для завершения доказательства леммы на основе разбиения ∆, введенного в лемме 6.2, и представления (6.3) построим для ФАЛ µn формулу F̃n следующим образомF̃n (x1 , . .
. , xn , y0 , . . . , y2n −1 ) =2λ__ α 0(6.4)=Ai x0 & & Jσ00 (x00 ) ∨xj σ0 yν(σ0 ,σ00 ) σi=1σ 00 ∈B n−qσ 0 ∈δiгде Ai — совершенная ДНФ ФАЛ χi , i = 1, . . . , λ, и Jσ00 (x00 ) =K σ00 (x00 ). Легко видеть, что F̃n реализует мультиплексорнуюФАЛ µn , бесповторна по БП y0 , . . . , y2n −1 и что Alt (F̃n ) 6 3.Пусть, далее, формула Mn получается в результате оптимизации формулы F̃n по глубине. Тогда приl n mn > 3 и m = log3сложность и глубина Mn будут удовлетворять условиям леммы. Действительно, если1 n > 6, то q 6 n − m и, следовательно, e n = 2q−m q · 2m + 2n−q (n − q) + 2m+1 6R F6 2n+1 + n · 2n−m 6 2n+1 + 3 · 2n = 5 · 2n .При этом, очевидно,L¬ (F̃n ) 611R(F̃n ) − 2n 6 2n+12Случай n 6 5 рассматриваются отдельно.48Глава 3.
Синтез и сложность управляющих системи, таким образом,L(F̃n ) 6 R(F̃n ) + L¬ (Fn ) − 1 6 7 · 2n − 1,откуда в силу теоремы 2.1 главы 2 следует, что D(Mn ) 6n + 6.Лемма доказана.Следствие. Из полученных оценок в силу следствий излеммы 2.5 вытекает, чтоLС (µn ) ∼ 2n+1 ,§7D(µn ) = n + O(1).Асимптотически наилучший метод синтезаформул в базисе {&, ∨, ¬}. Поведение функции Шеннона для глубины ФАЛ.Применим технику моделирования ФАЛ из ДУМ переменными для синтеза формул в стандартном базисе.Теорема 7.1 (ср.
[14]). Для любой ФАЛ f , f ∈ P2 (n), в UΦсуществует реализующая ее формула Ff , для которой2n2 log log n + O (1)L (Ff ) 61+,(7.1)log nlog nD (Ff ) 6 n − log log n + 8 + o (1) .(7.2)Доказательство. Пусть параметры m, s и p удовлетворяютсоотношениям m2ms62 , p=, m + p · 2s 6 n,sа G — стандартное ДУМ порядка m и высоты s, для которого |G| = λ 6 p · 2s (см. §5). Пусть, далее, q = m + λ и,следовательно, q 6 n, а ∆ = (δ1 , . . . , δ2λ ) — разбиение куба→−B q , полученное по лемме 6.1 для системы ФАЛ G .§7.
Асимптотически наилучший метод синтеза формул 49Положим x0 = (x1 , . . . , xq ) и заметим, что произвольнаяФАЛ h, h ∈ P2 (q), на любой компоненте δi , i ∈ [1, 2λ ], в силуее m-регулярности совпадает с некоторой ФАЛ ĥ(x1 , . . . , xm ).При этом ФАЛ ĥ равна дизъюнкции p ФАЛ из ДУМ G, каждая из которых в силу леммы 6.1 совпадает на δi с буквойодной из БП xm+1 , .
. . , xq . Следовательно, ФАЛ h совпадаетна δi с ЭД ранга p от указанных БП.Для ФАЛ f (x) из P2 (n), где x = (x1 , . . . , xn ), x00 =(xq+1 , . . . , xn ) рассмотрим ее представление в видеf (x) =σ_=q+1xq+1· · · xσnn σ 00 =(σq+1 ,...,σn )=2q−m_i=12q−m_i=1xix0 fσ00 x0 =x0ix _σq+1xq+1· · · xσnn Jσ00,i x , (7.3)0σ 00 =(σq+1 ,...,σn )где x (x0 ) — характеристическая ФАЛ множества δi , i = 1, . . .
, 2q−m ,iа ЭД Jσ00,i ранга p от БП xm+1 , . . . , xq , совпадает на δi с ФАЛfσ00 (x0 ) = f (x0 , σ 00 ).e f с подПостроим для ФАЛ f на основе (7.3) формулу Fнятыми отрицаниями, которая имеет видλef =F2_Ai (x0 )Mn−q x00 , Je0,i , . . . , Je1,i ,i=1где Mn−q (x00 , y0 , . . . , y2n−q −1 ) — бесповторная по информационным БП формула из леммы 6.3, реализующая ФАЛ µn−q ,а Ai , i ∈ [1, 2λ ], — совершенная ДНФ ФАЛ x .ib f получается из формулы Fe f опПусть, далее, формула Fтимизацией по глубине (см.
§2 гл. 2), а формула Ff — оптимизацией ЭД по числу отрицаний, то есть заменой каждой50Глава 3. Синтез и сложность управляющих системЭД Jσ00 ,i вида xj1 ∨. . .∨xjt ∨xjt+1 ∨. . .∨xjp , где t 6 p, формулой Jbσ00 ,i вида xj1 ∨ . . . ∨ xjt ∨ xjt+1 · · · xjp , что увеличивает глубину не больше, чем на 1. Заметим, что число ФЭ ¬во всех формулах Ai , i ∈ [1, 2λ ], равно половине их суммарного ранга, что в каждой формуле вида Jbσ00 ,i имеетсяодин ФЭ ¬, и напомним (см. лемму 6.3), что Alt (Mn−q ) 6 3,R(Mn−q ) 6 5 · 2n−q и L¬ (Mn−q ) 6 2 · 2n−q . Следовательно, всилу леммы 2.1 главы 2,L&,∨ (Ff ) 6 2q−m q · 2m + (p − 1)2n−q + 5 · 2n−q , (7.4)L¬ (Ff ) 6 q · 2q−1 + 3 · 2n−m .(7.5)Выбирая значения параметров m и s так, чтоm = b3 log log nc − 1,s = blog n − 2 log log nc − 1,и подставляя эти значения в (7.4), (7.5), получим неравенство n 2n2L (Ff ) 6+O,log n − 2 log log nlog2 nиз которого для сложности формулы Ff следует оценка (7.1).При этом из (7.1), учитывая то, что b f ) 6 2L(Ff ), D(Ff ) 6 D(Fb f ) + 1 и Alt Fb f 6 6,L(Fс помощью теоремы 2.1 из §2 главы 2 непосредственно выводится неравенство (7.2).Теорема доказана.Следствие.
Из (7.1) и (7.2), с учетом нижних оценок,следствия из леммы 9.1, вытекает, чтоLΦ (n) ∼2n,log nD (n) = n − log log n ± O (1) .§8. Асимптотически наилучший метод синтеза КС§851Асимптотически наилучший метод синтезаконтактных схемЗаметим сначала, что асимптотически наилучший метод синтеза СФЭ из §5 без существенных изменений переносится накласс контактно-вентильных схем (КВС), в которых нарядус контактами можно использовать «вентили», то есть ориентированные ребра, проводящие только в направлении своейориентации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
