Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 71
Текст из файла (страница 71)
8.18 Рис. 8.14 функций от набора (хь...,х, уь...,у,) =-а(1) Хд(1) — систему (У|(1), ..., У,(1)) =д(1+1), т.е. функцию б, и систему г~(1), ...,а,(1), т.е. функцию 1,. Эти две системы называются каноническими уравнениями сети 6. Сеть 6 в целом принимает вид рис. 8.14, где блоки б и А образуют логический блок бс (но при этом б и й не обязательно отдельные блоки и могут иметь общие части), а блок задержки 0 состоит нз й двоичных задержек.
Это и дает автоматное описание СЛС 6. П Для ациклических СЛС с задержками справедливы следующие два утверждения: 1) любая ациклическая ППЛС реализует определенный автомат (см. пример 8.9, в); 2) любой определенный автомат можно реализовать ациклической СЛС с задержками. Доказательство этих утверждений не очень сложно н предоставляется читателю. Пример 8.10. Для иллюстрации метода теоремы 8.!2 приведем сеть на рис.
8.15, которая содержит три логических блока (один из них — с тремя входами и двумя выходами, реализующими функции р|рз и р1~/рз от входов 0О 0! !0 11 Описание поведения асинхронных логических сетей, в которых зна. чеииями задержек могут быть произвольные действительные числа, дано в первом издании настоящей книги. Здесь отметим лишь, что в об. Вем случае вто поведение не может быть описано никаким конечным автоматом, 842 Р! Рм Рз блока) и две задержки.
Канонические уравнения сети: У! ††ха~/д!ут, Уя=х!у„ з= х!у!уК'хя. Переходы автомата, реализуемого этой сетью, приведены в табл. 8.13. Заметим, что первые два состояния этого автомата эквивалентны. СЛС с единичными задержками и конечные автоматы — . адекватные друг другу описания в том смысле, что пара- метры т, и, й СЛС определяют Уабяяип ~ ~З соответствующие параметры !А(, ~У), 1Я! автомата, и нарт ря оборот. Если же попытаться обобщить понятие задержки и считать, что задержки мо- !0,0 00,! Ы,о 01,! 10,0 00,1 !1,0 01,1 гут быть 'не только единич!о,о 00,! ю,о 00,1 ными, то связь между й и !Я1 ю,о !0,! !о,! !0,! становится менее очевидной. Рассмотрим, например, сеть (см, рис.8.10, а), где 5! и5т— двоичные элементы задержки с величинами т! и тт (т! и та — произвольные натуральные числа).
Со структурной точки зрения сложность этой сети всегда одна н та же: она определяется числом элементов и соединений между ними и не зависит от значений т! и тя. Сложность же соответствующего автоматного описания существенно зависит от т! и тх. Дело в том, что значения выходов д!, уа сети в момент 1 определяются не только значениями входов У!, Ух в момент 1 и выходов в момент à — 1; если у(1) =О, а У(!) =1, то для вычисления у(!+1) нужно знать, сколько тактов назад У изменился на единицу.
Автоматное описание можно получить, разбив каждую задержку на единичные. Полученный автомат будет иметь т!+тя единичных задержек и 2'+'*состояний, откуда видно, что сложность автоматного описания простых сетей с различными целочисленными задержками может быть сколь угодно большой. Поэтому для описания синхронных сетей с нетривиальными временными зависимостями применяются методы, не использующие понятие абстрактного автомата (см., например, (16)). Синтез автоматных сетей. рассмотренные ранее методы получения единого автоматного описания для сетей из автоматов называются методами композиции автоматов. Методы композиции решают задачу анализа сетей, поскольку исследование поведения сетей и, в частности, реализуемого сетью отображения удобно проводить при наличии автоматного описания: таблицы переходов, графа переходов или системы канонических уравнений. Обратная задача — построение сети по заданному автомату — называется задачей декомпозиции или разложения автоматов.
Возможны различные задачи декомпозиции в зависимости от того, какие условия накладываются на искомую автоматную сеть. Например, существуют- методы разложения автомата на сеть из автоматов, соединенных заданным образом — последовательно, параллельно и т. д. Некоторые из этих методов и литература по ним приведены в [14, т. 11, $8.41. Наиболее практически важной и хорошо изученной задачей декомпозиции является задача реализации автомата в заданном автоматном базисе, т. е.
задача построения сети, реализующей данный автомат, из заданного набора автоматов (автоматного базиса), называемых в этом случае элементарными автоматами, или просто элементами. Эта задача обычно называется задачей структурного синтеза или структурной реализации автоматов, а получаемые сети — схемами из функциональных элементов. Из проблем, которые здесь возникают, кратко коснемся двух основных: 1) любой ли автомат 5 можно реализовать схемой из множества элементов Х (если да, то Х называется автоматнополным набором элементов); 2) среди всех схем в базисе Х, реализующих 5, найти минимальную схему. Начнем со структурного синтеза логических комбинационных автоматов, т.
е. со схемной реализации систем логических функций. Если функция Г' задана формулой г" над множеством функций Х (см. гл. 3), то формуле г можно поставить в соответствие схему 6 из комбинационных автоматов, реализующих функции Х.
Построение схемы 6 определяется индукцией по глубине формулы: 1) если Р=~р(хц, ...,х~ ), где «р~Х, хц,..., х~ — исходные переменные, то схема 6 состоит из одного элемента у, входы которого отождествлены с переменными хч,...,хгм а выход — с переменной г; 2) если р=ф(с', гь), где с'; — переменная хй или функция, уже реализованная схемой 6ь то схема 6 для г строится так: к 1-му входу элемента ~р присоединяется выход схемы 6; (если г,— функция) или переменная (если Г;=х1, )„ выходом г схемы 6 объявляется выход элемента ~р.
Например, формуле х~х2хг~/хзхгх4 соответствует схема на рис. 8.16, а. Риа 8.16 Схема, полученная описанным методом, всегда имеет вид ориентированного дерева; ее входы соответствуют концевым вершинам, а выход — корню дерева. Между множеством формул над Х и множеством древовидных схем из элементов, реализующих функции Е, существует взаимно однозначное соответствие: по любой формуле г над 6 описанный метод однозначно строит схему 6; с другой стороны, анализ схемы 6, проведенный методом теоремы 8.12, даст исходную формулу г" (второй факт и дает основание утверждать, что 6 действительно реализует г).
Число знаков операций в г" равно числу элементов в 6. Это обстоятельство сводит задачу преобразования (и, в частности, минимизации) древовидных схем к задаче преобразования логических формул, рассматривавшейся в гл. 3. Итак, по формуле над Е всегда можно построить древовидную схему из элементов Х; обратное утверждение в силу теоремы 8.1! верно для произвольных (а не только древовидных) схем над Х. Отсюда получаем следующий важный, хотя и очевидный, факт: для того чтобы произвольная функция могла быть реализована схемой над Х, необходимо и достаточно, чтобы множество функций Е было функ- 344 йионально полным е смьгсле р 3.3.
Ясно, что для реализации системы функций ответ в точности тот же. Вторая задача — задача минимизации — оказывается гораздо более сложной. Проблема минимизации формул сама по себе довольно трудна, однако она не исчерпывает всех возможностей минимизации схем. Например, схема на рис.8.18, б реализует ту же формулу, что и рис.8.16, а, однако схема б не древовидная и имеет меньше элементов, чем любая формула в булевом базисе. До настоящего времени известно очень небольшое количество классов функций, для которых найдены минимальные схемные реализации, Исследования в этой области дают — пока косвенные — свидетельства того, что в общем случае поиск минимальных схемных решений невозможен без большого перебора и практически не реализуем; достаточно точно оценить по данной функции хотя бы число элементов в минимальной схеме — не проводя синтеза — также не удается. Поэтому теоретические исследования задачи синтеза пошли по пути глобальных характеристик сложности схем.
Основной результат здесь формулируется следующим образом. Пусть Ех ® — число элементов минимальной схемы в базисе Е, реализующей функцию 1. Обозначим 1.з(п)= шах Ьх (!), где максимум берется по всем функциям !АР г»г от п переменных. Функция 1.х (и) называется функцией Шеннона для базиса Х; она равна минимальному числу элементов из Е, достаточному для реализации любой функции от и переменных. Теорема 8.13 (теорема Шеннона — Лупанова). Для любого базиса Х 2" г, (и) — с —, где сх — константа,зависящаяотбазиса,причем для любо- 2» го е)ОдолЯ фУнкций 1, длЯ котоРых г.х (1)((1 — е)сх —, л стремится к нулю с ростом и.
П Здесь знак обозначает асимптотическое равенство (а(и) Ь(и), если 1пп — = 1). Смысл второго утвержа (») » о ь(») дения теоремы в том, что с ростом и почти все функции реализуются со сложностью, близкой к верхней границе, т.е. (.(п). 345 Доказательство этой теоремы содержится, например, в (б91, Для автоматов общего вида уже задача существования схемы в заданном наборе Е оказывается довольно трудной.
Правда, из обсуждения схемной реализации логических функций и теоремы 8.11 следует, что набор К элементов, состоящий из элемента единичной задержки и любого функционального полного набора логических элементов, является автоматно полным. Однако в общем случае проблема автоматйой полноты для произвольного набора автомата оказывается алгоритмическн неразрешимой (в отличие от проблемы функциональной полноты для логических функций, решение которой дается теоремой 3.9). Сравнительно простое доказательство этого результата имеется в 160), где данная проблема сводится к проблеме эквивалентности слов в ассоциативных исчислениях. Практические методы синтеза автоматов разработаны в основном для набора К, описанного ранее, либо для наборов, полученных из набора К заменой элемента задержки иа какой-либо другой элементарный автомат. Долгое время основной считалась каноническая схема синтеза Хаффмена — Глушкова, которая разбивает процесс структурной реализации автоматов на следующие этапы: 1) построение автомата по какому-либо описанию автоматного отображения (например, по регулярному событию); 2) минимизация числа состояний автомата; 3) двоичное кодирование состояний (а танже входных и выходных алфавитов, если исходный автомат абстрактный, а не логический) и получение канонических уравнений будущей сети, описывающих блоки б и 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
