оки3 (1155746), страница 3
Текст из файла (страница 3)
В классе UC построим схемный дешифратор порядка n, удовлетворяющий первому неравенству (2.4),следующим образом:1. разобьем набор БП X(n) на группы x0 == (x1 , . . . , xq ), x00 = (xq+1 , . . . , xn ), где q = dn/2e;2. возьмем дешифраторы Σ0 и Σ00 от БП x0 и x00 порядкаq и (n − q) соответственно, реализующие каждую своюЭК по лемме 1.1;3. объединим СФЭ Σ0 и Σ00 , после чего конъюнктируемкаждый выход Σ0 с каждым выходом Σ00 , а выходы всехиспользованных для этого 2n ФЭ & (и только их) объявим выходами искомого дешифратора.Аналогичным образом строится дизъюнктивный схемный дешифратор порядка n, удовлетворяющий второму неравенству (2.4).§2.
Нижние оценки17xn•xn••x1•x2x2••x2•y0•a1x1x2y1a2y2n −2•xn•xn•y2n −1•Рис. 2.1: примеры π-схемИскомым контактным дешифратором порядка n является (1, 2n )-контактное дерево, показанное на рис. 1.1, а искомым контактным мультиплексором порядка n являетсяπ-схема, приведенная на рис. 2.1. Заметим, что сложностьсхем, показанных на рис. 1.1 и 2.1, равна 2n+1 − 2 и 3 · 2n − 2соответственно, то есть удовлетворяет неравенствам (2.5) и(2.6), причем число размыкающих контактов в каждой изних равно 2n − 1.В результате моделирования указанной π-схемы можнопостроить бесповторную по информационным БП формулуFn (x1 , . . .
, xn , y0 , . . . , y2n −1 ) =! !___=xσ1 1 xσ2 2 · · ·xσnn yν(σ1 ,...,σn ) · · · ,σ1 ∈Bσ2 ∈Bσn ∈Bкоторая удовлетворяет второму неравенству (2.6), так как18Глава 3. Синтез и сложность управляющих системx1x2•x1x2•••Σ⊕2x3•&•w•'¬∨Σ⊕2•...•z1 &xq•Σ⊕2z1a)b)Рис. 2.2: пример суперпозиции СФЭреализует ФАЛ µn и имеет сложность 4 · 2n − 3.Неравенства (2.7) при n = 1, очевидно, выполняются.Искомой СФЭ, реализующей линейную ФАЛ `n , n > 2,со сложностью (2.7), является СФЭ Σ⊕n , показанная нарис.
2.2a,b. Аналогичная СФЭ для ФАЛ `n получается в результате замены ФЭ & на ФЭ ∨ и ФЭ ∨ на ФЭ & в первой⊕подсхеме вида Σ⊕2 схемы Σn (см. рис. 2.2a).Лемма доказана.Следствие.→−→−LС ( Q n ) ∼ LС ( J n ) ∼ 2n .Лемма 2.4. Если система ФАЛ F = (f1 , . . . , fm ) состоитиз попарно различных ФАЛ от БП X(n), отличных от 0 и§2. Нижние оценки191, тоKL (F ) > 21−nmXNf .jj=1Доказательство. Возьмем приведенную (1, m)-КС Σ, реализующую систему ФАЛ F , и заметим, что при любом α, α ∈B n , в сети Σ|α имеется связная компонента, которая содержит вход Σ и те ее выходы, где реализуемые ФАЛ обращаются в 1 на наборе α. Из неравенства (1.2) главы 2 следует,что при этом|E (Σ|α )| > f1 (α) + · · · + fm (α).Суммируя полученное неравенство по всем наборам α, α ∈B n , придем (см. доказательство леммы ??) к неравенству2n−1 L(Σ) >mXNf ,jj=1из которого вытекает неравенство леммы.Лемма доказана.Следствие.LK (Jn ) > 2n+1 − 2.Замечание.
В силу следствия (1, 4)-КС с входом a, которая состоит из двух непересекающихся по внутренним вершинам (a − a)-цепей (циклов) с ЭК провеодимости x1 x2 x1и x1 x2 x1 , является минимальным дизъюнктивным контактным дешифратором порядка 2.Лемма 2.5. Если для ФАЛ f , f ∈ P2 (n), и для любого σ,σ ∈ B, ФАЛ fσ (x1 , . . . , xn−1 , σ) 6≡ 0, 1, тоCCLC&,∨ (f ) > min{L&,∨ (f0 ), L&,∨ (f1 )} + 2.(2.8)20Глава 3.
Синтез и сложность управляющих системДоказательство. Пусть Σ — минимальная по числу ФЭ &и ∨ СФЭ из класса UC , которая реализует ФАЛ f и котораяне содержит цепочек из двух последовательно соединенныхФЭ ¬. Из условия леммы следует, что выход ФЭ ¬, присоединённого к входу xn СФЭ Σ не может быть её выходом.Пусть цепь C соединяет вход xn СФЭ Σ с её выходом z1и пусть константа σ, σ ∈ B, равна 0 тогда и только тогда,когда БП xn подается в C либо на вход ФЭ &, либо на входФЭ ¬, к выходу которого в C присоединён ФЭ ∨.b которая реализует ФАЛ fσ , fσ 6≡ 0, 1,Рассмотрим СФЭ Σ,и получена из СФЭ Σ в результате подстановки xn = σ, атакже последующего ЭП на основе тождеств τ ПК (см. §5гл.
2) вплоть до устранения всех вхождений констант. Убедимся в том, что при указанном ЭП будут удалены по крайней мере два ФЭ типа & или ∨.Действительно, в случае σ = 0 из СФЭ Σ будет удаленФЭ E0 , являющийся первым ФЭ типа & или ∨ цепи C. Заметим, что выход ФЭ E0 не может быть выходом схемы и неможет быть входом ФЭ ¬, выход которого является выходомсхемы, так как при этом ФАЛ fσ была бы равна константе.Следовательно, на цепи C СФЭ Σ имеется ФЭ E00 типа &или ∨, на вход которого поступает либо выход E0 , либо выход ФЭ ¬, присоединенного к выходу E0 . Легко видеть, чтоb и, следоваФЭ E00 тоже будет удален при переходе от Σ к Σтельно, справедливы неравенстваb + 2 > L&,∨ (fσ ) + 2,L&,∨ (f ) = L&,∨ (Σ) > L&,∨ (Σ)из которых вытекает (2.8).Случай σ = 1, когда БП xn подаётся в C либо на входФЭ ∨, либо на вход ФЭ ¬, к выходу которого присоединёнФЭ типа &, рассматривается аналогично.Лемма доказана.§3.
Метод каскадов для КС и СФЭ21Следствие 1.LC (µn ) > 2n+1 + n − 1.(2.9)Действительно, (2.9) получается в результате применения леммы 2.5 последовательно ко всем информационнымБП y2n −1 , . . . , y1 и учитывая, что получившаяся в результате соответствующих подстановок констант ФАЛ существенно зависит от БП x1 , . . . , xn , y0 .Следствие 2.
Из (2.9) в силу леммы 4.1 главы 2 вытекеает неравенствоD(µn ) > n + 1.Замечание. В силу следствия 1 формула x1 y0 ∨x1 y1 являетсяминимальной СФЭ, раеализующей ФАЛ µ1 и LC (µ1 ) = 4.§3Каскадные контактные схемы и схемы из функциональных элементов. Метод каскадов и примеры его применения, метод ШеннонаПриведенные в §1 простейшие методы синтеза позволяютстроить формулы и π-схемы, специфика которых не допускает многократного использования «промежуточных результатов». Метод каскадов [21] является достаточно простым ив то же время довольно эффективным методом синтеза какКС, так и СФЭ, который позволяет это делать. Он связанс последовательным разложением заданных ФАЛ по БП ирекурсивным построением схемы, реализующей эти ФАЛ.Основу метода каскадов составляет специальный частный случай корректной суперпозиции КС — операция присоединения к выходам одновходовой КС одного или двухпротивоположных контактов, которая заключается в следующем.
Пусть (1, m)-КС Σ получается из (1, m̌)-КС Σ̌ в результате добавления новой выходной вершины v, которая22Глава 3. Синтез и сложность управляющих системсоединяется с выходными вершинами v0 и v1 КС Σ̌ контактами xi и xi соответственно (см. рис. 3.1a). Тогда в вершинахv0 и v1 КС Σ в силу нулевой проводимости между входамиприсоединяемой (2, 1)-КС реализуются те же самые ФАЛ g0и g1 , что и в КС Σ̌, а в вершине v — ФАЛ g видаg = µ (xi , g0 , g1 ) = xi g0 ∨ xi g1 .(3.1)Аналогичные соотношения будут справедливы и тогда,когда вершина v КС Σ связана с вершиной vσ только однимконтактом вида xσi , σ ∈ {0, 1} (см. рис.
3.1b). В этом случаев вершине v КС Σ реализуется ФАЛg = xσi gσ ,(3.2)а в вершине vσ по-прежнему реализуется ФАЛ gσ .Описанные выше операции присоединения одного илидвух противоположенных контактов очевидным образом распространяются на случай КС с несколькими входами. Крометого, они допускают моделирование в классе СФЭ в базисеБ0 . Так, переход от СФЭ Ǔ , Ǔ ∈ UC , которая реализует ввыходных вершинах v0 и v1 ФАЛ g0 и g1 соответственно, кСФЭ U, U ∈ UC , которая реализует ФАЛ g, удовлетворяющую (3.1) ((3.2)), показан на рис. 3.2a (соответственно 3.2b).Заметим, что при этом разложение (3.1) в случае gσ ≡ 1 эквивалентно представлениюg = xσi ∨ gσ ,схемная реализация которого показана на рис.
3.2c.Определим, далее, каскадную КС как приведенную КСбез изолированных полюсов, которая может быть полученаиз системы тождественных вершин в результате ряда операций присоединения одного или двух противоположных контактов и операций переименования выходов. Каскадная КС(ККС) считается полной, если она была построена без использования операции присоединения одного контакта. Так,§3. Метод каскадов для КС и СФЭ23например, КС, показанная на рис.
4.3c гл. II, является полной ККС, если её входами считать вершины a1 и v, а выходами — вершины a2 и a3 , или наоборот. К числу ККС относятся также контактные деревья, показанные на рис. 4.4 гл. II,причем (2n , 1)-КД является полной ККС.Заметим, далее, что, в силу отмеченных выше свойстврассматриваемых операций присоединения контактов, ККСимеет нулевые ФАЛ проводимости между своими входами.Отсюда следует, что в каждой вершине ККС реализуетсястолбец, в котором никакие две ФАЛ не обращаются в единицу одновременно, причем в случае полной ККС дизъюнкция всех ФАЛ этого столбца дает 1.
Так, в частности, вкаждой вершине полной ККС с двумя входами реализуетсястолбец из двух противоположных ФАЛ.Вершина ККС, введенная в нее с помощью операцииприсоединения одного контакта, называется неполной вершиной этой ККС. Будем говорить, что ККС Σ00 являетсядополнением неполной ККС Σ0 , если она получается в результате соединения всех неполных вершин Σ0 отсутствующими в них контактами с новым входом, удаления всех«старых» входов и перехода к соответствующей приведенной КС.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
