автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Дискретные системы на полурешетках

РГ в од

1 О ПАЙ Щ

омский государственный университет

На правах рукописи

АгиОалов Геннадий Петрович

ДИСКРЕТНЫЕ АВТОМАТЬ НА ПОЛУРЕШЕТКАХ

Специальность 05.13.01 - Управление в технических системах

Автореферат диссертации на соискание ученой степени доктора технических наук

Томск -1990

УДК 519. 714

Работа выполнена в Томском государственном университете

Официальные оппоненты:

- доктор технических наук,

наук,

- доктор технических наук,

- доктор технических наук,

доктор '(¿иё'ико-математических профессор Бухараев Р. Г. профессор Сагалович Ю. Л. профессор Ямпольский к 3.

Ведущая организация: Институт проблем управления (ИАТ) РАН

Защита состоится " /0." Ь 1993г. в / ^ час. на заседании специализированного совета Д 063. 53.03. Томского государственного университета по адресу: 634050, Томск, Ленина 36, тел. совета 23-30-96

С диссертацией можно ознакомиться в' научной библиотеке Томского госуниверситета.

Автореферат разослан ".-2-А 1993г.

Ученый секретарь специализированного совета

глндидат физ.-мат. наук, доцент /¡^ ^ Тривоженко Б. Е.

- 1 -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Под дискретным автоматом здесь подразумевается система логического управления, или-управляющая система со свойствами конечных абстрактного и структурного автоматов, понимаемых в том широком смысле, который допускает в схеме автомата элементы с управляемой проводимостью, двунаправленные каналы передачи информации, отождествление выходных полюсов компонент и многозначность структурного алфавита, присущие современным большим (БИС) и сверхбольшим (СБИС) интегральным микросхемам. В автомате на полурешетках каждая переменная принимает значения в некоторой конечной верхней полурешетке, т. е. в частично упорядоченном множестве, в котором любые два элемента имеет точную верхнюю грань, называемую суммой этих элементов, и которое вместе с математическими действиями, "моделирующими структурные операции в ад-томате, образует полурешеточно упорядоченную алгебру. Имеются по меньшей мере три свидетельства актуальности теории дискретных автоматов на полурешетках.

Во-первых, математический аппарат классических функциональных систем (алгебры логики, многозначной логики, теории автоматов) , будучи удобным языком для адекватного описания статического (при фиксированном входном состоянии) поведения дискретного устройства, к сожалению, недостаточен для адекватного описания динамического (вызываемого асинхронным изменением компонент входного состояния) поведения устройства. Этот недостаток преодолевается в функциональных системах на полуреиетках,' казовыми являются полу-ре шеточно упорядоченные алгебры. В описании динамического поведения дискретного автомата средствами такой алгебры отношение.порядка в последней интерпретируется как отношение сравнения состояний в автомате по степени их неопределенности, обязанной явлению состязаний, которые возникают между компонентами состояния в процессе их асинхронного изменения, а сумма состояний в полурешзтке моделирует это изменение как промежуточное (переходное) состояние.

■ Далее, в функциональных системах с частично определенными функциями, такими, как частичные функции конечно-вначной логики , частичные автоматы, частично-рекурсивные функции и т.п. , неопределенность значения переменной (аргумента, функции) трактуется обычно одним способом - как любое из всех возможных определенных вначений этой переменной. В приложениях к дискретным автоматам, в особенности на базе БИС, такая трактовка ведет нередко к снижению

- г -

точности используемых моделей со всеми вытекающими отсюда неприятными последствиями: в синтезе затрудняются формализация исходных функций и их декомпозиция, в анализе - теряется необходимая информация. Этот недостаток математического аппарата можно преодолеть, если в область значений каждой переменной ввести разные значения неопределенности, где каждое .значение неопределенности трактуется как любое из некоторых определенных значений. Подобное размножение неопределенности означает фактически расширение области значений переменной до верхней полурешетки подмножеств множества определенных значений.

Наконец, важнейшими характеристиками любой математической модели, чем в сущности и служит дискретный автомат, являются ее адекватность и степень точности. В случае дискретных моделей первая понимается как безошибочность в том смысле, что результат адекватного моделирования всегда содержит в себе истинное значение моделируемой величины, з вторая - кар,- степень неопределенности этого результата /1,2/. Аппарат теории полурешеток и полуреше-точно упорядоченных алгебр позволяет формализовать эти понятия, если принять, что в адекватной модели оперируют с наибольшими элементами смежных классов основной полурешетки по некоторой конгруэнции, которая, собственно, и представляет собой степень точности этой модели. В рамках этого аппарата удается формализовать также понятие физической реализуемости функций дискретного автомата,' выразив его в понятии квазимонотонности, определяемой как реализуемость монотонной функцией, которая, в свою очередь, выражается через отношение порядка в основной полурешетке.

Актуальность теории дискретных автоматов на полурешетгах подтверждается включением исследований по ней в 1981-1990 гг. в Координационные планы работ АН СССР (по проблеме "Кибернетика"), • МВиССО СССР (по программе "Микропроцессоры и микро-ЭВМ"), МВиССО РСЗСР (по программе САПР), стран-членов СЭВ (lio теме 25.01К) и в 1992-1995 гг. в Программу "Университеты России" (по направлениям " Зундаментальные проблемы математики и механики" и "Математическое моделирование"),

Целью работы является создание математической теории дискретных автоматов на полурешетках для решения задач логического проектирования дискретных динамических систем логического управления, в том числе на базе БИС и СБИС, и микросхемах промышленных серий. Достижение этой цели предполагает развитие в соответствую-

щем направлении теории полурешеток и полурешеточно упорядоченных алгебр, разработку основ теории функциональных систем и конечных автоматов на полурешетках, создание подходяще'й дискретной математической модели БИС на транзисторном и вентильном уровнях абстракции, разработку методов их проектирования, включая абстрактный и логический синтез с заданным динамическим поведением, логический анализ и адекватное моделирование с заданной точностью, эквивалентные преобразования и минимизацию форм представления, функциональную и структурную декомпозицию, а также проверку разработанных математических аппарата, модели и методов на реальных объектах и задачах проектирования.

Методы исследования представляют собой сочетания методов дискретной математики (комбинаторного анализа, многозначной логики, теории автоматов, теории синтеза управляющих систем) и общей алгебры (теории полурешеток и полурешеточно упорядоченных алгебр) .

Научная новизна. Принципиально новым здесь является то обстоятельство, что рассматриваемые автоматы функционально описываются в терминах переменных, определенных не, как обычно, на абстрактных множествах, но на конечных верхних полурешетках.

В теории это позволило, во-первых, формализовать такие понятия как адекватная модель, динамическое поведение и физическая реализуемость дискретного автомата и сделать утверждения о них доказательными, во-вторых, традиционные задачи (эквивалентных преобразований, минимизации, декомпозиции, иодирования, анализа, синтеза) поставить и решить в новой, более общей постановке, отражающей динамику поведения автомата и отвечающей требованиям его физической реализуемости, и в-третьих, должным образом развить необходимый математический аппарат теории полурешеток и полурешеточно упорядоченных алгебр, в том числе получив ряд новых результатов в этой области. •

В приложениях же к логическому моделированию БИС это позволило расширить, класс регистрируешх состояний узлов схемы аа счет так называемых динамических состояний разной степени неопределенности, представленных подмножествами статических состояний, указав тем самым фактически новую возможность для повышения точности и разрешающей способности дискретных моделей.

Кроме того, принципиально новым в представленной адесь переключательной модели БИС на транзисторно-вентильном уровне абс-

тракции является то обстоятельство, что в ней, в отличие от известных теперь моделей (Дж. М. Зейес, R.E.Bryant, F. J. Ramming и др.), во-первых, возмозкные статические состояния узла схемы не постулируются изначально как нечто данное извне и моделирующее значение и силу сигнала в узле, но представляются тем, чем последние в сущности и определяются,- наборами проводимостей схемы . от полюсов источника питания до этого узла и, во-вторых, любая компонента БИС (диод, резистор, транзистор, логический вентиль и т.п.) представляется изначально не как элемент для преобразования сигнала - функциональный элемент, но в соответствии с ее физическими основами как элемент с управляемыми проводимостями - переключательный элемент, вследствие чего моделирование схемы сводится к вычислению не значения и силы сигнала в ее узле, но именно проводимостей схемы до узла от полюсов источника питания, в том числе через входы схемы. Этим достигается одновременно и однородность модели, обеспечивающая единообразие, в моделировании схем из разнородных элементов - транзисторов, резисторов, вентилей, ключей и др., и ее адекватность схемам, выполненным по самым разным технологиям, чего не скажешь про другие модели.

Практическая значиьк^ть. Полученные в диссертации результаты могут служить теоретической основой для разработки практических алгоритмов логического проектирования и моделирования, в том числе адекватно с разной степенью точности и неопределенности, динамического поведения дискретных управляющих устройств и их современной элементной базы - БИС и СБИС на транзисторном, вентильном и конечно-автоматном уровнях представления. В развитие отдельных положений и идей диссертационной работы под руководством автора выполнены и успешно защищены пять кандидатских диссертаций, четыре из которых имеют указанную практическую направленность. Данное в диссертации решение задачи структурной декомпозиции - покрытия схем свободными модулями распространяется на системы модулей, которые серийно выпускаются отечественной промышленностью.

Реализация результатов работы. Основные элементы теории дискретных автоматов на полурещетках реализованы в промышленных системах функционально-логического проектирования матричных ШОП ВИС в ОКЕ при 1ШП Новосибирский завод полупроводниковых приборов, где на большом производственном опыте (спроектировано несколько десятков реальных UK и СБИС) подтвервдена эффективность этой теории, ее адекватность как проектируемым объектам, так и задачам проек-

тирования, включая моделирование,' анализ, синтез, тестирование. Теория дискретных автоматов на полурешетках составляет также математическую основу подсистемы проектирования цифровых сверхскоростных интегральных микросхем на арсениде галлия в Томском НИИПП. Программы логического синтеза, используюшде ее математический аппарат, работают в САПР РЭА, реализуемых на БИС, в ЦКБ "Алмаз" Сг. Москва). Методами декомпозиции, развитыми в диссертации, в ОКБ РА при Томском РТЗ спроектирована цифровая ячейка для сложного комплекса аппаратуры, прошедшая необходимые испытания и выпускаемая серийно. Наконец, в Томском госуниверситеге на факультетах радиофизическом и прикладной математики и кибернетики результаты диссертации используются в ряде курсов лекций по дисциплинам специализаций "Математическая электроника" и "Математическое обеспечение САПР электронной техники", а в Томском институте АСУ и радиоэлектроники - в учебно-исследовательской САПР ЛОГИКА-Т.

Апробация работы. Основные результаты диссертации докладывались на XI Международном конгрессе ИФАК в 1990 г. в Таллинне, на четырех международных конференциях (по основам теории вычислений в 1987 г. в Казани, САПР СВТ-89 в 1989 г. в Ленинграде, по алгебре в 1989г. в Новосибирске и в 1991 г. в Барнауле), на международном совещании стран - членов СЭВ по теории автоматов и ее при- t ложениям в 1983г. в Таллинне, на'IV Международном семинаре по • дискретной математике в 1993 г. в Москве, на VIII Всесоюзной конференции по проблемам теоретической кибернетики в 1988 г. в Горьком, на 1 Всесоюзном совещании по автоматизации проектирования интегральных схем в 1978 г. в Киеве, на XI Всесоюзном совещании по проблемам управления в 1989 г. в Ташкенте, на Всесоюзных школах-семинарах им. U А. Гаврилова по теорий дискретных автоматов (в 1Э8&Г. в Миассе,- в 1983 г. в Киеве) и по ЕС ЭВМ (в 1987 г. в Тбилиси, в 1989 г. в Киеве), на многочисленных-научных семинарах в Ш. АН Украины, ИТК АН Беларуси, ИПУ РАН, НИИПП, МГУ, КГУ, ТГУ, СФТИ.

Структура и объем диссертации. Диссертация представляет собой опубликованную монографию /21/ и приложение. Монография состоит из введения и восьми глав, ее объем - 14.25 пёч.л., библиография - 9S наименований; объем приложения - 12 стр.

В приложении содержатся документы о внедрении и практическом использовании результатов исследования, подтверждающие эффективность разработанной теории дискретных автоматов на полурешетках, ее адекватность задачам и предмету проектирования.

- б -ОБЗОР ЛИТЕРАТОРЫ

Для целей адекватного описания динамического поведения дискретного автомата в общем случае идут на усложнение используемых математических моделей как в рамках дискретной математики (допустимые последовательности состояний /Р. Миллер, А. Е Чеботарев/, асинхронные процессы /Е И, Варшавский и К0/, сети Петри, графы логических функций и переходов /Э. А. Якубайтис/, дискретные процессы /Ю. В. Капитонова и А. А. Летичевский/, булево дифференциальное исчисление /Д. Еохманн и X Постхоф/ и др.), так и выходя за ее пределы в область непрерывного времени /В. Е Рогинский, В. И. Левин, 3. Л. Рабинович, О. П. Кузнецов, У. С. Но/, Несмотря, однако, на обилие попыток создания обших моделей для динамического поведения дискретных автоматов, ни одна из них не стала столь же общепринятой парадигмой, каковой в свое время стали дифференциальные уравнения для динамических систем с непрерывными переменными. Именно в отсутствии такой парадигмы видится сейчас главная причина относительной слабости существующих методов анализа и синтеза дискретных динамических систем /У. С. Но/.

Идея использования переходного (промежуточного) состояния в качестве модели для асинхронного изменения состояния в дискретном автомате восходит к известной работе Эйхельбергера, где она применяется для обнаружения состязаний в двоичных комбинационных и последовагельностных схемах. Нам же эта идея позволила увидеть возможность введения на множестве состояний в схеме автомата алгебраической структуры верхней полурешетки, что, собственно, и' послужило отправным пунктом к данному исследованию, начатому в работах /1,2/, где впервые по предложению автора в многозначной модели схемы появились переменные с неопределенными (в разной степени) значениями, представленными подмножествами определенных значений, образующими в совокупности верхнюю полурешетку по отношению включения. Несколькими годами позже такого рода неопределенные значения возникли в модели СБИС у Ф. Ремминга (1986) и в расчете динамических процессов в дискретных автоматах у Ей, Левина (1992), во ни Ф. Ремминг, ни Е И. Левин но усмотрели в их совокупности алгебраической структуры полурешетки, вследствие чего это направление, судя по всему, пока но получило развития в работах других исследователей.

Автором же уже в /1,2/ разработаны основные элементы полурешеточно упорядоченной алгебры проводимостей и ее' средствами опи-

сана предложенная математическая модель БИС из элементов с управляемой проводимостью, включая полевые транзисторы, в рамках которой совместно с соавторами поставлены и решены некоторые задачи логического анализа, синтеза и диагностики таких БИС. В последующих исследованиях автора в этом направлении /3-11,18,19/ сформировалась концепция дискретного автомата на полурешетках и разработаны основы абстрактной и структурной теории таких автоматов и необходимые для этого элементы теории полурешеток и полурешоточно упорядоченных алгебр, составившие содержание монографии /21/.

Из сказанного следует, что диссертанту принадлежит приоритет не только в открытии аппарата полурешеток и полурешеточно упорядоченных алгебр для цифровой микроэлектроники и теории дискретных автоматов, ко также и в его должном развитии для нужд последних, и в его приложениях к логическому моделированию и проектированию БИС, и в развитии теории дискретных автоматов средствами этого аппарата.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ 1. Полурешетки

Полурешетка здесь - это конечная верхняя полурешетка, т. е. конечное ч.у. множество, в котором любые два элемента имеют точную верхнюю грань, называемую их суммой. Полурешетка, чьи элементы суть непустые подмножества множества Я, а отношение порядка есть отношение включения, называется полурешеткой подмножеств в М. Полурешетка точечная, если она порождается ¿своими минимальными элементами (точками).

Теорема 1.1, Всякая точечная полурешётка изоморфна полурешётке подмножеств своих точек.

Пусть S - полурешетка со сложением + и f - конгруэнция на ней. Если Де S/f, то А - подполурешетка в S,- и в А есть наибольший элемент sup А. Пусть S/<r «-(sup А : А е S/s"> и sup A a sup В = sup[sup А + sup Ю^. Вместе с операцией ш множество S/r образует полурешетку и называется адекватной моделью полурешетки S с точностью <г . Ввиду георемы о гомоморфизмах алгевр все гомоморфные образы (модели) любой полурешётки исчерпываются полурешетками, изоморфными ее адекватным моделям.

Пусть М - полурешетка всех непустых подмножеств в М, R - эквивалентность на Ы, Ш - подполурешетка в Ы, порожденная множеством M/R, и R - конгруеншя ка определенная как

А 8 В V ае А 3 Ье В (а /? Ь) а V Ье В ае А (а Я Ь).

Т е о р е м а 1.3. Ш = М/ Я.

В случае, когда Л/ есть декартово произведение множеств и М -множество всех' непустых подмножеств в М, которые сами являются декартовыми произведениями (они называются интервалами на М), множество М вместе с отношением включения является полурешеткой. Пусть в этом случае </?> = ИМИ- и /? есть минимальная конгруэнция на М, такая, что для любого смежного класса А в М/й существует смежный класс в (¡/К, содержащий в качестве элементов все одноэлементные подмножества в Л, и отношение ргШ5, определено как и?У ** Ки)=ЯV), где ИР) для РеМ есть минимальный интервал в <й>, для которого И Р) э Р.

Т е о р е м а 1.4. <Я> - М/Я.

Т е о р е м а 1.5. <Я> = Ш/р .

Следствия: 1)А) есть адекватная модель М; 2) адекватные модели Л/ являются адекватными моделями М; 3) </?> есть адекватная модель М.

Полурешётки М, М л Ш точечные.

Теорема 1.6. Полурешетка <#> точечная, если М/К г М.

ПЬлурешетки подмножеств множества Е=10,1,Х> называются полурешетками проводимостей, а полурешетки подмножеств г-й декартовой степени Еъ множества Е для гг-2 - полурешетками состояний. Символы О, 1, X в них интерпретируются как статические или определенные проводимости соответственно разомкнутой, замкнутой и резистивной электрических цепей, а их наборы в Ег - как статические или определенные состояния узла электронной схемы, представленные прово-димостями схемы от полюсов источника питания до данного узла. Соответственно этому подмножества в Е, обозначаемые как 0'=-(1,Х>, 1'={0,Х>, X' =<0Д>, Е=<0,1,Ю, - это динамические или в разной' степени неопределенные проводимости цепей, а подмножества в Ег -это такие же состояния узлов схемы. Приводятся примеры адекватных моделей полурешеток состояний для адекватного моделирования ЦДЛ-схем различных классов с той или иной точностью.

Теорема!. 7. Всякая точечная полурешетка с к точками изоморфна полурешетке состояний любой размерности г >,- к.

Определяется покрытие полурешетки 3 как такое покрытие Р множества Б различными и непустыми его подмножествами, называемыми блоками покрытия, в котором каждый блок есть подполурешетка в г и для любых его блоков А и В существует блок С, являющийся точ-

ной верхней гранью по отношению включения для A-tB, в этом случае С называется суммой Л и S в покрытии Р и обозначается А ® Я Покрытие Р называется ассоциативным, если в нем ассоциативно определенное так сложение ® . Вместе с последним ассоциативное покрытие полурешетки само есть полурешетка. Покрытие полурешетки называется П-покрытием, если сложение в нем совпадает с пересечением.

Т е о р е м а 1. 8. Всякая полурешетка изоморфна своему П-по-крытию.

Всюду далее через m (L) обозначается множество минимальных элементов полурешетки L, через M (L) множество всех минимальных (по включению) подмножеств в L, не имеющих в L нижней грани, и

г (L) = шах | А |.

AeM(L)

Пусть В и Q - полурешетки и п - натуральное число. Если существуют полурешетка /<£ в"'(с элементами и порядком в полурешетке Вп) и эпиморфизм полурешеток h: K-^Q, что для любого подмножества U^K, имеющего в В* нижнюю, грань, подмножество h(U) £ Q имеет нижнюю грань в 0, то h называется кодированием, а К кодом полурешетки Q с основанием В, длиной п и значностью к =|га (В) |.

Теорема 1.9. Для полурешетки Q, допускающей ¿с-значное кодирование, к >.r(Q). Точечная полурешетка Q допускает fc-значное кодирование, если и только если к >,riQ).

Т е о р е м а 1.10. Точечная полурэшетка Q тогда и только тогда допускает кодирование с основанием В s if, когда |Af|î- riQ).

Для любого A^Q определяется Q ( Л) как qeQ ( А) q е m ( Q) S ЗаеЛ (дч<а) и Q (a)=Q (4), если Подмножество Ts Q (л) на-

зывается допустимым, если Г л 0 (а) = £для некоторого а в А. Вектор с |л ((?) I компонентами, поставленными во взаимно однозначное соответствие элементам в m (Q) и имеющими значения в В, называется разделяющим вектором подмножества А в Q, если существует разбиение множества Q (А) на допустимые подмножества (блоки) так, что значения любых двух компонент вектора, соответствующих элементам в Q (Л) из разных блоков разбиения, не имеют общей нижней грани в полурешетке В. Матрица с элементами в .5, составленная из |ш (0)1 строк и имеющая для 1саддого А £ И (0) разделяющий вектор-столбец, называется разделяющей матрицей полурешетки Q. Подполуреиетка в В порождается матрицей, если строки последней образуют порождающее множество этой подподурешетки.

Теорема 1.11. Точечная полурешетка, допускающая код с длиной п и основанием В допускает :сод с длиной п и основанием

В, порожденный ее разделявшей матрицей с.элементами в т (6).

Ввиду этой теоремы кратчайший код точечной полурешетки (? с основанием В = Ы порождается ее разделяющей матрицей с наименьшим числом столбцов. Построение такой матрицы сводится к нахождению кратчайшего покрытия множества А) ((?) векторами в М"; где яН т( 0) I и вектор V покрывает А, если V является разделявшим вектором для А Алгоритмы нахождения кратчайших покрытий множеств известны.

2. Полурешеточно упорядоченные алгебры

Предлагается метод точечного расширения абстрактных алгебр до полуреветочно упорядоченных алгебр, состоящий в том, что множество элементов А абстрактной алгебры расширяется до некоторой полурешетки А' так, что ш ( А' )=Л, и каждая л-местная операция и) на А распространяется на А' по правилу точечного продолжения: л?(а(>... ,аЛ)-2сг (Ь,,... ,ЬЛ), где сумма в А' берется по всем наборам (Ьг . .Ьк), в которых Ь.ел и Ь-^а^ для ¡=1.....л. Этим методом строятся полурешеточно упорядоченные алгебры к-значной логики, проводиюстей и состояний. Первые определяются как точечные

расширения на полурешетках подмножеств в £А={0,1,____,к-1У алгебры

¿-значной логики (Ек, т ,л , V ), где та=/с-1-а, ад Ь=шп(а, Ь), ауЬ =тах(а, Ь). В них операции!,л , V над операндами в Ек вводятся по правилу точечного продолжения, а именно:

1и={та:аеи}, и л у~<ал Ь-. аеи, Ь«гу>, и V У=<ау Ь: ае и, Ьсу).

Теорема 2.1. В полурешеточно упорядоченной алгебре

т ,л ,у ) наряду с обычными затонами идемпотентностиг~ассоци^ ативности, коммутативности операций л и V , де Моргана и двойного отрицания имеют место следующие законы, где х0, х-, х1 обозначают соответственно наименьший, произвольный и наибольший элементы в £(., содержащиеся в элементе х из Ек-

1) слабого поглощения - а s av (алЬ), а ^ ал (ау Ь) ;

2) слабой дистрибутивности -ал(Ьус)е(ал£>)1/(алс) , а V (Ьл с) е- (а V Ь) ^ (а ^ с) ;

3) обобщённой дистрибутивности -

( а л Ь) V (а л с) = (адЬ)« (алс) V (аМЬ/с)) , (а V Ь) л (а V с) = (а V Ь) л (а V с) (а V (Ь и с)) ;

4) частичной дистрибутивности -

аЧЬ*с)-(алЬ) " (ал с)<н-или Ь;<а„ или Ь^щ или Ь^еа) и '/ (с£ > а: или с^<а0 или или с^ а), а^(Ьлс)-(а« Ь) а (а V V b¿(b¿<ac или Ьоа, или Ь^с, или Ь£г-а)

- и -

иУс^с. <а0 или с. >а( или с. < Ь( или о, с а);

5) частичного поглощения -а = а у (ал Ь) и а = а л (а V Ь) V Ь£ (Ь£ < а0 или Ь. > а( или Ь. <= а).

Таким образом, законы дистрибутивности и поглощения алгебры к-аначной логики не сохраняются в ее точечном расширении на полурешетке Ек. Это есть отражение известного свойства асинхронных схем - зависимости их функционирования от состязаний, которые в разных логических структурах проявляются по разному.

В алгебрах. проводимостей элементы -принадлежат полурешетке проводимостей £, а операциями могут быть 1 ,л , V , 9 и др. На множестве £ операции л С конъюнкция), V (дизъюнкция) и 9 определяются как модели функций проводимости соответственно последовательного, параллельного и мостикового соединений цепей с проводимостями в £, а операция ^ (отрицание), сохраняя проводимость К, переводит одну в другую проводимости 0 и 1. На полурешэтке £ все они распространяются по правилу точечного продолжения. При таком определении (£, т.л.у) в (£,-,,

Теорема 2.3. В алгебре проводимостей (£, л , у ): а а (Ь%/ с) = (ал Ь) V "(ал с) а ф К или [(Ь или с £Х') и (с или Ь£Х')];

а V (Ьл с) = (а V Ь)л (а^ с) а £ X' или С(Ь или С£Х') и (с +й или Ь £X') ];

а = ау(адЬ) и а = а л (а V Ь) а #Х' или Ь£X'.

Алгебры состояний - это подурешеточно упорядоченные векторные алгебры с состояниями в полурешегке £*• в качестве векторов и с проводимостями в полурешетке £ в качестве скаляров. Операциями в них могут быть умножение скаляра.на вектор* и операции над векторами т , I, а ,7. Для скаляра с в £ и вектора а в Еъ вектор с»а есть покомпонентная конъюнкция векторов с*и а. Одноместные т, 1 и двухместные лиг над векторами в Ег определяются как покомпонентное отрицание проводимостей, инверсия порядка следования компонент и покомпонентные конъюнкция и дизъюнкция соответственно. Для проводимостей в £и состояний ч Еъ все эти операции определяются по правилу точечного продолжения. В электронных схемах произведение с*а моделирует передачу состояния а по цепи с проводимостью с, а операция V - функцию узла схемы; состояние узла, в котором сходятся различные проводники, равно результату применения 7 к состояниям, в которых находятся другие концы этих проводников. Операции л и V не имеют аналогов в алгебре Л-значной логики, свиде-

тельствуя о ее недостаточности для моделирования современных БИС.

Вводится понятие адекватной модели для полурешеточно упорядоченной алгебры. В ней множество элементов является адекватной моделью с некоторой точностью а' для полурешетки элементов данной алгебры А, а операциями - адекватные модели для операций л в А, определяемые как ^ ( а,,..., aj =sup[ £ ( а,,..., ад ) \. Адекватные модели алгебр состояний служат адекватному моделированию БИС различных классов с разной степенью точности.

3. Функции

Имеется в виду функции на полурешетках, т. е. отображения полурешёток в полурешётки. Области определения и значений функции f обозначаются Dу и соответственно, функция называется аддитивной, если она является гомоморфизмом полурешёток. Функция Г точечная, если для любого а в ее значение f(а) есть Sf[b) по всем be £),(а).

Т е о р е м а 3.1. Всякая аддитивная функция с точечной областью определения точечная. Всякая точечная функция f с о - M аддитивна.

Функция f называется монотонной, если a<b f(a)4<f(W. 1унк-mm .g- реализует функцию f. если Df&D., y}s V<, и g(a) ч< ft a) для всех а в Df. Сункция называется квазимонотонной из полурешетки D в полурешётку V, если она реализуется некоторой монотонной функцией g: D V. Квазимокото1шад_из_Р^ V фуикция_^0--*-У-называется квазимонотоиюй.

Интерес к данным классам функций объясняется тем. что функции на полурешетках у элементов реальных схем аддитивные или точечные, у самих схем - монотонные, а реализуемые ими - квазимоно-тоиные.

Теорема 3.2. Все аддитивные и точечные функции монотонные. Суперпозиция монотонных или квазимонотонных функций есть функция соответственно монотонная или квазимонотониая.

Теорема 3.3. Функция f квазимонотонна из D в V, если и только если D, У и для любого U-rD,, где i ÎUUIm(V)l и xei/^-П х) * sup Y, из существования i; D нижней грани для U следует существование в И нижней грани для /ТУ).

В случае Df- Xf*. ХЛ функция г зависит от л аргументов х,,

.... х„, определенных на полуреиютках X......Х„, соответственно.

55одмножество этих аргументов .....х; > для J, <■•■<), доста-

Jl Jk 1 к

точно для Г, если существует монотонная функция g от аргументов в Z, удовлетворяющая для каждого а=(аг .. аА) в Соотношению реализации «Jf-Jfci-iay, ...ал:(а,а^...ал)ЧЛ.

Теорема 3.5. Подмножество 2 достаточно для Г, если и только если для любого подмножества UsD^, для которого 2« 1 U( jf... jk) |ni fy) |, из существования в Xj *...» Xjk нижней грани для t/( j1... ]к) следует существование в Vj_ нижней грани для fX U), Ввиду этой теоремы если каждому минимальному подмножеству [Ыа(-, аи.-.а^: i-1,2,..., |i/|> £ D^, для которого f\U) не имеет нижней грани в Vf , сопоставить булев вектор Ь, Ьг... ьл, в котором bj= 1 тогда и только тогда, когда в Xj нет нижней грани для iaLj:

1=1.....|U|>, j«l.....n, и выписать все такие векторы один под

другим, то получится матрица, номера столбцов кратчайшего покрытия которой указывает на Аргументы достаточного для f подмножества наименьшей мощности. Гак решается задача минимизации числа аргументов квазимонотонной функции на полурешетках.

Упорядоченное разбиение множества X аргументов функции Г: S*1* S на два или три класса, где первый класс есть А и второй -В, обозначается А/В\ в нем р=М|, <j=|ß| и r=n-(frt-q). Если r^s"', т. е. х - набор значений переменных X, то через xq, xg и хс обозначаются элементы в s'\ S*' и S1, являющиеся наборами тех значений переменных А, В и Х-(А и В) соответственно, которые содержатся в х. 4ункция f называется разделимой по разбиению А/В, если существуют квазимонотонные функции у S и <р S, что для любого х в S^h любой квазимонотонной функции^' ':SUi-*S, реализуют a<f. fix^, хс, у'(хс,хр) ч< f\x). Пусть Hq{f) ДЛЯ i В s\ ] в S^ есть множество всех квазимонотонных функций h,y: Sp-+ S, реализующих функции S'-»S, определяемую как f-j (tri) =П х), где хе=], xc=i. ^ Теорема 3.7. Квазимонотонная функция Г: S -* S разделима по разбиению А/В, если и только если для любых i в SlB j в S^ можно указать s-- в S и в /i-(f) так, что s^ h^ -hfa и для любых т1Г..,тк в S?, i,,..., ik в Sb и j,,... ,Jk в S? где 2 s<Jf s< |ffl(S) |, из существования нишей траки в для Ц j,.....ikik} ив Sf-iffm im, i, s£fA..... следует существование нижней грани в 5 для is^^,... ,sc:> и .., hikjk(mk)} соответственно.

функция gr. называется адекватной моделью функции Г с точностью ( r,j>), если if и j> суть конгруэнции на Dу. и V^ соответст-

венно, D^D^Jr, V^ Jf .и g<a) =sup[f(a)3f для всех a в функция Г сохраняет пару ( г , ^ ), если а^Ь f(a)f Г(й).

Теорема 3.8. Пусть g- - адекватная модель f с точностью ). 1. Если функция f монотонная или квазимонотонная, то функция g также монотонная или квазимонотонная соответственно. 2. Если функция f сохраняет (t,j>) и аддитивна, то функция g также

аддитивна 3. Пусть Ц.....fm), функция trc есть адекватная

модель функции Га с точностью ( i , у ), функция ^ есть адекватная модель функции Q с точностью (<r,Jj), i=l,...,m, ^ = <Tf»...>Sm и ,£„,)■ Тогда если функция Q монотонная, то g~<h\ если яэ функция Гс сохраняет ( <Г , f ), то g=h.

Утверждение 3 теоремы допускает следующую интерпретацию: заменив в какой-либо схеме функции элементов их адекватными моделями, получим схему, функция которой реализуется адекватной моделью функций прежней схемы, если функции элементов монотонные, и совпадает с ней, если функции элементов сохраняют точности их моделей.

Функция g: D -* Y реализует бинарное отношение as 13«V, если Зс< b =*> g<a)^b. Отношение л квазимонотонно, если оно реализуется квазимонотонной функцией.

Теорема 3.9. Отношение л s D*V квазимонотонно, если и

только если для любых (a<fb,).....в* , где 2< лч<|я(И)| и

<at,... ,ап} имеет нижнюю грань в D, множество ibf,... ,£>„} имеет нижнюю грань в С.

___ 4. Полу ре ввточиые функции к-значной логики

Так называются функции вида f: Ek для k=X,2,... ; их множество обозначается Р~. Методологически теория функций в Р-к- строится так же, как для булевых функций: указывается табличный способ задания, вводятся элементарные функции, изучаются их свойс- • тва, определяются понятия формулы и функции, ею представляемой, а также понятия днф, минимальной, кратчайшей и совершенной днф, устанавливается существование и единственность последней для функции, отличной от 0, показывается возможность приведения элементарными преобразованиями произвольной формулы к виду днф й совершенной днф, формулируется закон двойственности, ставятся и решайся задачи минимизации в классе днф и т. п. Здесь мы остановимся лишь на особенностях этого построения, свойственных общему случаю (к >2) и обязанных недистрибутивности полурешеточно упорядоченной алгебры ic-значной логики и требованию физической реализуемости

формул.

Прежде всего, днф бывает ортогонализированной и неортогона-лизированной. В последней, в отличие от первой, возможна пара элементарных конъюнкций с разными ненулевыми значениями. Раскрытие скобок осуществляется по правилу: а(^с)^ак^ак^...уак/п, где есть ортогонализированная днф для Ь/ с.

Во-вторых, наряду с представлением функций формулами, рассматриваются их реализации последними, т. е. отношения вида Р ч< Г, и задачи минимизации в классе днф ставятся как задачи построения кратчайшей или минимальной днф Г, представляющей или реализующей данную функцию f. В этой постановке, кроме того, предполагается, что члены элементарных конъюнкций в днф принадлежат некоторому заданному множеству функций (например, функций транзисторов), называемых базисными. В таком предположении, естественно, не любая функция может допускать представление или реализацию в виде днф, и решение задач минимизации включает проверку условий существования решения.

В-третьих, наряду с импликантами вводятся квазиимпликант Элементарная конъюнкция в называется имплккантой или квазиимпли-кантой функции Г, если или 6 V Г соответственно. Имплика-

