Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 151
Текст из файла (страница 151)
7.4. Проектирование тактируемых синхронных конечных автоматов 677 РЕШЕНИЕ МИНИМАЛЬНОЙ СТОИМОСТИ В нашем примере карты возбуждения при выборе стратегии минимальной стоимости составить немного легче, поскольку во всех местах в таблице переходов, где должны быть указаны состояния, следующие за неиспользуемыми, можно просто поставить символ безразличия "г!". Уравнения возбуждения с правыми частями вида «сумма произведений», следующие из (не приведенных) карт минимальной стоимости имеют вид.
К1 = О К2=ОЗ'.А В'+С!З А' В' КЗ = А'. ,)1=1 42=01 ОЗ' А'+ОЗ А ЗЗ=А Кодирование состояний при использовании дК-триггеров то же самое, что и в случае й-триггеров, так что уравнения выхода такие же как для минимального риска (2 = О1 О2), так и для минимальной стоимости (2 = О2). ! !ринципиальная схема, реализующая уравнение минимальной стоимости, представлена на рис. 7.56. В этой схеме на два вентиля больше, чем в схеме минимальной стоимости на 0-триггерах, приведенной на рис.
7.54, из чего следует, что ЗК-триггеры так ничего нам и не сэкономили. лезет с ськ рис 7.66. Принципиальная схема рассматриваемого в качестве примера ко- нечного автомата на 4К-триггерах с логикой возбуждения минимальной сто- имости 7.4.6. Дальнейшие примеры проектирования на основе 0-триггеров В заключение этого параграфа приведем еще два примера проектирования конечных автоматов на основе О-триггеров, Первый пример -- это кавтомат, считающийй число единицы 678 Глава 7. Принципы проектирования последовательностных схем Построить тактируемый синхронный конечный автомат с двумя входами Х и у и одним выходом Е, Выходной сигнал должен равняться 1, если число ели- ниц, поступивших на входы Х и ус момента запуска, кратно 4; в пРотивном случае сигнал на выходе должен равняться О. С первого взгляда может показаться, что этому автомату понадобится бесконечное число состояний, коль скоро подсчет числа единиц на входах продолжается неограниченно долго.
Но выходной сигнал должен указывать число принятых единиц ломодулю 4, поэтому будет достаточно четырех состояний. Назовем их 80-83, где 80 — начальное состояние, а полное число принятых единиц, когда автомат находится в состоянии 80 равно ( по модулю 4. В результате получаем таблицу состояний и значений выходного сигнала, приведенную в табл. 7.12.
Табл. 7.12. Таблица состояний и значений выходного сигнала для автомата, считающего единицы. З 00 01 11 10 2 Принято 0 единиц (по модулю 4) 80 Принята 1 единица (по модулю 4) 81 Принято 2 единицы (по модулю 4) 82 Принято 3 единицы (по модулю 4) 83 81 82 81 82 83 82 83 80 83 80 81 80 80 81 82 83 Для кодирования четырех состояний автомата, считающего единицы, можно воспользоваться двумя переменными состояния и при этом неиспользуемых состояний не будет.
В таком случае имеется только 4! возможных способов присвоить состояниям с именами те или иные кодовые комбинации. И все же мы выберем из них только один и вполне определенный. Мы установим соответствие между состояниями с именами и кодами состояний в том порядке, какой принят на картах Карно (ОО, 01, 11, 10), по двум причинам: во-первых, при заданной таблице состояний это минимизирует число изменяющихся переменных состояния в большинстве переходов, потенциально упрощая тем самым уравнения возбуждения; во-вторых, это упростит механический перенос информации в карты возбуждения.
При выбранном способе кодирования состояний таблица «переходГвозбужденне» имеет вид, указанный в табл. 7.13. Поскольку мы используем ()-триггеры, таблицы переходов и возбуждения одинаковы. Соответствующие карты Карно для сигналов Р1 и 02 показаны парис. 7 57. Так как неиспользуемых состояний нет, вся нужная нам информация содержится в таблице возбуждения и не нужно выбирать между минимальным риском и минимальной стоимостью. Уравнения возбуждения можно записать, гляля на каРты а уравнение выхода непосредственно вытекает из таблицы «переход/возбуждение»: 7.4.
Проектирование тактируемых синхронных конечных автоматов 679 Р! = С!2 Х' У+ а1' Х У+С!1 Х'.У" +а2 Х У' Р2 = С!1'. Х' У+ С!1' Х У'+ С!2 Х' У'+ Р2' Х У 2 = 01' О2'. Табл. 7.13. Таблица «переход/воз- буждение» и значения выходного сигнала для автомата, считающего единицы ХУ О1 О2 00 01 11 10 00 00 О! 1! О! О! 11 !О !1 !1 !О 00 !!! 10 00 01 00 01 !1 !О 01 С!2" ог Р1 Р2 Р!' Х'. Х а!аг Х 01 01 [ 10 10 01 Х'.У' 02 Х' У' 7.57. Карты возбуждения для входных сигналов Р1 и Р2 в автомате, считающем единицы Второй пример — конечный автомат, управляющий кодовым замком: автомат выдает сигнал «открыть», когда ему на вход поступает определенная двоичная комбинация: Построить тактируемый синхронный конечный автомат с одним входом Х и двумя выходами РИ~К и Н!ИТ.
Выходной сигнал РИ!.К должен равняться 1 в том и только в том случае, когда Х равно О, а в предшествующие семь тактов на вход Х поступила последовательность 0110111. Выходной сигнал Н!ИТ должен равняться 1 тогда и только тогда, когда текущее значение Х является правильным с точки зрения продвижения автомата в сторону «открытого» состояния (то есть состояния с РИСК = 1). По этим уравнениям можно составить принципиальную схему на Р-триггерах с логикой возбуждения на структурах И-ИЛИ или И-НЕ-И-НЕ. ВВО Глввв г. Принципы проектирования послвдоввтвльиостиых схем Табл.
7.14. Таблица состояний и значений выходных сигналов для автомата, управляющего кодовым замком "Счет не открыт" А Принято 0 В Принято 01 С Принято 011 0 В,01 А,ОО В,ОО С,О! В„ОО О, 01 Е,01 А,ОО В,ОО ЕО! В,ОО 6.0! Е,ОО Н,О1 В. 11 А. 00 Принято 0110 Е Принято 01101 Е Принято 011011 6 Принято 0110111 Н Вч. 1!Й1 К Н1НТ Восемь состояний кодового замка можно представить тремя переменными состояния; неиспользуемых состояний при этом не будет. Соответствие между состояниями с именами и двоичными комбинациями можно выбрать 8! способами. Чтобы не усложнять себе жизнь, воспользуемся простейшим способом кодирования и назначим состояниям А-Н кодовые комбинации в порядке двоичного Из словесного описания очевидно, что речь идет об автомате Мили.
Значение выходного сигнала 0ыьК зависит как от предыстории входных воздействий, так и от текущего значения х, и сигнал н1ыт зависит от состояния и от того, что действует иа входе (в самом деле, если текущее значение входного сигнала Х таково, что НОЧТ = О, то знающий селрет пользователь захочет изменить значение Х до наступления очередного такта). Таблица состояний и значений выходных сигналов для кодового замка представлена в табл.
7. 14. Предполагается, что в начальном состоянии А не принято никакой части требуемой входной последовательности; автомат ждет прихода первого 0 последовательности. Поэтому он остается всостоянии А втечение всего времени, пока на вход поступают единицьг, и переходит в состояние В, когда принят О. Находясь в состоянии В, автомат ждет прихода 1. Если поступает именно она, то автомат переходит в состояние С; если нет, то должен оставаться в состоянии В, поскольку талько что принятый 0 может оказаться первым нулем требуемой последовательности.
Пребывая в каждом следующем состоянии, автомат будет переходить дальше, если на вход поступает правильный сигнал, и возвращаться в состояния А или В в случае прихода неправильного сигнала. Исключением является состояние Ей если автомат находится в этом состоянии и на вход поступает неправильное значение сигнала (0), то предыдущие три входных сигнала все же могут оказаться первыми тремя битами требуемой последовательности, так что автомагу надо возвращаться в состояние Е, а не в состояние В.
Попав в состояние Н, когда принята требуемая последовательность, автомат выдает 1 на выходе О!Ч!.К, если Х будет равен О. В каждом состоянии вырабатывается единичное значение сигнала Н1!ЧТ, если значение Х таково, что оно продвигает нас ближе к состоянию Н. 7.4. Проектирование тактируемых синхронных конечных автоматов 681 счета, что приведет к таблице «переход(возбуждение», приведенной в табл. 7.15. Соответствующие карты Карно для сигналов 01, 02 и 03 показаны на рис.
7,53, Иепосредственно из этих карт получаем уравнения возбуждения: 01 = 01 02'. Х+ 01' 02 ОЗ Х' О О! . 02 ОЗ' 02 = 02'. 03 Х+ 02 03' Х 03 =О! 02' ОЗ'+01. ОЗ Х'+02' Х'+03'. 01' Х'+02 03' Х Значения выходных сигналов переносим из таблицы «переход/возбуждение» в другой набор карт (рис. 7.59). Соответствующие уравнения выхода имеют вид: 0)Ч) К = 01 02 . ОЗ Х' Н)ЫТ=О(' 02' 03' Х'+01 02' Х+02' ОЗ К+02 Оз Х'+02 ОЗ' Х Заметьте, что в уравнениях возбуждения и в уравнениях выхода есть повторяющиеся термы, что лает возможность немного сэкономить на стоимости реализации логики И вЂ” ИЛИ. Если бы мы преодолели трудности формальной одновременной минимизации нескольких логических функций в отношении всех пяти функций возбуждения и выхода, то мы могли бы сэкономить еще два вентиля (см, задачу 7.55). Табл.
7.15. Таблица «переход/ возбуждение» для автомата, управляющего кодовым замком 01 02 х 01 Х Х01 02 ОЗ ОО О! 11 10 02' ОЗ. 01. 02 ОЗ~ ага оо аг х 02 01" 02 ОЗ.Х' 01.02 ОЗ' огоз х О!' ОЗ'-Х' 02 ОЗ' Х 01, 02 и 03 в автомате, управ- Рис. 7.58. Карты возбуждения для сигналов ляющем кодовым замком ООО 001 010 01! 100 10) 110 ()1 001, 01 (ХХ), (Х) 001,00 О!0,01 001. ОО 011. О! !00,0! 000. 00 00),00 )Е,О! 001,00 !10,01 !(Х),00 111, 01 001, 11 000. 00 О!»02*03*, О!»).К Н!)ЧТ 682 Глава 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
