Lectionc3 (С.А. Ложкин - Лекции по основам кибернетики (2007)), страница 3

Метод каскадов [20] является достаточно простым ив то же время довольно эффективным методом синтеза какКС, так и СФЭ, который позволяет это делать. Он связанс последовательным разложением заданных ФАЛ по БП ирекурсивным построением схемы, реализующей эти ФАЛ.Для построения соответствующей контактной схемы используется специальный частный случай корректной суперпозиции КС (см. §9 главы 2) — операции присоединения16Глава 3.

Синтез и сложность управляющих системqqqqq •QvQ0qqQQQxiqQQQqqq1 •qMMMM Σ̌mmm• vmMMMmm ximmMMM •MM v1qqqqqqqqxσiqqq1 •MqMMM Σ̌ • vσMMMMMMMMa)•vb)Рис. 2.1: присоединение одного или двух противоположныхконтактоводного или двух противоположных контактов, которая заключается в следующем. Пусть (1, m)-КС Σ получается из(1, m̌)-КС Σ̌ в результате добавления новой выходной вершины v, которая соединяется с выходными вершинами v0 иv1 КС Σ̌ контактами xi и xi соответственно (см. рис.

2.1a).Тогда в вершинах v0 и v1 КС Σ в силу разделительности повходам присоединяемой (2, 1)-КС реализуются те же самыеФАЛ g0 и g1 , что и в КС Σ̌, а в вершине v — ФАЛ g видаg = µ (xi , g0 , g1 ) = xi g0 ∨ xi g1 .(2.1)Аналогичные соотношения будут справедливы и тогда,когда вершина v КС Σ связана с КС Σ̌ только одним контактом вида xσi , σ ∈ {0, 1}, соединяющим ее с вершиной vσ(см. рис.

2.1b). В этом случае в вершине v КС Σ реализуетсяФАЛg = xσi gσ .(2.2)Переход от СФЭ Ǔ , Ǔ ∈ UC , которая реализует в выходных вершинах v0 и v1 ФАЛ g0 и g1 соответственно, к СФЭU, U ∈ UC , которая реализует ФАЛ g, удовлетворяющую(2.1) ((2.2)), показан на рис. 2.2a (соответственно 2.2b).Определим сначала каскадную КС как приведенную КСбез изолированных полюсов, которая может быть полученаиз системы тождественных вершин в результате ряда опера-§2. Метод каскадов для КС и СФЭ17xi••... ...••xi • ¬Ǔ•&v1 v0' QQ•zQQxσi•...

...•Ǔ•vσ&•&•(vvl•w$QQQ∨ lllll(•vlva)b)•xσi•... ...•Ǔvσ•∨•(vvc)Рис. 2.2: к описанию метода каскадов для СФЭ18Глава 3. Синтез и сложность управляющих системций присоединения одного или двух противоположных контактов и операций переименования выходов. Каскадная КС(ККС) считается полной, если она была построена без использования операции присоединения одного контакта.

Так,например, КС, показанная на рис. 6.3c главы 2, являетсяполной ККС, если её входами считать вершины a1 и v, авыходами — вершины a2 и a3 , или наоборот. К числу ККСотносятся также контактные деревья, показанные на рис. 6.4главы 2, причем (2n , 1)-КД является полной ККС.Заметим, далее, что, в силу корректности рассматриваемых операций присоединения контактов, ККС является разделительной по входам КС. Отсюда следует, что в каждойвершине ККС реализуется столбец, в котором никакие двеФАЛ не обращаются в единицу одновременно, причем в случае полной ККС дизъюнкция всех ФАЛ этого столбца дает1. Так, в частности, в каждой вершине полной ККС с двумя входами реализуется столбец из двух противоположныхФАЛ.Вершина ККС, введенная в нее с помощью операцииприсоединения одного контакта, называется неполной вершиной этой ККС.