нта в неприводима по форме или по значению, если не существует импликанты Н, что и соответственно г(Н)<г(СТ> или ЛИ?, где

г(Ю - ранг элементарной конъюнкции К Аналогично, квазиимпликан-в неприводима по форме или по значению, если не существует .азиимпликанты Н, что Н\<вУН и соответствен^ г(Н)<г(в) или не Импликанты и квазиимпликанты, неприводимые одновременно по форме и по значению, называются простыми. Устанавливается, что кратчайшая днф, представляющая Г, может быть построена из любых импликант - простых, неприводимых по форме или неприводимых по значению, а минимальная днф, представляющая Г, - только из неприводимых по форме ишликант функции Г. . Построение кратчайшей днф, реализующей Г, возможно из неприводимых по форме квазиимпликант Л а минимальной днф, реализующей Г,- только из неприводимых по форме квазиимпликант функции Г.

Наконец, требуемые импликанты и квазиимпликанты находятся не, как в булевом случае, склеиванием конъюнкций, которое в данном случае неуместно, но путем построения подходящих покрытий и квазипокрытий так называемой базисной таблицы.

Система квззимонотонных функций 0= Я называется П-полной,

Iе

если каждая квазимонотонная функция в реализуется формулой, построенной из функций в 0 при помощи операций а и», система О независима, если для любой функции Г в 0 система (}-<П не является П-полной. Пусть М-.=Фси{о, 1,2>, где о, 1 и 2 - функции, тождественно равные {О}, Ш и -(2} соответственно, и множества Ф0 и Ф1 функций,в вводятся при помощи следующего определения, в котором 0/"иЧа:а^ , Ла)={),.....]„}} для любых 1, в Еу.

1) если Г(Р3, 1 = 10/1=1, и для всех , деО/ , п , г г выполняются условия

а) рпц =0, рпг*ф , цл г*0> и б) рп 5 = 0 или я а в - 0 ;

2) ГйФ., если Ге Я-, |0°'|=|0'/|=1, V0 , 0,° =0' = 0 и

<7/ -5 г У / > ' Г т Г

ДЛЯ всех ргОу: , ягОу: выполняются условия

а) рпц , рот 1>ф , япт *<р, рпяп г =ф и

б) рпэ = Ф ИЛИ ЯГ, 5 = 0 ИЛИ р/7 5

По тесту квазимонотонности (теорема 3.3) функции в Ф0 и Ф. квазимонотонные.

Теорема 4.11. Система функций М~П-полна и независима

Вводится двоичное представление констант в Е и.функций в Я-, при котором константа а представляется булевым вектором еа'а../"'а, где Усь Ек (са =1*з>се.а), а л-местная функция Г - набором из к булевых функций СГГГ...к''с, зависящих от к-п аргументов.

~ 5. Системы уравнений

Рассматриваются системы уравнений, связывающие функциональной зависимостью переменные, определенные на полурешётках, они могут служить как функциональными, так и структурными моделями дискретных автоматов. Каждое уравнение в системе имеет вид г=Д I) и указывает на зависимость Г переменной г от переменных множества 7~ Обозначая через х, у и а наборы переменных, встречающихся соответственно только в правых, только в левых и в обоих частях уравнений системы последнюю можно записать в общем случае как пару векторных уравнений у=у(х,ч) и а= У(. х,я). Переменные в х, у, ц называются соответственно входными, выходными и внутренними переменными, а наборы их значений - соответствующими состояниями системы I. Их множества обозначаются X, г и <3 соответственно. По условию X. У и 0 - полурешетки, а у и у - функции на полурешетках, <р: Х'О -* У и у: Х*0 -* 0. Функция /у называется монотонной в точке агчХ'О, еслиуЧа,г)$г или ^ (а,г)>,г; в этом случае аг называется

точкой монотонности у. В частности, если у (а,г)=г, то у стабильна в аг, и аг - точка стабильности^. Множества точек монотонности и стабильности функции у обозначаются Му и S^ соответственно. В случае монотонных у и <р система L называется монотонной; в этом случае вводятся функции у1: Af^Q и ipf: Y как f£(a,r)= f (а, <f£(a,r)) afí(a,r)=q(m), где tj(l)=r, g(t+l) = f (a,q( t)) для t=1,2, ... им удовлетворяет условию c?(m)=q(mfl). Набор из семи элементов (ab, rfcs, uv), где arc-Sf, b <¡ X. t =^£(а+Ь,г), s-vHb.t). u= f£(a-tb,r), v=<f£(b, t), называется динамическим переходом в системе L Его диаграмма имеет следующий вид:

a (a+b)/u b/v

Q тьуи Q b/v Q

г t s

Его содержательный сшсл следующий: если в дискретном автомате, моделируемом системой L и имеющем внутреннее состояние в г, входное состояние в некоторый момент времени асинхронно меняется из а в Ь, то в автомате возникает такой переходный процесс, в течение которого внутреннее и выходное состояния не выходят за пределы t и и соответственно и по завершению которого оказываются в s и v соответственно. СовокупностьL) всех динамических переходов системы L называется её динамическим поведением.

Операция, состоящая в подстановке в правую часть некоторого уравнения е системы вместо некоторой внутренней переменной z правой части fXZ) уравнения для z, называется „элементарной подстановкой. Если уравнение, е и уравнение для z - это разные уравнения, то элементарная подстановка называется элементарной суперпозицией, в противном случае - самоподстановкой. Уравнение, которое не изменяется в результате саыоподстановки, называется нормальным.

Теорем а 5.1. Пусть система уравнений f получена из монотонной L элементарными подстановками. Тогда: 1) /(L) е f(L'); 2) если все уравнения в L нормальные, то fiL)'T'(L'); 3) если все подстановки - элементарные суперпозиции, то T(L)"T{1') ■

Утверждение 1 теоремы означает, ' что в понятии динамического поведения формализовано такое поведение дискретного автомата, которое сохраняется с повышением скорости срабатывания его компонент. Утверждение 2 означает, что для автомата с нормальным! уравнениями компонент это поведение вообще не зависит от величин задержек в компонентах автомата

Подмножество внутренних переменных называется размыкавшим множеством, если его представитель есть в каждом контуре графа зависимости переменных в системе. Подстановка во все уравнения для внутренних ' переменных некоторого размыкающего множества правых частей всех остальных внутренних переменных называется суперпозицией по этому размыкающему множеству. Процедура, состоящая в выполнении сначала суперпозиции по некоторому размыкающему множеству, а затем исключения из полученной системы уравнения для каждой недостижимой переменной, т.е. такой внутренней переменной, от которой не зависит непосредственно или транзитивно ни одна из выходных,переменных, называется минимизацией.

Теорема 5.2. Пусть система уравнений и получена минимизацией монотонной системы I и для любых х в X и с? в (? символы х" и ц' обозначают те входное и внутреннее состояния системы Ь', которые является частями х и я соответственно. Тогда если (аЬ, гЬэ, и^е^Ш , то (а'Ь', г'Ь'г', иу)€ ;Г(£/).

В общем случае, когда у и <р не обязаны быть монотонными, динамический переход в I определяется для любой пары аг в Х<0 через функции уЯ* С -»<? и^: Х<0 -> У, вводимые при помощи следующего определения, в котором для любой функции на полурешетках Г: А ->■ В функция Г'*: А ->В определена как Г^(а)= ^ДЬ) по всем Ь ч< а: = и^£(*,<7)=рШ, где к удовлетворяет условию

р(к)=р(Ш), р( </И.)»^(*.р( £)) для Ь>Л, 1 удовлетвори-

-ет-условию-д(-.1)=<7и+1);-<7(СхТчСI)) для ЬЛ и с?(1)=с/. В этом случае утверждение теоремы 5.2 ослабляется до следующего: если (аЬ, гЬб, иу) е У (Ц и (а'Ь', г'рц, »г)е ?"(£.'), то р=Ь', , V ¿и, г^у.

6. Конечные автоматы Коночный'автомат Б=(Х,0,У, у где X -входной и У - выходной алфавиты, <? - множество состояний, ^ - функция переходов, у :Х"0 <?, и у - функция выходов, ¡с :Х>0 -» У, называется автоматом на полурешетках, если множества X, (?, У являются полурешетками. Под автоматом далее подразумевается именно автомат на полурешетках, а автомат Б с абстрактными множествами X, 0, У называется абстрактным автоматом. Автомат называется точечным, аддитивным, монотонным или квазимонотонным, если соответственно таковы его функции переходов и выходов. Автомат 2 называется гомоморфным (изоморфным) автомату 1=(Ы,Р,У,А ,<5), если существуют эпиморфизмы (соответственно изоморфизмы) полурешеток и -» X, Р -> О,

- 19 -

h3: V -» Y, что для всех upc- U*P

hjA(u.p) - ylh,u, h^p), hj(u,p) =f(h,u, h^p) ; в этом случае hthzhj назьшается гомоморфизмом (изоморфизмом) L на S, а автомат S - гомоморфным образом, или моделью, автомата L, который, в свою очередь, называется наибольшим гомоморфным прообразом автомата S, если

J(u,p) - sup h^yihfU, h£p), Ли,р) = sup hj1 f(htu, ft,p).

Теорема 6.1. Любая модель квазимонотонного, монотонного или аддитивного автомата является соответственно квазимонотонным, монотонным или аддитивным автоматом.

Теорема 6.2. Всякий наибольший гомоморфный прооораз квазимонотонного или монотонного автомата является соответственно квазимонотонным или монотонным автоматом.

Подавтомат автомата "на полурешетках называется точным подавтоматом, если его полурешетки являются подполурешетками соответствующих полурешеток автомата. Говорят, что автомат S (точно) реализуется автоматом L, если существует в L (точный) подавтомат L'=(W ,Р ,V', у , и гомоморфизм (соответственно изоморфизм) автомата L' на автомат S такие, что для любого V's U'^P" из существования для } '(IO нижней грани в Р следует существование для h^XiV) нижней грани в Q, а из существования для S'(,V) нижней грани в V - существование для нижней грани в Y.

Те ope м а 6.3. - Автомат тогда и только тогда реализуется квазимонотонным автоматом, когда он сам квазимонотонный.

Автомат на полурешетках называется точеным продолжением абстрактного автомата, если его функции являются точечными продолжениями соответствующих функций последнего.

Теорема б. 4. Пусть абстрактный автомат L • гомоморфно отображается на абстрактный автомат S и автомат на полурешетках S" является точечным продолжением автомага. S. Тогда существует точечное продолжение L' автомата L такое, что L' гомзморфио отображается на S".

Для автомата S и конгруэнций ¡\, }'г , <\ на его aojiypetei'!^:. X, Q, Y соответственно определяется автомат 'SJfJ/,^ " U'//,,<? ¡^ У//:,, y'.f'), в котором фумпишу' н о' являэтся апекваткими моделями функций у и у с точносшм (¡у;,,)1) и (;V;.соответственно. Если он является моделью авюм-ата S, то он казываб«;. адекватной моделью последнего с точностью / . Тройка копгдоп-ций ftf, р называется стабильной в автомат*« если пари (/¡/^.Д)

сохраняется функцией у , а пара (/;*/г ) - функцией <р .

Теорема 6.5. Если тройка конгруэнций стабильна в автомате S, то автомат S/j,^ является моделью автомата S и, следовательно, его'адекватной моделью. Обратно, если автомат S' яв- . ляется моделью автомата S, то существует стабильная в S тройка конгруэнций frfi,f3 такая, что S" и SJf,^» изоморфны, и следовательно, S изоморфен адекватной модели S с точностью .

