OK_metodichka_part_2 (1132797), страница 4
Текст из файла (страница 4)
. . , xn ; z1 , . . . , zm ) над базисом Б. Сначала индукцией по q, q = 0, 1, . . ., определим для каждой вершиныv глубины q в схеме Σ реализуемую в ней формулу Fv =Fv (x1 , . . . , xn ) глубины q над базисом Б. Если q = 0, то естьv — вход Σ, положим Fv = xj , где xj — входная БП, сопоставленная вершине v. Пусть теперь v — вершина глубиныq + 1, q > 0, схемы Σ, которая имеет пометку ϕi и в которуювходит ki дуг, причем дуга с номером j, 1 6 j 6 ki , исходитиз вершины vj глубины qj , где уже реализована формулаFj = Fvj глубины qj , а для чисел q, q1 , .
. . , qki выполнено(2.2). Тогда в вершине v реализуется формула F = Fv вида(2.1), которая имеет глубину (q + 1). При этом считается,что в вершине v СФЭ Σ реализуется ФАЛ f (x1 , . . . , xn ),если ФАЛ f реализуется формулой Fv , и что СФЭ Σ реализует систему ФАЛ F, F = (f1 , . . . , fm ), или реализуетсистему булевых уравнений z1 = f1 , . . . , zm = fm , еслиfj , j = 1, . . .
, m, — ФАЛ, реализованная в той выходнойвершине СФЭ Σ, которой приписана БП zj .Заметим, что квазидерево, которое соответствует формуле F, реализующей ФАЛ f , а также любая СФЭ, полученная из него отождествлением изоморфных квазиподдеревьев, реализует и формулу F, и ФАЛ f . Так, СФЭ на рис.{0,2,3}2.4 реализует формулу (2.3) и ФАЛ s3(x1 , x2 , x3 ), или{0,2,3}уравнение z1 = s3(x1 , x2 , x3 ).В соответствии с §1 две СФЭ считаются изоморфными,если они изоморфны как помеченные графы, и эквивалентными, если они реализуют равные системы ФАЛ.
Заметим,что СФЭ всегда эквивалентна системе формул, реализуемыхею на своих выходах. Заметим также, что изменение нуме-§2. Формулы и СФЭ23рации дуг, входящих в такую вершину v СФЭ Σ, которойсопоставлен ФЭ Ei с симметрической ФАЛ ϕi , не изменяет ФАЛ, реализуемую в вершине v, а значит, не влияет нафункционирование Σ.
В связи с этим в подобных случаяхномера дуг, входящих в вершину v, как правило, не указываются. Легко видеть, что в соответствующих друг другувершинах изоморфных СФЭ реализуются одинаковые формулы, а значит, и одинаковые ФАЛ. Следовательно, две изоморфные СФЭ эквивалентны, то есть для СФЭ справедливонеравенство (1.7).Вершина СФЭ называется висячей, если она являетсястоком, но не является выходом схемы. Схема называетсяприведенной, если в ней нет висячих вершин.
Заметим, чтосистема формул является приведенной СФЭ, и что из любой СФЭ можно получить эквивалентную ей приведеннуюСФЭ с помощью операции удаления висячих вершин. Заметим также, что приведенные СФЭ, и только они, получаются из систем квазидеревьев в результате отождествлениянекоторых изоморфных квазиподдеревьев, и что в приведенных СФЭ все вершины лежат на цепях, идущих от входов схемы к ее выходам.Также как и для формул, для каждой СФЭ Σ, Σ ∈ UCБ,определим следующие параметры (функционалы сложности):1.
L (Σ) — сложность Σ, то есть число всех ее ФЭ;2. D (Σ) — глубина Σ, то есть максимальная глубина еевершин.3. R (Σ) — ранг Σ, то есть число дуг,исходящих из ее входов.Лемма 2.1 обобщается для СФЭ следующим образом.24Глава 2. Основные классы управляющих системЛемма 2.2. Для приведенной СФЭ Σ, Σ ∈ UC , с однимвыходом, выполняются неравенстваR (Σ) 6 L&,∨ (Σ) + 1 6 L (Σ) + 1 6 2D(Σ) ,(2.6)где L&,∨ — число ФЭ & и ∨ в Σ.С содержательной точки зрения различные функционалы сложности отражают различные параметры моделируемых схем или программ. Так, например, сложность может характеризовать стоимость, размеры или потребляемую мощность СБИС, а также время выполнения программы на одном процессоре.
При этом задержка схемы характеризует время срабатывания СБИС или время выполненияпрограммы на параллельных процессорах. Ранг схемы отражает число обращений программы к памяти, в которойхранятся значения входных БП и т.п.ΦОбозначим через UΦБ (L, n) и UБ [D, n] множество формулF = F (x1 , . . . , xn ) над базисом Б, для которых L (F) 6 L иD (F) 6 D, причем индекс Б0 будем, как обычно, опускать.Заметим, что из неравенства (2.4) вытекает включениеUΦ [D, n] ⊆ UΦ 2D − 1, n .(2.7)Лемма 2.3.
Для любых натуральных n, L, D выполняются неравенства ΦU (L, n) 6 (10n)L+1 , ΦU (L, n) 6 (8n)L+1 , ΦU [D, n] 6 (8n)2D .(2.8)(2.9)(2.10)Доказательство. Для того, чтобы задать с точность до изоморфизма упорядоченное дерево D, соответствующее формуле F, F ∈ UΦ (L, n), достаточно:§2. Формулы и СФЭ251. выбрать упорядоченное двоичное корневое дерево D0 сq, q 6 L, нелистовыми вершинами, в котором вершиныс полустепенью захода 2 помечены ФС &, ∨;2. каждый исток D0 пометить одной из БП x1 , . . . , xn , авершины с полустепенью захода 1 — ФС ¬.Пронумеруем множество нелистовых вершин дерева D0 с помощью естественной нумерации τ (см. §1) числами 1, 2, . .
. , qи сопоставим каждой такой вершине v с полустепенью захода d, d ∈ [1, 2] набор α, α ∈ B d , где α = (α1 , . . . , αd ) иαj = 1 тогда и только тогда, когда дуга с номером j, входящая в v, начинается с листа дерева D0 . Заметим, что наборγ = (γ1 , . . . , γL ), где γi — набор, сопоставленный вершинес номером i, если 1 6 i 6 q, и произвольный набор из объединения B 1 ∪ B 2 в случае i > q, а также набор ФС & и∨, приписанных тем вершинам vi , 1 6 i 6 L, для которыхγi ∈ B 2 , однозначно определяет дерево D0 с точностью доизоморфизма.Следовательно, число упорядоченных деревьев D0 рассматриваемого вида не больше, чем 10L , а число получаемых из него деревьев D не больше, чем nL+1 , так как в силулеммы 2.1R (F) 6 L + 1.Перемножая указанные числа, получаем оценку (2.8).
Оценка (2.9) доказывается аналогично с учетом того, что приснятии нумерации с дуг дерева D0 двоичные наборы длины2, сопоставленные его вершинам , можно выбирать из множества {(00) , (01) , (11)} и поэтому число неупорядоченныхдеревьев D0 рассматриваемого вида не больше, чем 8L .Неравенство (2.10) вытекает из (2.9) и (2.7).Лемма доказана.26Глава 2. Основные классы управляющих системЛемма 2.4. Для любых натуральных n и L выполняетсянеравенство CU (L, n) 6 (8 (L + n))L+1 .(2.11)Доказательство. Заметим, что для того, чтобы задать СФЭΣ, Σ ∈ UC (L, n), с точность до эквивалентности достаточно:1.
выбрать её остовное неупорядоченное наддерево D0 cq, q 6 L, нелистовыми вершинами, которые помеченыФС базиса Б0 ;2. присоединить каждый лист D0 либо к одному из n входов Σ, либо к одной из нелистовых вершин D0 , отличной от корня.Оценка (2.11) получается из приведенной в лемме 2.3 оценкичисла деревьев D0 и оценки числа способов присоединениякаждого листа D0 путем их перемножения.Лемма доказана.§3Задача эквивалентных преобразований схемна примере формул. Оптимизация подобныхформул по глубинеЭквивалентные преобразования (ЭП), то есть преобразования, не изменяющие функционирования схем, играют важную роль при решении различных задач теории управляющих систем и, в частности, задачи синтеза схем (см.
§1главы 3). Следуя [30], изложим в данной главе ряд вопросовЭП схем из основных классов и рассмотрим сначала понятия, связанные с эквивалентными преобразованиями схемна основе тождеств на примере формул над базисом Б. Напомним, что некоторые ЭП формул базиса Б0 уже использовались для раскрытия скобок и приведения подобных припостроении сокращенной ДНФ (см. §3 главы 1).§3. Эквивалентные преобразования формул27Для того чтобы выделить набор x = (xi1 , . . . , xin ), который состоит из всех различных БП алфавита X, встречающихся в формуле F и перечисленных в порядке возрастания их номеров, будем записывать ее в виде F = F (x).
Приэтом формулу, которая получается из F в результате заменыкаждого вхождения БП xij , j = 1, . . . , n, формулой Fj будемсчитать результатом подстановки формулы Fj вместо БПxij , j = 1, . . . , n, в формулу F и будем обозначать ее черезF (F1 , .
. . , Fn ). Заметим, что формула F (F1 , . . . , Fn ) реализует ФАЛ f (f1 , . . . , fn ), где ФАЛ f (ФАЛ fj ) — ФАЛ, реализуемая формулой F (соответственно Fj , j = 1, . . . , n). Отсюда следует, что если указанную подстановку применитьк обеим частям тождества t : F0 = F00 , где F0 = F0 (x) иF00 = F00 (x), мы получим тождествоb0 = Fb 00 ,bt: Fb 0 = F0 (F1 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