Будем говорить, что ККС Σ00 являетсядополнением неполной ККС Σ0 , если она получается в результате соединения всех неполных вершин Σ0 отсутствующими в них контактами с новым входом, удаления всех«старых» входов и перехода к соответствующей приведенной КС. При этом, очевидно,(2.3)L Σ00 6 2L Σ0 ,объединение Σ0 и Σ00 является полной ККС, а ККС Σ00 , всилу отмеченных выше свойств полных ККС, реализует си0стему ФАЛ F , если ККС Σ0 имеет один вход и реализуетсистему ФАЛ F 0 .Метод каскадов позволяет по произвольной заданной системе функций алгебры логики F = (f1 , . .

. , fm ), F ∈ P2m (n),§2. Метод каскадов для КС и СФЭ19строить (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каются.b i , где 1 6 i 6 n,Заметим, что любую ФАЛ g, g ∈ Gможно представить в виде (2.1), где gσ = g (σ, xi+1 , . . . , xn ),и, следовательно, gσ ∈ Ǧi+1 ∪ {0, 1} для всех σ, σ ∈ B.Если при этом для некоторого σ, σ ∈ B, ФАЛ gσ равна0, то вместо (2.1) будем использовать разложение (2.2), гдеgσ ∈ Ǧi+1 ∪ {1}.Пусть (1, 1)-КС Σ̌n+1 представляет собой изолированныйвход, который одновременно является выходом и реализует константу 1.

Пусть, далее, для некоторого i, 1 6 i 6n, уже построена (1, m̌i+1 )-КС Σ̌i+1 , реализующая системуФАЛ Ǧi+1 ∪ {1}. Построим тогда (1, m̌i )-КС Σ̌i , которая реализует систему ФАЛ Ǧi ∪ {1} следующим образом:20Глава 3. Синтез и сложность управляющих систем1. КС Σ̌i содержит КС Σ̌i+1 в качестве подсхемы, на выходах которой (они одновременно являются выходамиΣ̌i ) реализуются ФАЛ из множества Ǧi+1 ∪ {1};b i , реализуется согласно (2.1)2. Каждая ФАЛ g, g ∈ G((2.2)) на выходе v КС Σ̌i , который при α = 0, 1 (соответственно α = σ) соединен контактом вида xαi с темвыходом vα подсхемы Σ̌i+1 , где реализуется ФАЛ gα == g (α, xi+1 , .

. . , xn ) так, как это показано на рис. 2.1a(соответственно рис. 2.1b).Таким образом, построенная указанным выше способом КСΣ̌1 реализует систему ФАЛ Ǧ1 ∪ {1}, и для получения искомой КС ΣF достаточно «снять» пометки с тех выходныхвершин КС Σ̌1 , в которых реализуются ФАЛ, отличные отf1 , . . . , fm . При этом константа 1 всегда реализуется КС Σ̌1 ,а константа 0 может быть реализована в изолированной вершине, и поэтому их включение в систему ФАЛ F не влияетна построение КС ΣF и ее сложность.Аналогичным образом по методу каскадов строится иСФЭ UF , реализующая систему ФАЛ F , с той лишь разницей, что:1. СФЭ Ǔn реализует систему ФАЛ I, состоящую из БПx1 , . . .

, xn , а также ФАЛ вида xi , 1 6 i 6 n, которыевстречаются в КС ΣF ;2. для всех i, i = (n − 1) , . . . , 1, при переходе от СФЭǓi+1 , реализующей систему ФАЛ Ǧi+1 ∪ I, к СФЭ Ǔi ,реализующей систему ФАЛ Ǧi ∪ I, разложение (2.1),b i и g0 , g1 ∈ Ǧi+1 , реализуется так, как покагде g ∈ Gзано на рис. 2.2a, а разложение (2.2), применяемое вслучае gσ = 0 (разложение g = xσi ∨ gσ xσi = xσi ∨ gσ вслучае gσ = 1), — так, как показано на рис. 2.2b (соответственно 2.2c);3. каждая ФАЛ вида gσ xσi , используемая в предыдущем§2.

Метод каскадов для КС и СФЭ21пункте при реализации разложений вида (2.1) или (2.2)для различных ФАЛ g, реализуется только один раз.Как и в случае КС, СФЭ UF , реализующая систему ФАЛ Fи построенная по методу каскадов, получается из СФЭ Ǔ1в результате «снятия» тех выходов, в которых реализуютсяФАЛ, отличные от ФАЛ из 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На рис. 2.3 показана построенная для данной системы ФАЛКС Σ̌1 , вершины которой помечены сопоставленными имФАЛ, на рис. 2.4 — соответствующая ей КС ΣF , а на рис. 2.5 —СФЭ UF .Другим примером КС, построенной по методу каскадовдля линейной ФАЛ `n , где n > 2, является известная схема Кардо [31], показанная на рис.

2.6. Заметим, что эта КСимеет сложность (4n − 4) и является минимальной. В то жевремя СФЭ, построенная для `n , n > 2, по методу каскадовимеет сложность (7n − 9) и не является минимальной, таккак имеет бо́льшую сложность по сравнению со схемой Σ⊕nсложности (4n − 4), показанной на рис. 9.1 главы 2. Аналогичные оценки справедливы для ФАЛ `n (см. лемму 1.3).При построении по методу каскадов (1, 2n )-КС, реализу→−ющей систему функций алгебры логики Q n , мы получим22Глава 3. Синтез и сложность управляющих системx1 f2x11 x4•x4x3 ⊕ x4x2••x2 (x3 ⊕ x4 )x3x3x4x4•x3x1x3 x4•x2x2 ∨ x3 x4•x1x2 f1Рис. 2.3: пример КС с помеченными вершинами,построенной методом каскадовx1 f2x11 x4••x2•x3x1x3x4•x3x2•x2•x1 f1Рис.

2.4: пример КС, построенной методом каскадов§2. Метод каскадов для КС и СФЭx1•¬ •x/423x3•///// ///?¬¬ ••??? ????& ??&?•//•// // // ∨/J• JJJJJJJJJJ∨J&J•$• &&&&•/ /••)•//////// // //∨//∨/ / ••x2••f2f1Рис. 2.5: СФЭ для системы ФАЛ F , построенная методомкаскадовx2Gw•ww• GGGwwwwGwwGwGG wwww1 GwGG x1 x2 wwwwGGGGx2GGGGGG www xGG2G•ww•x1......xn−1GGGww• GGGGxnGGwwGGwGG wwGGwGwxn−1 w Gxn−1 x ww `nn wGGwwww xn−1 GGG wwwwwww•••GGРис. 2.6: схема Кардо для линейной функции `n24Глава 3.

Синтез и сложность управляющих системконтактное дерево порядка n, показанное на рис. 6.4a из§6 главы 2. Как будет показано в §5 это КД не являетсяминимальным контактным дешифратором.Аналогичным образом с помощью метода каскадов можно построить контактный универсальный многополюсник сложnности не больше, чем 2 · 22 , а также контактный мультиплексор порядка n и сложности 3 · 2n − 2, показанный нарис. 6.6b главы 2 (см. лемму 1.3).

Заметим, что указанныймультиплексор получается при разложении ФАЛ µn сначала по адресным, а затем по информационным БП. В тоже время, контактный мультиплексор порядка n, построенный по методу каскадов при разложении ФАЛ µn сначалапо информационным, а затем по адресным БП, содержитКД порядка 2n от информационных БП и поэтому имеетnсложность не меньше, чем 22 +1 . Это показывает, что выбор«правильного» порядка переменных при разложении ФАЛможет существенно уменьшить сложность КС, построеннойпо методу каскадов.Учитывая все сказанное выше, дополним лемму 1.3 следующим утверждением.Лемма 2.1. Для любого натурального n и σ ∈ B выполняются неравенства:LK (`σn ) 6 4n − 4 + 1,n→−nLK P 2 (n) 6 2 · 22 .Рассмотрим, в заключение, метод Шеннона для синтеза КС и СФЭ (см.