Пара уравнений y"<?(.x,q), q=p(x,q) называется канонической системой уравнений автомата S=(X,Q,y,f,<p). Это есть система функций на полурешетках. Динамические переходы в ней и ее динамическое поведение называются соответственно динамическими переходами и динамическим поведением автомата S. Последовательность динамических переходов £"-( Tf T¿...называется цепью, если ^Ча.а^ , r¿hr¿H' u¿v¿ * для k^0™ i п. Командой над тройкой полу-

решеток X, Q, Y называется всякий набор из шести объектов с=(аЬ, rp, wz), где а<-Х, b*X, rc?Q, рс-0, v е У, zbY. В ней аг называется начальной точкой. Последовательность команд <? =(cr ... сл) называется цепью, если c¿=(a;a¡,^, P¿P¡rH, v¿z¿) Для i=l,...,n. Команда с реализуется в автомате S динамическим переходом T=(ab, rts, uv), если s4<p, и и v ¿z. Цепь команд & реализуется в S цепью переходов Г , если r¿ 4 р-н, u¿i y/¿ и v¿< z¿ для

1.....п. Система SC некоторых команд на X, Q, Y реализуется автоматом 5, если каждая команда в ней реализуется некоторым динамическим переходом -В^У;—система-5С-сильно~реализуется~в~5, если-каждая цепь команд в ней реализуется цепью динамических переходов в S. Система команд называется автоматной, если она реализуется монотонным автоматом.

Теорема 6.6. Система команд SC сильно реализуется монотонным автоматом S, если и только если она реализуется этим ав- • томатом.

Теорема б. 7. Система команд SC автоматна, если и только если для каадой ее команды c-(ab, rp, wz) можно указать такие t., и р. в С, что г N< t,, p„=inf( р, t,) и бинарные отношения

I. С. _ L С С

Г £ (X'Q)'Y и d £ (X*Q)<Q , определенные высказываниями (Ь, tc)fz , (а+Ь, tc)fnr , (b, tL)¿Грс , (a+b, tc) Н- , выписанными для всех команд с =(ab, rp, vz) в SС, квазимонотонны, и отношение $ реализуется монотонной функцией, стабильной в начальных точках всех коменд в ЭС.

Конечная последовательность N=Qez..S,z¿Sz.. .ZgS^z^Q^^ авто-

матов состояний =(Х^,Оу, ^ ) для J=1,2,...)J и отображений

гу. 0о* .. 0е-> X: для j=l, 2.....1+1, где Хгн , называется

автоматной сетью. В ней в,..... называются компонентами, г,,

...,ге - связями, 0С- входным алфавитом, 0гн~ выходным алфавитом, г(н~ функцией выходов и 1 - длиной сети. Сеть // называется сетью на полурешетках, если в ней все множества Х(,...,Хе и 00 ,<?,,... ,0М суть полурешетки и все связи ,... , ге суть гомоморфизмы полурешеток. Сеть на полурешетках квазимонотонная, если квазимонотонны функции всех компонент и выходов сети.

Сеть N имеет стандартную форму, если для любого .М,...,1 в ней Х^-'Х^.. .<Хц и г-(.я0яг . . .г^.(.яе) для

некоторых zíj:Q¿-* X¿■ , ¡=0,1,... ,1. Автоматом сети N называется автомат 5Л,-(0г, С!*...*0е, 0М ,г„ . где для х в 0о и я=Яг-.Це в 0,*..

= (у, (г,(х,ч) ) .....ч>£ (г^х.я) ,<?,)),

Сеть N (точно) реализует автомат 5, если ее автомат (точно) реализует 5. Если сеть N в стандартной форме точно реализует автомат 5 и есть соответствующий изоморфизм точного подавтомата в 5а, на автомат 5, то для любых * и ; в ряду 1,2.....1 можно

определить бинарные отношения г£, ^¿^ на полурешетке С? и бинарное отношение д. на полурешетке X как ядерные конгруэнции•гомоморфиз-мовлг-^', г^Т^ ц Ьг соответственно, где х-{яг.. Они называются конгруэнциями, индуцированными в 5 сетью N (при изоморфизме.Л,Ь^Ьз). Наконец, система конгруэнций на полурешетке полна, если их пересечение совпадает с равенством.

Теорема 6. 8. Для автомата Б, конгруэнций е^-и р£-. на полурешетке 0 и конгруэнций /*• на полурешетке X для 1,} в <{,... ,1} существует квазимонотонная сеть N в стандартной форме, точно реализующая Я и индуцирующая в 3 данные конгруэнции, если и только если выполняются следующие условия:

1) гс <л Ду для всех 1 и к

2) система конгруэнций г,.....г-, полна;

3) для каждого ] пара конгруэнций (/*•« (а. л ...п^п г.), с.) сохраняется функцией у; <! ^ '

4) для каждого ^ и любого Ууе О , где Б-- Х/^.* О/р,-*.. О/

Щ, иг{1х„^Ляп\...Лч„\гЛЯп?г:. ю-1.....и 2</^<1Ж(?/г.)1.

из существования для нижней грани в £ь следуит существование в (?/гг- нижней грани для V- -■([у (* : п>-1...../<•>;

5) для любого ЛеО, где 0-Х*О/г.. .к 0/г, . Л={х[аД____

] с щ "X С^ с^

. Д-> и |/л(П I, из существования для 4 нижней грани в О следует существование ^ У' нижней грани для Щх^.д,,,): п>= 1.....

6) для любого УгХ'С. где V ^х^: л=1,...,/е> и 3,< кС \ п( (?) |, из существования в О/г,*...* 0/?е низшей грани для V ={£ у

.. Л у (Хд.а^)]^: в=1,... следует существование в <? нижней грани для у(ЬО = .....й.

Говорят, что компонента сети N не зависит от компоненты или входа сети, если связь ,д/.. не зависит существенно от <5^ или соответственно. Сеть N называется каскадной, параллельно-последовательной или параллельной, если в ней каждая компонента не зависит от компоненты для ш, для j 1 или для всех j соответственно. Параллельно-последовательная сеть последовательная, если каждая для 1 не зависит от входа сети. Каскадная, параллельно-последовательная, параллельная или последовательная сеть N. (точно) реализующая автомат 5, называется его (точной) соответственно каскадной, параллельно-последовательной, параллельной или последовательной декомпозицией. Число состояний в автомате называется его порядком. Конгруэнция на полурешетке А нетривиальна, если она отличается от наименьшей (0,) и наибольшей (1Д) конгруэнций на А.

Теорема 6. 9. Квазимонотонный автомат г допускает точную параллельную квазимонотонную декомпозицию на компоненты мень-_шего_порядка.^если_и_только-если-на-полурешетке-его-состоянийсу— щзствует полная система нетривиальных конгруэнций г^ , со-

храняемых функцией у и удовлетворяющих условиям 5 и 6 теоремы б. 8.

Т е о р е м а 6.10. Квазимонотонный автомат 5 допускает точную каскадную квазимонотонную декомпозицию на компоненты меньшего порядка, если и только если на полурешетке его состояний существует полная система из двух нетривиальных конгруэнций г, таких, что ег, сохраняется функцией у и удовлетворяются условия 5 и 6 теоремы 6.8 (для 1=2) и следующее условие

4') из существования в ХА0/г1 * 0/с, нижней грани для

{*т[с/я]£-, !<?„,! ^ : .....^ следует существование в 0/гь нижней

грани для : п)=1.....кг.

Т е о р е м а 6.11. Автомат 5 допускает точную параллельно-последовательную квазныонотонную декомпозицию длины с, если и только если на его полурешетке состояний существует полная система 1юягрузнций с. ,..., с таких, что конгруэнция с, и пари конгру-

энций (0_*(гг ,1Г,-),г>) для 1=2.....J сохраняемы функцией у и вы-

Jiy bit i

полняются условия 4-6 теоремы 6. 8.

Теорема 6.12. -Автомат 5 допускает точную последовательную квазимонотонную декомпозицию длины 1>У 2, если и только если на его полурешетке состояний существует полная система кон-

груэнций г,.....ze таких, что конгруэнция cf и пары конгруэнций

(Оу<(%_,/!), ф и Д-®я J=2.....1 сохраняемы функцией У

и выполняются условия 4-6 теоремы 6. 3.

Покрытие Р полурешетки Q регулярно, если для любых его блоков 4 и Виз 3 as A3 be- В (a 4 b) следует A N< В. Покрытие Р сохраняется в автомате S, если для любых х в X и А в Р существует В в Р,. что у (х, 4) £ В. Система покрытий fj ,...., £ полурешетки 0 удовлетворяет условию ортогональности, если |4(ч.. л 4^ |ч<1 для любых .4., в Fj.....4g в .

Т е о р е м а 6.13. Пусть Q' =Р, , где .....суть

регулярные ассоциативные покрытия полурешетки Q квазимонотонного автомата 5, сохраняемые его функцией у и удовлетворяющие условию

ортогональности, и для любого W**ia1ql.....akqk>sX*Q и любых

(4,Л...4Л,)<? О*, где и Атп... л ^,„=<<7га>. выполняются

условия:

1) из и существования для <a„4Im... Ат\го-1.....к>

£X*Q' нижней грани в Х*(7 следует существование в У нижней грани дляу(Ю;

2) из | К 0) I и существования в 0' нижней грани для некоторого V<=iBin... В(т: т* 1,... ,k>£Q', где для 1-1,..,1 и .. ,к блок Bin является минимальным (по порядку в Р ) из тех блоков Bt в Рс, для которых y(am Aim) следует существование в Q нижней грани дляЧ'(Ю-

Тогда сеть W=Xz,S( z.^... zeStz(t,Y, где для каждого 1-1,... ,1 компонента ,ус) и для а в X и А. в ^ блок ул С а явля-

ется минимальным (по порядку в Р(-) из тех блоков В; в Р , для которых у(а 4£-) £В£, z.(a а и

f{a,q), если qe 4;л...л4{,,

z„ , (а 4... .4 ) =

' I sup У, если 4f/>. ..л Ае"0,

является квазимонотонной параллельной декомпозицией автомата S.

Теорема остается в силе, если в ней за ^(3,4^) и соответственно за В£|1г принимается не минимальный из указанных блоков в Р., но наибольший из них.

I е о р е ма 6.14. Пусть С-if* Рг , где Pt и Р} суть ассоци-

ативные покрытия полурошетки Q квазиюнотонного автомата S, удовлетворяющие условию ортогональности, покрытие Pf регулярно и сохраняется функцией у и для любого (Ma,q( ,... ,аддА> sX«Q и любых • где ■■■>!< и AZm=iqm), выполняются условие 1 теоремы 6.13 при 1-2 и следующие условия:

2) из 2 4к ч< | и существования в Q' нижней грани для некоторого У={В)!П В2т: ,... ,Й£ 0', где для т=1.....к блок В1п является минимальным (по порядку в /J) из тех блоков Bt в Pt , для которых f (аяг В(, и блок В2п является наибольшим (по порядку в Р,) из тех блоков Вх ъ Р^, для которых ^ (ад,дп)е В2, следует существование в 0 нижней грани для у (&0;

3) из 24к$1л(Рг)1 и существования для iamA^m А^-.

-X*Q' нижней грани в X*Q' следует существование в Pt нижней грани для .....ВцсУ^р1, где для лИ......к блок Bzn является наибольшим (по порядку в Pz) из тех блоков В1 в PL, для которых

Тогда сеть M^Xz(S/zzSazJУ, где S2=(X»i> ,уг)

и для любых а ъ X, At в Р1 и Az в Р2 блок ц (, А,) является минимальным (по порядку в Р}) из тех блоков В, в Р, , для которых у (а Л()£В(, <f^(a 4,,^) является наибольшим (по порядку в Рг) из тех блоков В„ в , для которых у (а,А^Аг) s В^, zf (a Af А^ =а,

(Via.qf), если чеДлАя

-z■3{а-А.АЛ-=-\-—:-' 2---

' * I sup У, если At<lAz=0,

является квазимонотонной каскадной декомпозицией автомата S.

Теорема остается в силе, если в ней за ц(а,At) и соответственно за В1п принимается не минимальный, но наибольший блок иди за s^(a A^Aj) и соответственно за- Birn_ принимается не наибольший, но минимальный блок из числа указанных.

Автомат ¿=(X,Р, У,^ где Рев"; называется кодом автомата 5=(Х,0,У, fj если существует эпиморфизм полурешеток hF^Q, что hMx.p) =f(x,h(р)), <fU.p) -у(х,Л(р)) и для любого W£X*P из существования для V нижней грани в Х*ВЬ следует существование для M.W) и нижних граней в В* и У соответственно, а из существования для JHW) нижней грани в Вл--существование для ЛА(Ю нижней грани в 0; в этом случае h называет-' ся кодированием автомата S, а полурешетка В и числа л и £=|и(В) t - соответственно основанием, длиной и значностью кодирования h и кода L. Код L называется наибольшим, если автомат L является наи-

большим гомоморфным прообразом автомата г при гомоморфизме /г Автомат I. называется квазимонотонным на подурешетке в аР, если его функции и I? квазимонотонны из Х<(3 в в и в У соответственно.

Т е о р е м а 6.15. 1) Всякий код автомата с основанием В и длиной п является автоматом, квазимонотонным на в4". 2) Всякий автомат, допускающий кодирование, квазимонотонный. 3) Всякий наибольший код автомата квазимонотонный; наибольший код монотонного автомата монотонный. 4) Любому кодированию автомата отвечает по крайней мере один монотонный код.

Т е о р е м а 6.16. Любое кодирование полурешетки состояний квазимонотонного автомата является кодированием самого автомата

Т е о р е м а 6.17. Автомат тогда и только тогда допускает кодирование, когда .он квазимонотонный.

Пусть гО= пах М|, где = МД^ V МАО) еМ(<?) и

Л еМСЯ 012.

для любого А В М(0):

1) АеМдО, если А 5 (X 0);

2) А е и (5), если существует я,.... „> £ Х*0, что х,.

...,х^ имеют общую нижнюю грань в X, А£<я1.....и хотя бы

одно из подмножеств г (3 £ 0 или (2) £ У не имеет нижней грани в полурешетках <? и У соответственно;

3) 4£МЛ(0), если А={а(,Ь}, где Ы 0 и а«-л<0) - С(Ь).

Автомат называется непримитивным, если он не является гомоморфным образом автомата, функция переходов которого реализуется константой.

Т е о р е м а б. 18. Непримитивный квазимонотонный автомат 5 с - точечной полурешеткой состояний тогда и только тогда допускает к-значное кодирование, когда к >,г(5).

Т е о р е м а б. 19. Непримитивный квазимонотонный автомат 5 с точечной полурешеткой состояний допускает кодирование с основанием В '= М, если и только если |М|^г(5).

Говорят, что автомат Ь словарно реализует автомат Б, если Удё 03 ре РУ<<еХ\Х(ы. ,р)ч<у("<■ .а)): говорят также, что словарно реализует 5 с моделированием автомата состояний, если существует эпиморфизм полурешеток Ь. 0-*Р, что Ьг(х.а)- } (х.Ш) и о ( С х, . Ассоциативное покрытие Р полурешетки состояний (? квазимонотонного, монотонного или аддитивного автомата 5 согласуется с Б, если существуют соответственно квазимонотонные, монотонные или аддитивные функции у':Х<Р -> Р и у':Х*Р -» У, что для любого х в X и любого бло1са А в Р имеет место включение у (х,Л) £ f'{x,Л) и

значение <f'ix.A) является в У нижней гранью для fix, А); в этом случае, если F^Q/tr для некоторой конгруэнции с , говорят, что с согласуется с S.

Т е о р е ы а 6.20. Если аддитивный автомат S словарно реализуется аддитивным автоматом с а состояниями, то на полурешетке состояний в S существует П-покрытие мощности не более т, согласуемое с S. Обратно, если на полурешетке состояний аддитивного автомата S существует П-покрытие мощности и, согласуемое с S, то S словарно реализуется аддитивным автоматом с т состояниями.

t е о р е ма 6.21. Квазимонотонный, монотонный или аддитивный автомат тогда и только тогда словарно реализуется с моделированием автомата состояний соответственно квазимонотонным, монотонным или аддитивным автоматом с т состояниями, когда на его полурешетке существует согласуемая с ним конгруэнция индекса т.

Ставятся следующие задачи минимизации в заданном классе А автоматов на полуреиетках: для автомата S из класса А найти авто-иат L в классе А с наименьшим числом состояний, который либо словарно реализует автомат S - задача 1, либо словарно реализует S с моделированием полурешетки состояний - задача 2, либо словарно реализует S с моделированием автомата состояний - задача 3. Ввиду теорем 6.20 и б. 21 задача 1 для класса аддитивных автоматов и задача 3 для лххЗого из классов квазимонотонных, монотонных иди аддитивных автоматов сводятся к пост роению на _полурешетке - состояний -заданного автомата согласуемых с ним соответственно П-покрытия наименьшей мощности и конгруэнции наименьшего индекса

7. Переклтательнш сета Рассматриваются сети, называемые переключательными, в которых ребра наделены проводимостями из некоторой полурешетки прово-димостей Р, а полюсы - состояниями из некоторой полурешетки состояний S, где (S.v.P.k) является полурешеточно упорядоченной алгеброй и.S содержит высокоимпедансное состояние Ог. Решаются задачи анализа таких сетей, состоящие в определении полных проводи-мостей между вершинами данной сети и функций состояний ее вершин. В дистрибутивных сетях (когда алгебра проводимостей (P,a,v) дистрибутивна) полные проводимости строятся методами, заимствованными из теории контактных схем (методы цепей, сечений, возведения в степень матрицы непосредственных проводимостей, последовательного разложения и др.), а для произвольных сетей, для которых эти ме-

тоды не пригодны, с указанной целью предлагаются новые общие методы - комбинаторный, короткого замыкания, характеристических функций, а тага® метод имитационного моделирования.

Пусть 0,.. есть дизъюнкция проводимостей всех цепей, соедини-

v

отих вершину 1 с вершиной ] в бесповторной переключательной сети, ^ - искомая полная проводимость последней между вершинами 1 и ], а - произвольный набор значений ее аргументов х1 ,. . . ,хк- проводимостей ребер сети, и хМ, если х = с, и хе=0, если х с.

Комбинаторный метод (вычисляется (а)). В 0-. подставляют-ся значения переменных из а, равные 0 или 1; в полученной формуле выполняются всевозможные поглощения по правилу А * (Ал В)=А, после чего в нее подставляются значения остальных переменных из а; константа, в которую таким образом свертывается и есть Г. (а). *

Метод короткого замыкания:

Ь IX,.....V - V .

<г с, . . . сц • «

где дизъюнкция берется по всем наборам констант с;.....с^ в {0,1},

2<с)=2, если с=1, г(с) =2, если с=0, и получается из %

подстановкой 1 вместо каждой переменной х^, для которой с^ =1, с последующим выполнением всевозможных поглощений.

Метод характе р^стиче_с_к и_х ф у н к_ц и й: Г'; = V Г,7 а с, Л? , Г.'. - >Г. лхг.. , Г.*- дГ: Л Т.. .

? с^Б ' У У У _ ^ ' ^ ? ^ ? г/- Лег.; л 'г. ,' я!'- V,- лЪ. Л • . Г?'-^, А 'г.. Л *г.. .

Ч У V '</ у V У У .У # у у г|Г л 'у л. и есм = • •лто

'г., -'о.. - V'* л 'лг л...л'* , СЛ. =сй,. - Л (°л- ).

Я У к *< К У К И

а выражение для ^ получается из выражения для щ последова-

телышм применением следующих действий: 1) приведение к виду днф (законы де Моргана и дистрибутивность); 2) замещение каждого выражения ¡хл^х равным х"\ 3) подстановка *х, х° и х' вместо х*, "х и 1х соответственно; 4)-замещение каждого х" равным 'хухх и каждого Р равным

функции состояний вершин в сети в общем случае определяются (после отождествления вершин, связанных замкнутой цепью) методом имитационного моделирования итерационной процедурой приписывания состояний вершинам сети так,

что для любого ребра к1 с проводимостью р^ и состояниями вк и его концов вершине 1 приписывается новое состояние - результат моделирования ребра - * Бк). В дистрибутивном же-случае, а

также в сети, разделительной со стороны вершины j (когда в и для разных полюсов 1 и к нет общей переменной со значением в X') У функция состояний последней в зависимости от состояний з,.... полюсов сети и от проводимостей х.,...,хм ребер сети выражается

Л!

•ик 5 («1..........- £ Vгу (*/•• • •

8. Схеиы

Схема - это тройка объектов (X, 2,20), где X - конечное множество элементов схемы; г - множество ее узлов, или цепей, и 20 -множество полюсов схемы, Элемент схемы характеризуется ко-

нечным множеством своих полюсов и, в свою очередь, может Сыть схемой из других элементов. Множество узлов 1 является разбиением множества всех полюсов элементов в схеме. Элемент схемы, имеющий и полюсов, называется переключательным, если выделено некоторое подмножество его полюсов, названных управляющими, и элементу поставлена в соответствие квадратная матрица Пе^ || размера тхт, в которой есть монотонная функция, на полурешетках, названная проводимостью элемента от его полюса ./ к полюсу ], принимающая значения в некоторой полурешегке проводимостей Р и зависящая от аргументов, которые поставлены во взаимно однозначное соответствие -управляющим -полюсам элемента и принимает значения в некоторой— полурешетке состояний £, Предполагается, что в 5 есть высокоиы-педансное состояние и что (5.17,Р,*) и суть полурещеточно

упорядоченные алгебры: первая - векторная алгебра состояний, вторая - алгебра проводимостей. ' Пара (Р,Б) называется типом элемента, и схема из однотипных переключательных элементов называется переключательной схемой. ' Тип элемента в ней называется ее типом. Узел в переключательной схеме называется управляющим, если он содержит управляющий полюс некоторого элемента. Различным узлам переключательной схемы присваиваются различные переменные со значениями в названные собственными переменными этих узлов. Те из них, что присвоены управляющим узлам, названы управляющими переменными схемы. Различным полюсам в схеме, кроме того, присвоены различные переменные со вначениями в й, отличные от собственных переменных схемы й названные ее входными переменными, а также различные переменные, отличные как от собственных, так и от вход-

них переменных и названные выходными переменными схемы. Таким образом, одному и тому же полюсу схемы присвоены три переменные -входная, выходная и собственная. Дизъюнкция всех проводимостей элементов схемы от их полюсов в узле а к их полюсам в узле Ь, в которых (проводимостях) каждый аргумент замещен управляющей переменной узла схемы, содержащего тот управляющий полюс элемента, который соответствует этому аргументу, называется непосредственной проводимостью схемы между ее узлами.а и Ь (от а к Ь). Бесповторная переключательная сеть К называется соответствующей данной переключательной схеме N. если вершинами и полюсами в сети К являются соответственно узлы и полюсы схемы М и ребро аЬ существует в К тогда и только тогда, когда непосредственная проводимость схемы N от а к Ь не есть 0. В этом случае функция, которая получается замещением в полной проводимости между вершинами а и Ь сети К переменной проводимости каждого ребра к1 непосредственной проводимостью схемы И между к и 1, называется полной проводимостью схемы ЛГ между узлами а и Ь (от а к Ь). Аналогичным образом определяется функция состояний узла ) в схеме N по функции состояний вершины ] в соответствующей сети К. По теореме 3.2 непосредственные и полные проводимости в переключательной схеме является монотонными функциями от ее управляющих переменных, а функции состояний узлов - монотонными функциями от входных и управляющих переменных схему. Уравнение У; . где у, и - соответственно выходная и собственная переменные, присвоенные полюсу 1, называется уравнением для выходной переменной полюса ¡. Уравнение 2.-у (*,,... ,хЛ,г..), где г- - собственная переменная узла х,, ..., хп- все входные переменные схемы, }'• - функция состояний узла ) и 2у- набор ее существенных аргументов из множества управляющих переменных схемы, называется уравнением для собственной переменной узла Совокупность уравнений для всех выходных и достижимых собственных переменных схемы N называется канонической системой уравнений схемы //. На нее, а вместе с ней и на схему N распространяются все понятия и утверждения, относящиеся к системам уравнений на полурешетках, в том число понятия внутренней переменной, состояния, динамического перехода и динамического поведения, процедура минимизации числа уравнений и др. Переключательная схема называется комбинационной, если число внутренних переменных в ней после минимизации равно 0; в противном случае схема называется последовательностиой. Динамический переход в комбина-

