Пример построения автома- та Мили по МСА с миними- зацией числа состояний

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пусть ОУ имеет вид:

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

p1p2 = 11 задает алгоритм А1.

p1p2 = 10 задает алгоритм А2.

p1p2 = 00 задает ожидание инициирова-

337 ния работы (алгоритм А3).

Влияние микроопераций на значение x таково:

y1,y2 - не меняет x

y3 - устанавливает x любым

y4 - устанавливает x = 1

Значения p1p2 не меняются во время ра- боты УА по частному алгоритму.

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

           
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru   Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru
 
   
Частные МСА
 

кк
К6
К5
К4
К3
К1
ОМСА

К2  

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

p1p2 p1p2x p1p2x p1p2 p1p2 p1p2 p1p2;p1p2 p1p2 p1p2 p1p2
Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru
Кнн

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

К1

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

К2

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

К3

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

К4

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

К5

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

К6

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

p1p2 p1p2 p1 p1p2x p1p2x p1p2
j

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

p1p2 p1p2x p1 p1p2x p1p2x p1p2
y
341

Полученные yi подставляем в МСА, что дает:

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Повторные получения yi и их подстанов-

ки дают такую же МСА и процесс уточ- нения заканчивается.

По этой МСА строим автомат, отмечая

как S0 Кн, Кк, а также К3 и К6, так как от них есть переход только к Кк (См. 3.9).

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

После минимизации имеем

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Упростив условия переходов, получаем

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Синтез схем МПА

Схемы с дешифраци- ей состояний.

См. методическое пособие

Каган Б.М., Першеев В.Г. "Синтез МПА",

раздел 2.

Будем строить схему по обратной структурной таблице (ОСТ) автомата, являющейся расшире-

нием ОТП и имеющей формат вида:

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

1 2 3 4 5 6 7

j - сигналы возбуждения ЭА.

Сначала из ОТП в ОСТ заносим содер-

жимое колонок 1,3,4 и 6. Далее, закоди-

ровав состояния МПА, заполним колон-

ки 2 и 5 и в 7 заносим имена сигналов j, требующих единичного значения для обеспечения перехода из Sисх в Sпер (по матрицам переходов ЭА).

Затем выписываем для каждого имени из 6 и 7 условия их единичных значений, то- есть функ-ции выходов и возбуждения. При этом Sисх пред-ставляются своими именами, а не через состоя-ния ЭА.

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Далее строится схема вида:

Пример

Возьмем МПА из 3.14 и опишем ОСТ.

В качестве ЭА выберем триггеры типа D.

Состояния Q2Q1 00, 01, 10 примем для кодов S0, S1, S2.

ОСТ имеет вид

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Из ОСТ выписываем:

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Далее рассмотрим схему.

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Выделение как отдельной схемы дешифратора упрощает реализацию j и Y, так как в нем сконцентрированы общие повторяющиеся части конъюнкций (для кодов S) функций выходов и возбуждения.

МПА Мура строится аналогично. При этом

функцию выходов в ОСТ удобнее заносить

(а затем выписывать из ОСТ ), считая

аргументом для Y значение Sпер , что дает

более простую форму для записи Y = F(S).

Схема с дешифрацией состояний может упростится при неполной дешифрации

состояний.

При этом дешифрация идет только для

двух половин кодов состояния (как в прямоугольном дешифраторе).

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Для полного выделения состояния полу- чаются как конъюнкции сигналов с вы- ходов раздельных дешифраторов. Они реализуются в конъюнкторах КС для j
и Y, что мало влияет на их сложность.

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

 
Si¢
Si (Si= Si¢× Si¢¢)
Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Si¢¢

       
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru
    Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

(L+1) - вход

L - входов

Увеличение числа входов на 1 обычно мало влияет на цену.

Схемы с КС на базе

ПЛМ.

Сбф для КС МПА обычно состоят из большого числа бф, зависящих от боль- шого числа переменных, но эти сбф по-

чти всегда компактно представимы в ДНФ. (Число конъюнкций сбф не пре- вышает числа строк таблицы переходов МПА.)

Отсюда следует целесообразность ис- пользования БИС ПЛМ для КС МПА.

При такой реализации КС будет иметь входы Х ( логические условия), Р (иден- тификация частного алгоритма) и Q (сос-

тояния ЭА, представляющие состояния

МПА).

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Использование предварительной деши- фрации состояний здесь лишено смысла.

Дешифрация приведет к резкому увели-

чению числа входов КС (j , Y), а число конъюнкций в сбф останется тем же, что

только ужесточит требования к ПЛМ.

Сбф МПА обычно не удается реализо- вать в одной БИС ПЛМ. При этом син-
тез КС выполняется в условиях нехват-

ки конъюнкторов и выходов ПЛМ.

При разложении КС по нескольким

ПЛМ в условиях нехватки конъюнкто-
ров следует учитывать, что как прави-

ло выходы ПЛМ объединяются конъюн-

ктивно, что требует разбиения Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru или Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru .

В первом случае для Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru =j1 Ú j2 Ú...Ú jq имеем

       
    Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru
 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

369 Отсюда следует схема

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru yi могут быть получены либо по ДНФ Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru , либо инверсией ДНФ Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru на выходном инверторе ПЛМ.

Следует помнить , что реализуя Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru , мы обрабатываем (и соответственно выпи-

сываем как исходную) Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru .

Выражения для Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru использоваться нами

не будут.

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru В втором случае для Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru = j1 Ú j2 Ú...Ú jq имеем

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

372 Отсюда следует схема

           
 
  y1
    Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru
     
Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru
 
 

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

  yq
. . .
Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Как и ранее, yi могут быть получены либо как ДНФ Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru , либо как инверсия ДНФ Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru .

Использование дополнительного инвер- тора нежелательно, но иногда осущест- вляется разделение по Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru , а не по Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru , ес-

ли инверсия может быть получена без

затрат оборудования.

Это может быть, например, при реали- зации функций возбуждения D - триг- геров, имеющих инверсный выход .

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

КС на базе ПЛМ могут упрощаться

при специальном кодировании состоя-

ний МПА. Добиться этого можно так.

Сначала сбф КС рассматривается с

незакодированными состояниями.(Вмес-

то кодов состояний берутся их имена: S0 ,

S1, S2, ...)

Очень удобно при этом рассматривать сбф , представленные обратной струк- турной таблицей переходов.

Затем всюду, где это удастся, не простые импликанты заменяются простыми.

Например, пара строк таблицы

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

заменяется на одну

 
 
Six2Sjypyq  

Далее отбирается k конъюнкций для очередной формируемой ПЛМ (k - чис-

ло конъюнкторов ПЛМ). Рассматри-

ваются конъюнкции, отличающиеся

только именами входящих в них сос- тояний и являющиеся импликантами одних и тех же бф.

Для них выбираются коды состоя-

ний так, чтобы они давали склеива-

ние конъюнкций и соответственно

сокращение их числа. (Разрядность

кодов определяется по числу состоя-

ний.Сами коды можно выбирать про-

извольно, но не совпадающими с ра-

нее использованными.)

Например, имея

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

можно взять коды для Si, Sk, Se и Sm так, чтобы все конъюнкции склеились.

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Это в итоге даст строку таблицы

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

вместо четырех строк.

Если в результате выполненных дейст-

вий в ПЛМ появятся неиспользованные конъюнкторы, то к сбф ПЛМ добавля- ются новые конъюнкции, которые могут привести к фиксации новых кодов сос- тояний и т.д.

Кончив работать с очередной ПЛМ и зафиксировав часть кодов состояний, продолжаем такие же действия с ос- тальными ПЛМ, а в конце произволь- ным образом кодируем ранее незако-

дированные состояния.

Примечание

Исходное состояние S0 , как правило, получает нулевой код ввиду удобства
его начальной установки.

Нехватка входов ПЛМ возникает редко,

особенно с учетом того, что МПА с очень большим числом входов строятся особым

образом ( см.3.15.3).

В заключение отметим, что в КС для

МПА Мура иногда для реализации фу-

нкций выходов Y=F(S) используются не

ПЛМ, а ПЗУ (это может быть дешевле),

так как число аргументов этих бф неве-

лико (равно числу ЭА).

Схемы с

Мультиплексированием

Входных сигналов.

Для МПА характерно наличие неболь- шого числа разных условий (перемен- ных), проверяемых при переходе из

любого одного его состояния. Это поз- воляет строить КС МПА с мультиплек- сированием входных сигналов, что осо- бенно выгодно при большом числе вхо- дов.

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Каноническая реализация МПА имеет вид:

Мультиплексирование сокращает число входных переменных , идущих на КС j,Y

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Это позволяет достаточно просто реа-

лизовать КС на БИС ПЛМ и даже ПЗУ

при числе входов МПА, превышающем

число входов БИС.

Схема строится так. Определяется max числа входных переменных, использу- емых в условиях перехода в одном сос- тоянии МПА. Это число L задает коли- чество новых переменных Z1, ...ZL, кото- рые будут использоваться как входные

для КС j,Y.

Для получения соответствия между входными переменными и новыми переменными Z строится таблица соответствия вида:

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Для каждого Si задается соответствие между входными переменными и Z.

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример

Пусть L=5

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Z1 Z2 Z3 Z4 Z5
395

Задавая соответствия, нужно делать их одинаковыми для Si и Sj , если у них одинаковые заменяемые входные пере- менные. Кроме того желательно зано- сить переменные в те столбцы Z, в ко- торых эти переменные уже встречались. Это может упростить схему формиро- вания Z.

Пример

   
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru
 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Далее строки таблицы нумеруются чис-

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru лами (0¸R), которые записываются дво- ичными кодами длиной r = log2(R + 1) .

Таблица задает все варианты соответ- ствия между переменными в нумерован- ном виде, причем для каждого Si есть номер варианта. (У одинаковых строк одинаковые номера.)

Строим схему МПА вида

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Здесь КС R формирует по коду каждого состояния управляющий код, который задает номер варианта соответствия пе- ременных Х переменным Z. Соответ- ствие реализуется схемой из L мульти- плексоров с r управляющими входами.

На информационный вход Di мульти- плексора MSjподается переменная, ука-

занная в строке с номером i колонки Zj.

(Если там "-", можно подавать что угод-

но.)

Теперь на входах КС j,Y Z1, ... ZL при любом состоянии МПА будут значения Х, заданные таблицей соответствия. Отсюда вытекает спо-

соб описания КС j,Y.

Сначала получается описание так, как будто КС строится без мультиплекси- рования входов, а з атем все входные переменные заменяются на Z1, ...ZL ,

как зафиксировано в таблице соответс-

твия.

Реализация может быть и иной при ис- пользовании специального кодирования состояний МПА.

Можно в код каждого состояния МПА внести его номер варианта соответствия

и убрать КС R.

(Подобное кодирование рассмотрено в

разделе 2.3)

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru Пример

(Для краткости примера не рассматриваем функцию выходов.)

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Отсюда получим схему формирования Z1 и Z2

               
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru
    Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru  
R1 R2 Q1 0 0 0 0 1 0 1 0 1 1 1 0 1 0 0
     
Þ
 
 

Теперь для Z1 и Z2 имеем

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Закодируем S0 ¸ S4

           
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru  
R1 R2 Q1 0 0 0 0 1 0 1 0 1 1 1 0 1 0 0
   
Þ
 

410 Далее можно построить схему

Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Схема без мультиплексирования имела бы вид :

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Итак мультиплексирование дало КС с числом входов на 2 меньше.

Если бы мы строили КС на микро- схемах ПЗУ, то нам потребовалось бы ПЗУ объемом в 4 раза меньше.

Варианты схем МПА. Кодирование состояний МПА.

ОА как правило представляют собой автоматы Мили по выходам оповеща- ющих сигналов. При этом УА является автоматом Мили с задержкой или авто- матом Мура.

Автоматы Мура , как правило, реализу-

ются схемой вида :

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

КС jобычно строится на базе ПЛМ (ПЗУ при малом числе входов), а КС Y - чаще на базе ПЗУ.

Перед КС j может быть схема мульти-плексирования входов, если число их ве-

лико. В этом случае КС j может стро-

иться на базе ПЗУ.

Иногда схема строится так, что функции

выходов получаются непосредственно

на выходах ЭА (полностью или частич-

но) как описано в 2.3.

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Схемы с дешифрацией состояний ис- пользуются редко и строятся для не-

больших МПА на базе схем малой сте- пени интеграции. (см.3.15.1)

Автоматы Мили с задержкой (см. 4.2.) содержат КС j и КС Y функции кото- рых зависят от одних и тех же перемен- ных.

 
  Пример построения автома- та Мили по МСА с миними- зацией числа состояний - student2.ru

Выбор способа кодирования состояний

МПА в основном зависит от способа

реализации КС в МПА.

Если КС строятся на базе ПЗУ, кодиро-

вание может быть произвольным, если
yi ¹ Qi .

Если КС строятся на ПЛМ, кодирование целесообразно выполнять подобно тому,

как это показано в 3.15.2.

Для схем с дешифрацией состояний це- лесообразно выполнять кодирование с использованием приемов, описанных в разделе 2.3.

Кодирование состояний, учитывающее взаимосвязь функций возбуждения и

выходов, используется редко из-за того,

что число выходов обычно заметно бо-

льше числа ЭА.

Выбор варианта схемы МПА связан со спецификой реализуемого автомата и осуществляется по результатам пробно-

го синтеза.

Наши рекомендации