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

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

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

Лкпский Валерий Борисович

РАЗРАБОТКА И РЕАЛИЗАЦИЯ АЛГОРИТМОВ ЛОГИЧЕСКОГО ПР02КТИР0ВАККЯ шттш АВТОМАТОВ, УСТОЙЧИВЫХ К СОСТЯЗАНИЯМ

Специальность: СБ. 13.01 - управление в технических системах

Автореферат

киссэртзшя на соискание ученей отвлеки какдндата технических наук

Томск - 1.994

УДК 519.714

. Работа выполнена в Сибирском ^изико-тыкическсы института при Токскоы государственно»! университете

Научный руководитель:

- доктор технических наук Агибалов Г.П.

Офпуалъныэ ошюкентк:

- доктор тегниадских наук, акацеаих РАЕН Тистоь В.П.

- кандидат геанкческих наук Воробьёв В.'.

Ведущая органийаиия: ВЦ СО РАН "

Зекнта состоится 50- дЪ 1994 г. в й- час. на заседают', специализированного совете Д 063.52.03. Тоыокого государстзекного университета по адресу: 534050. Томок, Ленина 36, тел. совета 23-30-96

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

Автореферат разослал - Щ-&Л 1994 г.

Ученый сакретарь Опециагаз'.фоьеннсгс совета, ; -'

кандидат физ.-мат. наук, доцент у, • ' / Тривожнко Б.Е.

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

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

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

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

Методы исследования. 3 работе использовались методы теории автоматов, теории булевых Ф/шсиий, дискретной математики.

Научная новизна диссертационной р&5оты состоит в следу мнем:

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

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

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

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

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

Практической значение, работы. ?а-зраСстэлньй алгоритмы запрограммированы на кзьке ЛШС-М.

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

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

Екоциекке р о з у л г т э т о в. Результаты работы внедрены в Киевский институт автоматики. Омский ГОШ приборостроение, Омское предириягко ч/я В-2С65, Тснский политехнический институт, Иркутский гоеункверситэт, Томское ОКБ ГА, НИИ АЭМ при Томском институте эЕтоматизлриванных систем управления л радиоэлектроники, в ОКЙ при НоЕс^.йбирском заводе ПОЛУПРОВОДНИКОВЫХ ПрИбСрОЕ.

Результаты работы использовались ь лабораторных работах ко САПР студентами Ргдио^.зического факультета ТГУ, а тагае воыли о отчёты лаборатории Синтеза дискретных автоматов по различным НйР.

Апробация работы. Результаты диссертационной работы ' докладывались на Всесоюзной конференции "Автоматизированное техническое проектирование электронной аппаратуры", Каунас, 1ЭТ9 г.; на региональной конференции "Математичоскче методы в задачах управления", Пенза, 1931 г.; на V Всесоюзном совещании по технической диагностике. Суздаль, 1682 г.; на VI Всесоюзном совещании по технической диагностике, Ростса-на-Дону, 1Э8? г.; на научно-практической конференции "Региональная межвузовская целевая комплексная научно-техническая программа 1,Минвуза РСФСР "Автоматизация и её роль в реализации областной программы "Уокоренш-90",'Томск, 1988 г.

По результатам диссертационной работы имеется 12 публикаций.

Структура и объем работы. Диссертационная работа содержит 103 страницы и состоит из четырёх глав, введения, заключения, списка'цитированной литературы из 76 названий и приложения.

ОБЗОР ЛИТЕРАТУРЫ Все сутествующго методы обнаружения состязаний можно раз- . бить нг два. класса: методы, базирующиеся на имитационном моделировании цифрового устройства для ис ледуемого перехода, и аналитические методы выявления переходов в устройстве, при которых возникают состязания.

Наиболее эффективные с точки арония алгоритмизации методы моделирования обладают малой точностью из-за отсутствия ограничительных предположений о . задержках элементов /Зйхельбергер, Фантаззи/. Мэделировяние, учитываюдоо задерх-си элементов схемы /Б.И.Левин/, т,хзбует значительно больших объзмов вычислений и точного знания величин таких задержек, что тают ограничивает область его практического использования.

Распространенный подход к устранению состязаний представляет собой добавлеьиз ограничений в процедуры проектирования, обоспечивагяеа устойчивость г. отдельны!,; разновидностям состлза- \ !шй. Например, обеспач&нке ортогональности интервалов пар перз-ходое при кодировании ьиу-гр&чниз постоянна аьтоиата позволяет ¡юлучать схемы, устойчиво состязаниям переменных пьмяти.

З'-^'Ктпыгьгй сгоооб устранения состязаний - "еннхротза-

иия". Однако синхронные схемы работают медленнее.

Несмотря на то, что по проблема состязаний написано большое количество работ, остаётся актуальна создание структурных и функциональных моделей цифровых устройств, отображающих явленна состязаний, с целью постановки и решения в рамхах этих моделей :<здач проектирования цифровьс устройств, устойчивых к состязания«, В настоящей работе эта проблема решается в р-тсах теории автоматов на полу решётках, разработанной Г.П.Агибаловш для продсгаялеякя динамического поведения цифровых устройств.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ 6 первой г леве формулируется и кчсается задача синтеза комбинационных схем, устойчив»« к состязаниям.

Условимся векторы с компонентами, являющаяся символами некоторых алфавитов, называть наборами, а векторы, с компонента!». являющийся мнсззестваии таких символов - интервалами. Последние будем употреблять для обозначения множеств первых, считая, что интервал и = . . .un обозначает (представляет) множество наборов а = а, ...un, в которых а(« для каждого 1-1, ...,п. Тем самьы можно говорить о принадлежности набора интервалу , о включении интервала з интервал и о всех творетико-множественных ттскомг^нентных операциях над интервалами.

Гримам следующий обозначения для непустых годмножёств множества <0,1>: 0 « Í0>, 1 - tí), - » £0,1?. Тогда наборы в алфавите С -ío, !,-> представляет интервалы в алфавите Í0,1) и Наоборот. •

На множестве интервалов ü ввзкбм операцию сяоавния >, приняв интервал с g '/ за сумму интервалов а,Ь & О, если a s с, Ъ с. с и caá для любого теторвгла flej, такого, что a s d, Ь ь d. Множество интервалов U называется колурелалеой интервалов, если для любой пары интервалов а.Ь U сумма а ♦ Ъ е и, т.а. если оно замкнузо огносктэлыю операции сложения.

Определение. Отображение /: X где X и Y - полурешётки интервалов, называется Л1тервплыюЯ функцией.

Интервальные фунхцил вида /: С" —(Р, С - <0,1,-}, на^чва-ьтся п-масхндаи к я-компоначтными трсичиоыи фуккцк^ми.

Д::я интервальных функций /: X -» У и ц: X -* Í будам говорить, что g реализует / или / реализуется функцией g, если

В « т.е. если в(и) л /(и) для любого интервала й е X.

Интервальная футсция /: X -* У называется мснотонной, если для любых «,о с I из и = V слэдубт /(и) •= /(и).

Внтервальная функция / называется квазимонотончоЯ, если она реализуется некоторой монотошюй функцией. Очевидно, интерзальная фут-алм монотонна или КЕазжонототга тогда и только тогда. когда каждая её компонента соответственно монотонна или квззимонотонна. Яалез будут рассматриваться только квазныоно-тонные функции, поскольку функции реальных цифровых устройств монотонны.

Обозначим через я (У) шохостео наборов, которш образуют ■ все интервалы тюлурапйткн 0.

Тоорема(тесг квазимонотонностя). Пусть /: X —* У есть некоторая 1-1КШОНентная интервальная 'функция и 1г - /г/!(У)|. Тогда Функция / кэазкмонотонна, если и только осли для лзбых (но обязательно различных) интервалов и,,... е X таких, что и, п...п и^ « и * о имеет-место

/(«,) Л...П /(1^) .« в .

Следствие. Троичная функция Сл—. С™ гсвазкмонотокна тогда и только тогда, когда для лвСчас двух интервалов ,и? <= сп-из и, п * о следует /(и,) п /(и2) *

Утверждение 1.1. Суперпозиция ::вазимоиЬтою(ых функция ость функция квязимокотонная.

Последовательности конечной длины, составленные из сияво-лоб некохочого алфавита, 'называются словами в этом ■ алфавите. Слова дли:т 2 называются переходами.

Рассмотрим интервальнум функций /(а) и переход (с..р) в X.

Определение. Функция / содержит статические состязания при переходе (а.р), если /(а) - /(р) /(а + р).

Определение. Функция / содержит динамические состязания при переходе (а,р),'если /(а) * /(р) л существует интервал 7 г а к р такой, что /(7) - /(р) * /(7 4 р).

Рассмотрим однокомгонечтнь» трокчныэ^ квазимонотонныи функции /(х,.....I) и п,г * 1.

Пусть ^ = = ^ f^■a'> = 6 . 0,1,-, и = и

Будем говорить, что функция / ра-злояима по 'функции ?г, если она реализуется функцией из <0,1.....тп> йли существуют ква-

- в -

зимонотонныа функции /, (I,,... ,хп)...../г (х;.... ,хв) такие, что

1) /(х,.....хп) реализуется суперпозиций! ,...,/г);

2) для каждой функции , ; - 1,...,г, ньлдется ■ функция <р « <0,,... ,хь>, рэалязутая , или с

Е этом случае функции /,...../г называется компонентами

разложения / относительно А или по Н.

Множастзо фуасций В называется декомпозиционно полнда, или образует декомпозиционно полную систему, если для либо» одно-ксыпонантнсй троичной кзазимонстсикой функции / существует функция /I, гркнахлэтааая Я клк являвшаяся суперпозицией вида'

/0(/,...../ш) ©нкций из В и <0.1), такая, что / разложима по

Л.

Теорема о декомпозиционной полноте. Множество Н трои"чых квазимонотонных функций образует * декомпозиционно полнуя систему, если и только если Н содержит функцию ^(г.,...,*г) со свойством

1) суоаструм наборы

а.а....аг, р - ^ .. .Рр « 7 - 7,."7Г « 6 - <0.1>

такие, что дли любого J * 1.....г вдрио

а1 - - или р. - - :ш ^ -и функцию Л, (г,.....со свойством

2) ¡¡ушессвулт наборы а «• а .. .аг с Н^ и р » р,.. -Рг ь

такие, что для льбого J 1,...,г ...

а. » 1 и (5. - 0 или а. п 3. к е.

Комбинационные охамн строятся из комбинационных элементов. КомбинагаонныЯ элемент - это («г, 1) - полгажс и одногсомтгокентная квьзимонотоннач троичная фуккц/я, аргументы ¿»горой поставлены вс ьзгимчо однозначное ссю'/реотЕиа входные полюсам элемента.

Каждому полюсу I стеку принисквазтся троичная функция следующем образоч:

1) Если г лйляэтся ьходным полюсом схемы, которому приписана входная переменная х, '¿о X', "

&сл:< I - выходной полюс элемента с схемы, Вдодньм полюсам

которого ппнтс&ни фунмыи .....то = ...... где

и - Яунюшя эйемз"та е.

Фунгси, пршгсанные т-аадм оОразом вь/ояп-м полтош схема.

называются «функциями схемы.

Из утверждения 1.1 следует, что функции комбинационных схем являются квазимонотоннжи.

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

Определение. Множество комбинационных элементов К называется декомпозиционно полнш, бели функции элементов в К образуют декомпозиционно полную систему.

Определение. Комбинационная схема называется устойчивой на некотором полюсе I к статическим состязаниям при заданном переходе, если функция, Ернпксаннгя полюсу {, не содержит статических состязаний при этом переходе.

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

Ставится следующая задача синтеза. Заданы п-местные одно-компонентные кваБИмонотошые троичные функции .....множества переходов Ь, в С" и декомпозиционно полное множество элементов К. Каждая функция - 1не содержит статических состязаний.'-при переходах из-' множества Ък. Требуется из элементов в К построить- консигнационную схему Э, которая на своих выходных полюсах реализует функции .....Р,л и является устойчивой к статический состязаниям при всех переходах из множеств I,____соответственно.

Онизим лроиз£ольныЯ шаг метода синтеза. Пусть .5' ость та часть схемы которая построена к моменту выполнения данного шага. (К начальному шаг/ Я' состоит из еходных и еыходных полисов г.гоны й и из полисов, на которых задаются константы 0 и 1). Определим з 3' маож«стьо полюсов Спо слядукдам индуктивным правилам:

1) все входные полюсы схемы £ и полюсы, на которых заданы кокет-гиты, принадлежат множеству 0:

2) воли все входы элемента в 3' содержатся в С. то и выход этого элемента принадлежит а-,

3) других полюсов б <} н&1.

Рассмотрим в 5' некоторый полюс { « 0. (На начальном шаге это есть один из выгодных полисов схемы Б). Пусть на полюсе £ схема £ должна реализовать функцию / и пусть Ф есть множество фртжций от X, приписанных полюсам множества С/. Возможны следующие случаи.

1. Функция / реализуется некоторой функцией <р « <5. В этом случае полюсы £ и на котором 5 реализует <р, отоадеатвлягася.

2. Функция / но реализуется юс одной иг фушсций Ф. В этом случае, выбирается некоторый элемент в в К, по функции Ыу^,...,уг) которого раздолмма функция / или функция у. и строятся компоненты .',/ соответствующего разложения. Б силу лолчоты базиса требуемый элемент непременно найдется. В схему 5 вчпЕчается элемент е, выход которого отождествляется с полюсом I непосредственно или через инвертор. Каждая функция

'/,, для 3 - 1.....г рассматривается в дальнейшем как функция,

которую охамз 5 должна реализовать на „'-м входе элшэнта в. .

Синтез заканчивается, когда множество а содержит все полосы в г.

Фзкг, что условие для окончания процесса синтеза обязательно заполнигея чьрез конечное число шагов (факт сходимости метода), следует кз того, что компоненты разложения функции /, рассматриваемой на произвольном нага, либо доопредеяимы до функций (из уже реализованных схемой; либо заданы собственней частью осласги задания И^ функции /. Кроме того, построенная схема Я устойчива ча еыуодй < к статическим состязаниям при любом переходе (а,р), для которого а + р е Ир . Таким образом

схема построенная предлагаемым методом синтеза, реализует на своих выходных полках 1____заданные Функции .....?к и устойчива к стетичега:«! состязания*; ка них при всех ьзрзяедах из заданных множеств I,.....соответственно.

Рассмотрим комбинационную сему 5 с входными переменными

.....хп и переход (а,}1) в С". Пусть футтом элемента е гхемы

£ есть /1(2,.....гг)\ .....£г суть ^оласы в Б явллмиося входами элыяаьта с, отЕечаьспми перекг.ннш г ■.. ооствьтстген-

но,'и jf - функция, приписанная полюсу { схамы 3. Тогда набор значений (f?} (a).../fr(a)) на входах элемента s будем обозначать /|(а). Наборы /^(а) принадлежат множеству Сг всех наборов значений переменных z1....,zr.

Определение. Схема S устойчива к динамическим состязаниям на полюсе { при переходе (а,0), если Í есть вход схемы S, /fía) - - /fía) - /?(.в> или ч случае, когда i есть

выход некоторого элемента в, /f(a),jf(P) -а (О t) и /f(a) " ff(P), функция ft элемента е не содержит динамичэских состязаний при переюде (/^(а) в Сг и схема S устойчива

к статическим и динамическим состязаниям на входах элемента е при переходе (a.f)).

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

Во второй главе предложен интервальный автомат в качестве функциональной модели цифрового устройства с память», отображающий явление функциональных состязаний в последнем. Под интервальные автоматом понимается конечный автомат А -(Х.ОХф.ф), гдэ входной алфавит А", множество внутренних cocí -яний Q и выходной ал?'лвиг Y - полурешРткч интервалов, з функции г.ерэхг>дов ф л выходов <р являзтся интервальными функция:«:. Интервальный автомат с квазимоночстоннчки функциями переходов- и выходов называется квазимснотокным. Будем рассматривать только квазкыонотонныа автоматы. Золи алфавиты Х,<3,У инторвапькою автомата являгтсл векторами из С - íO, 1,->, то ав"">мат называется троичньм; КомпоНк.иы функций троичного автомата называются соответственно структурами функциями переходов и выходов. Пары х - а 1 х Q называются полными состояния;« эвт'''ага .1. Полное состояние устойчиво, если = q.

Определенно. Автомат А - (Х.О.У.ф.ф) реализуется авюмзтси В -- (Т,Г,У,ф' ,<$'), если суиэстьует гзочсрфчзм полурезйток р: Q— Г, татоР, что для любых. щ X >. Q м>;егт место cooího-

ЕЙНИЯ

ф\\гр^:) £ р Сф(лг^);

Ф'(.гр(q)) с ifíTqi & этом случае с назьтаотся отоОратенк&м реализации етсната А

автоматом В.

Отношение реализации автоматов тралзитквно.

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

Определение. Пусть 5 ее ъ комбинационная схема и 3 некоторое мнохсстео её полисов, |«Т| > 0. Отождествим каждый полюс /с <Гс некоторым входндак полюсами схемы 5 так. что с любш входным полюсом отождествляется не более одного полюса из 3. Полученную схему" Я назовём лоследовательностной схемой. Полюсы в J называются внутренними полюсами схемы N. Схема 5 называется логически преобразователем схема N ют об комбинационной часты. ■

Рассмотрим последовательностную схему N с логическим преобразователем Б, имеющую п входов, я выходов и I внутренних по-юсов. Сопоставим последоватьльностной схеме И с логическим преобразователем 5 троичный автомат

А - (С ,<?", (/*.. ./• }, .. ) где С - <0,1,-> и - троичная функция, приписанная полюсу J логического преобразователя 8 'схемы N. Будем называть его автоматом схемы N. На последовательности)** схемы распространяются все понятия, определённые для соответствующих автоматов: функции переходов и выходов, внутренние состояния, квазхмоноток-ность и др. Можно говорить о реализации одной схемы другей, автомата схемой, схемы автоматом.

Постановка- задачи синтеза: задан квазимонотонный. интервальный приведённый автомат А - (Х,{?,У,ф,<р) и декомпозиционни полная система элементов А. Требуется из элементов б К построить последоватальяосгнуы схему, автомат которой реализует А.

, Предлагаемый метод синтеза состоит из следующих этапов.

1. Кодирование внутренних состояний автомата Л - (1,0,У,ф,ф) понимаемое как отыскание отображения-

р: в -» Р £ С1 для I > 1 такого, чте существует тр ;1чный автомат В - (Х.Г.У.ц-',Ф') с кваз'.агонотокньми структурная функциями, реализующий А при отображении реализации р.

2. Синтез комбинационной схемы 5 в базисе К, реализующей структурные фунтик аьтонать В.

После выполнения этих этапов искомая схема К получается в

' -It-

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

Суаествование и способ построения троичного автомата, реализующего заданный, устанавливается следупоей теоремой.

Теорема. Интервальный автомат А - (X,Q,Y,<p,fp) реализуется троичнь« автоматов, если и только если для лчбых г1д1,...,хкдк'« Х х Q, таких, что

■i, иои ф(*т<7,) П.. .n - в

найдутся i,) « <1,...,ft), I * J, для которых Ф(х4qt) niyííj? ) -о.

Построим троимый автомат Я - (Т,Р,У,ф',ф*), реализующий А.

Отображение реализации р: Q-* Р, Р «С1, I > 1, выбирает-, ся таким, чтобы для любых двух векторов, лг, q, ,s,g2 «1*0 таких, что хл п гг" в, и выполняется хотя бы одно из равенств

ФС*,^) о ф(хг<^) - с» или фСх,«?,) п ф\хгяг) - в имело Mocío

Р<<?,) п p(q2) - 0. •

Структурные фунхции <f» (ф'.-.ф^), ф'- (<?,'...ф^) автомата В строятся tío следу кип правилам, примзнчемнм к каждому вектс / щ « X х 0: а

а) значение ф^ (aqp(q)) равно i-й компоненте вектора

р(фич)), i 1.....1; .

б) <p¿(xp(q)) - <pt(xq), i - 1.....и.

Логический преобразователь S синтезируемо^ послздователь-ностной схемы И строится методами главк 1. Нетрудно видеть, что автомат схема И ¡ зализует автомат В, а стдевггьльне и А.

В третьей г л a j е рассмотрены методы построения 1тугтерва.'!ьных автоматов, реализующих заданное -йункционировзнка для различных типоз устройств. Функционирование цифрового устройства задайся последсвателькостной функцией - четвёркой сбъ-ектоз Р (I.Q.y.D, где X,Q,7 - конечные алфавиты: соответственно входной, внутренний и выходной, a f s (Ь Q) ■■■ (X * Q) * Y - множество переходов. Произвольный лерьх^д из Г имеет вид t - (г, с, где х1 ,r, ^ X, q. ,qz s. <J, j/ •= У.

Реализация перехода.! - Цq. .x¿qr,-j) в устройстве з.г,'лзчаетгл р слъдугйок: всякий рг.з когда на входах уотройстга, нахолчкего-

-\г -

ся во внутреннем состоянии из множества q1, входное состояние из множества х, заменяется входным состоянием из множества хг, устройство переходит бо внутреннее состояние из множества q2, а его выходное с чояние не выходит за пределы множества у.

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