- 30 -

ционной схеме вырождается в четверку вида (аЬ, иу).

Переключательные элементы являются математическими моделями физических компонент в БИС и СБИС - диодов, резисторов, транзисторов. Например, полевой транзистор моделируется переключательным элементом с тремя полюсами, каздый из которых управляющий; проводимости в нем между затвором и остальными полюсами равны 0, а проводимость между истоком и стоком есть функция от состояний всех его полюсов, которая определяется типом данного транзистора. Логические компоненты в БИС (вентили, ключи, триггеры) моделируется функциональными элементами - простейшими переключательными схемами. Соответственно этому переключательные и функциональные схемы - это математическая модель БИС и СБИС на транзисторном и вентильном уровнях абстракции, функции состояний в них определяются при помощи одних и тех же процедур анализа переключательных схем, которые (процедуры) не привяааны к какому-либо типу БИС, благодаря чему сама эта модель в равной мере эффективна и для N1*011, и для КМОП, и для любых других типов БИС и СБИС.

Говорят, что система команд К, где каждая команда имеет вид с=(аЬ, иг) и в ней а и Ь принадлежат полурешетке В\ шаг- полурешетке В"г и В -£г, динамически реализуема, если существует комбинационная схема с п входами и т выходами, в которой для любой команды с в К есть динамический переход (аЬ, иу), удовлетвори ющий соотношениям ич-и'-и-у ч<-г.--—--

