Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 147
Текст из файла (страница 147)
Применительно к рассматриваемой нами задаче составления таблицы состояний временные диаграммы пусть имеют внд, указанный на рис. 7.47. РЕз!!ЛИЗАЦИэ1 НАДЕЖНОЙ НАЧАЛ)яНОй Уз ТяйтоВКИ Система будет работать надлежащим образом только атом случае, если конструкция конечного автомата гарантирует, что прн включении он войдет в известное начальное состояние типа состояния !й!Т в разбираемом нами примере. Обычно для этого аналоговой схемой генерируется сигнал начальной установки ВЕЗЕТ. Такая схема, как правило, обнаруживает напряжение, близкое к полному напряжению питания 1скажем, 4.5 В) н повторяет это напряжение на своем выходе в течение времени (например, порядка 100 мс), достаточного для того, чтобы все компоненты (в том числе генераторы) успели войти в установившийся режим, пока система еше остается «незапущенной».
Такой аналоговой ИС, предназначенной для начального запуска, является микросхема Т!.7705 фирмы Техаз 1пзггцтепгз; она имеет встроенный эталонный источник напряжения 4.5 В, используемый для обнаружения включения питания, а время, в течение которого система остается «незапущенной», задается внешними резистором и конденсатором. Есл и конеч ны й автомат строится на дискретных триггерах с асинхронными входами установки в состояние ! н сброса, то автомат можно ввести в желаемое начальное состояние, подавая сигнал ВЕЗЕТ иа эти входы. Когда таких входов нет, или в том случае, когда запуск должен быть синхронным (как это бывает в системах с быстродействующими микропроцессорами), лля сигнала ВЕЗЕТ можно выделить отдельный вход конечного автомата, такой что при действии сигнала на этом входе происходит желаемая начальная установка всех элементов, ответственных за следующее состояние автомата.
7 4. Проектирование тактируемых синхронных конечных автоматов 66! с«ос« рис. 7.47. Временные диаграммы для конечного автомата, рассматриваемого в качестве примера (С1 ОСК вЂ” тактовый сигнал) Первый шаг при составлении таблицы состояний заключается в подготовке трафарета. Из словесного описания нам известно, что предмет нашего рассмотрения является автоматом Мура: сигнал на его выходе зависит только от текущего состояния, то есть от того, что происходило в течение предшествующих периодов тактового сигнала.
Следовательно, мы должны предусмотреть по одному столбцу, в котором будут перечислены следующие состояния, для каждой возможной комбинации входных сигналов и один столбец для значений выходного сигнала, что и сделано на рис. 7 48(а). Порядок, в котором перечисляются комбинации входных сигналов, на этом этапе существенен, но мы выбираем его таким, как на карте Карно, чтобы позднее нам было проще вывести уравнения возбуждения.
В случае автомата Мили нам надо было бы опустить столбец, относящийся к выходу, а значения выходного сигнала записывать вместе со следующими состояниями для каждой комбинации входных сигналов. Левый столбец предназначен для словесгюго комментария, который просто напоминал бы нам значение каждого состояния или связанной с ним «истории».
В словесном описании ничего не говорится о том, что должно происходить в автомате с самого начала, так что здесь мы должны импровизировать. Предположим, что сразу после включения питания автомат входит в иачаяьиое сосщояиие (гни!а! «гаге), которое мы назовем в этом примере !ы!т. пишем имя начального состояния (1Ы1Т) в первой строке и оставляем достаточно места для других строк (состояний), которые понадобятся в дальнейшем. Мы можем также заполнить место для значения Е в состоянии 1Ы!Т; здравый смысл подсказывает нам, что это значение следует взять равным О, поскольку никаких входных сигналов у нас не было. Теперь нам необходимо заполнить строку 1Ы1Т информацией о следующих состояниях. Выходной сигнал 2 не сможет стать равным 1, пока мы не увидим, по меньшей мере, двух значений сигнала на входе А, поэтому возможны только два состояния АО и А1, которые булут «помнить» значение сигнала А на предыдучцем такте [рис.
7.48 (Ь)[. В каждом из этих состояний сигнал бравен О, так как условия возникновения! на выходе все еще не уловлетворены. Точное значение состояния АО таково: «На предыдущем такте сигнал А равнялся О, за такт до этого сигнал А не равнялся нулю и сигнал В не оставался равным 1 со времени предыдущей пары одинаковых значений сигнала А». Аналогично определяется состояние А1.
662 Глава 7. Принципы проектирования последовательиостиых схем (а) д яв Значение (Ь Значение АВ оо и ~~ и~ д Нннмнкаме нн дт дд О надоев а ~нп АО яа (д) Значение с Значение яв а~ м ~! АВ и Ю ~нн м м ок яа АО ок О~ а»в Д ннннаоаене ~но яо Наа она О м нада А! надоеаднодндее ок ННННН:СОПНЕ нада о Надвма ваада дноаеане ад о м О о яо м ок м Яо М ОК А~ м ок о м о ок О Рис. 7.46. Процесс составления таблицы состояний К этому моменту мы знаем, что у нашего конечного автомата есть, по крайней мере, три состояния, и мы приготовились заполнить еще две пустые строки. Хм! Это не очень хорошая тенденция! При заполнении данными о следующих состояниях одной строки (соответствующей состоянию 1(ч)Т) нам понадобилось два новых состояния АО и А1.
Если продолжать в том же темпе, то к вечеру у нас будет 65 535 состояний! Впрочем, нам надо будет внимательно присматриваться к уже существующим состояниям, имеющим то же самое значение, всякий раз, когда нам, возможно, понадобится вводить новые состояния. Давайте посмотрим, как это делается. Пусть автомат находится в состоянии АО; тогда известно, что на последнем такте сигнал А равнялся О. Поэтому, если сигнал А будет равен О снова, то мы перейдем в новое состояние ОК со значением выходдюго сигнала Е, равным ! [рис. 7 48(с)). Если же сигнал А будет равен 1, то у нас не будет двух одинаковых значений этого сигнала подряд, так что автомат перейдет в состояние А1, запомнив тем самым, что в последний раз была!. Аналогично, из состояния А1 мы переходим в состояние ОК, если получаем вторую ! на входе А подряд, или в состояние АО, если придет О [см.
рис. (д)1. Описание автомата говорит нам, что после тою, как автомат попал в состояние ОК, он может оставаться в нем, пока В = 1, независимо от значений сигнала на входе А [см. рис, 7.49(а)]. Если В = О, то снова необходимо проверить, нет ли двух единиц или двух нулей подряд на входе А. Однако в этом случае мы стачкиваемся с небольшой проблемой. Текущее значение входного сигнала А может быть вторым следующим подряд тем же самым значением, а может и не быть; таким образом, мы можем опять остаться в состоянии ОК или должны вернуться назад к состоянию АО или А1.
Мы определили состояние ОК слишком широко; оно не «помнитв достаточно информации, чтобы сказать нам, куда идти дальше. 7.4. Проектирование тактируемых синхронных конечных автоматов 663 АВ а! Ос 11 1О а) АВ а сп~ о! !о нею ииюопа Ю На А бнл О НаАбанс НпАДЮЮНО ЮОЮ н В Пе НпилыюоюоВ66 Наде по НаАбню1 Диоииазв аап пю идпее А = О Дю!Впп ази л хпедаи А = 1 ЮО Аа Ю А! АС ОКП ОКП А! м аа м! ок 1НО АП Ас ОК ю ок м о А1 о 'Ю' о 1 АП А! ок м АП Ок ок ок м о л! о ок о око ок! АВ о! Ад (с со 1Д !И Ос АО М окп м ао ок! око ок! Нуюнюсоюаапе на лакло ЮАЫЮ! Дед рюал завив псслплню А = О Дпар'аннлзаювп псе педиа А = 1 А! о м о ок! о А 1ИО АС м ока лп око ю око АП М ОКО Ас Ап ОК! око ок ! 1Ют Ю Ас ОКП м ю око око о м о ок! о А Нуаансбси св е НаАбнлб На А«па ! лирпю павии псслюибА=О днов кслуюспп ппследнес А = 1 СЮ! Ас ОКО ОК! ОК! ОК1 с* Рис.
7.49. Продолжение процесса составления таблицы состояний «боек втдтд н«т Ао око Ас ок! Ао око оке око м ок! Ао Рис. 7.60. Временные диаграммы и последовательность состояний для конечного автомата в рассматриваемом примере (СЕОСК вЂ” тактовый сигнал, ВТАТŠ— состояние) Эта проблема решается расщеплением состояния ОК на рис. 7 49(Ь) на два состояния ОКО и ОК1, которые «помнят» последнее значение сигнала на входе А. Для состояний АО и А1 все следующие состояния можно выбрать из уже существующих, как это следует из рисунков 7.49(с) и (б)).
Если, например, автомат, находясь в состоянии ОКО, получает 0 на входе А, то он может оставаться в состоянии ОКО; мы не должны вводить новое состояние, чтобы «помнить» три нуля подряд, так как описание автомата не требует от нас обнаружения этого случая. Таким образом, мы достигли «замкнутостн» таблицы состояний, которая описывает теперь автомат с конечным числом состояний. Ради спокойствия, в качестве проверки парис. 7.50 повторены временные диаграммы, приведенные ранее на рис.
7.47, только на этот раз они сопровождаются перечислением состояний, через которые должен проходить автомат согласно нашей окончательной таблице состояний, 664 Глава 7. Принципы проектирования последовательностных схем При нашем словесном описании таблица состояний парис. 74!)(С)) является «минимальнойл в том смысле, что содержит наименьшее возможное число состояний.
Но возможны и другие таблицы с большим числом состояний, как, например, на рис. 7.51, которые также будут работать. К таким таблицам можно применить формальную процедуру минимизации числа состояний. (а) АВ АВ Знииние 5 ОО Ы 11 1О О О окп о т ОК11 ОК1 1 Ап А1 «К!1 На Ои се сосне не На Абинб На А бина 1 НаАбтссб На А бнпс 11 ОК, наАбинб ОК, на А била 1 МТ Ас АО ОКОО А1 Ао Оксе ОКСО ОК11 Ао ОКАО ОК«1 ОКА! Ао АО А! ОКСО А1 Ао ОК11 ОКСО ОКА! ОКАО ОК1 ! ОКСО ОКЮ ОКДО ОК11 О А! б ОК11 О а! ОК11 А1 ОН!1 ! рис. 7.61. Неминимальные таблицы состояний, эквивалентные таблице на рис.
7.49(б)) Основная идея формальных процедур минимизации заключается в обнаружении Вквиваеентных состояний (едигка!Внг Егнгез)' два состояния эквивалентны, если их невозможно различить, наблюдая только текущие и следующие значения сигналов на выходе автомата (но не переменных состояния, характеризующих его внутренние состояния).
Пару эквивалентных состояний можно заменить одним состоянием. Два состояния 81 и 82 эквивалентны, если выполнены следующие два условия. Во-первых, находясь в состояниях 81 и 82 автомат должен вырабатывать одинаковые значения сигнала(или сигналов) на выходе; в случае автомата Мили это должно быть верно для всех входных комбинаций. Во-вторых, при каждой входной комбинации за состояниями 81 и 82 должно следовать либо одно и тоже состояние, либо эквивалентные состояния. Детали формальных процедур минимизации числа состояний можно найти в литературе. Однако большинство разработчиков цифровых устройств редко пользуется этими процедурами. Более тщательное увязывание значения состояний с требованиями задачи позволяет опытным проектировщикам — в случае задач небольшого объема — составлять таблицы с минимальным или близким к минимальному числом состояний, не прибегая к формальной процедуре минимизации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
