Antik (1082243), страница 6
Текст из файла (страница 6)
Эти же начала ибудут именами состояний (столбец 1) в автоматной таблице 1.Таблица 7.2.-11имяΛaabacabaacbabcabqabaqabcbabcq2I,I,I,I,I,I,I,aaSabaaSaaaaaabΛabSacbabSabcbΛΛSΛcΛacabcSacΛSΛΛΛΛqΛΛabqΛabaqΛabcqSSΛS3№123456788684кодx10a00b00c00a01b01c01q00q00b01q00Таблица 7.2.-2кодb10c10q10a00b00c00a01b01c01q001,1,1,1,aa00a00a00—a01a00—a00a00a00b—b10b10b00—b01b00—b01b10cc10—c10c01c01—c00c10—c10qq10q10—q10q00q10q00q10q00—Комментарии к автоматной таблице. Буква S означает переход в то же состояние в силу асинхронности языка.
Использование такого символа позволяет упростить процесс минимизациисостояний автомата – (эквивалентные состояния выглядят как явно эквивалентные). Чтобы не загромождать таблицу, выходноезначение обозначено только там, где должно индицироваться искомое событие. В столбце 3 строки-состояния перенумерованытак, что эквивалентные состояния имеют один и тот же номер. Встолбце 4 код состояний выбран так, что бы два разряда кода33формировались кодом символа, поступившим последним.
Длясостояния Λ буква х означает любой символ кроме а.Удалив эквивалентные состояния, получим автоматнуютаблицу 2 (состоянию Λ соответствуют первые три строки таблицы).Реализовать автомат можно в виде схемы рис.23. Контурнаячасть схемы идентична выше расположенным CL—RG с инымподключением входов:A1 Æ i2A2 Æ i1in1 1in2 2B1 Æ i4B2 Æ i3D1 RG Q1Q2D2C c1A 21 12 2B1 12 2 comp1=1syn & C22i1 d0i2i3 d1i4 d2i5i6 CL1 outD1 RG Q1Q2D2C cРис.23. Реализация автомата7.3.Детерминизация источникаРассмотрим процедуру, позволяющую преобразовать источник в автомат Мура.Термины: Чтобы различать сходные понятия в источнике ив автоматном графе вершины источника будем называть узлами,а дуги источника будем называть стрелками.
Стрелки нумеруются. Узлам сопоставляются имена, а также индексы, состоящие изподмножества номеров стрелок. Состояниям автомата сопоставляется шифр, состоящий из подмножеств номеров стрелок.Действия:1) Нумерация стрелок. Петли без меток из источника удаляются; каждая помеченная стрелка получает уникальный номер,34начиная с 2 и далее 3,4,...2) Таблица источника. Заготавливается таблица (пустая), вкоторой должны быть следующие столбцы: имена узлов, индексыузлов, остальные столбцы соответствуют всем символам входного алфавита.3) Индексация узлов.
Образуется новый единственный входной узел, который получает индекс 1. Этот узел соединяетсястрелками без меток со всеми старыми входными узлами. Каждому узлу (за исключением узлов, из которых выходят толькопустые стрелки) присваиваются уникальные имена, которые помещаются в таблицу. Узлам присваивается индекс, состоящий изномеров всех входящих в этот узел стрелок. Индекс узла, из которого выходит пустая стрелка, приписывается к индексу узла, вкоторый эта стрелка входит. Индексы именованных узлов помещаются в таблицу.4) В столбцы, именованные входными символами, записываются номера стрелок, выходящих из узла, соответствующегоданной строке и данному входному символу.5) Автоматная таблица. Заготавливается таблица (пустая), вкоторой должны быть следующие столбцы: шифр состояния, выходное значение, остальные столбцы соответствуют всем символам входного алфавита.6) Заполнение строки автоматной таблицы.
Первой строке,соответствующей начальному состоянию автомата, присваивается шифр 1. Начиная с этой строки, в столбцы, именованныевходными символами, записываются номера стрелок, имеющихметку, совпадающую с именем столбца и выходящих из всех узлов, в индексах которых содержится какой-либо номер из шифраэтого состояния (строки). Если таких стрелок нет, то записывается номер 0.
В строке с шифром 0 во всех столбцах содержатсянули. (Состоянию с шифром 0 соответствует “тупиковое” состояние.)7) Порождение новых строк. После заполнения очереднойстроки в столбцах, именованных входными символами, записанышифры состояний. Если в строке появились новые шифры, невстречавшиеся ранее, то они порождают новые строки.358) Выходные значения. Выходным значением-индикаторомпомечается то состояние, в шифре которого есть номер, совпадающий с номером из индекса финального узла.Пример 7.3.-1.
Воспользуемся ранее рассмотренным примером. Спроектировать автомат, который устанавливает на выходе 1, если в последних 3-х тактах на двухразрядном входе автомата перед появлением кода 11 (в 4-м такте) появился толькоодин раз код 00.Введем следующие обозначения для сигналов на входе автомата:00 Æ O11 Æ I(01,10) Æ XПостроим источник дефинитного языка (рис.1) и детерминизируем его.Рис.24. Источник дефинитного языкаТаблица источника:имяabc1c2c3d1d2d3efиндекс1,2,3,41,2,3,4510,1115,166,71217,188,9,13,14,1920O25-12---19---X310,156-17813----I411,167-18914-20--36Таблица автомата:шифрO12,52,52,53,10,152,5,124,11,162,5,123,10,15,62,5,124,11,16,72,5,122,5,122,53,10,15,172,5,12,194,11,16,182,5,12,193,10,15,17,82,5,12,194,11,16,18,92,5,12,193,10,15,6,132,5,124,11,16,7,142,5,122,5,12,192,54,11,16,18,20 1 2,5,12,194,11,16,7,14,20 1 2,5,124,11,16,18,9,20 1 2,5,12,19X3,10,153,6,10,153,10,15,173,10,15,173,8,10,15,173,8,10,15,173,6,10,13,153,10,15,173,10,15,173,10,15,173,10,15,173,8,10,15,173,8,10,15,173,8,10,15,173,10,15,173,8,10,15,173,10,15,17I4,11,164, 7,11,164,11,16,184,11,16,184,9,11,16,184,9,11,16,184,7,11,14,164,11,16,184,11,16,184,11,16,18,204,11,16,18,204,9,11,16,18,204,9,11,16,18,204,7,11, 14,16,204,11,16,184,7,11,14,16,204,11,16,18,20ABCCDDEFFGGHHJFIHIGIУдаляя явно эквивалентные состояния, получаем автоматную таблицу, в последнем столбце которой приведены обозначения состояний из примера 7.1.-1.Таблица 7.3.-1ABCDEFGHJFI,1HI,1GI,1OBBEEBJJEBJEJXCDFGHFFGHFGFICDFGHFFIGIHIFGIFIΛOHOHHOHHOHHHOHHHOOHHIHHOIHOHI37ГЛАВА II.
СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРОЕКТИРОВАНИЯ1.Декомпозиция автоматовРассмотрим два примера синтеза автоматов с применениемметода декомпозиции.Пример 1.-1. Синтезировать автомат с одноразрядным входом и одноразрядным выходом, на выходе которого фиксируетсяпо модулю 2 количество единичных блоков с нечетным числомединиц.Рис.1. Временные диаграммы автоматаНа временной диаграмме (рис.1) приведены два возможныхварианта выхода: out_v1 - c “привязкой” изменения к входномусигналу и out_v2 - с “привязкой” изменения к сигналу синхронизации.Решение 1.
В этой задаче нужно считать по модулю 2, какколичество блоков, так и количество единиц в блоке. Поэтомувозможна следующая композиции автоматов - рис.2.insy nA1A2ino ut_v1sy nA1A2o ut_v2Рис.2. Декомпозиция автоматаАвтомат A1 считает по модулю 2 количество единиц в блокеи сбрасывается в ноль, если нет единиц на входе. Автомат A2счетчик по модулю 2 с параметром. В первом варианте А2 синхронизируется отрицательным фронтом входного сигнала in, переключается при единице на q; во втором варианте А2 - синхронизируется отрицательным фронтом сигнала q, переключаетсяпри нулевом входном сигнале in.
Временные диаграммы (рис.3),автоматные таблицы и схема (рис.4) иллюстрируют решение. Всхеме использованы JK-триггеры ради минимизации комбинационной схемы автомата.38Рис.3. Временные диаграммы автоматовАвтоматные таблицы и таблицы возбуждения триггеровA1in01001100010011XX010XX111sinsJinsKA2_V1q01001110010011XX010XX101sqsJ=inqsK=1A2_V2in01010101010101XX010XX110sinsJ=qinsK=qJ=⎯inK=⎯inРис.4. Схемы автоматовРешение 2 - без использования декомпозиции. Пусть искомый автомат имеет две группы состояний:xP - состояния, в которых автомат находится, если в текущейвходной последовательности нечетное количество блоков с нечетным числом единиц;39xR - все тоже самое, но с четным количеством блоков.В каждую из групп входят состояния:Kx - закончился или не начался блок единиц;Lx - текущее количество единиц в блоке нечетно;Mx - текущее количество единиц в блоке четно;Чтобы получить временную диаграмму по варианту-1(out_v1), надо синтезировать автомат Мили, а, если – по варианту-2 (out_v2), то надо синтезировать автомат Мура.ВАРИАНТ-1ВАРИАНТ-2Рис.5.
Диаграммы автоматов без декомпозицииСостояния (KP,MP) и (KR,MR) явно эквивалентны, поэтомув графах останется по четыре состояния.Если коды состояний для автомата Мура (вариант-2) выбрать так, чтобы начальное состояние (KR) имело код [00], а выходное значение совпадало со значением одного из разрядов кода, то способов кодирования состояний, приводящих к различным схемам, всего 2.KR0000код1код2LR1010KP0111LP1101После минимизации комбинационной части автомата получаем: при реализации памяти на D-триггерах переменные di, адля JK-триггеров – переменные (Ji, Ki).as2,s1 00011110000010001(d1=a ⋅ s2 ⋅⎯s1 V ⎯s2 ⋅ s1 V a ⋅ s1) (J1=K1=∼a*s2)110110100(d2= ⎯a ⋅ s2)код1(J2= a, K2=1)40aas2,s1 00011110код2(J1=⎯a ⋅ s2, K1=⎯a ⋅⎯s2)000001111(d1=⎯a⋅s2 V a⋅s1)110110100(d2= a+s2)s2,s1 00011110автомат Мили (ВАРИАНТ-1)(J2=K2= a)00011код210110out_v1=d1=⎯a⋅s2 V a⋅s1Пример 1.-2.
Синтезировать устройство, которое вычисляетмаксимальное из нескольких чисел. Каждое из чисел поступаетпо одноразрядной шине, начиная со старших разрядов. Одноименные разряды всех чисел поступают синхронно. На одноразрядном выходе синхронно появляется результат - значения разрядов максимального из чисел.Для каждого отдельного числа спроектируем локальный автомат со следующими состояниями:M - число максимальное - значение на выходе равно входному;N - число немаксимальное - на выходе автомата 0, т.е.
наименьшее возможное значение.Теперь можно сравнить значения на выходе всех автоматови выдать максимальное, т.е. выполнить дизъюнкцию, см. рис.6.Рис.6. Структура автомата поиска максимальногоЛокальный автомат (Ai) переходит из состояния M в состояние N тогда, когда число перестает быть максимальным, т.е.когда значение входного разряда числа меньше значения на выходе дизъюнкции.Выход m, а значит и выход qi должен зависеть без сдвига отпеременной di. В то же время выход автомата qi должен зависеть41со сдвигом от переменной m, поскольку это переменная обратнойсвязи. Поэтому структура автомата должна быть такой, как нарис.7.Рис.7.
Схема локального автоматаАвтоматная таблица:Таблица f:Таблица g:d,m00s011110sd..01d,m00 01 11 10sM0,M0,N1,MX,X00,1,0,0,1,0,XN0,N0,N0,N0,N10,0,1,1,1,1,1К методам декомпозиции можно также отнести приемы,рассмотренные в гл.I,п.п. 7.1.3, 7.1.4., 7.2.2.Автоматы на регистрах сдвигаАвтоматы, память которых реализована на регистрах сдвига,имеют следующие достоинства:1) Облегчается решение «вечной» проблемы контроля и диагностики сложных схем.
(Современные схемотехнические варианты процедур диагностики связаны с объединением элементовпамяти цифрового устройства в регистр сдвига. Построение автомата на регистрах сдвига позволяет уменьшить число обратныхсвязей, что облегчает решение математической стороны той жепроблемы.)2) В ряде случаев такая структура памяти позволяет упростить комбинационную часть схемы автомата.2.1. Автоматы без обратной связиНазовем индексом обратной связи минимальное число ветвей, которые должны быть «рассечены» для того, чтобы в схеме(ориентированном графе) не было бы контуров.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
