Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 52
Текст из файла (страница 52)
Граф зацепления и его раскраска для автомата, изображенного на рнс. 4.17,а, приведены на рис. 4.18,а. В результате раскраски 288 Гл. 4. Теория формальных грамма»пик и автоматов графа зацепления имеем следующие подмножества состояний, каждое нз которых состоит из незацепленных между собой состояний: У1 = (эб! 522! эь)! У11 = 1э»! ~1)! Ь1П = Фи)! )1ч = 1э»)" Иэ пзждого подмножестзз У; (ь = 1, ..., 1Ч) зыбирзем по олиому элементу, иепрнмер, Яь, Я„, Я», Б; нз зыбрзнныт элемеитоз образуем подмнонестзо Ую = (ль, Я», Я», 5»). Долее, сполз из кззшого подмноз!естзз У; зыбнреем по одному из оставшихся элемеитоз и снопе образуем из иид подмнонесгзо.
Выборпу осуществляем до тет иор, попе пзждое нз подмнонестз У; не преобрззуется з пустое множества. Обрззозеииые з результате экой выборки подмноз!естзе н являются подмножестззмн, состояшиыи из ззпепленных состояний. В денном слу ьзе они имеют следующий зид: Уьз = (аь, 5~ ! а, Б!), Уьз = (азз оь) Узз = (о!) ° Каждое подмножество, состоящее из залепленных состояний, заменяем одним состоянием, вес которого является совокупностью мякролучей, соответствующих объединяемым вершинам (в частном случае микролуч может состоять из одной микрокоманды).
Такую замену будем называть стягиванием залепленных состояний. В результате стягивания зацепленных состояний графа переходов (рис. 4.17,а) получаем граф переходов Са (рис. 4.18,6). Стягивания залепленных состояний также нарушают детерминированность автомата. Детерминированность синтезируемого автомата н его эквивалентность сохраняем, введя в обратную связь элемент памяти, в котором будет фиксироваться краска, соответствующая микролучу, выполняемому в данный момент (рис. 4.18,в). Тогда совокупность кода вершины окончательного графа переходов, краска и показания счетчика микрокоманд в микролуче взаимно однозначно определяют выполняемую микрокоманду.
В результате такого преобразования граф переходов можно представить в виде частичного декартова произведения соответствующих графов (рис. 4.18, в), что упрощает процесс кодирования внутренних состояний и практически уменьшает аппаратурные затраты при синтезе схемы возбуждения обратных каналов автомата. Если контуры в графе переходов, соответствующем реализуемым микропрограммам, отсутствуют, то целесообразно разложить его только на два графа, исключив граф, показывающий смену красок. При этом проводят свертывание двухинцидентных подграфов в каждом графе переходов, соответствующем реализуемой операции, с последующим склеиванием совместимых состояний.
Если граф переходов является деревом, то в обратной связи автомата-оставляют только счетчик. При этом граф переходов реализуется счетчиком при условии запоминания или наличия значений логических переменных, характеризующих вычисления. Начальному внутреннему состоянию автомата сопоставляется начальный код на счетчике, например код О. Внутренние состояния, в которые автомат переходит из состояния Я;, имеющего код А, кодируются как А + 1. Смена кодов происходит прибавлением единицы 14.4. АБстрактное проектирование аетаматое 289 в счетчик при каждом переходе. Тогда при наличии разветвления некоторые внутренние состояния будут иметь одинаковые коды.
Детерминированность автомата при этом не нарушается благодаря хранению логических признаков, характеризующих проводимые вычисления. Показания счетчика и значения логических переменных однозначно определяют нужную микрокоманду. Данное утверждение справедливо, так как граф переходов является деревом, т. е. не содержит циклов. В конце выполнения операции происходит гашение счетчиков.
При представлении графа переходов, соответствующего автомату управления одной операцией, в виде частичного декартова произведения производят следующие преобразования: 1) склеивание псевдоэквивалентных состояний; 2) свертывание двухинцидентных подграфов, причем в результате изменения последовательности применения этих преобразований возникает несколько эквивалентных вариантов. Рассмотрим греф перепадал упрззления оперзпией деления (см. рис. 4.11). стягиззя дзудиндидеитные подгрефы, получзем грзф перепадал ь» (рис.,4 19, а).
Вершинем этого графа соатветстзупн следующие мяиролучи: Яз — а; 5„— Рис. 4.19 бсасосас; Яь — Бс; Яь — Бс; Яь — Бс; Бу — 1!я; Бь — еУд; Язз — оз. Следоззтельно, для зосстеиозлеиия зязнззлеитного фуиипионирозеиия необходим счетчик нз 8 состояний.
Вершины, соотзетстзуюшие состояниям Бу н Яь з графе переходил (рнс. 4.19, а), можно сплеить при наличии ззпомянзния призиепз рь, детермниироззиносгь ззтомзте при этом ие иерушзегся. Окаичетельно имеем граф перетодоз С, изобрененный нз рис. 4.19, 6. Состояния счетчипз, признак рь н иод вершины графа переходов (рис. 4.19,6) однозизчио определяют зыполняемую мипр опомзнду. Внутренние состояния нзэыззются псеедоэкеиеалеитиыми, если з них резлизуется одне и тз же мииропомзидз.
Для графа передодоз С» (см. рис. 4.11) имеем следуюшне множестзз псездоэязизелеитных состояний: М» = (Яь, Яь, а», аз, Б!1, озз! азь! а!1); Мь = (аь!,аь! аь! азз, азз! азь, азь). В результзге склеивания псездозпзиззлеитньпс состояний (рис. 4.20, а) изрушзется дегермипироззниость езтомзте. Дезермпнирозенность и эизизелеитиость фуиипнонироззиия ззтометз зосстенззлиззем введением счетчика при оргзииззпин пизлз переменной длины.
Не рис. 4.20,6 призедеиз программа !Ь Э. Л. Г»рте »» (х, о'> Ь' (Ь,+1Сч,710 И' (Н,+1Сч4'1 Х ро Рнс. 4.21 Рис. 4.20 290 Гл.4. Теория формальных грамматик и аетомотоа работы счетчикоа; а рассматрнэаемом аэтомате 1с = 7. Внешний цикл реалиауегся счетчиком длины цикла СчДЦ. Внутренний цикл реалпауется счетчиком числа циклоп СчЦ. Признак т, который аоссхаиаэлиаает детерминироэанность аэтомата, эычисляется э блоке, включающем эти счетчики (рис. 4.20,е).
В том ие блоке эычисляется и при- энак окончания одерацни В (как сигнал переполнения счетчика СчДЦ, причем начальное состояние этого счетчика рвано 2). После эосстаноэлення детерминироаанности аатомата проиааодим склеикание дэухинцидвгтных подграфоэ (рис. 4.21, а, б).
Лля эосстаноаления дехерминироаанности функцнонироэания аэтомата после стягиэания дэухинцидентных подграфоэ введем еще дэа счетчика, имеющих трн и даа состояния соотэетстэенно. 14.4. Абстрактное проектирование аатоматоа 291 При восстановлении цетерминировзнности звтомзта с помошью введения счетчиков возникает задача минимизации числа счетчиков, которая сводится к задаче раскраски графа эапгираиил Сэ .
Каждому счетчику взаимно однозначно сопоставляется вершина графа (х,: лве вершины графа С,т смежны, если поцграфы рабаты соответствующих счетчиков имеют хотя бы одну обшую вершину (попгрзф С является полгрвфом работы счетчика сг, если лля реализации в этом папгрзфе прзвильных переходов необходимо знать состояние счетчика гг). Лля рассматриэаемого случая счетчикам СчЦ, СчДЦ, Сч(Я„) и Сч(Яо) соотаегстэуют цодграфы, носители которьпс имеют соотэегстэенно следующий энд: (Я„ое), (Яэ, Яю ое, Я Яд оээ), (Я ) и (Яд).
Граф эатнрания С,т для рассмахриэаемого случая иаобраиеи иа рис. 4.21, а. Очевидно, пвз счетчика, соответствуюшие несмежным вершинам в графе ззтирзния, можно рассматривать кзк один физический счетчик, так кзк не найдется ни одного состояния, в котором лля прзвильного функционирования звтамзтз необходимо было бы знать состояние обоих счетчиков.
Таким образом, минимизация числа счетчиков свалится к раскраске вершин графов ззтирзния. 292 Гл.4. Теория формальных грамиатик и овтомотоа В ванном случае согласно минимальной раскраске вершви графа аатираиия (рис. 4.21,а) востаточио наличия леул сметчиков: смегчива СчДц и сметчика СчЦК, который вклкгсаетсл в моменты рабаты счетчиков СчЦ, Сч(д ) и Сч(бя) (рис. 4.21, е). Применение счетчиков в цепи обрвтной связи ввтомвтов управления позволяет использавзть стандартные узлы ЭВМ, выполненные в виде интегральных микросхем.
В результзте поиска оптимальной декомпозиции ввтомзтав получаем несколько эквнвзлентных вариантов, нз которых выбираем окончательный вариант, имеющий минимальное значение р(СМ): 1Ц где ]Ц вЂ” количество слов в мографе, кзждае из которых соответствует автоматному переходу и представляет собой ХЯ+Я У; 1 — число букв (терман), образующих слово ХЯ+Я У; под внешним знаком 2 находится выражение, являющееся средним знвчением производной дСм/дЯ, вычисленной нв парах букв, образуюшнх слово ХЯ+Я У. Этому взривнту соответствует более простая структурная реализация. 2 4Л.
Кодирование внутренних состояний Нв этапе кодирования внутренних состояний отобрзжение ХЯ+Я У, полученное нз этвпе абстрзктного проектирования, преобразуется в отабрзжение ХК+ -+ К У, где Я+, Я вЂ” идентификаторы внутренних состояний, рвссмвтриввемых соответственно в моменты времени 1 и $+ т; г+, К вЂ” коды этих состояний, элементами которых являются буквы используемого структурного алфавита; для случая булевой логики это О и 1. Кодировзнне внутренних состояний автомата можно осуществлять, исходя из требовзний уменьшения зппвратурных ззтрвт либо увеличения надежности функционираввния ввтамвтв, либо удовлетворения обоих требований одновременно.
Рассмотрим метод кодирования, удовлетворяющий первому требовзнню. Число способов кодирования Ж вершин графа переходов 0 = (У, сУ) увеличивается с ростом ]У] кзк (20обт 1иП 1)1 )ч' — „,, (4.9) (29обт1еП вЂ” Щ)! ([1обт ]У]])1' где [] — ближайшее целое число. Каждый способ кодирования определяет сваи аппзрзтурные затрзты цри реализации звтомвтз. б 4.6.
Кодирование енутреннив состояний 293 Наиболее интересным является метод кодирования с использованием яодстоновочных разбиений, предложенный Хвртмзнисом и Стирнсом. Это метод основан нз уменьшении функциональной эзвисимостн функций возбуждения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
