Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 148
Текст из файла (страница 148)
Бывают также такие ситуации, когдаунб«!ичение числа состояний может упростить конструкцию или уменьшить ее стоимость; в таких случаях даже нет необходимости прибегать к помощи автоматизированной процедуры минимизации числа состояний. Разработчик может больше сделать для упрощения конечного автомата на этапе представления состояний в двоичной записи, о чем идет речь в разделе 7.4,3, 7.4.2. Минимизация числа состояний Опас е 5 На итсе састонние Мт На А бнп б Ас не А бина! т НаАбтооб Оксо На д бина 11 Ока! Напбипобо1,5=1 НО! НаАбина 110, В=1 м1о наАспноьь !б,б=пде10 напсипссь б! В=! пес! НЕУЖЕЛИ ВСЕ ЭТО НУЖНО НА САМОМ ДЕЛЕ? м до ап Ок!на Окоп л Дс М Ока! Скос ОКСО АОО1 Яо А!10 ОК11 АО АЕ!О ОК11 Оксо Оксо аеоп ОКСО ОКСО АЕО1 Ао ЯЕ!с ОК11 5 ктнроввние твктнруемых синхронных конечных автоматов 666 7.4.
ПРое (1 меняя формальную процедуру минимизации числа состояний к таблице Примен состояний, нй лРиведенной на Рис. 7.51(а), мы видим, что состоЯниЯ ОКОО и ОКА0 валентиы, пес«ель у в этих со ояниях вырабаты ается одно и тоже значение эквивалентиь, выходногос ного сигнала и их множества следующих состояний тождественны, Так как эти состоя остояния эквиваленты, состояние ОКОО можно исключить, а там, где оно встречается ечается в таблице, заменить его состоянием ОКА0; можно поступить и наобо- рот. пал Аналогично, эквивалентными являются состояния ОК11 и ОКА1.
Чтобы минимизировать таблицу состояний, приведенную на рис. 7.51(Ь), в рам- ках фор ах формальной процедуры придется прибегнуть к рассуждениям, носящим отча- сти цикл~ тн циклический характер. Находясь в состояниях ОКОО, А110 и АЕ10, автомат вырабатывает один и тот же сигнал и в качестве еледуюгцих состояний имеет почти „дентичные множества состояний, так что эти три состояния могли бы быть экви- валентными. Они строго эквивалентны только в том случае, если эквивалентны состояния А011 н АЕ01. Аналогично, состояния ОК11,А001 и АЕ01 эквивалентны только тогда, когда эквивалентны А110 и АЕ10. Другими словами, состояния, входя- щие в первый набор, эквивалентны, если эквивалентны состояния, входящие во второй набор, и наоборот. Так вот, давайте двигаться вперед, приняв, что они экви- валентны.
7.4.3.1ьодированиесостояний Следующий шаг в процессе проектирования состоит в определении того, сколько требуется двоичных переменных для представления состояний в таблице состояний, и в распределении двоичных комбинаций между состояниями с теми нли иными именами. Мы будем называть двоичную комбинацию, присвоенную конкретному состоянию, кодом состояния (сог7ей маге). 1!олное число состояний (гоги! питдег о7' лгшел) автомата с и триггерами равно 2", так что число триггеров, необходимое для кодирования л состояний, равно ~1од, л1, то есть наименьшему целому числу, большему, чем!оя, л, илн равному этой величине. Ради удобства, в табл. 7.6 вновь воспроизведена таблица «состояние!выход» лля автомата, рассматриваемого в качестве примера.
у него пять состояний, так что ему требуется три триггера. Конечно, у трех триггеров полное число состояний равно восьми, поэтому в данном случае 3 из них являются неиспользуемыми состояниями (ипилег(мигел). Мы рассмотрим альтернативные варианты обращения с неиспользуемыми состояниями в конце этого раздела. А сейчас нам нужно разобраться с массой возможностей„возникающих при выборе способа кодирования состояний. НАЧАЛЬНОЕ СОСТОЯНИЕ И СОСТОЯНИЕ НЕЗАНЯТОСТИ Конечный автомат, рассматриваемый в этом разделе в качестве примера, попадает в начальное состояние только при запуске, тогда как многие автоматы "роектируются таким образом, чтобы у них было «состояние незанятости» ( нйе ' шаге), в которое автомат попадал бы как лри запуске, так и во всех тех ~дунаях, когда он ничего не должен делать.
666 Глава 7. Принципы проектирования последовательностных схем Табл. 7.6. Таблица состояний и значений выходного сигнала в З Оп 01 11 10 ~ рассматриваемом примере МТ Аа АО А1 А1 О АО ОКО ОКО А1 А1 0 А1 АО АО ОК1 ОК1 О ОКО ОКО ОКО ОК1 А1 ОК1 АО ОКО ОК1 ОК1 ЯФ Простейший способ назначения з кодов состояний из 2' возможных двоичных комбинаций заключается в использовании первых я целых двоичных чисел в порядке двоичного счета, как это сделано в левом столбце назначаемых кодов состояний в табл 7.7.
Однако простейн~ий способ назначения не всегда приводит к простейшим уравнениям возбуждения и уравнениям выхода, и, следовательно, к наиболее простой принципиальной схеме, Действительно, назначение состояний часто существенно влияет на стоимость схемы и может быть тесно связано с другими факторами, такими как выбор элементов памяти (например, О-триггеры или ОК-трнперы) и подход к реализации логики возбуждения и логики выхода (например, в виде «суммы произведений», «произведения сумм» или в каком-то частном виде применительно к данному проекту).
МАТЕМАТИКА ПРЕДОСТЕРЕГАЕТ Число различных способов, которыми можно выбрать и кодов состояний из п возможных кодовых комбинаций, задается бинолинольныи коэффиииен- гн н н! таи ~ш), Равным,, 1Мы Уже встРечались с биномиальными коэффициентами в параграфе 2.10 в связи с кодированием десятичных чисел.) В 181 нашем примере имеется 15) различных способов выбора пяти кодов состояний из восьми возможных, и при каждом таком выборе существует 5! способов распределения пяти состояний с именалзи по выбранным двоичным 8! комбинациям. Таким образом, мы можем — 5!=6720 способами устано- 5131 вить соответствие между пятью состояниями нашего автомата и комбинациями из трех двоичных переменных состояния.
Нам не хватит времени перебрать все способы. 7.4. Проектирование тактируемых синхронных конечных автоматов 667 Имя Простейшее С разбиением Прямое состояния 05-03 01-03 01-05 Почти прямое 01-04 000 100 101 110 111 00001 00010 00100 01000 ! 0000 000 001 010 О!! 100 0000 0001 0010 0100 1000 1М1Т АО А1 ОКО ОК1 Спрашивается: как же наилучшим образом выбрать кодирование состояний в данной задаче? В общем случае единственный способ найти лучшее кодирование состоит в том, чтобы перепробовать все варианты кодирования. Это, конечно, ели шком большая работа даже для студента.
Вместо этого большинство разработчиков цифровой техники полагается на свой опыт и руководствуются несколькими практическими принципами при выборе разум ного способа кодирования: Код начального состояния выбирается таким образом, чтобы автомат можно было легко установить в это состояние при запуске (в типичных схемах это 00...00 или 1! ...11). Минимизируется число переменных состояния, которые изменяются на каждом переходе. Максимизируется число переменных состояния, которые не изменяются в пределах ~руппы связанных друг с другом состояний (тоесть в пределах такой группы состояний, для которой большинство переходов не выводит за пределы этой группы).
Используется симметрия в условиях задачи и соответствующая ей симметрия в таблице состояний. Другими словами, предполагается, что одно состояние или группа состояний означают почти то же самое, что н другое состояние или группа. После назначения кода состояния первому из сопоставляемых по принципу симметрии состояний, подобное же назначение следует произвести и в отношении второго состояния, изменив лишь один бит. Если существуют неиспользуемые состояния (тоесть если в < 2", п= ~!ой з !), то выбираются влучшиев из имеющихся комбинаций переменных состояния для достижения упомянутых выше целей. Из этого следует, что, как правило, не останавливаются на выборе в качестве кодов состояний з первых л-разрядных целых чисел.
Множество переменных состояния разбивают на отдельные биты или поля таким образом, чтобы каждый бит нли поле имели определенное значение в смысле воздействия входных сигналов или поведения автомата со стороны выхода. 7абл. 7.7. Возможные способы кодирования состояний в случае автомата, описываемого табл. 7 6 668 Глава 7. Принципы проектирования последовательностных схем ° Рассмазриваются варианты с использованием большего числа переменных состояния, нежели минимальное, с тем чтобы оказалось возможным кодирование с разбиением.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
