Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 146
Текст из файла (страница 146)
Тактируемый синхронный конечный автомат с тремя триггерами и восьмью состояниями 7.3. Анализ тактируемых синхронных конечных автоматов 655 Табл. 7.4. Таблицы «переходувыход» и .состояние/выход» для конечного ав- томата на рис. 7.43 (Ь) 8 ОО ОТ ТО тт Х122 (а) айа)ао ОО От )О !т гтгг 02ь О! Диаграмма состояний в данном примере имеет внд, показанный на рис. 7.44.
Поскольку здесь мы имеем дело с автоматом Мура, значения сигналов указаны вместе с именами состояний. Каждая стрелка помечена выражепиви перехода (ггапигуоп ехргетз!оп) переход по стрелке происходит при таких входных комбинациях, для которых это выражение перехода равно 1. Переходы, помеченные единицами, выполняются всегда. Х' У' Рис. 7.44. диаграмма состояний в соответствии с табл. 7 4 000 00! 010 011 100 10! 110 1!! 000 100 001 001 О!О 110 О!1 01! 101 101 001 00! 111 !!! 011 О!1 00! ОО! !0 011 011 !О 000 000 10 О!О О!О ОО 10! 10! !1 001 001 10 !!1 !!1 11 011 011 !1 я г)Оь А А Е В В В В 0 С С 0 А 0 0 0 С Е Е Е г В В В Й Н Н Н Н 0 0 0 В 10 0 !О А 10 С 00 1! В 10 Н 1! 0 11 ббб Глава 7.
Принципы проектирования лослезховвтельностных схем Выражения переходов у стрелок, выхолящих из данного состояния, должны быть взаимна исключающими (тигиа! ехс)илгап) и исчерпывающими е совокупности (а11 1пс1илгоп) согласно следуюгцим правилам: ° Никакие два выражения перехода не могут равняться 1 при одной и той же входной комбинации, поскольку при фиксированной входной комбинации у автоматов не может быть двух следующих состояний. ° Для любой возможной входной комбинации какое-то выражение перехода должно равняться 1, так чтобы оказались предусмотренными все возможные следующие состояния. Используя информацию, содержащуюся в таблице состояний, можно записать выражение перехода из любого текущего состояния в следующее состояние в виде суммы минтермов для тех входных комбинаций, которые вызывают этот переход.
При желании выражение можно минимизировать, что позволяет представить информацию в более компактном виде. Выражения переходов более всего полезны при проектировании таких конечных автоматов, в отнощеини которых эти выражения можно вывести из словесного описания задачи, как мы увидим это в параграфе 7.5. *7.3.5. Анализ конечных автоматов на ) К-триггерах Основная процедура анализа тактируемых синхронных конечных автоматов с ОК- триггерами — та же, что и в предыдущем разделе.
Единственное отличие состоит в том, что теперь у каждого триггера имеются два уравнения возбуждения: ло одному для входов О и К. Чтобы получить уравнение переходов, необходимо подставить оба выражения для этих входных сигналов в характеристическое уравнение ОК- триггера: О* = О 0'+ К' 0 . На рис, 7.45 приведен пример конечного автомата с ОК-триггерами. Глядя на принципиальную схему, можно записать следующие уравнения возбуждения: )О = Х Ъ' КО = Х ~'+ У 01 ,)1 = У 00 + У К1 вт С!О'+ Х У 00.
Подставляя 00, КО, )1 и К1 в характеристические уравнения ОК-триггеров, полу- чим уравнения переходов: СЮ* = 30 ОО'+ КО' СЮ =Х. т' ОО'+ (Х ~'+У 01)' 00 =Х У' 00'+Х' 1л С!О+К'. 01' СЮ+У 01' СЮ 01*=)1 01'+ К1' 01 =(Х 00+У) 01'+(У ОО'+Х.У' ОО)' 01 =Х.01'.00+У.01'+Х' Зе.01+~ 01 ОО'+Х' 01 00+У 01.СЮ. Табл. 7. 5(а) представляет собой таблицу переходов, составленную по этим уравнениям.
Из принци ли ал ьной схемы следует также, что уравнение выхода имеет вид: Е = Х. 01. 00+У 01' 00', 7.3. Анализ тактируемых синхронных конечных автоматов 557 результирующие значения выходного сигнала указаны в табл. (а) в каждом из столбцов вместе со слелующим состоянием. Присваивая состояниям имена от А до С, получаем таблицу «состояние1выход» [табл. (Ь)). Соответствующая диаг- рамма состояний с выражениями переходов показана на рис, 7,46 сгк Рис. 7.45. Тактируемый синхронный конечный автомат с ОК-триггерами Табл. 7.5.
Таблицы «переходУвыход» и «состояние/выход» для конечного ав- томатана рис.7.45 (а) (Ь) ХУ !71 ОО ОО 01 10 8», Е О)1»СО', Е х .т' а-и Рис. '7.45. Диаграмма состояний для конечного автомата, описываемого таба. 7.5. 00 01 10 11 00.0 !0,1 01.0 !0,1 О!.0 11.0 10 О 11,0 10. О 00. 0 11. О 00. 0 11.0 10.0 00,1 10,1 А А, О С, 1 В. 0 С, 1 В ВО ()О СО СО С СО АО 00 АО () 00 СО А1 С) 658 Глава 7. Принципы проектирования последоввтельностных схем 7.4.
Проектирование тактируемых синхронных конечных автоматов Создание тактируемого синхронного конечною автомата начинается с его словесного описания или задания его технических характеристик, а затем выполняются те же шаги, что и при анализе, перечисленные в предыдущем параграфе, только в обратном порядке: 1. На основе словесного описания составляется таблица «состояние/выход»; для состояний используются мнемонические имена. (Можно также начинать с диаграммы состояний; этот метод рассмотрен в параграфе 7.5.) 2. (Необязательный шаг) Минимизируется число состояний в таблице «состояние!выход» (гааlе т!п!тиаг!оп).
3. Выбирается набор переменных состояния и комбинации переменных состояния ставятся в соответствие именам состояний (таге аз»!8птеп!). 4. Чтобы получить таблицу «переход!выход», комбинации переменных состояния подставляются в таблицу «состояние!выход»; в результате каждой возможной комбинации «состояние!вход» теперь соответствует желаемая следующая комбинация переменных состояния и желаемый выход.
5. Выбирается тип триггеров для памяти состояния (например, 0- или ~Ктриггеры). В большинстве случаев этот выбор бывает уже произведен в уме на начальной стадии проекта, но данный шаг — это ваша последняя возможность передумать. 6.
составляется таб»ила возбуждеп1т (ехсиа!!оп габ7е), в которую заносятся значения возбуждающих воздействий, необходимые для того, чтобы получить желаемое следующее состояние для каждой комбинации «состояние/вход». 7. Из таблицы возбуждения выводятся уравнения возбуждения. 8. Из таблицы «переход!выход» выводятся уравнения выхода. 9. Рисуется принципиальная схема, включающая элементы, хранящие переменные состояния, и реализующая требуемые уравнения возбуждения и выхода.
(Впрочем, уравнения можно реализовать непосредственно в программируемом логическом устройстве.) В данном параграфе мы рассмотрим каждый из этих шагов в процессе построения конечного акюмата. Самым важным является шаг!, так как именно здесь разработчик занимается собственно проектированием в творческом процессе перевода словесного (возможно, неоднозначного) описания конечного автомата на обычном языке в формальное табличное описание. Шаг 2 практически никогда опытными разработчиками не выполняется, а вот дяя шага 3 требуется большое мастерство. После того как первые три шага пройдены, все остающееся можно считать рутинной работой, требующей следования вполне определенным правилам синтеза.
Самыми утомительными являются шаги 4 и 6-9, но нх легко автоматизировать. Например, при разработке конечного автомата, который предстоит реализовать в программируемом логическом устройстве, рутинную часть работы можно поручить компилятору языка АВЕЬ, как это будет сделано в разделе 7.1!.2. Но все же важно понимать детали процедуры синтеза как для того, чтобы иметь возможность оценивать работу компилятора, так и для того, чтобы была возмож- т,а. Проектирование тактнруемых синхронных конечных автоматов 659 ность сообразить, что происходит в действительности, когда компилятор дает неожиданные результаты. Поэтому ниже в этом параграфе рассматриваются все девять шаюв процедуры проектирования конечного автомата, СОСТАВЛЕНИЕ ТАБЛИЦЫ СОСТОЯНИЙ— ЭТО СВОЕГО РОДА ПРОГРАММИРОВАНИЕ Составление таблицы состояний (или, что эквивалентно, вычерчивание диаграммы состояний) — творческий процесс, многими своими чертами напоминающий написание программы лля компьютера; ° Вы начинаете с достаточно точною описания входов и выходов, но с возможно неоднозначным описанием желаемого соотношения между ними, не заботясь о том, как действительно получить желаемые выходы при имеющихся входах.
° В процессе осуществления проекта вам, возможно, приходится уточнять, что именно и каким из многих способов будет реализовываться, иногда руководствуясь здравым смыслом, а иногда произвольно. ° Возможно, вам понадобится оговорить специальные случаи, о которых не было речи в первоначальном описании, и предусмотреть их обработку.
° Вероятно, при выполнении этой работы вам надо будет не упускать из виду несказько идей. ° Поскольку выполняемые действия не алюритмизуемы, нет никакой гарантии, что вы составите таблицу состояний с конечным числом состояний или напишете программу, состоящую из конечного числа строк. Однако, если вы не работаете на правительство, вы должны попытаться сделать это.
° Когда, наконец, вы запустите конечный автомат или программу, он или она будут делать точно то, что вы им повелели, — ни больше и ци меньше. ° Нет гарантии, что ваш продукт заработает с первого раза; возможно, придется его отлаживать или даже весь процесс в целом повторить. Хотя составление таблицы состояний — это, конечно, проблема, не надо бояться.
Если вам приходилось сталкиваться с подобными задачами во время учебы, то вы, вероятно, уже написали несколько работающих программ; вот почему вы вполне можете стать также хорошим составителем таблиц состояний. 7.4.1. Пример составления таблицы состояний Сугцествует несколько различных способов описания таблицы состояний конечного автомата. Позднее мы увидим, как можно косвенно задавать таблицу состояний на языках АВЕЕ и т'НОЕ. Однако в этом параграфе мы будем иметь дело только с таблицами состояний, задаваемыми явно, в той же самой табличной форме, в какой мы пользовались ими при анализе в предыдущем параграфе. Процесс составления таблицы состояний, а затем — в следующих разделах — вся процедура синтеза, будут представлены нами на примере следующей простой задачи: Построить тактируемый синхронный конечный автомат с двумя входами А и В и олним выходом Е, таким что выходной сигнал е равен К если ян г.
~ принципы проектирования последовательностных схем входной сигнал А имел одно и то же значение на каждом из двух предыдущих тактов в тактовом сигнале вы входной сигнал В равен ! с последнего момента времени, когда первое условие было выполнено. В противном случае выходной сигнал должен равняться О.
Не волнуйтесь, если на этом этапе смысл данного задания, мягко ~ оворя, вам не вполне ясен. Ваша задача как разработчика состоит в преобразовании описания такого рода в таблицу состояний, которая должна быть совершенно недвусмысленной; даже если не получится то, что имелось в виду, все же будет, по крайней мере, основа для обсужления и усовершенствования. В качестве дополнительною «указанная или требования условия задачи о составлении таблицы состояний включают временные диаграммы, демонстрирующие ожидаемое поведение конечною автомата для одной илн нескольких последовательностей входных сигналов. Такого рода временные диаграммы вряд ли однозначно зададут поведение автомата прн всех возможных входных воздействиях, но, как и раньше, это служит хорошей отправной точкой и контрольным тестом, по которому можно будет проверить правильность работы созданного устройства.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
