Теория автоматов

Рисунок 7 Гонки в цифровом автомате

Если после воздействия на вход автомата сигнала х_i автомат попадает в состояние,  которое имеет код (0010), а затем на вход его поступает сигнал x_k, который должен перевести автомат в состояние с кодом (1011), то во время этого перехода должны переключиться два элемента памяти. При этом возможны промежуточные переключения в состояния  с кодами (1010) или (0011), не входящие в программу работы автомата. Избежать критических состязаний элементов памяти можно, кодируя состояния таким образом, чтобы все переходы совершались между состояниями, закодированными соседними кодами. Кодирование смежных состояний соседними кодами называется противогоночным  кодированием. Такие коды, как правило, избыточны. Кроме того, для таких кодов существуют ограничения:

• невозможно использование противогоночного кодирования при наличии в графе автомата циклов нечетной длины;
• если пара соседних вершин второго порядка имеет более двух  промежуточных состояний, соседнее кодирование также невозможно.
• существуют такие случаи, когда такое кодирование невозможно без введения дополнительных меток в ГСА. 

Поэтому такой метод борьбы с  гонками практически не применяется.

Аппаратные методы борьбы с гонками

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

Другой способ ликвидации гонок состоит в использовании двухтактной памяти. В этом случае каждый элемент памяти дублируется, причем переключение второго слоя триггеров происходит по отсутствию тактирующего сигнала. Сигналы обратной связи снимаются  со второго слоя триггеров, а поступление сигналов возбуждения на входы триггеров  и сигналов обратной связи на входы схемы оказываются разнесенными во времени, что и устраняет причину гонок. 

Замена входных переменных и  кодирование состояний

Обычно число переменных, от которых  существенно зависит каждый переход  в микропрограммном автомате (МПА), невелико по сравнению с мощностью множества входных переменных. Пусть МПА задан таблицей переходов-выходов, Табл. 1. Рассмотрим способ реализации МПА, основанный на замене множества входных переменных Х множеством новых переменных Р, содержащим, как правило, существенно меньшее число элементов. Обозначим через X{a_m} множество входных переменных, определяющих все переходы автомата из состояния a_m. В рассматриваемом примере :

X(a₁)={x₁}, X(a₂)=Æ,  X(a₃)={x₇,x₈}, X(a₄)={x₁, x₂, x₃},   X(a₅) = {x₄, x₆}, X(a₆) = {x₅, x₇}, X(a₇)=Æ,   X(a₈) = {x₆}.

Из этих выражений видно, что  наибольшее число переменных (три) случается  на переходе из состояния а₄. Обозначим это число в общем случае через G  и образуем новое множество переменных P={p₁, p₂ , ... , p_G}. Ясно, что мощность этого множества меньше мощности множества входных переменных Х. На практике  бывает значительно меньше.  Тогда каждую переменную из множества  Х можно заменить переменной из множества Р так, чтобы p_g =x_l,  если в состоянии a_m переменная  x_l  заменена переменной  p_g.

Предположим, что в примере замена переменных уже сделана так, как  это представлено в Табл. 2. В этой таблице на пересечении строки  a_m и столбца p_g  записан элемент x_l , если в состоянии a_m переменная x_l  заменяется переменной p_g.

Таблица 32

am	as	X(am,as)	[am]	[as]	P(am, as)	Yt	D1  D2  D3	h
a1	a1 a3	`x1 x1	000	000 001	`p1 p1	-            Y0 y7                 Y8	0    0    0 0    0    1	1 2
a2	a3	1	011	001	1	y10 y11         Y4	0    0     1	3
a3	a6 a8 a2	x7 `x7   x8 `x7 `x8	001	101 111 011	p2 `p2p3 `p2`p3	y10 y11         Y4                    Y0 y2 y5 y10          Y1	1    0     1 1    1     1 0    1     1	4 5 6
a4	a1 a3 a7 a4	x1   x3 x1 `x3 `x1   x2 `x1 `x2	010	000 001 100 010	p1p3 p1`p3 `p1p2 `p1`p2	y3 y4            Y2 y1 y3 y4        Y3 y3 y4             Y7 y1                         Y6	0    0     0 0    0     1 1    0     0 0    1     0	7 8 9 10
a5	a4 a5 a8	x4  x6 x4 `x6 `x4	110	010 110 100	p1p2 p1`p2 `p1	y6 y13                 Y9 y6 y13                  Y9 y6 y8                    Y5	0    1     0 1    1     0 1    0     0	11 12 13
a6	a2 a3 a8	x5 `x5 x7 `x5`x7	101	011 001 111	p1 `p1p2 `p1`p2	y10 y11                Y4 y12                        Y10 y10 y11                 Y4	0    1     1 0    0     1 1    1     1	14 15 16
a7	a5	1	100	110	1	y1                           Y6	1    1     0	17
a8	a8 a5	x6 `x6	111	111 110	p2 `p2	-                    Y0 y9 y11              Y7	1    1     1 1    1     0	18 19

 

