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

Обычно число переменных, от которых существенно зависит каждый переход в микропрограммном автомате (МПА), невелико по сравнению с мощностью множества входных переменных. Пусть МПА задан таблицей переходов-выходов, Табл. 32. Рассмотрим способ реализации МПА, основанный на замене множества входных переменных Х множеством новых переменных Р, содержащим, как правило, существенно меньшее число элементов. Обозначим через 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.

Предположим, что в примере замена переменных уже сделана так, как это представлено в Табл. 33. В этой таблице на пересечении строки 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₃.

 

 

a5     a8   a2 t2 a4 t3 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 -

 

 

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

В правой части Табл. 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 или 2. Для этого в граф-схему алгоритма добавляют пустые операторные вершины, которым не соответствуют никакие микрокоманды. Они обозначаются Y_e. При этом число строк таблицы сокращается, но число состояний автомата (число меток на ГСА) может увеличиться. При выборе желаемой длины условного перехода следует учитывать это обстоятельство.

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

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

Y0 = Æ;	Y1 = {y2, y5, y10};	Y2 = {y3, y4};	Y3 = {y1, y3 , y4};
Y4 = { y10, y11};	Y5 = {y6, y8};	Y6 = {y1};	Y7 = {y9, y14};
Y8 = {y7};	Y9 = {y6, y13};	Y10 = {y12}.

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

 

⇐ Предыдущая78910111213141516Следующая ⇒

Поделиться: