Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 153
Текст из файла (страница 153)
а коды используются при составлении уравнений переходов Табл. 7.17. Список переходов для конечного автомата, управляющего зад- ними огнями автомобиля марки Гог(( Типо()егщг(( 3 а2 ат ао В рере дв 9* а2 а(~ аО. (ОЬЕ 0 0 0 ((.ЕРТ ВЮНТ - НА2)' !0(.Е и О 0 1 Г(З 1.63 10 ~Е 0 0 0 г(2 ! 1 1 1 0 0 1 1 0 О О 0 и (.(зЗ (13 1. (зЗ !(ЗЕЕ 10(.Е 0 О 0 После того как список переходов составлен, оставшаяся часть синтеза представляет собой рутинную работу довольно большого объема Процедурам син- 10(.Е 0 О 0 !.ЕРТ НАЛ' ГНСНТ' 1 ! !ОЬЕ 0 И и НА2 ( (.ЕРТ Г(!ОНТ ЬГ(3 101 Е 0 О 0 В(УНТ НА2' (,ЕРТ' !(! !.! 0 0 1 НА2' (! 0 0 1 НАЛ 'ь2 О 1 1 НАЛ' 12 0 1 ! НАЛ '3 0 ! О Я! 1 0 1 НА2 ))! 1 0 1 НА2 Н2 1 1 ! НА2' (!2 ! 1 ! НА2 ()3 1 1 0 ЫЗ 1 0 0 ! 0 0 ! 1 0 0 ! 0 О 1 1 1 0 0 0 1 О 1 0 0 690 Глава 7.
Принципы проектирования последовательностных схем теза посвящен параграф 7.6. Хотя эти процедуры можно реализовать вручную, они обычно бывают включены в пакет программ системы автоматизиРованного проектирования (системы САП); таким образом, параграф 7.б может помочь вам разобраться с тем, что делает (или в чем ошибается) ваш любимый программный продукт. Мы уже столкнулись в этом параграфе с одним таким рутинным шагом — с поиском неоднозначности в диаграммах состояний.
Хотя рассмотренную нами процедуру нетрудно автоматизировать, почти никакие программы систем САП этого не делают. Например, одна из программ «ввода диаграмм состояний» молча удаляет повторяющиеся переходы и в случае пропуска переходов указывает переход в состояние с кодовым именем "00...00", не выдавая пользователю предостережений. Таким образом, прибегая к помощи тех или иных средств проектирования, разработчик в большинстве случаев сам несет ответствен ность за однозначность в описании конечного автомата.
Хороним подспорьем в этом служат языки описания конечных автоматов, о которых идет речь в конце этой главы. *7.6. Синтез конечных автоматов на основе списка переходов Построением диаграммы состояний автомата и выбором способа кодирования, по существу, исчерпывается творческая часть процесса проектирования. Остальную часть процедуры синтеза можно выполнить с помощью программ системы САП.
Как показано в предыдущем параграфе список переходов составляется по диаграмме состояний автомата с учетом выбранных кодов состояний. В этом параграфе мы продемонстрируем, как по списку переходов синтезируется сам конечный автомат. Подробно рассматривается ряд возможностей и нюансов, возникающих при проектировании конечного автомата на основе списка переходов. Хотя материал этого параграфа и полезен для синтезирования автоматов вручную, его главное назначение — помочь вам понять логику работы и возможные капризы программ и языков, используемых в системах САП при конструировании конечных автоматов.
*7.6.1. Уравнения переходов Первый шаг при синтезе конечного автомата по списку переходов заключается в выводе системы уравнений переходов, которыми задаются следующие значения 'ч'* всех переменных состояния как функции текущего состояния и входного воздействия, Список переходов можно считать своего рода гибридной таблицей истинности, в которой комбинацил переменных состояния перечислены явно, а комбинации входных сигналов приведены в алгебраической форме. Двигаясь сверху вниз по столбцу Ч* в списке переходов, мы получаем последовательность нулей и единиц, то есть значений Ч* для различных комбинаций состояние/вход (прн условии, конечно, что мы все записали в списке переходов правильно).
Выражение для следующего значения переменной состояния Ч* в уравнении переходов может быть разновидностью гибридной канонической суммы: Т б. Синтез конечных автоматов на основе списка переходов 691 Х (р-терм перехода). ио всем строкам списка переколов, в которых Чк =- 1 другими словами, в уравнение переходов входит по одному «р-терму перехода» на каждую строку списка переходов, содержащую 1 в столбце Ч*. р-терм пере„од«(ггапийоп р-гегьт) данной строки — это произведение минтерма текущего состояния и выражения перехода.
Согласно списку переходов в табл. 7.17 уравнение переходов для переменной 02* автомата, управляющего задними огнями автомобиля марки Гого ТЬ«пг(егбйп), можно записать в виде суммы, состоящей из восьми р-термов: 02* =02'.01'.00' (НА2+ ЬЕРТ й!ОНТ) + 02'. 01'. О(У (й(ОНТ НАЛ' СЕЕТ') т02'. 01' 00 (НА2) +02' 01 ОО (НАЛ) +02 01' 00 (НА2') + 02 01' 00 (НА2) +02 01 00 (НА2') +02 01 00 (НА2). Непосредственными алгебраическими преобразованиями это соотношение упрощается в результате обьединения первых двух, следующих двух и последних четырех р-термов: 02* = 02' 01'.
00' (НА2+ й)ОНТ) +02' 00 (НА2) + 02 ОО. Аналогично могут быть получены уравнения переходов для 01 «и 00«: О1* =02' 01' 00' (НА2') +02' 01 00 (НА2') + 02. 01' 00 (НА2') +02 01 ОО (НА2') =ОО НАЛ' СЮ* =02' 01' ОО' (1.ЕГТ НА2' ВАНТ') +02' 01'.00' (й(ОНТ НАЛ' 1.ЕРТ') -Ог 01 .О() (НА2) + 02 С)1' 00. (НА2') =02' 01' НА2'(~ЕЕТЮй)ОНТ)+01' ОО НА2'. За исключением переменной 01*, нет никаких гарантий, что найденные соотношения для переходов являются в том или ином смысле минимальными: действительноо, выражения для 02* и О()* не имеют даже стандартного вида «суммы произведений» или «произведения сумм». упрощенные или неу прощенные уравнения служат лишь четло сформулированной отправной точкой, чтобы можно оыло выбрать какой-нибудь комбинационный метод синтеза логики возбуждения в конечном автомате: на основе структуры И-НЕ-И-НЕ, на ИС средней степени интеграции или как-то еше.
При разработке на основе ПЛУ вы могли бы просто вставить эти уравнения в программу на языке АВЕ(. и велеть компьютеру найти 692 Глава т. Принципы проектирования последовательнсстных схем минимальные выражения вида «сумма произведений» лля реализации на решетке И-ИЛИ в ПЛУ. *7.6.2. Уравнения возбуждения Несмотря на то, что мы уже подошли к логике возбуждения, до сих пор нами выведены только уровиеяил переходов, но не уровттонил возбуждения.
Однако в случае, когда в качестве элементов памяти в наших конечных автоматах применяются 0-триггеры, уравнения возбуждения являются тривиальным следствием уравнений переходов, поскольку характеристическоеуравнение 0-триггера имеет вид: О* = О. Поэтому из уравнения переходов для переменной состояния 0)* О(* = выражение получаем следующее уравнение возбуждения для сигнала на входе соответству- ющего 0-триггера: О! = выражение.
Рациональные уравнения возбуждения для триггеров других типов, особенно для ,) К-триггеров, выводятся не так легко (ем. задачу 7,63). По этой причине в подавляющем большинстве случаев в конечных автоматах, создаваемых на дискретных компонентах, на основе ПЛУ или специализированных ИС, используются 0-триггеры. *7.6.3. Варианты схем Существуют и другие способы получения уравнений переходов и уравнений возбуждения из списка переходов. Если столбец со следующими значениями какойто одной переменной состояния содержит меньше нулей, чем единиц, то имеет смысл записать уравнение переходов для этой переменной в терминах нулей в этом столбце: Х (р-терм перехода). по всем сорокам списка переходов, в которых Н* = О Другими словами, Ув' равно! для всех р-термов, для которых Ув равно О.
Следовательно, уравнения переходов для 02*' можно записать в виде суммы, состоящей из семи р-термов: 02*' = 02' Ч 01' 00' (((ЕРТ+ й!ОНТ+НА2)') е 02' 01' 00' (АЛЕЕТ НА2' Н)ОНТ') +02'. 01' 00. (НА2') + 02'. 01 00 (НА2') +02' 01 00' (1) +02 01 00' (1) +02 01' 00' (1) =02' 01' 00' НА2' (Ч!ОНТ'«02' 00 НА2'вО! 00'+02 00'. Чтобы придти к уравнению для 02», достаточно просто взять дополнения обвит частей последнего, свернутого равенства. г.7. Другой пример проектирования конечного автомата 693 Выражение для следующего значения переменной состояния Ч* можно получить из нулей в списке переходов непосредственно, беря дополнение правой части общего выражения для Ч", тогда на основании теоремы Де Моргана приходим к разновидности гибридного канонического произведения: п (з-терм перехода).
по вссы строкам списка переходов, в кокорев Ч' = О Здесь з-т«рм перехода гггапзггвоп з-геггп) данной строки — это сумма макстерма текущего состояния и дополнения выражения перехода. Если выражение перехода является простым термом-произведением, то его дополнение есть сумма, и поэтому переменная Ч' в уравнении переходов представляется в виде произведения сумм. *7.6.4. Реализация конечного автомата После того как уравнения возбуждения для конечного автомата получены, все, что нам остается, — это решить задачу построения комбинационной логики с несколькими выходами.
Конечно, реализовать комбинационную логику, представленную уравнениями, можно многими способами, но простейший из них состоит в том, чтобы набрать соответствующую программу на языке АВЕЕ или ЧИПА и воспользоваться компилятором для синтеза схемы в ПЛУ, в ИС типа ГРПА или в специализированной ИС.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