Синхронное изменение входного состояния х на х, моделируется замещением значения непосредственно значением хг, а ого асинхронное изменение - заыеш.энкем значением хг через проыэ-луточное значение х^ + хг. Синхронное изменение внутреннего состояния q(, вызванное входным состоянием хг, переводит автомат с функцией переходов ф во внутреннее состояние > > а его

асинхронное изменение - в состояние фБ(1-г<3,), где - итерра-циоиная нроцодур-i, определенная следующим образом:

пусть x?qs е X х Q; строятся последовательности u>t,.... и ,...,ut интервалов такие, что

»'■», - Ч, . V _,) 'Dt. t = 2,... ,р,

v^ i^» ф^,«,^) п ut_1. i -p и t определяется из условий: « ш, tt » i't_,; голого no определению ф!13 (x.,q1) = i>t.

'га»-, как ti/^ .. и ti^a.... то эти условия обязательно выполнятся чзраз конечное одело шагов.

Рассмотрим три типа устойсгв и, соответствен!- три способа реализации перелодоь: синхронный, асинхронный в статике и асинхронный ь динамике. В синхронных устройствах все состояния из-маняигся синхронно. В ¿синхронных в схати?» - внутренние сссто-и-мя изменятся аскнуроюю. а входные - синхронно. Б асинхронных в динамика устойетвах всо состояния изменяются асинхронно.

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

Если Р * (Х,0,7,Т) - песледователъностная функция, то «функции переходов и выходов автомата А - (Х.О.У.ф.ф), реализующего переходы из Т синхронньи способом, строятся следуапим образом: для каждого перехода (а^д, ,х^г,у) Т полагаем

♦(.хг9| > =* > " У-

Легко убедиться, что построенная таким образсм автомат кврзймоноток9н, если для любых двух переходов

Ц<7, .^.ЬЫ^.х^.у') « ? из 3.29,0 а£<?1*'* » следует я^у п - о

Для асинхронного в статике способа функционирования строится автомат Л - полагая

ф(хг(<?, и ч2)) - дг и ф(х2<<* и д2)) - у для каждого перехода ,хгЦг.у) «Г.

Построенный таким образом автомат квазимонотокен и реализует многество переходов Т асинхронным в статике способом, если для любых двух переходов (х}д1,хгяг,у).(х'д^,х.^,У) « Г из' хг{% и л и ЯР * 0 следует п «».

Для асинхронного в динамике способа функционирования каждому переходу 4 - (х,,х2д2,у) последовательностноП функции Р (Х.О.У.Г) сопоставим мношетво <4> с 9 называемое интервалом перехода $ и понимаемое как множество промежуточных состояний, появляющихся при реализации порохеда I. Очевидно д1 ,д2 в

Множество Г назовём нормалыгьм, если для л^ой пары переходов г - ц(], .¿?дг.у).г - « г из условия Гг П " 0' (?г п " а ТаКЖЭ 153 УСЛОВИЙ (с, ♦ х2) п (х; 1 хр - о, у п у' - 0 следует

<1> п <Г> - в; Построим автомат /4 - (*,<},У,<)\<р), определив функции ф и <р следующим образом: *

ФЧЦ + х^д,? - ф(<х, + х,)<г>) <Г> ф(г2<*>) - яг- + з:г"><1>> - У> для любого 4 - Цд, ,х„дг.у) « Т.

Утверздьнко. Построенный предлагаемом способом автомат А кьазимсноюнныЯ к реализует яадгкхое юютаство пароходов Г ¿¿ч-

нхронным в динамика спслобом, если У является нормальным.

Автомат А реализуем троичным автомате«!, если для любых

/ переходов г.....V' е г из и1 п...пип = в, где и1 в {д*,^1: V,

