Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 50
Текст из файла (страница 50)
4.9 [С сч НР51 — содеринмое ого раврада регистра Р5, 1 1, ..., 4 Рис. 4.10 274 Гл,4. Теория формальных ероммотик и автоматов операций, а число входных каналов равно ~)опт ЯХД~], гле [ )— знак ближайшего целого числа. При снитеае управлщощего автомата, реалиауюшето заданный алгоритм, предварительно составляют временные диаграммы, детализирующие каидый пункт алгоритма. Временная диаграмма, соответствующая вычислению нулевого разряда частного иа операционном автомате (рис. 4.
8) по приведенному алгоритму деления, приведена нв рнс. 4.9. Временные диаграммы, соответствующие вычислениям последующих раарядов частного, отличаются от диаграмм, иаобрвиенных иа рнс. 4.9, только в первом блоке, в именно: лри вычислении ьго разряда частного вместо чепорехкратного выполнения микрооперации Д4 имеет место соответственно (4 — 1)-кратное выполнение микрооперации Д(4 — 1), т. е.
прн вычислении вервого разряда выполняется пятикратное возбуидение Д5 и т. д. Следовательно, чтобы испольаовать первый временной блок, надо перед вычислением соответствующего разряда частного производить его настройку. Настройка первого временного блока заклкггается в следующем: Дт рассматривают квк входной параметр етого алоиз и перед вычислением нулевого разряда у присваивают аначение 4, а после вычисления каидого разряда частного аначение у увеличивают иа 1.
Осущеситм настройку первого временного блока введением дополнительного четырехраарядного регистра Р5, в который перед началом выполнения операции деления записывается 1, а после вычисления каидого рааряда частного пронвводится сдвиг. регистра Р5 иа один разряд. Выход ьго заряда регистра Р5 подается на клапан ДЯ ю 3). я нахоидения числа вычисленных разрядов частного введем трехразрядиый счетчик (СчД), состояние 101 которого уколет на то, что вычислено пять разрядов частного и надо передавать управление в блок нормалиаапнн. 14.3. Алгоритмический этол проектирования Основываясь иа проведенном анализе, делесообраано иаменить мноиество микрооперакнй в именно: вместомикроопервюяй Д4, Д5, Дб, Ду ввести мг»- кроолерацни СоР5 (сдвиг регистра Р5) и 1вР5 (запись единицы в регистр Р5) и дополнительно ввести микрооперацню +1 СчЦ (прибавление единицы в счетчик циклов Счу() и Сч((в "0" (установление счетчика циклов в "нуль").
В результате рассмотренных преобразований временная диаграмма, приведенная ив рис. 4.9, преобразуется во временную диаграмму, изобраиенную иа рис. 4.10. 277 е (х с) ), с) Рис. 4.11 Рис. 4.12 276 Гл.4. Теория формальных грамматик и автоматов Временная диаграмма еще не дает автоматного отображения.
Действительно, одному значению входного вектора, определяющего выполняемую операцию, соответствуют несколько значений выходного вектора (микрокоманд), т. е. временная диаграмма задает неоднозначное преобразование входного вектора в выходной. Следовательно, это преобразование не является автоматным отображением. Для получения автоматного отображения необходимо ввести в синтезируемый автомат память.
При этом заведомо достаточен объем памяти, равный числу всех микрокоманд. Совокупность входного вектора и состояния памяти однозначно определяет мнкрокоманду. В соответствии с временной диаграммой построим граф переходов автомата. Внутреннее состояние автомата взаимно однозначно сопоставляется столбцу во временной диаграмме. Граф переходов автомата, ревлиэуюший временную диаграмму (рис. 4.10), иэобр анен иа рис. 4.11. Микракоманды на этом рисунке обозначены латинскими буквами и имеют следующий вид: о =41вР5, СчЦв "О"); Ъ = (Сару', СаГИ, ПК1, ОКР, 1УР1, ирй, +1 ~, +1Сч1О; 5 4.3.
Алгоритмический этап проектирования с=(Вхр1); йю (Сйру, Сбрт, ПК1, ОК5, ЦР5); е = 1+12,); 1 = (Ьх)уру); д = 4СВРЗ, 11СОР5, Сбр»; л=(5'аоаер1); ью 4сарз, лсбру, сйр4, Р4 Р1), = (сарб). Считаем, что если иа вход автомата управления поступила еюоиша (х = 1), то автомат выполняет увравление делением. Логические переменные (признаки), алределяюшие хад управления, обозна- чим квк: о; — содериимое ого разряда регистра Р5; )У вЂ” условное состояние СчуУ, „у )' 1, если состояние счетчика есть 101, 1 0 в противном случае; Ре — перенос в нулевой рааряд кри суммировании чисел. Рассмотрим большую систему промышленной автоматнви — систему сии- гания твердого топлива в плотном слое.
Система содериит четыре лолугвзавые топки, установки подачи топлива, воздуха и установку удаления шлака. Схема полугазовай топки иэабраиена ив рис. 4.12, где: 1 — конвейер; 5 — ллуиок; л 8 — входной бункер; 4 — топливо; 5 — дитатель; б — забрасыватель; 7— лолугаз; 8 — подача воздуха; 9 — рабочая замера; 10 — шлак; 11 — слой све- (1, 1) 1. О) ) . 0) (о, 0) (О.
1) , 1) Рис. 4.14 Таблица 4.3 д(эм — (Я„дь) = О. дд 280 Гл.4. Теарив формальных грамматик и автоматов Из определения эквивалентных состояний следует, что если каждый класс эквивалентных состояний заменить одним состоянием, склеивая соответствующие вершины, то полученный граф переходов будет задавать то же отображение Х -+ У, что и первоначальный. Метод обсп)рактпно(1 минимизации овп)омон)о, основанный на склеивании эквивалентных состояний, был предложен Хафменом и состоит в последовательном выделении классов эквивалентных состояний с помощью таблиц выходов и переходов. Рассмотрим метод Хафмена на примере. Пример 4.1.
Пусть в результахе кроведения алгоритмического этака синхеаа был лолучен граф переходов, нзобраненный на рис. 4.14, а. Строим п»облику анхо»)оа, кредставляюшую собой двумерную хаблиду (табл. 4.3), кендой строке которой вааимна одноаиачио соответствует значение входного вектора Х, столбцу — внутреннее сосхояние автомата и на пересечении Ьй строки с у'-м схолбцом находится аиачеиие выхолного вектора У, который вырабатывается на выходе, когда авхомах находится в У-м внутреннем состоянии и из входе подан (-й вектор.
Если двум внутренним састояниам авхомата соответствуют различные аначения столбцов в таблице выходов, то сосхояння ие эквивалентны, тав как в этих сосхояииях отобранения Х -+ У различные. Предварительно разобьем все мнонесхво сосхаяний на классы условно экеизалекп»пмх састолпиб, а именно в один и хот не класс иокадзця те состояния, которым соответствуюх одинаковые значения схолбцов в таблице выхолов: К, = (Я», Яэ, Яв), Кэ = = (Яв, Я» Яв, Ят). Если таблицу выходов рассматривать как матрицу инцидент- ности некоторой модели, то внутренние состояния попадают в один и тот же класс, если в соответствующей ей частотной матрице отношений собственные и взаимные частоты внутренних 34.4. Абстрактное проектирование автоматов 281 состояний равны друг другу, т.
е. дб~, У- — 2У.ь+ 1ьь Для того чтобы внутренние состояния автомата были эквивалентными, одного и того же соответствия Х -) У только в этих состояниях не достаточно, нужно, чтобы и при любом другом возможном переходе из этих состояний отображение Х -ь У было одним и тем же. Для проверки этого условия схроим таблицу переходов (хабл. 4.4).
Кендой схроке, столбцу в этой хаблице соответствуют хе не значения, чха в хаблице выходов, и иа пересечении Ьй строки с,)-м столбцам находится класс условно эквивалентных состояний, в который дереходит автомат из сосхояиия Я» лод воадействием Хп Таблица 4.4 Если класс условно эквивалентных состояний, выделенный иа дредыдушем шаге, ие является классом эквивалентных сосхояиий, то состояниям этого класса соответствуют рааличные значения схолбцов; это оаначает, чхо лри дальнейших кереходах отабранения Х -+ У различны для данных состояний. Каидый класс К» разбивается на новые классы условно эквивалентных состояний, причем в один и тат не класс входят все состояния класса К» с одинаковыми значениями схолбцов: К» = (б», Яэ, Яв), Кэ = (Яв, Яв), Кэо = (Я», Ят).
Составим по таблице переходов частотную матрицу отношений, определив при эхом умножение как К( х К( = 1, К( х К, = О (ь ф у). Тогда внутренние состояния попадают в один и тот же класс при разбиении классов, полученных на предыдущем шаге, если собственные и взаимные частоты этих состояний равны друг другу, т. е. После лолучения классов К», Кэ, Кэа опять охраны хаблицу переходов и х.
д. до хех вор, кока каилый класс условие эквивалентных состояний, выделенкь»й иа лредыдушем шаге, ие станет иеивменным. Посхроим таблицу переходов (хзбл. 4.5), учитывая раабнение класса Кэ. Таблица 4.5 Анализируя эту таблицу, делаем вывод, чхо все сосхояния келлога из выделенных влассов "вед)т себя друнио": переходят кол воздействием Х в один и 282 Гл. 4. Теория уэормальных грамматик и аатоматоз тот ие класс, что обуслзввивзет получение из выходе олного и того ие зизчения У для всех состояний клзссз прн одном переходе. Следовательно, все состояния олного классе ведут себя кзк одно состояние, которым его и заменяют.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
