OK_metodichka_part_3 (1132798), страница 3
Текст из файла (страница 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 .Рассмотрим, в заключение, метод Шеннона для синтеза КС и СФЭ (см. [32, 14]), который позволяет установитьпорядок роста функций Шеннона LK (n) и LC (n) (см. §4).Метод Шеннона заключается в выборе некоторого параметра q, 1 6 q 6 n, и построении схемы Σf , реализующейпроизвольную ФАЛ f (x1 , . . . , xn ) на основе ее разложения§2. Метод каскадов для КС и СФЭ25по части переменных (см.
равенство (2.5) из гл. 1):σq+1· · · xσnn · fσ00 x0 ,xq+1_f x0 , x00 =σ 00 =(σ(2.4)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 в соответствиис (2.4).Полагаяq = blog (n − 2 log n)c ,построим для ФАЛ f (x1 , .
. . , xn ) указанным выше способомКС (СФЭ в базисе Б0 ) Σf , где Σ00 — (2n−q , 1)-КД порядка(n − q) из §6 главы 2 (соответственно формула Fn−q из леммы 1.3), а Σ0 — универсальный многополюсник из леммы 2.1(соответственно леммы 1.6). Корректность построенной суперпозиции в случае КС обеспечивается разделительностьюКД. Для сложности полученной схемы Σf будут справедливы оценки n2n+22qL (Σf ) 6 2 · 22 + 2 · 2n−q 6+O,n − 2 log nn2если Σf ∈ UK , иL (Σf ) 6 22qn−q+4·28 · 2n+O6n − 2 log n2nn2,если Σf ∈ UC . Таким образом, доказано следующее утверждение.26Глава 3. Синтез и сложность управляющих системТеорема 2.1. Для функций Шеннона LK (n) и LC (n) выполнены соотношения:LK (n) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
