Математическая теория систем. Математические основы теории систем
 Скачать 2.07 Mb.
|
|
Теорема 2.5.2. Всякая правильная синхронная логическая сеть (ПЛС) со входами х 1 , … х m , выходами z 1 , … z n и k элементами задержки является конечным автоматом, входной алфавит которого состоит из 2 m двоич- ных наборов длины m, выходной алфавит – из 2 n наборов длины n, а множество состояний – из 2 k наборов длины k. Доказательство. Вначале возьмем ПЛС без задержек, а, следова- тельно, и без циклов. Такие сети носят название линейно-упорядоченных сетей (ЛУС), так как элементы такой сети можно пронумеровать таким образом, что любая межэлементная связь будет соединять выходной по- люс элемента с меньшим номером с входным полюсом элемента с боль- шим номером. Рассмотрим любой выход сети z. Блок, которому он при- надлежит, реализует на этом выходе логическую функцию ( ) 1 1 1 1 1 2 , ,... r z f p p p = , где 1 1 1 ,... r p p – входы блока. Каждый из этих входов является либо входом сети (переменной х), либо присоединен к выходу другого блока – ( ) 1 2 1 2 2 2 2 , ,... mk i i i i i p f p p p = и, таким образом, 117 ( ) ( ) ( ) ( ) 1 2 1 2 1 2 1 2 1 2 2 2 2 2 2 2 2 2 2 2 2 1 2 , ,... , , ,... ,... , ,... k k kr i i i j j j r n n n z f f p p p f p p p f p p p = , где вместо некоторых 2 i f стоят, возможно, переменные х. Следующее повторение этой процедуры дает формулу глубины 3 с функциями 3 i f и переменными 3 i p и т.д., причем верхний индекс у k i p равен числу блоков между полюсом k i p и выходом z. Так как сеть ациклическая, то этот про- цесс рано или поздно закончится, и все переменные будут заменены пе- ременными х. Поскольку задержек в сети нет, то в результате получим z(t) как логическую функцию от некоторых из x 1 ( t),…x m ( t) и, следователь- но, ПЛС без задержек – это логический комбинированный автомат. Теперь возьмем произвольную ПЛС (обозначим ее G). Удалив из нее элементы задержки, получим ЛУС G 0 без задержек, которая является ло- гическим комбинационным автоматом. Входами G 0 являются: во-первых, входы G, а во-вторых, выходы z 1 , …z k элементов задержки G, выходы G 0 – это выходы G и входы z 1 ',…z k ' элементов задержки G (см. рис. 2.25). Та- ким образом, входной набор G 0 имеет вид ( x 1 , …x m , z 1 , …z k ), а выходной набор – ( y 1 , …y n , z 1 ',…z k '). Теперь считаем набор (x 1 ( t),…x m ( t)) входным сигналом x(t) сети G, набор (y 1 ( t),…y n ( t)) – выходным сигналом y(t) сети G, а набор (z 1 ( t),…z k ( t)) – состоянием q(t) сети G.Учитывая, что ( z 1 '(t),…z k '(t))=(z 1 ( t+1)…z k ( t+1))=q(t+1), получим, что сеть G 0 вычисляет две системы логических функций от набора x(t)×q(t) – систему (z 1 '(t),…z k '(t))=q(t+1), т.е. функцию переходов δ, и систему (y 1 ( t),…y n ( t)), т.е. функцию выхода λ. Эти две системы функций называются канониче- скими уравнениями сети G. Рис. 2.25. Правильная синхронная сеть, представляющая автомат G x 1 x m z 1 ….. z k y 1 y п z 1 ' z k ' … … 118 Окончательно сеть G принимает вид рис. 2.25, где δ и λ образуют ло- гический комбинационный автомат G 0 , а блок задержки D состоит из k двоичных задержек. Это и есть автоматное описание ПЛС. Что и требо- валось доказать. Рассмотрим теперь сети, составленные только из логических элемен- тов и содержащие в отличие от ПЛС контуры (обратные связи). Анализи- руя поведение таких сетей, можно прийти к одному из выводов: а) при любой комбинации значений входных полюсов сеть будет пе- реходить в некоторое устойчивое состояние и оставаться в нем, пока входной сигнал не изменится; б) при некоторых обстоятельствах условие предыдущего пункта мо- жет нарушаться, и в сети возникают противоречия (как, например, это было в сети, изображенной на рис. 2.23, а). Сеть, удовлетворяющая первому выводу, называется асинхронной се- тью и ее можно рассматривать как структуру асинхронного автомата. Простейший пример приведен на рис. 2.26. Рис. 2.26. Схема триггера Легко видеть, что эта сеть оказывается триггером, который с учетом переобозначений входов совпадает с изображенным на рис. 2.22. Рассматривая триггеры как элементы, произвольный асинхронный ав- томат по аналогии с рис. 2.25 можно представить некоторым логическим комбинационным автоматом G 0 и совокупностью триггеров, концентри- рующих в себе “память” автомата (рис 2.27). Вход и выход автомата представляются, как обычно, двоичными наборами х и y, а внутренние состояния – значениями вектора q п =( q 1п , q 2п , …q kп ), где q iп – правый вы- ходной полюс i–го триггера. Переменная q ∧ всегда (см. автоматную таб- ∨ ∨ q ˄ q п x 1 = p п x 2 = p ∧ 119 лицу на рис.2.22) принимает инверсное значение по отношению к q п , в связи с чем можно считать, что логические функции, реализуемые ком- бинационным автоматом G 0 , зависят только от переменных x 1 , …x m , q 1п , …q kп Рис. 2.27. Асинхронный автомат, представленный сетью Эти функции представляют собой, во-первых, функции выхода: ( ) { } 1 1п п ,..., , ,..., , 1, 2,... i i m k y x x q q i n = λ = , а во-вторых, функции возбуждения триггеров: p i∧ ( ) { } 1 1п п ' ,..., , ,..., , 1, 2,... m k x x q q i k = δ = (для левого входа), и p iп ( ) { } 1 1п п '' ,..., , ,..., , 1, 2,... m k x x q q i k = δ = G x 1 x m ….. y 1 y n … … … 01 p k q k p k q 01 p 1 p 1 … 120 (для правого входа). При решении задачи синтеза асинхронного автомата большое значе- ние имеет нахождение функций возбуждения триггеров. Определение этих функций допускает некоторую вольность, которая становится ясной при анализе автоматной таблицы триггера (рис. 2.22). Действительно, если при реализации некоторого перехода между внутренними состояни- ями автомата i-й триггер должен сменить состояние 0 на состояние 1 (условно обозначим этот факт как 0→1), то на его вход должна быть по- дана вполне определенная комбинация 01. Но если переход при смене состояний должен быть 0→0, то такое возможно как при комбинации на входе 00 (как не меняющей состояние триггера), так и при комбинации 10 (эта комбинация всегда переводит триггер в состояние 0 независимо от того, в каком состоянии он перед этим находится). Таким образом, на входе должна быть комбинация – 0, где прочерк означает произвольное значение (либо 0, либо 1). Анализируя автоматную таблицу триггера, придем к следующей таблице смены состояний триггера. Таблица 2.19 Тип изменения состояний триггера Требуемая комбинация на вхо- де 0→0 - 0 0→1 01 1→0 10 1→1 0 - Изображенный на рис. 2.26 триггер реализован на элементах Пирса, но возможна реализация триггера и на других логических элементах, например на элементах Шеффера. Из других видов триггеров полезно упомянуть счетный триггер (или триггер со счетным входом), таблица переходов которого приведена ниже. Таблица 2.20 Тип изменения состояний Значение входа 0→0 0 0→1 1 1→0 1 1→1 0 В состав счетного триггера входят два уже рассмотренных ранее триг- гера и логическая комбинационная схема. При небольших умственных 121 затратах можно нарисовать структурную схему счетного триггера. Реко- мендуется проделать это самостоятельно в качестве упражнения. 2.5.5. Анализ комбинационных автоматов Из теорем 2.5.1 и 2.5.2. следует, что структуру комбинационного ав- томата всегда можно представить линейно-упорядоченной сетью, содер- жащей только логические элементы. Для краткости назовем такую сеть комбинационной. Если соответствующее какой-либо комбинационной сети отображе- ние P\X в Q является взаимно-однозначным отображением P\X на неко- торое подмножество Q, то такая сеть называется сходящейся, если нет, то расходящейся. Необходимо напомнить, что Р – множество входных по- люсов элементов сети, Х – множество входных полюсов сети, а Q – мно- жество выходных полюсов элементов сети. То есть связи расходящейся сети могут ветвиться (один выходной полюс может быть соединен с не- сколькими входными), а для сходящейся сети это невозможно. Если комбинационная сеть имеет только один выходной полюс (реа- лизует одну логическую функцию) и является сходящейся, то ее можно представить в виде одной формулы, задающей суперпозицию логических функций, реализуемых элементами сети. Для подобного представления расходящейся сети требуется уже система формул. Эта система может быть получена путем введения дополнительных переменных для обозна- чения тех связей, удаление которых превращает расходящуюся сеть в сходящуюся. Ясно, что система формул требуется и для описания комбинационной сети с более чем одним выходным полюсом. Исследование комбинационных автоматов сводится к исследованию отношений между логическими функциями и их представлением в виде суперпозиции элементарных функций, реализуемых отдельными элемен- тами сети. При анализе по заданной суперпозиции, определяемой комби- национной сетью, находится формула (или система формул), представ- ляющая логическую функцию (систему функций). Затем путем эквива- лентных преобразований эта формула представляется в некоторой более удобной форме. Пример 2.25. Проведем анализ сети, изображенной на рис. 2.28. Вводя промежуточные переменные, соответствующие расходящимся выходам элементов, получаем систему формул: 122 e=b∨c, f=c⋅d, g=e⋅f, y=(ab∨ e)g∨gf. Подставляя в последнюю формулу выражения для промежуточных переменных и применяя правила эквивалентных преобразований булевых формул, получаем окончательно весьма простую булеву формулу y=cd, которую, очевидно, можно реализовать и одним элементом. Рис. 2.28. К анализу сети (пример 2.25) 2.5.6. Синтез комбинационных автоматов При синтезе заданную логическую функцию ƒ необходимо предста- вить в виде суперпозиции элементарных функций, определяющей струк- туру комбинационного автомата. Если функция ƒ задана формулой F над множеством ∑ элементарных функций, то формуле F можно поставить в соответствие схему G из логических элементов, реализующих функции ∑. Построение G осуществляется индукцией по глубине формулы: 1) если F=ϕ(x i1 , …x ik ), где ϕ∈∑, x i1 , …x ik – исходные переменные, то схема G состоит из одного элемента ϕ, входы которого отождествляются с переменными x i1 ,… x ik , а выход – с переменной y; 2) если F=ϕ(F 1 , …F k ), где F i – переменная x ji или функция, уже реали- зованная схемой G i , то схема G для F строится так: к i-му входу элемента ϕ присоединяется выход схемы G i (если F i – функция) или входная пере- менная (если F i = x ij ), выходом y будет выход элемента ϕ. & ∨ & ∨ & & & ∨ а b c d e f g y 123 Такой способ построения всегда приводит к линейно-упорядоченной сходящейся сети, т. е. имеет форму дерева, причем входные полюса соот- ветствуют концевым вершинам, а выход – корню дерева. Понятно, что между множеством формул над ∑ и множеством древо- видных схем из элементов, реализующих функции ∑, существует взаим- но-однозначное соответствие: по любой формуле F над ∑ изложенный метод однозначно строит схему G и, наоборот, анализ схемы G (напри- мер, с помощью теоремы 2.5.2) дает исходную формулу F. Число знаков операций в F равно числу элементов схемы G. Все это сводит задачу пре- образования схем (в том числе их минимизацию) к задаче преобразова- ния логических формул. Итак, по формуле над ∑ всегда можно построить линейно - упорядо- ченную сходящуюся сеть из элементов ∑; обратное утверждение в силу теоремы 2.5.2 верно для любой (не обязательно сходящейся) сети. Отсю- да следует важный, хотя и очевидный факт: для того чтобы произвольная логическая функция могла быть реализована схемой над ∑, необходимо и достаточно, чтобы множество функций ∑ было функционально полным. Для системы функций справедливо то же самое. Проблема минимизации схемных решений оказывается куда более сложной. Задача минимизации формул сама по себе сложна, но и она не исчерпывает возможности минимизации схем. До настоящего времени известно очень небольшое количество клас- сов функций, для которых найдены минимальные схемные решения. И в общем случае, видимо, поиск минимальных решений невозможен без большого перебора вариантов. Даже достаточно точно оценить по задан- ной функции хотя бы число элементов в минимальной схеме (не проводя синтеза) также не удается. Из общих теоретических результатов здесь следует упомянуть теоре- му Шеннона – Лупанова. Пусть ( ) L f Σ – число элементов минимальной схемы в базисе ∑, реа- лизующей функцию ƒ. Введем функцию 2 ( ) ( ) max ( ) f P n L n L f Σ Σ ∈ = , где макси- мум берется по всем двоичным функциям от n переменных. Эта функция носит название функции Шеннона для базиса ∑ и равна она минималь- ному числу элементов из ∑, достаточному для реализации любой функ- ции n переменных. Теорема Шеннона – Лупанова утверждает, что для любого базиса ∑ 2 ( ) n L n C n Σ Σ ≈ , 124 где С ∑ – константа, зависящая от базиса ∑, а знак ≈ означает асимптоти- ческое равенство. При этом для любого 0 ε > доля функций ƒ, для которых 2 ( ) (1 ) n L f C n Σ Σ ≤ − ε , стремится к нулю с ростом n. Смысл второго утверждения теоремы в том, что с ростом n почти все функции реализуются со сложностью, близкой к верхней границе, т.е. к L ∑ ( n). Ознакомимся теперь с методами синтеза, развитыми для конкретных базисов ∑. Базис произвольных дизъюнктивных нормальных форм (ДНФ). Это базис, в котором синтезируются структуры, непосредственно соответ- ствующие ДНФ. Элементами базиса являются конъюнкторы и дизъюнк- торы с произвольным числом входов, реализующие конъюнкцию и дизъюнкцию любого числа переменных. Эти элементы могут соединять- ся так, чтобы образовывались двухъярусные сети, в которых элементами первого яруса служат конъюнкторы, а элементами второго – дизъюнкто- ры. При этом выходные полюсы элементов первого яруса могут соеди- няться с входными полюсами элементов второго яруса, а выходные по- люса элементов второго яруса являются выходными полюсами сети в целом. Входные же полюсы сети соединены непосредственно с входны- ми полюсами элементов первого яруса. Эти правила соединения – син- таксис базиса. Отмечая некоторые из входных полюсов сети символами инверсий аргументов, предполагаем, что эти инверсии получаются где-то вне син- тезируемой сети и доступны измерению (наблюдению). Это обеспечивает функциональную полноту базиса. Для реализации одной функции в базисе произвольных ДНФ нужно построить в данном базисе сеть с одним выходным полюсом. При этом сеть должна быть оптимальной в каком-то смысле. Например, если мы по ДНФ найдем известными методами тупиковую ДНФ, получим схему с минимальным числом элементов. Можно минимизировать число вход- ных полюсов сети, отказываясь от дублирования прямых значений аргу- ментов их инверсиями. Можно стремиться к минимуму инверсных зна- чений. Можно заняться выравниванием нагрузки среди аргументов, когда минимизируется максимальное число конъюнкторов, непосредственно связанных с одним и тем же входным полюсом сети. Существуют и дру- гие задачи, которые приводят к разным методам синтеза. 125 При синтезе комбинационного автомата, реализующего систему функций, возникают другие проблемы. Можно, конечно, реализовать каждую функцию отдельно, но такое решение вряд ли будет лучшим в каком-то смысле. Пусть, например, требуется минимизировать число элементов в сети. Число элементов второго яруса, как правило, равно числу функций. Ис- ключения бывают, когда функция представлена одной конъюнкцией или когда некоторые функции равны либо становятся равными при соответ- ствующем их дополнении. Это случаи тривиальные и поэтому неинте- ресные. Следовательно, основные усилия должны быть направлены на минимизацию числа элементов первого яруса. Исходная же система функций может задаваться по-разному, в зави- симости от таких параметров, как число функций, число аргументов, сте- пень определенности функций, степень их взаимосвязи и т.д. Разными в таких случаях получаются и методы минимизации. Функция Шеффера (элемент “И-НЕ” или инверсный конъюнктор) и стрелка Пирса (элемент “ИЛИ-НЕ” или инверсный дизъюнктор). Каж- дый из этих элементов может реализовать функционально полный базис. Рассмотрим двухъярусные сети, элементами которых могут служить элементы Шеффера с произвольным числом входных полюсов. Применим правило де Моргана к ДНФ простейшей функции, напри- мер, к xy∨zu: & xy zu xy zu ∨ = Легко видеть, что синтез сети данного класса, реализующий заданную функцию, может быть сведен к синтезу соответствующей двухъярусной сети в базисе произвольных ДНФ с последующей заменой всех элемен- тов полученной сети на элементы Шеффера. К этому же можно свести и синтез двухъярусной сети на элементах Пирса. Для этого достаточно перейти от дизъюнктивной нормальной формы (ДНФ) к конъюнктивной нормальной форме (КНФ), построить соответствующую двухъярусную сеть (на этот раз первый ярус будет содержать дизъюнкторы, а второй – конъюнкторы) и согласно формуле ( ) & ( ) x y z u x y z u ∨ ∨ = ∨ ∨ ∨ заменить все элементы построенной сети элементами Пирса. |