Теорема 8.1. Система команд К динамически реализуема, если и только если бинарное отношение р^Вп*Вт', определенное высказываниями Ь рг и (а+ЬЭри', выписанными для всех команд (аЬ, «г) в К, квазимонотонно.

Ввиду этой теоремы синтез комбинационной схемы с заданным динамическим поведением осуществляется так: сначала проверяется Условие динамической реализуемости данной системы команд К (теорема 3.9) ив случае, их выполнения способом, изложенным в доказательстве . достаточности условий теоремы 3.9, строится квазимонотонная функция Г, выражающая зависимость выходных состояний искомой схемы от ее входных состояний; затем из элементов заданного базиса строится комбинационная схема, реализующая функцию Г.

Автомат, чья каноническая система уравнений есть минимизированная каноническая система уравнений последовательностнои схемы, называется автоматом этой схемы. Говорят, что система команд ЗС, где каждая команда имеет вид с=(аЬ, чб, шг) и в ней а и Ь принад-

лежат полурешетке X, иг и г - полурешетке У и я и я - полурешетке С, динамически реализуема, если существует последовательностная схема М, подавтомат 1=(и,Р,У,Х,$) автомата схемы Н и эпиморфизмы полурешеток Ь?:(/->Х, \\Р-* О, /у К -»У, такие, что: 1) для любых и, , и, в и и р,, р, в Р из Ь, (и,) (и,) и Л, (р.) «Ь, (р,) следует

ЬЛ(и,,Р,) - и Ь/(и, ,ц ) -

2) для любой команды с=(аЬ, цз, уг) в Ж найдется в динамический переход Т=(и;и1, ptJr, v, ^ ), в котором (и,) =а, Л, (а )-=Ь, \(р) =<7, /^(гХсг, ^(и, кОС и ^(к, ).<2.

Т е о р е м а 8.2. 1) Всякая динамически реализуемая система команд 5С авгоматна 2) Автоматная система команд 5Г на полурешетках Л, О, К динамически реализуема, если полурешетки X, О, К точечные и допускают 3-значное кодирование.

В соответствии с этой теоремой синтез последовательностной схемы с заданным динамическим поведением сводится к следующей цепочке действий: сначала проверяются условия авгсматности заданной системы команд 5С Стеорема б. 7) ив случае их выполнения способом, изложенным в доказательстве достаточности условий теоремы б. 7, строится автомат реализующий 5С; затем проверяются условия существования кода необходимой значности для автомата 5 (теорема 6.18) и в случае их выполнения способом, изложенным в доказательстве достаточности условий теоремы 6.18, строится автомат - код автомата £ требуемой значности; наконец, синтезируется комбинационная схема в заданном базисе, реализующая функции автомата Ь. В эту цепочку могут быть вставлены процедуры минимизации и де-крмпозиции автомата 5 (из гл.6).

При наличии некоторых ограничений на схему последняя называется допустимой, если она удовлетворяет этим ограничениям. Разбиение схемы на допустимые подсхемы называется допустимым разбиением. Количество подсхем в нем называется длиной раэбиения. Задача, состоящая в-нахождении кратчайшего допустимого разбиения схемы X, называется ЗКДР X. Формулируется метод сокращенного обхода дерева поиска для решения любой ЗКДР X (для простоты изложения подсхема отождествляется с множеством своих элементов):

1. Х(,) :-Х, «=/?„, . -1.

2. Вычисляется и/0.....>- - ч'( '¡>(Х"})); '

3. (с.:=(с.+1. Если к->1Г, то^п. 4; в противном случае х'"^:- ' Х(0- X, ¡Г-.- Ри <Х!.'/'}, Если ' - 0, то п. 5; иначе если |/?|> (X ^), то п.2, в противном случае л. 4.

4. Если i S<1, то п. 6; иначе i:=i-l, : =1?-iX^1 > и п. 3.

5. Если |ffk|f?4, то п. 4; в противном случае i?. =i? несли |i?|>Fc (X), то п. 4, иначе п.6.

6. Конец. Если R + Ф, то R - решение задачи; в противном случае задача не имеет решения.

Здесь R0, if, у и F0 - параметры метода: RB - начальное допустимое разбиение, доставляемое некоторым эвристическим алгоритмом (в отсутствие такового условно считается Rc-Ф и | ffj, | = <=« ) ; f -алгоритм перечисления (в любой подсхеме У перечисляет некоторые допустите ее подсхемы, содержащие некоторый фиксированный элемент в У); у - операция сокращения (ее результатом является некоторое подмножество перечня f(Y)); F0 - функция нижней оценки (для любой подсхемы У значение /¿(У) не превосходит наименьшего числа подсхем в допустимом разбиении У). Параметры метода называются подходящими к конкретной ЗКДР X, если в их определении и в постановке последней условия допустимости совпадают и, кроме того, для любой подсхемы Y в X и для любого допустимого разбиения R схемы Y существует такое допустимое разбиение R' схемы Y, что и

Vf (У) Л R . При подходящих к ЗКДР X параметрах метода последний тогда и только тогда доставляет решение этой задачи, когда таковое существует.

Схема, в которой каждый узел одноэлементный, называется свободным модулем. Рефлексивное и транзитивное бинарное отношение^ -(квазипорядок)~на~множестве~элементов~схем называется покрытием и обозначается > . Для переключательных элементов условие ai>b (а покрывает Ь) мокет означать, например, что функции состояний элемента Ь реализуются функциями состояний элемента а и тем самым в побей схеме элемент b может быть заменен элементом а с сохранением реализуемых схемой функций. Для заданной схемы X говорят, что элемент а поглощает элемент b на схеме X, и пишут a i>b, если для любого элемента х в X из b > х следует а г> х. Свободный модуль m покрывает (поглощает на X) некоторую схему Y, если каждому элементу последней можно поставить во взаимно однозначное соответствие покрывающий его (поглощающий на X) элемент модуля; в этом случае пишут m и Y (соответственно тс£ У). Ясно, что из m с-У следует mi.>Y. ЗКДР Л', в которой подсхема считается допустимой, если она покрывается некоторым модулем в заданной системе свободных модулей М, называется задачей о кратчайшем покрытии (схемы X) .свободными модулями (системы Ai).

Свободный модуль называется линейно упорядоченным для X, если его элементы образуют ряд е, .. с^е^, в этом случае е( называется первым, ае^- последним элементами модуля. Система свободных модулей М называется линейно упорядоченной (л. у. с.) для X, если в ней каждый модуль линейно упорядочен для.Л и модули образуют ряд т^, где для каждого ]=1.....первый элемент

модуля т^ поглошается на X последним элементом модуля л?£; в этом случае элементы схемы X можно записать в ряд следующим образом: сначала выписываются элементы, покрываемые модулем т, и не покрываемые модулем для затем элементы, покрываемые иги не покрываемые т- для 1>2, и так далее, пока не будут выписаны элементы, покрываемые лу, среди элементов, покрываемых модулем т.-е^у?.. с^е^) и не покрываемых т^ для ¡>у, первыми в ряду выписываются элементы, покрываемые элементом е, и не покрываемые элементами вк для к >1, вторыми элементы, покрываемые е, и не покрываемые ек для к >2. и так далее, пока не будут выписаны элементы, покрываемые еь. Этот ряд называется соответствующим заданной

л. у. с. М. Для любой подсхемы У={ у,.....урУ и заданной системы

свободных модулей АМт,.....т^У с фиксированной нумерациией элементов и модулей через У(к,]) для М,...,ри к=1.....с? обозначается подсхема в У,- которая индуктивно определяется так: если АгУ(к,Л и 1 есть наименьший номер элемента в У-А со свойством т то у.сУ1к,]). Если М есть л. у. с., элементы в У записаны в порядке их' вхождения в ряд, соответствующий системе М, и к есть наибольший номер модуля в М, покрывающего элемент у, , го определяются: .

[ Ш1,1)>, если к~ 1,

<('100 -

НУ(М), У{к-1,1)}, если к >1;

МУ(1,1)), если ^-1 или |У(2,1)|ч<|т.

У2(У) - 1

нУ(2,1)} в противном случаэ;

<рЗ(У) - Шк.1)Ь Система модулей М называется неприводимой для X, если в ней ¿¿с>*-т> 1-у. Свободный модуль называется однородным для X, если для лкюых элементов а и Ь в нем а г>Ь и Ьс;1а

Теорема 8.3. Пусть ЗКДР X - это задача о кратчайшем покрытии схемы X линейно упорядоченной и неприводимой для X системой свободных модулей Ы и

- 34 -|Ч>2, если |М|=2, f И <f3, если модули в М однородны для X, I <j> 1 в остальных случаях. Тогда <f подходит к данной ЗЩ> X в качестве алгоритма перечисления в методе сокращенного обхода дерева поиска.

Система свободных модулей W0=ím/, ..., m(¡} называется специальной, если для некоторого натурального u, 2su?g, модули т,,..., тодноэлементны, модули т^и двухэлементны и линейно упорядочены, m^íc,d}, aob и c>d, подсистема W0= imUH> есть л у. с. однородных модулей и для любого элемента е схемы X выполнены условия:

1) boe mtít< t> е;

2) а>в & d>e Ь>е;

3) b>e в с > е =t> 3 t^.u+3 ( m^ £> е);

4) 7íb>e) V fc»iH2 ( 7 (1й >e));

Б) l(ci>e) V t>u+3 ( 7(л^ oe));

6) ci>e 8 7(aoe) V t»u-l (t * u >e));

7) ci> e & 7(d>e) V t>u (7 (л^£>е)).