Предположим, что связь входных  переменных и состояний, переход  из которых они инициируют, а также  новые переменные, заменяющие исходные, представлены в Табл. 2. В этой таблице в столбцы  p₁, p₂, p₃  записаны имена новых переменных, от которых существенно зависит переход из состояния  a_m в любое состояние a_s.  Из таблицы видно, что р₁ должна быть равна х₁ в состояниях а₁ и а₄,  х₄ в состоянии а₅, х₅ в состоянии а₆. Тогда выражение для р₁ будет иметь вид

p₁ =a₁x₁ Ú a₄x₁ Ú a₆x₅.

Действительно, если МПА находится в состоянии а₁, то а₄ = а₅ = а₆ = =0, а а₁ = 1, поэтому р_{1 =} х₁ . Выражения для р₁,  р₂, и р₃ можно получить непосредственно из табл. 2. Однако, если в какой либо клетке данного столбца таблицы стоит прочерк, то функция не полностью определенная, т.е.   переменная p_g может быть равна любой переменной в состоянии a_m.  Точно так же переменная р₁ не определена в состояниях а₂, а₇ и а₈.  В связи с этим в выражение для р₁ можно добавить всевозможные  слагаемые: a₂x_t, a₃x_t, a₇x_t,   a₈x_t, используя их для упрощения р₁. В качестве x_t следует выбирать только переменные из столбца р₁. Тогда выражение для р₁ примет вид

p₁ = a₁x₁ Ú a₄x₁ Ú a₅x₄ Ú a₆x₅ Ú [(a₂ Ú a₃ Ú a₇ Ú a₈) & (x₁ Ú x₄ Ú x₅)],

где доопределяющие слагаемые заключены  в квадратные скобки. Для р₂ и р₃ получим аналогичные выражения и преобразуем их таким образом, чтобы дизъюнктивный сомножитель при каждой исходной переменной  содержал имена тех  состояний, переход из которых зависит от этой переменной, и тех состояний, которые не зависят от этой переменной.

p₁ = (a₁ Ú a₄ Ú [a₂ Ú a₃ Ú a₇ Ú a₈] )x₁ Ú (a₅ Ú  [a₂ Ú a₃ Ú a₇ Ú a₈] )x₄ Ú

(a₆ Ú  [a₂ Ú a₃ Ú a₇ Ú a₈] )x₅;

p₂ = (a₃ Ú a₆ Ú [a₁ Ú a₂ Ú a₇] )x₇ Ú (a₄ Ú [a₁ Ú a₂ Ú a₇] )x₂  Ú (a₅ Ú a₈ Ú [a₁ Ú a₂ Ú a₇] )x₆;

p₃ = (a₃ Ú [a₁  Úa₂ Ú  a₅ Ú a₆ Ú  a₇ Ú  a₈] )x₈ Ú (a₄ Ú  [a₁  Úa₂ Ú  a₅ Ú a₆ Ú  a₇ Ú  a₈] )x₃.

 

Для кодирования  состояний МПА используем диаграмму  Вейча, размещая в ней имена состояний таким образом, чтобы они склеивались между собой, образуя интервалы наименьшего ранга. В каждой склейке могут участвовать метки состояний, соответствующие переменной x_j, в данном столбце табл.2, и метки состояний, занесенных в квадратные скобки данного уравнения. Если для кодирования состояний используются не все возможные кодовые комбинации, соответствующие всем наборам значений внутренних переменных, то неиспользуемые коды образуют области неопределенности функции (диаграммы), которые могут участвовать в любых склейках. Необходимо только следить за тем, чтобы в склейку, определяющую конъюнкцию при переменной  xj,  не попадали метки состояний , для которых обозначен переход в другие состояния под действием других переменных в этом же столбце таблицы. Очевидно, что разным способам размещения меток в диаграмме  будут соответствовать разные выражения, определяющие новые внешние переменные МПА. Искусство разработчика состоит в минимизации суммарной сложности  выражений, определяющих значения новых переменных.

 

 

a5	a8	a2	a4
a7	a6	a3	a1

Таблица 33

 

Pg am	p1	p2	p3
a1	x1	-	-
a2	-	-	-
a3	-	x7	x8
a4	x1	x2	x3
a5	x4	x6	-
a6	x5	x7	-
a7	-	-	-
a8	-	x6	-

 

 

 

 

 

В правой части Табл. 2  приведен возможный вариант  кодирования  состояний. В этом случае уравнения  для новых входных переменных микропрограммного автомата примут вид:

p₁ = `t<sub>1</sub> x<sub>1</sub> Ú  t<sub>1</sub>t<sub>2</sub>x<sub>4</sub> Ú `t₂ t₃x₅,

p₂ =  `t<sub>2</sub>x<sub>7</sub> Ú `t₁`t₃x₂ Ú t₁t₂x₆,

p₃ = `t₂x₈ Ú t₂x₃.

 

Введем в структурной таблице  МПА, Табл. 1, дополнительный столбец  P(a_m, a_s),  в котором входные переменные из множества Х заменены переменными p₁, p₂, p₃  в соответствии с Табл.2. В столбцы [a_m], [a_s] запишем коды состояний МПА в соответствии с размещением меток   в диаграмме Вейча, показанном в правой части Табл.2, и определим функции возбуждения элементов памяти, а именно входные сигналы D- триггеров.

Следующим этапом  проектирования МПА является построение логических функций возбуждения элементов  памяти. Простейшим способом является построение этих функций непосредственно по таблице переходов-выходов (тривиальная реализация).

D₁ = a₃(p₂Ú`p<sub>2</sub>p<sub>3</sub>) Ú a<sub>4</sub>`p₁p₂ Ú a₅(p₁`p<sub>2</sub>Ú`p₁) Ú a₆`p<sub>1</sub>`p₂ Ú a₇ Ú  a₈(p₂ Ú`p₂);

D₂ = a₃(`p<sub>2</sub>p<sub>3</sub> Ú `p₂`p<sub>3</sub>) Ú a<sub>4</sub>`p₁`p<sub>2</sub> Ú  a<sub>5</sub>(p<sub>1</sub>p<sub>2</sub> Ú p<sub>1</sub>`p₂) Ú a₆(p₁ Ú`p<sub>1</sub>`p₂)   Ú  a₇ Ú  a₈(p₂ Ú `p₂);

D₃ = a₁p₁ Ú a₂  Ú a₃(p₂  Ú `p<sub>2</sub>p<sub>3</sub> Ú `p₂`p<sub>3</sub>) Ú a<sub>4</sub>p<sub>1</sub>`p₃ Ú a₆(p₁ Ú `p<sub>1</sub>p<sub>2</sub> Ú `p₁`p₂) Ú a₈p₂.

Преобразуя эти выражения с использованием правил склеивания, обобщенного склеивания и поглощения, получим:

D₁ = a₃(p₂ Ú p₃) Ú a₄`p<sub>1</sub>p<sub>2</sub> Ú a<sub>5</sub> (`p₁ Ú  `p<sub>2</sub>) Ú a<sub>6</sub>`p₁`p₂ Ú a₇ Ú a₈;

D₂ =  a₃`p<sub>2</sub> Ú a<sub>4</sub>`p₁`p<sub>2</sub> Ú a<sub>5</sub>p<sub>1</sub>  Ú a<sub>6</sub>(p<sub>1</sub> Ú `p₂) Ú a₇ Ú a₈;

D₃ = a₁p₁ Ú a₂ Ú a₃ Ú a₄p₁`p₃ Ú a₆ Ú a₈p₂.

Можно проверить, что  суммарная сложность схем, реализующих  преобразование переменных и функции возбуждения элементов памяти, меньше, чем при тривиальной реализации функций исходной таблицы. При больших таблицах этот выигрыш более существен.

Замену переменных и кодирование состояний автомата можно выполнять различными способами, которые будут приводить к различным выражениям для функций  D₁, D₂, D₃ и различным значениям сложностей схем. Поэтому важно выполнить замену переменных и кодирование таким образом, чтобы обеспечить минимальное число термов в окончательных уравнениях. С этой целью рекомендуется руководствоваться следующими правилами:

• до замены переменных произвести минимизацию числа строк таблицы переходов-выходов структурного автомата, так как это способствует уменьшению числа переменных, определяющих переход в строках таблицы;
• при замене переменных нужно стремиться  поместить каждую переменную x_i в одном столбце таблицы замены, что, однако, не всегда возможно;
• при кодировании состояний важно, чтобы дизъюнкции в круглых скобках склеились в одну конъюнкцию.

Кодирование микрокоманд

О кодировании микрокоманд имеет  смысл говорить только для случая построения автомата Мили. В принципе выходные сигналы автомата Мили формируются из тех же конъюнкций, из которых строились функции возбуждения элементов памяти автомата.  Так что можно использовать имеющиеся термы, полученные при тривиальной реализации, и сформировать из них  микрокоманды. Так как некоторые микрооперации выполняются более чем в одной микрокоманде,  для последующего формирования сигналов, инициирующих выполнение микроопераций, используются дизъюнкции микрокоманд. Например, для выходных сигналов в Табл.1 микрокоманды имеют следующий состав: