оки3 (1155746), страница 4
Текст из файла (страница 4)
При этом, очевидно,L Σ00 6 2L Σ0 ,(3.3)а объединение Σ0 и Σ00 является полной ККС. ДополнениеΣ00 к полной ККС Σ с 1 входом будем называть инверснойк Σ0 ККС. Заметим, что ККС Σ00 , в силу отмеченных выше0свойств полных ККС, реализует систему ФАЛ F , если ККСΣ0 реализует систему ФАЛ F 0 .
Таким образом, в силу (3.3)справедливо следующее утверждениеЛемма 3.1. Если (1, m)-ККС Σ0 реализует систему ФАЛ0 ), то существует (1, m)-ККС Σ00 , котораяF 0 = (f10 , . . . , fm24Глава 3. Синтез и сложность управляющих систем000реализует систему ФАЛ F = f 1 , . . . , f m и для которойL (Σ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 } ,Gb1 , . . . , Gb n не пусты и попарно не пересеа множества ФАЛ Gкаются.→−Построим КС Σ̌F , которая реализует систему ФАЛ G F ,b1 ∪ .
. . ∪ Gb n с помощью операций присоединениягде GF = Gодного или двух противоположных контактов. При этом дляb i , реаликаждого i, i = n, (n−1), . . . , 1, каждая ФАЛ g, g ∈ Gзуется согласно (3.1) ((3.2)) на выходе v, который при α =0, 1 (соответственно α = σ) соединен контактом вида xαi стем выходом vα , где реализуется ФАЛ gα = g (α, xi+1 , . .
. , xn ),§3. Метод каскадов для КС и СФЭ•1•v0xi•vΣ̌•251•Σ̌xi•xσivσ•vv1a)b)Рис. 3.1: присоединение одного или двух противоположныхконтактовпринадлежащая множеству Gi+1 , так, как это показано нарис. 3.1a (соответственно рис. 3.1b).Заметим, что указанное присоединение одного или двухпротивоположенных контактов не изменяет ФАЛ, реализуемые в вершинах vα , α ∈ {0, 1}.Для получения искомой КС ΣF достаточно «снять» пометки с тех выходных вершин КС Σ̌F , в которых реализуются ФАЛ, отличные от f1 , .
. . , fm .Аналогичным образом по методу каскадов строится и→−СФЭ ǓF , реализующая систему ФАЛ G F , с той лишь разницей, что:1. сначала реализуются все ФАЛ вида xi , 1 6 i 6 n,которые встречаются в КС ΣF ;2. для всех i, i = (n − 1) , . . . , 1, разложение (3.1), гдеb i и g0 , g1 ∈ Ǧi+1 , реализуется так, как показаноg ∈Gна рис. 3.2a, а разложение (3.2), применяемое в случаеgσ = 0 (разложениеg = xσi ∨ gσ xσi = xσi ∨ gσ(3.4)в случае gσ = 1), — так, как показано на рис.
3.2b(соответственно 3.2c);26Глава 3. Синтез и сложность управляющих системxi••... ...••xi • ¬Ǔ•&•'zv1 v0∨•(vvxσi•... ...•Ǔ•vσ&•&•v(v•$wa)b)•xσi•... ...•Ǔvσ•∨•v(vc)Рис. 3.2: к моделированию операций присоединения контактов в классе СФЭ§3. Метод каскадов для КС и СФЭ273.
каждая ФАЛ вида gσ xσi , используемая в предыдущемпункте при реализации разложений вида (3.1) или (3.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На рис.
3.3 показана построенная для данной системы ФАЛКС Σ̌F , вершины которой помечены сопоставленными имФАЛ, на рис. 3.4 — соответствующая ей КС ΣF , а на рис. 3.5 —СФЭ UF .Другим примером КС, построенной по методу каскадовдля линейной ФАЛ `n , где n > 2, является известная схемаКардо [32], показанная на рис. 3.6.
Заметим, что эта КСимеет сложность (4n − 4) и является минимальной. В то жевремя СФЭ, построенная для `n , n > 2, по методу каскадовимеет сложность (7n − 9) и не является минимальной, таккак имеет бо́льшую сложность по сравнению со схемой Σ⊕nсложности (4n − 4), показанной на рис. 2.2. Аналогичныеоценки справедливы для ФАЛ `n (см.
лемму 2.3).При построении по методу каскадов (1, 2n )-КС, реализу→−ющей систему функций алгебры логики Q n , мы получим28Глава 3. Синтез и сложность управляющих системx1x1x4•x4x3 ⊕ x4x2•x1x31x4x4•x3f2•x2 (x3 ⊕ x4 )x3x3 x4•x2x2 ∨ x3 x4•x1x2f1Рис.
3.3: пример КС с помеченными вершинами,построенной методом каскадовx1x1x4••x2f2•x3x1x31x4•x3x2•x2•x1f1Рис. 3.4: пример КС, построенной методом каскадов§3. Метод каскадов для КС и СФЭx1x4•x3•x2••¬•¬ •&¬ •29&• • ∨•∨&• •$&&• &• &• ∨•)∨••f2f1Рис. 3.5: СФЭ для системы ФАЛ F , построенная методомкаскадов1x2•x1x2x1••...xn−1xn−1x2x2••...••xnxn−1 xnxn−1•Рис. 3.6: схема Кардо для линейной функции `n`n30Глава 3. Синтез и сложность управляющих системконтактное дерево порядка n, показанное на рис.
4.4 гл. II.Как будет показано далее это КД не является минимальнымконтактным дешифратором.Аналогичным образом с помощью метода каскадов можно построить контактный дизъюнктивный дешифратор порядка 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следующим утверждением.Лемма 3.2.
Для любого натурального n и σ ∈ B выполняются неравенства: →−1nK σL (`n ) 6 4n − 4 +,LK P 2 (n) 6 2 · 22 ,n→− LK J n 6 2n+2 − 6.Рассмотрим, в заключение, метод Шеннона для синтеза КС и СФЭ (см. [33, 14]), который позволяет установитьпорядок роста функций Шеннона LK (n) и LC (n).Метод Шеннона заключается в выборе некоторого параметра q, 1 6 q 6 n, и построении схемы Σf , реализующей§3. Метод каскадов для КС и СФЭ31произвольную ФАЛ f (x1 , .
. . , xn ) на основе ее разложенияпо части переменных (см. равенство (2.5) из гл. 1):σq+1· · · xσnn · fσ00 x0 ,xq+1_f x0 , x00 =σ 00 =(σ(3.5)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 в соответствии с (3.5).Полагаяq = blog (n − 2 log n)c ,построим для ФАЛ f (x1 , . . .
, xn ) указанным выше способомКС (СФЭ в базисе Б0 ) Σf , где Σ00 — (2n−q , 1)-КД порядка(n − q) (соответственно формула Fn−q из леммы 2.3), а Σ0 —универсальный многополюсник из леммы 3.2 (соответственно леммы 1.3). Корректность построенной суперпозиции, т.е.реализация схемой Σf ФАЛ f в случае СФЭ очевидна, а вслучае КС обеспечивается тем, что её можно представитьв виде результата многократной операции присоединениядвух противоположенных контактов, корректность которойбыла отмечена выше (см. рис. 3.1). Для сложности полученной схемы Σf будут справедливы оценкиL (Σf ) 6 2 · 22qn−q+2·22n+26+On − 2 log n2nn2,если Σf ∈ UK , иL (Σf ) 6 22qn−q+4·28 · 2n6+On − 2 log n2nn2,32Глава 3. Синтез и сложность управляющих системесли Σf ∈ UC .
Таким образом, доказано следующее утверждение.Теорема 3.1. Для функций Шеннона LK (n) и LC (n) выполнены соотношения:2n2nLK (n) . 4 ,LC (n) . 8 .nn§4Нижние мощностные оценки функции ШеннонаУстановим теперь ряд нижних оценок для введенных в §1функций Шеннона. Все эти оценки получены с помощьюмощностного метода, предложенного Шенноном [33, 14], который основан на том, что число ФАЛ от БП x1 , . .
. , xn неможет быть меньше числа тех попарно не эквивалентныхсхем, сложность которых не превосходит значения соответствующей функции Шеннона от аргумента n.Пусть U — один из рассмотренных в главе 2 классов схем,Ψ — введенный там функционал сложности, а Ψ (n) — функция Шеннона для класса U относительно Ψ. Обозначим через U (Ψ, n) множество тех схем Σ, Σ ∈ U, которые реализуют одну ФАЛ из P2 (n) и для которых Ψ (Σ) 6 Ψ. Следующее «мощностное» равенство вытекает непосредственно изопределений:nkU (Ψ (n) , n)k = 22 .(4.1)Заметим также, что если для некоторого натурального n иb δ, где 0 < δ < 1, выполняется неравендействительных Ψ,ство nb n b(4.2) 6 δ · 22 , то Ψ(f ) > ΨU Ψ,nдля не менее чем (1 − δ) · 22 ФАЛ f из P2 (n).Верхние оценки величины kU(Ψ, n)k, установленные вглаве 2 для различных классов схем и функционалов сложности, а также соотношения (4.1)–(4.2) служат основой для§4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
