Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 155
Текст из файла (страница 155)
В программе для конечного автомата на языке АВЕ1. совсем легко указывать состояния, следующие за безразличными состояниями, с помощью директивы фэСяет, как это объясняется в одном из замечаний в разделе 7.11.2. На языке ЧН01 это выглядит несколько неуклюже. '7.7.3. Кодирование состояний выходными комбинациями Давайте рассмотрим другую реализацию автомата для игры на угалыван не. Сигналы на выходе автомата являются функциями только состояния; более того, в каждом из состояний р разными именами вырабатываются раз«ичпые выходные комбинации. Поэтому можно воспользоваться выходными сигналами в качестве переменных состояния и присвоить каждому состоянию с именем кодовое обозначение в виде требуемой комбинации выходных сигналов. Такого рода код«рв«а«ие состпояпий «ыходпыми «ачба«ауияии (а«григ-соЫеЫ згаг«аэ«1япгпега) иногда приводит к более простым уравнениям возбуждения, чем в случае, когда лля кодирования состояний используется минимальное число переменных состояния.
В табл. 7.19 приведен список переходов автомата для игры на угадывание, возникающий при кодировании состояний выходными комбинациями. В каждом уравнении переход/возбуждение совсем мало р-терм ов перехода, поскольку число единиц в столбцах следующих состояний в списке переходов невелико: 699 Глава Т. Принципы проектирования последовательностных схем (.1* = (.1' 12'.13' Ь4 ЕВЯ' (01' 02' 03'.
04) + 1 1' 12' (.3' Ы' Ейй' (01' . 02' 03' 04') + 1 1' 12' (3' 1.4' Ейй (01' . 02' 03' 04') 12* = 1.1 12' (.3' 1.4' Ейй' (01' 02'. 03' 04') 13* = Е1' 12 ).3'.14' Ейй' (01' 02' 03' 04') 14* = 1.1' (2' ЕЗ 14' Ейй' (01' 02' 03' 04') Ей й * = 1 1 . 12' (3' Е4' Ей В' . (02 + 03 + 04) + И' (2 . 13' Е4' Ейй'. (01 4- 03 + 04) + 1.1' 12' (3 14'. ЕВР'.
(01 + 02+ 04) + Е1' 1.2' ЕЗ' Е4 Ейй' (01 + 02 + 03) + 1.1' 12' 1.3' 1.4' Ейй (01 + 02+ 03+ 04). Табл. 7.19. Список переходов автомата для игры на угадывание при исполь- зовании выходных сигналов в качестве переменных состояния Следующее состояние Текуцее состояние 5» С!» ),2» СЗ Ь4* Елй» Ш ) О О О 0 0 О О О 0 0 0 0 0 О ) 0 ! 0 О О О 0 0 о о о о О О 0 О 6!'. 62'. 62' 64' 8! 82' 65' 64' 62 -ГЗ -84 6!' 82' 60' 64' 6! .62 65' 84' 6! -6З -64 6!'.62' 6К 64' 8!'.6г'.6з 64' 8!»- 82 !. 64 ОГ 62* 85' 04' 6!' 62'.
65' 64 6!» 62 »-80 ОП +62 »-65 ! 64 6!' ГИ 6З'.64' 6! - 82-62» 64 6!' 62'.63' 84' 50К О зейн О О О О ш ) о Ш ) 0 зг о 52 О ! о о о о о о О 0 0 0 О 0 55 О 5ОК и 5ЕПН О 52 54 О зок о зенн о О О! о о О О 0 0 0 О 0 0 О 0 О 0 0 О ) о о ! о 0 О О 0 О О 0 л о о о О О О 0 о о о о о о о 5! ) 5ОК 0 О ! О о ) о О ! О 5ЕЯН О 5ОК О 5! 5ЕНЛ О з! 54 зок О О О 0 О о о о о о и о 0 0 0 О зок 0 О 0 О В совокупности выведенные здесь соотношения имеют примерно такую же сложность, как и уравнения переходов и уравнения выхода, получаемые из табл.
7.18. И хотя в данном примере кодирование состояний выходными комбинациямии не приводит к более простому набору соотношений, все же при проектировании на основе ПЛУ можно сэкономить в стоимости, так как в целом оказываются необходимыми меньшее число макроячеек ПЛУ или выходов. Уравнения выхода, естественно, отсутствуют. Самым плохим из приведенных яв- ляется выражение для Ейй*; ему требуется 1б термов независимо от того, в каком минимальном виде оно представлено: в виде суммы произведений или в виде произведения сумм, 7.7. Другой пример проектирования конечного автомата 699 7.7.4.
Кодирование «безразличных» состояний Состояние Г. т 1.2 (.3 (.4 Ейй 1 х 0 1 0 0 О О О О 0 0 х х х х 83 84 8ОК 8Ейй 1 х 0 0 0 О О При таком подходе каждое неиспользуемое текущее состояние подобно ближайшему «нормальному» состоянию; эту идею иллюстрирует рис. 7.67, Ничего плохого не произойдет с автоматом, если он нечаянно попадет в неиспользуемое состояние; он перейдет в «нормальное состояние».
Вместе с тем, этот подход приволит к дальнейшему упрощению логики возбуждения и логики выхода благодаря введению символов безразличия в список переходов. При записи р-герма перехода, соответствующего данной строке, те переменные состояния, значения котоРых в текущем состоянии отмечены как безрахчичные, опускаются; например, Ейй' =11 (02+ 03+04) +11' 1.2 (01+03+04) + 1 1' 1.2' 1 3 (О1 + 02 +04) +(Л' 1.2'. 1.3'. 14. (01+ 02+ 03) + (.Г 02' 13'. Ь4' Ейй (О1 + 02+ 03+ 04). Сравнивая это выражение с выражением, полученным для Ейй" в предыдущем разделе, мы видим, что при представлении этого состояния в виде суммы произведений оно по-прежнему содержит 1б термов. Однако в виде минимального произведения Нз 32 возможных кодов состояний при пяти переменных в табл.
7.19 использу,тся только шесть. Остальные состояния являются неиспользуемыми, и следу, шим за ними состоянием будет состояние 00000, если автомат построен по уравнениям, приведенным в предыдущем разделе. Аккуратное использование соображений «безразличия» при отнесении кодов к текущим состояниям позволяет иначе распределить неиспользуемые состояния, нежели это было сделано нами в предыдущем разделе, В табл.
7.20 представлено одно из таких соответствий в автомате для игры на угадывание при кодировании состояний выходными комбинациями, о котором говорилось. В этом примере текущему состоянию с данным именем соответствует нескол ько возможных комбинаций переменных состояния (например: 10! 11 =- 81, 00101 =- 83). Однако следующему сосшолишо присваивается одна вполне определенная комбинация, как и в предыдущем разделе. В результате мы получаем список переходов, приведенный в табл. 7.21.
Табл. 7.20. Кодирование текущих состояний в автомате для игры на угадывание прн безразличном отношении к некоторым комбинациям выходных сигналов 700 Глава 7. Принципы проектирования последовательностных схем Текущее состояние Выражение перехода Следуклцее состояние а< с1 сг* сз 04* енл 32 О ) О О <. 61' 62' 83' 84' 06К О О О О О БЕПР О О О О ! С 62 ЬЗ' 84 6" < 83 <84 81' ог' оз' 84' 61' 82 83' 84' С1 — 6З 64 61' 82' 83' 64' 61' 62' СЗ 64. 61-62< 64 61' 62' СХ 64' 8 ог' оз' 84 6 462+63 6; 82 63464 81' 62 63' 64' 6! 62 63 -84 61' 62' 63' 64' ! «< ! < л 0 ! < О О 1 О л зск о о ! о ЗЬРП О О О О Нг 0 ! «< ! О О О О 1 ') О О О О 3 О О 1 о о о О О О ! О БОК О О О О О БЕЛО О О 0 0 О О О О БСК О О О 0 БЕРН О О О О БОК ) О О О и ВСК О О О О еск о о о ) о ЕЕНР О О о О БЕРЯ О О О О ! о о о о БЕЛЧ 0 О 0 О ! о о о о Кодовые имена СЛ)ЕДУЮНО)Х СОС)ОЯННй И))довые имена текущих состонннй Рис. 7.67.
кодирование состояний при безразличном отношении к некото- рым комбинациям выходных сигналов сумм ему тРебуется всею пять термов, благодаря чему прн реализации автомата на основе ПЛУ оказывается более удобным формировать дополнение к Ег)йн. Табл. 7.21. Список переходов автомата для игры на угадывание при безраз- личном отношении к некоторым комбинациям выходных сигналов 7.8.
Разбиение конечных автоматов на блоки 701 *7.8. Разбиение конечных автоматов на блоки Точно так же, как обстоит дело с большими процедурами и подпрограммами при программировании на языках высокою уровня, большие конечные автоматы трудно у о удерживать в сознании, проектировать и отлаживать. Поэтому, сталкиваясь с задачей, в которой речь идет о большом конечном автомате, разработчики цифрово овой техники часто ищут возможности решить проблему с помощью совокупности меньших по размерам конечных автоматов. Существует развитая теория разбиения конечных автачатов на блокк (тагетас)ггпе йесотрагдюп), позволяющая проанализировать любой заданный как единое целое конечный автомат на предмет возможности реализации его в виде совокупности меньших конечных автоматов.
Однако теория разбиения на блоки не так уж полезна для тех, кто хотел бы вообще избежать проектирования больших конечных автоматов. Опытный разработчик скорее постарается представить требуемую консзрукцию в виде упорядоченной иерархической структуры, в которой назначение и функции подавтоматов были бы очевидными, так что отпала бы необходимость составлять таблицу состояний для эквивалентного большого автомата в целом. Простейший и чаше всего используемый тип разбиения на блоки представлен на рис. 7.68.
Главный автаиат (тагп тас7гте) с основными входами и выходами исполняет управляющий алгоритм верхнего уровня. Подавтоматы (липтасlппел) под контролем главного автомата выполняют шаги нижнего уровня и могут, в частности, обрабатывать сигналы на отдельных входах и выходах из числа основных. Входы Выходы Рис. 7.68. Типичная иерархическая структура конечного автомата. Роль подавтомата очень часто играет счетчик, Главный автомат запускает счетчик, когда нужно, чтобы автомат оставался в некотором частном состоянии в течение п периодов талтового сигнала; на п-м такте счетчик выдает сигнал ООГчЕ. Главный автомат спроектирован так, что он ждет, пребывая в одном и том же состоянии, пока не поступит сигнал ООМЕ. Для этого главному автомату нужны лополнительные выход и вход (ЯТАГЗТ и ООМЕ), но зато экономится п — ! состояние. 702 Глава 7. Принципы проектирования поспедоввтепьностных схем В качестве примера реализации этих идей осуществим разбиение на блоки конечного автомата для игры на угадывание из параграфа 7.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