Для заданной специальной системы М0 в любой подсхеме Y в X определяются подмножества элементов Yk для k=l,...,q как etY^a^ е é У а тАС> е & V t>k 7 (m{t> е), . а также подмножества элементов W - -te: eeíit, & dP-еУ, Y^ = Y^ - Yi¿nt \

Y£.¿ - ie: eeY^i ft aOe>, y£,¿ = Y4,,¿ - Ytu ,

- <e: eeY^.c SaM, Y&,c = Y%,c - _

и подмножество UsY£4¿, удовлетворяющее условию: если или НиХбк \Y¿íc I, то |í/|=0; в противном случае |£/|>1. Строится^ последовательность (Kt,Kt.....%,-)=( .....täc» ^Л- • Cci-W'

Yu.,,Yuti»I- Yutfl < и элементы в У записываются в ряд yfyL---yp в порядке их вхождения в множества К(.....рассматриваемые в данной последовательности, а именно: сначала выписываются, элементы из K1t затем из Кг и т.д. до Через J обозначается множество номеров л всех тех элементов в этом ряду, для которых п >1 и ти^1о<у1 или m^o iy1 ,jjНаходится к из условия yf е Yk и определяется у0( У) как

И <У, ,У-> >, если k=u, J гр И i » min J;

Ч'О(У) ' u

U )'(A",1) ) в остальных случаях.

Теорема 8.4. Пусть ЗКДР X - это задача о кратчайшем покрытии схемы X модуля «и специальной системы М() и f = у 0. Тогда f

подходит к данной ЗКДР X в качестве алгоритма перечисления в методе сокращенного обхода дерева поиска.

Система свободных модулей называется разделимой на подсистемы если модули из разных подсистем не покрывают общих элементов схемы. Есть много (более двух десятков) промышленных серий интегральных микросхем, которые являются системами свободных модулей, разделимыми на подсистемы, каждая из которых либо линейно упорядоченная, часто даже одно- двухмодульная или с однородными модулями, либо является частью некоторой специальной системы модулей. Кратчайшее покрытие схем модулями любой из этих систем без труда строится методом сокращенного обхода дерева поиска с применением подходящих алгоритмов перечисления ус для 1=0,1,2,3.

ЗАКЛЮЧЕНИЕ

В диссертации разработана- теория дискретных автоматов на полурешетках, ориентированная на приложения к анализу, синтезу и адекватному моделированию систем логического управления, построенных на элементной базе современных БИС и СБИС и интегральных микросхемах отечественных промышленных серий. Теория обеспечивает необходимыми понятиями, моделями, методами и теоремами процесс сквозного синтеза асинхронного управляющего устройства от системы команд, задающей динамическое поведение устройства, до его принципиальной электрической схемы из компонент БИС или ссрийных микросхем, реализующей данное динамическое поведение, и обратный процесс - анализа,, имеющий целью определение динамического поведения устройства по его принципиальной схеме. Важнейшими шагами процесса синтеза являются абстрактный синтез, минимизация, декомпозиция и кодирование для автомата на полурешетках, минимизация его канонической системы уравнений, эквивалентные преобразования, минимизация форм представления и функциональная разделимость функций на полуреюетках, синтез переключательной схемы, реализующей заданные полурешеточные функции, покрытие схем свободными модулями и др. Процесс анализа сводится к нахождению полных прово-димостей и функций состояний в переключательных сетях, построению канонической системы уравнений данной схемы и ее автомата на полурешетках состояний и определению динамического поведения последнего. Предложенная теория позволяет для управляющих устройств, моделируемых дискретными автоматами на полурешетках, строить их

адекватные математические модели с любой наперед заданной точностью. Это достигается, благодаря возможности формализации понятия адекватной модели и ее точности, которую предоставляет аппарат теории полурешеток и полурешеточно упорядоченных алгебр.

На защиту выносятся:

- концепция дискретного автомата, снабженного структурами конечных верхних полурешеток и названного дискретным автоматом на полурешетках, в соответствии с которой теория дискретных автоматов рассматривается как пограничная с теорией полурешеток и полурешеточно упорядоченных алгебр;

- формализация понятий адекватной модели и ее точности, динамического поведения и физической реализуемости дискретного автомата, позволяющая ставить и решать задачи анализа, адекватного моделирования и схемной реализации динамического поведения дискретных автоматов с заданной точностью;

- элементы теории полурешеток и полурешеточно упорядоченных алгебр, служащие математической основой теории дискретных автоматов на полурешетках, в том числе полурешетки и полурешеточно упорядоченные алгебры проводимостей, состояний и к-значной логики, играющие фундаментальную роль в моделировании БИС на транзисторном и вентильном уровнях абстракции, основные законы в них и, в частности, свойство недистрибутивности полурешеточно упорядоченной алгебры ^-значной логики (при к >2); изоморфизм точечных полурешеток полурешеткам подмножеств своих точек и полуреиеткам состояний; общий метод построения полурешеточно упорядоченных алгебр - метод точечного расширения абстрактных алгебр; понятия адекватной модели и ее точности для полурешеток и полурешеточно упорядоченных алгебр, метод построения адекватных моделей полурешеток подмножеств и интервалов с точностью до зквивалентностей на множествах их, минимальных элементов; понятие покрытия полурешетки и изоморфизм любой полурешетки ее покрытию со сложением, тождественным пересечению; понятие кодирования полурешетки, условия его существования с заданными значностью или основанием, метод построения кратчайшего кода точечной полурешетки;

- результаты по теории функций на полурешетках, относящиеся к их классификации, эквивалентным преобразованиям и минимизации форм задания, адекватным моделям, полноте, функционально»! разделимости, в том числе Еажнейшие классы функций на полурешеисах -аддитивные, точечные, монотонные и квазимонотонные, их свойства и

отношения между ними, конструктивные тесты квазимонотонности, условия достаточности подмножества аргументов и метод минимизации их числа, критерий функциональной разделимости по заданному разбиению, понятие адекватной модели для функции на полурешетках и ее свойства для функций важнейших классов и их суперпозиций; методы построения минимальной и кратчайшей днф для представления И реализации полурешегочных функций к-значной логики (функций в Я); процедуры приведения (в условиях недистрибутивности) произвольной формулы для функции в Р. к виду днф и совершенной днф; построение полной и независимой системы квазимонотонных функций в Р- для реализации всех квазимонотонных функций в Р.. П-формулами над функциями в системе;

- результаты по абстрактной и структурной теории конечных автоматов на полурешетках, относящиеся к их динамическому поведению, адекватному моделированию, синтезу, анализу, минимизации, декомпозиции, кодированию состояний, в том числе понятие динамического поведения и метод минимизации числа уравнений автомата, сохраняющий его динамическое поведение; важнейшие классы автоматов на полурешетках (точечные, аддитивные, монотонные, квазимонотонные), их сохраняемость в гомоморфных образах и прообразах, отношения реализации и точечного продолжения между автоматами, связь реализуемости с квазимонотонностью, точечной продолжаемости с гомоморфизмами, понятие адекватной модели для автомата на полурешетках и характеризация адекватных моделей автомата в терминах стабильных ■ троек конгруэнций; понятия системы команд на полурешетках, ее реализуемости, сильной реализуемости и автоматности, эквивалентность реализуемости и сильной реализуемости, условия автоматности системы команд и метод синтеза автомата, реализующего заданную автоматную систему команд; понятие декомпозиции и квазимонотонной декомпозиции для автоматов на полурешетках, характеризация точных квазимонотонмых декомпозиций в терминах систем конгруэнций на полурешетках автомата, необходимые и достаточные условия существования некоторых нетривиальных точных параллельных, каскадных-, последовательных и параллельно-последовательных квазимонотонных декомпозиций, параллельная и каскадная декомпозиция с помощью ассоциативных покрытий полурешетки состояний автомата; понятие кодирования для автомата на полурешетках. условия существования и методы кодирования с заданной значностью и с заданным основанием; постановка задач минимизации в заданном

классе автоматов на полу;.. шегках с моделированием автомата состояний или без и их решение дли важнейших классов автоматов; понятия переключательной сети и переключательной схемы на полурешетках проводимостей и состояний, методы их анализа в дистрибутивном и общем случаях; постановка задач синтеза комбинационных и после-довательностных схем с заданным динамическим поведением, условия существования решения для них и метод синтеза; постановка задач декомпозиции схем и решение задачи кратчайшего покрытия схем свободными модулями методом сокращенного обхода дерева поиска в случаях линейно упорядоченных и специальных систем модулей;

- приложения разработанной теории к логическому моделированию и проектированию БИС на различных уровнях абстракции (транзисторном, вентильном и конечно-автоматном) путем представления их переключательными схемами и описания последних каноническими системами уравнений, а также к компоновке схем в корпуса микросхем ряда промышленных серий.

ПУБЛИКАЦИИ Ш) ТЕМЕ ДИССЕРТАЦИИ Целиком диссертация опубликована в монографии /21/ и частями - в трех других монографиях /2,13,15/ и в ряде статей и докладов.

1. Агибалов Г. Е , Еузанов Е А., Липе кий К Е , Румянцев В. Ф. Математическая модель схем из элементов с управляемой проводимостью // Автоматика и телемеханика. - 1982. - N9. - С. 89-98.

2. Агибалов Г. П , Еуеанов В. А. , Липский Е Б.,—Румянцев Б. Ф. Логическое проектирование переключательных автоматов. - Томск: Изд-во Том. ун-та, 1983.- 154 с,

3. Агибалов Г. П. Функциональные системы на полурешетках // Алгоритмы решения задач дискретной . математики. Вып. 2. - Томск: Изд-во Том. ун-та, 1937,- С. 3-39.

4. Агибалов Г. П. Квазймонотоняые функции и их минимизация 11 Кибернетика - 1989. - N2. - С. 111-113.

5. Агибалов Г. П. К кодированию полурешеток и автоматов на полурешетках //Дискретная математика. - 1991,- Том 3, вып. 2.-С. 74-87.

6. Агибалов Г. й Математические . и программные средства автоматизированного проектирования цифровых автоматов // I Международная научно-практическая конференция САПР СВТ'89. Доклады. Секция 1. Разработка и внедрение САПР СНГ. Ленинград, 17-21 апреля 1989 г.- М. : АН СССР, 1989. - С. 116-124.

7. Агибалов Г.II О гомоморфизме и квазимонотонности конечных

автоматов на полурешетках // Проблемы теоретической кибернетики. Тезисы VIIí Всесоюзной конференции (ишь 1988 г.). Часть 1. - Горький: АН СССР, 1988. - С. 8-9.

• 8. Агибалов Г. П. К кодированию полурешеток // Международная конференция по алгебре, посвященная памяти А. И. Мальцева. Тезисы докладов по теории моделей и алгебраических систем. - Новосибирск: ИМ СО АН СССР, 1989. - С. 3.

9. Агибалов Г. П. О полурешеточных расширениях алгебр конечно-значной логики // Международная конференция по алгебре, посвященная памяти А. И. Ширшова. Тезисы докладов по логике и универсальным алгебрам, прикладной алгебре. - Новосибирск ИМ СО АН СССР, 1991.- С. 3.

10. Агибалов Г. П. Об автоматах на полурешетках // XI Всесоюзное совещание по проблемам управления. Тезисы докладов. - М. : АН СССР, 1989,- С. 492-493.

11. Агибалов Г. П. К синтезу последовательности!« схем управления в САПР цифровых систем // ■ Сборник тезисов докладов Всесоюзной школы-семинара ЕС ЭВМ - 89.- Киев, 1989,- с. 14-17.

12. Агибалов Г. П., Комаров Е М., Липский В. Б. Синтез комбинационных схем, свободных от статических состязаний // Автоматика и вычислительная техника. - 1979,- N3.- С. 1-6.

13. Агибалов Г. IL , Евтушенко Н. В. Декомпозиция конечных автоматов. - Томск: Изд-ço Том. ун-та, 1985. - 128 с.

14. Агибатов Г. П., Беляев Е А. Метод сокращенного обхода дерева поиска и его применение в синтезе интегральных схем // Управляющие системы и машины.- 1977.- N6,- С. 99-103.

: 15. Агибалов Г. Е. Беляев НА. Технология решения комбинаторно-логических задач. - Томск: Изд-во Том. ун-та, 1981.- 125 с.

16. Агибалов Г. П., Орапов А. М. Покрытие логических схем модулями некоторых серийных систем // Кибернетшса. - 1986.- N2. -С. 34-38,- 43.

17. Агибалов Г. П. , Ораиов А. М. О покрытии схем модулями // Вопросы автоматизации проектирования интегральных схем. -

' Киев: АН УССР,. 1978. : С. 46-57.

18. Aglbalov G. P. Functional systems on semi lattices // R. G. Bukharaev, 0. B. Lupanov (Eds.). Fundamentals of Computation Theory. - Berlin; Sprinper-Verlag-, 1987.- pp. .5-9.

19. Aglbalov G.P. Finite automata on partially ordered seta // V. Utkln, U. Jaaksoo (Eds.). 11th IFAC Vorld Congress Pry-

prints. - Tallinn, 1990.- Vol. 6.- pp. 264-266; Толе// U. Jaaksoo, V. Utkin (Eds.). Automatic Control. llth IFAC Vorld Congress Proceedings. - Oxford, New York, Seoul, Tokyo: Pergaircn Press, 1991. - Vol. 3.

20. Agibalov ß.P. , Lipskl j V.B. Analyse und Synthese stabiler binarer Automaten mit Hilfe logischer Gleichungen // D. Bochmann, A. D. Zakrevski], C. Posthoff (Eds.). Boolische Gleichungen. - Berlin: VEB Verlag Technik, 1984.- z. 175-183.

21. Агибанов Г.П. Дискретные автоматы на полурешетках.- Томск: Изд-во Том. ун-та, 1993. - 227с.

Из результатов, полученных в соавторстве, в диссертацию вошли: представление состояния узла в электронной схеме как набора проводимостей и транзистора как переключательного элемента /1,2/, метод характеристических функций в анализе переключательных сетей /2/, метод сокращенного обхода дерева поиска для решения комбинаторно-логических задач /14,15/ и его параметры для покрытия схем свободными модулями /16,17/.