Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 152
Текст из файла (страница 152)
Принципы проектирования последоввтельностных схем Х 01' 02" 0ЬЗ" Х' 0203~ 00 01 11 10 01 10 02 03 Х' 02 03'Х 01 02 03'Х' Рис. 7. 59. Карты Карно для выходных функций ОН~К и Н!йТ в автомате, управляющем кодовым замком 7.5. Проектирование конечных автоматов с помощью диаграмм состояний Помимо планирования структуры цифровой системы в целом, построение конечных автоматов„возможно, является самой творческой задачей, какую приходится решать конструкторам цифровых устройств. Большинству из них нравится графический подход.
Вам, наверное, приходилось решать многие задачи, рисуя эскиз. По этой причине при проектировании небольших конечных автоматов и устройств средних размеров часто пользуются диаграммами состояний. В этом параграфе мы приведем примеры разработки с использованием диаграмм состояний и опишем простую процедуру синтеза схем на их основе. Эта процедура лежит в основе метода, реализуемою средствами автоматизированного проектирования, которые могут создавать логическую структуру из графического представления или даже из текстового представления диаграмм состояний. Составление диаграмм состояний во многом подобно составлению таблицы состояний, которое, в свою очередь, очень похоже на написание программы, как мы видел и это в разделе 7 А.1.
Однако имеется одно принципиальное различие между диаграммой состояний и таблицей состояний, которое делает составление диаграммы состояний проще, хотя при этом риск допустить ошибку увеличивается: Таблица состояний представляет собой исчерпывающий список следующих состояний для каждой комбинации состояние!вход. Никакая неоднозначность не возможна. ° В диаграмме состояний имеется множество стрелок, у которых надписаны выражения переходов. Даже при наличии многих входов с каждой стрелкой связано только одно выражение перехода.
Однако при составлении диаграммы состояний нет гарантии, что выражениями переходов у стрелок, выходящих из данного состояния, все комбинации входных сигналов покрываются точно по одному разу. Т б. Проектирование конечных автоматов с помощью диаграмм 883 8 неоднозначной диаграмме состояний (атЫдиокя жше Йаягат), то есть в диаграмме состояний, составленной ненадлежащим образолг, для некоторых комбинации входных сигналов следующее состояние может оказаться не заданным, что в общем случае нежелательно, тогда как для других комбинаций входных сигналов может быть указано песков ько следующих состояний, что, очевидно, неправильно, '1акнм образом, составление диаграмм состояний необходимо осуществлять с большой осторожностью.
Приведем несколько примеров. Нашим первым примером будет конечный автомат, управляющий задними огнями в автомобиле марки Рогг1 ТйнпоегЬ1гд выпуска 1965 года (рис. 7.60). С каждой стороны имеется потри фонаря, и при поворотах они зажигаются последовательно, как показано на рис. 7.61, чтобы наглядно демонстрировать направление поворота. У конечного автомата два входных сигнала1 ЕЕТ и ВАНТ, которые несут поступающую от водителя информацию о его намерении совершить левый или правый поворот.
Имеется также вход аварийного мигания Ндс; при поступлении сигнала на этот вход задние огни должны работать в аварийном режиме; все шесть фонарей мигают одновременно, включаясь и выключаясь. Мы предположим также, что есть автономный источник тактового сигнала, частота которого равна желаемой частоте мигания. ЙА ЙВ ЙС зьнс. Ч.88. Задние фонари автомобиля марки Еогг) Тнипг1егЬ~гг1 7.6.
Проектирование конечных автоматов с помощью диаграмм 686 О.еот з мент ОВЗ Таблица выхода сасзооиио сс ев Ох пх вв пс |с|а а о о ы о а Ог О сз В| О О О аз 0 О О пз а о о |ВЗ о о о а а о о о о о о о о о а 1 1 ! ! 1 1 Рис. 7.62. Первоначальный вариан~ диаграммы состояний и таблица выхо- да для автомата, управляющего задними огнями автомобиля марки Еого Т!зипоегЬ!гб В диаграмме состояний, представленной на рис.
7.62, остается нерешенной одна существенная проблема: в ней не предусмотрена обработка случаев, когда одновременно действует несколько входных сигналов. Например, что произойдет, если автомат находится в состоянии !ОЕЕ и поступают оба сигнала СЕЕТ и НАЛ? Согласно диаграмме состояний автомат переходит в два состояния Е! и (ЯЗ, что невозможно, На практике автомат перешел бы только в одно следующее состояние, которым могло бы быть!.1, ЫЗ илн вообще какое-то третье (возможно неиспользуемое) состояние, не имеющее никакого отношения к данной ситуации, в зависимости от тою, как именно реализован конечный автомат (см., например, задачу 7.58).
Эта проблема преодолена в диаграмме состояний, показанной парис 7.бЗ, где более высоким приоритетом наделен входной сигнал НА7. Кроме того, одновременное включение сигналов СЕЕТ и В!ВНТ воспринимается как требование аварийного режима, поскольку водитель явно смущен и ему нужна помощь.
В новой диа рамме состояний нет неоднозначности, поскольку выражения переходов„надписанные у стрелок, выходящих из каждого состояния, являются взаимно исключающими и исчерпывающими в совокупности. Другими словами, для каждого состояния нет двух выражений, которые равнялись бы! при одной и той же комбинации входных сигналов, и при каждой входной комбинации какое-то одно из выражений равно !. В этом можно убедиться алгебраически, выполнив в отношении этой или любой другой диаграммы состояний следующие два шага: 686 Глава 7. Принципы проектирования последовательностных схем (1.ЕЕТ + О Рис. 7.63. Исправленная диаграмма состояний для автомата, управляющего задними огнями автомобиля марки Еогг( Тйнпс(егтй(гг( 1.
Взаииное исключение (тшиа( атс(ив(ол). Для каждого состояния показать, что все возможные попарные логические произведения выражений переходов у стрелок, выходящих из данного состояния, равны О. Если имеется и стрелок, то вычислить нужно п(л — 1)(2 логических произведений. 2. Исчерпывающее включение (а(( тс(ив(оп). Для каждого состояния показать, что логическая сумма выражений переходов ч всех стрелок, выходящих из данного состояния, равна 1. Когда имеется много переходов из каждого состояния, зти шаги, особенно первый из них, очень трудно выполнимы.
Однако в типичном случае, даже при наличии у конечного автомата большого числа состояний и входов, число переходов из каждого состояния невелико, потому что большинство разработчиков вообще не в состоянии вообразить себе такие сложные автоматы. Именно в атом Г1роектирование конечных автоматов с помощью диаграмм 687 проя вдаются относительные достоинства и недостатки таблиц состояний и диаг„м состояний. При составлении таблицы состояний указанные два шага не нужны,т ы так как сама структуРа таблицы состояний гарантирует взаимное исключение переходов и полный охват всех возможностей.
Но при большом числе входов у таблицы состояний стишкам много столбцов. Проверка диаграммы состояний на однозначность может быть трудной в прин„ипе, но не очень страшной на практике в случае небольших диаграмм состояний. На рис 7 63 из большинства состояний выходит единственная стрелка, у которой в качестве выражения перехода указана 1; в этом случае проверка тривиальна, На ~ямом деле, требует проверки только состояние 1ОЕЕ, из которого возможно четыре перехода.
Это можно сделать на черновике, перечислив восемь комбинаций трех входных сигналов и убедившись, что каждая из них покрывается тем или иным выражением перехода. Каждая входная комбинация должна давать 1 точно в одном выражении. В качестве упражнения можно рассмотреть диаграммы состояний на рис. 7.44 и 7.46: обе они проверяются в уме. Вернемся к автомату, управляющему задними огнями автомобиля марки Еогд ТЬнпоегЬ1го. Теперь, если есть желание, мы можем приступить к синтезу схемы по диаграмме состояний.
Однако в случае, если мы хотим чуть изменить поведение автомата, то сейчас самое время это сделать до синтеза схемы. В частности, обратите внимание на следующее: если автомат начнет выполнять цикл правого или левого поворота, то, согласно диаграмме состояний на рис. 7.63, этот цикл будет выполнен до конца даже в том случае, если появится сигнал НА2. Может быть это и хорошо с ~очки зрения эстетики рисунка, но для тех, кто находится в автомобиле, было бы безопаснее заставлять автомат переходить в аварийный режим возможно скорее.
Видоизмененная диаграмма состояний, в которой сделано это уточнение, приведена на рис. 7.64. Теперь мы окончательно готовы синтезировать схему автомата. В диаграмме имеется восемь состояний, поэтому нам необходимы, как минимум, три триггеРа, чтобы хранить коды состояний. Очевидно, что кодирование состояний можно выполнить многими способами 18! способами, если быть точным); мы воспользуемся тем из них, который указан в табл.
7.16, по следующим причинам: 1. Код 000 присваивается начальному состоянию 1незанятости), поскольку большинство триггеров н регистров легко устанавливаются в О. 2 Две переменные состояния О1 и ОО позволяют прн выполнении левого поворота осуществлять «счет» в последовательности, задаваемой кодом Грея (Ю1-Е э Е1 -+ 02 — з ЕЗ -э 1ОЕЕ).
Это сводит к минимуму число изменяющихся переменных состояния при переходе от одного состояния к другому, а это часто упрощает логику возбуждения. В силу симметрии переменные О1 и ОО проходят ту же самую последовательность значений и при правом повороте. За различие между левым и правым поворотами отвечает переменная 02. 4 Остающаяся комбинация переменных состояния используется для обозначений состояния ГВЗ. 688 Глава 7. Принципы проектирования последовательностных схем (ЬЕРТ + Рис. 7.64.
Усовершенствованная диаграмма состояний для автомата, уп- равляющего задними огнями автомобиля марки гого' Тбепоегб|гг! Состояние ай а1 ае 0 О О !П.Е 11 ~2 1.3 1!1 ВЗ ЙЗ 1.йЗ О О 0 1 1 О 1 О 1 О 1 1 1 1 1 ! 0 ! О О Табл. 7.16. Кодирование состояний ко- нечного автомата, управляющего задни- ми огнями автомобиля марки роге ТЬ ипоегЬ~п1 7 б. Проектирование конечных автоматов о помощью диаграмм 689 Следующий шаг состоит в написании своего рода таблицы переходов Однанам следует воспользоваться другим форматом, отличающимся от приведенного в разделе 7 4 4, поскольку в диаграмме состояний переходы задаются выражениями, а не исчерпывающим перечислением следующих состояний Мы обратимся к записи переходов в новой форме, в виде списка переходов 1(гапгп(оп !мг), в котором одна строка соответствует каждому переходу, выражаемому стрелкой на диаграмме состояний Такой список переходов для диаграммы состояний на рис 7 б4 и способа „д рования, указанного в табл 7 16, представлен в табл 7 17 Каждая строка содержит текущее состояние, следующее состояние и выражение перехода для одной из стрелок на диаграмме состояний Указаны оба названия текущего и следующего состояний их имена и их колы Имена состояний полезны с точки зрения привязки к рисунку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
