ОК_Часть_3_2015_(320-328) (1132807), страница 5
Текст из файла (страница 5)
. . , f mL (Σ00 )6и для которой2L (Σ0 ).Метод каскадов позволяет по произвольной заданной системе функций алгебры логики F = (f1 , . . . , fm ), F ∈ P2m (n),строить (1, m)-КС ΣF , ΣF ∈ UK , и СФЭ UF , UF ∈ UC , которые реализуют F . Будем считать, что все ФАЛ f1 , f2 , .
. . , fmсистемы F различны, отличны от констант, и для каждойБП xi , 1 6 i 6 n, среди них есть ФАЛ, существенно зависящая от xi .Разложим ФАЛ f1 , f2 , . . . , fm сначала по БП x1 , потом поБП x2 и так далее. При этом построим последовательностиb i , состоящих из ФАЛ от БП xi , xi+1 , . . . , xn ,множеств Gi и Gгде i = 1, 2, . . . , n, такие, что1. Gi состоит из всех различных ФАЛ g (xi , . .
. , xn ) видаg = fj (σ1 , . . . , σi−1 , xi , xi+1 , . . . , xn ) ,где 1 6 j 6 m, (σ1 , . . . , σi−1 ) ∈ B i−1 ;b i состоит из всех различных функций g, g ∈ Gi , ко2. Gторые существенно зависят от xi .Легко видеть, чтоG1 = {f1 , . . . , fm } ,b n ⊆ {xn , xn } ,G§4. Метод каскадов для КС и СФЭ35b1 , . . .
, Gb n не пусты и попарно не пересеа множества ФАЛ Gкаются.b i , где 1 6 i 6 n,Заметим, что любую ФАЛ g, g ∈ Gможно представить в виде (4.1)g = µ (xi , g0 , g1 ) = xi g0 ∨ xi g1 ,где gσ = g (σ, xi+1 , . . . , xn ), и, следовательно, gσ ∈ Ǧi+1 ∪{0, 1} для всех σ, σ ∈ B. Если при этом для некоторогоσ, σ ∈ B, ФАЛ gσ равна 0, то вместо (4.1) будем использовать разложение (4.2)g = xσi gσ ,где gσ ∈ Ǧi+1 ∪ {1}.→−Построим КС Σ̌F , которая реализует систему ФАЛ G F ,b1 ∪ . .
. ∪ Gb n с помощью операций присоединениягде GF = Gодного или двух противоположных контактов. При этом дляb i , реаликаждого i, i = n, (n−1), . . . , 1, каждая ФАЛ g, g ∈ Gзуется согласно (4.1) ((4.2)) на выходе v, который при α =0, 1 (соответственно α = σ) соединен контактом вида xαi стем выходом vα , где реализуется ФАЛ gα = g (α, xi+1 , .
. . , xn )так, как это показано на рис. 4.1a (соответственно рис. 4.1b).Заметим, что указанное присоединение одного или двухпротивоположенных контактов не изменяет ФАЛ, реализуемые в вершинах vα , α ∈ {0, 1}.Для получения искомой КС ΣF достаточно «снять» пометки с тех выходных вершин КС Σ̌F , в которых реализуются ФАЛ, отличные от f1 , . . .
, fm .Аналогичным образом по методу каскадов строится и→−СФЭ ǓF , реализующая систему ФАЛ G F , с той лишь разницей, что:1. сначала реализуются все ФАЛ вида xi , 1 6 i 6 n,которые встречаются в КС ΣF ;36Глава 3. Синтез и сложность управляющих систем2. для всех i, i = (n − 1) , . . . , 1, разложение (4.1), гдеb i и g0 , g1 ∈ Ǧi+1 , реализуется так, как показаноg ∈Gна рис. 4.2a, а разложение (4.2), применяемое в случаеgσ = 0 (разложениеg = xσi ∨ gσ xσi = xσi ∨ gσ(4.4)в случае gσ = 1), — так, как показано на рис. 4.2b(соответственно 4.2c);3.
каждая ФАЛ вида gσ xσi , используемая в предыдущемпункте при реализации разложений вида (4.1) или (4.2)для различных ФАЛ g, реализуется только один раз.Как и в случае КС, СФЭ UF , реализующая систему ФАЛ Fи построенная по методу каскадов, получается из СФЭ ǓFв результате «снятия» тех выходов, в которых реализуютсяФАЛ, отличные от ФАЛ из F .Пусть, например, F = (f1 , f2 ), гдеf1 = x1 x2 (x3 ⊕ x4 ) ∨ x1 (x2 ∨ x3 x4 ) ,f2 = x1 (x3 ⊕ x4 ) ∨ x1 x4 .Тогда:b 1 = G1 = {f1 , f2 } ;Gb 2 = {x2 (x3 ⊕ x4 ) , x2 ∨ x3 x4 } , G2 = Gb 2 ∪ {x3 ⊕ x4 , x4 } ;Gb 3 = {x3 ⊕ x4 , x3 x4 } ,b 3 ∪ {x4 } ;GG3 = Gb 4 = {x4 , x4 } .GНа рис. 4.3 показана построенная для данной системы ФАЛКС Σ̌F , вершины которой помечены сопоставленными имФАЛ, на рис.
4.4 — соответствующая ей КС ΣF , а на рис. 4.5 —СФЭ UF .Другим примером КС, построенной по методу каскадовдля линейной ФАЛ `n , где n > 2, является известная схема§4. Метод каскадов для КС и СФЭ37x1x1x4•x4x3 ⊕ x4x2•x1x31x4x4•x3f2•x2 (x3 ⊕ x4 )x3x3 x4•x2x2 ∨ x3 x4•x1x2f1Рис. 4.3: пример КС с помеченными вершинами,построенной методом каскадовx1x1x4••x2f2•x3x1x31x4•x3x2•x2•x1f1Рис. 4.4: пример КС, построенной методом каскадов38Глава 3. Синтез и сложность управляющих системx1x4•x3••¬•¬ •&¬ •x2•&• • ∨•∨&• •$&&• &• &• ∨•)∨••f2f1Рис.
4.5: СФЭ для системы ФАЛ F , построенная методомкаскадов1x2•x1x2x1••...xn−1xn−1x2x2••...••xnxn−1 xnxn−1•Рис. 4.6: схема Кардо для линейной функции `n`n§4. Метод каскадов для КС и СФЭ39Кардо [32], показанная на рис. 4.6. Заметим, что эта КСимеет сложность (4n − 4) и является минимальной. В то жевремя СФЭ, построенная для `n , n > 2, по методу каскадовимеет сложность (7n − 9) и не является минимальной, таккак имеет бо́льшую сложность по сравнению со схемой Σ⊕nсложности (4n − 4), показанной на рис. 2.2.
Аналогичныеоценки справедливы для ФАЛ `n (см. лемму 2.3).При построении по методу каскадов (1, 2n )-КС, реализу→−ющей систему функций алгебры логики Q n , мы получимконтактное дерево порядка n, показанное на рис. 1.1. Какбудет показано далее это КД не является минимальным контактным дешифратором.Аналогичным образом с помощью метода каскадов можно построить контактный дизъюнктивный дешифратор порядка n и сложности не больше, чем 2n+2 − 6, контактныйуниверсальный многополюсник порядка n и сложности неnбольше, чем 2 · 22 , а также контактный мультиплексор порядка n и сложности 3 · 2n − 2, показанный на рис. 2.1 (см.лемму 2.3).
Заметим, что указанный мультиплексор получается при разложении ФАЛ µn сначала по адресным, а затемпо информационным БП. В то же время, контактный мультиплексор порядка n, построенный по методу каскадов приразложении ФАЛ µn сначала по информационным, а затемпо адресным БП, содержит КД порядка 2n от информациnонных БП и поэтому имеет сложность не меньше, чем 22 +1 .Это показывает, что выбор «правильного» порядка переменных при разложении ФАЛ может существенно уменьшитьсложность КС, построенной по методу каскадов.Учитывая все сказанное выше, дополним леммы 1.3 и 2.3следующим утверждением.Лемма 4.2. Для любого натурального n и σ ∈ B выполня-40Глава 3. Синтез и сложность управляющих системются неравенства:KL(`σn ) →−1n,LK P 2 (n) 6 2 · 22 ,6 4n − 4 +n− K →L J n 6 2n+2 − 6.Рассмотрим, в заключение, метод Шеннона для синтеза КС и СФЭ (см.
[33, 14]), который позволяет установитьпорядок роста функций Шеннона LK (n) и LC (n).Метод Шеннона заключается в выборе некоторого параметра q, 1 6 q 6 n, и построении схемы Σf , реализующейпроизвольную ФАЛ f (x1 , . . . , xn ) на основе ее разложенияпо части переменных:_σq+1f x0 , x00 =xq+1· · · xσnn · fσ00 x0 ,(4.5)σ 00 =(σq+1 ,...,σn )где x0 = (x1 , . . . , xq ) , x00 = (xq+1 , . . . , xn ) и fσ00 (x0 ) == f (x0 , σ 00 ) при всех σ 00 , σ 00 ∈ B n−q .
При этом схема Σf представляет собой суперпозицию вида Σ00 (Σ0 ), где Σ00 — мультиплексор порядка (n − q) от адресных БП x00 , информационные входы которого при выполнении указанной суперпозиции присоединяются к выходам универсального многополюсника Σ0 порядка q от БП x0 в соответствии с (4.5).Полагаяq = blog (n − 2 log n)c ,построим для ФАЛ f (x1 , . . . , xn ) указанным выше способомКС (СФЭ в базисе Б0 ) Σf , где Σ00 — (2n−q , 1)-КД порядка(n − q) (соответственно формула Fn−q из леммы 2.3), а Σ0 —универсальный многополюсник из леммы 4.2 (соответственно леммы 1.3).
Корректность построенной суперпозиции, т.е.реализация схемой Σf ФАЛ f в случае СФЭ очевидна, а вслучае КС обеспечивается тем, что её можно представитьв виде результата многократной операции присоединения§5. Нижние мощностные оценки41двух противоположенных контактов, корректность которойбыла отмечена выше (см. рис. 4.1). Для сложности полученной схемы Σf будут справедливы оценки n2n+222qn−q,L (Σf ) 6 2 · 2 + 2 · 26+On − 2 log nn2если Σf ∈ UK , иqL (Σf ) 6 22 + 4 · 2n−q 68 · 2n+On − 2 log n2nn2,если Σf ∈ UC .
Таким образом, доказано следующее утверждение.Теорема 4.1. Для функций Шеннона LK (n) и LC (n) выполнены соотношения:LK (n) . 4§52n,nLC (n) . 82n.nНижние мощностные оценки функции Шеннона, их обобщение на случай синтеза схемдля функций из специальных классовУстановим теперь ряд нижних оценок для введенных в §1функций Шеннона. Все эти оценки получены с помощьюмощностного метода, предложенного Шенноном [33, 14], который основан на том, что число ФАЛ от БП x1 , . .
. , xn неможет быть меньше числа тех попарно не эквивалентныхсхем, сложность которых не превосходит значения соответствующей функции Шеннона от аргумента n.Пусть U — один из рассмотренных в главе 2 классов схем,Ψ — введенный там функционал сложности, а Ψ (n) — функция Шеннона для класса U относительно Ψ. Обозначим через U (Ψ, n) множество тех схем Σ, Σ ∈ U, которые реализу-42Глава 3. Синтез и сложность управляющих системют одну ФАЛ из P2 (n) и для которых Ψ (Σ) 6 Ψ.
Следующее «мощностное» равенство вытекает непосредственно изопределений:nkU (Ψ (n) , n)k = 22 .(5.1)Заметим также, что если для некоторого натурального n иb δ, где 0 < δ < 1, выполняется неравендействительных Ψ,ство nb n b(5.2) 6 δ · 22 , то Ψ(f ) > ΨU Ψ,nдля не менее чем (1 − δ) · 22 ФАЛ f из P2 (n).Верхние оценки величины kU(Ψ, n)k, установленные вглаве 2 для различных классов схем и функционалов сложности, а также соотношения (5.1)–(5.2) служат основой дляполучения нижних мощностных оценок соответствующих функций Шеннона и сложности почти всех ФАЛ.
Напомним, что(см. леммы 4.3, 4.2, 6.2, 6.3 из главы 2) для любых натуральных n и L справедливы неравенства: CU (L, n) 6 (8 (L + n))L+1 ,(5.3) ΦU (L, n) 6 (8n)L+1 ,(5.4) KLU (L, n) 6 (8nL) ,(5.5)kUπ (L, n)k 6 (12n)L , ΦU [L, n] 6 (8n)2D .(5.6)(5.7)Лемма 5.1. Для положительных действительных чиселa, y, q из неравенствa log q > 1,(ay)y > q,(5.8)следует неравенствоlog qy>log (a log q)log log (a log q)1+,log (ae log q)(5.9)§5. Нижние мощностные оценки43где e — основание натуральных логарифмов, а из неравенствa > 1, ay > q — неравенствоy>log q.log a(5.10)Доказательство. Рассмотрим сначала случай, когда a = 1и log q > 1. В этом случае неравенство (5.9) следует из того,что левая часть (5.8) монотонно возрастает по y, и дляy 0 = (1 + ε)log q,log log qгдеlog log log q,log (e log q)справедливы соотношенияε=y 0 log y 0 =log q(log log q − log log log q + log e ln (1 + ε)) 6log log qlog log log qε log e6 log q (1 + ε) 1 −+=log log qlog log q= log q (1 + ε) (1 − ε) = log q 1 − ε2 6 log q.= (1 + ε)Заметим, что в случае a > 0 неравенство (5.8) эквивалентнонеравенству(ay)ay > q a ,и поэтому неравенство (5.9) получается из неравенства y > y 0в результате замены y на ay и log q на a log q, если выполненоусловие a log q > 1.Неравенство (5.10) в случае a > 1 получается в результате логарифмирования неравенства ay > q и деления обеихчастей полученного неравенства на log a.Лемма доказана.44Глава 3.
Синтез и сложность управляющих системТеорема 5.1. Для некоторых последовательностей εi =εi (n),где i = 1, . . . , 5 и n = 1, 2, . . ., таких, что εi (n) > 0 приn > n0 и εi (n) стремится к 0 при n стремящемся к бесконечности, для почти всех ФАЛ f , f ∈ P2 (n), выполняютсянеравенства2n,n2nLΦ (f ) > (1 − ε2 (n)),log n2nLK (f ) > (1 − ε3 (n)) ,n2nLπ (f ) > (1 − ε4 (n)),log nD (f ) > n − log log n − ε5 (n).LC (f ) > (1 + ε1 (n))(5.11)(5.12)(5.13)(5.14)(5.15)Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
