Методические указания к выполнению курсового проекта «Проектирование процессора эвм» по курсу «Организация эвм, комплексов и систем» для студентов дневного отделения специальности 2201 Ижевск 2001г (стр. 8 из 12)

Y_i

, (1)

где

-функция перехода от Y_i к Y_j; Y_j- отмеченная булева функция.

Формулы вида (1) носят название формул перехода. Множество формул перехода для всех i=0,1,…,T образует систему формул перехода . Систему формул перехода для объединенной ГСА получим в виде подсистем формул перехода для каждой из объединенных подматриц. Например, для подматрицы М₀³ имеем формулу перехода:

= . (2)

Представление формулы перехода в виде

Y_i

x_lA

_lB,

где x_l

{x₁,…,x_L,p₁,p₂}, а A и B - подформулы перехода, не зависящие от x_l, носит название приведения (разложения) формулы перехода по переменной x_l. Продолжая приведение подформул А и B по другим переменным до тех пор, пока во внутренних скобках не окажутся выражения вида

(x_pY_n

_pY_r),

x_p

{ x₁,…,x_L,p₁,p₂}; Y_n,Y_r

{Y₁,…,Y_T,Y_K },

получим скобочную Формулу перехода для оператора Y_i .

Если в некоторой строке объединенной подматрицы во всех ненулевых членах некоторая переменная x_p встречается только без инверсии (x_p) или только с инверсией (

_p), этой переменной в ГСА соответствует ждущая условная вершина, и при получении скобочной формулы перехода эту переменную нужно прежде всего вынести за скобку. Получим выражение вида Y_i

x_p (А) или Y_i

_p (A), где А - подформула, не содержащая x_p.

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

I). Если число Q объединяемых ГСА меньше 2^N, т.е. не все наборы значений переменных p₁,…,p_N используются для кодирования МСА M₁,…,M_Q, все формулы перехода не определены на неиспользуемых наборах значений переменных p₁,…,p_N.

2). Если оператор Y_t не встречается в каких-либо МСА M_q(q=1,…,Q),то формула перехода для Y_t не определена на тех наборах значений переменных, которыми закодирована МСА М_q . Так, выражение (2), дополненное термами, включающими в себя неиспользованный код операции

, имеет вид:

.

Это дает возможность сократить переменную p₁ . После приведения к скобочной форме формулы перехода для Y₄ получим:

. (3)

Скобочной формуле перехода однозначно соответствует подграф ГСА (рис.17).

Рис. 15. Разбиение МСА М1

Рис. 16. Граф объединяемых подматриц

Рис. 17. Подграф объединенной ГСА

На основе объединенных подматриц получаем следующую систему скобочных формул перехода:

М

: ( (p₂ ( ) ( ( ))) (

(

( )));

Y₂

p₂(

)

(

(

));

( ) ( ( )); (4)

M

: ;

:

: ;

;

;

.

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

M11	Y1	Y4	Y5	M12	Y2	M14	YK
Y0			x1x3x6	Y1	x2	Y5	x4
				Y6	1
Y2		x3x6
				M13	Y3	Y6
Y3		x3x6	Y4		x4x3

а)

M21	Y1	Y12	Y4	Y7	M22	Y2	M23	Y3
Y0		x7			Y1	x2	Y4	x4
Y2		x5
Y3		x5	M24	YK
Y12	1
б)	Y7	1

M31	Y1	Y4	Y7	M32	Y2	M33	Y3
Y0			x1x5	Y1	x2	Y4	x4
Y2		x5
Y3		x5	M34	YK
в)	Y7	1

Рис. 18. Подматрицы, полученные в результате разбиения :