Lectionc2 (1132951), страница 4
Текст из файла (страница 4)
Основные классы управляющих системОпределение. Схемой из функциональных элементов надбазисом Б называется ориентированная ациклическая упорядоченная сеть Σ, входная выборка которой состоит из всехистоков Σ, а вершины помечены следующим образом:1. каждому входу (выходу) Σ сопоставлена БП из X (соответственно Z), являющаяся пометкой связанной сним вершины, причем различным входам (выходам)сопоставлены различные БП, а упорядоченность вершин во входной и выходной выборках Σ определяетсяупорядоченностью сопоставленных им БП;2. каждая отличная от истока вершина v схемы Σ помечена ФС ϕi , где ki = d+Σ (v).Заметим, что в общем случае вершины в выходной выборке СФЭ могут повторяться, то есть одной и той же выходной вершине может быть сопоставлено несколько БП изZ.
Если множество X = {xi1 , . . . , xin } (Z = {zj1 , . . . , zjm }) состоит из всех входных (соответственно выходных) БП СФЭΣ, перечисленных в порядке возрастания их номеров в алфавите X (соответственно Z), то, в соответствии с §1, будемзаписывать СФЭ Σ в виде Σ = Σ (X; Z) или Σ = Σ (x; z),где x = (xi1 , . . . , xin ) и z = (zj1 , . . . , zjm ) — наборы БП, соответствующие множествам X и Z.Схема Σ, которая получается из дерева D, связанного сформулой F из UΦБ , в результате отождествления листьев содинаковыми пометками и приписывания его корню выходной БП из Z, называется квазидеревом, соответствующимформуле F.
Заметим, что указанное квазидерево Σ однозначно определяет формулу F и является СФЭ над базисомБ. Из этого квазидерева путем «отождествления» (наложения) его изоморфных квазиподдеревьев можно получать идругие СФЭ, задающие формулу F. На рис. 2.3b показаноквазидерево над базисом Б0 с входными БП x1 , x2 , x3 и вы-§2. Формулы и СФЭxG1x2GG www• 2wwGG1ww GGx3*•{w * w2 1 G•G# ∨GG ww•GGww& **wG2**ww GGG 2w*w{11 •#•2 * ∨** &1** 1•4•¬∨ 4444 2 44 1• ∨•Gz1a)23x#S1xk•2SSSkkkkk ##11 ukkk S1S1 ) 11& 11∨ x311#S## SSSS kkkk•SkSkSk#11 ukk 1S1 ) 11& 11∨ 11nnjjj11 vnnn 11 ujjjj11∨ 11¬ 1:1:::: 11 11∨ 1•# SSSz1b)Рис. 2.4: СФЭ, полученная из квазидерева на рис.
2.3bходной БП z1 , которое получено из дерева, сопоставленногоформуле (2.3) и изображенного на рис. 2.3a. На рис. 2.4aприведена СФЭ, полученная из данного квазидерева в результате отождествления двух его изоморфных квазиподдеревьев, а на рис. 2.4b дано более «наглядное» изображениеэтой СФЭ в виде системы соединенных соответствующимобразом ФЭ.Обозначим через UCБ множество всех СФЭ над базисомБ, и пусть UC = UC.Заметим,что система квазидеревьевБ0с общими входами, соответствующая системе формул надбазисом Б, является СФЭ над Б, если выходам этих квазидеревьев приписаны различные выходные БП.
В связи сэтим формулы над Б и их системы будем считать частнымслучаем СФЭ над Б, полагая, что имеет место включениеCCΦUΦБ ⊆ UБ . Заметим также, что СФЭ Σ, Σ ∈ UБ , входит в UБ24Глава 2. Основные классы управляющих системтогда и только тогда, когда все стоки Σ, и только они, являются ее выходами, а из каждой вершины Σ, отличной отее входов и выходов, исходит одна дуга.Определим теперь функционирование СФЭ Σ == Σ (x1 , . . .
, 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. Формулы и СФЭ25рации дуг, входящих в такую вершину v СФЭ Σ, которойсопоставлен ФЭ Ei с симметрической ФАЛ ϕi , не изменяет ФАЛ, реализуемую в вершине v, а значит, не влияет нафункционирование Σ. В связи с этим в подобных случаяхномера дуг, входящих в вершину v, как правило, не указываются. Легко видеть, что в соответствующих друг другувершинах изоморфных СФЭ реализуются одинаковые формулы, а значит, и одинаковые ФАЛ.
Следовательно, две изоморфные СФЭ эквивалентны, то есть для СФЭ справедливонеравенство (1.7).Вершина СФЭ называется висячей, если она являетсястоком, но не является выходом схемы. Схема называетсяприведенной, если в ней нет висячих вершин. Заметим, чтосистема формул является приведенной СФЭ, и что из любой СФЭ можно получить эквивалентную ей приведеннуюСФЭ с помощью операции удаления висячих вершин. Заметим также, что приведенные СФЭ, и только они, получаются из систем квазидеревьев в результате отождествлениянекоторых изоморфных квазиподдеревьев, и что в приведенных СФЭ все вершины лежат на цепях, идущих от входов схемы к ее выходам.Также как и для формул, для каждой СФЭ Σ, Σ ∈ UCБ,определим следующие параметры (функционалы сложности):1. L (Σ) — сложность Σ, то есть число всех ее ФЭ;2. D (Σ) — глубина Σ, то есть максимальная глубина еевершин.3.
R (Σ) — ранг Σ, то есть число дуг,исходящих из ее входов.Лемма 2.1 обобщается для СФЭ следующим образом.26Глава 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 (8n)L+1 ,(2.8) ΦDU [D, n] 6 (8n)2 .(2.9)Доказательство. Для того, чтобы задать с точность до изоморфизма неупорядоченное дерево D, соответствующее формуле F, F ∈ UΦ (L, n), достаточно:1. выбрать неупорядоченное двоичное корневое дерево D0с не более, чем L, нелистовыми вершинами, в которомвершины с полустепенью захода 2 помечены ФС &, ∨;§3. Эквивалентные преобразования формул272.
каждый исток D0 пометить одной из БП x1 , . . . , xn , авершины с полустепенью захода 1 — ФС ¬.Заметим, что в силу следствия из леммы 1.1 число вариантов выбора дерева D0 не больше, чем (8)L , а число получаемых из него деревьев D не больше, чем nL+1 , так как в силулеммы 2.1R (F) 6 L + 1.Перемножая указанные числа, получаем оценку (2.8). Неравенство (2.9) вытекает из (2.8) и (2.7).Лемма доказана.Лемма 2.4.
Для любых натуральных n и L выполняетсянеравенство CU (L, n) 6 (8 (L + n))L+1 .(2.10)Доказательство. Заметим, что СФЭ Σ, Σ ∈ UC (L, n), с точность до эквивалентности задается графом, удовлетворяющим условиям следствия 2 из леммы 1.2 при r = n и p = L(см. доказательство леммы 2.3). Оценка (2.10) вытекает изоценки числа соответствующих графов.Лемма доказана.§3Задача эквивалентных преобразований схемна примере формул. Оптимизация подобныхформул по глубинеЭквивалентные преобразования (ЭП), то есть преобразования, не изменяющие функционирования схем, играют важную роль при решении различных задач теории управляющих систем и, в частности, задачи синтеза схем (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