.1 - 1,...,а, н~йдутся 1,3 а {1.....ТО такие, что и1 п г • в.

3 результате предлагаемые б главах 1 3 алгоритмы позволяют проектировать П0слэд0в?"елы10стные схемы, реализующие заданное функционирование (мноеэстьо переходов) и устойчивые к состязаниям, то есть сохранякжие работоспособность при любых разброса.* задержек распространения сигналов в элементах и соединениях схемы. Следует отметить, что устойчивость синтезируемых схем к состязаниям обеспечивается на этапе построения интервальных автоматов, реализующих задаваемые переходы, а но на этапе кодирования внутренних состояний. Задача кодирования ;эр-мулируется и решается одинаково для всех способов функционирования и требует лишь обеспечения квазиыонотонности структурных Яункций переходов и выходов ..слушаемого троичного автомата, что является несомненным достоинством' предлагаемого подхода к проектированию устойчивых к состязаниям цифровых устройств.

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

В заключении перечислены результаты работы. Они сводятся к следующему.

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

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

- разработаны программы синтеза и имитационного моделирования цифровых устройств, предназначенных для включения в САПР цифровой аппаратуры

НА ЗАЩИТУ ЕКНССУГГСЯ: •

1. Формализация понятия устойчивости на полк* х комбинационной схемы к статическим и динамическим состязаниям ка задаваемых переходах.

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

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

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

5. Для казкого способа" реализации переходов получены следующий результаты:

- выведаны условия существования интервального автомата, реализующего заданные переходы соответствующим способе":

- предложен алгоритм построения такого автомата;

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

6. Программа логического синтеза комбинационных и последо-вательностных схем, рёглдаукаих заданные интервальные автоматы.

7. Программа имитационного моделирования схем с учётом задержек ев элементов.

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

Материалы диссертации опубликованы в следуг^их работах:

1. Агибалов \П., Бузанов В.А., Л:;пский п.В.. ' Р/мяшез В.Ф. Логическоо прозктированио переключательных автоматов // -"оме:;: Изд-бо Том. ун-та. -133Я. -154 о.

2. Атабаяов Г.П.. Бузанов Б.А., Липскчй В.В., Румянцев Б.Ф. Магематическая модель схем из элементов с управляемой П]х?-водлмостыз //Авмматжа и телемеханика.- -1532. ,-№5. а.89-98.

3. Атабалов Г.П., Бузанов- В.А., ЛипсккЙ В.Б., РумягабВ В.Структурнш а функциональные мода.™ в диагностика г;ора-г.то-чателнгьтс КИП // т< кн: Техническая диаткостю г. V Рсесркзнов совещание (тсзисы докладов): -Суздаль: -193Й. с.9-10.

4. Агибалов Р.П., Иволга В П., Комароа Ю.Ч., Кутупша

Е.С., Липский В.Б. Система чопсчесвого моделирования схем во времени // Обмен опытом в радиопромышленности. -1983. выл.4. -с.13-16. •

5. Агибал^в Т.П., Комаров D.M., Липскии Б.Б. Синтез комбинационных схем, свободных от статических состязание // Автоматика и вычислительная техника. -1979. -ta. -с.1-6.

"6. Агибапов Р.П., Комаров Ю.И., Лклский В.Б. Синтез посло-дователькостных схем, устойчивых к статическим состязаниям // В кн.: Математические методы в задачах управления. Тезисы докладов областного семинара: -Пенза. -1981. -с.29-30.

7. Беляев В.А., Евтушенко И.В.. Дубков D.U., Лввазииков A.A., Липский В.В.. Черкашин Ю.Д., Юфит Я.Г. Система компилятивного проектирования РЭА на БЭСМ-6 //в кн.: Автоматизация, математические методы и управление народом хозяйством. Сборник статей / Под ред. А.М.Корикоьа: «Томск: Изд-во Том. ун-та. -1S90. -с.53-60.

8. Комаров D.U., Липский В.В. Анализ переходных процессов в асинхронных логических схемах // В кн.: Вычислительная техника. Материалы всесоюзной конференции "Автоматизированное техническое проектирование электронной. аппаратуры": -Вильнюс. -1979.-с. WS-W.

9. Комков D.lf., Липский В.Б. Временное моделирование асинхронных логических схем // В кн.: Алгоритмы " решения задач дискретной математики, вып.1: -Томск: Изд-во Том., ун-та. -1979.-е J04-H2.

10. Липский В.Б. Синтез комбинационных схем без состязаний // В кн.: Алгоритмы решения задач дискретной математики, вы.,.1: -Томск. Изд-во Том. ун-та. -1979. -с.132-139.

•11. Липский В.В. Система логического синтеза интервальных азтоматов - СШП'А // В кн.: Алгоритмы решения задач дискретной математики, вып.2: -Тонек. Изд-во Том. ун-та. -1987. -с.65-72.

12. Agibalov G.P., LipskiJ V.B. АлаЗ.увэ und eynthese ata-Ы1сг binarer automater. ¡niv hilfe logischer gleic' 'ngen // Im buch: Boolischfc gleicriungen / Herausgegoben ven Bochman, Zafare-vsklj, Posthoff:'- Berlin: VEB Verlag Technik. -1Э84. -z.175-183.