Теормин (все билеты, кроме 12-14) (Мадорский) (1133375), страница 5
Текст из файла (страница 5)
Синтезсхем для некоторых дешифраторов и мультиплексоров.Множество δ, δ ⊆ B q , называется m-регулярным множеством наборов куба B q , если m < q, |δ| = 2m и все префиксы1 длины m наборов из δ различны. Заметим, что mрегулярному множеству δ, δ ⊆ B q , можно взаимнооднозначно сопоставить систему ФАЛ ψ = (ψ1 , . . . , ψq−m ) из P2q−m (m)так, что набор α = (β, γ), где β ∈ Bm и γ ∈ Bq−m, принадлежит δ тогда и только тогда, когда ψ (β) = γ.Лемма 6.1. Для любых натуральных m, λ и q = m + λ идля любой системы ФАЛ g = (g1 , . . . , gλ ) из P2λ (m) существует m-регулярное разбиение ∆ = (δ1 , .
. . , δ2q−m ) куба B qтакое, что любая ФАЛ gi на любой компоненте δj совпадает либо с одной из БП xm+1 , . . . , xq , либо с её отрицанием.Лемма 6.2 (ср. 1,n2,3, . . . выполняются нера Для n =−[14]).2nвенства LК →Qn 6 2 + O,n n− 2n+1К →Jn 62+OL.nСледствие.
Оценки леммы 6.2, следствия из леммы 2.2 иследствия излеммы2.4 дают асимптотические равенства− −→К →Q n ∼ 2n ,LK ( J n ) ∼ 2n+1 .LЛемма 6.3. Для n = 1,n 2, . . . выполняются неравенства n22CnπnL (µn ) 6 2 · 2 + O, L (µn ) 6 2 · 2 + O,nnD(µn ) 6 n + 6,причем существует такая реализующая ФАЛ µn и бесповторная по информационным БП формула Mn с поднятыми отрицаниями, глубина которой удовлетворяет последнему из них, альтернирование не больше 3, а сложностьне превосходит 7 · 2n .Следствие. Из полученных оценок в силу следствий излеммы 2.5 вытекает, что LС (µn ) ∼ 2n+1 , D(µn ) = n + O(1).21Асимптотически наилучший метод синтезаформул в базисе {&, ∨, ¬}. Поведение функцииШеннона для глубины ФАЛ.Теорема 7.1 (ср. [14]).
Для любой ФАЛ f , f ∈ P2 (n), в UΦсуществует реализующая ее формула Ff , для которой2 log log n + O (1)2n1+,L (Ff ) 6log nlog nD (Ff ) 6 n − log log n + 8 + o (1) .Следствие. Из (7.1) и (7.2), с учетом нижних оценок,следствия из леммы 9.1, вытекает, что2nLΦ (n) ∼, D (n) = n − log log n ± O (1) .log n22Асимптотически наилучший метод синтезаконтактных схемТеорема 8.1 (ср. [14]). Для любой ФАЛ f , f ∈ P2 (n), существует реализующая ее КС Σf такая, что2n1L (Σf ) 61+O √nnСледствие. Из (8.3) с учетом нижней оценки (4.13)2nвы-текает, чтоLK (n) ∼.n23 Задача синтеза схем для функций из специальных классов. Асимптотически оптималь-ные методысинтеза схем из функциональ-ных элементов и контактныхсхем для функ-ций из некоторых классовСледующее «мощностное» неравенство обобщает равенство (4.1)и вытекает непосредственно из определений:kU (Ψ (Q (n)) , n)k > |Q (n)| .Оно позволяет получить нижнюю оценку функции Шеннона Ψ (Q (n)) на основе известной верхней оценки величиныkU (Ψ, n)k.Лемма 9.1.
Для класса ФАЛ Q такого, что n == o loglog|Q(n)|log|Q(n)| (log n = o (log log |Q(n)|)), выполняются следующие асимптотические неравенстваlog |Q (n)|log |Q (n)|).LC (Q (n)) &, (соотв. LK (Q (n)) &log log |Q(n)|log log |Q(n)|Следовательно, в силу леммы 9.1, отсюда вытекает, что3 2n3 2nLK (Q (n)) & · .LC (Q(n)) & · ,4 n4 nВозьмем в качестве примера введенный выше класс ФАЛQ, состоящий из всех ФАЛ, симметричных по первым двумnБП, и докажем, что LC (Q (n)) . 3 · 2 ,4 nто есть, с учетом (9.4), установим для него асимптотику (9.5)3 2nвидаLC (Q (n)) ∼ · .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.Рассмотрим следующие операции над ФАЛ:1) добавление и изъятие фиктивных БП (переход к равной ФАЛ);2) переименование БП без отождествления (переход кконгруэнтной ФАЛ);3) подстановка констант 0, 1 вместо БП (переход к подфункции).Множество ФАЛ Q, Q ⊆ P2 , называется инвариантнымклассом ФАЛ, если оно замкнуто относительно трёх указанных операций. Множества {0}, {1}, {0, 1} называются тривиальными инвариантными классами.При этом инвариантным является класс Sb — классквазисимметрических ФАЛ, то есть функций, симметрических по всем своим существенным переменным.Лемма 9.2.
Пусть Q — инвариантный класс ФАЛ. Тогдаего мощностная последовательность σQ (n) монотонно невозрастает и сходится к пределуlog |Q(n)|σQ = lim σQ (n) = lim,n→∞n→∞2nгде число σQ удовлетворяет неравенствам 0 6 σQ 6 1.Лемма9.3. Для всякого инвариантного класса Q и n =1,2,... 2n 2nLC Q(n) ∼ σQпри σQ>0, LC Q(n) = o σQпри σQ=0.nn24Задача эквивалентных преобразований схемна примере формул. Полнота системы основных тождеств для эквивалентных преобразований формул базиса {&, ∨, ¬}Эквивалентные преобразования (ЭП), то есть преобразования, не изменяющие функционирования схем.et: F=FСчитается, что тождество eвыводится из системы тождеств τ , и этот факт записывается в виде выводимости τ 7→ te или τ |⇒ te в зависимостиот числа использованных переходов.
Заметим, что в силуСистема тождеств τ называется полной для ЭП формул над Б,если для любых двух эквивалентных формул F′ и F′′ над Бимеет место выводимость F′ |⇒ F′′. A AM A K OΠ DΠK ΠKAτ осн = tM& , t¬ , t& , t& , t& , t&,∨ , t1,& , t0,& , τ = t& , t∨ , OΠ OΠ OΠ KΠK ΠK ΠKτ K = tK= t& , t∨ , τ ΠK = tΠK& , t∨ , τ0,& , t1,& , t0,∨ , t1,∨ ,Dτ D = tD&,∨ , t∨,& , τeосн = τ M , τ A , τ K , τ OΠ , τ D , τ ΠK , tΠ .Систему τ осн будем называть системой основных тождеств,а систему τeосн — расширенной системой основных тождеств.Лемма 1.1. Система τeосн выводима из системы τ осн .Произвольную конъюнкцию букв, содержащую, вобщем случае, повторя-ющиеся или противоположныебуквы, будем называть обоб-щенной ЭК (ОЭК), адизъюнкцию таких конъюнкций, со-держащую, в общемслучае, повторяющиеся «слагаемые», — обобщенной ДНФ(ОДНФ). Обычную ЭК (ДНФ) и формулу x1 ·x1 будемсчитать канонической ОЭК (соответственно ка-ноническойОДНФ), а совершенную ДНФ и формулу x1 · x1 —совершенными ОДНФ.Лемма 1.2.
Любую формулу F (x1 , . . . , xn ), реализующуюФАЛ f , с помощью ЭП на основе системы тождеств τ оснможно преобразовать в совершенную ОДНФ ФАЛ f от БПX (n).Теорема 1.1. Система τ осн — полная система тождеств.Рис. 3.1: основные тождества для КСa) t1 :∼ ∅•x1b) t2 :•1x1c) t3 :x22∼x1•12∼d) t4 :11x222x12x1•x112x13•3x2: 11∼2x1x1(m)1x1e) t5 :f) t6∼2x1•1•x2x2x2∼•xm1•Рис. 3.3: вспомогательные тождества для КСa) t7 :x1x11∼2b) t8 :1∼13x1•23x2•∼11x1d) t10 :x2•x1•x2x1c) t9 :2x12x2x11x112∼x13x13x1x1x1x1m2x121e) t11 :1013x1∼mx1x1x12x10325Эквивалентные преобразования схем из функциональных элементов и моделирование с их помощьюэквивалентных преобразований фор-мул. Моделированиеэквивалентных преоб-разований формул и схем вразличных ба-зисах, теорема переходаЭквивалентность схем Σ′ и Σ′′ из U имеет место тогда итолько тогда, когда Σ′ и Σ′′ реализуют равные си-стемы(матрицы) ФАЛ. При этом, обычно, предполагается, чтосоответствующие друг другу полюса (выходы, входы) в Σ′ иΣ′′ имеют одинаковые пометки, а эквивалентность Σ′ и Σ′′записывается в виде тождества t : Σ′ ∼ Σ′′ .Для схем из U, как и для формул, определяется ряд«простейших» преобразований, сохраняющих эквивалентностьb′ ∼ Σb ′′ ,схем, которые наз.
подстановками. Тождество bt: Σкоторое получается в результате применения одной и тойже подстановки к обеим частям тождества t : Σ′ ∼ Σ′′ , называется подстановкой тождестваt. Схема Σ′ называетсяподсхемой схемы Σ, если V Σ′ ⊆ V (Σ) ,E Σ′ ⊆ E (Σ)и любая вершина v, v ∈ V (Σ′ ), которая либо относится кмножеству входов (выходов) Σ, либо служит конечной (соответственно начальной) вершиной некоторого ребра из E(Σ)\E(Σ′ ), является входом (соответственно выходом) Σ′ .На рис. 2.2a и 2.2b показаны тождество ветвления tBEiи тождество снятия tCEi для функционального элемента Ei , i ∈[1, b], соответственно, а на рис.
2.2c — тождество снятиявхода tCвх.x 1 . . . x kix 1 . . . x kix 1 . . . x ki••••••x kix1∼ • ... •∼ 1kiki1b)c)ϕϕi •ϕi • k i 1 • ϕii •x1z1 , z2z1z2• ∼ ∅a)Теорема 2.1. Если τ — конечная полная сис тема тожC , τ B — конечнаядеств для ЭП формул из UΦ,тоτ,τБполная система тождеств для ЭП СФЭ из UCБ. осн B C Следствие. Система тождеств τ , τ , τ— КПСТдля ЭП СФЭ из UC .Рассмотрим далее вопросы структурного моделированияформул в различных базисах. Пусть помимо базиса Б == {ϕi }bi=1 у нас имеется другой конечный полныйбазис′Б′ = {ϕ′i }bi=1 , и пусть формула Φ′i x1 , .
. . , xki′из UΦ, гдеБ′ki′ > ki , реализует ФАЛ ϕi , i = 1, . . . , b. Заметим, что вслучае ki′ > ki БП xki +1 , . . . , xki′ являютсяБП фиктивнымиформулы Φ′i . Положим Φ′ = Φ′1 , . . . , Φ′b ,Π′ = Π′1 , . . . , Π′b ,где Π′i — тождество вида ϕi = Φ′i , i = 1, . .
. , b, и формулы изΦ′ (тождества из Π′ ) будем называть формулами (соответственно тождествами) перехода от базиса Б к базису Б′ .′Для формулы F, F ∈ UΦБ , обозначим через Π (F)′формулу над базисом Б , которая получается из F заменой каждой ее подформулывида ϕi (F1 , . . . , Fki ) формулойΦ′i F1 , . . . , Fki , xki +1 , . . . , xki′ , то есть является результатомподстановки формулы Fj вместо БП xj в формулу Φ′i длявсех j, j = 1, . . . , ki .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
